Beating Product Constructions for Linear Equations Over Finite Fields

技術要約：有限体上の線形方程式における積構成の打破

問題提起
本論文は、特定のクラスの線形方程式に対する解を持たない、有限ベクトル空間 $\mathbb{F}_q^n$ の最大部分集合のサイズのアスンプトティック（漸近的）な挙動を扱っている。具体的には、種数（genus）1の並進不変な線形方程式に焦点を当てている。線形形式 $L(x_1, \dots, x_s) = \sum c_i x_i$ が並進不変であるとは、$\sum c_i = 0$ であることを指す。また、係数の空でない真の部分集合の和がゼロにならない場合、その形式は種数1である。

主な動機は、キャップセット問題（$q=3$ かつ $L(x,y,z) = x+y+z=0$ のケース）であり、これは最大サイズのキャップセット $r_3(\mathbb{F}_3^n)$ の漸近的な成長率を問うものである。多項式法（Ellenberg and Gijswijt）によって指数的な上界が確立された一方で、既知の最良の下界は、**直積（direct products）**を通じて有限次元の構成を拡張することによって得られている。もし集合 $A \subseteq \mathbb{F}_q^n$ が解を持たない（solution-free）ならば、$A \times A \subseteq \mathbb{F}_q^{2n}$ もまた解を持たない。これを反復することで、$c = |A|^{1/n}$ となる $c^n$ という形の型の下界が得られる。

本研究の中心的な問いは、固定された有限次元の構成 $A$ が、直積のみによって**漸近的に最適（asymptotically optimal）**になり得るか、という点である。言い換えれば、ある $A$ に対して、集合の列 $A^k$ が生成する直積が、最良の指数底 $c$ を提供する可能性があるのだろうか。

手法
著者らは、与えられた解を持たない集合の直積によって得られる下界を厳密に上回る構成を開発している。その手法は主に2つの段階で構成される：

1. 部分解の除去 (Lemma 3.1):
   一般的な種数1の方程式 $L$ に対して、著者らはまず、初期の $L$-free な集合 $A$ を、より大きな集合 $A' \subseteq \mathbb{F}_q^{kn}$（ここで $k$ は $s$ に依存する）へと変換する。この変換により、$A'$ は $L=0$ の完全な解を避けるだけでなく、高々 $s-2$ 個の変数を含む「部分的な」方程式の解をも回避することを保証する。これは、$A$ の平行移動の積を取り、部分和 $\sum_{i \in I} c_i(A+t_I)$ が 0 を含まないような平行移動ベクトル $t_I$ を選択することによって達成される。

2. 線形変換を用いた拡張積構成:
   核となる革新は、直積と可逆な線形変換を組み合わせた構成である。

   • キャップセットの場合 ($q=3$): 著者らは、$A$ から派生した2つの特定のキャップセット $A_1, A_2 \subseteq \mathbb{F}_3^{2n}$ を構成する。$A_1$ は標準的な直積 $A \times A$ であり、$A_2$ は線形写像 $T(x,y) = (x+y, x-y)$ による線形像 $T(A \times A)$ である。決定的なのは、これらの集合が $0 \notin A_1 \cup A_2$ かつ $0 \notin A_1 + A_2$ を満たすように構成されている点である。
   • 一般の場合: 同様の構成が、線形写像の族 $T_{\ell, m}$ を用いて $A'$ に対して適用され、より高次元の集合 $A_1$ と $A_2$ を作成する。
   • シフトされた積の和集合: 最終的な集合 $B$ は、$A_1$ と $A_2$ の（ゼロブロックを挟んだ）$r$ 個の異なる「ブロック」（直積）の和集合として形成される。具体的には、$B = \bigcup_{j=1}^r (A_1^{j-1} \times \{0\} \times A_2^{r-j})$ である。

$B$ が解を持たないことの証明は、ブロック間における変数の分布を分析することに基づいている。ゼロブロックの異なる位置と、$A_1, A_2$ の性質（$0$を含まないこと、および$A_1+A_2$ が和集合として解を持たないこと）により、もし解が存在したとしても、それは自明な解（すべての変数が等しい場合）に限られることが強制される。

主要な貢献と結果

• 定理 1.1 (キャップセット): 任意のキャップセット $A \subseteq \mathbb{F}_3^n$ および任意の整数 $r \ge 1$ に対して、サイズ $|B| = r |A|^{2r-2}$ を持つキャップセット $B \subseteq \mathbb{F}_3^{2nr}$ が存在する。
• 系 1.2: $A$ がサイズ $c^n$ を持つとき、より高い次元においてサイズ $c^m$ を超えるキャップセット $B$ が存在する。これは、単一のキャップセット $A$ が直積のみによって漸近的に最適な下界を与えることはできないことを証明している。
• 定理 1.3 (一般の種数1の方程式): この結果は、$\mathbb{F}_q$ 上の任意の並進不変な種数1の線形方程式へと一般化される。任意の $L$-free な集合 $A$ に対して、積の境界を厳密に超えるより大きな $L$-free な集合 $B$ が構成される。
• 次元解析: この構成は次元を大幅に増加させるが（およそ $2s(s-1)$ 倍）、指数成長の底の増加は保証されている。

意義と主張
本論文は、解を持たない集合に関する下界の理解における理論的なブレイクスルーを主張している：

1. 積構成の非最適性: 主要な結果は、直積構成は決して漸近的に最適ではないという決定的な回答である。いかなる有限次元の構成 $A$ に対しても、指数底 $c = |A|^{1/n}$ を破るような、より大きな集合 $B$ を高次元において構成することができる。これは、Edelによるものや最近のAI支援探索による既存の構成の潜在的な最適性に関する、第2著者らによる疑問に答えるものである。
2. 控えめな定量的影響: 著者らは、理論的には重要であるものの、定量的な改善は微々たるものであることを明示している。
   • $c$ への改善は、因子 $(r/|A|^2)^{1/2nr}$ である。
   • キャップセットの現在の記録（$c \approx 2.2203$）にこれを適用すると、改善は452桁目にしか現れない。
   • $\mathbb{F}_5^n$ における等差数列フリー集合の場合、改善は $10^{-11}$ のオーダーである。
   • 著者らは、この定理の価値は改善の存在にあるのであって、その大きさにあるのではないことを強調している。この構成は、現在、キャップセット問題に対して大幅に優れた下界を得るための実用的な道筋を提供するものではないが、「積の障壁」が硬い限界ではないことを確立している。

要約すると、本論文は、固定された集合の直積を単に反復する戦略は、解を持たない集合の真の漸近的極限を与えることはできないことを示している。そのような極限は、根本的に異なる種類の構成、あるいは単一の底集合 $A$ に収束しない一連の構成から生じなければならない。