A line detector over three symbols

The Polynomial That Saw Every Line

A polynomial over three symbols detects every forbidden line, then becomes diagonal when none remain. Build a cap set, watch the rank certificate count its monomials, and minimise the live bound until its exponential base falls below three.

P(x,y,z) = ∏i [1 - (xi + yi + zi)²]  in  F3
0 unless x+y+z=0, then 1

Each coordinate has only three values. A nonzero coordinate sum has square 1, so its factor vanishes. A zero coordinate sum has square 0, so its factor stays 1. The product sees the whole line at once.

Put the third point in

Choose two distinct points. The machine computes the one point that completes their line. Put it into the set and an off-diagonal tensor entry appears. Remove it and the entry is gone.

The set A

Every chip is one vector in F3n. Press a chip to include or exclude it.

|A| = 9 gold means included

Complete one line

Choose two distinct points, then complete their line.
Nontrivial lines in A

0

Diagonal support

9

Off diagonal

0

The restricted tensor, one cell for each ordered pair (x,y)

A lit cell means the unique completion z is also in A. For a cap, only x=y=z survives, so the support is exactly the diagonal.

diagonal support forbidden off-diagonal support completion absent

Count the slices, then move the base

Diagonal support has rank |A| in characteristic three. Expansion gives another description of the same tensor. Every term must have a low-degree x, y, or z block, so the number of possible slices puts a ceiling on |A|.

|A| = slice-rank(P restricted to A³)  ≤  mn + mn + mn = 3mn

The exact monomial count

This is the proof cutoff. At least one of the three blocks must land here.

coefficient convolution168
exponent enumeration
3mn504
whole space 3n729

The finite bound, root by root

The purple path is (3mn)1/n. The floor in the cutoff makes it wobble. The horizontal gold line is the limiting generating-function base, and the grey line is 3.

At n=6, |A| is at most 504 by the slice count. The whole space has 729 points.

An earlier bound of the form C3n/n1+epsilon has nth root tending to 3 for every fixed positive C and epsilon. No values for those unspecified constants are invented on this plot.

Open the product and sort every term

One coordinate contributes seven nonzero terms after expansion in F3. The microscope enumerates all 7n products and assigns each to the first block whose degree is low enough.

1-(x+y+z)² = 1 + 2x² + 2y² + 2z² + xy + xz + yz  in F3

Every product term has total degree at most 2n. If its x, y, and z blocks all had degree above 2n/3, their sum would exceed 2n. One block must therefore enter a ledger.

x ledger256 terms
10 distinct low blocks
y ledger80 terms
10 distinct low blocks
z ledger7 terms
1 distinct low block

All 343 expanded terms assigned. Each ledger uses no more than m3=10 low-block monomials.

Minimise the exponential envelope

The coefficient count obeys mn ≤ t-2n/3(1+t+t²)n for every 0<t<1. Move t. The curve itself tells you where the smallest base lives.

base = 2.801394247282882

c = min0<t<1 (1+t+t²)/t2/3 = ∛(5589+891√33)/8 = 2.755104613023633

Differentiation gives 4t²+t-2=0, so the positive root is t=(sqrt(33)-1)/8. The button keeps that exact JavaScript value. No stepped control rounds it.

The check

The green lane is recomputed in this browser. The other lanes name what entered from a source, what you were free to choose, and where the proof stops.

Recomputed now

P versus direct zero testcomputing
restricted tensorcomputing
mn, two routes168 = 168
current generating base2.801394247282882

The offline verifier also reconstructs the expanded polynomial from the grouped slices and exhausts every subset for n=1 and n=2. Run node research/cap-set-polynomial/verify-cap-set-polynomial.mjs.

Every free choice

  • You choose the small-space dimension, the members of A, and the ordered pair to complete.
  • Restore uses convenient constructed caps of sizes 2, 4, 9, and 16. The n=4 preset is not the published maximum 20.
  • You choose n and the degree cutoff in the coefficient bench. Only floor(2n/3) is the proof cutoff.
  • You choose the microscope dimension and t. The minimum button uses the exact positive root of 4t²+t-2=0.
  • The slice ledger assigns ties in x, then y, then z order. Another tie rule changes the ledger split, not the total ceiling of 3mn.

Vacuous and broken settings

  • If A contains a line, the tensor is not diagonal. The diagonal-rank step no longer bounds |A|.
  • Choosing x=y produces the unavoidable diagonal solution x=y=z. It is not a forbidden line.
  • For some small n, 3mn is at least 3n. The displayed theorem is then true but no better than counting the whole space.
  • The rank comparison uses output arithmetic in characteristic three. Over the real or complex numbers, this tensor does not give the same nontrivial rank bound.

Uncertainty and boundary

  • The exact maxima 2, 4, 9, 20, 45, 112 are published context. This bound does not derive them.
  • A peer-reviewed 2026 source says exact maxima are known through n=6. The exact value from n=7 onward remains unknown there.
  • The true asymptotic growth base is not known. The polynomial gives the upper endpoint 2.755104613023633, rounded to 15 decimal places.
  • The peer-reviewed lower endpoint reported in 2026 is 2.2202. A 2025 preprint claims 2.2203. The page does not merge their evidence levels.

What the certificate settled, and what it did not

Let M(n) be the largest cap in F3n. The method proved that limsup M(n)1/n is below 3. It did not determine M(n) in general, and it did not determine the true asymptotic base.

2n=1
4n=2
9n=3
20n=4
45n=5
112n=6

Published exact maxima, not outputs of the polynomial bound. The verifier independently recovers only the first two by exhaustive subset search.

2.2202

Lower endpoint reported by Grace in a peer-reviewed 2026 article.

2.2203

Lower bound claimed by Zhai and coauthors in a 2025 preprint. Not peer-reviewed.

2.755104613023633

Upper base computed here from the minimiser and the published algebraic form. Rounded to 15 decimal places.

Source status and chronology