整数論における中央二項係数の研究
整数論における中央二項係数の研究
皆様ごきげんよう。
初めに言っておきます。
今回は、いつものような解法や原理のまとめ記事ではありません。
以前、私が取り組んでいた研究を改めて整理し、その後の考察も加えてまとめたものです。
（ただ、今後の私の作問に生かされるかもしれません）
それでは、改めまして。
今回は、中央二項係数の素因数について考えてみます。
出発点は、「素因数が二種類以下となるのはいつか」という整数問題です。
その問題を解く途中で、中央二項係数そのものを素因数分解する代わりに、近くにある整数から素因数を取り出す方法が現れます。最初は$2n-3$に着目していた議論を、一般の$2n-l$へ、さらに複数の整数へと広げていきましょう。
中心となるのは、どの整数から、どの条件によって、中央二項係数の素因数が現れるのかという見方です。最後には、共通素因数を持たない例外の判定や、共通する約数の大きさまで考えます。
以下、$n$は正の整数とし、
$$
C_n={}_{2n}C_n=\frac{(2n)!}{(n!)^2}
$$
と書きます。$a\mid b$は「$a$が$b$を割り切る」、$\gcd(a,b)$は最大公約数を表します。
目次
1 出発点となった整数問題
2 一般の2n−lから素因数を取り出す
3 固定したずれには、例外が有限個しかない
4 複数の整数から相異なる素因数を取り出す
5 互いに素な整数そのものを構成する
6 素因数の個数への応用
7 共通する約数と、最適な補正係数
8 例外を正確に判定する
9 既知の結果との関係
1 出発点となった整数問題
正の整数$i,j,n$と素数$p,q$について、
$$
{}_{2n}C_n=p^i q^j
$$
を満たす組をすべて求めよ。$p,q$は相異なるとは限らないものとする。
まず、
$$
C_n=2\,{}_{2n-1}C_{n-1}
$$
より、$2\mid C_n$です。さらに$n\geq2$では、
$$
(n-1)\,{}_{2n-1}C_{n-1}
=(2n-1)\,{}_{2n-2}C_{n-2}
$$
が成り立ち、$\gcd(2n-1,n-1)=1$なので、
$$
2n-1\mid C_n
$$
も分かります。
したがって、$C_n$の素因数が二種類以下なら、$2n-1>1$の素因数は一種類の奇素数に限られます。その素数を$q$としましょう。
ここで、もう一つの奇数$2n-3$に着目します。
$$
\gcd(2n-1,2n-3)=1
$$
なので、$2n-3$の素因数は$q$とは異なります。もちろん奇数なので$2$でもありません。つまり、仮定の下では、$2n-3$と$C_n$は共通の素因数を持ってはいけないわけです。
この条件に矛盾することを示したい。ただ、$2n-3$の素因数を一つずつ調べるのは難しそうです。
そこで、調べる対象を変えます。「どの素数が現れるか」をすべて決める必要はありません。少なくとも一つ、$C_n$にも現れる素数を見つければ十分です。
指数全体ではなく、一項を見る
素数$p$に対し、正の整数$m$の素因数分解に現れる$p$の指数を$v_p(m)$と書きます。例えば、$v_3(72)=2$です。
ルジャンドルの公式は、
$$
v_p(m!)=\sum_{k=1}^{\infty}\left\lfloor\frac{m}{p^k}\right\rfloor
$$
という式です。$\lfloor x\rfloor$は、$x$以下の最大の整数を表します。階乗の中にある$p$の倍数、$p^2$の倍数、……を順に数えることで、この式が得られます。実際に非零となる項は有限個です。
中央二項係数に適用すると、
$$
v_p(C_n)
=\sum_{k=1}^{\infty}
\left(
\left\lfloor\frac{2n}{p^k}\right\rfloor
-2\left\lfloor\frac{n}{p^k}\right\rfloor
\right).
$$
ここで、
$$
\delta_{p,k}(n)
=\left\lfloor\frac{2n}{p^k}\right\rfloor
-2\left\lfloor\frac{n}{p^k}\right\rfloor
$$
とおきます。$n/p^k=u+\theta$、$u$は整数、$0\leq\theta<1$と書けば、
$$
\delta_{p,k}(n)=\lfloor2\theta\rfloor\in\{0,1\}.
$$
したがって、指数を全部計算しなくても、ある一つの$k$について$\delta_{p,k}(n)=1$を示せば、$p\mid C_n$が分かるのです。
2n−3の場合
$n\geq4$なら、$2n-3$は$3$より大きい奇数です。その素因数分解の中には、$3$より大きい素数冪$p^a$が必ずあります。
実際、すべての素数に対応する最大の素数冪が$3$以下なら、使えるのは$3^1$だけなので、$2n-3$は$1$か$3$になってしまいます。
そこで、$p^a\mid2n-3$、$p^a>3$となるものを取り、
$$
2n-3=p^a(2t+1)
$$
と書きます。商は正の奇数なので、$t\geq0$です。すると
$$
2n=p^a(2t+1)+3
$$
であり、$0<3< p^a$から
$$
\left\lfloor\frac{2n}{p^a}\right\rfloor=2t+1,
\qquad
\left\lfloor\frac{n}{p^a}\right\rfloor=t.
$$
よって$\delta_{p,a}(n)=1$、したがって$p\mid C_n$です。
これで、$2n-3$の素因数のうち少なくとも一つが、$C_n$にも現れると分かりました。先ほどの「現れてはいけない」という条件に矛盾します。したがって、$n\geq4$では$C_n$は少なくとも三種類の素因数を持ちます。
残りは
$$
C_1=2,\qquad C_2=6,\qquad C_3=20
$$
です。$i,j\geq1$なので$p^i q^j\geq4$であり、$n=1$は元の等式を満たしません。答えは、$(i,j,n,p,q)$の順に
$$
\boxed{
\begin{gathered}
(1,1,2,2,3),\quad(1,1,2,3,2),\\
(2,1,3,2,5),\quad(1,2,3,5,2)
\end{gathered}
}
$$
となります。
なお、「素因数が二種類以下となる$n$」という問いなら、答えは$n=1,2,3$です。元の等式では指数を正としたため、$n=1$が除かれます。
2 一般の2n−lから素因数を取り出す
今の計算では、$3$であることよりも、「正の奇数で、選んだ素数冪より小さい」ことが働いていました。そこで、$3$を一般の奇数へ置き換えます。
$l$を正の奇数とし、$X=2n-l>0$とする。ある奇素数$p$と正の整数$a$について、
$$
p^a\mid X,\qquad p^a>l
$$
が成り立つならば、$p\mid C_n$である。
$Q=p^a$とおく。$X$と$Q$は奇数なので、$X=Q(2t+1)$と書ける。$t\geq0$であり、
$$
2n=Q(2t+1)+l,\qquad
n=Qt+\frac{Q+l}{2}.
$$
$0< l< Q$より、$0<(Q+l)/2< Q$である。よって
$$
\left\lfloor\frac{2n}{Q}\right\rfloor=2t+1,
\qquad
\left\lfloor\frac{n}{Q}\right\rfloor=t.
$$
したがって$\delta_{p,a}(n)=1$となり、ルジャンドルの公式から$v_p(C_n)\geq1$を得る。
条件は$p>l$ではなく、$p^a>l$です。例えば$n=6,l=3$なら、$2n-l=9$から$3^2>3$を使えます。実際、${}_{12}C_6=924$は$3$の倍数です。
また、$a$を$v_p(X)$に一致させる必要もありません。条件を満たす素数冪を一つ見つければ十分です。
3 固定したずれには、例外が有限個しかない
次は、witnessで使う素数冪の存在を保証しましょう。
正の奇数$u$について、
$$
M(u)=\operatorname{lcm}(1,3,5,\ldots,u)
$$
と定めます。$\operatorname{lcm}$は最小公倍数です。特に$M(1)=1$です。
正の奇数$X$が$X>M(u)$を満たすなら、ある奇素数$p$について
$$
p^{v_p(X)}>u
$$
が成り立つ。
反対に、すべての素因数$p$について$p^{v_p(X)}\leq u$と仮定する。それぞれの素数冪は、$u$以下の正の奇数なので$M(u)$を割り切る。
異なる素数に対応する素数冪は互いに素であるため、その積である$X$も$M(u)$を割り切る。これは$X>M(u)$に矛盾する。
正の奇数$l$を固定する。
$$
2n-l>M(l)
$$
を満たすすべての正の整数$n$について、
$$
\gcd(2n-l,C_n)>1
$$
が成り立つ。
large-powerを$X=2n-l$、$u=l$に適用し、得られた素数冪にwitnessを適用すればよい。
ここでは$l$を固定しています。したがって、条件は$n$の一定の下界を与え、結論は十分大きいすべての$n$に対して成り立ちます。
一方、$\gcd(2n-l,C_n)=1$なら、witnessの対偶から、$2n-l$の各素数に対応する最大の素数冪は$l$以下です。したがって、
$$
2n-l\mid M(l)
$$
が必要です。例外の候補は有限個に絞れます。
ただし、これは十分条件ではありません。候補の中から本当の例外を判定する方法は、
第8節
で扱います。
4 複数の整数から相異なる素因数を取り出す
一つの整数から素因数を取り出せるなら、複数の整数でも同じことをしたくなります。ただし、各整数から取り出した素数が同じものになっては、個数を増やせません。
そこで、今度は素数冪の大きさを、整数同士の差とも比べます。
相異なる正の奇数$l_1,\ldots,l_r$を固定し、$L=\max_i l_i$とする。
$$
2n>M(L)+L
$$
ならば、それぞれの$X_i=2n-l_i$から、相異なる奇素数$p_1,\ldots,p_r$を選び、
$$
p_i\mid X_i,\qquad p_i\mid C_n
$$
を同時に満たすことができる。
すべての$i$について$X_i>M(L)$なので、large-powerにより
$$
p_i^{a_i}\mid X_i,\qquad p_i^{a_i}>L
$$
となる奇素数$p_i$と正の整数$a_i$を選べる。$L\geq l_i$より、witnessから$p_i\mid C_n$である。
もし$i\ne j$で$p_i=p_j=p$なら、
$$
p^{\min(a_i,a_j)}\mid X_i-X_j=l_j-l_i.
$$
ところが、
$$
0<|l_j-l_i|< L< p^{\min(a_i,a_j)}
$$
なので不可能である。よって、選んだ素数は相異なる。
特に、$l_i=2i-1$とすれば、連続する奇数
$$
2n-1,\ 2n-3,\ \ldots,\ 2n-(2r-1)
$$
のそれぞれから、相異なる素因数を取り出せます。必要な条件は
$$
2n>M(2r-1)+(2r-1)
$$
です。
ここで、$X_i$同士が互いに素である必要はありません。例えば$r=4,n=59$では、
$$
X_1=117,\quad X_2=115,\quad X_3=113,\quad X_4=111
$$
から$13,23,113,37$を取り出せますが、$\gcd(X_1,X_4)=3$です。一般の証明で排除したのは、整数同士の共通素因数すべてではなく、選んだ大きい素数冪に対応する素数の重複でした。
素数一つよりも多くの情報を残す
同じ考え方を少し丁寧に使うと、各$X_i$の一部が丸ごと$C_n$を割り切ることが分かります。
相異なる正の奇数$l_1,\ldots,l_r$について、$L=\max_i l_i$、$2n>L$とする。
$$
Y_i=\frac{2n-l_i}{\gcd(2n-l_i,M(L))}
$$
とおけば、
$$
Y_i\mid C_n,\qquad
\gcd(Y_i,Y_j)=1\quad(i\ne j).
$$
したがって、
$$
\prod_{i=1}^{r}Y_i\mid C_n.
$$
奇素数$p$に対し、$b=v_p(M(L))$、$e_i=v_p(2n-l_i)$とおく。$b$は$p^b\leq L$を満たす最大の非負整数である。
$b< k\leq e_i$なら、$p^k\mid2n-l_i$かつ$p^k>L\geq l_i$なので、witnessの証明から$\delta_{p,k}(n)=1$である。よって
$$
v_p(C_n)\geq\max(0,e_i-b)=v_p(Y_i).
$$
$Y_i$は奇数なので、すべての素因数についてこの不等式を使えば$Y_i\mid C_n$を得る。
また、ある$p$が$Y_i,Y_j$をともに割るなら、$p^{b+1}$が$2n-l_i,2n-l_j$をともに割る。すると、$L$より大きい$p^{b+1}$が、絶対値$L$未満の非零整数$l_j-l_i$を割ることになり、矛盾する。
最後の積の整除性は、$Y_i$同士が互いに素であることから従う。
さらに$2n>M(L)+L$なら、すべての$Y_i$が$1$より大きくなります。各$Y_i$から一つずつ素因数を選ぶことでも、simultaneousが得られます。
5 互いに素な整数そのものを構成する
前節では、元の整数同士の最大公約数は問いませんでした。別の方向として、
$$
\gcd(2n-l_i,2n-l_j)=1
$$
を同時に実現する構成も考えてみましょう。
中国剰余定理による構成
まず、以前考えていた構成を整理します。
互いに素な整数$a,b$について、ある整数$u,v$が存在して$au+bv=1$となることをベズーの等式といいます。これは合同式の逆数を作るために使えます。
また、中国剰余定理は、法が互いに素なら、それぞれの法で指定した余りを同時に実現でき、解が法の積を周期として並ぶという定理です。$x\equiv y\pmod m$は、$m\mid x-y$を表します。
$r$以下の奇素数すべての積を$K'$とし、該当する素数がなければ$K'=1$とします。
$$
l_i=1+2iK'\qquad(1\leq i\leq r)
$$
とおき、相異なる素数$s_i>l_r$を選びます。中国剰余定理によって
$$
2n\equiv0\pmod{K'},\qquad
2n\equiv l_i\pmod{s_i}
\quad(1\leq i\leq r)
$$
を同時に満たす$n$を作れます。法はすべて奇数で互いに素なので、$2$を逆数によって取り除いて中国剰余定理を適用できます。$K'=1$の条件は何も制限しません。
十分大きい正の解を取れば、$X_i=2n-l_i>0$です。また、
$$
s_i\mid X_i,\qquad s_i>l_i
$$
なので、witnessから$s_i\mid C_n$が得られます。
さらに、$X_i\equiv-1\pmod{K'}$、$X_i-X_j=2K'(j-i)$です。共通の奇素因数$p$があれば、$p\nmid K'$かつ$p\mid j-i$となります。しかし$|j-i|\leq r-1$なので、$p$は$K'$に含まれるはずです。矛盾して、$X_i$同士は互いに素となります。
この構成は、取り出す素数を先に指定できることが長所です。ただし、作られる$n$は一つの等差数列に属します。したがって、ここから直接言えるのは「そのような$n$が無限に存在する」ことです。「十分大きいすべての$n$」についての結論には、別の議論が必要です。
ずれを有限個の範囲で動かす
次の構成では、$n$に応じて$l_i$を選びます。その代わり、$l_i$を$r$だけで決まる範囲に抑えます。
正の整数$r$を固定する。$r-1$以下の奇素数すべての積を$K$とし、該当する素数がなければ$K=1$とする。
$$
L_r=2rK-1
$$
とおく。任意の$n$に対して、
$$
t\equiv2n-1\pmod K,\qquad 1\leq t<2K
$$
を満たす奇数$t$を選び、
$$
l_i=t+2(i-1)K\qquad(1\leq i\leq r)
$$
と定める。
このとき$t$は一意に存在し、$l_i$は相異なる正の奇数で、$l_i\leq L_r$である。$2n>L_r$なら、$X_i=2n-l_i$は正で、互いに素となる。
さらに、
$$
2n>M(L_r)+L_r
$$
なら、各$X_i$には$p_i^{a_i}>l_i$となる素数冪因子が存在する。これらの$p_i$は相異なる奇素数で、すべて$C_n$を割り切る。
$K$は奇数である。$1,3,\ldots,2K-1$は、法$K$ですべて異なる余りを持つ。
実際、この範囲の二つの奇数の差が$K$の倍数なら、その差は偶数でもあるので$2K$の倍数である。しかし絶対値は$2K$未満なので、差は$0$となる。候補は$K$個あるため、すべての余りを一度ずつ実現し、$t$の存在と一意性が従う。
$l_i$は正の奇数で、間隔$2K$の等差数列である。また、
$$
l_i\leq(2K-1)+2(r-1)K=L_r.
$$
したがって$2n>L_r$なら、すべての$X_i$が正である。
次に、
$$
X_i\equiv1\pmod K,\qquad
X_i-X_j=2K(j-i)
$$
を使う。$i\ne j$で共通の素因数$p$があるとする。$X_i$は奇数なので$p$も奇数であり、$X_i\equiv1\pmod K$から$p\nmid K$である。
よって$p\mid j-i$となるが、$1\leq|j-i|\leq r-1$より、$p$は$K$の定義に含まれる奇素数である。これは$p\nmid K$に矛盾する。
最後に、$2n>M(L_r)+L_r$なら、すべての$i$について$X_i>M(L_r)$である。large-powerにより$p_i^{a_i}>L_r\geq l_i$となる素数冪を取り出せる。witnessから$p_i\mid C_n$であり、$X_i$同士が互いに素なので$p_i$は相異なる。
$K=1$のときは$t=1$です。特に$r=1,2,3$では$K=1$となり、$l_i=2i-1$です。$r=1$のとき、互いに素という条件は比較する相手がないので自動的に満たされます。
この定理の量化は、「どの十分大きい$n$に対しても、適切な$l_i$を選べる」です。$l_i$は$n$に依存しますが、上界$L_r$と$n$の十分条件は$r$だけに依存します。
前節との違いも整理しておきましょう。simultaneousでは、ずれを固定したまま、取り出す素数の相異性を保証しました。coprime-constructionでは、ずれを動かして、元の整数同士まで互いに素にしています。
6 素因数の個数への応用
正の整数$m$の相異なる素因数の個数を$\omega(m)$と書きます。例えば、$\omega(72)=2$、$\omega(1)=0$です。
任意の正の整数$r$について、
$$
2n>M(2r-1)+(2r-1)
$$
ならば、
$$
\omega(C_n)\geq r+1.
$$
したがって、
$$
\lim_{n\to\infty}\omega({}_{2n}C_n)=\infty.
$$
simultaneousに$l_i=2i-1$を適用すれば、$r$個の相異なる奇素因数を得る。さらに$2\mid C_n$なので、合計で$r+1$種類以上となる。
任意の整数$R\geq1$に対して$r=R$を選べば、ある$N_R$が存在して、すべての$n\geq N_R$で$\omega(C_n)\geq R+1$となる。これが上の極限の意味である。
この証明から得られる十分条件を、いくつか並べます。
| 取り出す奇素数の個数$r$ | $M(2r-1)$ | $n$の十分条件 | 結論 |
|---|---|---|---|
| $1$ | $1$ | $n\geq2$ | $\omega(C_n)\geq2$ |
| $2$ | $3$ | $n\geq4$ | $\omega(C_n)\geq3$ |
| $3$ | $15$ | $n\geq11$ | $\omega(C_n)\geq4$ |
| $4$ | $105$ | $n\geq57$ | $\omega(C_n)\geq5$ |
これらは保証のための境界であり、常に最小の境界を与えるわけではありません。
また、正の整数$m$を固定したとき、$\omega(C_n)\leq m$なら、
$$
2n\leq M(2m-1)+(2m-1).
$$
したがって、素因数の個数が一定以下となる$n$は有限個です。出発点の問題は、その$m=2$の場合に当たります。
素因数の個数が発散するという事実は、以前の
中央二項係数に関する記事
でも、係数の大きさを比較する別の方法で扱いました。その方法からは、自然対数を$\log$として、
$$
\omega(C_n)\geq
\frac{n\log4-\log(2n+1)}{\log(2n)}
$$
という下界が得られます。
今回の構成は、個数そのものの評価としては粗い十分条件を与えます。同時に、$2n-1,2n-3,\ldots$のどこから素因数を取り出せるかを示しています。個数の評価と、素因数が現れる場所の情報とは、役割が異なります。
7 共通する約数と、最適な補正係数
ここからは、固定した$l$についての議論をもう少し進めます。
大きさの条件は、どこまで弱められるか
witnessでは$p^a>l$を使いました。この条件は十分条件として扱いやすいものですが、素因数の出現に必要な条件ではありません。
実際、$Q=p^a\mid2n-l$とし、$2n-l=Q(2t+1)$と書くと、
$$
\begin{aligned}
\delta_{p,a}(n)
&=2t+1+\left\lfloor\frac lQ\right\rfloor
-2\left\lfloor\frac{2t+1+l/Q}{2}\right\rfloor.
\end{aligned}
$$
$u=\lfloor l/Q\rfloor$とおけば、右辺は$2t+1+u$の偶奇で決まり、
$$
\boxed{
\delta_{p,a}(n)=1
\iff
\left\lfloor\frac{l}{p^a}\right\rfloor
\text{が偶数}
}
$$
となります。$p^a>l$の場合は、この整数が$0$なのでした。
例えば$n=5,l=7$では、$2n-l=3$、$\lfloor7/3\rfloor=2$です。$3<7$ですが、この一項だけで$3\mid{}_{10}C_5$が分かります。
ただし、この同値は選んだ一項が$1$となる条件です。$p\mid C_n$そのものの必要十分条件ではありません。他の指数の項が$1$となることもあるからです。
取り除くべき部分を正確に数える
前節のdivisor-productでは、$M(l)$に含まれる部分を除くことで、共通する約数を取り出しました。固定した$l$だけを考えるなら、さらに小さい一定の整数を使えます。
正の整数$m$について、
$$
\operatorname{odd}(m)=\frac{m}{2^{v_2(m)}}
$$
と書き、これを$m$の奇数部分と呼びます。$l=2s+1$、$s\geq0$に対して、
$$
H_l=\operatorname{odd}\left(l\,{}_{2s}C_s\right)
$$
と定めます。ここでは${}_{0}C_0=1$とします。
正の奇数$l$を固定し、$X=2n-l>0$とする。このとき、
$$
\boxed{\frac{X}{\gcd(X,H_l)}\mid C_n}
$$
が成り立つ。特に、
$$
\gcd(X,C_n)\geq\frac{X}{H_l}.
$$
さらに、正の整数$A$が、すべての$2n-l>0$となる正の整数$n$について
$$
2n-l\mid A C_n
$$
を満たすならば、$H_l\mid A$である。逆に$A=H_l$はこの条件を満たす。
奇素数$p$について、$h_p=v_p(H_l)$とおく。$l=2s+1$なので、
$$
l\,{}_{2s}C_s=\frac{l!}{(s!)^2}.
$$
ルジャンドルの公式から、
$$
h_p
=\sum_{k=1}^{\infty}
\left(
\left\lfloor\frac l{p^k}\right\rfloor
-2\left\lfloor\frac s{p^k}\right\rfloor
\right).
$$
ここで$\lfloor s/p^k\rfloor=\lfloor l/(2p^k)\rfloor$だから、各項は$\lfloor l/p^k\rfloor$が奇数なら$1$、偶数なら$0$である。つまり、
$$
h_p=\#\left\{k\geq1:
\left\lfloor\frac l{p^k}\right\rfloor
\text{が奇数}\right\}.
$$
$\#$は集合の要素数を表す。
$e=v_p(X)$とする。$1\leq k\leq e$については、先ほどの計算により、$\delta_{p,k}(n)=0$となるのは$\lfloor l/p^k\rfloor$が奇数のときに限る。零となる項は高々$h_p$個なので、
$$
v_p(C_n)\geq\max(0,e-h_p).
$$
右辺は$X/\gcd(X,H_l)$に含まれる$p$の指数である。$X$は奇数なので、すべての奇素数について比べれば最初の整除性を得る。
この約数は$X$も割り切るため、
$$
\gcd(X,C_n)\geq\frac{X}{\gcd(X,H_l)}
\geq\frac{X}{H_l}.
$$
また、$X/\gcd(X,H_l)\mid C_n$は$X\mid H_lC_n$を意味するので、$A=H_l$は条件を満たす。
最後に最適性を示す。$p\mid H_l$を一つ固定し、$p^e>l$となる正の整数$e$を選んで、
$$
n=\frac{p^e+l}{2}
$$
とおく。これは正の整数であり、$X=p^e$である。$2n=p^e+l<2p^e< p^{e+1}$なので、$k>e$の項はすべて零となる。
一方、$h_p$を数える非零項はすべて$k\leq e$に含まれる。したがって、
$$
v_p(C_n)=e-h_p.
$$
$X\mid AC_n$なら、$e\leq v_p(A)+e-h_p$、すなわち$v_p(A)\geq h_p$である。これを$H_l$のすべての素因数について使えば、$H_l\mid A$となる。
例えば、最初のいくつかは次の通りです。
| $l$ | $H_l$ | $M(l)$ |
|---|---|---|
| $1$ | $1$ | $1$ |
| $3$ | $3$ | $3$ |
| $5$ | $15$ | $15$ |
| $7$ | $35$ | $105$ |
| $9$ | $315$ | $315$ |
| $11$ | $693$ | $3465$ |
一般にも$H_l\mid M(l)$です。実際、$h_p$は$p^k\leq l$となる指数の個数以下なので、$v_p(M(l))$を超えません。
特に、固定した$l$については、
$$
\gcd(2n-l,C_n)\longrightarrow\infty
\qquad(n\to\infty)
$$
まで分かります。共通素因数が存在するだけでなく、共通する約数の大きさが$(2n-l)/H_l$以上となるのです。
ここでの「最適」は、すべての$n$に対して$2n-l\mid AC_n$を成立させる、$n$に依存しない整数$A$の意味です。個々の$n$での最大公約数を、この式が正確に与えるという意味ではありません。
8 例外を正確に判定する
optimal-correctionにより、
$$
\gcd(2n-l,C_n)=1
\quad\Longrightarrow\quad
2n-l\mid H_l
$$
です。候補は$M(l)$の約数よりも少なくなりました。
残る問題は、その候補が本当に例外かどうかです。これには、素数で割り切れない条件を使います。
$p$を奇素数とし、$n$を$p$進法で
$$
n=d_0+d_1p+\cdots+d_mp^m,
\qquad 0\leq d_j< p
$$
と表す。このとき、
$$
p\nmid C_n
\iff
d_j\leq\frac{p-1}{2}
\quad\text{がすべての桁で成り立つ}.
$$
$R_k$を$n$を$p^k$で割った余りとする。$n=up^k+R_k$と書けば、
$$
\delta_{p,k}(n)=\left\lfloor\frac{2R_k}{p^k}\right\rfloor.
$$
すべての桁が$(p-1)/2$以下なら、
$$
R_k\leq\frac{p-1}{2}(1+p+\cdots+p^{k-1})
=\frac{p^k-1}{2}.
$$
よって、すべての$\delta_{p,k}(n)$が零となり、$p\nmid C_n$である。
逆に、ある桁$d_j\geq(p+1)/2$なら、
$$
R_{j+1}\geq d_jp^j>\frac{p^{j+1}}2
$$
なので、$\delta_{p,j+1}(n)=1$となる。したがって$p\mid C_n$である。
これは、$p$進法で$n+n$を計算したときに繰り上がりがない条件です。二項係数の素因数の指数を繰り上がりの個数で表すクンマーの定理の、中央二項係数の場合に当たります。ここでは必要な部分を床関数から直接証明しました。
正の奇数$l$を固定する。$2n-l>0$の範囲で
$$
\gcd(2n-l,C_n)=1
$$
となる$n$は、次の手順で、漏れなく重複なく得られる。
- $H_l$の正の約数$d$を一つ選ぶ。
- $n=(d+l)/2$とおく。
- $d$のすべての素因数$p$について、$n$の$p$進法の各桁が$(p-1)/2$以下となるものだけを残す。
$d=1$では最後の条件は自動的に満たされる。
例外ならoptimal-correctionによって$d=2n-l$は$H_l$の約数である。また、$d$のどの素因数も$C_n$を割らないため、digit-testの条件を満たす。
逆に、この手順で残した$d$については、digit-testから、$d$のすべての素因数が$C_n$を割らない。よって$\gcd(d,C_n)=1$である。
$d,l$はともに正の奇数なので、$n=(d+l)/2$は正の整数であり、$2n-l=d>0$となる。異なる$d$は異なる$n$を与える。
この判定による例外の全リストを、最初のいくつかについて示します。
| $l$ | $\gcd(2n-l,C_n)=1$となる$n$のすべて |
|---|---|
| $1$ | $1$ |
| $3$ | $2,3$ |
| $5$ | $3,4,5,10$ |
| $7$ | $4,6,7$ |
| $9$ | $5,7,8,9,12,27$ |
| $11$ | $6,9,10,11,121$ |
たとえば、$l=7,n=21$では$2n-l=35$が$H_7=35$を割り切ります。しかし、これは例外ではありません。
実際、$p=5$について、
$$
\delta_{5,1}(21)=8-2\cdot4=0,
\qquad
\delta_{5,2}(21)=1-2\cdot0=1.
$$
したがって$5\mid C_{21}$です。$5^2$は$35$を割り切りませんが、その指数に対応する項が素因数を生んでいます。
この例からも、$2n-l\mid H_l$は候補を絞る必要条件であり、十分条件ではないと分かります。また、$2n-l$を割る素数冪に対応する項だけを調べて、素因数が現れないと結論することもできません。
9 既知の結果との関係
二項係数の素因数を床関数や繰り上がりで調べることは、ルジャンドルの公式とクンマーの定理に基づく古典的な方法です。
Granvilleの解説
には、これらの定理を含む二項係数の整数論的な背景がまとめられています。
digit-testの桁の条件も既知です。Erdős・Graham・Ruzsa・Strausの論文「On the Prime Factors of ${}_{2n}C_n$」では、この条件を使い、中央二項係数に現れる小さい素数について研究しています。
また、近接する整数から異なる素因数を取り出す問題は、連続整数の素因数に関する研究ともつながります。Erdős・Selfridgeの1971年の論文では、区間の長さより大きい素数冪は、区間内の二つの整数を同時には割れないという議論が使われています。前節までの相異性の証明にも、同じ基本原理が現れました。
ただし、今回扱ったのは、固定した奇数のずれ$l_i$に対し、$2n-l_i$から中央二項係数を割る素数を取り出す問題です。連続整数から相異なる素数を割り当てる一般の問題とは、仮定も結論も区別する必要があります。
素因数の個数については、今回の発散の結論より詳しい漸近評価も知られています。例えばXylourisの論文は、二項係数の素因数の個数を素数の分布と関連づけて調べています。本記事ではその理論に依存せず、素因数の取り出し方を明示することを優先しました。
固定したずれの集合に対する構成や、optimal-correctionの形の最適な補正係数については、既存文献における同一の定式化を確認できていません。これは新規性の証明ではないため、本記事では新発見とは断定しません。
最初の問題では、$2n-3$の素因数が「現れてはいけない」ところから出発しました。その条件に対し、指数全体を求める代わりに、ルジャンドルの公式の一項を$1$にすることで、素因数の存在を保証しました。
その後の一般化も、この一項を作ることが中心です。大きい素数冪の存在には最小公倍数を使い、複数の素数の相異性には整数同士の差を使いました。さらに、ずれを動かせば互いに素な整数を構成でき、零となる項を数えれば共通する約数や例外の判定まで進めます。
中央二項係数の素因数を調べる際に、「何個あるか」に加えて、「どこから取り出せるか」という視点が、一つの手掛かりになれば幸いです。
ここまでお読みくださり、ありがとうございました。
皆さんの日常に良き数学の彩のあらんことを。それでは、ごきげんよう。
参考文献
- bloom, みそすーぷ模試大問2模範解答&解説 , Mathlog. 中央二項係数の素因数の個数に関する、係数の大きさを比較する証明。
- Andrew Granville, Arithmetic Properties of Binomial Coefficients . 特に Introduction のクンマーの定理。
- P. Erdős, R. L. Graham, I. Z. Ruzsa, E. G. Straus, On the Prime Factors of ${}_{2n}C_n$ , Mathematics of Computation 29 (1975), 83–92. 桁による判定は84頁のFact。
- P. Erdős, J. L. Selfridge, Some problems on the prime factors of consecutive integers II , Proceedings of the Washington State University Conference on Number Theory (1971), 13–21. 関連する素数冪の議論はTheorem 3の証明。
- Triantafyllos Xylouris, Binomial Coefficients and the Distribution of the Primes , arXiv:0709.4676 (2007). 素因数の個数の漸近評価はTheorem 2。
