Small complete 3-term progression free sets in cyclic groups and vector spaces

技術要約：巡回群およびベクトル空間における、小さい完全な3項等差数列フリー集合

問題設定
本論文は、代数構造、具体的には巡回群 ($\mathbb{Z}_m$) および有限ベクトル空間 ($\mathbb{F}_p^n$) における、完全な 3項等差数列（3-AP）フリー集合の最小サイズを決定する問題に取り組んでいる。最大サイズの3-APフリー集合は加法的組合せ論の中心的なテーマであるが（例：Rothの定理、Croot-Lev-Pach、Ellenberg-Gijswijt）、完全な集合（これ以上拡張すると3-APが生成されてしまう集合）の最小サイズは、その下限側の類似問題である。単純な計数論的議論により、この最小サイズのオーダーは、構造の大きさの平方根以上であることが確立されている。著者らは、巡回群においてサイズ $O(\sqrt{|G|})$ の集合が存在するかどうか、およびベクトル空間において $p^{n/2}$ となるかという、平方根の下限のタイトさに関する未解決問題について調査している。

手法
著者らは、明示的な組合せ論的構成、モジュロ簡約技術、および有限体上の代数幾何学を組み合わせて用いている。

1. 巡回群 ($\mathbb{Z}_m$):

   • より強い性質: 著者らは、完全な (2, -1)-回避 集合に焦点を当てている。集合 $A$ が (2, -1)-回避であるとは、$A \cap (2A \dot{-} A) = \emptyset$ （ここで $2A \dot{-} A = \{2a - b : a, b \in A, a \neq b\}$）を満たすことを指す。これが完全であるとは、$G = A \cup (2A \dot{-} A)$ であることである。この性質は、外部の点が中点としてではなく、端点として等差数列を持つことを強制するため、完全3-APフリーであることよりも強い性質である。
   • R-完全集合: この構成は、「R-完全」集合（区間 $[0, R]$ 内の整数部分集合であり、内部的に (2, -1)-回避であり、かつ区間 $[-R, 2R]$ を飽和させているもの）に依存している。
   • 二進数字構成: 一般化された二進数字構成（補題3.3）を用いて、サイズ $2^n$ の $S_n$-完全な集合 $P$ を生成する。桁の数列 $d_i$ を慎重に選択することで、結果として得られる集合が幅広い法 $m$ をカバーするようにしている。
   • モジュロ簡約: 補題3.2は、$\mathbb{Z}$ における $R$-完全集合が、$2R < m \leq 3R + 1$ であるときに $\mathbb{Z}_m$ における完全な (2, -1)-回避集合へと降下することを示している。
   • 有限の検証: 一般的な構成が適用できない場合、または完全な (2, -1)-回避集合が存在しない可能性がある小さな法 $m < 81$ については、全探索による列挙を行っている。

2. ベクトル空間 ($\mathbb{F}_p^n$):

   • 二次形式グラフ: 構成の核となるのは、同次二次写像 $Q: U \to W$ のグラフである。具体的には、$A_Q = \{(u, Q(u)) : u \in U\}$ という形の集合を構成する。
   • 端点-中点完全性: 著者らは、「端点-中点完全」集合を定義している。これは、外部の点が $A$ の要素によって端点 ($x = 2a - b$) とも中点 ($2x = c + d$) とも表現できる集合である。この性質は、積構成において極めて重要である。
   • 部分体構成: 拡大体 $E = \mathbb{F}_{p^{kL}}$ と部分体 $T = \mathbb{F}_{p^k}$ において、非平方数 $\delta$ を用いた二次写像 $Q(x, s) = x^2 - \delta s^2$ を構成する。指標和とワイルの評価（Weil bound）を用いることで、この写像が全射であり、自明な核を持つことを証明し、特定の次元 $n_0 = k(2L+1)$ における完全な (2, -1)-回避集合を得る。
   • 積補題: すべての次元 $n$ へ結果を拡張するために、積補題（補題4.2）を用いる。もし $A$ が部分空間において端点-中点完全であり、$B$ が残りの座標において完全3-APフリーであれば、その積 $A \times B$ は全空間において完全3-APフリーとなる。これにより、特殊な次元をより小さな集合で「パディング」することで、任意の $n$ をカバーすることが可能になる。

主要な貢献と結果

1. 巡回群:

   • 定理 1.2: すべての整数 $m \geq 1$ に対して、サイズ $|A| < 2\sqrt{m}$ を満たす完全3-APフリー集合 $A \subseteq \mathbb{Z}_m$ が存在する。
   • 大きな $m$ に対するより強い結果: $m \geq 81$ の場合、構成された集合はより強い完全 (2, -1)-回避の性質を満たす。
   • 小さな法: 本論文は、$m \leq 80$ における $a(3\text{-AP}, \mathbb{Z}_m)$ および $a(2, -1)(\mathbb{Z}_m)$ の正確な値の表を提供しており、特定の小さな法（例：$m \in \{2, 5, 6, 8, 17, 18, 19, 20\}$）では完全 (2, -1)-回避集合が存在しないことを指摘している。

2. ベクトル空間:

   • 定理 1.3: 固定された奇素数 $p$ と $\epsilon > 0$ に対して、すべての $n \geq 1$ について以下を満たす定数 $C_{p,\epsilon}$ が存在する：
     $$a(3\text{-AP}, \mathbb{F}_p^n) \leq C_{p,\epsilon} n^{1+\epsilon} p^{n/2} = p^{n/2 + o(n)}$$
   • この結果は、指数バージョンの問題を、指数的な成長率に関して、指数が正確に $n/2$ となる形で解決している。これは、自明な計数による下限が、劣指数関数的な因子を除いて本質的にシャープであることを裏付けている。

意義と主張
本論文は、完全な進行数列フリー集合に関する平方根の下限のタイトさに関する2つの未解決問題を解決したと主張している：

• 巡回群: 下限が（絶対定数である2まで）タイトであることを示し、$m \geq 81$ に対してより強い (2, -1)-回避の性質を持つ明示的な構成を提供した。
• ベクトル空間: 固定された奇素数体における指数バージョンの問題を解決し、最小サイズが $p^{n/2 + o(n)}$ であることを示した。これは、自明な計数による下限が、指数的な成長率において本質的にシャープであることを確認するものである。

著者らは、巡回群の結果における定数因子（2）が、彼らの以前の研究で示唆された $3/2$ という目標値を上回っていることに触れており、この構成は意図的に、より強い (2, -1)-回避の性質に限定されているとしている。標準的な3-AP完全性（外部の点を中点として許容する性質）の余分な自由度を利用すれば、より小さな構成が得られる可能性があることを示唆している。同様に、ベクトル空間についても、すべての次元において一様な絶対定数が存在するか、およびすべての次元において完全 (2, -1)-回避集合の境界が存在するかという問題は依然として未解決である。本研究は、これらの加法的組合数学の問題を、有限幾何学、特に完全キャップ（complete caps）や飽和集合（saturating sets）へと結びつけている。