エルデシュ・トゥーランの定理

$N$ を正の整数とし、 $1 \leq a_1 < a_2 < \cdots < a_r \leq N$ を満たすような整数列 $\{a_n\}_{n=1}^r$ を考えましょう。 $\{a_n\}_{n=1}^r$ が等差数列をなすような三項を一切含まないとき、 $\{a_n\}_{n=1}^r$ は( $N$ に関する) $A$ -数列であるといいます。

定義 $A(N)$ を $N$ に関する $A$ -数列としてあり得る最大項数と定義する。

このとき、ErdősとTuránは次のような $A(N)$ の上からの評価を与えています。

定理１ $N \geq 4$ であれば、例外である $N=7$ を除いて $A(2N) \leq N$ が成立する。

証明の前に $A$ -数列に関する基本事項を三つ確認しておきましょう。

基本事項１ $1 \leq a_1 < a_2 < \cdots < a_r \leq N$ なる整数列 $\{a_n\}_{n=1}^r$ が $N$ に関する $A$ -数列であれば、

$N+1-a_r < N+1-a_{r-1} < \cdots < N+1-a_1$

の $r$ 個の整数からなる数列も $N$ に関する $A$ -数列である。

基本事項２ $1 \leq a_1 < a_2 < \cdots < a_r \leq N$ なる整数列 $\{a_n\}_{n=1}^r$ が $N$ に関する $A$ -数列であれば、 $k < a_1$ であるような任意の正整数 $k$ に対して

$a_1-k < a_2-k < \cdots < a_r-k$

の $r$ 個の整数からなる数列も $N$ に関する $A$ -数列である。

基本事項３ $n$ , $m$ を正の整数とする。このとき、

$A(n+m) \leq A(n)+A(m)$

が成り立つ。

基本事項３の証明. $1 \leq a_1 < a_2 < \cdots < a_r \leq m+n$ を満たすような $A$ -数列 $\{a_i\}_{i=1}^r$ を任意にとる。このとき、

$1 \leq a_1 < \cdots < a_s \leq m < a_{s+1} < \cdots < a_r \leq m+n$

を満たすような $s \leq r$ が一意的に存在する。このとき、 $\{a_i\}_{i=1}^s$ は $m$ に関する $A$ -数列なので、 $s \leq A(m)$ を満たす。また、基本事項２より

$a_{s+1}-m < a_{s+2} - m < \cdots < a_r-m \leq n$

から $n$ に関する $A$ -数列 $\{a_{s+i}-m\}_{i=1}^{r-s}$ が得られるので、 $r-s \leq A(n)$ である。以上によって

$r = s+(r-s) \leq A(m)+A(n)$

がわかった。最初にとった $A$ -数列は任意であったから $A(n+m) \leq A(n)+A(m)$ である。 Q.E.D.

定理１の証明

まずは $N$ が小さい場合に $A(2N)$ の値を順に決めていく。

$A(8)=4$

$A(8) \geq 5$ であると仮定する。項数 $5$ の $8$ に関する $A$ -数列が存在する。それは $1$ から $4$ または $5$ から $8$ のいずれかの数を三つ含む。必要ならば基本事項１を用いることによって $1$ から $4$ の数を三つ含むと仮定してよい*1。更に必要ならば基本事項２を用いることによって $1$ を含むとしてよい。 $1, 2, 3$ の三つは同時には含まないのだから、 $1, 2, 4$ または $1, 3, 4$ を含むことになる。例えば $1, 2, 4$ を含むとすると、 $7$ を含むことができないことはすぐにわかる( $1, 4, 7$ が等差数列となる)。このようにして全ての可能性(数通りしかない)を考えるとどの場合であっても等差数列を含んでしまって矛盾する。一方、 $1, 2, 4, 5$ は $A$ 数列なので $A(8)=4$ が確定する。

$A(10)=5$

$A(10) \geq 6$ であると仮定する。項数 $6$ の $10$ に関する $A$ -数列が存在する。 $A(8)=4$ であることを考慮すると、そのような数列は必ず $9, 10$ を含む。基本事項１を使えば $1, 2$ を含むようにできるが、それについても先ほどのことは成り立つ必要があるので、 $1, 2, 9, 10$ を含むとしてよい。この時点で $3, 5, 6, 8$ を含むことはできず、従って $1, 2, 4, 7, 9, 10$ という $A$ -数列であるということになるが、 $1, 4, 7$ は等差数列なので矛盾。一方 $1, 2, 4, 9, 10$ は $A$ -数列なので $A(10)=5$ が確定する。

$A(12)=6$

$A(12) \geq 7$ であると仮定する。項数 $7$ の $12$ に関する $A$ -数列が存在する。 $A(10)=5$ であることを考慮すると $11, 12$ を必ず含む必要があり、基本事項１を考えると $1, 2, 11, 12$ を含むとしてよい。 $A(8)=4$ を考慮すると、 $1, 2, 11, 12$ を含む場合は必ず $9$ も含む必要がある。すると基本事項１を使えば $1, 2, 4, 9, 11, 12$ を含むとしてよい。あと1つどの数を追加しようとも等差数列が作られ矛盾する。一方、 $1, 2, 4, 9, 11, 12$ は $A$ -数列なので $A(12)=6$ が確定する。

$A(14)=8$

$A(12)=6$ より、 $A(14) \leq 8$ 。一方、 $1, 2, 4, 5, 10, 11, 13, 14$ は $A$ -数列である。

$A(16)=8$

基本事項３を用いると、 $A(16) \leq A(8)+A(8) = 8$ 。一方、 $A(14)=8$ を実現する $A$ -数列は $16$ に関する $A$ -数列でもある。

確定させるのはここらへんまでにしておいて、基本事項３により

$\begin{align}&A(18)\leq A(8)+A(10)=9, \\ &A(20)\leq A(8)+A(12)=10, \\ &A(22) \leq A(10)+A(12)=11\end{align}$

がわかる。あとは $N \geq 12$ の場合に数学的帰納法で証明する。 $N-4$ で成立すると仮定すると、基本事項３により

$A(2N) \leq A(2N-8)+A(8) \leq N-4+4 = N$

と $N$ の場合も成立することがわかる。 Q.E.D.

実は $N$ が大きくなると $A(N)$ はもっと小さくなります。実際、Erdős-Turánは同じ論文で以下の定理２を証明しています。

定理２ 任意の $\varepsilon > 0$ に対して正整数 $N_{\varepsilon}$ が存在し、 $N \geq N_{\varepsilon}$ であれば

$\displaystyle A(N) < \left( \frac{4}{9}+\varepsilon \right) N$

が成り立つ。

準備となる命題の証明から始めましょう。

命題 $k \geq 3$ とする。このとき、

$A(2^k+2^{k-3}-1) \leq 2^{k-1}$

が成り立つ。

証明. $k$ に関する数学的帰納法で証明する。 $k=3$ のときは $A(8)=4$ より成立。 $k-1$ で成立すると仮定する。 $2^k+2^{k-3}-1$ に関する項数 $2^{k-1}+1$ の $A$ -数列 $\alpha$ が存在したと仮定する。帰納法の仮定と基本事項３より