[場所1E501（月曜日5限）]
HPに行く
定理
$\ell\ge 2$ かつ $4\le k\le n-4$ である場合に
$\binom{n}{k}=m^\ell$ に解がない。
を証明していました。
$2k\le n$ であることを仮定できます。
前回までに、
(1) $n\ge k^\ell\ge k^2$ であることと、
また、$n-j=a_jm^\ell_j$ のように、$\ell$ 乗とそれ以外と
分けて考えると、
(2) $i\neq j$ であれば、$a_i\neq a_j$ である。
までわかりました。
次に、(3) に入ります。
(3) は次の命題です。
$a_0,\cdots, a_{k-1}$ は、$1,2,\cdots, k$ の並び替えである。
エルデシュいわく、この部分が、証明の「核心」「真髄」と言っています。
確かに、この部分で大分進んだ気がしますね。
$a_0,a_1,\cdots, a_{k-1}$ が $k!$ を割ることを示せばよいです。
もし、そうなら、$k!=L\cdot a_0\cdots a_{k-1}\ge L\cdot 1\cdot 2\cdots k=Lk!$
であり、$L=1$ となります。
$$n(n-1)(n-2)\cdots (n-k+1)=a_0a_1a_2 \cdots a_{k-1}m_0^\ell m_{1}^{\ell}m_2^\ell\cdots m_{k-1}^{\ell}$$
$$=a_0a_1a_2 \cdots a_{k-1}(m_1 m_2\cdots m_{k-1})^{\ell}=m^\ell k!$$
$m_0m_1\cdots m_{k-1}$ と $m$ の公約数をわることで、
$u,v$ となるとする。つまり、$\gcd(u,v)=1$ であるとします。
あとは、$v=1$ であることを示せばよいです。
今 $v$ に素因数が存在するとして、それを $p$ とします。
ここで、ルジャンドルの定理から、$k!$ の中の 素因数 $p$ は、$\sum_{i\ge 1}\lfloor\frac{k}{p^i}\rfloor$ の分だけかけられています。
一方、$n,n-1,\cdots, n-k+1$ の間の $p^i$ の倍数が $s$ 個あるとして、
それを、$b_1<b_2<\dots<b_s$ であるとすると、
$b_s-b_1=(s-1)p^i$ であり、
$(s-1)p^i=b_s-b_1\le n-(n-k+1)=k-1$ であるから、
$s\le \frac{k-1}{p^i}+1<\frac{s}{p^i}+1$
よって、$s\le \lfloor\frac{k}{p^i}\rfloor+1$ です。
$n,n-1,\cdots, n-k+1$ の中の、$p^i$ の倍数の数の総数が、
$n(n-1)\cdots (n-k+1)$ の中の素因数 $p$ の含まれる数であり、それは、
$\sum_{i=1}^{\ell-1}\left(\lfloor\frac{k}{p^i}\rfloor+1\right)$ によって上から評価されます。
よって、
$u^\ell$ の中には、せいぜい、
$\sum_{i=1}^{\ell-1}\left(\lfloor\frac{k}{p^i}\rfloor+1\right)-\sum_{i\ge 1}\lfloor\frac{k}{p^i}\rfloor$
だけの $p$ が含まれており、
$$\sum_{i=1}^{\ell-1}\left(\left\lfloor\frac{k}{p^i}\right\rfloor+1\right)-\sum_{i\ge 1}\left\lfloor\frac{k}{p^i}\right\rfloor\le \ell-1$$
であることがわかります。
つまり、
$$n(n-1)\cdots (n-k+1)u^\ell/k!=v^\ell$$
の左辺には、$p$ は $\ell$ 個も含まれていないのだから、
右辺が $v^\ell$ であることに反します。
よって、$v$ には素因数 $p$ は含まれていない。
つまり、$v=1$ であることがわかります。
(4) は、定理の証明を完成させます。
$\ell=2$ であるとします。
このとき、$a_0,a_1,a_2,\cdots a_{k-1}$ の中に、$4$ は含まれます。
しかし、$a_0,\cdots, a_{k-1}$ は 2乗因子は含まれないはずだから矛盾します。
よって、そのようなことはありません。
つまり、$\ell\ge 3$ を仮定してよいことになります。
今、$a_{i_1}=1,a_{i_2}=2,a_{i_3}=4$ を仮定して、
$n-i_1=a_{i_1}m_{i_1}^\ell$ かつ $n-i_2=a_{i_2}m_{i_2}^\ell$ かつ $n-i_3=a_{i_3}m_{i_3}^\ell$ を満たします。
今、$(n-i_2)^2\neq (n-i_1)(n-i_3)$ を示しましょう。
もし、そうでないとすると、$(n-i_2)^2= (n-i_1)(n-i_3)$ が成り立ちます。
$b=n-i_2$ とし、$n-i_1=b-x$ と $b_{i_3}=b+y$ とすると、
$1\le |x|,|y|\le k-1$ であり、
$b^2=(b-x)(b+y)$ がなりたつから、$(y-x)b=xy$ となります。
ここで、
$$|xy|=b|y-x|\ge b>n-k>(k-1)^2\ge |xy|$$
となり矛盾します。
よって、$(n-i_2)^2\neq (n-i_1)(n-i_3)$ が成り立ちます。
つまり、 $m_{i_2}^{2}\neq m_{i_1}m_{i_3}$ が成り立ちます。
いま、$m_{i_2}^2>m_{i_1}m_{i_3}$ であると仮定しましょう。
そうすると、
$$2(k-1)n>n^2-(n-k+1)^2>(n-i_2)^2-(n-i_1)(n-i_{3})$$
$$=4(m_{i_2}^{2\ell}-(m_{i_1}m_{i_3})^\ell)\ge 4((m_{i_1}m_{i_3}+1)^{\ell}-(m_{i_1}m_{i_3})^\ell]$$
$$\ge 4\ell m_{i_1}^{\ell-1}m_{i_3}^{\ell-1}$$
となり、$\ell\ge 3$ かつ $n>k^\ell\ge k^3>6k$ であることから、
$$2(k-1)nm_{i_1}m_{i_3}>4\ell m_{i_1}^{\ell}m_{i_3}^{\ell}=\ell(n-i_1)(n-{i_3})$$
$$>(n-k+1)^2>3(n-\frac{n}{6})^2>2n^2$$
よって、
$$n<(k-1)m_{i_1}m_{i_3}$$
が成り立ちます。
$m_{i_j}^\ell\le n$ であるから、
$m_{i_j}\le n^{\frac{1}{\ell}}\le n^{\frac{1}{3}}$ となります。
よって、
$n<kn^{\frac{2}{3}}$ であることから、
$n^3<kn^2$ より、$n<k$ が成り立つ。
これは、$k<n-4$ であることに反します。
よって、$m_{i_1}^2>m_{i_1}m_{i_3}$ であることが成り立ちません。
同じように、$m_{i_1}^2<m_{i_1}m_{i_3}$ も成り立ちません。
定理
$\ell\ge 2$ かつ $4\le k\le n-4$ である場合に
$\binom{n}{k}=m^\ell$ に解がない。
を証明していました。
$2k\le n$ であることを仮定できます。
前回までに、
(1) $n\ge k^\ell\ge k^2$ であることと、
また、$n-j=a_jm^\ell_j$ のように、$\ell$ 乗とそれ以外と
分けて考えると、
(2) $i\neq j$ であれば、$a_i\neq a_j$ である。
までわかりました。
次に、(3) に入ります。
(3) は次の命題です。
$a_0,\cdots, a_{k-1}$ は、$1,2,\cdots, k$ の並び替えである。
確かに、この部分で大分進んだ気がしますね。
$a_0,a_1,\cdots, a_{k-1}$ が $k!$ を割ることを示せばよいです。
もし、そうなら、$k!=L\cdot a_0\cdots a_{k-1}\ge L\cdot 1\cdot 2\cdots k=Lk!$
であり、$L=1$ となります。
$$n(n-1)(n-2)\cdots (n-k+1)=a_0a_1a_2 \cdots a_{k-1}m_0^\ell m_{1}^{\ell}m_2^\ell\cdots m_{k-1}^{\ell}$$
$$=a_0a_1a_2 \cdots a_{k-1}(m_1 m_2\cdots m_{k-1})^{\ell}=m^\ell k!$$
$m_0m_1\cdots m_{k-1}$ と $m$ の公約数をわることで、
$u,v$ となるとする。つまり、$\gcd(u,v)=1$ であるとします。
あとは、$v=1$ であることを示せばよいです。
今 $v$ に素因数が存在するとして、それを $p$ とします。
ここで、ルジャンドルの定理から、$k!$ の中の 素因数 $p$ は、$\sum_{i\ge 1}\lfloor\frac{k}{p^i}\rfloor$ の分だけかけられています。
一方、$n,n-1,\cdots, n-k+1$ の間の $p^i$ の倍数が $s$ 個あるとして、
それを、$b_1<b_2<\dots<b_s$ であるとすると、
$b_s-b_1=(s-1)p^i$ であり、
$(s-1)p^i=b_s-b_1\le n-(n-k+1)=k-1$ であるから、
$s\le \frac{k-1}{p^i}+1<\frac{s}{p^i}+1$
よって、$s\le \lfloor\frac{k}{p^i}\rfloor+1$ です。
$n,n-1,\cdots, n-k+1$ の中の、$p^i$ の倍数の数の総数が、
$n(n-1)\cdots (n-k+1)$ の中の素因数 $p$ の含まれる数であり、それは、
$\sum_{i=1}^{\ell-1}\left(\lfloor\frac{k}{p^i}\rfloor+1\right)$ によって上から評価されます。
よって、
$u^\ell$ の中には、せいぜい、
$\sum_{i=1}^{\ell-1}\left(\lfloor\frac{k}{p^i}\rfloor+1\right)-\sum_{i\ge 1}\lfloor\frac{k}{p^i}\rfloor$
だけの $p$ が含まれており、
$$\sum_{i=1}^{\ell-1}\left(\left\lfloor\frac{k}{p^i}\right\rfloor+1\right)-\sum_{i\ge 1}\left\lfloor\frac{k}{p^i}\right\rfloor\le \ell-1$$
であることがわかります。
つまり、
$$n(n-1)\cdots (n-k+1)u^\ell/k!=v^\ell$$
の左辺には、$p$ は $\ell$ 個も含まれていないのだから、
右辺が $v^\ell$ であることに反します。
よって、$v$ には素因数 $p$ は含まれていない。
つまり、$v=1$ であることがわかります。
(4) は、定理の証明を完成させます。
$\ell=2$ であるとします。
このとき、$a_0,a_1,a_2,\cdots a_{k-1}$ の中に、$4$ は含まれます。
しかし、$a_0,\cdots, a_{k-1}$ は 2乗因子は含まれないはずだから矛盾します。
よって、そのようなことはありません。
つまり、$\ell\ge 3$ を仮定してよいことになります。
今、$a_{i_1}=1,a_{i_2}=2,a_{i_3}=4$ を仮定して、
$n-i_1=a_{i_1}m_{i_1}^\ell$ かつ $n-i_2=a_{i_2}m_{i_2}^\ell$ かつ $n-i_3=a_{i_3}m_{i_3}^\ell$ を満たします。
今、$(n-i_2)^2\neq (n-i_1)(n-i_3)$ を示しましょう。
もし、そうでないとすると、$(n-i_2)^2= (n-i_1)(n-i_3)$ が成り立ちます。
$b=n-i_2$ とし、$n-i_1=b-x$ と $b_{i_3}=b+y$ とすると、
$1\le |x|,|y|\le k-1$ であり、
$b^2=(b-x)(b+y)$ がなりたつから、$(y-x)b=xy$ となります。
ここで、
$$|xy|=b|y-x|\ge b>n-k>(k-1)^2\ge |xy|$$
となり矛盾します。
よって、$(n-i_2)^2\neq (n-i_1)(n-i_3)$ が成り立ちます。
つまり、 $m_{i_2}^{2}\neq m_{i_1}m_{i_3}$ が成り立ちます。
いま、$m_{i_2}^2>m_{i_1}m_{i_3}$ であると仮定しましょう。
そうすると、
$$2(k-1)n>n^2-(n-k+1)^2>(n-i_2)^2-(n-i_1)(n-i_{3})$$
$$=4(m_{i_2}^{2\ell}-(m_{i_1}m_{i_3})^\ell)\ge 4((m_{i_1}m_{i_3}+1)^{\ell}-(m_{i_1}m_{i_3})^\ell]$$
$$\ge 4\ell m_{i_1}^{\ell-1}m_{i_3}^{\ell-1}$$
となり、$\ell\ge 3$ かつ $n>k^\ell\ge k^3>6k$ であることから、
$$2(k-1)nm_{i_1}m_{i_3}>4\ell m_{i_1}^{\ell}m_{i_3}^{\ell}=\ell(n-i_1)(n-{i_3})$$
$$>(n-k+1)^2>3(n-\frac{n}{6})^2>2n^2$$
よって、
$$n<(k-1)m_{i_1}m_{i_3}$$
が成り立ちます。
$m_{i_j}^\ell\le n$ であるから、
$m_{i_j}\le n^{\frac{1}{\ell}}\le n^{\frac{1}{3}}$ となります。
よって、
$n<kn^{\frac{2}{3}}$ であることから、
$n^3<kn^2$ より、$n<k$ が成り立つ。
これは、$k<n-4$ であることに反します。
よって、$m_{i_1}^2>m_{i_1}m_{i_3}$ であることが成り立ちません。
同じように、$m_{i_1}^2<m_{i_1}m_{i_3}$ も成り立ちません。
0 件のコメント:
コメントを投稿