[場所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 件のコメント:
コメントを投稿