2017-12-11

フィボナッチ数34

整数整数-34 整数-17

Fibonacci数 $F_9=34$ について、その性質を少し紹介したいと思います。

integers.hatenablog.com

で私の好きな素数 $5882353=588^2+2353^2$ は全ての桁がFibonacci数であり、各桁の総和= $34$ もFibonacci数だという話をしましたが、 $34$ には他にも

・ $34$ は $144$ 以下の素数の個数であり、 $34$ も $144$ もFibonacci数。 $F_n=\pi(F_m)$ が成り立つような例は $n \geq 2$ では

$F_2=\pi(F_3), \ F_3=\pi(F_4), \ F_4=\pi(F_5), \ F_6=\pi(F_8), \ F_9=\pi(F_{12})$

しか知られていない。

・ $34$ は(重複を含めた)素因数の和が素数となるような最小のFibonacci合成数。

$34=2 \times 17, \ 2+17=19$ .

・ $6F_n-1, \ 6F_n+1$ がともに合成数となるような最小のFibonacci数 $n \geq 1$ 。

$\begin{align} &6F_1-1 = 5, \quad 6F_1+1=7 \\ &6F_2-1 = 5, \quad 6F_2+1=7 \\ &6F_3-1 = 11, \quad 6F_3+1=13 \\ &6F_4-1 = 17, \quad 6F_4+1=19 \\ &6F_5-1 = 29, \quad 6F_5+1=31 \\ &6F_6-1 =47, \quad 6F_6+1=49=7^2 \\ &6F_7-1 = 77=7\times 11, \quad 6F_7+1=79 \\ &6F_8-1 = 125=5^3, \quad 6F_8+1=127 \\ &6F_9-1 = 203=7\times 29, \quad 6F_9+1=205=5\times 41 \end{align}$

などの性質が知られています。これらはささやかな性質ですが、今日おすすめしたい一押しの性質が次の定理です。

定理 $34$ は偶半素数であるような唯一のFibonacci数である。

半素数であって偶数であるようなものを偶半素数と呼んでいます。この定理は「 $17$ は連続する二つのFibonacci数の平均となるような唯一の素数」と表現することもできます。

証明には次の有名定理を使います。

Carmichaelの定理 $n$ が $6$ でも $12$ でもないような $3$ 以上の整数であれば、 $F_n$ は $n$ 未満の正整数 $m$ に対する $F_m$ の素因数としては現れないような素因数を必ず有する。

この定理の一般化を以前紹介したことがあり、

integers.hatenablog.com

関連するZsigmondyの定理は証明を紹介しています。Carmichaelの定理の証明は飛鳥さんの教科書Fibonacci数(定理2.3.8.)で読むことができます。

$\omega(n)$ を $n$ の相異なる素因数の個数とします。

integers.hatenablog.com

補題１ $n > m$ を $2$ 以上の整数であって $mn \neq 6, 12$ であるようなものとする。このとき、 $m$ と $n$ が互いに素であれば

$\omega(F_{mn}) > \omega(F_m)+\omega(F_n)$

が成り立つ。

証明. 原始的約数の記事の命題より $F_m \mid F_{mn}$ かつ $F_n \mid F_{mn}$ であり、飛鳥さんの教科書の命題1.2.3.より

$\mathrm{gcd}(F_m, F_n) = F_{\mathrm{gcd}(m, n)}$

が成り立つので、 $\mathrm{gcd}(m, n)=1$ の仮定より $\omega(F_{mn}) \geq \omega(F_m)+\omega(F_n)$ がわかる。そうして、Carmichaelの定理より $F_{mn}$ は $F_m$ と $F_n$ の持たない素因数を持っているため等号を外すことができる。 Q.E.D.

補題２ (Bugeaud-Luca-Mignotte-Siksek) $n$ を正整数とする。 $\omega(F_n) \leq 2$ であれば、 $n=1, 2, 4, 8, 12$ または奇素数 $l$ を用いて $n=l, 2l, l^2$ と表される。

証明. $16 \mid n$ のとき:

$\omega(F_{n}) \geq \omega(F_{16}) = \omega(987) = \omega(3 \times 7\times 47) = 3.$

$24 \mid n$ のとき:

$\omega(F_n) \geq \omega(F_{24}) = \omega(46368) = \omega(2^5 \times 3^2 \times 7 \times 23) = 4 > 3.$

$pq \mid n$ , $p, q$ は相異なる奇素数のとき: 補題１より

$\omega(F_n) \geq \omega(F_{pq}) > \omega(F_p)+\omega(F_q) \geq 1+1=2$

なので $\omega(F_n) \geq 3$ がわかる。

以下、 $l$ は奇素数とする。 $l^3 \mid n$ のとき: Carmichaelの定理より

$\omega(F_n) \geq \omega(F_{l^3}) > \omega(F_{l^2}) > \omega(F_l) \geq 1$

なので $\omega(F_n) \geq 3$ がわかる。

$2l^2 \mid n$ のとき: Carmichaelの定理より

$\omega(F_n) \geq \omega(F_{2l^2}) > \omega(F_{l^2}) > \omega(F_l) \geq 1$

なので $\omega(F_n) \geq 3$ がわかる。

$4l \mid n$ , $l \neq 3$ のとき: Carmichaelの定理より

$\omega(F_n) \geq \omega(F_{4l}) > \omega(F_{2l}) > \omega(F_l) \geq 1$

なので $\omega(F_n) \geq 3$ がわかる。

$12 \mid n$ , $n \neq 12$ のとき: 奇数 $m > 1$ を用いて $n=12m$ と書ける場合を考えれば十分。補題１より

$\omega(F_n) = \omega(F_{12m}) > \omega(F_4)+\omega(F_{3m}) \geq 1+1=2$

なので $\omega(F_n) \geq 3$ がわかる。以上の結果から主張が従う。 Q.E.D.

定理の証明. 飛鳥さんの教科書の命題1.1.14.よりFibonacci数 $F_n$ が偶数であるための必要十分条件は $n$ が $3$ の倍数であることなので、補題２と合わせて $F_n$ が偶半素数であれば $n=3, 6, 9, 12$ しか候補がない。 $F_3=2, F_6=8, F_9=34, F_{12}=144$ なので定理が成立することが確認できた。 Q.E.D.

2017-12-10

孙智伟による素数表現関数

定理解説

この記事は日曜数学 Advent Calendar 2017 - Adventarの10日目の記事です。9日目はru_sackさんによる

http://stagnationpoint-y.tumblr.com/post/168336222377/prime-knot-912-150mm-150mm-%E9%89%9B%E7%AD%86-%E3%82%A2%E3%82%AF%E3%83%AA%E3%83%AB%E7%B5%B5%E5%85%B7-%E3%82%B1%E3%83%B3%E3%83%88%E7%B4%99-%E4%BA%A4%E7%82%B9%E6%95%B09

stagnationpoint-y.tumblr.com

でした。

今日は中国人数学者孙智伟(Zhi Wei Sun)による素数を表現する関数に関する定理および予想を紹介します。

みなさんの数学への思いや日曜数学の成果・興味がある数学トピックなどについて自由にお話しください。
面白さを読者が共感できるように「自分はなぜそのトピックを面白いと思ったのか」を熱く書いてもらえると嬉しいです。

素数表現関数です。自明に熱く面白いので、多くの方に読んでいただけますと嬉しいです。

定理１ 正整数 $n$ に対して、 $T(n)$ を $k(k-1), \ (k=1, 2, \dots, n)$ が $\bmod{m}$ でどの二つをとっても相異なる値となるような最小の $2$ 以上の整数 $m$ と定義する。このとき、 $T(n)$ は $2n-2$ より大きい「素数または $2$ の冪乗」のうち最小のものである。

定理２ 正整数 $n$ に対して、 $S(n)$ を $2k(k-1), \ (k=1, 2, \dots, n)$ が $\bmod{m}$ でどの二つをとっても相異なる値となるような最小の $2$ 以上の整数 $m$ と定義する。このとき、 $S(n)$ は $2n-2$ より大きい素数のうち最小のものである。特に、 $S\colon \mathbb{N} \to \mathbb{N}$ は素数表現関数である*1。

定理の証明

命題１ $m, n \geq 2$ を $k(k-1), \ (k=1, \dots, n)$ が $\bmod{m}$ で相異なる値をとるような整数とする。このとき、次が成り立つ。

$m \geq 2n-1.$
$n \geq 15$ かつ $m \leq 2.4n$ ならば $m$ は素数であるか $2$ の冪乗である。

証明. 1. の証明: $m \leq 2n-2$ と仮定する。このとき、 $n \geq m/2+1$ に注意する。 $m$ が偶数ならば

$\displaystyle \left(\frac{m}{2}+1\right)\left(\frac{m}{2}+1-1\right)-\frac{m}{2}\left(\frac{m}{2}-1\right) = m \equiv 0 \pmod{m}$

となって矛盾する。 $m$ が奇数のときは、 $n \geq \frac{m+3}{2}$ なので

$\displaystyle \frac{m+3}{2}\left(\frac{m+3}{2}-1\right)-\frac{m-1}{2}\left(\frac{m-1}{2}-1\right) = 2m \equiv 0 \pmod{m}$

となってこの場合も矛盾する。2. の証明は準備が必要なので少し後で証明する。 Q.E.D.

$n \geq 15, m \in [2n-1, 2.4n]$ なる整数 $n, m$ であって、 $k(k-1) \bmod{m}, \ (k=1, \dots, n)$ が相異なる値を取るようなものがあったとして固定する。

補題１ 任意の奇素数 $p$ に対して、 $m \neq 2p$ である。

証明. $m=2p$ とする。このとき、

$\displaystyle \frac{p+3}{2}\left(\frac{p+3}{2}-1\right) - \frac{p-1}{2}\left(\frac{p-1}{2}-1\right) = 2p \equiv 0 \pmod{2p}$

が成り立つので、 $\frac{p+3}{2} > n$ でなければならない。すると、 $2n-1 \leq p=m/2 \leq 1.2n$ となるが、このような不等式は今の状況では成り立ち得ない。 Q.E.D.

補題２ 任意の奇素数 $p$ に対して、 $p^2 \nmid m$ である。

証明. $m=p^2q$ と書けたと仮定する( $p$ は奇素数で $q$ は正整数)。 $k=\frac{p+1}{2}, \ l=k+pq \leq 2pq$ とおく。このとき、

$\displaystyle l(l-1)-k(k-1)=(l-k)(l+k-1)=pq(pq+2k-1) \equiv 0 \pmod{p^2q}$

なので、 $2pq \geq l > n$ でなければならない。 $p > 3$ ならば

$\displaystyle n < \frac{2m}{p} \leq \frac{2}{5}m \leq \frac{2}{5}\cdot 2.4n < n$

となって矛盾する。また、 $p=3$ のときは

$\displaystyle n < l=2+3q=2+\frac{m}{3} \leq 2 + 0.8n \leq n$

で矛盾する( $n \geq 15$ に注意)。 Q.E.D.

命題１の2. の証明. $n \geq 15, m \leq 2.4n$ とする。 $m$ が素数でも $2$ の冪乗でもないと仮定して矛盾を導く。補題１、２より $m=pq$ ( $p$ は奇素数で $q > 2$ は $p$ で割れない)と仮定してよいことがわかる。 $k \in [1, \frac{q}{(2, q)}]$ を

$\displaystyle k \equiv \frac{1-p}{2} \pmod{\frac{q}{(2, q)}}$

を満たすようにとる。ここで、 $(2, q)$ は $2$ と $q$ の最大公約数を表す。 $l=k+p$ とおく。このとき、

$l(l-1)-k(k-1) = p(2k-1+p) \equiv 0 \pmod{pq}$

が成り立つので、 $n < l$ でなければならない。 $q$ が偶数であると仮定すると、 $q \geq 4$ であり、

$\displaystyle l \leq p+\frac{q}{2} = \frac{m}{q}+\frac{m}{2p} \leq \frac{m}{4}+\frac{m}{6} = \frac{5}{12}m \leq \frac{5}{12} \cdot 2.4n = n$

となって矛盾するので、 $q$ は奇数である。

$\displaystyle l \leq p+q = \frac{m}{p}+\frac{m}{q} \leq \left(\frac{1}{p}+\frac{1}{q}\right)\cdot 2.4n$

であるが、 $p$ と $q$ がともに $3$ より大きければ

$\displaystyle \frac{1}{p}+\frac{1}{q} \leq \frac{2}{5} < \frac{5}{12}$

なので、

$\displaystyle l < \frac{5}{12} \cdot 2.4n = n$

となって矛盾する。さて、 $m$ の任意の素因数を $p$ として選べるので、この議論により $m$ は $3$ より大きい素因数を二つ以上もてないことがわかる。すると残るケースは $m=pq$ ( $p$ は $3$ より大きい素数で $q=3$ )の場合のみとなった。このとき、

$\displaystyle l \leq p+q = \frac{m}{3}+3 \leq \frac{2.4n}{3}+3=0.8n+3 \leq n$

となって、結局矛盾する( $n \geq 15$ に注意)。 Q.E.D.

命題２ $n > 1, m \geq 2n-1$ とする。
1. $m$ が素数または $2$ の冪乗であるとする。このとき、任意の $k, l \ (1 \leq k < l \leq n)$ に対して

$k(k-1) \not \equiv l(l-1) \pmod{m}$

が成り立つ。
2. $m$ が $2$ の冪乗であって、 $m \leq 2.4n$ を満たすとする。このとき、或る $k, l \ (1 \leq k < l \leq n)$ が存在して

$2k(k-1) \equiv 2l(l-1) \pmod{m}$

が成り立つ。

証明. 1. の証明: $m=2^a$ とする( $a$ は正整数)。 $n \leq \frac{m+1}{2} = 2^{a-1}+\frac{1}{2}$ より $n \leq 2^{a-1}$ である。任意の $1 \leq k < l \leq n$ に対して $0 < l-k < n \leq 2^{a-1}$ , $0 < l+k-1 < 2n \leq 2^a$ であることより

$l(l-1)-k(k-1) = (l-k)(l+k-1) \not \equiv 0 \pmod{2^a}$

がわかる( $l-k$ と $l+k-1$ のパリティが異なることに注意)。次に、 $m=p$ ( $p$ は奇素数)とする。任意の $1 \leq k < l\leq n$ に対して $0 < l-k < n \leq \frac{p+1}{2} < p$ , $0 < l+k-1 < 2n-1 \leq p$ であることより

$l(l-1)-k(k-1) = (l-k)(l+k-1) \not \equiv 0 \pmod{p}$

である。2. の証明: $2k(k-1) \equiv 0 \pmod{4}$ が任意の $k=1, \dots, n$ に対して成り立つので、 $m=2^a \ (a > 2)$ と仮定してよい。 $k=2^{a-2}, l=k+1$ とする。このとき、

$2l(l-1)-2k(k-1) =2^a \equiv 0 \pmod{2^a}$

が成り立つ。 $k < l = 2^{a-2}+1 < \frac{2^a}{2.4} \leq n$ であるから、証明が完了する。 Q.E.D.

Bertrandの仮説の拡張に関する研究は膨大であるが、次の事実を証明なしに用いることにする。

事実 $13$ 以上の整数 $n$ に対して、区間 $[2n-1, 2.4n]$ は必ず素数を含む。

補題３ 任意の正整数 $n$ に対して、 $2n-1 \leq T(n) \leq S(n) \leq 2.4n$ が成り立つ。

証明. $S(1)=T(1)=2$ より、 $n=1$ のときは正しいことがわかる。 $n \geq 2$ とする。 $2k(k-1) \ (k=1, \dots, n)$ が $\bmod{S(n)}$ で相異なる値をとるならば、 $k(k-1) \bmod{S(n)} \ (k=1, \dots, n)$ もそうなので、 $S(n) \geq T(n)$ であることがわかる。また、命題１の1. より $2n-1 \leq T(n)$ がわかる。残るは $S(n) \leq 2.4n$ であるが、 $n < 13$ の場合は直接計算で確かめられる。 $n \geq 13$ のとき、奇素数 $p \in [2n-1, 2.4n]$ をとる。命題２の1. より

$k(k-1) \not \equiv l(l-1) \pmod{p}$

が任意の $1 \leq k < l \leq n$ に対して成り立つが、これは

$2k(k-1) \not \equiv 2l(l-1) \pmod{p}$

と同値であることに注意すると、 $S(n) \leq p \leq 2.4n$ が成り立つことがわかる。 Q.E.D.

定理１、２の証明. $n=1, \dots, 14$ については直接確認できる。 $n \geq 15$ とする。補題３より $T(n) \in [2n-1, 2.4n]$ であるから、命題１の2. より $T(n)$ は素数または $2$ の冪乗であることがわかる。そして、命題２の1. より $T(n)$ は $2n-2$ より大きい素数または $2$ の冪乗のうち最小の整数であることが従う。同様に、補題３より $S(n) \in [2n-1, 2.4n]$ であり、命題１の2. および命題２の2. から $S(n)$ は素数であることがわかる。命題２の1. より $S(n)$ は $2n-2$ より大きい最小の素数であることが従う。 Q.E.D.

追記

定理２には「事実」を使う代わりにBertrandの仮説だけで十分な数学的帰納法を使ったより短い証明が存在することを飛鳥さんと彼のご友人に教えていただきました。

*1:だけでなく、全ての素数を表現する。

2017-12-10

セメレディの定理の組合せ論的証明ー４

等間隔に並ぶ素数を追い求めて

$K$ -AP $\overrightarrow{P{ }}$ に対して、一様確率測度 $\mu_{\overrightarrow{P{ }}}\colon 2^{\mathbb{Z}} \to [0, 1]$ を $\mathbf{A} \subset \mathbb{Z}$ に対して

$\displaystyle \mu_{\overrightarrow{P{ }}}(\mathbf{A}) := \frac{1}{K}\#\{i \in [K] \mid P(i) \in \mathbf{A}\}$

と定義する。

$L, H \in \mathbb{N}$ に対して、 $\overrightarrow{R{ }}$ が $L\times H$ -長方形であるとは、 $a \in \mathbb{Z}, r, s \in \mathbb{N}$ を用いて

$\displaystyle \overrightarrow{R{ }}=(a+lr+hs)_{(l, h) \in [L]\times [H]}$

と表されるもののことをいう。 $\overrightarrow{R{ }}$ に付随する写像 $R\colon \mathbb{Z}^2 \to \mathbb{Z}$ を $R(l, h) := a+lr+hs$ で定義する。

$L\times H$ -長方形 $\overrightarrow{R{ }}$ に対して、各 $h \in [H]$ 毎に $L$ -AP $\overrightarrow{R_h}$ を

$\overrightarrow{R_h}:= (R(l, h) )_{l \in [L]}$

で定義し、各 $l \in [L]$ 毎に $H$ -AP $\overrightarrow{R^l}$ を

$\overrightarrow{R^l} := (R(l, h) )_{h \in [H]}$

で定義する。また、一様確率測度 $\mu_{\overrightarrow{R{ }}}\colon 2^{\mathbb{Z}} \to [0, 1]$ を $\mathbf{A} \subset \mathbb{Z}$ に対して

$\displaystyle \mu_{\overrightarrow{R{ }}}(\mathbf{A}) := \frac{1}{LH}\#\{(l, h) \in [L]\times [H] \mid R(l, h) \in \mathbf{A}\}$

と定義する。このとき、二重カウンティング恒等式

$\displaystyle \mu_{\overrightarrow{R{ }}} = \frac{1}{H}\sum_{h \in [H]}\mu_{\overrightarrow{R_h}} = \frac{1}{L}\sum_{l \in [L]}\mu_{\overrightarrow{R^l}}$

が成り立つ。

確率測度 $\mu, \nu\colon 2^{\mathbb{Z}} \to [0, 1]$ に対して、全変動 $d_{\mathrm{TV}}(\mu, \nu)$ を

$\displaystyle d_{\mathrm{TV}}(\mu, \nu) := \sup_{\mathbf{A} \subset \mathbb{Z}}\left|\mu(\mathbf{A})-\nu(\mathbf{A})\right|$

で定義する。

補題１ $L, H \in \mathbb{N}, L \leq H$ , $\overrightarrow{P{ }}$ : $H$ -APとし、 $L\times H$ -長方形 $\overrightarrow{R{ }}$ を $\overrightarrow{R{ }}:=(P(l+h) )_{(l, h) \in [L]\times [H]}$ で定義する。このとき、

$\displaystyle d_{\mathrm{TV}}(\mu_{\overrightarrow{P{ }}}, \mu_{\overrightarrow{R{ }}}) \leq \frac{2L}{H}$

が成り立つ。

証明. $\mathbf{A} \subset \mathbb{Z}$ を任意にとる。このとき、

$\displaystyle \mu_{\overrightarrow{R{ }}}(\mathbf{A}) = \frac{1}{H}\sum_{l \in [L]}\mu_{\overrightarrow{R^l}}(\mathbf{A}) = \frac{1}{LH}\sum_{l \in [L]}\#\{h\in l+[H] \mid P(h) \in \mathbf{A}\}$

なので、

$\displaystyle \mu_{\overrightarrow{R{ }}}(\mathbf{A})-\mu_{\overrightarrow{P{ }}}(\mathbf{A}) = \frac{1}{LH}\sum_{l \in [L]}\left(\#\{h\in l+[H] \mid P(h) \in \mathbf{A}\}-\#\{h\in [H] \mid P(h) \in \mathbf{A}\}\right)$

が成り立つ。 $[H]$ と $l+[H]$ が重ならない部分は高々 $2L$ なので、

$\displaystyle \left|\mu_{\overrightarrow{R{ }}}(\mathbf{A})-\mu_{\overrightarrow{P{ }}}(\mathbf{A}) \right| \leq \frac{1}{LH}\sum_{l \in [L]}2L = \frac{2L}{H}$

が得られる。 $\mathbf{A}$ は任意だったので証明が完了する。 Q.E.D.

APからなる集合 $\mathcal{P} \subset \mathcal{AP}$ が非有界であるとは、集合 $\{\mathrm{len}(\overrightarrow{P{ }}) \mid \overrightarrow{P{ }} \in \mathcal{P}\}$ が非有界であることと定義する。非有界な $\mathcal{P} \subset \mathcal{AP}$ と $\mathbf{A} \subset \mathbb{Z}$ に対して、 $\mathbf{A}$ の $\mathcal{P}$ に沿った上密度 $\overline{d}_{\mathcal{P}}(\mathbf{A})$ を

$\displaystyle \overline{d}_{\mathcal{P}}(\mathbf{A}) := \limsup_{\mathrm{len}(\overrightarrow{P{ }}) \to \infty, \ \overrightarrow{P{ }} \in \mathcal{P}}\mu_{\overrightarrow{P{ }}}(\mathbf{A})=\inf_{N \in \mathbb{Z}}\sup_{\overrightarrow{P{ }} \in \mathcal{P}, \ \mathrm{len}(\overrightarrow{P{ }}) \geq N}\mu_{\overrightarrow{P{ }}}(\mathbf{A})$

と定義し、 $\mathbf{A}$ の $\mathcal{P}$ に沿った下密度 $\underline{d}_{\mathcal{P}}(\mathbf{A})$ を

$\displaystyle \underline{d}_{\mathcal{P}}(\mathbf{A}) := \liminf_{\mathrm{len}(\overrightarrow{P{ }}) \to \infty, \ \overrightarrow{P{ }} \in \mathcal{P}}\mu_{\overrightarrow{P{ }}}(\mathbf{A})=\sup_{N \in \mathbb{Z}}\inf_{\overrightarrow{P{ }} \in \mathcal{P}, \ \mathrm{len}(\overrightarrow{P{ }}) \geq N}\mu_{\overrightarrow{P{ }}}(\mathbf{A})$

と定義する。定義から明らかに $0 \leq \underline{d}_{\mathcal{P}}(\mathbf{A}) \leq \overline{d}_{\mathcal{P}}(\mathbf{A}) \leq 1$ が成り立つ。 $\underline{d}_{\mathcal{P}}(\mathbf{A})= \overline{d}_{\mathcal{P}}(\mathbf{A})$ が成り立つとき、その値を $\mathbf{A}$ の $\mathcal{P}$ に沿った密度といい、 $d_{\mathcal{P}}(\mathbf{A})$ と表す。

例１) $\mathcal{P} = \{\overrightarrow{[N]} \mid N \in \mathbb{N}\}$ の場合、 $\overline{d}_{\mathcal{P}}(\mathbf{A})$ は $\mathbf{A}$ の上漸近密度で $\underline{d}_{\mathcal{P}}(\mathbf{A})$ は下漸近密度、 $d_{\mathcal{P}}(\mathbf{A})$ は漸近密度(自然密度)である。

例２) $\mathcal{P} = \{a+\overrightarrow{[N]} \mid a \in \mathbb{Z}, N \in \mathbb{N}\}$ の場合、 $\overline{d}_{\mathcal{P}}(\mathbf{A})$ は $\mathbf{A}$ のBanach上漸近密度で $\underline{d}_{\mathcal{P}}(\mathbf{A})$ はBanach下漸近密度、 $d_{\mathcal{P}}(\mathbf{A})$ はBanach漸近密度である(Banach上漸近密度しか使わない)。

$\mathcal{P} \subset \mathcal{AP}$ は非有界とし、 $\mathbf{A} \subset \mathbb{Z}$ とする。任意の $\varepsilon > 0$ に対して $N \in \mathbb{N}$ が存在し、長さが $N$ 以上の $\overrightarrow{P{ }} \in \mathcal{P}$ に対して

$\displaystyle \mu_{\overrightarrow{P{ }}}(\mathbf{A}) \leq \overline{d}_{\mathcal{P}}(\mathbf{A})+\varepsilon$ −①

が成り立ち、いくらでも長さが大きい $\overrightarrow{P{ }} \in \mathcal{P}$ が存在して

$\displaystyle \left|\mu_{\overrightarrow{P{ }}}(\mathbf{A})- \overline{d}_{\mathcal{P}}(\mathbf{A})\right| \leq \varepsilon$ −②

が成り立つ。 $\mathbf{A}$ の $\mathcal{P}$ に沿った密度が存在すれば、任意の $\varepsilon > 0$ に対して $N \in \mathbb{N}$ が存在して

$\displaystyle \left|\mu_{\overrightarrow{P{ }}}(\mathbf{A})- d_{\mathcal{P}}(\mathbf{A})\right| \leq \varepsilon$ −③

が長さが $N$ 以上の $\overrightarrow{P{ }} \in \mathcal{P}$ に対して成り立つ(定義の確認)。

注意) この記号設定においては、Szemerédiの定理は $\overline{bd}(\mathbf{A}) > 0 \Longrightarrow \overline{d}_{\mathcal{AP}}(\mathbf{A})=1$ と簡潔に表現することができる。この同値性に関する $\Longrightarrow$ は自明であるが、 $\Longleftarrow$ は次のように示す*1: $K \in [N]$ を任意にとる。 $\overline{d}_{\mathcal{AP}}(\mathbf{A})=1$ が成り立つと仮定すると、②より

$\displaystyle \#\{i \in [M] \mid P(i) \in \mathbf{A}\} \geq \left(1-\frac{1}{K+1}\right)M > M-L$

が成り立つような $M$ -AP $\overrightarrow{P{ }}$ が存在する( $M=KL+N, L, N \in \mathbb{N}, 0 \leq N < K$ )。任意の $l \in [L]$ に対して $P( (l-1)K+[K]) \not \subset \mathbf{A}$ であると仮定すると

$\displaystyle \#\{i \in [M] \mid P(i) \not \in \mathbf{A}\} \geq L$

となって矛盾する。よって、或る $l \in [L]$ が存在して $P( (l-1)K+[K]) \subset \mathbf{A}$ となる。これは $\mathbf{A}$ が $K$ -APを含むことを示しており、 $K$ は任意であるためSzemerédiの定理が従う。

補題２ (劣加法性) $\mathbf{A}, \mathbf{B} \subset \mathbb{Z}$ と非有界な $\mathcal{P} \subset \mathcal{AP}$ を考える。このとき、

$\overline{d}_{\mathcal{P}}(\mathbf{A}\cup \mathbf{B}) \leq \overline{d}_{\mathcal{P}}(\mathbf{A}) + \overline{d}_{\mathcal{P}}(\mathbf{B})$

が成り立つ。

証明. これは

$\displaystyle \limsup \mu_{\overrightarrow{P{ }}}(\mathbf{A} \cup \mathbf{B}) \leq \limsup (\mu_{\overrightarrow{P{ }}}(\mathbf{A})+\mu_{\overrightarrow{P{ }}}(\mathbf{B}) ) \leq \limsup \mu_{\overrightarrow{P{ }}}(\mathbf{A})+\limsup \mu_{\overrightarrow{P{ }}}(\mathbf{B})$

からわかる。 Q.E.D.

補題３ (上密度に対する鳩ノ巣原理) $\mathcal{P} \subset \mathcal{AP}$ は非有界で、 $\mathbf{S} \subset \mathbb{Z}$ は $\mathcal{P}$ に沿った上密度が正であるとする。このとき、 $\mathbf{S}$ をどのように有限色に類別しても、 $\mathcal{P}$ に沿った上密度が正であるような類が存在する。

証明. 劣加法性と背理法で示せる。 Q.E.D.

重要な概念を定義する。

定義 (二重カウンティンング性質) $\mathcal{P} \subset \mathcal{AP}$ が二重カウンティング性質を持つとは以下の性質が成り立つときにいう: 任意の $\varepsilon > 0$ に対して $N_1(\varepsilon) \in \mathbb{N}$ が存在し、 $\varepsilon$ と任意の整数 $L \geq N_1(\varepsilon)$ に対して $N_2(\varepsilon, L) \geq L$ が存在して、 $N_1(\varepsilon) \leq L_1 \leq N_2(\varepsilon, L_1) \leq L_2$ なる $L_1, L_2\in \mathbb{N}$ をとる。 $H_1, H_2 \in \mathbb{N}$ とし、 $L_1 \times H_1$ -長方形 $\overrightarrow{R_1}$ と $L_2\times H_2$ -長方形 $\overrightarrow{R_2}$ であって

$\displaystyle d_{\mathrm{TV}}(\mu_{\overrightarrow{R_1}}, \mu_{\overrightarrow{R_2}}) \leq \frac{1}{L_1}$

が成り立つようなものを考える。このとき、 $H_2$ 個の $L_2$ -AP $(\overrightarrow{R_2})_h \ (h \in [H_2])$ が $\mathcal{P}$ に属するならば、高々 $\varepsilon H_1$ 個の例外を除く $L_1$ -AP $(\overrightarrow{R_1})_h \ (h \in [H_1])$ は $\mathcal{P}$ に属する。

とりあえず $\mathcal{AP}$ は自明に二重カウンティング性質を満たす。二重カウンティンング性質の威力は次の命題の形で発揮される。

命題 $\mathcal{P} \subset \mathcal{AP}$ は二重カウンティング性質を満たすとする。任意の $\varepsilon > 0$ に対して $N_1(\varepsilon) \in \mathbb{N}$ が存在し、 $\varepsilon$ と任意の整数 $N \geq N_1(\varepsilon)$ に対して $N_2(\varepsilon, N) \geq N$ が存在して、 $N_1(\varepsilon) \leq L \leq N_2(\varepsilon, L) \leq H$ なる $L, H\in \mathbb{N}$ をとるとき、次が成立する。
(i) $H$ -AP $\overrightarrow{P{ }} \in \mathcal{P}$ に対して、高々 $\varepsilon H$ 個の例外を除いて $L$ -AP $(P(h+l) )_{l \in [L]} \ (h \in [H])$ は $\mathcal{P}$ に属する。
(ii) $L\times H$ -長方形 $\overrightarrow{R{ }}$ に対して、 $L$ 個の $H$ -AP $\overrightarrow{R^l} \ (l \in [L])$ が $\mathcal{P}$ に属するならば、高々 $\varepsilon H$ 個の例外を除いて $L$ -AP $\overrightarrow{R_h} \ (h \in [H])$ は $\mathcal{P}$ に属する。

証明. (i)の証明: $N_1(\varepsilon)$ は二重カウンティング性質の定義のものとし、 $N_2(\varepsilon, N)$ は定義のものと $2N^2$ の $\max$ をとって再定義する。

$\displaystyle \overrightarrow{R_1} := (P(h+l) )_{(l, h) \in [L]\times [H]}, \quad \overrightarrow{R_2} := (P(h) )_{(h, 1) \in [H] \times [1]}$

とすると、 $(\overrightarrow{R_2})_1 = \overrightarrow{P{ }}\in \mathcal{P}$ である。また、補題１より

$\displaystyle d_{\mathrm{TV}}(\mu_{\overrightarrow{R_1}}, \mu_{\overrightarrow{R_2}}) \leq \frac{2L}{H} \leq \frac{1}{L}$

が成り立つので、 $\mathcal{P}$ の二重カウンティング性質を $L_1=L, L_2=H, H_1=H, H_2=1$ として適用することにより、高々 $\varepsilon H$ 個の例外を除いて、 $h \in [H]$ に対して

$(\overrightarrow{R_1})_h = (P(h+l) )_{l \in [L]} \in \mathcal{P}$

である。

(ii)の証明: $\overrightarrow{R_1}:=\overrightarrow{R{ }}=(R(l, h) )_{(l, h) \in [L]\times [H]}$ として、 $\overrightarrow{R_2}$ を

$\displaystyle \overrightarrow{R_2} := (R(l, h))_{(h, l) \in [H]\times [L]}$

と定義する。このとき、二重カウンティング恒等式から

$\displaystyle \mu_{\overrightarrow{R_1}} = \frac{1}{L}\sum_{l \in [L]}\mu_{\overrightarrow{(R_1)^l}}= \frac{1}{L}\sum_{l \in [L]}\mu_{\overrightarrow{R^l}}= \frac{1}{L}\sum_{l \in [L]}\mu_{\overrightarrow{(R_2)_l}}=\mu_{\overrightarrow{R_2}}$

なので、 $d_{\mathrm{TV}}(\mu_{\overrightarrow{R_1}}, \mu_{\overrightarrow{R_2}}) = 0$ である。よって、 $\mathcal{P}$ の二重カウンティング性質を $L_1=L, L_2=H, H_1=H, H_2=L$ として適用することにより主張が従う。 Q.E.D.

*1:セミナー中に飛鳥さんに指摘していただきました。

INTEGERS

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

フィボナッチ数34

孙智伟による素数表現関数

定理の証明

関連する極めて興味深い予想

追記

セメレディの定理の組合せ論的証明ー４