How does counting lines over a finite field produce a Gaussian coefficient?
A finite field replaces the continuum of coordinates by a finite arithmetic system. The smallest example is $\mathbb F_2=\{0,1\}$, with addition and multiplication modulo $2$. In $\mathbb F_2^3$, a vector is a triple of bits, addition is coordinatewise, and a subspace contains zero and is closed under addition and scalar multiplication. A basis is a linearly independent spanning list; its length is the dimension. A $k$-dimensional subspace has $2^k$ vectors because its basis coefficients can be chosen independently.
A vector line means a one-dimensional subspace. Every nonzero vector in $\mathbb F_2^3$ generates a different vector line, so there are seven. Over a field $\mathbb F_q$ with $q$ elements, each vector line has $q-1$ nonzero vectors; distinct vector lines share none. Consequently the number of vector lines in $\mathbb F_q^n$ is
$$\frac{q^n-1}{q-1}=1+q+\cdots+q^{n-1}.$$
The same division principle counts higher-dimensional subspaces: count ordered independent lists, then divide by the number of ordered bases belonging to each subspace. For $0\le k\le n$, write $\genfrac{[}{]}{0pt}{}{n}{k}_q$ for the resulting Gaussian binomial coefficient. At step $i$, the previously chosen $i$ vectors span $q^i$ vectors, so there are $q^n-q^i$ choices outside that span. Thus
$$\genfrac{[}{]}{0pt}{}{n}{k}_q=\prod_{i=0}^{k-1}\frac{q^n-q^i}{q^k-q^i}.$$
The empty product is $1$. This counts subspaces, whereas the ordinary binomial coefficient counts subsets. The denominator is essential: different bases often describe the same geometric object.
To pass from vector spaces to projective geometry, regard vector lines as points and two-dimensional vector subspaces as projective lines. Incidence means containment. Two distinct points span exactly one two-dimensional subspace, hence lie on exactly one projective line. In $\mathbb F_2^3$, every such subspace has three nonzero vectors, so a projective line contains three points. There are seven projective lines because $(7\cdot6)/(3\cdot2)=7$. Each point lies on three lines: its six other points occur in pairs on those lines. This is the Fano plane, with $21$ point-line incidences.
These definitions, the basis-counting argument, and the following complete instance are the chapter foundation. They suffice for the core investigation without the numbered extensions. Review binomial coefficients and identities, combinatorial designs, geometric combinatorics, and coding theory and combinatorial designs for connections to earlier chapters.
How does counting lines over a finite field produce a Gaussian coefficient?
Label a nonzero vector $(x,y,z)$ by the integer $j=x+2y+4z$. The complete point list is:
| Label | Vector | Label | Vector |
|---|---|---|---|
| $1$ | $(1,0,0)$ | $4$ | $(0,0,1)$ |
| $2$ | $(0,1,0)$ | $5$ | $(1,0,1)$ |
| $3$ | $(1,1,0)$ | $6$ | $(0,1,1)$ |
| — | — | $7$ | $(1,1,1)$ |
For distinct nonzero vectors $u,v$, the corresponding projective line consists of $u,v,u+v$. Here are all seven lines, written as sets of point labels:
$$123,\quad145,\quad167,\quad246,\quad257,\quad347,\quad356.$$
For example, $1+4=5$ in vector arithmetic, and the associated subspace is $\{0,1,4,5\}$. Integer addition would give the wrong result for $1+3$: vector addition instead gives label $2$. Computationally, labels add by bitwise exclusive-or.
Task. Count the ordered bases of one two-dimensional subspace and explain why the list is complete.
Solution. Choose any of its three nonzero vectors first, then either of the other two. Each pair is independent over $\mathbb F_2$, giving six bases. The ambient space has $7\cdot6=42$ ordered independent pairs. Dividing by six gives seven subspaces, exactly the seven distinct triples displayed above. Revisit this question over $\mathbb F_3$: each projective point will have two vector representatives rather than one.
42.1 Finite fields and vector spaces
Optional extension; not required to complete the chapter foundation.
A field permits division by every nonzero element. A finite field has order $q=p^r$, where $p$ is prime and $r\ge1$. Its prime subfield is $\mathbb F_p$; its additive structure is an $r$-dimensional vector space over that subfield. Fields of every prime-power order exist and are unique up to isomorphism. These classification facts are background here; their full proofs require irreducible polynomials and splitting fields. Arithmetic modulo a composite integer is generally not a field: in $\mathbb Z/4\mathbb Z$, $2\cdot2=0$ although $2\ne0$.
A concrete extension avoids treating $\mathbb F_4$ as integers modulo four. Let
$$\mathbb F_4=\mathbb F_2[t]/(t^2+t+1),\qquad\alpha=t\bmod(t^2+t+1).$$
The defining polynomial has no root in $\mathbb F_2$, so it is irreducible of degree two. Its quotient is a field, with elements $0,1,\alpha,1+\alpha$ and relation $\alpha^2=\alpha+1$. Thus $\alpha(\alpha+1)=1$. This verifies inverses explicitly for the two unfamiliar nonzero elements.
For an $n$-dimensional vector space $V$ over $\mathbb F_q$, a basis identifies $V$ with $\mathbb F_q^n$, but changing the basis changes coordinates rather than the space. A linear map $T:V\to W$ has kernel $\ker T$ and image $\operatorname{im}T$; rank-nullity gives $\dim V=\dim\ker T+\dim\operatorname{im}T$. Counting vectors in these spaces yields $\lvert V\rvert=\lvert\ker T\rvert\lvert\operatorname{im}T\rvert$: each fiber over the image is a kernel coset.
Solved example. Take $T:\mathbb F_2^3\to\mathbb F_2$, $T(x,y,z)=x+y$. The image contains both field elements. The kernel consists of $(0,0,0),(1,1,0),(0,0,1),(1,1,1)$ and has dimension two. Each value has four preimages, accounting for all eight vectors.
An $n$-dimensional space over $\mathbb F_q$ has $q^n$ vectors, but a projective point has $q-1$ nonzero representatives. Keep the coefficient field fixed when discussing dimension: $\mathbb F_4^2$ has dimension two over $\mathbb F_4$ and dimension four over $\mathbb F_2$.
Exercise. How many solutions does $x+y+z=1$ have in $\mathbb F_4^3$? Hint: choose two coordinates. Solution: each of the $4^2=16$ pairs $(x,y)$ determines exactly one $z=1-x-y$. The solution set is an affine coset of a two-dimensional kernel, not a vector subspace because it excludes zero.
42.2 Projective and affine geometries
Optional extension; not required to complete the chapter foundation.
The affine space $\operatorname{AG}(n,q)$ has points $\mathbb F_q^n$. An affine $k$-flat is a coset $a+U$, where $U$ is a $k$-dimensional vector subspace. Two cosets of the same $U$ are parallel: they either coincide or are disjoint. There are $q^{n-k}$ distinct cosets of $U$.
The projective space $\operatorname{PG}(n-1,q)$ has one-dimensional subspaces of $\mathbb F_q^n$ as points. A projective $j$-flat comes from a $(j+1)$-dimensional vector subspace. Homogeneous coordinates $[x_1:\cdots:x_n]$ identify nonzero scalar multiples. This shift in dimension explains why a projective line is not a vector line.
Projective completion records directions as points at infinity. Embed the affine plane by $(x,y)\mapsto[x:y:1]$ in $\operatorname{PG}(2,q)$. Points with final coordinate zero form the line at infinity. Parallel affine lines acquire the same point there; different directions acquire different points.
Projective and affine geometries: a worked example
In $\operatorname{AG}(2,2)$ the four points are $(0,0),(1,0),(0,1),(1,1)$. Its six lines fall into three parallel classes:
| Direction | First line | Second line | Point at infinity |
|---|---|---|---|
| $(1,0)$ | $y=0$ | $y=1$ | $[1:0:0]$ |
| $(0,1)$ | $x=0$ | $x=1$ | $[0:1:0]$ |
| $(1,1)$ | $x+y=0$ | $x+y=1$ | $[1:1:0]$ |
Each equation has exactly two solutions. Every unordered pair of distinct affine points determines its difference vector and therefore a unique line; the six lines account for all $\binom42=6$ pairs. Adding the appropriate point at infinity turns each affine line into a three-point projective line. The three new points form a seventh line, producing seven points and seven lines in total.
With the chapter's binary labels, affine points have labels $4,5,6,7$, and points at infinity have labels $1,2,3$. For instance, $y=0$ becomes line $145$ and $x+y=1$ becomes line $356$. The completion is precisely the Fano plane already listed, not a separate incidence structure.
Exercise. Count affine lines in $\operatorname{AG}(2,3)$. Hint: count directions, then cosets. Solution: there are $(3^2-1)/(3-1)=4$ directions, each with three cosets. Hence there are twelve lines, each containing three points. The $9\cdot4=36$ point-line incidences also equal $12\cdot3$.
42.3 Gaussian binomial coefficients and subspace counting
Optional extension; not required to complete the chapter foundation.
Let $\operatorname{Gr}_q(n,k)$ denote the set of $k$-dimensional subspaces of $\mathbb F_q^n$, called a finite Grassmannian. Its cardinality is $\genfrac{[}{]}{0pt}{}{n}{k}_q$. The ordered-basis argument in the foundation proves the product formula and its integrality; the individual fractions need not be integers.
Solved example. For two-dimensional subspaces of $\mathbb F_2^4$,
$$\genfrac{[}{]}{0pt}{}{4}{2}_2=\frac{(16-1)(16-2)}{(4-1)(4-2)}=35.$$
The numerator counts $210$ ordered independent pairs. Every subspace contributes six such pairs. None of the $35$ subspaces is distinguished until additional geometry or a coding constraint is imposed.
Fix a hyperplane $H$ of dimension $n-1$. Subspaces $U\subseteq H$ contribute $\genfrac{[}{]}{0pt}{}{n-1}{k}_q$. If $U$ is not contained in $H$, then $U\cap H$ has dimension $k-1$. For each fixed intersection $W$, choose a vector $e$ outside $H$. Every such $U$ is $W+\langle e+h\rangle$ for some $h\in H$. Two choices give the same subspace exactly when they differ by an element of $W$. There are $\lvert H/W\rvert=q^{n-k}$ choices. Therefore
$$\genfrac{[}{]}{0pt}{}{n}{k}_q=\genfrac{[}{]}{0pt}{}{n-1}{k}_q+q^{n-k}\genfrac{[}{]}{0pt}{}{n-1}{k-1}_q.$$
For $1\le k\le n-1$ this is a genuine two-case proof; boundary values are $1$. A fixed nondegenerate bilinear form supplies the bijection $U\mapsto U^\perp$, proving symmetry under $k\leftrightarrow n-k$.
The diagram lists all seven two-dimensional subspaces of $\mathbb F_2^3$. Each row gives the three nonzero point labels; add zero to recover the vector subspace. The right column records the six ordered bases of that row, without confusing basis lists with distinct subspaces.
Exercise. Count flags $P\subset L$ in $\mathbb F_2^3$ with dimensions one and two. Hint: count from either endpoint. Solution: seven two-dimensional spaces each contain three vector lines, giving $21$. Conversely, for each vector line $P$, containing two-dimensional spaces correspond to vector lines in the two-dimensional quotient $\mathbb F_2^3/P$, of which there are three. This again gives $7\cdot3=21$.
42.4 Finite projective planes
Optional extension; not required to complete the chapter foundation.
A projective plane is an incidence structure in which every pair of distinct points has a unique common line, every pair of distinct lines has a unique common point, and there exist four points with no three collinear. A finite plane of order $q$ has $q+1$ points on each line and $q+1$ lines through each point. Its number of points and lines is
$$v=q^2+q+1.$$
For the construction $\operatorname{PG}(2,q)$, two independent vector representatives span a unique two-dimensional space. Two distinct two-dimensional subspaces of a three-dimensional space intersect in dimension one: the dimension formula gives a lower bound of one, and an intersection of dimension two would make them equal. These prove the two uniqueness axioms. The points represented by the three coordinate vectors and their sum give four points with no three collinear.
A two-dimensional subspace has $(q^2-1)/(q-1)=q+1$ projective points. Lines through a point correspond to vector lines in a two-dimensional quotient, so their number is also $q+1$. Counting the points other than a fixed point along its $q+1$ lines gives $1+q(q+1)=v$. Dual counting gives the same number of lines.
Solved example. In $\operatorname{PG}(2,3)$ there are thirteen points, thirteen lines, four points per line, and $52$ incidences. Normalizing the first nonzero coordinate of a representative to one gives nine representatives $(1,a,b)$, three $(0,1,b)$, and one $(0,0,1)$, totaling thirteen without duplicates.
The field construction gives a plane for every prime power. The foregoing argument does not classify all finite projective planes or all possible orders; no such classification is needed here.
Exercise. How many lines avoid a specified point in a plane of order $q$? Hint: subtract the lines through it. Solution: $v-(q+1)=q^2$. For the Fano plane, four lines avoid any specified point; this can be checked directly in the seven-line list.
42.5 Blocking sets and arcs
Optional extension; not required to complete the chapter foundation.
A blocking set $B$ meets every projective line. A set containing an entire line is called trivial in this convention, since any two projective lines meet. An arc $A$ is a point set with no three collinear. Blocking asks for unavoidable contact; an arc asks how many points can coexist without a forbidden triple.
Every blocking set in a plane of order $q$ has at least $q+1$ points. If $B$ is not the entire point set, choose a point $x$ outside it. The $q+1$ lines through $x$ must each meet $B$, and their parts outside $x$ are disjoint. They require at least $q+1$ distinct points. The entire point set also satisfies this bound. A line attains it.
An arc has at most $q+2$ points: choose $x\in A$. Every other arc point lies on one of the $q+1$ lines through $x$, with at most one other arc point per line. This elementary bound is valid without asserting that equality is possible for every order.
Solved example. In the Fano plane, $B=\{1,2,3\}$ is a blocking set of minimum size three. Its complement $A=\{4,5,6,7\}$ is an arc: inspecting the seven triples shows none contained in $A$. The general arc bound is four when $q=2$, so this arc is maximum. A five-point set cannot be an arc: from one selected point, its four companions occupy only three lines, forcing two companions on the same line and hence a collinear triple.
Exercise. Does the complement of every line in every projective plane form an arc? Hint: intersect another line with the deleted one. Solution: another line loses one of its $q+1$ points and retains $q$. For $q\ge3$ it therefore supplies a collinear triple in the complement. The Fano example relies specifically on $q=2$; it cannot be extrapolated unchanged.
42.6 Finite-field incidence problems
Optional extension; not required to complete the chapter foundation.
Let $P$ be a set of points and $\mathcal L$ a set of lines in a projective plane of order $q$. Define $I(P,\mathcal L)$ as the number of incident pairs. Write $B$ for the real $v\times v$ incidence matrix, with rows indexed by points and columns by lines. Although the geometric coordinates belong to a finite field, the following matrix calculation uses real arithmetic.
Every row has $q+1$ ones. Distinct rows have scalar product one, since distinct points share exactly one line. If $I_v$ is the identity matrix and $J_v$ the all-ones matrix, then
$$BB^{\mathsf T}=qI_v+J_v.$$
Let $\mathbf1$ be the all-ones column vector and center the indicator vectors:
$$x=\mathbf1_P-\frac{\lvert P\rvert}{v}\mathbf1,\qquad y=\mathbf1_{\mathcal L}-\frac{\lvert\mathcal L\rvert}{v}\mathbf1.$$
Both are orthogonal to $\mathbf1$. Row and column sums yield $x^{\mathsf T}By=I(P,\mathcal L)-(q+1)\lvert P\rvert\lvert\mathcal L\rvert/v$. The matrix identity gives $\lVert B^{\mathsf T}x\rVert^2=q\lVert x\rVert^2$. Cauchy–Schwarz therefore proves
$$\left\lvert I(P,\mathcal L)-\frac{(q+1)\lvert P\rvert\lvert\mathcal L\rvert}{v}\right\rvert\le\sqrt q\sqrt{\lvert P\rvert\left(1-\frac{\lvert P\rvert}{v}\right)\lvert\mathcal L\rvert\left(1-\frac{\lvert\mathcal L\rvert}{v}\right)}.$$
The main term is the incidence count predicted by uniform density; the error quantifies possible concentration.
Solved example. In the Fano plane take $P=\{1,2,3\}$ and $\mathcal L=\{123,145,167\}$. The three lines contribute $3,1,1$ incidences, so $I=5$. The main term is $27/7$, the deviation is $8/7$, and the bound is $12\sqrt2/7$. Squaring verifies $64\le288$, without relying on rounded numerical values.
Real-plane incidence estimates cannot simply be transplanted. All $q^2$ affine points and all $q(q+1)$ affine lines have $q^2(q+1)$ incidences. This grows like $q^3$, whereas the usual real-plane expression with exponents $2/3$ grows like $q^{8/3}$ for these set sizes. Finite-field algebra supplies extra concentration and changes the scale of the question.
Exercise. Evaluate the bound when $\mathcal L$ contains every projective line. Hint: the centered line indicator vanishes. Solution: its factor $1-\lvert\mathcal L\rvert/v$ is zero. Hence the incidence count is exactly $(q+1)\lvert P\rvert$, consistent with the number of lines through each point.
42.7 Polynomial method over finite fields
Optional extension; not required to complete the chapter foundation.
The bridge to the optional later sections 43.1 and 43.2 is short: choose a polynomial space with more coefficients than evaluation constraints, then restrict a vanishing polynomial to lines. The facts below are supplied here, so those later sections are not entry requirements. For a full primary application of this bridge, see Dvir's paper on finite-field Kakeya sets.
A polynomial $f\in\mathbb F_q[X_1,\ldots,X_n]$ has total degree at most $D$ if every monomial $X_1^{a_1}\cdots X_n^{a_n}$ appearing in it satisfies $a_1+\cdots+a_n\le D$. There are $\binom{n+D}{n}$ such monomials, by introducing a slack exponent and applying stars and bars. Thus, if a finite set $S\subseteq\mathbb F_q^n$ has fewer than this many points, the homogeneous equations $f(s)=0$ have a nonzero coefficient solution. This is a nonzero formal polynomial, not necessarily a nonzero function on the field.
The distinction matters: $X^q-X$ is a nonzero polynomial that vanishes on all of $\mathbb F_q$. A safe uniqueness condition is degree less than $q$ in each variable. Such a polynomial vanishing on every field point must be zero: induct on the number of variables, regarding it as a polynomial in the last variable. At each fixed choice of the others, its $q$ roots force every coefficient to vanish; the induction hypothesis then applies to those coefficient polynomials.
Solved example. Over $\mathbb F_3$, a polynomial $a+bX+cY$ vanishing at $(0,0)$ and $(1,0)$ satisfies $a=b=0$. Taking $c=1$ gives $f=Y$, whose zero set is exactly the three-point horizontal line. Two constraints in a three-dimensional coefficient space have left a nonzero solution. Adding $(0,1)$ forces $c=0$, showing why the strict dimension inequality matters.
Restricting a degree-$D$ polynomial to $a+tv$ gives a univariate polynomial of degree at most $D$. If $D\lt q$ and it vanishes at all $q$ values of $t$, that restriction is identically zero. Its leading coefficient can then constrain the direction $v$, the key step used in section 42.10.
Exercise. Produce a nonzero polynomial of total degree at most two vanishing at any five prescribed points of $\mathbb F_3^2$. Hint: count coefficients, rather than guess a factorization. Solution: the six coefficients of $1,X,Y,X^2,XY,Y^2$ satisfy five homogeneous equations, so their kernel has positive dimension. Because every variable degree is at most two, the resulting nonzero polynomial cannot vanish on all nine field points.
42.8 Finite geometry and combinatorial designs
Optional extension; not required to complete the chapter foundation.
A $2$-$(v,k,\lambda)$ design consists of $v$ points and blocks of size $k$, with each pair of distinct points in exactly $\lambda$ blocks. Let $r$ be the number of blocks through a point and $b$ the total block count. Double counting gives $r(k-1)=\lambda(v-1)$ and $bk=vr$. These equations are necessary constraints, not existence proofs.
Projective planes yield $2$-$(q^2+q+1,q+1,1)$ designs. Their block and point counts coincide, making them symmetric designs. Their incidence-matrix identity in section 42.6 encodes the same pair uniqueness. Affine planes yield $2$-$(q^2,q,1)$ designs with $r=q+1$ and $b=q(q+1)$. Their direction classes partition the point set into disjoint blocks, giving a resolution.
Solved example. The Fano plane is a $2$-$(7,3,1)$ design. A block contains three unordered pairs, and seven blocks contain $21=\binom72$ pairs. The explicit line list verifies that no pair repeats, so every pair occurs once. The count alone would not have ruled out repetition. In the affine plane of order two, the six blocks are all two-element subsets of four points, and its three resolutions are the parallel classes listed earlier.
Geometric construction explains these designs rather than merely matching parameter equations. It also connects the Fano triples to the weight-three supports of the binary Hamming code in the prerequisite chapter: a triple sums to zero exactly when its three vectors form a projective line.
Exercise. Find the parameters of the line design of $\operatorname{AG}(2,3)$. Hint: every point pair has a unique affine line. Solution: $v=9$, $k=3$, $\lambda=1$, $r=4$, and $b=12$. Check $4(3-1)=9-1$ and $12\cdot3=9\cdot4$. The four parallel classes each contain three blocks.
42.9 Subspace codes and Grassmannian combinatorics
Optional extension; not required to complete the chapter foundation.
A subspace code is a collection of vector subspaces used as distinct messages. The subspace distance is
$$d_S(U,W)=\dim U+\dim W-2\dim(U\cap W).$$
For constant dimension $k$, it equals $2(k-\dim(U\cap W))$. Thus maximum separation means minimum overlap. It is a metric: for the triangle inequality, the subspaces $U\cap W$ and $W\cap Z$ inside $W$ give
$$\dim(U\cap Z)\ge\dim(U\cap W)+\dim(W\cap Z)-\dim W,$$
because their intersection lies in $U\cap Z$. Substitution proves $d_S(U,Z)\le d_S(U,W)+d_S(W,Z)$. Nonnegativity, symmetry, and equality only for identical subspaces follow directly.
Solved example. View $\mathbb F_4^2$ as a four-dimensional space over $\mathbb F_2$. Its five one-dimensional $\mathbb F_4$-subspaces become two-dimensional binary subspaces:
$$U_m=\{(t,mt):t\in\mathbb F_4\}\quad(m\in\mathbb F_4),\qquad U_\infty=\{(0,t):t\in\mathbb F_4\}.$$
For $m\ne m'$, a common vector satisfies $(m-m')t=0$, hence $t=0$. The vertical subspace also meets each graph only in zero. These five codewords therefore have pairwise distance four. Write $a=a_0+a_1\alpha$, $b=b_0+b_1\alpha$ and label $(a,b)$ by $a_0+2a_1+4b_0+8b_1$. Their nonzero label sets are:
| Subspace | Nonzero labels |
|---|---|
| $U_0$ | $1,2,3$ |
| $U_1$ | $5,10,15$ |
| $U_\alpha$ | $7,9,14$ |
| $U_{1+\alpha}$ | $6,11,13$ |
| $U_\infty$ | $4,8,12$ |
They partition all fifteen nonzero binary vectors. Such a partition by subspaces is a spread. Any two-dimensional binary subspace contributes three nonzero vectors, so a distance-four constant-dimension code in this ambient space has at most $15/3=5$ codewords. The construction meets that upper bound.
In random linear network coding, transmitted packets are mixed by linear combinations. A receiver may learn a span without learning the original basis; subspaces therefore provide a natural alphabet. Koetter and Kschischang's primary paper develops this coding model. The five-word example illustrates geometry-based separation; it does not by itself specify a complete network protocol or practical performance model.
Exercise. Take $U=\langle e_1,e_2\rangle$ and $W=\langle e_2,e_3\rangle$ in $\mathbb F_2^4$, where $e_i$ are coordinate vectors. Compute their distance. Hint: identify their intersection. Solution: it is $\langle e_2\rangle$, of dimension one, so $d_S(U,W)=2$. Shared dimension reduces separation by two.
42.10 Finite-geometric extremal problems
Optional extension; not required to complete the chapter foundation.
Extremal geometry fixes an incidence or intersection condition and optimizes the size of a configuration. The maximum Fano arc and the five-subspace spread are fully proved examples. A different condition requires an affine line in every direction. A Kakeya set $K\subseteq\mathbb F_q^n$ has, for each nonzero direction vector $v$, some $a$ such that $a+tv\in K$ for every $t\in\mathbb F_q$. Scalar multiples describe the same direction, and the base point may depend on the direction.
An established classical consequence of Dvir's polynomial argument is
$$\lvert K\rvert\ge\binom{q+n-1}{n}.$$
This is a proved lower bound, not a conjecture or a claim of optimality. The original primary paper establishes the finite-field Kakeya theorem. The displayed bound follows from the argument below; no assertion about the current sharp constant or unresolved classification is needed for this chapter.
Proof sketch, with dependencies explicit. Use the coefficient count, the univariate root bound, and the grid uniqueness lemma proved in section 42.7; no further prerequisite is omitted. If $\lvert K\rvert\lt\binom{q+n-1}{n}$, choose a nonzero polynomial $f$ of total degree at most $q-1$ vanishing on $K$. Its degree $d$ is positive, since a nonzero constant cannot vanish on the nonempty set $K$. Let $f_d$ be its homogeneous degree-$d$ part. For every nonzero $v$, a line of direction $v$ lies in $K$, so $f(a+tv)$ has $q$ roots and degree less than $q$. It is identically zero, and its coefficient of $t^d$ is $f_d(v)$. Hence $f_d$ vanishes on every nonzero vector and also at zero because $d\gt0$. Each variable degree is less than $q$, so grid uniqueness forces $f_d=0$, contradicting the choice of the top-degree part. This proves the bound.
Solved example. In $\mathbb F_2^2$, a Kakeya set needs at least $\binom32=3$ points. The set $K=\{(0,0),(1,0),(0,1)\}$ attains this: its three point pairs have directions $(1,0),(0,1),(1,1)$, and a line over $\mathbb F_2$ contains just two points. A two-point set realizes only one direction, so the minimum is exactly three. This exact small result is stronger information than merely checking that the lower bound is satisfied.
The proof turns many complete lines into algebraic constraints on their directions. The spread argument instead turns pairwise disjoint nonzero vectors into a packing bound. Both begin with finite-field structure but optimize different objects: Kakeya sets are point sets with required incidences, while spread codes are collections of subspaces with restricted intersections.
Exercise. Apply the displayed Kakeya bound for $q=3,n=2$. Hint: count polynomials of degree at most two. Solution: $\lvert K\rvert\ge\binom42=6$. If there were at most five points, a nonzero quadratic vanishing on them would restrict identically to all four required directions, forcing its top homogeneous part to vanish on the full grid. This exercise proves a lower bound; it does not claim a six-point construction.
Enumerate a finite geometry and test an incidence or code construction
The core investigation uses only binary arithmetic, spans, and the complete Fano instance in the foundation. The optional code investigation adds extension-field arithmetic and demonstrates how the same counting ideas create a provably optimal small code. In both branches, a finite field supplies exact objects, incidence verification supplies evidence, and a counting argument supplies the extremal certificate.
Enumerate a finite geometry and test an incidence or code construction
Inputs. Use point labels $1,\ldots,7$ for nonzero vectors in $\mathbb F_2^3$, with the bit convention from the motivating problem. Add vectors by exclusive-or. Treat lines and point sets as unordered sets; zero belongs to vector subspaces but is never a projective point.
Warm-up — 20 points. List the eight vectors including zero; compute $\genfrac{[}{]}{0pt}{}{3}{1}_2$ and $\genfrac{[}{]}{0pt}{}{3}{2}_2$; generate the line arising from point labels $2$ and $4$. Deliver the vector table and a one-paragraph basis-counting explanation.
Worked solution. There are eight binary triples. Both Gaussian coefficients are seven. The span of $2$ and $4$ is $\{0,2,4,6\}$ and its projective line is $246$. There are $42$ ordered independent pairs and six per two-dimensional subspace.
Proof — 30 points. Prove that the generated triples form a $2$-$(7,3,1)$ design. Then prove that the minimum blocking-set size is three and the maximum arc size is four. Hints: a pair spans a unique subspace; lines through an unselected point partition the other points; lines through a selected arc point can contain only one companion.
Worked solution. Any distinct nonzero binary vectors are independent. Their span has the unique nonzero triple $\{u,v,u+v\}$, establishing pair uniqueness and block size three. The seven triples consequently form the design. A blocking set of size at most two has an outside point; its three incident lines require three distinct blocking points, a contradiction. Any line supplies a size-three blocking set. An arc point has only three incident lines, so an arc has at most four points. The complement $4567$ of line $123$ attains four, as direct line inspection confirms.
Computation or visual enumeration — 35 points. Generate all triples $\{a,b,a\mathbin{\oplus}b\}$ for $1\le a\lt b\le7$, sort each triple, and remove duplicates. Produce the complete line list, the incidence matrix, and histograms of blocking sets and arcs by cardinality. To classify a subset $S$, test whether every line meets it and whether no line has three points in it. Enumerate all $2^7=128$ subsets, including the empty and full sets.
Expected checks and solution. The line list must be $123,145,167,246,257,347,356$. Every point and every line has degree three; every distinct point pair occurs once; the incidence matrix satisfies $BB^{\mathsf T}=2I_7+J_7$. The complete histograms are:
| Size | Blocking sets | Arcs |
|---|---|---|
| $0$ | $0$ | $1$ |
| $1$ | $0$ | $7$ |
| $2$ | $0$ | $21$ |
| $3$ | $7$ | $28$ |
| $4$ | $28$ | $7$ |
| $5$ | $21$ | $0$ |
| $6$ | $7$ | $0$ |
| $7$ | $1$ | $0$ |
For the size-three arc count, subtract the seven collinear triples from $\binom73=35$. A four-point arc has a three-point complement that meets every line; the preceding minimum argument forces such a three-point blocking set to be a line: if its points were noncollinear, the three pair-lines would cover six of the seven lines through their union, leaving one line disjoint. Equivalently, inspect the seven triples. Thus exactly seven four-point arcs occur. Finally, complementation sends blocking sets to arcs in this plane because a line has exactly three points: a line misses $S$ precisely when it is wholly contained in the complement. This checks the reversed histograms independently.
Interpretation — 15 points. Explain which conclusions are proved beyond the computation. State the exact field and dimension used, and explain why these finite results need not hold unchanged over other fields. Relate the incidence design to parity-check columns of the binary Hamming code: a triple of distinct nonzero columns sums to zero exactly when its support is a Fano line.
Optional extension, ungraded. Enumerate all $35$ two-dimensional subspaces of $\mathbb F_2^4$ by generating and deduplicating spans of independent pairs. Verify that the five triples in section 42.9 are among them, cover labels $1,\ldots,15$ once, and have pairwise trivial intersection. Prove the packing bound $3\lvert\mathcal C\rvert\le15$ and explain why equality certifies optimality. A further exploration may search for other five-subspace spreads; describe that as an enumeration project rather than an unresolved research claim.
Extension solution outline. Each independent pair generates $\{0,a,b,a\mathbin{\oplus}b\}$. There are $15\cdot14/6=35$ distinct subspaces. The five displayed nonzero triples partition the fifteen labels and each is closed under exclusive-or after adjoining zero. Their distance is four. Any competing distance-four constant-dimension code also has disjoint three-element nonzero sets and therefore at most five codewords. This is the promised connection from field arithmetic to a finite-geometric extremal result and a network-coding alphabet.
Assessment and validation scope. Award the warm-up points for correct objects and basis multiplicities, proof points for explicit uniqueness and extremal arguments, enumeration points for deduplication and all incidence/histogram checks, and interpretation points for precise scope and the coding connection. Exhaustive enumeration proves the stated finite instance if the generation and tests are justified; matching a few examples is only experimental evidence. The field-independent projective-plane bounds require the separate proofs given above. No site deployment, physical-network simulation, or general classification is part of this investigation.
Next in the Series
In Chapter 43: The Polynomial Method, we'll explore Encode discrete constraints algebraically to obtain sharp bounds.