Cap set問題(cap set problem)とは、$\mathbb{F}_3^n$ の部分集合で同じ直線上の異なる 3 点を含まないもの(cap set)の最大の大きさを問う問題である。$\mathbb{F}_3^n$ では 3 点が直線上にあることと 3 項の等差数列をなすこと、和が $0$ であることが同値なので、3 項等差数列を含まない集合の問題でもある。Ellenberg–Gijswijt は Croot–Lev–Pach の多項式の方法を使い、cap set の大きさが $3\cdot2.756^n$ 以下であることを示した。証明は、和が $0$ であることの指示関数を低次の単項式で分け、対角な 3 変数関数のスライスランクと比べる線形代数の議論である。
Cap set 問題(cap set problem)とは、$3$ 元体 $\mathbb{F}_3$ 上の $n$ 次元空間 $\mathbb{F}_3^n$ の部分集合で、同じ直線上に並ぶ異なる 3 点を含まないもの(cap set)が、どれほど大きくなりうるかを問う問題である。$\mathbb{F}_3^n$ では 3 点が同じ直線上にあることと 3 項の等差数列をなすことが同じなので、これは「3 項の等差数列を含まない集合の最大の大きさ」を問う問題でもある。
全体の大きさは $3^n$ である。cap set の大きさの上界は Meshulam の $O(3^n/n)$ などと少しずつ改良されてきたが(EG17 p. 1)、$(3-\varepsilon)^n$ の形の上界があるかどうかは長く分からなかった。2016 年に Croot–Lev–Pach が $(\mathbb{Z}/4\mathbb{Z})^n$ で多項式を使う新しい方法を見つけ、Ellenberg と Gijswijt がそれを $\mathbb{F}_3^n$ に移して、cap set の大きさは $2.756^n$ 程度で抑えられることを示した(EG17)。証明は短い線形代数の議論である。
この記事では、cap set を定義して小さい例と下界の構成を述べ、Tao による対称な定式化(Tao16)に沿って、3 変数関数の「スライスランク」を使った Ellenberg–Gijswijt の上界の完全な証明を与える。
$\mathbb{F}_3^n$ の 直線 とは、$x\in\mathbb{F}_3^n$ と $0$ でない $d\in\mathbb{F}_3^n$ によって $\{x,\ x+d,\ x+2d\}$ と書ける 3 点の集合である。
$x,y,z\in\mathbb{F}_3^n$ が相異なるとき、次は同値である。
$\mathbb{F}_3$ では $3=0$、$-2=1$、$2=-1$ である。2 ⇔ 3:$y-x=z-y$ は $x+z=2y=-y$、すなわち $x+y+z=0$ と同値である。3 ⇒ 1:$d:=y-x\ne0$ とおくと、$x+2d=2y-x=-y-x=z$ なので、$\{x,y,z\}=\{x,x+d,x+2d\}$ である。1 ⇒ 3:$\{x,y,z\}=\{x',x'+d,x'+2d\}$ なら $x+y+z=3x'+3d=0$ である。最後の主張:$x=y$ なら $z=-2x=x$ である。$\square$
条件 2 は順番によらない。3 の条件が対称だからである。とくに、$\mathbb{F}_3^n$ の任意の 2 点 $x\ne y$ について、それらを通る直線はただ 1 つで、3 点目は $-x-y$ である。
$A\subset\mathbb{F}_3^n$ が cap set であるとは、$A$ が同じ直線上の相異なる 3 点を含まないことをいう。lem-cap-line により、これは次と同値である:$x,y,z\in A$ が $x+y+z=0$ をみたすのは $x=y=z$ のときに限る。$\mathbb{F}_3^n$ の cap set の大きさの最大値を $r(n)$ と書く。
カードゲーム SET の 81 枚のカードは、4 つの属性がそれぞれ 3 通りの値をとるので $\mathbb{F}_3^4$ の点と見なせ、ゲームの「セット」(各属性で 3 枚が全部同じか全部違う)は $\mathbb{F}_3^4$ の直線にあたる。各属性で「全部同じか全部違う」ことは、その成分の和が $0$ であることと同じだからである。
$n=1$:$\mathbb{F}_3$ 自身が 1 本の直線なので、$r(1)=2$ である。$n=2$:$\{(0,0),(0,1),(1,0),(1,1)\}$ は cap set で、$r(2)=4$ である。$n=3$ では $r(3)=9$ である。$r(2)=4$、$r(3)=9$ は、全ての部分集合を分枝限定法で調べる計算で確かめた。$n=4$ では、次の $20$ 点(成分を並べて書く)は cap set である:$0020$, $0100$, $0201$, $0202$, $0221$, $0222$, $1001$, $1002$, $1021$, $1022$, $1120$, $1200$, $2001$, $2002$, $2010$, $2020$, $2200$, $2210$, $2221$, $2222$。どの 2 点 $x\ne y$ についても 3 点目 $-x-y$ がこの中にないことは、$190$ 組を調べれば確かめられる。
1:$x,y,z\in\{0,1\}^n$ で $x+y+z=0$ とする。各成分で $x_i+y_i+z_i$ は整数として $0,1,2,3$ のどれかで、$3$ で割り切れるのは $0$ か $3$、すなわち $x_i=y_i=z_i$ のときだけである。よって $x=y=z$。2:$(a_1,b_1)+(a_2,b_2)+(a_3,b_3)=0$ なら $a_1+a_2+a_3=0$ と $b_1+b_2+b_3=0$ なので、$a_1=a_2=a_3$ かつ $b_1=b_2=b_3$ である。$\square$
$r(4)\ge20$ と 2 を合わせると $r(4k)\ge20^k$ で、$r(n)\ge20^{\lfloor n/4\rfloor}$ を得る($20^{1/4}=2.114\dots$)。EG17 の時点(2016 年)で知られていた最良の下界は $2.2^n$ 程度である(EG17 p. 1、Edel の構成)。thm-cap-main の上界の底 $2.756$ との間には隔たりがある。
$\mathbb{F}$ を体、$A$ を有限集合とし、関数 $T\colon A\times A\times A\to\mathbb{F}$ を考える。
$T\colon A^3\to\mathbb{F}$ が スライス であるとは、ある関数 $f\colon A\to\mathbb{F}$、$g\colon A^2\to\mathbb{F}$ によって、$T(x,y,z)=f(x)g(y,z)$、$f(y)g(x,z)$、$f(z)g(x,y)$ のどれかの形に書けることをいう。$T$ をスライスの和として書くときの項の個数の最小値を $T$ の スライスランク という。
2 変数の関数($A\times A$ の行列)では、$f(x)g(y)$ の形の和として書く項の個数の最小値が 行列の階数 であった。スライスランクはその 3 変数版の 1 つで、1 つの変数だけを切り離せればよい。Tao16 はこれを単に rank と呼んでいる。
$c_a\in\mathbb{F}$($a\in A$)がすべて $0$ でないとき、
$$
T(x,y,z)=\sum_{a\in A}c_a\,\delta_a(x)\,\delta_a(y)\,\delta_a(z)
$$
のスライスランクは $|A|$ である。ここで $\delta_a(x)$ は $x=a$ のとき $1$、それ以外で $0$ をとる関数である。
各項は $\delta_a(x)\cdot c_a\delta_a(y)\delta_a(z)$ というスライスなので、スライスランクは $|A|$ 以下である。逆を示すため、
$$
T(x,y,z)=\sum_{i=1}^{r_1}f_i(x)g_i(y,z)+\sum_{i=1}^{r_2}f'_i(y)g'_i(x,z)+\sum_{i=1}^{r_3}f''_i(z)g''_i(x,y)
$$
と書けたとする。$r_1+r_2+r_3\ge|A|$ を示せばよい。
関数 $h\colon A\to\mathbb{F}$ で、全ての $i\le r_3$ について $\sum_{z\in A}f''_i(z)h(z)=0$ をみたすものの全体 $V$ は、$r_3$ 個の一次方程式の解空間なので $m:=\dim V\ge|A|-r_3$ である。$V$ の基底 $h_1,\dots,h_m$ を並べた $m\times|A|$ 行列は階数 $m$ なので、ある $m$ 個の点 $z_1,\dots,z_m$ の列が正則な $m\times m$ 小行列をなす。よって $V\to\mathbb{F}^m$、$h\mapsto(h(z_1),\dots,h(z_m))$ は全単射で、$h(z_1)=\dots=h(z_m)=1$ となる $h\in V$ がとれる。
この $h$ を掛けて $z$ について和をとる。左辺は
$$
S(x,y):=\sum_{z}T(x,y,z)h(z)=\sum_{a\in A}c_ah(a)\,\delta_a(x)\delta_a(y)
$$
で、対角成分が $c_ah(a)$ の対角行列であり、そのうち少なくとも $m$ 個($a=z_1,\dots,z_m$)が $0$ でない。よって行列 $S$ の階数は $m$ 以上である。右辺では第 3 の和は $h$ の選び方から消え、
$$
S(x,y)=\sum_{i=1}^{r_1}f_i(x)\Bigl(\sum_zg_i(y,z)h(z)\Bigr)+\sum_{i=1}^{r_2}\Bigl(\sum_zg'_i(x,z)h(z)\Bigr)f'_i(y)
$$
は階数 $1$ 以下の行列 $r_1+r_2$ 個の和なので、階数は $r_1+r_2$ 以下である。よって $|A|-r_3\le m\le r_1+r_2$。$\square$
$\{0,1,2\}^n$ の元 $e$ について $|e|:=e_1+\dots+e_n$ とし、
$$
N_n:=\#\{e\in\{0,1,2\}^n : |e|\le 2n/3\}
$$
とおく。これは $\mathbb{F}_3$ 上の $n$ 変数の単項式で、各変数の次数が $2$ 以下、全次数が $2n/3$ 以下のものの個数である。
$A\subset\mathbb{F}_3^n$ を任意の部分集合とする。$T(x,y,z)$ を、$x+y+z=0$ のとき $1$、それ以外で $0$ をとる $A^3$ 上の $\mathbb{F}_3$ 値関数とすると、$T$ のスライスランクは $3N_n$ 以下である。
$\mathbb{F}_3$ では $t\ne0$ なら $t^2=1$ なので、$1-t^2$ は $t=0$ で $1$、$t\ne0$ で $0$ である。よって
$$
T(x,y,z)=\prod_{i=1}^{n}\bigl(1-(x_i+y_i+z_i)^2\bigr).
$$
各因子は $x_i,y_i,z_i$ の全次数 $2$ 以下の多項式なので、展開すると右辺は単項式 $x^ay^bz^c=\prod_ix_i^{a_i}y_i^{b_i}z_i^{c_i}$ の一次結合で、どの単項式も各 $i$ で $a_i+b_i+c_i\le2$ をみたす。とくに $a,b,c\in\{0,1,2\}^n$ で $|a|+|b|+|c|\le2n$ なので、$|a|,|b|,|c|$ のどれかは $2n/3$ 以下である。
単項式を 3 組に分ける:$|a|\le2n/3$ のものを第 1 組、残りで $|b|\le2n/3$ のものを第 2 組、残り($|c|\le2n/3$)を第 3 組とする。第 1 組を $a$ ごとにまとめると $\sum_{a}x^aF_a(y,z)$($a$ は $|a|\le2n/3$ の $\{0,1,2\}^n$ の元を動く)の形になり、各項はスライスで、項は $N_n$ 個以下である。第 2・第 3 組も同様で、$T$ は $3N_n$ 個以下のスライスの和である。$A^3$ に制限しても同じ式が成り立つ。$\square$
$A\subset\mathbb{F}_3^n$ が cap set なら $|A|\le3N_n$ である。さらに
$$
N_n\le c^n,\qquad c:=\min_{0< x\le1}\frac{1+x+x^2}{x^{2/3}}=2.7551\dots<2.756
$$
なので、$|A|\le3\cdot2.756^n$ である。
$A$ を cap set とし、lem-cap-polynomial の $T$ を考える。$x,y,z\in A$ で $x+y+z=0$ となるのは $x=y=z$ のときだけで(def-cap-main)、そのとき $x+y+z=3x=0$ なので、
$$
T(x,y,z)=\sum_{a\in A}\delta_a(x)\delta_a(y)\delta_a(z)
$$
である。lem-cap-diagonal(全ての $c_a=1$)からスライスランクは $|A|$ で、lem-cap-polynomial から $3N_n$ 以下である。よって $|A|\le3N_n$。
$N_n$ の評価:$0< x\le1$ を固定する。$|e|\le2n/3$ なら $x^{|e|-2n/3}\ge1$ なので、
$$
N_n\le\sum_{e\in\{0,1,2\}^n}x^{|e|-2n/3}=x^{-2n/3}(1+x+x^2)^n=\Bigl(\frac{1+x+x^2}{x^{2/3}}\Bigr)^{n}.
$$
右辺を最小にする $x$ は、対数微分 $\frac{1+2x}{1+x+x^2}=\frac{2}{3x}$、すなわち $4x^2+x-2=0$ の正の根 $x_0=\frac{\sqrt{33}-1}{8}=0.5930\dots$ で、$c=\frac{1+x_0+x_0^2}{x_0^{2/3}}=2.75510\dots$ である。$c<2.756$ の確認には最小値を使う必要はなく、例えば $x=0.593$ で $\frac{(1+x+x^2)^3}{x^2}< 2.756^3$ を有理数の計算で確かめればよい。$\square$
EG17 は Theorem 4(p. 2)で一般の有限体 $\mathbb{F}_q$ について、$x+y+z=0$ の代わりに $\alpha x+\beta y+\gamma z=0$($\alpha+\beta+\gamma=0$、$\gamma\ne0$)の自明でない解をもたない集合に対し $|A|\le3m_{(q-1)n/3}$($m_d$ は各変数の次数が $q-1$ 以下で全次数が $d$ 以下の単項式の個数)を示し、$q=3$ の場合を Corollary 5(p. 3)として $|A|=o(2.756^n)$ の形で述べている。ここでの $N_n$ は $q=3$ のときの $m_{2n/3}$ である。
実は $N_n^{1/n}\to c$ であり、$N_n$ の評価として底 $c$ はこれ以上小さくできない(Cramérの定理(大偏差) による。EG17 p. 3)。
多項式法 の典型は、「集合の上で消える低次の多項式」を使って集合の大きさを抑える議論である。ここでは $\delta_0(x+y+z)$ という次数 $2n$ の多項式を、「$x,y,z$ の少なくとも 1 つについては低次」という形に分けられることが要である。cap set の条件は、この関数を $A^3$ に制限すると対角になることとして使われ、対角な関数を少ない項で表せないことは、1 つの変数を消して行列の階数に帰着させる lem-cap-diagonal で示される。
EG17 の元の形は、低次の多項式 $P$ で $P(a+b)=0$($a\ne b\in A$)となるものに対し、行列 $(P(a+b))_{a,b\in A}$ の階数を評価する議論(Proposition 2、p. 2)である。上の対称な形は Tao16 の Lemma 1・Lemma 2 による。
| 主張 | 外す仮定 | 例 | 何が成り立たなくなるか |
|---|---|---|---|
| thm-cap-main の上界 $3N_n$ | $A$ が cap set | $A=\mathbb{F}_3^4$ | $N_4=15$ で $3N_4=45$ だが $A$ は $81$ 点 |
| lem-cap-diagonal | 全ての $c_a$ が $0$ でない | $c_a=0$ となる $a$ がある | スライスランクは $c_a\ne0$ となる $a$ の個数に等しく、$A$ の元の個数より小さい |
| lem-cap-polynomial | 値を $\mathbb{F}_3$ でとる | 同じ $T$ を $A=\mathbb{F}_3^n$ 上の複素数値の関数とみる | スライスランクはちょうど $3^n$ で、$3N_n$ 以下にならない($n\ge4$) |
1 行目:$3^n>3N_n$ は $n\ge4$ で成り立つ($n\ge13$ では $3N_n\le3c^n< 3^n$ から、$4\le n\le12$ では計算で確かめた。$n\le3$ では成り立たない)。よって cap の条件なしでは上界が成り立たない。
2 行目:$c_a\ne0$ となる $a$ の集合を $A'$ とする。$T$ は $|A'|$ 個のスライス $\delta_a(x)\cdot c_a\delta_a(y)\delta_a(z)$($a\in A'$)の和である。逆に $T$ の分解を $A'^3$ に制限すると項の個数は増えず、制限は $A'$ 上の lem-cap-diagonal の形なので、項は $|A'|$ 個以上いる。
3 行目:$\omega=e^{2\pi i/3}$ とし、$\xi\cdot x:=\sum_i\xi_ix_i$($\xi_i,x_i\in\{0,1,2\}$ の整数としての積の和)とおくと、指標の直交性から
$$
T(x,y,z)=3^{-n}\sum_{\xi\in\mathbb{F}_3^n}\omega^{\xi\cdot x}\omega^{\xi\cdot y}\omega^{\xi\cdot z}
$$
である。$x$ の関数の空間で基底を $\{\omega^{\xi\cdot x}\}_\xi$ に取り替える可逆な線形変換を 3 つの変数それぞれに施すと、スライスはスライスに移り、$T$ は係数 $3^{-n}\ne0$ の対角な関数に移る。よって lem-cap-diagonal からスライスランクは $3^n$ である(Tao16 Remark 6)。$1-t^2$ が $t=0$ の指示関数になるのは $\mathbb{F}_3$ に値をとるからで、標数 $3$ が本質的に使われている。
$\mathbb{F}_3^n$ の cap set 問題は、整数の中の 3 項等差数列を含まない集合の問題(Roth の定理、Szemerédiの定理 の 3 項の場合)の有限体版として調べられてきた(EG17 p. 1)。ところが整数の区間 $\{1,\dots,N\}$ では、Behrend の構成(Szemerédiの定理 の定理「Behrendの構成」)により、3 項等差数列を含まない集合が任意の $\varepsilon>0$ について $N^{1-\varepsilon}$ より大きくとれる($N$ が十分大きいとき)ので、thm-cap-main のような $N^{\log_3c}$($\log_3c< 1$)の形の上界は成り立たない。指数的な節約は $\mathbb{F}_3^n$ に特有の現象である。
スライスランクの方法は、その後、3 つ組の和についての他の問題(例えば $\mathbb{F}_p^n$ の 3 項等差数列、EG17 Theorem 4)にも同じ形で使われる。$q$ が奇数の有限体 $\mathbb{F}_q$ では、3 項等差数列 $x,y,z$ の条件 $x-2y+z=0$ の指示関数 $\delta_0(x-2y+z)$ を $\prod_i(1-(x_i-2y_i+z_i)^{q-1})$ と書いて同じ議論を行う。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する