Erdősの食い違い問題

同義語:Erdős discrepancy problemErdős discrepancy conjecture

概要

Erdősの食い違い問題(Erdős discrepancy problem)とは、$\pm1$ の値をとる無限列 $f$ について、斉次な算術級数に沿った和 $\sum_{j=1}^nf(jd)$ の絶対値が $n,d$ を動かすと上に有界でないか、という問題である。Tao が 2016 年に、どの列でも有界でないことを証明して解決した。有界性の問題は有限の列の問題に言い換えられ、和を $1$ 以下に抑えられる列の長さは $11$ までである。完全乗法的な列では食い違いは部分和の上限に等しく、3 進展開の数字 $1$ の個数で和が増える例は増え方が対数的である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 完全乗法的関数, 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$ 以上である。

Erdős の食い違い問題の解決(Tao)

$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. $\operatorname{disc}(f)\le C$ となる無限列 $f\colon\mathbb Z_{>0}\to\{-1,+1\}$ がある。
  2. すべての $N$ について、$\operatorname{disc}(f)\le C$ となる長さ $N$ の列がある。

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$ の場合は手で解ける。

食い違いが 1 以下の列

食い違いが 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$ で埋めると、食い違いは有限でなくなるが、増え方はきわめて遅い。

3 進展開の 1 の個数(Borwein–Choi–Coons の例)

$\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 の対数的な増え方はきわめて遅い。

Tao の証明の筋

thm-edp-main の証明は 3 つの段階からなる(Tao16 pp. 1, 4–6)。どれもこの記事では証明しない。

  1. 完全乗法的な場合への帰着:Polymath5 の共同研究(2009〜2010 年。KL14 p. 2)で得られた Fourier 解析の議論により、定理は次の主張と同値になる。単位円周 $\{z\in\mathbb C\mid\lvert z\rvert=1\}$ に値をとる確率的な完全乗法的関数 $g$ について $\sup_n\mathbb E\bigl\lvert\sum_{j\le n}g(j)\bigr\rvert^2=\infty$(Tao16 Theorem 1.8、p. 5)。ここで同値になるのは Hilbert 空間に値をとる形の thm-edp-main であり、確率的な関数はその形に対応する(Tao16 p. 5)。
  2. Elliott 予想の対数平均版:乗法的関数の 2 点の相関 $\sum_{x/w< n\le x}g_1(a_1n+b_1)g_2(a_2n+b_2)/n$ は、$g_1$ が「指標 $\chi(n)n^{it}$ のふりをしない」なら小さい(Tao16 Theorem 1.10、p. 5。Chowla予想 の対数平均の $k=2$ の場合の一般化)。これと van der Corput の差分の議論から、反例になりうる $g$ は指標のふりをするものに限られる。
  3. 指標のふりをする場合:Polymath5 の別の議論を広げ、そのような $g$ の部分和が有界でないことを示す。prop-edp-base3 は、この場合に和の増え方が遅くなりうることを示す例である。

反例

各行は、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$ になる点を許さない」ことに依っていることを示す。

関連項目

参考文献

[1]
Terence Tao, The Erdős discrepancy problem, Discrete Analysis, 2016, 27 pp.(頁は arXiv:1509.05363v6 による。Theorem 1.1・Corollary 1.2・Example 1.3 p. 2、Example 1.4 pp. 2–3、Example 1.7 p. 4、Theorem 1.8・Theorem 1.10 p. 5)
[2]
Boris Konev, Alexei Lisitsa, A SAT attack on the Erdős discrepancy conjecture, Theory and Applications of Satisfiability Testing – SAT 2014, Lecture Notes in Computer Science 8561, Springer, 2014, pp. 219–226(番号と頁は arXiv:1402.2184v2 による。Abstract p. 1、§1 p. 2、Proposition 3・Theorem 1 p. 5)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する