betaFeedback

WorksMathematics

Large caps in F39\mathbb{F}_3^9 and F311\mathbb{F}_3^{11}

Abstract

We construct sets of 11041104 points in F39\mathbb{F}_3^9 and 57445744 points in F311\mathbb{F}_3^{11}, each containing no three distinct collinear points. A reflection lift sends the Calderbank–Fishburn 236236-cap to a cap with three parallel layers of sizes 512,80,512512,80,512; both outer layers are linearly equivalent to the FunSearch 512512-cap. A coordinate substitution in Hill's 112112-cap uses replacement sets of sizes 80,32,3280,32,32 for the three values of one scalar coordinate. Assigning the 8080-point set to a noncentral 4545-point section gives 57445744, gaining 240240 points over the 55045504 construction obtained from a central 4040-point section.

Introduction

A cap in F3d\mathbb{F}_3^d is a set whose solutions of x+y+z=0x+y+z=0 have x=y=zx=y=z; equivalently, it contains no three distinct collinear points. Write r3(F3d)r_3(\mathbb{F}_3^d) for the largest size of such a set. Table 1 places our two constructions alongside previously reported bounds in dimensions up to eleven.

Dimension dd1234567891011
Previous bound2492045112236512108224325504
This paper––––––––1104–5744

Table 1. Lower bounds for r3(F3d)r_3(\mathbb{F}_3^d); our improvements are bold. Values for d≤6d \le6 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 K⊆F39K \subseteq\mathbb{F}_3^9 and L⊆F311L \subseteq\mathbb{F}_3^{11} defined below are caps of sizes 1104 and 5744, respectively. The three parallel layers of KK have sizes 512, 80, 512, and both outer layers are linearly equivalent to the FunSearch cap. In particular,

r3(F39)≥1104,r3(F311)≥5744.r_3(\mathbb{F}_3^9) \ge1104,\qquad r_3(\mathbb{F}_3^{11}) \ge5744.

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 KK, reflection pairs the fibers of two Hill caps and preserves their assembly into the 236-cap. For LL, 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 {1,2,3}\{1,2,3\}, and similarly for other supports. On six coordinates take the classical design

D={123,124,135,146,156,236,245,256,345,346}.\mathcal{D}=\{123,124,135,146,156,236,245,256,345,346\}.

Let P⊆F36P\subseteq\mathbb{F}_3^6 consist of all vectors obtained by assigning 1 or −1-1 independently on these supports, with zeros elsewhere, and put

Qϵ={x∈{±1}6:∏j=16xj=ϵ},ϵ∈{1,−1}.Q_{\epsilon}=\left\{x\in\{\pm1\}^6:\prod_{j=1}^{6}x_j=\epsilon\right\},\qquad\epsilon\in\{1,-1\}.

Then ∣P∣=80|P|=80, ∣Qϵ∣=32|Q_{\epsilon}|=32, and H=P∪Q1H=P\cup Q_1 is the standard Hill 112-cap [2 Section 2]. Let H′H' use the complements of the ten supports in D\mathcal{D}, with the same full-support set Q1Q_1. These sets serve both constructions: H,H′H,H' supply the fibers of KK, while P,Q1,Q−1P,Q_1,Q_{-1} are the replacement sets for LL.

The classical 236-cap. Let E6={±ei:1≤i≤6}E_6=\{\pm e_i:1\le i\le6\}. The Calderbank–Fishburn cap [1], in the coordinates of [2 Theorem 5 and Table 2], is

K236=({1}×H)∪({0}×E6)∪({−1}×H′).(1)K_{236}=(\{1\}\times H)\cup(\{0\}\times E_6)\cup(\{-1\}\times H'). \tag*{(1)}

Its three layers have sizes 112, 12, 112.

The reflection lift. We construct KK from K236K_{236} by a reflection lift, keeping the layer coordinate tt unchanged. We describe the lift here and prove that it preserves the cap property in § 3. Write a source point as (t,v,q)(t,v,q), where v=(x1,x2,x3,x4)v=(x_1,x_2,x_3,x_4) and q=(x5,x6)q=(x_5,x_6). Fixing qq gives a fiber of retained coordinates (t,v)(t,v). Negating qq preserves K236K_{236}, so opposite source positions have identical fibers. Choose the four representatives

(d1,d2,d3,d4)=((1,0),(0,1),(1,1),(1,−1)).(d_1,d_2,d_3,d_4)=((1,0),(0,1),(1,1),(1,-1)).

Replace the two coordinates qq by four block coordinates zz. Copy the central fiber to the eight signed axes, and the fiber at each pair {di,−di}\{d_i,-d_i\} to the eight positions whose only zero coordinate is ii:

E={±e1,…,±e4},Fi={z∈F34:zi=0, zj≠0 for j≠i},1≤i≤4.E=\{\pm e_1,\ldots,\pm e_4\},\qquad F_i=\{z\in\mathbb{F}_3^4:z_i=0,\ z_j\ne0\text{ for }j\ne i\},\qquad1\le i\le4.

Explicitly, in coordinates (t,z,v)∈F3×F34×F34(t,z,v)\in\mathbb{F}_3\times\mathbb{F}_3^4\times\mathbb{F}_3^4, define

K={(t,z,v):z∈E, (t,v,0,0)∈K236}∪⋃i=14{(t,z,v):z∈Fi, (t,v,di)∈K236}.(2)\begin{aligned} K={}&\{(t,z,v):z\in E,\ (t,v,0,0)\in K_{236}\}\\ &\cup\bigcup_{i=1}^{4}\{(t,z,v):z\in F_i,\ (t,v,d_i)\in K_{236}\}. \tag*{(2)} \end{aligned}

Here (t,v,di)(t,v,d_i) denotes concatenation of the retained coordinates with the two entries of did_i.

For example, setting q=0q = 0 in HH leaves the signings of supports 123 and 124, hence 16 vectors. Each of the eight EE blocks in the upper layer contains a copy of these 16 points. The same count holds for H′H', using supports 134, 234; the central fiber of E6E_{6} has eight points. For a source layer of size ss with cc points at q=0q = 0, the lift gives 8c+4(s−c)=4(s+c)8c + 4(s - c) = 4(s + c) points, as summarized in Table 2.

Source layerSize ssCentral fiber ccLifted size 4(s+c)4(s + c)
HH11216512
E6E_{6}12880
H′H'11216512
Total236401104

Table 2. The reflection lift takes the three layers of K236K_{236} to those of KK.

Write B+,M,B−B_{+}, M, B_{-} for the layers of KK at t=1,0,−1t = 1, 0, -1, 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 tt, zz and represents a four-dimensional affine flat; the 81 possible dot positions encode vv. Repeated patterns are the copied fibers of HH, E6E_{6}, and H′H'.

The three layers of the 1104-cap $K$ at a common scale

Figure 1. The three layers of the 1104-cap KK at a common scale; each dot is one point. Columns and rows encode (z1,z2)(z_1,z_2) and (z3,z4)(z_3,z_4) for blocks, (v1,v2)(v_1,v_2) and (v3,v4)(v_3,v_4) for dots within blocks. Both 9×99 \times9 grids use lexicographic pair order, −1<0<1-1 < 0 < 1, rightwards and upwards. Colors label E,F1,…,F4E,F_1,\ldots,F_4. Positions encode coordinates; three dots aligned on the page need not represent collinear points over F3\mathbb{F}_3.

The reflection lift

We now formulate the reflection lift of Section 2 in general and prove that it preserves the cap property. Let VV have dimension mm, and let S⊆F32×VS \subseteq\mathbb{F}_3^2 \times V be a cap unchanged by the simultaneous sign flip

g(q1,q2,v)=(−q1,−q2,v).g(q_1,q_2,v)=(-q_1,-q_2,v).

The fibers Sq={v∈V:(q,v)∈S}S_q=\{v\in V:(q,v)\in S\} satisfy Sq=S−qS_q=S_{-q}. Choose representatives d1,…,d4d_1,\ldots,d_4 for the four nonzero pairs {q,−q}\{q,-q\}, and write C=S0C=S_0 and Ai=Sdi=S−diA_i=S_{d_i}=S_{-d_i}. Thus

S=({0}×C)∪⋃i=14({di,−di}×Ai).(3)S=(\{0\}\times C)\cup\bigcup_{i=1}^{4}(\{d_i,-d_i\}\times A_i). \tag*{(3)}

The fixed cap points are exactly those above q=0q=0. Put c=∣C∣c=|C|, ai=∣Ai∣a_i=|A_i| and s=∣S∣=c+2∑iais=|S|=c+2\sum_i a_i. Empty or repeated fibers are allowed.

Using the block positions E,Fi⊆F34E,F_i\subseteq\mathbb{F}_3^4, copy CC to EE and each AiA_i to FiF_i. The reflection lift is

R2(S,g)=(E×C)∪⋃i=14(Fi×Ai).(4)R_2(S,g)=(E\times C)\cup\bigcup_{i=1}^{4}(F_i\times A_i). \tag*{(4)}

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 R2(S,g)⊆F3m+4R_2(S,g)\subseteq\mathbb{F}_3^{m+4} is a cap of size

∣R2(S,g)∣=8(c+∑iai)=4(s+c).|R_2(S,g)|=8\left(c+\sum_i a_i\right)=4(s+c).

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:

0∉C+Ai+Ai,0∉Ai+Aj+Ak(i,j,k distinct).(5)0\notin C+A_i+A_i,\qquad0\notin A_i+A_j+A_k\quad(i,j,k\ \text{distinct}). \tag*{(5)}

The first restriction comes from the three source addresses 00, did_i, −di-d_i. For the second, write dk=adi+bdjd_k=ad_i+bd_j with a,b∈{±1}a,b\in\{\pm1\}, possible because the three direction pairs are distinct. The addresses adiad_i, bdjbd_j, −dk-d_k 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 (zr,vr)(z_r,v_r), r=1,2,3r=1,2,3, sum to zero. The block addresses zrz_r and local vectors vrv_r must separately sum to zero. If two block addresses agree, then z1+z2+z3=0z_1+z_2+z_3=0 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 EE has one nonzero coordinate; an address in FiF_i has exactly one zero coordinate, at position ii. These support patterns leave only two possible types of zero-sum address triple:

E,Fi,FiorFi,Fj,Fk(i,j,k distinct).E,F_i,F_i\qquad\text{or}\qquad F_i,F_j,F_k\quad(i,j,k\ \text{distinct}).

Indeed, two distinct EE addresses have a sum with zero or two nonzero coordinates, whose negative is unoccupied. With exactly one EE address, the other two must have the same missing coordinate: otherwise the EE address would need two nonzero coordinates to cancel their sum. For three addresses in the FiF_i, 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 (q,v)↦(Bq,Av+b)(q,v)\mapsto(Bq,Av+b). The map BB permutes the four source direction pairs, say by σ\sigma. The lifted map (z,v)↦(Pσz,Av+b)(z,v)\mapsto(P_\sigma z,Av+b) carries one lift to the other, where Pσei=eσ(i)P_\sigma e_i=e_{\sigma(i)}.

Applying the lift to K236K_{236}. For completeness, we first verify the classical source.

Lemma 3. The set K236K_{236} in (1) is a cap.

Proof. Each layer is a cap. A triple meeting all three layers would require a point of HH and a point of H′H' 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 KK in Theorem 1. The sign flip (t,v,q)↦(t,v,−q)(t,v,q)\mapsto(t,v,-q) preserves each layer of K236K_{236}. Apply Theorem 2 with local space V=F3×F34V=\mathbb{F}_3\times\mathbb{F}_3^4 retaining (t,v)(t,v) and the direction representatives chosen in Section 2. After reordering the coordinates to (t,z,v)(t,z,v), the resulting lift is exactly (2). It is therefore a cap, including across layers. Table 2 gives c=40c=40, so its size is 4(236+40)=11044(236+40)=1104, 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 B−B_- with B+=R2(H,g)B_+=R_2(H,g), and an invertible linear map sends B+B_+ 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 383^8 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 (s,c)(s,c) becomes (4(s+c),4c)(4(s+c),4c). The source (236,40)(236,40) gives (1104,160)(1104,160), 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 HH, retain five complementary coordinates, and replace the scalar’s value by one of the sets already defined:

A0=P,A1=Q1,A−1=Q−1.A_0=P,\qquad A_1=Q_1,\qquad A_{-1}=Q_{-1}.

These classical ingredients [8 Section 3] have sizes 80, 32, 32 and are disjoint. Each pairwise union is a cap: P∪Q1=HP\cup Q_1=H, reversing one coordinate carries it to P∪Q−1P\cup Q_{-1}, and Q1∪Q−1Q_1\cup Q_{-1} is the cube {±1}6\{\pm1\}^6. This property permits the following coordinate substitution.

Lemma 4 (Coordinate substitution). Let A0,A1,A−1⊆F3rA_0, A_1, A_{-1} \subseteq\mathbb{F}_3^r be disjoint, with each pairwise union a cap. If

S=⋃i∈F3({i}×Si)⊆F3nS = \bigcup_{i\in\mathbb{F}_3} (\{i\} \times S_i) \subseteq\mathbb{F}_3^n

is a cap, then

Φ(S)=⋃i∈F3(Si×Ai)⊆F3n+r−1\Phi(S) = \bigcup_{i\in\mathbb{F}_3} (S_i \times A_i) \subseteq\mathbb{F}_3^{n+r-1}

is a cap of size ∑i∣Si∣∣Ai∣\sum_i |S_i||A_i|.

Proof. Consider three points (yj,aj)(y_j,a_j) of Φ(S)\Phi(S) summing to zero, with aj∈Aija_j \in A_{i_j}. If the labels iji_j use at most two values, the aja_j lie in one of the pairwise unions and hence coincide; disjointness makes their labels equal. Otherwise the labels are 0,1,−10,1,-1. In either case i1+i2+i3=0i_1+i_2+i_3=0, so the corresponding source points (ij,yj)(i_j,y_j) sum to zero and must coincide. All three aja_j now lie in the same cap AiA_i, 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 PP, Q1Q_1, Q−1Q_{-1} above. The 80-point set PP consists of Hill’s sparse vectors; it is distinct from the 80-point middle layer MM of KK. If the source has NN points and its zero section has mm points, then

∣Φ(S)∣=80m+32(N−m)=32N+48m,Φ(S)⊆F3n+5.(6)|\Phi(S)| = 80m + 32(N-m) = 32N + 48m,\qquad\Phi(S) \subseteq\mathbb{F}_3^{n+5}. \tag*{(6)}

Each point in the zero section receives 80 replacements instead of 32, so we seek a large section of HH.

A noncentral 45-section. In our coordinates, the linear functional ℓ(x)=x3+x4+x5\ell(x)=x_3+x_4+x_5 gives

∣H∩{ℓ=0}∣=22,∣H∩{ℓ=1}∣=∣H∩{ℓ=−1}∣=45.|H \cap\{\ell=0\}|=22,\qquad|H \cap\{\ell=1\}|=|H \cap\{\ell=-1\}|=45.

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 HH is centered at the origin, the two 45-sections are noncentral.

Construction of LL in Theorem 1. Set

α(x)=x3+x4+x5−1,y(x)=(x1,x2,x4,x5,x6).\alpha(x)=x_3+x_4+x_5-1,\qquad y(x)=(x_1,x_2,x_4,x_5,x_6).

The map x↦(α(x),y(x))x\mapsto(\alpha(x),y(x)) is an affine coordinate change: x3=α+1−x4−x5x_3=\alpha+1-x_4-x_5. Define explicitly

L={(y(x),a):x∈H, a∈Aα(x)}⊆F311.(7)L=\{(y(x),a):x\in H,\ a\in A_{\alpha(x)}\}\subseteq\mathbb{F}_3^{11}. \tag*{(7)}

The source sections at α=0,1,−1\alpha=0,1,-1 have sizes 45, 45, 22. Lemma 4 proves that LL is a cap, and

∣L∣=80⋅45+32⋅45+32⋅22=5744.|L|=80\cdot45+32\cdot45+32\cdot22=5744.

An ordinary coordinate, such as x6x_6, gives sections of sizes 40, 36, 36 and hence 80⋅40+32(36+36)=550480\cdot40+32(36+36)=5504, recovering the signed-support construction of [6 Corollary 2]. Choosing α=ℓ−1\alpha=\ell-1 assigns the larger replacement set to a noncentral 45-section instead of that central 40-section, gaining exactly

(80−32)(45−40)=240.(80-32)(45-40)=240.

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. [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. [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. [3]H. (M.) R. Thackeray, The cap set problem: Up to dimension 7, arXiv:2206.09804 (2022). https://arxiv.org/abs/2206.09804.
  4. [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. [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. [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. [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. [8]Y. Edel, Extensions of generalized product caps, Designs, Codes and Cryptography 31 (2004), 5–14. https://www.yvesedel.de/Papers/ExtProd.pdf.

Paper details

vlnc:W_6uq9gawv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents