Erdősの食い違い問題(Erdős discrepancy problem)とは、$\pm1$ の値をとる無限列 $f$ について、斉次な算術級数に沿った和 $\sum_{j=1}^nf(jd)$ の絶対値が $n,d$ を動かすと上に有界でないか、という問題である。Tao が 2016 年に、どの列でも有界でないことを証明して解決した。有界性の問題は有限の列の問題に言い換えられ、和を $1$ 以下に抑えられる列の長さは $11$ までである。完全乗法的な列では食い違いは部分和の上限に等しく、3 進展開の数字 $1$ の個数で和が増える例は増え方が対数的である。
前提知識: 完全乗法的関数, Dirichlet指標, Kőnigの補題
Erdős の食い違い問題(Erdős discrepancy problem)とは、$+1$ と $-1$ だけからなる無限列 $f(1),f(2),\dots$ について、斉次な算術級数 $d,2d,\dots,nd$ に沿った和 $\sum_{j=1}^nf(jd)$ がいくらでも大きな絶対値をとるか、という問題である。1930 年代に P. Erdős が問い(KL14 p. 1)、肯定的な答えが予想されていた。T. Tao が 2016 年に肯定的に解決し(Tao16 Corollary 1.2)、題に「問題」とあるが内容は定理になった。
$+1$ と $-1$ を交互に並べれば、$d=1$ の和は $0$ と $1$ にとどまる。しかしそのとき $d=2$ の和は $-1,-2,-3,\dots$ と減り続ける。どの $d$ についても和を小さく抑えるように符号を選ぶことはできない、というのが定理の内容である。
この記事では、主張と、有限の列への言い換え、和を $1$ 以下に抑えられる列の長さが $11$ までであることの証明、完全乗法的な列への帰着と和がゆっくり増える例、Tao の証明の筋を述べる。
$\mathbb Z_{>0}=\{1,2,3,\dots\}$ とする。
$f\colon\mathbb Z_{>0}\to\{-1,+1\}$ の 食い違い(discrepancy)を
$$
\operatorname{disc}(f):=\sup_{n,d\ge1}\Bigl\lvert\sum_{j=1}^nf(jd)\Bigr\rvert\in\{1,2,\dots\}\cup\{\infty\}
$$
と定める。有限の列 $f\colon\{1,\dots,N\}\to\{-1,+1\}$ についても、$nd\le N$ となる $n,d$ にわたる最大値として $\operatorname{disc}(f)$ を定める。
$n=d=1$ の項から、食い違いはつねに $1$ 以上である。
$f\colon\mathbb Z_{>0}\to\{-1,+1\}$ ならば $\operatorname{disc}(f)=\infty$ である。より一般に、$H$ を実または複素の Hilbert 空間とし、$f\colon\mathbb Z_{>0}\to H$ がすべての $n$ で $\|f(n)\|=1$ を満たすなら、$\sup_{n,d}\bigl\|\sum_{j=1}^nf(jd)\bigr\|=\infty$ である(Tao16 Theorem 1.1、Corollary 1.2、p. 2)。
この記事ではこの定理を証明しない。証明の筋は後の節で述べる。和をとる級数が $0$ から始まる斉次なものに限られていることに注意する。$a+d,a+2d,\dots$ のような一般の算術級数を許すと、問題はずっとやさしくなる。$+1$ と $-1$ の 2 色の塗り分けに van der Waerdenの定理 を当てると、どの $k$ についても同じ符号が並ぶ $k$ 項の等差数列があり、その上の和は $\pm k$ になるからである。
正の整数 $C$ について、次の 2 条件は同値である。
1 から 2 は、無限列を $\{1,\dots,N\}$ に制限すればよい。制限した列の和は元の列の和の一部だからである。
2 から 1 を示す。長さ $N$ の列で食い違いが $C$ 以下のもの全体を $\mathcal T_N$ とし、$\mathcal T=\bigcup_N\mathcal T_N$ に「始めの部分」の順序を入れて根つき木とみる(根は長さ $0$ の列)。$\mathcal T_{N+1}$ の列の始めの $N$ 項は $\mathcal T_N$ に属する(和の一部だから)ので、$\mathcal T$ は始めの部分をとる操作で閉じた木であり、各頂点の子は高々 2 個である。仮定から各段 $\mathcal T_N$ は空でないので $\mathcal T$ は無限である。Kőnigの補題 により、$\mathcal T$ には無限に続く枝がある。枝に沿った列を合わせて無限列 $f$ を作る。$\sum_{j=1}^nf(jd)$ は始めの $nd$ 項だけで決まり、始めの $nd$ 項は $\mathcal T_{nd}$ の元なので、その絶対値は $C$ 以下である。よって $\operatorname{disc}(f)\le C$ である。$\square$
したがって thm-edp-main は「各 $C$ について、十分長い列の食い違いは $C$ を超える」と同値である。$C$ ごとの最小の長さを求める問題は有限の問題であり、$C=1$ の場合は手で解ける。
長さ $N$ の列 $f\colon\{1,\dots,N\}\to\{-1,+1\}$ で $\operatorname{disc}(f)\le1$ となるものがあるのは、$N\le11$ のときに限る。$N=11$ のとき、そのような列は
$$
f(1),\dots,f(11)=\varepsilon(+,-,-,+,-,+,+,-,-,+,\ \pm)\qquad(\varepsilon=\pm1)
$$
の 4 個である(最後の符号は $\varepsilon$ と独立に選べる)。
偶数個の和は $0$。 $\operatorname{disc}(f)\le1$ とする。$d$ と $k$ を $2kd\le N$ となるようにとる。$\sum_{j=1}^{2k}f(jd)$ は $\pm1$ を偶数個足したものなので偶数であり、絶対値が $1$ 以下だから $0$ である。$k-1$ の場合との差をとると
$$
f\bigl((2k-1)d\bigr)+f(2kd)=0,\qquad\text{すなわち}\qquad f(2kd)=-f\bigl((2k-1)d\bigr)
$$
を得る。この条件を $(\ast)$ と呼ぶ。逆に、すべての $2kd\le N$ で $(\ast)$ が成り立てば、各 $d$ について偶数個の和は $0$、奇数個の和は直前の偶数個の和に $\pm1$ を足したものなので $\pm1$ であり、$\operatorname{disc}(f)\le1$ である。よって $\operatorname{disc}(f)\le1$ は「$2kd\le N$ のすべてで $(\ast)$」と同値である。
$N=12$ は不可能。 $N\ge12$ とし、$a:=f(1)$ とおく。$(\ast)$ を次の順に当てはめる(括弧内は $(d,k)$)。
$$
\begin{aligned}
&f(2)=-a\ (1,1),\quad f(4)=-f(2)=a\ (2,1),\quad f(3)=-f(4)=-a\ (1,2),\\
&f(6)=-f(3)=a\ (3,1),\quad f(5)=-f(6)=-a\ (1,3),\quad f(8)=-f(4)=-a\ (4,1),\\
&f(7)=-f(8)=a\ (1,4),\quad f(10)=-f(5)=a\ (5,1),\quad f(9)=-f(10)=-a\ (1,5).
\end{aligned}
$$
ここで $(3,2)$ から $f(12)=-f(9)=a$、$(6,1)$ から $f(12)=-f(6)=-a$ となり、$a\ne0$ に矛盾する。
$N=11$ の列。 $2kd\le11$ となる $(d,k)$ は $(1,1),\dots,(1,5)$、$(2,1),(2,2)$、$(3,1)$、$(4,1)$、$(5,1)$ である。上の計算は $(2,2)$ 以外のすべてを使って $f(1),\dots,f(10)$ を $a$ で決めており、$(2,2)$ の条件 $f(8)=-f(6)$ も $-a=-a$ で成り立つ。$f(11)$ はどの条件にも現れない。よって条件を満たす列はちょうど主張の 4 個であり、$N\le11$ の場合はその始めの部分をとればよい。$\square$
この結果と prop-edp-finite から、食い違いが $1$ の無限列は存在しない。$C=2$ については、B. Konev と A. Lisitsa が問題を充足可能性問題(SAT)に書き直して計算機で解き、食い違いが $2$ 以下の列の最大の長さが $1160$ であることを示した(KL14 Proposition 3、Theorem 1、p. 5)。$1161$ の長さで解がないことの証明は、計算機が出力した反駁の証明書(約 13 GB)を別のプログラムで検証したものである(KL14 p. 5)。
完全乗法的関数 $g$($g(mn)=g(m)g(n)$ がすべての $m,n$ で成り立つ)では、斉次な算術級数に沿った和が簡単になる。
$g\colon\mathbb Z_{>0}\to\{-1,+1\}$ が完全乗法的なら $\sum_{j=1}^ng(jd)=g(d)\sum_{j=1}^ng(j)$ であり、
$$
\operatorname{disc}(g)=\sup_{n\ge1}\Bigl\lvert\sum_{j=1}^ng(j)\Bigr\rvert
$$
である。長さ $N$ の範囲に制限した食い違いも、右辺の上限を $n\le N$ に制限したものに等しい。
$g(jd)=g(j)g(d)$ を $j=1,\dots,n$ で足せば第 1 式を得る。$\lvert g(d)\rvert=1$ なので $\bigl\lvert\sum_{j\le n}g(jd)\bigr\rvert=\bigl\lvert\sum_{j\le n}g(j)\bigr\rvert$ である。$nd\le N$ なら $n\le N$ であり、逆に $d=1$ で $n\le N$ はすべて現れる。$\square$
Erdős 自身がこの場合を重要な試金石とみていた(Tao16 p. 4)。Liouville関数 $\lambda$ は完全乗法的で $\pm1$ の値をとり、その部分和が $o(n)$ であることは 素数定理 と同値である。食い違いを小さく抑える候補として自然なのは、Dirichlet指標 に近い関数である。
$\chi$ を法 $q$ の主でない Dirichlet 指標とする。$\chi$ は完全乗法的で、長さ $q$ の連続する整数の上の和は $0$ である。よって $\sum_{j\le n}\chi(j)$ は $n$ を $q$ で割った余りの部分の和に等しく、絶対値は $q$ 以下である。prop-edp-multiplicative と同じ計算から、すべての $n,d$ で $\bigl\lvert\sum_{j\le n}\chi(jd)\bigr\rvert\le q$ となる(Tao16 Example 1.3、p. 2)。たとえば法 $3$ の指標 $\chi_3$($n\equiv1$ で $1$、$n\equiv2$ で $-1$、$n\equiv0$ で $0$)では部分和は $1,0,0,1,0,0,\dots$ で、すべての $n,d$ について絶対値は $1$ 以下である。これは thm-edp-main に反しない。$\chi(n)=0$ となる $n$ があり、値が $\pm1$ だけという仮定を満たさないからである。
指標の $0$ を $\pm1$ で埋めると、食い違いは有限でなくなるが、増え方はきわめて遅い。
$\tilde\chi_3$ を、$\tilde\chi_3(3)=1$、$3$ 以外の素数 $p$ で $\tilde\chi_3(p)=\chi_3(p)$ とする完全乗法的関数とする。このとき、すべての $n\ge1$ について
$$
\sum_{j=1}^n\tilde\chi_3(j)=\bigl(n\text{ の 3 進展開に現れる数字 }1\text{ の個数}\bigr)
$$
である。したがって長さ $N$ に制限した $\tilde\chi_3$ の食い違いは、$\frac{3^k-1}2\le N$ となる最大の整数 $k$ に等しく、$\log_3N+1$ 以下である(Tao16 Example 1.4、pp. 2–3)。
$j$ を $j=3^im$($i\ge0$、$3\nmid m$)と書くと、完全乗法性から $\tilde\chi_3(j)=\tilde\chi_3(3)^i\tilde\chi_3(m)=\chi_3(m)$ である($m$ の素因数はどれも $3$ でなく、$\chi_3$ も完全乗法的なので $\tilde\chi_3(m)=\chi_3(m)$)。$\chi_3(m)=0$ となる $m$ は $3$ の倍数なので、$3\nmid m$ の条件を外しても和は変わらない。よって
$$
\sum_{j=1}^n\tilde\chi_3(j)=\sum_{i\ge0}\ \sum_{m\le n/3^i}\chi_3(m)=\sum_{i\ge0}T\bigl(\lfloor n/3^i\rfloor\bigr),\qquad T(x):=\sum_{m\le x}\chi_3(m)
$$
である。$T(x)$ は $x\equiv1\pmod3$ のとき $1$、それ以外は $0$ である(ex-edp-character の部分和)。$n=\sum_ic_i3^i$($c_i\in\{0,1,2\}$)と 3 進展開すると $\lfloor n/3^i\rfloor\equiv c_i\pmod3$ なので、$T(\lfloor n/3^i\rfloor)$ は $c_i=1$ のとき $1$、それ以外は $0$ である。和は数字 $1$ の個数になる。
食い違いについては、prop-edp-multiplicative から $n\le N$ での数字 $1$ の個数の最大値を求めればよい。数字 $1$ を $k$ 個もつ最小の数は $11\cdots1_{(3)}=\frac{3^k-1}{2}$ である(数字 $1$ を $k$ 個含む数は $3$ 進で $k$ 桁以上あり、$k$ 桁なら各桁が $1$ 以上だから)。$\frac{3^k-1}2\le N$ なら $3^{k-1}\le N$、すなわち $k\le\log_3N+1$ である。$\square$
計算機による探索では、長さ $N$ の範囲で完全乗法的な列の制限になっていて食い違いが $3$ 以下のものは、$N=127\,645$ まであり、それより長いものはない(Konev–Lisitsa の 2015 年の論文などの計算。Tao16 Example 1.7、p. 4 の紹介による)。ランダムな符号の列の食い違いは長さ $N$ に対して $N^{1/2+o(1)}$ 程度で増える(KL14 p. 2)ので、prop-edp-base3 の対数的な増え方はきわめて遅い。
thm-edp-main の証明は 3 つの段階からなる(Tao16 pp. 1, 4–6)。どれもこの記事では証明しない。
各行は、thm-edp-main の仮定を 1 つだけ変えた例である。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 値がすべての $n$ で $\pm1$ であること($0$ を許す) | 法 $3$ の指標 $\chi_3$ | すべての $n,d$ で和の絶対値が $1$ 以下で、食い違いは有限 |
| 列が無限であること | thm-edp-c1 の長さ $11$ の列 | 食い違いは $1$ |
| 公差 $d$ をすべて動かすこと($d=1$ だけにする) | $f(n)=(-1)^{n+1}$ | $d=1$ の和は $0$ と $1$ だけで有界($d=2$ を許すと和は $-n$) |
| Hilbert 空間版でノルムが $1$ であること($\le1$ に緩める) | $H=\mathbb R$、$f=\chi_3$ | $\lvert f(n)\rvert\le1$ だが和は有界 |
1 行目と 4 行目は同じ例を別の仮定から見たものである。どちらも、定理が「値が $0$ になる点を許さない」ことに依っていることを示す。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する