インテジャーズ

INTEGERS

数、特に整数に関する記事。

日記

好きな音楽と勉強した数学について書きます。

Stickerbrush Symphony

David Wiseの楽曲が昔から好きで、Stickerbrush Symphonyは特に好きな曲の一つです(スーパードンキーコング2の「とげとげタルめいろ」で通じる人も多いと思います)。最近またよく聴くようになっていて、ほぼ原曲通りの演奏動画を見つけたのでここで紹介します。

www.youtube.com

あと、最近ドンキーコングトロピカルフリーズというゲーム作品の楽曲をWiseが提供していたことを知って興奮しています。まだ聴きこめてないですが、とりあえずいい感じの曲を四つほどあげておきます。

www.youtube.com

www.youtube.com

www.youtube.com

www.youtube.com

ゲーデルの定理

定理 ([G], 1933) 三次元Euclid空間内の四面体をなす四点は或る球面上に等長に埋め込める。球面上では大円距離を考える。

三次元Euclid空間内の四面体ABCDを考える。AB=a_1, AC=a_2, AD=a_3, BD=a_4, BC=a_5, CD=a_6とする。このとき、或る球面SS上の四点E, F, G, Hが存在してd_S(E,F)=a_1, d_S(E,G)=a_2, d_S(E,H)=a_3, d_S(F,H)=a_4, d_S(F,G)=a_5, d_S(G,H)=a_6が成り立つということ。ただし、d_SS上の大円距離。

証明. 三次元Euclid空間内の任意の四面体をとってTとし、六つの辺の長さをa_1, \dots, a_6とする。Tの外接球の半径をRとする*1a:=\max\{a_1, \dots, a_6\}として、0 < x \leq \pi/aおよび1 \leq i \leq 6に対して

\displaystyle a_{i,x}:=\frac{2}{x}\sin\frac{a_ix}{2}

とおく。初等幾何的計算によって、これは半径1/xの円の円周上の長さa_iの円弧の弦の長さに等しいことがわかる。従って、或るxが存在して、六つの辺の長さ(Euclid距離)がa_{1,x}, \dots, a_{6,x}であるような四面体であって外接球の半径が1/xであるようなものが存在すれば、その四面体の四頂点が所望の四点である。以下、実際にそのようなものが存在することを示す。

xに対して、六つの辺の長さ(Euclid距離)がa_{1,x}, \dots, a_{6,x}であるような四面体(ただし、ここでは同一平面上に潰れている四点を許す)が存在する場合、そのような四面体を一つとってT(x)と名付ける*2

どれぐらい存在するかであるが、\displaystyle \lim_{x \to 0}a_{i,x}=a_iおよびa_{i,x}が連続関数であることに注意すると、T(0):=Tを連続的に変形すればx0に近いときは常に存在することがわかる。もう少し詳しくいうと、四面体の存在条件は七つの連続関数 f_j(x), 1 \leq j \leq 7を用いて f_j(x) \geq 0と表すことができることからわかる(等号が一つでもあると平面上に潰れている)。

任意のx \in [0,y]に対してT(x)が存在するような0 < y \leq \pi/aの最大値を\bar{x}とする。\bar{x}の存在性について、実数の連続性からこのような最大値が存在するか、T(x)が存在しないようなx \in [0, y]が存在するようなyの最小値が存在するかのどちらかであるが、T(x)が存在しないということは或るjに対して f_j(x) < 0であるから後者にはなりえない。特に、\bar{x}=\pi/aであるか、\bar{x} < \pi/aかつT(\bar{x})が平面上にあるかのどちらかの状況になっている。

x\in[0,\bar{x}]に対して f(x)T(x)の半径の逆数と定義する。f(0)=1/Rであり、T(x)が平面上に潰れている場合は f(x):=0とすると f(x)は連続関数である。f(x)=xとなるようなxの存在性を示せばよい。

\bar{x}=\pi/aのときはT(\pi/a)が長さ2a/\piの辺を持つので、簡単にわかるように f(\pi/a) < \pi/aが成り立つ。一方、f(0) > 0なので、中間値の定理より f(x)=xなるx \in (0,\pi/a)が存在する。

\bar{x} < \pi/aかつT(\bar{x})が平面上にある場合は 0=f(\bar{x}) < \bar{x}なので、やはり f(0) > 0と合わせて中間値の定理より f(x)=xなるx \in (0,\pi/a)が存在する。よって、証明が完了した。 Q.E.D.

Croot-Lev-Pachの定理

Gを有限アーベル群とする(演算は+で表す)。部分集合A \subset Gが等差数列自由であるとは、どの二つも相異なるような任意のa,b,c \in Aに対してa+b\neq 2cが成り立つときにいう。r_3(G)を等差数列自由な部分集合のサイズの最大値と定義する。n \to \inftyを考えるとき、r_3(\mathbb{Z}/n\mathbb{Z})=o(n)がRothの定理であった*3。Rothは実際には

\displaystyle r_3(\mathbb{Z}/n\mathbb{Z})=O\left(\frac{n}{\log\log n}\right)

を示したが、現在では改良されておりBloomが2016年に

\displaystyle r_3(\mathbb{Z}/n\mathbb{Z})=O\left(\frac{n(\log\log n)^4}{\log n}\right)

を示している。さて、他の群の無限族に関する研究もあって、Sandersが2011年にAnn. of Math.の論文で或る\varepsilon > 0が存在して

\displaystyle r_3( (\mathbb{Z}/4\mathbb{Z})^n)=O\left(\frac{4^n}{n(\log n)^{\varepsilon}}\right)

が成り立つことを示していたが、Croot-Lev-Pachが最近次のように改良した:

定理 ([CLP], 2017) n \geq 1のとき、r_3( (\mathbb{Z}/4\mathbb{Z})^n)\leq 4^{\gamma n} が成り立つ。

ただし、H(x)を二値エントロピー関数

\displaystyle H(x) := -x\log_2x-(1-x)\log_2(1-x), \quad (0 < x < 1)

とするとき*4\gamma

\displaystyle \gamma := \max\left\{\left.\frac{H(0.5-\varepsilon)+H(2\varepsilon)}{2} \ \right| \ 0 < \varepsilon < 0.25\right\} ≒ 0.926

と定義される*5。以下、この定理の証明を解説する。次の多項式に関する補題がKeyとなる。

補題1 n \geq 1, d \geq 0を整数とし、\mathbb{F}を体とする。Pは多重線形な\mathbb{F}係数n変数で総次数がd以下の多項式であり、\mathbb{F}^nの部分集合A
\displaystyle \#A > 2\sum_{0 \leq i \leq d/2}\binom{n}{i}
を満たしているとする。このとき、Pが任意のa, b \in A(ただし、a \neq b)に対してP(a-b)=0を満たしているならばP(0)=0が成り立つ。

証明. m:=\sum_{0\leq i \leq d/2}\binom{n}{i}, \mathcal{K}:=\{K \subset [n] \mid \#K \leq d/2\} = \{K_1, \dots, K_m\}と記号を導入する([n]:=\{1,2,\dots, n\})。また、I \subset [n]x=(x_1, \dots, x_m) \in \mathbb{F}^nに対してx^I:=\prod_{i \in I}x_iと略記する。このとき、Pの定義からI, J \subset [n]に対して或るc_{I,J} \in \mathbb{F}が存在して、任意のx, y \in \mathbb{F}^nに対して

\displaystyle P(x-y)=\sum_{I,J\subset [n], I\cap J = \varnothing, \#I+\#J\leq d}c_{I,J}x^Iy^J

と書ける。これを\sum_I\sum_Jという順番の和に変形してI \in \mathcal{K}およびI \in [n]\setminus \mathcal{K}の二つの和に分け、後者については\sum_J\sum_Iの順番に入れ替えることによって

\displaystyle P(x-y) = \sum_{I\in\mathcal{K}}x^I\sum_{J\subset [n]\setminus I, \#J\leq d-\#I}c_{I,J}y^J+\sum_{J\in\mathcal{K}}\left(\sum_{I\subset [n]\setminus J, d/2 < \#I\leq d-\#J}c_{I,J}x^I\right)y^J

と書き直せる。よって、u(x)=(u_1(x),\dots, u_m(x) ), v(y)=(v_1(y), \dots, v_m(y) ) \in \mathbb{F}^{2m}

\displaystyle u_i(x)=x^{K_i},\quad u_{m+i}(x)=\sum_{I\subset [n]\setminus K_i, d/2 < \#I\leq d-\#K_i}c_{I,K_i}x^I

\displaystyle v_i(y)=\sum_{J\subset [n]\setminus K_i, \#J\leq d-\#K_i}c_{K_i,J}y^J,\quad  v_{m+i}(y)=y^{K_i}

によって定めると(1 \leq i \leq m)、上の表示は

P(x-y)=u(x)\cdot v(y)

という内積表示になっていることがわかる。さて、Pが任意のa, b \in A(ただし、a \neq b)に対してP(a-b)=0を満たしているにも関わらずP(0) \neq 0であったと仮定しよう。これは

u(a) \perp v(b) \Longleftrightarrow a \neq b \quad (a, b \in A)

を意味する。このことから\{u(a)\}_{a \in A}\mathbb{F}上一次独立でなければならない*6u(a)達が住んでいる空間\mathbb{F}^{2m}の次元は2mなので\#A \leq 2mということになるが、これは仮定に矛盾する。 Q.E.D.

次の補題は二値エントロピー関数に関する有名な不等式(と言っても確率方面を勉強していない私は今回初めて知った)とのことですが、検索しても確率論的に証明している文献が多く出てきます。が、次のように初等的にも示せます。

補題2 n \geq 1, 0 < z \leq n/2であるとき、不等式
\displaystyle \sum_{0 \leq i\leq z}\binom{n}{i} < 2^{nH(z/n)}
が成り立つ。

なお、左辺の和に綺麗に閉じた公式はないです。

証明. x:=z/n \leq 1/2とおく。

\displaystyle 1=(x+(1-x) )^n > \sum_{0 \leq i \leq z}\binom{n}{i}x^i(1-x)^{n-i}=\sum_{0 \leq i \leq z}\binom{n}{i}(1-x)^n\left(\frac{x}{1-x}\right)^i.

ここで、0\leq x \leq 1/2なので、0 \leq \frac{x}{1-x} \leq 1である。従って、

\displaystyle \left(\frac{x}{1-x}\right)^i \geq \left(\frac{x}{1-x}\right)^z

であり、

\displaystyle 1 > \sum_{0 \leq i \leq z}\binom{n}{i}{x}^z(1-x)^{n-z} = \sum_{0 \leq i \leq z}\binom{n}{i}2^{-nH(x)}

が得られ、これが所望の不等式である。 Q.E.D.

二倍写像(\mathbb{Z}/4\mathbb{Z})^n \to (\mathbb{Z}/4\mathbb{Z})^n, g\mapsto 2gのKernelをF_nとする。F_nは自然に(\mathbb{Z}/2\mathbb{Z})^nと同型である。

補題3 n \geq 1とし、A \subset (\mathbb{Z}/4\mathbb{Z})^nは等差数列自由な部分集合とする。0 < \varepsilon < 0.25を任意にとるとき、少なくとも2^{nH(0.5-\varepsilon)+1}個のAの元を含むようなF_n-cosetの数は2^{nH(2\varepsilon)}未満である。

証明. \varepsilonを固定して、少なくとも2^{nH(0.5-\varepsilon)+1}個のAの元を含むようなF_n-coset全体のなす集合を\mathcal{R}とする。R \in \mathcal{R}に対してA_R:=A\cap Rとすると、定義より

\#A_R \geq 2^{nH(0.5-\varepsilon)+1} \tag{1}

が成り立つ。(\mathbb{Z}/4\mathbb{Z})^nの部分集合Sに対して

S+S:=\{s_1+s_2 \mid (s_1, s_2) \in S\times S, s_1 \neq s_2\}, \quad 2S:=\{2s \mid S\}

S+Sおよび2Sを導入する。以上の記号設定を用いて、B, C \subset F_n

\displaystyle B:=\bigcup_{R \in \mathcal{R}}(A_R+A_R),\quad C:=\bigcup_{R\in \mathcal{R}}(2R)

と定義する。これらがF_nの部分集合であることはR+R, 2R \subset F_nであることからわかる*7。このとき、B \cap C=\varnothingかつ\#C=\#\mathcal{R}が成り立っている。理由: r \in R2r \in B \subset A+Aを満たしたと仮定する。このとき、任意のa =r+F_n=Rに対して2a=2r \in A+Aとなってしまい*8aとしてAの元を取ることができるので、Aが等差数列自由であることに反する。よって、B\cap C=\varnothingが示された。また、2RR=r+F_nと代表元をとると2R=\{2r\}と一点集合になっていることがわかる。そうして、2r_1=2r_2 \Leftrightarrow r_1-r_2 \in F_n \Leftrightarrow r_1+F_n=r_2+F_nであることからC\mathcal{R}の間に全単射があることがわかった

d:=n-\lceil 2\varepsilon n\rceilとおく。このとき、0 < z:=d/2 \leq n/2, z/n \leq 0.5-\varepsilonなので、補題2と(1)より

\displaystyle 2\sum_{0 \leq i\leq d/2}\binom{n}{i} < 2^{nH(0.5-\varepsilon)+1} \leq \#A_R \quad ({}^{\forall}R \in \mathcal{R}) \tag{2}

が成り立つ。ここで、\overline{C}:=F_n\setminus Cとおく。以下、\#\mathcal{R} \geq 2^{nH(2\varepsilon)}と仮定して矛盾を導けばよい。

\displaystyle 2^n=\sum_{i=0}^n\binom{n}{i} = \sum_{i=0}^d\binom{n}{i}+\sum_{i=d+1}^n\binom{n}{i}, \quad \sum_{i=d+1}^n\binom{n}{i}=\sum_{i=d+1}^n\binom{n}{n-i}=\sum_{i=0}^{\lceil 2\varepsilon n\rceil -1}\binom{n}{i}

なので、0 < z':=\lceil 2\varepsilon n\rceil -1 < n/2, z' \leq 2\varepsilonより、補題2から

\displaystyle \sum_{i=0}^d\binom{n}{i}=2^n-\sum_{i=0}^{\lceil 2\varepsilon n\rceil -1}\binom{n}{i} > 2^n-2^{nH(2\varepsilon)}\geq 2^n-\#\mathcal{R}=2^n-\#C=\#\overline{C} \tag{3}

が得られる。

多重線形な\mathbb{F}_2係数n変数で総次数がd以下の多項式全体のなす\mathbb{F}_2ベクトル空間をVとする。また、F_nn次元\mathbb{F}_2ベクトル空間\mathbb{F}_2^nの加法群と同一視する。この同一視のもと、定義域が\overline{C}である\mathbb{F}_2値関数全体のなす\mathbb{F}_2ベクトル空間\mathrm{Map}(\overline{C}, \mathbb{F}_2)を考える。すると、(3)

\displaystyle \dim_{\mathbb{F}_2}V > \dim_{\mathbb{F}_2}\mathrm{Map}(\overline{C}, \mathbb{F}_2)

を言っている*9。従って、多項式を代入によって関数化した関数に対応させる写像

\displaystyle e\colon V \longrightarrow\mathrm{Map}(\overline{C}, \mathbb{F}_2)

のKernelは潰れていない。すなわち、0でない多項式P \in Vが存在して、Pは任意の\overline{C}の元で消えているようなものが存在する(e(P)=0)。ところで、多重線形な\mathbb{F}_2係数n変数の多項式全体のなす\mathbb{F}_2ベクトル空間を\overline{V}とするとき、e

\displaystyle \overline{e}\colon \overline{V} \longrightarrow\mathrm{Map}(\mathbb{F}_2^n, \mathbb{F}_2)

から自然に誘導されるが*10\overline{e}は同型(ともに次元が2^n)なので\overline{e}(P) \neq 0のはずである。

R \in \mathcal{R}, r \in Rを任意にとって固定する。Q(x):=P(2r+x)とおくとQ \in Vである。任意のx \in (A_R-r)+(A_R-r)に対してQ(x)=0が成り立つ。理由: 2r+x \in A_R+A_R \subset B \subset \overline{C}e(P)=0であるから これはQが任意のa, b \in A_R-r(ただし、a \neq b)に対してQ(a-b)=0を満たしているということだ*11(2)より

\displaystyle 2\sum_{0 \leq i\leq d/2}\binom{n}{i} < \#(A_R-r)

であるから、補題1が適用できてQ(0)=0が従う。つまり、P(2r)=0であるが、rおよびRが任意であったことからPは任意のCの元で消えていることになる。\mathbb{F}_2^n = C\cup \overline{C}でありe(P)=0であったので、これは\overline{e}(P)=0を意味し矛盾に到達した。 Q.E.D.

定理の証明. Aを等差数列自由な(\mathbb{Z}/4\mathbb{Z})^nの部分集合とする。x \geq 0に対して、N(x)を少なくともx個のAの元を含むようなF_n-cosetの数とする。すると、

\displaystyle \#A=\sum_{k=0}^{\infty}N(k) = \int_0^{\infty}N(x)\mathrm{d}x

とカウンティングできる。x > 2^nのときはN(x) = 0であるが(各F_n-cosetのサイズは2^n)、後のために

\displaystyle \#A=\int_0^{2^{n+1}}N(x)\mathrm{d}x \tag{4}

という表示を与えておく。この積分を二つにわけて評価する。N(x) \leq 2^nなので(F_n-cosetは全部で2^n個)、

\displaystyle \int_0^{2^{nH(0.25)+1}}N(x) \mathrm{d}x \leq 2^{(H(0.25)+1)n+1} < 2\cdot 4^{\gamma n} \tag{5}

と評価しておく*12。残りの部分について、x=2^{n(H(0.5-\varepsilon)+1}と変数変換する。このとき、x2^{nH(0.25)+1} \to 2^{n+1}なので\varepsilon0.25 \to 0であり、

\displaystyle \frac{\mathrm{d}x}{\mathrm{d}\varepsilon} = 2^{nH(0.25-\varepsilon)+1}\times \log 2 \times \frac{\mathrm{d}}{\mathrm{d}\varepsilon}\left(nH(0.5-\varepsilon)+1\right).

ここで、\frac{\mathrm{d}}{\mathrm{d}x}H(x) = -\log_2\left(\frac{x}{1-x}\right)なので

\displaystyle \frac{\mathrm{d}x}{\mathrm{d}\varepsilon} = n2^{nH(0.25-\varepsilon)+1}\log\frac{0.5-\varepsilon}{0.5+\varepsilon}

が得られ、変数変換の結果は

\displaystyle \int_{2^{nH(0.25)+1}}^{2^{n+1}}N(x)\mathrm{d}x = n\int_0^{0.25}2^{nH(0.5-\varepsilon)+1}N(2^{nH(0.5-\varepsilon)+1})\log\frac{0.5+\varepsilon}{0.5-\varepsilon}\mathrm{d}\varepsilon

となる。補題3はN(2^{nH(0.5-\varepsilon)+1}) < 2^{nH(2\varepsilon)}を示しているため

\displaystyle n\int_0^{0.25}2^{nH(0.5-\varepsilon)+1}N(2^{nH(0.5-\varepsilon)+1})\log\frac{0.5+\varepsilon}{0.5-\varepsilon}\mathrm{d}\varepsilon < 2n\int_0^{0.25}2^{n\left(H(0.5-\varepsilon)+H(2\varepsilon)\right)}\log\frac{0.5+\varepsilon}{0.5-\varepsilon}\mathrm{d}\varepsilon

と評価でき、0 \leq \varepsilon \leq 0.25\log\frac{0.5+\varepsilon}{0.5-\varepsilon} \leq \log 3なので

\displaystyle 2n\int_0^{0.25}2^{n\left(H(0.5-\varepsilon)+H(2\varepsilon)\right)}\log\frac{0.5+\varepsilon}{0.5-\varepsilon}\mathrm{d}\varepsilon < (2\log 3)n\int_0^{0.25}2^{n\left(H(0.5-\varepsilon)+H(2\varepsilon)\right)}\mathrm{d}\varepsilon

を得る。そうして、(2\log 3)/4 < 1であることと\gammaの定義から

\displaystyle  \int_{2^{nH(0.25)+1}}^{2^{n+1}}N(x)\mathrm{d}x < n4^{\gamma n}

が得られたことになる。(4)(5)を合わせると

\#A < (n+2)4^{\gamma n} \tag{6}

あれ?欲しい不等式になってないじゃないか!と思われるそこのあなた。こここそがテンソル積トリックの使いどころですぞ*13k \geq 1を任意にとるとき、A\times \cdots \times A \subset (\mathbb{Z}/4\mathbb{Z})^{kn}Aの性質より等差数列自由な部分集合になっている。よって、knに対する(6)から

\displaystyle (\#A)^k < (kn+2)4^{\gamma kn}

が成り立ち、すなわち

\displaystyle \#A < \sqrt[k]{kn+2}\cdot 4^{\gamma n}

がいえた。\displaystyle \lim_{k \to \infty}\sqrt[k]{kn+2} = 1であるから、\#A \leq 4^{\gamma n}でなければならない。 Q.E.D.

Croot-Lev-Pachの補題1を用いる技術革新を取り入れることによって、Ellenberg-Gijswijt ([EG])が任意の有限体\mathbb{F}_qの加法群に対して

r_3( (\mathbb{F}_q)^n) = O(c_q^n)

を示すことに成功しています(c_qq未満の或る正定数)。特に、Bateman-Katzの2012年の記録: 或る\varepsilon > 0が存在して

\displaystyle r_3( (\mathbb{Z}/3\mathbb{Z})^n)=O\left(\frac{3^n}{n^{1+\varepsilon}}\right)

を塗り替えて

r_3( (\mathbb{Z}/3\mathbb{Z})^n)=o(2.756^n)

を与えています。

参考文献

[G] K. Gödel, On the isometric embeddability of quadruples of points of R_3 in the surface of a sphere, In S. Feferman, J. Dawson, S. Kleene, G. Moore, R. Solovay, and J. van Heijenoort, editors, Kurt Gödel: Collected Works, vol. I, pages (1933b) 276–279. Oxford University Press, Oxford, 1986.

[CLP] E. Croot, V. F. Lev, P. P. Pach, Progression-free sets in \mathbb{Z}_4^n are exponentially small, Ann. of Math., Vol. 185, Issue 1 (2017), 331–337.

[EG] J. S. Ellenberg, D. Gijswijt, On large subsets of \mathbb{F}_q^n with no three-term arithmetic progression, Ann. of Math., Vol. 185, Issue 1 (2017), 339–343.

*1:四面体の外接球の存在証明が2011年の京都大学の入試問題として出題されています。四面体の外接球の半径についてという日本語の論文を発見しました。

*2:T(x)の位置は重要ではないが、選択公理で選んで固定する。

*3:ロスによるエルデシュ・トゥーラン予想の解決 - INTEGERS この記事で紹介しているErdős-Turán予想。ここでの定式化との同値性は簡単にわかる。

*4:H(x)のグラフをdesmosで書くと次のようになります。f:id:integers:20190203150029p:plain:w200

*5:\gammaの定義に現れる関数をdesmosで書くと次のようなグラフになります。 f:id:integers:20190202181328p:plain:w200

*6:\sum_{a \in A}\lambda_au(a)=0のとき、任意のb \in Aをとって両辺を内積の意味でv(b)倍すると\lambda_b=0となる。

*7:2R \subset F_nは自明で、R+R \subset F_nR \in \mathcal{R}F_n-cosetであることとF_nが群であることからわかる。

*8:2a=r2にはF_nの定義を用いていることに注意。

*9:\dim_{\mathbb{F}_2}V=\sum_{i=0}^d\binom{n}{i}は自明であろう。\dim_{\mathbb{F}_2}\mathrm{Map}(\overline{C}, \mathbb{F}_2)=\overline{C}\overline{C}の元毎にその元で1, 他の元で0を返す関数を考えるとそれらが基底になっている。

*10:\overline{V}からVに制限した後、\mathrm{Map}(\mathbb{F}_2^n, \mathbb{F}_2) \to \mathrm{Map}(\overline{C}, \mathbb{F}_2)と合成する。

*11:A_R \subset R=r+F_nよりA_R-r \subset F_nなので、a, b \in A_R-rに対してa+b=a-bであることに注意。

*12:\frac{1}{2}(H(0.25)+1) \leq \gamma.

*13:Weil予想の証明でDeligneが使ったアレ。 tsujimotter.hatenablog.com