Twenty cards with no set among them

The card game SET is played with eighty-one cards. Each card shows one, two or three shapes; the shapes are diamonds, ovals or squiggles; they are red, green or purple; and they are empty, striped or solid. Every combination of the four features occurs exactly once, which is why there are $3^4 = 81$ cards. A set is three cards on which each feature is either the same on all three or different on all three. Players race to spot one among twelve cards on the table, and every so often nobody can, because there is none — and the question the game raises, which the mathematicians who played it asked at once, is how many cards can lie on the table with no set among them.

The answer is twenty. Twenty cards can be chosen with no set, and twenty-one cannot. It is a question about geometry over a finite field, and it belongs to a family of questions — how large can a set be that avoids some pattern? — which the sums of residues modulo a prime began, and whose answers in higher dimensions turned out to need an idea found only in 2016.

A set is a line #

Write each card as four digits from $\{0, 1, 2\}$, one per feature, so the cards are the points of $(\mathbb{Z}/3)^4$ — a vector space over the integers mod 3, the smallest odd case of a finite field, where addition is digit by digit and carries nothing. Take three cards $x$, $y$, $z$ and look at one coordinate. If the three digits are equal, their sum is $3a \equiv 0$. If they are all different, they are $0$, $1$ and $2$ in some order, and their sum is $3 \equiv 0$. If exactly two agree — $a, a, b$ with $b \ne a$ — the sum is $2a + b$, which is nought modulo three only if $b = a$. So three cards form a set exactly when $x + y + z = 0$, coordinate by coordinate.

And $x + y + z = 0$ is the equation of a line. Over the integers mod 3, a line through $x$ in direction $d$ is $\{x, x + d, x + 2d\}$, whose sum is $3x + 3d = 0$; conversely three distinct points adding to nought are $x$, $y$ and $-x - y = x + 2(y - x)$, which is the third point of the line through $x$ and $y$. Lines in this space have exactly three points, any two points lie on exactly one line, and the third point of that line is $-x - y$. Every pair of cards completes exactly one set — which is why a player looking at two cards knows precisely which third card they need.

A set of points with no three on a line is called a cap, and the game’s question is the size of the largest cap in four dimensions. It is the same question in any number of dimensions, and it is also a question about arithmetic: three points on a line are an arithmetic progression $x, x + d, x + 2d$, so a cap is a set with no three-term progression in it — the finite-field version of the question whether every dense set of whole numbers contains progressions.

Four points in the plane #

In two dimensions there are nine points and twelve lines: three horizontal, three vertical, and six that wrap diagonally round the grid.

The four points in the corner square form a cap: each of the twelve lines holds at most two of them. Six lines hold two, four hold one, two hold none, and those counts are forced — the four points make six pairs, and each pair has its own line. A fifth point cannot be added, and not only to this cap: the search in the figure tries every set of points and finds that four is the largest cap in the plane, and that there are 54 of them.

There is a short argument for the four, and it is worth having because it is the only proof on this page that is not a search. Suppose a cap had five points. Through any one of them pass four lines, and together they cover the other eight points of the plane, two to a line; each line can hold at most one more cap point, and there are four other cap points, so every line through a cap point must hold exactly one more. Now take any one family of three parallel lines. The five cap points are spread over three lines with at most two on each, so one of those lines holds exactly one cap point — and that line passes through a cap point and holds no other. The two requirements contradict each other, and five is impossible.

Nine points in the cube #

In three dimensions there are twenty-seven points, and the figure lays them out as three slices of nine.

The cap drawn is not spread evenly: four points in each of two slices and one in the third, and each slice’s share is itself a cap of the plane — the four-point slices are the largest planar caps from the figure above. A search that tries every set of points in increasing order, abandoning a branch as soon as a third point would complete a line, settles the three-dimensional question in a fraction of a second: nine is the largest, and there are 2,106 caps of nine. The count carries a consistency check. The space has 303,264 affine symmetries — 11,232 invertible linear maps of three coordinates mod 3, each combined with one of 27 translations — and every one carries a largest cap to a largest cap. Three hundred and three thousand two hundred and sixty-four is exactly 144 times 2,106, which is what the count would be if every cap of nine were a copy of every other, each fixed by 144 symmetries; a search that had missed caps would be unlikely to land on a divisor.

The numbers so far are two, four and nine in dimensions one, two and three — each a bit more than double the last. The space triples with each dimension. So the share of the space a cap can occupy is falling: two thirds of the line, four ninths of the plane, a third of the cube.

Twenty of the eighty-one cards #

Four dimensions is the game itself.

Twenty cards with no set among them: the figure’s twenty points were found by a seeded random search and are checked on the drawing itself — every pair’s third point lies among the other sixty-one, and every one of the sixty-one is the third point of some pair, so the cap is complete: nothing can be added. That a cap of twenty exists is therefore settled by the figure. That no cap of twenty-one exists is not, and the searches that settled dimensions two and three are hopeless here — the number of twenty-one-point subsets of eighty-one points is around $10^{19}$. Giuseppe Pellegrino proved it by hand in 1970, working in the projective space that contains this one and counting how a cap must meet its three-dimensional slices.

For a player, the number means that twenty-one cards on the table always contain a set. The game deals twelve and adds three when nobody can find one, so a table of twenty-one cards never needs a twenty-fourth. The drawing also shows how the twenty sit: one of the nine three-by-three blocks holds four of them — a block is a plane, and four is the plane’s limit — and each of the other eight holds exactly two, arranged so that no line running across three blocks picks up a point from each.

A cap nobody can add to is not a largest cap #

The figure’s cap of twenty took four hundred random attempts to find. That is worth a figure of its own.

The procedure is the obvious one: go through the points in some order and keep each point that does not complete a line with two kept already. What comes out is always a complete cap — nothing more can be added to it — and it is almost never a largest one. Of two thousand random orders, one reached twenty. Most stopped at seventeen, and not one of the two thousand stopped at nineteen: an eighteen-point cap built this way is typically boxed in completely, with every remaining point already the third point of some pair.

This is the practical meaning of the gap between complete and largest, which is the gap between a local and a global optimum. Every greedy cap is a local optimum — it cannot be improved by adding a point — and nearly all of them are well short of the global one. The same gap is why the searches in two and three dimensions had to try every set rather than trust any construction, and why four dimensions needed a proof: no amount of greedy searching certifies that twenty-one is impossible, since failing to find a cap is not evidence that none exists.

The same question in a projective plane, and in a code #

Caps were not first studied because of a card game, which dates from the 1970s. They were studied because of statistics. Raj Chandra Bose, designing agricultural experiments in the 1940s, needed sets of points in the finite projective spaces with no three on a line, and he asked the cap question there in 1947.

In a projective plane the question is the one the curve that no three points in line define answers: a set of points with no three collinear is an arc, the largest arcs in the plane of order $q$ have $q + 1$ or $q + 2$ points, and for odd $q$ they are exactly the conics. The affine plane over the integers mod 3 is that projective plane of order three with one line removed, and the four-point cap of the first figure is a whole conic of it, lying clear of the removed line. So the planar case is the ovals of the smallest planes, and the cap question is what the oval question becomes when the plane is replaced by a space of four, five or a hundred dimensions — where there are no conics to compare with and no Segre’s theorem to say that the largest sets are algebraic.

Bose also saw the second disguise. Write the points of a cap in projective space as the columns of a matrix. A set of columns with no three dependent — no three on a line — is exactly the parity-check matrix of a code in which every nonzero codeword has weight at least four, since a codeword of weight three would be three columns adding to nought. So a large cap is a long ternary code that detects three errors and corrects one, with the least redundancy the dimension allows, and the question of how large a cap can be is the question of how good a code can be at one particular distance. Pellegrino’s twenty and Potechin’s hundred and twelve are, read that way, statements about the longest codes of a given redundancy — and the codes that fill space with spheres are the same kind of object at a different distance.

The table stops at six #

The largest cap is known exactly in six dimensions and no more.

The column of shares is the clearest way to read the table. Each extra dimension triples the space, and the largest cap never keeps pace: two thirds of the line, four ninths of the plane, a third of the cube, a quarter of the cards, and less than a sixth of the six-dimensional space. Nothing guarantees that the shares keep falling — a pattern in six numbers can stop — but the upper bounds below make sure they do.

Five dimensions give 45, settled by Yves Edel, Sandy Ferret, Ivan Landjev and Leo Storme in 2002; six give 112, settled by Aaron Potechin in 2008, both with extensive computer searches guided by the structure of smaller caps. Seven is open: the best cap known has 236 points and nobody has shown that 237 is impossible.

The last column is the one that matters for large dimensions. A cap of size $c_n$ in dimension $n$ grows roughly like $\lambda^n$ for some rate $\lambda$ between two and three: two, because the points with every coordinate $0$ or $1$ always form a cap — three of them adding to nought would need each coordinate’s digits to be all equal or all different, and with only two values available they must be all equal — and three because that is the size of the whole space. Products of caps are caps, so a good cap in one dimension gives good caps in every multiple of it, and the best such product, found by Edel in 2004 from a cap of 112 in six dimensions and larger structured caps, gives a rate of about $2.2174$, improved slightly since, most recently in 2023 with the help of a computer-guided search. The table’s $n$-th roots, $2.00$ to $2.20$, are creeping towards that.

Is the rate below three? #

That leaves the question of the upper end. Does the largest cap take a vanishing exponential share of the space — is its growth rate strictly less than three — or only a share that shrinks like a power of $n$?

For decades the second was all anybody could prove. Roy Meshulam showed in 1995, by an argument about Fourier coefficients modelled on Klaus Roth’s proof for progressions in the integers, that a cap has at most about $2 \cdot 3^n / n$ points: a vanishing share, but vanishing slowly. Michael Bateman and Nets Katz improved the $n$ to slightly more than $n$ in 2012, after years of effort, and the general view was that an exponential improvement, if true, was far away.

In May 2016 Ernie Croot, Vsevolod Lev and Péter Pál Pach proved an exponential bound for the analogous problem in $(\mathbb{Z}/4)^n$ with a two-page argument about polynomials, and within days Jordan Ellenberg and Dion Gijswijt had adapted it: a cap in $(\mathbb{Z}/3)^n$ has at most $2.756^n$ points. The proof is shorter than this essay, uses nothing beyond counting monomials, and is the subject of the next one. What it does not do is close the gap. The truth lies somewhere between about $2.22^n$ and $2.756^n$.

What the searches settle, and what they do not #

Dimensions two and three are settled by the figures. The search in each tries every subset in increasing order and prunes only when a line is completed, so its “no cap of five” and “no cap of ten” are complete verdicts, and the counts 54 and 2,106 are complete counts of the largest caps.

Dimension four is only half settled by a figure. The drawing proves that twenty is achievable. It says nothing about twenty-one, which is Pellegrino’s theorem; the greedy census does not bear on it at all, since a procedure that never finds twenty-one proves nothing about whether one exists.

Dimensions five and six are quoted. The figures do not reach 243 or 729 points with any search of this kind, and the values 45 and 112 are taken from the computer-assisted proofs that established them.

The growth rate is invisible. Six terms of a sequence do not reveal the base of its exponential growth, and the table’s creeping roots are consistent with limits anywhere from 2.2 to 2.76.

Still open: the growth rate #

The largest cap in dimension $n$ has size $\lambda^{n + o(n)}$ for some number $\lambda$, and the limit exists — caps multiply, so the logarithm of the largest size is superadditive and its average converges. What the number is, is not known: it lies between about $2.2202$, from the best construction, and $2.7551$, from the polynomial method.

Neither end looks final. The constructions are products of carefully found caps in modest dimensions, and each improvement has come from finding a better small cap by search; nothing suggests the best small caps have been found. The upper bound comes from a method that, as the next essay shows, bounds a quantity called the slice rank rather than the cap itself — and the same bound turns out to be exactly right for a looser object, the tri-coloured sum-free sets, as Robert Kleinberg, William Sawin and David Speyer showed in 2018, so any argument that also bounds those can never do better than $2.7551$. Closing the gap will need either a better way of building caps or a different kind of upper bound — and in the meantime the first unknown exact value, dimension seven, sits between 236 and whatever the next clever argument can rule out.