Munim Technologies

Research/Mathematics

A computer search finds no Kakeya set in F43 smaller than 28 points

An exact reduction splits the question into 22 small integer programs, and the solver HiGHS proved every one infeasible at 27 points. If that holds up, the smallest Kakeya set in the 64-point space F43 has exactly 28 points, and a known construction is optimal there. A second solver confirmed 16 of the 22 cases, and a certificate check is queued.

Nov 21, 2026 · 6 min read

We ran a pre-registered exact computation asking how small a Kakeya set in F43 can be, and it found none with fewer than 28 points. A Kakeya set contains a full line in every direction. The three-dimensional space over the four-element field F4 has 64 points and 21 directions, and the known range for its smallest Kakeya set was 21 to 28. The computation split the question into 22 cases, and the integer-programming solver HiGHS proved that none of the 22 cases allows a Kakeya set of 27 points. So, by this computation, the minimum is exactly 28. That would make the even-q construction of Kopparty, Saraf and Sudan, which has 28 points here, exactly optimal. Over fields with more than three elements, we found no earlier exact value in dimension 3 or higher. Six of the 22 cases rest on one solver, so we have queued an independent check that produces a machine-checkable proof.

The question

Finite-field Kakeya sets have been central since Dvir proved in 2008 that they must contain a constant fraction of the whole space. The sharpest general lower bound, by Bukh and Chao, gives at least 21 points in F43. For even q, the construction of Kopparty, Saraf and Sudan (as quoted by Bukh and Chao) uses, in dimension 3, one quarter of all the points plus three quarters of the points of one plane. In F43 that is 16 + 12 = 28 points. Exact minima are classical in the plane. Above it, the only one we found is over the three-element field: Vsevolod Lev found by computer in 2009, in a comment on Terence Tao's Polymath thread, that the minimum in F33 is 13. An exhaustive search in this repository confirmed it independently. F43 is the smallest open case over a larger field.

What we did

Suppose a Kakeya set K has at most 27 points. Among the 84 planes of F43, pick one that meets K in the fewest points, say n0. Four parallel planes split the space, so n0 is at most 6. A line that is not parallel to a plane meets it, so n0 is at least 1. An affine map moves that plane to the bottom layer, and a symmetry of the plane moves the bottom layer to a fixed representative of its orbit under the 2,880 affine maps of F42. Lines through the bottom layer then determine the 16 slanted directions, and lines inside a single layer give the other 5. What is left is a 0/1 problem with 48 point variables for the three upper layers. It needs every plane to meet K in at least n0 points and the total to be at most 27. There are 22 orbit representatives of sizes 1 to 6, so 22 problems.

Each problem went to two solvers, OR-Tools CP-SAT (900 s) and HiGHS (300 s). Before the search, the job checked its own machinery. The group has 2,880 distinct elements, and the orbit sizes add up to the binomial coefficients. Both solvers accept the known 28-point set at 28 and reject it at 27. Every solution either solver reports is re-checked by brute force. Our predictions were written down before the run: 45% that both solvers would prove 28, 20% that a smaller set exists, 10% that only CP-SAT would finish, 10% undecided, 15% bug.

What we found

22 of 22

cases HiGHS proved infeasible at 27 points

16 of 22

cases CP-SAT also proved within 900 s

0

Kakeya sets of 27 or fewer points found

28

smallest Kakeya set in F43, by this computation

The 22 cases, grouped by the smallest plane section n0

n0casesproved by CP-SATproved by HiGHSlongest HiGHS run (s)
11110.0
21110.0
32224.1
443444.6
5505113.9
69990.0
From results/kmin34-v1/summary.json and cases.csv. The whole run took 7,074 s on 2 cores.

The hard cases are those where the sparsest plane holds 4 or 5 points. CP-SAT could not finish those within 900 seconds, while HiGHS closed every one in under two minutes. With at least 6 points in every plane, four parallel planes already hold 24 of the 27 points, and those problems were decided almost at once.

HiGHS time for the six cases CP-SAT could not close

seconds

Representatives are point indices 4a + b of (a, b) in F42. These six cases rest on HiGHS alone until the certificate check reports. Source: results/kmin34-v1/cases.csv

How it grades

The outcome does not match any pre-registered label exactly. We had allowed for both solvers finishing, or CP-SAT alone, but not HiGHS alone. The job's code therefore labels the run UNDECIDED, even though no case was left open by both solvers. We are not upgrading that label after the fact. The 45% prediction that both solvers would prove 28 did not come true, and the 20% prediction of a smaller set failed.

Bounds on the smallest Kakeya set in F43

points

Lower bound from arXiv:2108.00074, Theorem 1; construction sizes from their formulas. Source: results/kmin34-v1/summary.json

Corrections

A literature re-check for this article found that our repository had over-claimed in four places. The 28-point set in F43 is the Kopparty-Saraf-Sudan construction, not a new one. The value 13 for F33 was found by Lev in 2009, so our exhaustive search confirms it rather than being the first. Lev also had a 27-point set in F34. And a 53-point set in F35 by Chung, Du and Wesley beats the 56 points we listed. All four are set out in CORRECTIONS.md. The new part here is the matching lower bound for F43.

What it means and what comes next

If the six HiGHS-only cases hold, K(3,4) = 28, and the even-q construction is exactly optimal in F43. We have queued an independent re-check that shares no model code with this run. It writes each of the 22 cases as a SAT formula with a new encoding and solves it with kissat, which emits a DRAT proof, and every proof is checked by drat-trim. Before the real cases, its self-checks compare the encoding with brute force on 90 test sets. A sister computation for F34 is also waiting for compute. It tests Lev's 2009 conjecture that the minimum there is 27, which has been open since he made it.

More research