No set with a line in every direction is small

In 1917 Sōichi Kakeya asked for the smallest region in the plane inside which a needle of length one can be turned all the way round. A disc of diameter one works and has area $\pi/4$. A curved triangle with three cusps, the deltoid, works and has area $\pi/8$, and for a while it looked as though that might be the answer. It is not, and the true answer is stranger than any shape: Abram Besicovitch showed in 1928 that the needle can be turned round inside a region of as small an area as anyone cares to name, and that a set containing a unit segment in every direction can have area exactly zero.

Such sets are called Kakeya sets, or Besicovitch sets, and the zero area is not the end of the story. They cannot be thin in the other sense of the word: however small their area, they seem always to be as large as the plane in dimension, and the question of whether that holds in every number of dimensions is one of the central open problems of analysis. Kakeya’s needle, a puzzle about turning a stick, became a question about how much room directions take up.

This essay asks the same question over a finite field, where every set has a size that is simply a count of points, and where the answer turns out to be the reverse of Besicovitch’s. A set that contains a whole line in every direction always fills a fixed share of the space — more than half of it in the plane — and the proof is one polynomial of low degree that the set would have to kill if it were smaller.

The plane over the integers modulo seven #

The integers modulo a prime $q$ form a field: they can be added, subtracted, multiplied and divided by anything non-zero. Pairs $(x, y)$ of them form a plane with $q^2$ points, and a line in it is the set of solutions of an equation $y = mx + c$, or $x = c$ for the vertical ones. Every line has exactly $q$ points. The slope $m$ can be any of the $q$ residues and the vertical lines add one more, so there are $q + 1$ directions.

A Kakeya set in this plane is a set of points containing at least one complete line in each of the $q + 1$ directions. The whole plane is one, with $q^2$ points. The question is how few points can do it.

The figure’s set is built from a parabola. Over the real numbers, the tangent to $y = x^2$ at the point where the slope is $m$ is the line $y = mx - m^2/4$, and there is exactly one tangent of each slope. The same formula makes sense modulo any odd prime, because 4 has a reciprocal there, so it gives one line of each of the $q$ non-vertical slopes. Adding the vertical line $x = 0$ completes the set of directions. Eight lines of seven points each would cover 56 points if none of them overlapped. They cover 31, because they overlap a great deal.

Which points the tangents reach #

Why 31? The count can be read off the equation. A point $(x, y)$ lies on the tangent of slope $m$ exactly when $y = mx - m^2/4$, and multiplying through by 4 and rearranging turns that into

$$(m - 2x)^2 = 4(x^2 - y).$$

So for a given point the question is how many residues $m$ make the left side equal a fixed number. If $x^2 - y$ is zero, one: $m = 2x$. If $x^2 - y$ is a non-zero square, two, since a non-zero square has two square roots. If $x^2 - y$ is not a square, none. Each point lies on two tangents, one, or none, and which of the three is decided by whether $x^2 - y$ is a square.

Over a field of odd size, exactly half of the non-zero residues are squares — the fact that the squares are the even powers of a primitive element makes that exact rather than approximate, and it is also the fact quadratic reciprocity is built on. So in each column, where $x$ is fixed, the value $x^2 - y$ runs through every residue once as $y$ does, and the tangents catch the one value that makes it zero plus the $(q-1)/2$ that make it a non-zero square: $(q+1)/2$ points per column, and $q(q+1)/2$ in all. The vertical line $x = 0$ then adds the points in its own column that the tangents missed, which are the $(q-1)/2$ where $-y$ is not a square. The total is

$$\frac{q(q+1)}{2} + \frac{q-1}{2} = \frac{q^2 + 2q - 1}{2},$$

which is 31 for $q = 7$.

The parabola does its job through its points of tangency. Every point of the plane on or below the parabola, in the sense that $x^2 - y$ is a square, is reached, and every point above it is missed. It is the finite-field version of the familiar fact that from a point outside a real parabola there are two tangents and from a point inside there are none — and the reason this construction is economical is that no point lies on more than two of its lines. The parabola is also, in a finite plane, an oval: $q + 1$ points counting its point at infinity, no three on a line, with exactly one tangent at each. Its $q$ ordinary points have tangents of $q$ different slopes, and that is the property that hands this construction one line in every direction but the vertical.

A bound from how lines meet #

How much better than 31 could one do? The first lower bound needs nothing but the fact that two lines in different directions meet in exactly one point.

Take any Kakeya set and choose one of its lines in each direction, and list the $q + 1$ lines in any order. The first contributes $q$ points. The second meets the first in one point, so it contributes at least $q - 1$ new ones. The third meets each of the first two in at most one point, so it contributes at least $q - 2$, and so on down to the last, which may contribute nothing new. The total is at least

$$q + (q-1) + (q-2) + \dots + 1 + 0 = \frac{q(q+1)}{2},$$

which is 28 for $q = 7$. So the smallest Kakeya set in this plane has somewhere between 28 and 31 points, and the gap is $(q-1)/2$ — the same vertical-line correction that appeared in the construction. The counting bound treats each new line as if it met all the earlier ones at separate points. The parabola’s tangents mostly do, which is why the two numbers are close, but they cannot all do so at once.

Deciding the small planes by search #

For small $q$ the gap can be closed by trying everything. A Kakeya set with one line chosen in each direction is determined by $q + 1$ choices of $q$ lines each, and shifting the whole plane does not change the size of a union, so the first two choices can be fixed. That leaves $q^{q-1}$ combinations — nine for $q = 3$, 625 for $q = 5$, 117,649 for $q = 7$ — and the smallest union among them is the smallest Kakeya set, because a set containing more than one line per direction is never smaller than the union of one of each.

The search agrees with the parabola every time. No choice of lines in the plane over the integers modulo 3, 5 or 7 does better than the tangents, and the counting bound is not reached. In 2008 Aart Blokhuis and Francesco Mazzocca proved that this is the pattern for every odd $q$: the minimum is exactly $(q^2 + 2q - 1)/2$, and the sets achieving it are essentially the parabola’s. The figure’s search is a check of their theorem at three sizes, not a substitute for it — but it is a complete check at those sizes, because it leaves no configuration untried.

The minimum is a little over half the plane: 31 of 49, 17 of 25, 7 of 9. That is already the whole contrast with Besicovitch. In the real plane a set with a segment in every direction can have no area at all. In the finite plane a set with a line in every direction always has more than half of it.

The same construction at thirteen #

As $q$ grows the fraction settles towards one half from above.

Over the integers modulo 13 the tangents and the vertical line take 97 of the 169 points, about 57 percent, and the counting bound says no Kakeya set can have fewer than 91, about 54 percent. As $q$ grows, both numbers divided by $q^2$ tend to one half, so in the plane the question of how small a Kakeya set can be is settled to the leading term by an argument two lines long, and settled exactly by Blokhuis and Mazzocca.

The shape of the set in the figure is worth noticing. The covered points form a region bounded by the parabola, with the uncovered ones on one side of it, and the rows are not random: in each column the covered points are the ones where $x^2 - y$ is a square, which is to say a translate of the set of squares. The pattern that looks irregular across a column is the pattern of quadratic residues, the same scatter whose sum a finite-field curve’s point count is built from.

Why the plane does not settle three dimensions #

In three dimensions over a field of $q$ elements there are $q^3$ points, and there are $q^2 + q + 1$ directions, one for each line through the origin. A Kakeya set holds a whole line in each of them. The counting argument can be run again, and it is much weaker, for a reason the plane hid.

In the plane, two lines in different directions always meet. In three dimensions they usually do not: two lines in space are typically skew. So the lines of a Kakeya set can mostly avoid one another, and an argument that charges each line only for its meetings with the others proves very little. Arguments of that kind were sharpened for years — gathering many lines through one point, a bush, or many lines through one line, a hairbrush — and they proved lower bounds like $q^{(n+2)/2}$ in $n$ dimensions. They did not come near $q^n$, which is what the question asks: whether a Kakeya set must fill a fixed share of the space, or whether its share can shrink to nothing as $q$ grows, the way Besicovitch’s sets shrink to zero area.

Thomas Wolff posed the finite-field version in 1999 as a model of the real problem, expecting it to be almost as hard. It was solved in 2008 by Zeev Dvir, then a graduate student, in a proof of about a page.

One polynomial that the set would have to kill #

Dvir’s argument begins with an interpolation fact. A polynomial in $n$ variables of degree at most $d$ has one coefficient for each monomial of degree at most $d$, and there are $\binom{d+n}{n}$ of those. Asking a polynomial to vanish at a given point is one linear equation on its coefficients. So if a set has fewer points than there are coefficients, the equations are fewer than the unknowns, and some polynomial that is not identically zero vanishes on the whole set. This is the same linear algebra that makes a polynomial through given values exist, run in reverse: instead of fitting given values, it fits zero everywhere on the set with coefficients to spare.

Take $d = q - 1$, and suppose a Kakeya set $K$ has fewer than $\binom{q - 1 + n}{n}$ points. Then some non-zero polynomial $f$ of degree at most $q - 1$ vanishes at every point of $K$. It is not a non-zero constant, since it vanishes somewhere, so its degree $d$ is at least 1.

Now use the lines. For each direction $b$, the set contains a line $\{a + tb\}$ as $t$ runs through the field. Restricted to that line, $f$ becomes a polynomial in the single variable $t$, of degree at most $d$, and it vanishes at all $q$ values of $t$. A polynomial of degree below $q$ with $q$ roots is identically zero, so every coefficient of $f(a + tb)$, as a polynomial in $t$, is zero. The coefficient of $t^d$ is the top-degree part of $f$ evaluated at $b$ — the terms of $f$ of exact degree $d$, with $b$ substituted in — and the starting point $a$ has dropped out of it entirely. So the top-degree part of $f$ vanishes at every direction $b$, and, being made of terms of positive degree, at zero too.

That puts it at zero on every point of the space. But a non-zero polynomial whose degree in each variable is below $q$ cannot vanish at every point of the space — a fact proved one variable at a time from the same root count — and the top-degree part of a polynomial of degree $d$ is non-zero by definition. The assumption was false. Every Kakeya set in $n$ dimensions has at least $\binom{q + n - 1}{n}$ points, which is at least $q^n / n!$.

The same number in the plane, and the right power in space #

The first check of a new bound is to run it where the answer is known.

In two dimensions Dvir’s bound is $\binom{q+1}{2} = q(q+1)/2$ — exactly the counting bound, reached by a completely different route. The counting argument used the fact that lines in the plane meet; the polynomial argument never mentions meetings at all, only that a line has $q$ points and a polynomial of degree below $q$ cannot vanish on all of them. The two arguments land on the same number in the plane, and only one of them survives the move to three dimensions, which is the whole point.

In three dimensions the polynomial gives $\binom{q+2}{3}$, about $q^3/6$: a Kakeya set must take at least a sixth of the space, however large $q$ is. The known constructions take about a quarter. The bound and the constructions differ by a constant factor and share the right power of $q$, which is everything the Kakeya question asked for and everything the arguments from meeting lines could not reach.

The constant has since been improved. In 2009 Dvir, Swastik Kopparty, Shubhangi Saraf and Madhu Sudan made the polynomial vanish at each point of the set to high order, not merely vanish, which lets it be of much higher degree while still being forced to zero on each line. That raised the lower bound to about $q^n/2^n$, and the best constructions take about $q^n/2^{n-1}$, so in every dimension the smallest Kakeya set is known to within a factor of 2. The figure draws Dvir’s first bound, not the improved one, because it is the one whose proof fits in the paragraphs above.

Why this does not settle the real question #

The finite field has no scales. A line has $q$ points and that is the end of its structure; a set either contains a point or does not. In the real plane a Kakeya set can be spread across infinitely many scales at once — thin tubes of width $\delta$ around each segment, for every $\delta$ — and Besicovitch’s construction exploits exactly that, piling the tubes so that they overlap almost entirely at every scale. The right question in the real case is therefore not about area but about dimension: how the number of balls of radius $\delta$ needed to cover the set grows as $\delta$ shrinks. The conjecture is that it grows like $\delta^{-n}$, as for a solid region, even though the set has no volume to speak of.

In the plane that was proved by Roy Davies in 1971. In three dimensions it was announced as proved in 2025 by Hong Wang and Joshua Zahl, in a long paper built on decades of partial results. In four dimensions and above it is open. Dvir’s polynomial does not transfer, because the real question is about tubes of width $\delta$ rather than exact lines: the argument needs every line in the set to be complete and every point on it counted, so that a polynomial is forced to zero along it, and a real Kakeya set seen at a scale offers neither. What did transfer was the method’s spirit: Larry Guth and Nets Katz used polynomials that vanish on carefully chosen sets of points to solve Erdős’s distinct-distances problem in 2010, and the idea that a low-degree polynomial is a way of controlling a set of lines has been one of the most productive in combinatorics since.

What the figures cannot show #

The construction and the search are limited to odd $q$ and small planes. The tangent formula divides by 4 and needs $q$ odd; over fields of even size the minimum is different and the construction is different, and nothing drawn here covers them. The search is exhaustive at $q = 3$, 5 and 7 and at no larger size.

The three-dimensional constructions are quoted, not built. The figure’s upper curve in three dimensions is the size of constructions from the literature, drawn as their stated share; no three-dimensional Kakeya set is listed point by point here, and the one-quarter share is not checked against a search.

The fields drawn are all prime. A field with $q = p^k$ elements for $k > 1$ exists and Dvir’s proof applies to it word for word, since it uses only that the field is finite and has $q$ elements; the pictures, which draw residues modulo a prime, do not show one.

And no figure reaches the real question. The finite-field theorem is complete, and its relation to the problem Kakeya’s needle opened is an analogy, not a reduction: nothing on this page says anything about sets of real numbers, and the dimension of a real Kakeya set is not something a count of points can estimate.

Where the polynomial goes next #

The shape of Dvir’s proof — suppose a set is small, find a low-degree polynomial that vanishes on it, and show that the polynomial must then vanish somewhere it cannot — was not new in 2008. It is a version of an argument Noga Alon had packaged a decade earlier as the Combinatorial Nullstellensatz, and its first and cleanest application is to a question about addition rather than lines: if two sets of residues modulo a prime are added, element by element, how small can the set of sums be? The answer is a theorem of 1813, and its polynomial proof is the subject of its own essay.

The two problems look unrelated — one is about lines in a space, the other about sums of numbers — and the proofs have the same three moves. Assume the set in question is small. Build a polynomial, of degree fixed by the assumed smallness, that vanishes on something the smallness controls. Then find a place where a polynomial of that degree cannot vanish: along a whole line here, and at one coefficient that a binomial number makes non-zero there. The contradiction is the theorem, and no configuration of the sets is ever examined.

A set that has to be large because a polynomial cannot be small #

A finite plane has $q + 1$ directions, and holding a line in each of them costs more than half its points. In any dimension it costs a fixed share of the space. The tangents of a parabola achieve the least possible cost in the plane, a search confirms it in the small planes, and a single polynomial of degree $q - 1$ shows that no cleverness in higher dimensions can make the cost vanish.

None of that is visible in the figures directly. What they show is the outcome — a set that stays more than half full however the lines are chosen — and the search that confirms nothing smaller exists in the planes small enough to search. The explanation of why the share cannot shrink is not in any picture; it is in the count of monomials against the count of points, and in the one fact that a line has more points than a polynomial of degree below $q$ has roots. That the whole of an old and stubborn question in finite geometry fits into those two counts is what made Dvir’s page so surprising, and why its method has been borrowed ever since.

When a set must meet many lines completely, count its points against the polynomials that could vanish on it — a polynomial of low degree cannot vanish on a whole line without vanishing everywhere along it, and a set too small to escape that is too small to hold the lines.