日記

その他

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

Stickerbrush Symphony
ゲーデルの定理
Croot-Lev-Pachの定理
参考文献

Stickerbrush Symphony

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

www.youtube.com

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

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$ とする。このとき、或る球面 $S$ と $S$ 上の四点 $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_S$ は $S$ 上の大円距離。

証明. 三次元Euclid空間内の任意の四面体をとって $T$ とし、六つの辺の長さを $a_1, \dots, a_6$ とする。 $T$ の外接球の半径を $R$ とする*1。 $a:=\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$ を連続的に変形すれば $x$ が $0$ に近いときは常に存在することがわかる。もう少し詳しくいうと、四面体の存在条件は七つの連続関数 $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となる。

補題１ $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}$ 上一次独立でなければならない*6。 $u(a)$ 達が住んでいる空間 $\mathbb{F}^{2m}$ の次元は $2m$ なので $\#A \leq 2m$ ということになるが、これは仮定に矛盾する。 Q.E.D.

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

補題２ $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$ と同型である。

補題３ $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 R$ が $2r \in B \subset A+A$ を満たしたと仮定する。このとき、任意の $a =r+F_n=R$ に対して $2a=2r \in A+A$ となってしまい*8、 $a$ として $A$ の元を取ることができるので、 $A$ が等差数列自由であることに反する。よって、 $B\cap C=\varnothing$ が示された。また、 $2R$ は $R=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$ なので、補題２と $(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$ より、補題２から

$\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_n$ を $n$ 次元 $\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)$

であるから、補題１が適用できて $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}$ と変数変換する。このとき、 $x$ は $2^{nH(0.25)+1} \to 2^{n+1}$ なので $\varepsilon$ は $0.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$

となる。補題３は $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}$

あれ？欲しい不等式になってないじゃないか！と思われるそこのあなた。こここそがテンソル積トリックの使いどころですぞ*13。 $k \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の補題１を用いる技術革新を取り入れることによって、Ellenberg-Gijswijt ([EG])が任意の有限体 $\mathbb{F}_q$ の加法群に対して

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

を示すことに成功しています( $c_q$ は $q$ 未満の或る正定数)。特に、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_n$ は $R \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$ を返す関数を考えるとそれらが基底になっている。