Beating Product Constructions for Linear Equations Over Finite Fields

Technical Summary: Beating Product Constructions for Linear Equations Over Finite Fields

Problem Statement
The paper addresses the asymptotic behavior of the size of the largest subset of a finite vector space $\mathbb{F}_q^n$ that avoids non-trivial solutions to a specific class of linear equations. Specifically, it focuses on translation-invariant linear equations of genus one. A linear form $L(x_1, \dots, x_s) = \sum c_i x_i$ is translation-invariant if $\sum c_i = 0$. It is of genus one if no non-empty proper subset of the coefficients sums to zero.

The primary motivation is the cap set problem (the case where $q=3$ and $L(x,y,z) = x+y+z=0$), which asks for the asymptotic growth rate of the maximum size of a cap set, denoted $r_3(\mathbb{F}_3^n)$. While the polynomial method (Ellenberg and Gijswijt) established an exponential upper bound, the best known lower bounds are derived from finite-dimensional constructions extended via direct products. If a set $A \subseteq \mathbb{F}_q^n$ is solution-free, then $A \times A \subseteq \mathbb{F}_q^{2n}$ is also solution-free. Iterating this yields a lower bound of the form $c^n$, where $c = |A|^{1/n}$.

The central question investigated is whether a fixed finite-dimensional construction $A$ can be asymptotically optimal via direct products alone. In other words, is it possible that for some $A$, the sequence of sets generated by $A^k$ provides the best possible exponential base $c$?

Methodology
The authors develop a construction that strictly improves upon the lower bounds obtained by direct products of any given solution-free set. The methodology involves two main stages:

1. Elimination of Partial Solutions (Lemma 3.1):
   For a general genus-one equation $L$, the authors first transform an initial $L$-free set $A$ into a larger set $A' \subseteq \mathbb{F}_q^{kn}$ (where $k$ depends on $s$). This transformation ensures that $A'$ not only avoids full solutions to $L=0$ but also avoids solutions to any "partial" equation involving at most $s-2$ variables. This is achieved by taking a product of translates of $A$ and selecting translation vectors $t_I$ such that the partial sums $\sum_{i \in I} c_i(A+t_I)$ do not contain 0.

2. Extended Product Construction with Linear Transformations:
   The core innovation is a construction that combines direct products with invertible linear transformations.

   • For Cap Sets ($q=3$): The authors construct two specific cap sets $A_1, A_2 \subseteq \mathbb{F}_3^{2n}$ derived from $A$. $A_1$ is the standard direct product $A \times A$, and $A_2$ is a linear image $T(A \times A)$ where $T(x,y) = (x+y, x-y)$. Crucially, these sets are constructed such that $0 \notin A_1 \cup A_2$ and $0 \notin A_1 + A_2$.
   • General Case: A similar construction is applied to $A'$ using a family of linear maps $T_{\ell, m}$ to create sets $A_1$ and $A_2$ in a higher dimension.
   • Union of Shifted Products: The final set $B$ is formed by taking the union of $r$ distinct "blocks" (direct products) of $A_1$ and $A_2$, interspersed with zero blocks. Specifically, $B = \bigcup_{j=1}^r (A_1^{j-1} \times \{0\} \times A_2^{r-j})$.

   The proof that $B$ is solution-free relies on analyzing the distribution of variables across the blocks. If a solution existed, the distinct positions of the zero blocks and the properties of $A_1, A_2$ (specifically the absence of 0 and the sum-free property of $A_1+A_2$) force the solution to be trivial (all variables equal).

Key Contributions and Results

• Theorem 1.1 (Cap Sets): For any cap set $A \subseteq \mathbb{F}_3^n$, and for any integer $r \ge 1$, there exists a cap set $B \subseteq \mathbb{F}_3^{2nr}$ of size $|B| = r |A|^{2r-2}$.
• Corollary 1.2: If $A$ has size $c^n$, there exists a cap set $B$ in a higher dimension with size strictly greater than $c^m$. This proves that no single cap set $A$ yields an asymptotically optimal lower bound via direct products alone.
• Theorem 1.3 (General Genus One Equations): The result is generalized to any translation-invariant linear equation of genus one over $\mathbb{F}_q$. For any $L$-free set $A$, a larger $L$-free set $B$ is constructed with a size strictly exceeding the product bound.
• Dimensional Analysis: The construction increases the dimension significantly (by a factor of roughly $2s(s-1)$), but the increase in the base of the exponential growth is guaranteed.

Significance and Claims
The paper claims a theoretical breakthrough in the understanding of lower bounds for solution-free sets:

1. Non-Optimality of Product Constructions: The primary result is the definitive answer that direct products are never asymptotically optimal. For any finite-dimensional construction $A$, one can always construct a larger set $B$ in a higher dimension that breaks the exponential base $c = |A|^{1/n}$. This resolves a question raised by the second author and others regarding the potential optimality of existing constructions like those by Edel or recent AI-assisted searches.
2. Modest Quantitative Impact: The authors are explicit that while the result is theoretically significant, the quantitative improvement is negligible.
   • The improvement to the constant $c$ is a factor of $(r/|A|^2)^{1/2nr}$.
     Applying this to the current record for cap sets ($c \approx 2.2203$), the improvement would only appear in the 452nd decimal place.
   • For progression-free sets in $\mathbb{F}_5^n$, the improvement is on the order of $10^{-11}$.
   • The authors emphasize that the value of the theorem lies in the existence of an improvement, not the magnitude of it. The construction does not currently offer a practical path to significantly better lower bounds for the cap set problem, but it establishes that the "product barrier" is not a hard limit.

In summary, the paper demonstrates that the strategy of simply iterating direct products of a fixed set cannot yield the true asymptotic limit for solution-free sets. Any such limit must arise from a fundamentally different type of construction or a sequence of constructions that do not stabilize on a single base set $A$.