4
大学数学基礎解説
文献あり

ErdösによるSylvester-Schurの定理の証明とBertrand-Chebyshevの定理

147
0
$$\newcommand{P}[0]{\mathbb{P}} $$

はじめに

 はじめまして.Mathlog初投稿です.よろしくお願いします.
 こちらは AMC2023 (Advent Math Calendar2023) の23日目の記事です.毎日楽しく記事を読んでいましたが,それと同時に記事のクオリティがどれも高くてハードルが上がっているのを日々感じていました.昨日公開された Hi_mathさんの記事 は一風変わった切り口の記事でとても興味深かったです.まだ読んでいない方はぜひお読みください!
 さて,今回何について書くかはあれこれ思案しましたが(丸一日悩みました…),私の好きな定理のひとつ,Bertrand-Chebyshevの定理について書くことにしました.ただBertrand-Chebyshevの定理に関してはそれなりに日本語のサイトが充実しているので,今回はその一般化であるSylvester-Schurの定理について紹介します.
 この記事では,まずErdösが1934年に発表した論文に沿ってSylvester-Schurの定理を証明し,次にこの定理から従う幾つかの主張について紹介します.

Sylvester-Schurの定理とは

 Sylvester-Schurの定理の主張は以下の通りです.

Sylvester-Schurの定理

 $n,k$を正整数とする.$n\geq2k$のとき,$k$個の正整数$n,n-1,\ldots,n-k+1$の中で$k$より大きな素因数$p$を持つものが存在する.

 美しいですね.この定理は以下と同値です.

Sylvester-Schurの定理と同値な主張

 $n,k$を正整数とする.$n\geq2k$のとき,二項係数$\dbinom{n}{k}$$k$より大きな素因数$p$をもつ.

 この記事では主に定理2の証明を目指します.

 以下,次の記号を断りなしに使用します.

  • 素数全体の集合を$\P$と書く.
  • 正整数$n$が素数$p$で割り切れる最大の回数を$v_p(n)$と書く.
  • 正整数$n$に対して,$n$以下の素数の個数を$\pi(n)$と書く.
  • 半開区間$\{\, x \, |\, a < x \leq b \,\}$のことを$(a,b\,]$と書く.

証明の方針

  • まず,証明に用いる命題をいくつか準備します.
  • 次に,$1 \leq k \leq 7$$8 \leq k \leq 32$$33 \leq k$に分けて議論します.
  • $8 \leq k \leq 32$では$k \leq \sqrt{n}$$k > \sqrt{n}$に分けて議論します.
  • $33 \leq k$では$k \leq n^\frac{2}{3}$$k> n^\frac{2}{3}$に分けて議論します.さらに,$k> n^\frac{2}{3}$のときは$n < 900$$n \geq 900$に分けて議論します.

証明

準備

 $a = v_p\left(\dbinom{n}{k}\right)$とおく.このとき,$p^a \leq n$が成立する.

 $\dbinom{n}{k} = \dfrac{n!}{k!(n-k)!}$だから,Legendreの定理より
$$a = \sum_{i=1}^{\infty} \left( \left\lfloor \frac{n}{p^i} \right\rfloor - \left\lfloor \frac{k}{p^i} \right\rfloor - \left\lfloor \frac{n-k}{p^i} \right\rfloor \right)$$
が従う.ここで,任意の$i$について$\left\lfloor \dfrac{n}{p^i} \right\rfloor - \left\lfloor \dfrac{k}{p^i} \right\rfloor - \left\lfloor \dfrac{n-k}{p^i} \right\rfloor$$0$$1$のいずれかをとり,$p^i>n \iff i > \log_p n$のときは常に$\left\lfloor \dfrac{n}{p^i} \right\rfloor - \left\lfloor \dfrac{k}{p^i} \right\rfloor - \left\lfloor \dfrac{n-k}{p^i} \right\rfloor = 0$となるから,
$$a \leq \sum_{i=1}^{\log_p n}1 = \log_p n$$
となり補題は成立する.

 $n$を正整数とする.このとき,$\dbinom{2n}{n}$は以下の条件を満たす任意の素数$p$で割り切れる:
$$\text{「} \, \lfloor\sqrt[l]{n}\rfloor < p \leq \lfloor\sqrt[l]{2n}\rfloor \, \text{を満たす正整数} \, l \, \text{が存在する.」}$$

 素数$p$に対して$\lfloor\sqrt[l]{n}\rfloor < p \leq \lfloor\sqrt[l]{2n}\rfloor$,つまり$\sqrt[l]{n} < p \leq \sqrt[l]{2n}$を満たす正整数$l$が存在するとき,$n< p^l \leq 2n$である.ここで,Legendreの定理より
\begin{align*} v_p\left(\dbinom{2n}{n}\right) &= \left( \left\lfloor \frac{2n}{p} \right\rfloor + \cdots + \left\lfloor \frac{2n}{p^{l-1}} \right\rfloor + \left\lfloor \frac{2n}{p^l} \right\rfloor \right) - 2\left( \left\lfloor \frac{n}{p} \right\rfloor + \cdots + \left\lfloor \frac{n}{p^{l-1}} \right\rfloor \right) \\ &= \left( \left\lfloor \frac{2n}{p}\right\rfloor - 2\left\lfloor \frac{n}{p}\right\rfloor \right) + \cdots + \left( \left\lfloor \frac{2n}{p^{l-1}}\right\rfloor - 2\left\lfloor \frac{n}{p^{l-1}}\right\rfloor \right) + \left\lfloor \frac{2n}{p^l} \right\rfloor \end{align*}
が成立する.
 このとき,任意の$1 \leq i \leq k-1$に対して$\left\lfloor \dfrac{2n}{p^{i}}\right\rfloor \geq 2\left\lfloor \dfrac{n}{p^{i}}\right\rfloor$であり,$\left\lfloor \dfrac{2n}{p^l} \right\rfloor = 1$だから$ v_p\left(\dbinom{2n}{n}\right) \geq 1$.よって$\dbinom{2n}{n}$$p$で割り切れる.

 正整数$i$に対して$a_i = \left\lceil \dfrac{n}{2^i} \right\rceil$ とおき,$m$$2^m \geq n$を満たす最小の正整数とする.このとき,任意の正整数$l$に対して
$$\bigcup_{i=1}^m \left(\lfloor \sqrt[l]{a_i} \rfloor, \lfloor \sqrt[l]{2a_i} \rfloor \right] \supseteq \left(1,\lfloor \sqrt[l]{n} \rfloor \right]$$
が成立する.

 数列$\{a_i\}$は広義単調減少だから,$\{\lfloor \sqrt[l]{a_i} \rfloor\}$,$\{\lfloor \sqrt[l]{2a_i} \rfloor\}$も広義単調減少である.
 ここで,$\lfloor \sqrt[l]{a_m} \rfloor = 1$であり,$2a_1 = 2\left\lceil \dfrac{n}{2} \right\rceil \geq n$より$ \lfloor \sqrt[l]{2a_1} \rfloor \geq \lfloor \sqrt[l]{n} \rfloor$である.
 また,任意の$1< i< m$に対して$ \left\lceil \dfrac{n}{2^i} \right\rceil \leq 2\left\lceil \dfrac{n}{2^{i+1}} \right\rceil$,すなわち$a_i \leq 2a_{i+1}$が成立するから$\lfloor \sqrt[l]{a_i} \rfloor \leq \lfloor \sqrt[l]{2a_{i+1}} \rfloor$が従う.
 よって
$$\bigcup_{i=1}^m \left(\lfloor \sqrt[l]{a_i} \rfloor, \lfloor \sqrt[l]{2a_i} \rfloor \right] \supseteq \left(1,\lfloor \sqrt[l]{n} \rfloor \right]$$
が示された.

 今後,この補題で定義した意味で$a_i$$m$を用います.

$$\prod_{\substack{p \leq n \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \cdot \cdots \leq \binom{2a_1}{a_1} \binom{2a_2}{a_2} \cdots \binom{2a_m}{a_m}$$
が成立する.

 補題4より,右辺は$\lfloor \sqrt[l]{a_i} \rfloor < p \leq \lfloor \sqrt[l]{2a_i} \rfloor$($i,l$は正整数,$1 \leq i \leq m$)を満たす素数$p$で割り切れる.ここで,補題5より,右辺は$1 < p \leq \lfloor \sqrt[l]{n} \rfloor$,つまり$1 < p \leq \sqrt[l]{n}$($l$は正整数)を満たす素数$p$で割り切れる.
 ここで,$m_i$$2^{m_i} \geq a_i$を満たす最小の自然数とすると,$1 \leq l < m_i$のとき$\sqrt[l+1]{2a_i} \leq \sqrt[l]{a_i}$となるから,$(\sqrt[l+1]{a_i},\sqrt[l+1]{2a_i}\,] \, \cap \, (\sqrt[l]{a_i},\sqrt[l]{2a_i}\,] = \varnothing$となる.また,$l \geq m_i$のとき$\lfloor \sqrt[l]{a_i} \rfloor < p \leq \lfloor \sqrt[l]{2a_i} \rfloor$を満たす素数$p$は存在しない.
 よって,右辺は$\prod_{\substack{p \leq n \\ p \in \P}}p$で割り切れ,右辺を$\prod_{\substack{p \leq n \\ p \in \P}}p$で割ったものは$\prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p$で割り切れ,右辺を$\prod_{\substack{p \leq n \\ p \in \P}}p \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p$で割ったものは$\prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p$で割り切れ,…となる.つまり右辺は$\prod_{\substack{p \leq n \\ p \in \P}}p \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \cdot \cdots$で割り切れる.従って
$$\prod_{\substack{p \leq n \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \cdot \cdots \leq \binom{2a_1}{a_1} \binom{2a_2}{a_2} \cdots \binom{2a_m}{a_m}$$
が成立する.

 この定理の一連の証明の中で一番難しかったです.Erdösの論文では"From all this, it follows that…"で終わりでした(証明は書かれていません).

$$\binom{2a_1}{a_1} \binom{2a_2}{a_2} \cdots \binom{2a_m}{a_m} \leq 4^n\tag{1}$$
が成立する.

 $n < 10$のときは調べると分かる.
 $n \geq 10$のときを考える.$n$未満の任意の正整数で式(1)が成立すると仮定する.
 ここで,式(1)において$n = 2a_2 - 1$とすると
$$ \binom{2a'_1}{a'_1} \binom{2a'_2}{a'_2} \cdots \binom{2a'_{m'}}{a'_{m'}} \leq 4^{2a_2 - 1}$$
となる.ただし,$a'_i = \left\lceil \dfrac{2a_2 - 1}{2^i} \right\rceil$$m'$$2^{m'} \geq 2a_2-1$を満たす最小の正整数とおいた.このとき,
$$a'_i = \left\lceil \frac{2a_2 - 1}{2^i} \right\rceil = \left\lceil \frac{1}{2^{i-1}}\left\lceil \frac{n}{2^2} \right\rceil - \frac{1}{2^i}\right\rceil = \left\lceil \frac{n}{2^{i+1}} \right\rceil = a_{i+1}$$
であり,$m' = m-1$であるから,この式は
$$ \binom{2a_2}{a_2} \binom{2a_3}{a_3} \cdots \binom{2a_m}{a_m} \leq 4^{2a_2 - 1} \iff \binom{2a_1}{a_1} \binom{2a_2}{a_2} \cdots \binom{2a_m}{a_m} \leq \binom{2a_1}{a_1} 4^{2a_2 - 1}$$
と書ける.
 また,$n \geq 10$より$a_n \geq 5$であり,正整数$l \geq 5$に対して$\dbinom{2l}{l} < 4^{l-1}$が成立するから(これは数学的帰納法により示せる),この式は
$$ \binom{2a_1}{a_1} \binom{2a_2}{a_2} \cdots \binom{2a_m}{a_m} \leq 4^{a_1 + 2a_2 - 2}$$
と書ける.ここで,$2a_1 \leq n+1$$2a_2 \leq a_1+1$より$a_1 + 2a_2 - 2 \leq 2a_1-1 \leq n$となるから
$$ \binom{2a_1}{a_1} \binom{2a_2}{a_2} \cdots \binom{2a_m}{a_m} \leq 4^n$$
が従う.よって,任意の$n$に対して式(1)が成立することが示された.

 正整数$n$に対して
$$\prod_{\substack{p \leq n \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \cdot \cdots \leq 4^n$$
が成立する.

 補題6,補題7より従う.

 $\dbinom{n}{k}$$N$より大きな素因数をもたないとする.このとき,
$$\dbinom{n}{k} \leq \prod_{\substack{p \leq N \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \cdot \cdots$$
が成立する.

 $N$以下の素数$p$を考える.$p^l \leq n < p^{l+1}$を満たす正整数$l$をとると,$\sqrt[l+1]{n} < p \leq \sqrt[l]{n}$が従うから
$$v_p \left( \prod_{\substack{p \leq N \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \cdot \cdots \right) = l$$
となる.一方,$a = {v_p\left(\dbinom{n}{k}\right)}$ とおくと,命題3より$p^a \leq n$となるので$a \leq l$
 つまり,任意の$N$以下の素数$p$に対して
$$ v_p\left(\dbinom{n}{k}\right) \leq v_p \left( \prod_{\substack{p \leq N \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \cdot \cdots \right) $$
が成立するから補題は従う.

 以下の証明では命題3,命題8,命題9を使います.

$k \geq 33$のとき

$k \leq n^{\frac{2}{3}}$のとき

 $33\leq k \leq n^\frac{2}{3}$のとき定理2は成立する.

背理法で示す.

 $\dbinom{n}{k}$の素因数が全て$k$以下であると仮定する.
 $k\ \geq 33$のとき$\pi(k) \leq \dfrac{1}{3}k$だから,命題3より
$$\binom{n}{k} = \prod_{\substack{p\leq k \\ p \in \P}} p^{v_p{(\binom{n}{k})}} \leq \prod_{\substack{p\leq k \\ p \in \P}} n = n^{\pi(k)} \leq n^{\frac{1}{3}k}$$
となる.
一方,
$$\binom{n}{k} = \frac{n}{k} \cdot \frac{n-1}{k-1} \cdot \cdots \cdot \frac{n-k+1}{1} > \left( \frac{n}{k} \right)^{k}$$
が成立する.これより
$$\left( \frac{n}{k} \right)^{k} < n^{\frac{1}{3}k} \iff n^{\frac{2}{3}k} < k^k$$
が従うが,これは$k \leq n^{\frac{2}{3}}$に矛盾する.よって示された.

$k > n^\frac{2}{3}$のとき

$n \geq 900$のとき

$$\prod_{\substack{p \leq k \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \cdot \cdots \leq 4^{k+\sqrt{n}}$$
が成立する.

 命題8より
$$\prod_{\substack{p \leq N \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt{N} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{N} \\ p \in \P}}p \cdot \cdots \leq 4^N\tag{2}$$
が成立する.
 式(2)に$N = \lfloor \sqrt{n} \rfloor$を代入して
$$\prod_{\substack{p \leq \lfloor \sqrt{n} \rfloor \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \lfloor \sqrt[4]{n} \rfloor \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \lfloor \sqrt[6]{n} \rfloor \\ p \in \P}}p \cdot \cdots \leq 4^{\lfloor \sqrt{n} \rfloor}$$
となる.ここで,$p$が素数のとき$p \leq \lfloor \sqrt[2l]{n} \rfloor \iff p \leq \sqrt[2l]{n}$であり,$4^{\lfloor \sqrt{n} \rfloor} \leq 4^\sqrt{n}$だから
$$\prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[4]{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[6]{k} \\ p \in \P}}p \cdot \cdots \leq 4^\sqrt{n}\tag{3}$$
となる.
 また,$k>n^\frac{2}{3}$のとき,任意の$l \geq 2$に対して$\sqrt[l]{k} \geq \sqrt[2l-1]{n}$となるから,式(2)より
$$\prod_{\substack{p \leq k \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[5]{n} \\ p \in \P}}p \cdot \cdots \leq 4^k\tag{4}$$
となる.
 よって,式(3)と式(4)より
$$\prod_{\substack{p \leq k \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \cdot \cdots \leq 4^{k+\sqrt{n}}$$
が成立することが示された.

 式(2)に$k = \lfloor \sqrt{n} \rfloor$を代入する場面,Erdösの論文では「$k = \sqrt{n}$として~」となっていました….

 $n \geq 4k$のとき定理2は成立する.

背理法で示す.

 任意の正整数$k$に対して$\dbinom{2k}{k} \geq \dfrac{4^k}{2k}$が成立することが数学的帰納法により分かる.
 ここで,
$$\dbinom{n}{k} \geq \dbinom{4k}{k} = \dbinom{2k}{k} \frac{4k}{2k} \frac{4k-1}{2k-1} \cdots \frac{3k+1}{k+1} \geq \frac{4^k}{2k} \cdot 2^k = \frac{8^k}{2k}$$
と評価できる.
 さて,$\dbinom{n}{k}$の素因数が全て$k$以下であると仮定すると,命題9より
$$\dbinom{n}{k} \leq \prod_{\substack{p \leq k \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \cdot \cdots$$
が成立する.これと補題11より$\dbinom{n}{k} \leq 4^{k+\sqrt{n}}$が従うから,
$$\frac{8^k}{2k} \leq 4^{k+\sqrt{n}} \iff \frac{2^k}{2k} \leq 4^\sqrt{n}$$
となる.ここで,$k \geq 33$$2^{\frac{1}{3}k} > 2k$が従うから,$2^{\frac{2}{3}k} \geq 2^{2\sqrt{n}}$,つまり$k \geq 3\sqrt{n}$が成立する.一方,$k > n^\frac{2}{3}$であるから$n^\frac{2}{3} < 3\sqrt{n}$となる.
 しかし,これは$n \geq 900$では成立せず矛盾.よって示された.

 $\dfrac{5}{2}k < n < 4k$のとき定理2は成立する.

背理法で示す.

$$\binom{n}{k} \geq \binom{\left\lfloor \frac{5}{2}k \right\rfloor}{k} = \binom{2k}{k} \frac{\left\lfloor \frac{5}{2}k \right\rfloor}{2k} \frac{\left\lfloor \frac{5}{2}k \right\rfloor -1}{2k-1} \cdots \frac{\left\lfloor \frac{5}{2}k \right\rfloor -k+1}{k+1} \geq \frac{4^k}{2k} \left( \frac{5}{4} \right)^k$$
と評価できる.
一方,$\dbinom{n}{k}$の素因数が全て$k$以下であると仮定すると,命題12の証明と同様にして$\dbinom{n}{k} \leq 4^{k+\sqrt{n}}$が従う.これより
$$\frac{4^k}{2k} \left( \frac{5}{4} \right)^k \leq 4^{k+\sqrt{n}} \iff \left( \frac{5}{4} \right)^k \leq 2k \cdot 4^\sqrt{n}$$
となる.ここで,$n < 4k$より$\left( \dfrac{5}{4} \right)^k < 2k \cdot 4^\sqrt{4k}$となり,これは$k<205$で成立する.しかし,これは$n \geq 900$に矛盾する.よって示された.

 $2k \leq n \leq \dfrac{5}{2}k$のとき定理2は成立する.

背理法で示す.

$$\dbinom{n}{k} \geq \dbinom{2k}{k} \geq \frac{4^k}{2k}$$
と評価できる.
 ここで,素数$p \leq k$$\dbinom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$を割り切るとすると,$v_p(k! \, (n-k)!) \geq 2$より$v_p(n!) \geq 3$である必要がある.だから$p \leq \dfrac{1}{3}n$となる($p=2$のときも$n \geq 33$より従う).
 これより,$\dbinom{n}{k}$の素因数が全て$k$以下であると仮定すると,$\dbinom{n}{k}$の素因数は$\dfrac{1}{3}n$より大きな素因数をもたないから,命題9において$N = \left\lfloor \dfrac{1}{3}n \right\rfloor$とし,補題11も用いて
$$\dbinom{n}{k} \leq \prod_{\substack{p \leq \left\lfloor \frac{1}{3}n \right\rfloor \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \cdot \cdots = \prod_{\substack{p \leq \frac{1}{3}n \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \cdot \cdots < 4^{\frac{1}{3}n + \sqrt{n}} \leq 4^{\frac{5}{6}k + \sqrt{n}}$$
が成立する.これより
$$\frac{4^k}{2k} < 4^{\frac{5}{6}k + \sqrt{n}} \iff 4^{\frac{1}{6}k} < 2k \cdot 4^\sqrt{n}$$
となる.ここで,$2k \leq n < 4^\sqrt{n}$$k \geq \dfrac{2}{5}n$だから
$$4^{\frac{1}{15}n} < 4^{2\sqrt{n}} \iff n< 30\sqrt{n}$$
となるが,これは$n \geq 900$では成立せず矛盾.よって示された.

 これで$n \geq 900$のときが示せました.なお,Erdösの論文はここまでの議論と後で登場する命題16で終わっています(「残りは有限の領域なので調べられる」と述べて論文を締めていました).

$n < 900$のとき

 $n < 900$のとき定理1は成立する.

 今$k \geq 33$を仮定しているので,$66 \leq n < 900$について考えればよいが,この範囲に連続$33$数が合成数となる区間は存在しないので(これは素数表を見れば分かる),連続する$k$数を選べば常に素数が含まれる.よって示された.

 ここまでで$k \geq 33$のときは示し尽くしました.

$8 \leq k \leq 32$のとき

 $8 \leq k \leq \sqrt{n}$のとき定理2は成立する.

背理法で示す.

 $\dbinom{n}{k}$の素因数が全て$k$以下であると仮定する.
 $k \geq 8$のとき$\pi(k) \leq \dfrac{1}{2}k$だから,命題3より
$$\binom{n}{k} = \prod_{\substack{p\leq k \\ p \in \P}} p^{v_p{(\binom{n}{k})}} \leq \prod_{\substack{p\leq k \\ p \in \P}} n = n^{\pi(k)} \leq n^{\frac{1}{2}k}$$
となる.一方,
$$\binom{n}{k} = \frac{n}{k} \cdot \frac{n-1}{k-1} \cdot \cdots \cdot \frac{n-k+1}{1} > \left( \frac{n}{k} \right)^{k}$$
が成立する.これより
$$\left( \frac{n}{k} \right)^{k} < n^{\frac{1}{2}k} \iff n^{\frac{1}{2}k} < k^k$$
が従うが,これは$k \leq \sqrt{n}$に矛盾する.よって示された.

 $k > \sqrt{n}$のとき定理1は成立する.

 $k > \sqrt{n}$のとき,$n < k^2 \leq 32^2 = 1024$である.これと$n \geq 2k$より$16 \leq n <1024$について考えればよい.
 ここで,この範囲における素数または$37$以上の素因数をもつ整数の列を考えると,隣り合う$2$数の差が$8$以上になるものが存在しないことが分かる.よって示された.

$16 \leq n < 1024$における,素数または$37$以上の素因数をもつ整数の列

17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,74,79,82,83,86,89,94,97,101,103,106,107,109,111,113,118,122,123,127,129,131,134,137,139,141,142,146,148,149,151,157,158,159,163,164,166,167,172,173,177,178,179,181,183,185,188,191,193,194,197,199,201,202,205,206,211,212,213,214,215,218,219,222,223,226,227,229,233,235,236,237,239,241,244,246,249,251,254,257,258,259,262,263,265,267,268,269,271,274,277,278,281,282,283,284,287,291,292,293,295,296,298,301,302,303,305,307,309,311,313,314,316,317,318,321,326,327,328,329,331,332,333,334,335,337,339,344,346,347,349,353,354,355,356,358,359,362,365,366,367,369,370,371,373,376,379,381,382,383,386,387,388,389,393,394,395,397,398,401,402,404,407,409,410,411,412,413,415,417,419,421,422,423,424,426,427,428,430,431,433,436,438,439,443,444,445,446,447,449,451,452,453,454,457,458,461,463,466,467,469,470,471,472,473,474,477,478,479,481,482,485,487,488,489,491,492,497,498,499,501,502,503,505,508,509,511,514,515,516,517,518,519,521,523,524,526,530,531,533,534,535,536,537,538,541,542,543,545,547,548,549,553,554,555,556,557,559,562,563,564,565,566,568,569,571,573,574,577,579,581,582,583,584,586,587,590,591,592,593,596,597,599,601,602,603,604,606,607,610,611,613,614,615,617,618,619,622,623,626,628,629,631,632,633,634,635,636,639,641,642,643,645,647,649,652,653,654,655,656,657,658,659,661,662,664,666,668,669,670,671,673,674,677,678,679,681,683,685,687,688,689,691,692,694,695,697,698,699,701,703,705,706,707,708,709,710,711,712,716,717,718,719,721,723,724,727,730,731,732,733,734,737,738,739,740,742,743,745,746,747,749,751,752,753,755,757,758,761,762,763,764,766,767,769,771,772,773,774,776,777,778,779,781,785,786,787,788,789,790,791,793,794,795,796,797,799,801,802,803,804,807,808,809,811,813,814,815,817,818,820,821,822,823,824,826,827,829,830,831,834,835,838,839,842,843,844,846,848,849,851,852,853,854,856,857,859,860,861,862,863,865,866,869,871,872,873,876,877,878,879,881,883,885,886,887,888,889,890,892,893,894,895,898,901,902,903,904,905,906,907,908,909,911,913,914,915,916,917,919,921,922,923,925,926,927,929,932,933,934,937,938,939,940,941,942,943,944,946,947,948,949,951,953,954,955,956,958,959,962,963,964,965,967,970,971,973,974,976,977,978,979,981,982,983,984,985,987,989,991,993,994,995,996,997,998,999,1002,1003,1004,1005,1006,1007,1009,1010,1011,1013,1016,1017,1018,1019,1021,1022

 これで$8 \leq k \leq 32$のときが終わりました.

$1 \leq k \leq 7$のとき

 $1 \leq k \leq 5$のとき定理1は成立する.

それぞれの$k$に対して調べる.
  • $k=1$のときは自明に成立する.
  • $k=2$のとき
     $4$以上の正整数$n,n-1$のうちいずれか$1$つは$3$以上の奇数だから示された.
  • $k=3$のとき
     $6$以上の正整数$n$に対して$n,n-1,n-2$$2,3$以外の素因数をもたないと仮定する.
     $n$が奇数のとき,$n$$3^i$の形で表せる必要があるが,このとき,$n-2$$3$で割り切れない奇数となるので矛盾.
     $n$が偶数のとき,$n-1$は奇数だから$n-1$$3^i$の形で表せる必要がある.このとき,$n,n-2$$3$を素因数にもたないのでともに$2^i$の形で表せる必要があるが,これを満たす$n \geq 6$は存在しないので矛盾.よって示された.
  • $k=4$のとき
     $8$以上の正整数$n$に対して$n,n-1,n-2,n-3$$2,3$以外の素因数をもたないと仮定する.
     このとき,いずれか$2$つは奇数であり,それらは$3^i$の形で表せる必要があるが,ともに$3$の倍数になることはないので矛盾.よって示された.
  • $k=5$のとき
     $10$以上の正整数$n$に対して$n,n-1,n-2,n-3,n-4$$2,3,5$以外の素因数をもたないと仮定する.
     $n,n-2,n-4$が奇数のとき,この中で$3$の倍数と$5$の倍数はそれぞれ高々$1$つだから,いずれか$1$つは$3$の倍数でも$5$の倍数でもない奇数となる.これは矛盾.
     $n-1,n-3$が奇数のとき,一方は$3^i$の形で,もう一方は$5^i$の形で表される必要がある.このとき,$n,n-2,n-4$$3,5$を素因数にもたないので全て$2^i$の形で表せる必要があるが,このような$n$は存在せず矛盾.よって示された.

 $k=6,7$かつ$k \leq n^\frac{3}{7}$のとき定理2は成立する.

背理法で示す.

 $\dbinom{n}{k}$の素因数が全て$k$以下であると仮定する.
 $k =6,7$のとき$\pi(k) \leq \dfrac{4}{7}k$だから,命題3より
$$\binom{n}{k} = \prod_{\substack{p\leq k \\ p \in \P}} p^{v_p{(\binom{n}{k})}} \leq \prod_{\substack{p\leq k \\ p \in \P}} n = n^{\pi(k)} \leq n^{\frac{4}{7}k}$$
となる.一方,
$$\binom{n}{k} = \frac{n}{k} \cdot \frac{n-1}{k-1} \cdot \cdots \cdot \frac{n-k+1}{1} > \left( \frac{n}{k} \right)^{k}$$
が成立する.これより
$$\left( \frac{n}{k} \right)^{k} < n^{\frac{4}{7}k} \iff n^{\frac{3}{7}k} < k^k$$
が従うが,これは$k \leq \sqrt{n}$に矛盾する.よって示された.

 $k = 6,7$かつ$k> n^\frac{3}{7}$のとき定理1は成立する.

 $k > n^\frac{3}{7}$のとき,$n < k^\frac{7}{3} \leq 7^\frac{7}{3} < 94$である.これと$n \geq 2k$より$12 \leq n <94$について考えればよい.このとき,この範囲に連続$6$数が合成数となる区間は存在しないので(これも素数表を見れば分かる),連続する$k$数を選べば常に素数が含まれる.よって示された.

 これで証明終了です!

Sylvester-Schurの定理から従う主張

 Sylvester-Schurの定理を出発して様々な主張が得られます.この中からいくつかを紹介します.

Bertrand-Chebyshevの定理

 任意の自然数$n$に対して$n < p \leq 2n$を満たす素数$p$が存在する.

 定理1において$n = 2k$とし,$k$$n$に替えると,$2n,2n-1,\ldots,n+1$の中で$n$より大きな素因数$p$をもつものが存在することが分かる.これを$N$とする.
 ここで,$N \neq p$とすると,$N$$p$の倍数だから$N \geq 2p \geq 2(n+1)$となるが,これは$N$$2n,2n-1,\ldots,n+1$のうちのいずれかであることに矛盾する.つまり$N=p$.これは$n < p \leq 2n$を満たす素数$p$が存在することに他ならない.

 Sylvester-Schurの定理はBertrand-Chebyshevの定理の一般化であることが分かりました!

 連続する$n \,(\geq 2)$自然数の積は平方数にならない.

 証明は こちらのサイト に詳しく書かれています.この定理は以下の東大入試の問題の部分的な一般化になっています:

東京大学理系数学2012-4

 $n$$2$以上の整数とする.自然数($1$以上の整数)の$n$乗になる数を$n$乗数と呼ぶことにする.以下の問いに答えよ.

  1. 連続する$2$個の自然数の積は$n$乗数でないことを示せ.
  2. 連続する$n$個の自然数の積は$n$乗数でないことを示せ.

 正整数$k,l,m,n$に対し,方程式$\dbinom{n}{k} = m^l$$l \geq 2$$4 \leq k \leq n-4$のとき解をもたない.

 証明は省略します(M.アイグナー・G.M.ツィーグラー著『天書の証明』などにこの定理の証明が掲載されています).この3つの定理は全てErdösによって初等的な証明が与えられました.

おわりに

 ここまでSylvester-Schurの定理について色々と見てきました.シンプルな主張ながら様々な場面で用いることができ,私のお気に入りの定理のひとつです.今後も面白いと思った話題について記事を書いていきたいと思います(が,最近それなりに多忙なので気長にお待ちください>_<).
 さて,今月1日から始まった AMC2023 (Advent Math Calendar2023) も残すところあと2日となりました.明日(imabcさん)・明後日(W2TZMSさん)の記事もとても楽しみです!
 そして,皆さん素敵なクリスマスイブ&クリスマスをお過ごしください!

参考文献

投稿日:20231222

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

roofs
roofs
4
147

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中