WorksMathematics
Large caps in and
Abstract
We construct sets of points in and points in , each containing no three distinct collinear points. A reflection lift sends the Calderbank–Fishburn -cap to a cap with three parallel layers of sizes ; both outer layers are linearly equivalent to the FunSearch -cap. A coordinate substitution in Hill's -cap uses replacement sets of sizes for the three values of one scalar coordinate. Assigning the -point set to a noncentral -point section gives , gaining points over the construction obtained from a central -point section.
Introduction
A cap in is a set whose solutions of have ; equivalently, it contains no three distinct collinear points. Write for the largest size of such a set. Table 1 places our two constructions alongside previously reported bounds in dimensions up to eleven.
| Dimension | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| Previous bound | 2 | 4 | 9 | 20 | 45 | 112 | 236 | 512 | 1082 | 2432 | 5504 |
| This paper | – | – | – | – | – | – | – | – | 1104 | – | 5744 |
Table 1. Lower bounds for ; our improvements are bold. Values for are exact [3]. Sources for dimensions 7, 8, 9–10, and 11 are [1], [4], [5], and [6], respectively. We call the dimension-eight example the FunSearch cap, after the program-search method guided by a large language model that produced it.
Theorem 1. The sets and defined below are caps of sizes 1104 and 5744, respectively. The three parallel layers of have sizes 512, 80, 512, and both outer layers are linearly equivalent to the FunSearch cap. In particular,
To the best of our knowledge, these improve the previously reported lower bounds of 1082 and 5504, respectively. The former follows by doubling the 541-cap in PG(8, 3) recorded by Bierbrauer–Edel [5 Theorem 1 and Table 1]; the latter is stated explicitly in [6 Corollary 2].
Both constructions copy sections of classical caps into larger spaces. For , reflection pairs the fibers of two Hill caps and preserves their assembly into the 236-cap. For , the same Hill model supplies both the source and three replacement sets; the size is governed by a single affine section.
The companion repository, github.com/holdenmatt/capset-constructions, contains both point lists, their constructors, exact checks of the cap property and the FunSearch equivalences, and the 1104 coordinate diagrams.
Both constructions use classical fiber and generalized-product ideas [7, 8]. FunSearch already gives an explicit recipe for its 512-cap and discusses its relation to Hill’s cap [4 Figure 4 and Supplement E.2].
Constructing the 1104-cap
The Hill ingredients. The support of a vector is the set of its nonzero coordinate positions; write 123 for , and similarly for other supports. On six coordinates take the classical design
Let consist of all vectors obtained by assigning 1 or independently on these supports, with zeros elsewhere, and put
Then , , and is the standard Hill 112-cap [2 Section 2]. Let use the complements of the ten supports in , with the same full-support set . These sets serve both constructions: supply the fibers of , while are the replacement sets for .
The classical 236-cap. Let . The Calderbank–Fishburn cap [1], in the coordinates of [2 Theorem 5 and Table 2], is
Its three layers have sizes 112, 12, 112.
The reflection lift. We construct from by a reflection lift, keeping the layer coordinate unchanged. We describe the lift here and prove that it preserves the cap property in § 3. Write a source point as , where and . Fixing gives a fiber of retained coordinates . Negating preserves , so opposite source positions have identical fibers. Choose the four representatives
Replace the two coordinates by four block coordinates . Copy the central fiber to the eight signed axes, and the fiber at each pair to the eight positions whose only zero coordinate is :
Explicitly, in coordinates , define
Here denotes concatenation of the retained coordinates with the two entries of .
For example, setting in leaves the signings of supports 123 and 124, hence 16 vectors. Each of the eight blocks in the upper layer contains a copy of these 16 points. The same count holds for , using supports 134, 234; the central fiber of has eight points. For a source layer of size with points at , the lift gives points, as summarized in Table 2.
| Source layer | Size | Central fiber | Lifted size |
| 112 | 16 | 512 | |
| 12 | 8 | 80 | |
| 112 | 16 | 512 | |
| Total | 236 | 40 | 1104 |
Table 2. The reflection lift takes the three layers of to those of .
Write for the layers of at , respectively. § 3 proves that the lift preserves the cap property for the whole source, including triples crossing these layers. Figure 1 displays the resulting cap. Each small square fixes , and represents a four-dimensional affine flat; the 81 possible dot positions encode . Repeated patterns are the copied fibers of , , and .

Figure 1. The three layers of the 1104-cap at a common scale; each dot is one point. Columns and rows encode and for blocks, and for dots within blocks. Both grids use lexicographic pair order, , rightwards and upwards. Colors label . Positions encode coordinates; three dots aligned on the page need not represent collinear points over .
The reflection lift
We now formulate the reflection lift of Section 2 in general and prove that it preserves the cap property. Let have dimension , and let be a cap unchanged by the simultaneous sign flip
The fibers satisfy . Choose representatives for the four nonzero pairs , and write and . Thus
The fixed cap points are exactly those above . Put , and . Empty or repeated fibers are allowed.
Using the block positions , copy to and each to . The reflection lift is
The subscript records the two coordinates reversed by the reflection; the lift replaces them with four, increasing the ambient dimension by two.
Theorem 2 (Cap-preserving lift). The set is a cap of size
An affine equivalence of source caps intertwining their chosen sign flips induces an affine equivalence of their lifts.
Proof. Every fiber is a cap. The source also restricts how three local vectors can interact:
The first restriction comes from the three source addresses , , . For the second, write with , possible because the three direction pairs are distinct. The addresses , , sum to zero, and changing a representative’s sign leaves its fiber unchanged. In both cases the source addresses are distinct, even if some local vectors coincide.
Now suppose three lifted points , , sum to zero. The block addresses and local vectors must separately sum to zero. If two block addresses agree, then forces all three to agree. All points lie in one copied fiber, whose cap property forces the three points to coincide.
It remains to consider three distinct blocks. An address in has one nonzero coordinate; an address in has exactly one zero coordinate, at position . These support patterns leave only two possible types of zero-sum address triple:
Indeed, two distinct addresses have a sum with zero or two nonzero coordinates, whose negative is unoccupied. With exactly one address, the other two must have the same missing coordinate: otherwise the address would need two nonzero coordinates to cancel their sum. For three addresses in the , exactly two equal missing coordinates leave a coordinate with a single nonzero entry. If all three missing coordinates agree, the other entries can sum to zero only by agreeing coordinatewise, which would make the addresses identical. Hence their missing coordinates must all differ.
In Figure 1, these two types mean one blue block and two blocks of one other color, or three nonblue blocks of different colors. Their local vectors would violate the respective restrictions in (5). The five sets of block addresses are disjoint and each has size eight, giving the stated count.
Finally, an affine map intertwining two such source symmetries has, in these coordinates, the form . The map permutes the four source direction pairs, say by . The lifted map carries one lift to the other, where .
Applying the lift to . For completeness, we first verify the classical source.
Lemma 3. The set in (1) is a cap.
Proof. Each layer is a cap. A triple meeting all three layers would require a point of and a point of to sum to an axis vector. If both points have support of size three, they cannot sum to an axis vector: their support symmetric difference would have size at most one, forcing their supports to agree, whereas the two support families are disjoint. A point of support size three and a full-support point have a sum with at least three nonzero coordinates. Two full-support points summing to an axis would be opposite in five coordinates and equal in one, so their coordinate products would be opposite. Both products are 1, a contradiction.
:::
Cap property and size of in Theorem 1. The sign flip preserves each layer of . Apply Theorem 2 with local space retaining and the direction representatives chosen in Section 2. After reordering the coordinates to , the resulting lift is exactly (2). It is therefore a cap, including across layers. Table 2 gives , so its size is , with layers of sizes 512, 80, 512.
Identification with the FunSearch cap. Both outer layers are linearly equivalent to the FunSearch cap. A coordinate permutation identifies with , and an invertible linear map sends to the published construction [4 Figure 4c and Supplement Figure E.23]. The companion repository gives both maps in verify_funsearch.py and verifies exact equality by evaluating the published membership rule on all vectors and comparing the resulting set with the mapped layers.
Repeating the reflection lift gives a first continuation to dimension eleven. Negating two new address coordinates fixes four axis copies of the preceding fixed fiber, so becomes . The source gives , and the next lift has 5056 points, below the previously reported lower bound of 5504 [6 Corollary 2]. To surpass that bound, we instead apply coordinate substitution to Hill’s cap using a noncentral section, obtaining 5744 points.
Coordinate substitution and the 5744-cap
Choose an affine scalar coordinate on , retain five complementary coordinates, and replace the scalar’s value by one of the sets already defined:
These classical ingredients [8 Section 3] have sizes 80, 32, 32 and are disjoint. Each pairwise union is a cap: , reversing one coordinate carries it to , and is the cube . This property permits the following coordinate substitution.
Lemma 4 (Coordinate substitution). Let be disjoint, with each pairwise union a cap. If
is a cap, then
is a cap of size .
Proof. Consider three points of summing to zero, with . If the labels use at most two values, the lie in one of the pairwise unions and hence coincide; disjointness makes their labels equal. Otherwise the labels are . In either case , so the corresponding source points sum to zero and must coincide. All three now lie in the same cap , so they too coincide. This proves the cap property, including triples with repeated components. Disjointness gives the size formula.
Apply the lemma with the six-dimensional sets , , above. The 80-point set consists of Hill’s sparse vectors; it is distinct from the 80-point middle layer of . If the source has points and its zero section has points, then
Each point in the zero section receives 80 replacements instead of 32, so we seek a large section of .
A noncentral 45-section. In our coordinates, the linear functional gives
These counts follow directly from the displayed signed-support model and realize the classical 22/45/45 Hill sections [3 Lemma 3.1(a)]. Since is centered at the origin, the two 45-sections are noncentral.
Construction of in Theorem 1. Set
The map is an affine coordinate change: . Define explicitly
The source sections at have sizes 45, 45, 22. Lemma 4 proves that is a cap, and
An ordinary coordinate, such as , gives sections of sizes 40, 36, 36 and hence , recovering the signed-support construction of [6 Corollary 2]. Choosing assigns the larger replacement set to a noncentral 45-section instead of that central 40-section, gaining exactly
Neither construction is asserted to be globally optimal.
Exact pair checks also confirm the cap property for both coordinate sets. The existence proofs above are independent of these computations.
Use of AI tools. OpenAI’s Codex (using GPT-6 Astra) assisted with computational exploration, code development, and preparation and revision of the manuscript. The author takes responsibility for the mathematical claims, references, and final text.
References
- [1]A. R. Calderbank and P. C. Fishburn, Maximal three-independent subsets of {0,1,2}ⁿ, Designs, Codes and Cryptography 4 (1994), 203–211.DOI
- [2]Y. Edel and J. Bierbrauer, Large caps in small spaces, Designs, Codes and Cryptography 23 (2001), 197–212. Corrected author version: https://www.yvesedel.de/Papers/smallCaps.pdf.DOI
- [3]H. (M.) R. Thackeray, The cap set problem: Up to dimension 7, arXiv:2206.09804 (2022). https://arxiv.org/abs/2206.09804.
- [4]B. Romera-Paredes et al., Mathematical discoveries from program search with large language models, Nature 625 (2024), 468–475; Supplement E.2. https://doi.org/10.1038/s41586-023-06924-6.
- [5]J. Bierbrauer and Y. Edel, Large caps in projective Galois spaces, in Current Research Topics in Galois Geometry (2012), 87–104. https://www.yvesedel.de/Papers/CapSurvey.pdf.
- [6]I. Karapetyan and K. Karapetyan, Complete Caps in AG(n, 3), Proceedings of CSIT 2023, 135–136. https://doi.org/10.51408/csit2023_30.
- [7]Y. Edel and J. Bierbrauer, Recursive constructions for large caps, Bulletin of the Belgian Mathematical Society Simon Stevin 6 (1999), 249–258. https://www.yvesedel.de/Papers/RCap.pdf.DOI
- [8]Y. Edel, Extensions of generalized product caps, Designs, Codes and Cryptography 31 (2004), 5–14. https://www.yvesedel.de/Papers/ExtProd.pdf.