数学外書輪講I(第10回)

[場所1E501（月曜日5限）]

HPに行く

これは6/24の外書輪講に行われた授業に基づいています。

ベルトランの仮説の後半

ここ(リンク)においてベルトランの仮説の前半について書きました。

まず、ベルトランの仮説とは次のような定理のことを言います。

定理

任意の正の整数 $n$ に対して、$n<p\le 2n$

となる素数 $p$ が存在する。

この定理を証明をするための発想として、
もし$n<p\le 2n$ となるような素数 $p$ が存在しないとすると、
二項係数 $\binom{2n}{n}=\frac{(2n)!}{n!n!}$ の分子は、$n$ 以下の素数
しか現れないということになる。もしそのようなことが起これば
$n$ は十分に小さいことを証明できれば良い。

この定理の証明として、以下のようなステップで考えます。

Step 1

$n\le 511$ まででこの仮説が正しいことを証明する。

Step 2

$x\ge 2$ のときに、$\prod_{p\le x}p\le 4^{x-1}$ が成り立つことを示す。

ここで、$\prod_{p\le x}p$ は $x$ 以下の素数の全ての積

を表します。

Step 3

$\binom{2n}{n}$ を割り切る$2n$ 以下の素数 $p$ は、

$p>\sqrt{2n}$ を満たすなら、$p$ を割ることができる回数は

高々1回であり、$\frac{2}{3}n< p\le n$ を満たす素因数が現れない。

Step 4

$\binom{2n}{n}$ のある上からの評価をすること。

Step 5

定理の証明

前回の輪講までで、Step 2が終わりました。

Step 3の証明

ルジャンドルの定理から、

$\binom{2n}{n}$ を割り切る素数 $p$ の数はちょうど

$\sum_{k\ge 1}\left(\left\lfloor\frac{2n}{p^k}\right\rfloor-2\left\lfloor\frac{n}{p^k}\right\rfloor\right)$

と計算できます。

ここで、$\left\lfloor\frac{2n}{p^k}\right\rfloor-2\left\lfloor\frac{n}{p^k}\right\rfloor< \frac{2n}{p^k}-2(\frac{n}{p^k}-1)=2$

ですから、上の和の各項は高々1です。

また、$p^k>2n$ となる $k$ に対しては、各項は $0$ ですから、

$\sum_{k\ge 1}\left(\left\lfloor\frac{2n}{p^k}\right\rfloor-2\left\lfloor\frac{n}{p^k}\right\rfloor\right)\le\max\{r|p^r\le 2n\}$

となります。

特に、$p>\sqrt{2n}$ となるような素数 $p$ は $\max\{r|p^r\le 2n\}=1$ であるから、

$\sum_{k\ge 1}\left(\left\lfloor\frac{2n}{p^k}\right\rfloor-2\left\lfloor\frac{n}{p^k}\right\rfloor\right)\le 1$ となります。

つまり、そのような素数 $p$ が $\binom{2n}{n}$ の約数になるとすると、

その $p$ のべきは高々1ということになります。

さらに、エルデシュによりますと、$\frac{2}{3}n< p\le n$ となる素因数は、

$\binom{2n}{n}$ には決して現れません。

というのも、もしそのような素数が存在したら、

$n!$ の中にはそのような素因数はただ1つ現れ、

$3p\le 2n$ ですから $(2n)!$ の中には、ただ2つだけ現れます。

よって、$\binom{2n}{n}$ ではちょうど割り切れてしまって素因数として

現れないからです。

Step 4の証明

Step 3を使うと、

$$\frac{4^n}{2n}\le \binom{2n}{n}\le \prod_{p\le \sqrt{2n}}(2n)\cdot \prod_{\sqrt{2n}<p\le \frac{2}{3}n}p\cdot \prod_{n<p\le 2n}p$$

が成り立ちます。

ここで、$n<p\le 2n$ となる素数の個数を

$P(n)$としますと、最後の項は、$(2n)^{P(n)}$ より大きいので、

$$4^n\le (2n)^{\sqrt{2n}}\cdot 4^{\frac{2}{3}n}\cdot (2n)^{P(n)+1}$$

を満たします。

よって、整理することで、

$$4^{\frac{1}{3}n}<(2n)^{\sqrt{2n}+P(n)+1}$$

を満たします。

Step 5の証明

この不等式の $\log_2$ を取ると、

$$\frac{2n}{3}<(\sqrt{2n}+1+P(n))\log_2(2n)\Leftrightarrow \frac{2n}{\log_2(2n)}-\sqrt{2n}-1<P(n)$$

を満たします。

よって $\log_2(2n)$ が $n$が大きくなると、$\sqrt{2n}$ に比べて圧倒的に

大きくなることを示せば良いのです。

つまり、$\sqrt{2n}-1>3\log_2(2n)$ であることがわかれば、

$$P(n)>\frac{2n-1}{3\log_2(2n)}-(\sqrt{2n}+1)=(\sqrt{2n}+1)\left(\frac{\sqrt{2n}-1}{3\log_2(2n)}-1\right)$$

となるので、$P(n)$ は正の数となります．

よって、$f(x)=\sqrt{x}-1-3\log_2x$ とおくと、

$$f'(x)=\frac{1}{2\sqrt{x}}-\frac{3}{(\log 2) x}=\frac{(\log 2)\sqrt{x}-6}{(2\log 2)x}$$

を満たします．

よって、$x>\left(\frac{6}{\log 2}\right)^2$ の場合に、$f(x)$ は単調増加になり、

$x\ge 2^{10}$ であれば、$f(x)$ は単調増加であり、

$f(2^{10})=2^5-1-3\cdot 10=1>0$ であるから、

$f(x)$ は $f(x)>0$ となります。

よって、$n\ge 512$ であるときに、$\sqrt{2n}-1-3\log_2(2n)>0$ が成り立つこと

つまり、$P(n)>0$ がわかります．

よって、$n\ge 512$ のときに、$n<p\le 2n$ を満たす素数 $p$ が存在することが

わかりました。

同じサイズを持つ共通集合

マトウセクのMiniature 4をやりました。

この話も極値集合論です。

次の定理を示してもらいました。

定理

$C_1,\cdots, C_m$ を互いに異なる空ではない $n$ 点集合の部分集合とする。

この時、$i\neq j$ なら $C_i\cap C_j$ が同じサイズの集合であるとき、

$n\ge m$ を満たす。

証明

まずは、条件から、$i\neq j$ のとき、$|C_i\cap C_j|=t$ であるとします。

ある $C_i$ のサイズが $t$ であるとします。

簡単のため、$i=1$ としておきます。

このとき、$j\neq 1$ のとき、$C_1\cap C_j\subset C_1$ であり、

これらはサイズが同じ集合であるから、

$C_1\cap C_j=C_1$ となります。

つまり、$C_1\subset C_j$ であることがわかります。

よって、$D_j:=C_j\setminus C_1$ と定義すると、

$D_j$ は重複のない相異なる $n$ 点集合の

部分集合となります。

つまり、$|D_1\sqcup D_2\sqcup\cdots \sqcup D_m|\le n$ ですから、

そのような $m$ はせいぜい $n$ 以下で抑えられます。

つまり、$m\le n$ となります。

次に、任意の $C_i$ に対して、$|C_i|>t$ であるとします。

このとき、

$m\times n$ 行列 $A=(a_{ij})$ を

$$a_{ij}=\begin{cases}1&j\in C_i\\0&otherwise.\end{cases}$$

と定義すると、

$B=AA^T$ はの $(i,i)$ 成分はちょうど $|C_{i}|=d_i$ であり、

$(i,j)$ 成分は $C_i\cap C_j|=t$ であることがわかります。

つまり、この行列は、

$$B=\begin{pmatrix}d_1&t&\cdots&\cdots&t\\t&d_2&t&\cdots&t\\\cdots&\cdots&\cdots&\cdots&\cdots\\t&\cdots&\cdots&t&d_m \end{pmatrix}$$

となります。

よって、この行列は正則になります。

この行列が正定値であることを示せれば良いです。

$B=tJ+\begin{pmatrix}d_1-t&0&\cdots&\cdots&0\\0&d_2-t&0&\cdots&0\\\cdots&\cdots&\cdots&\cdots&\cdots\\0&\cdots&\cdots&0&d_m-t \end{pmatrix}$ とおいておきます。ここで、$J$ は全ての成分が $1$ の行列です。

最後の対角行列を $D$ とおきます。

${\bf v}\in {\mathbb R}^m$ を ${\bf v}=(v_1,v_2\cdots, v_m)^t$ とします。

${\bf v}^tB{\bf v}={\bf v}^ttJ{\bf v}+{\bf v}^tD{\bf v}$ であり、

${\bf v}^tD{\bf v}=\sum_{i=1}^m(d_i-t)v_i^2>0$ です。

また、${\bf v}^ttJ{\bf v}=t(v_1+v_2+\cdots+v_m)^2\ge 0$ となります。

よって、${\bf v}^tB{\bf v}>0$ であることがわかったので、

$B$ は正定値行列であることがわかりました。

特に$B$は正則であり、$\text{rank}(B)=m$ となります。

一方、$B=AA^t$ であり、$\text{rank}(A)\le \min\{n,m\}$ ですから、

$m=\text{rank}(B)\le \text{rank}(A)\le \min\{n,m\}\le n$ ですから、

この場合も、$m\le n$ であることが言えます．