Open MathsAll courses

Polynomial pairings on punctured spaces

Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).

The incidence criterion of The glued group and planar balance asks for vectors \(x_v\in K^m\) on the points of an incidence system with \[ \begin{gathered} \sum_{v\in f}x_vx_v^{\mathsf T}=0\ \text{ on every line }f,\\ \sum_{v\in V}x_vx_v^{\mathsf T}=-I_m , \end{gathered} \] and with \(m<|V|\). This lesson constructs such vectors from low-degree polynomials on an affine space \(Q^n\) over a field of characteristic two. Products of two polynomials of degree at most \((q-2)/2\) have degree at most \(q-2\), and such polynomials sum to zero over every full affine line and over the whole space. The interpolation polynomials of a set \(O\) of removed points, the holes, have unit vectors as values at the holes, so removing the holes leaves the total \(-I_m\). The lines themselves only have to avoid the holes; their arrangement is the subject of the next three lessons.

Let \(Q\) be a finite field with \(q\) elements. Its multiplicative group is cyclic (Abstract Algebra II: Judson, Abstract Algebra: Theory and Applications, Corollary 22.11). Polynomials in \(n\) variables are formal polynomials with coefficients in \(Q\); the total degree of a monomial \(X_1^{k_1}\cdots X_n^{k_n}\) is \(k_1+\cdots+k_n\).

1. Interpolation on an index simplex

Enumerate \(Q\) as \(a_0,a_1,\ldots,a_{q-1}\). For \(0\le d<q\) and \(n\ge1\) put \[ \begin{aligned} S_d=\Bigl\{&(a_{k_1},\ldots,a_{k_n}):\\ &k_i\ge0,\ \sum_ik_i\le d\Bigr\}\subseteq Q^n . \end{aligned} \] Since \(d<q\), every index \(k_i\le d\) is a valid index, distinct index tuples give distinct points, and \(|S_d|=\binom{d+n}{n}\), which is also the number of monomials of total degree at most \(d\).

Lemma 1.1 (interpolation; [OpenAI-DF2, Lemma 2.1]). Evaluation on \(S_d\) is a linear isomorphism from the space of polynomials of total degree at most \(d\) to the space \(Q^{S_d}\) of functions on \(S_d\).

Proof. For an index tuple \(k=(k_1,\ldots,k_n)\) with \(\sum_ik_i\le d\) let \[ N_k=\prod_{i=1}^n\prod_{0\le u<k_i}(X_i-a_u), \] a polynomial of total degree \(\sum_ik_i\le d\). At the point with index tuple \(j\), \(N_k\) vanishes if \(j_i<k_i\) for some \(i\), because the factor with \(u=j_i\) is zero. Order the tuples lexicographically. If \(N_k\) is nonzero at the point \(j\), then \(j_i\ge k_i\) for all \(i\), so \(j\) comes after or equals \(k\). The square matrix of values \(N_k(\text{point }j)\) is therefore triangular, with diagonal entries \[ N_k(\text{point }k)=\prod_{i=1}^n\prod_{0\le u<k_i}(a_{k_i}-a_u)\ne0 . \] So the \(\binom{d+n}{n}\) polynomials \(N_k\) have linearly independent evaluations on \(S_d\). They lie in the polynomial space, which has the same dimension, so they form a basis of it, and evaluation is an isomorphism. \(\square\)

In particular, for each point \(o\in S_d\) there is a unique polynomial \(f_o\) of total degree at most \(d\) that equals \(1\) at \(o\) and \(0\) at the other points of \(S_d\).

2. Sums over affine lines

An affine line in \(Q^n\) is a translate \(p+Qw\), \(w\ne0\), of a one-dimensional subspace; it has \(q\) points, parametrized by \(z\mapsto p+zw\).

Lemma 2.1 (line sums; [OpenAI-DF2, Lemma 2.2]). Let \(g\) be a polynomial on \(Q^n\) of total degree at most \(q-2\). Then the sum of the values of \(g\) over every affine line is zero, and so is the sum over \(Q^n\).

Proof. Restricted to a line \(z\mapsto p+zw\), \(g\) becomes a polynomial in \(z\) of degree at most \(q-2\). It suffices to show \(\sum_{z\in Q}z^k=0\) for \(0\le k\le q-2\), with \(z^0=1\). For \(k=0\) the sum is \(q\cdot1=0\) in \(Q\). For \(1\le k\le q-2\), choose \(c\in Q^\times\) with \(c^k\ne1\); it exists because \(Q^\times\) is cyclic of order \(q-1>k\). Multiplication by \(c\) permutes \(Q\), so \(\sum_zz^k=\sum_z(cz)^k=c^k\sum_zz^k\), and \((1-c^k)\sum_zz^k=0\) forces the sum to vanish. Finally, \(Q^n\) is a disjoint union of parallel lines. \(\square\)

The bound \(q-2\) is sharp: \(\sum_{z\in Q}z^{q-1}=q-1=-1\) (Exercise 4.2).

3. The pairing supplied by holes

Proposition 3.1 (the pairing supplied by holes; [OpenAI-DF2, Proposition 2.3]). Let \(q\ge4\) be a power of two, \(Q\) a field with \(q\) elements, \(n\ge1\), \(d_0=(q-2)/2\), \(S=S_{d_0}\subseteq\mathcal A=Q^n\) and \(N_{\rm pt}=q^n\). Let \(\ell\) be an odd prime and \(D=\ell+1\). Let \(O\subseteq S\) be a set of holes with \[ \frac{2N_{\rm pt}}{D^2}\le|O|\le\frac{7N_{\rm pt}}{D^2}, \] and \(\mathcal F\) a family of affine lines contained in \(V=\mathcal A\setminus O\). Let \(K\) be a finite field containing \(Q\). Put \(m=|O|\), \(t=|V|\), and for \(v\in\mathcal A\) \[ x_v=\bigl(f_o(v)\bigr)_{o\in O}\in Q^m\subseteq K^m , \] with the interpolation polynomials \(f_o\) of total degree at most \(d_0\) of Section 1. Then \[ \begin{gathered} 0<m<t\le m\ell^2,\\ \sum_{v\in V}x_vx_v^{\mathsf T}=-I_m,\\ \sum_{v\in f}x_vx_v^{\mathsf T}=0\quad(f\in\mathcal F). \end{gathered} \]

Proof. The entry \((o,o')\) of \(W_v=x_vx_v^{\mathsf T}\) is \(f_o(v)f_{o'}(v)\), the value at \(v\) of a polynomial of total degree at most \(2d_0=q-2\). By Lemma 2.1, \[ \sum_{v\in f}W_v=0\quad(f\in\mathcal F),\qquad\sum_{v\in\mathcal A}W_v=0 . \] For a hole \(o\), the vector \(x_o\) is the unit vector of the coordinate \(o\), because \(f_{o'}(o)=1\) exactly when \(o'=o\) (both lie in \(S\)). Hence \(\sum_{o\in O}W_o=I_m\), and \[ \sum_{v\in V}W_v=\sum_{v\in\mathcal A}W_v-\sum_{o\in O}W_o=-I_m . \] The lines lie in \(V\), so their sums are not affected by the removal.

For the sizes: \(m\ge2N_{\rm pt}/D^2>0\). Since \(\ell\ge3\), \(D\ge4\), and \(m\le7N_{\rm pt}/16<N_{\rm pt}/2\), so \(t=N_{\rm pt}-m>m\). Finally \[ \begin{aligned} \frac tm=\frac{N_{\rm pt}}m-1&\le\frac{D^2}2-1\\ &\le(D-1)^2=\ell^2 , \end{aligned} \] where the last inequality is equivalent to \((D-2)^2\ge0\). \(\square\)

Remark 3.2. The identities are consistent with a regular line system only in suitable characteristic. If every point of \(V\) lies on exactly \(D\) lines of \(\mathcal F\), summing the line identities gives \(D\sum_{v\in V}W_v=0\), that is \(-D\,I_m=0\), so the characteristic of \(K\) must divide \(D=\ell+1\) (Exercise 4.4). This is where the characteristic enters the construction: characteristic two divides \(\ell+1\) for every odd prime \(\ell\).

The vectors \(x_v\) are computed by finite-field linear algebra: \(f_o\) is obtained by inverting the triangular matrix of Lemma 1.1.

4. Exercises

4.1 (easy). Let \(q=4\), \(Q=\{0,1,\omega,\omega^2\}\) with \(\omega^2=\omega+1\), \(n=1\), and enumerate \(a_0=0\), \(a_1=1\). Find \(S_1\) and the interpolation polynomials \(f_0\), \(f_1\) of degree at most \(1\), and check \(\sum_{z\in Q}f_0(z)f_1(z)=0\).

4.2 (easy). Show that \(\sum_{z\in Q}z^{q-1}=-1\), so Lemma 2.1 fails for degree \(q-1\).

4.3 (medium). Show that the number of affine lines through a point of \(Q^n\) is \((q^n-1)/(q-1)\), and that two distinct affine lines meet in at most one point.

4.4 (medium). Let \(K\) be any field, \((V,\mathcal F)\) an incidence system in which every point lies on exactly \(D\) lines, and \(W_v\in\operatorname{Mat}_m(K)\) with \(\sum_{v\in f}W_v=0\) for all lines and \(\sum_vW_v=-I_m\), \(m\ge1\). Show that the characteristic of \(K\) divides \(D\).

5. Solutions

4.1. \(S_1=\{a_0,a_1\}=\{0,1\}\). The polynomials of degree at most one with the prescribed values are \(f_0(z)=1+z\) and \(f_1(z)=z\) (in characteristic two \(-1=1\)). Then \(f_0f_1=z+z^2\), and \(\sum_zz=0+1+\omega+\omega^2=0\), \(\sum_zz^2=\sum_zz=0\), since squaring permutes \(Q\). The degree of \(f_0f_1\) is \(2=q-2\), as Lemma 2.1 requires.

4.2. For \(z\ne0\), \(z^{q-1}=1\) because \(Q^\times\) has order \(q-1\), and \(0^{q-1}=0\). So the sum is \((q-1)\cdot1=-1\) in \(Q\).

4.3. A line through \(p\) is \(p+Qw\); two nonzero vectors give the same line exactly when they are proportional, so the lines through \(p\) correspond to the \((q^n-1)/(q-1)\) one-dimensional subspaces. If two lines share two points \(p\ne p'\), both are \(p+Q(p'-p)\).

4.4. Each point lies on \(D\) lines, so \(\sum_f\sum_{v\in f}W_v=D\sum_vW_v=-D\,I_m\). The left side is zero, so \(D\cdot1=0\) in \(K\).

References