INTEGERS

予想 (Feit-Thompson, 1962) $p, q$ を相異なる素数とする。このとき、 $\displaystyle \frac{p^q-1}{p-1}$ は $\displaystyle \frac{q^p-1}{q-1}$ を割り切ることはない。

この予想はFeit-Thompsonの定理の文脈で、もし正しければその証明を簡略化できるだろうという形で提起されました。より強く $\displaystyle \frac{p^q-1}{p-1}$ と $\displaystyle \frac{q^p-1}{q-1}$ は互いに素であるかという主張も考えられますが(これがFeit-Thompson予想と呼ばれることもある)、

N. Stephens, On the Feit–Thompson conjecture, Math. Comp., 25 (1971), 625.

において、こちらは否定されています。実際、 $p=17$ , $q=3313$ とすると、

$\begin{align} \frac{3313^{17}-1}{3313-1} &= 210704631469613851903863028967414811023076458348545820561 \\ &=112643\times 23946003637421\times 78115430278873040084455537747447422887\end{align}$

ですが、 $4076$ 桁の数 $\displaystyle \frac{17^{3313}-1}{17-1}$ も $112643$ で割り切れます。

アルゴリズム

まず、正整数の逆数を並べます。

$\displaystyle 1 \quad \frac{1}{2} \quad \frac{1}{3} \quad \frac{1}{4} \quad \frac{1}{5} \quad \frac{1}{6} \quad \frac{1}{7} \quad \frac{1}{8} \quad \frac{1}{9} \quad \frac{1}{10} \quad \frac{1}{11} \quad \frac{1}{12} \quad \frac{1}{13} \quad \cdots$

その後、ある計算規則に基づいて一行ずつ下に数列を追加していきます。その計算規則は

f:id:integers:20180611024202p:plain:w200

新しい数列の左から数えて $N$ 番目の数が $C$ で、 $C$ の上にある数が $A, B$ のとき、

$C=N(A-B)$

と計算されます。

この計算規則に基づいて得られる数列の一部分を見てみましょう：

例えば、

の部分は

$\displaystyle \frac{5}{84}=6\left(\frac{3}{28}-\frac{7}{72}\right)$

と計算されています。

さて、こうして得られた計算結果の一番左端に注目してみましょう。

なんと、関-Bernoulli数になっています！！

integers.hatenablog.com

これが、秋山・谷川アルゴリズムです。

証明(by 金子先生)

数列 $\{b_{n,k}\}_{n, k\geq 0}$ を $b_{0, k}=\frac{1}{k+1}$ および漸化式

$b_{n+1,k}=(k+1)(b_{n,k}-b_{n,k+1})$

で定義するとき、 $b_{n,0}=B_n$ を示せばよい( $B_n$ は関-Bernoulli数)。 $\displaystyle f_n(t):=\sum_{k=0}^{\infty}b_{n,k}t^k$ と母関数を作ると、漸化式より $n\geq 1$ のとき

$\begin{align}f_n(t) &= \sum_{k=0}^{\infty}(k+1)(b_{n-1,k}-b_{n-1,k+1})t^k\\ &=\frac{\mathrm{d}}{\mathrm{d}t}\left(\sum_{k=0}^{\infty}b_{n-1,k}t^{k+1}\right)-\frac{\mathrm{d}}{\mathrm{d}t}\left(\sum_{k=0}^{\infty}b_{n-1,k+1}t^{k+1}\right)\\ &=\frac{\mathrm{d}}{\mathrm{d}t}\left(tf_{n-1}(t)\right)-\frac{\mathrm{d}}{\mathrm{d}t}\left(f_{n-1}(t)-b_{n-1,0}\right)\\ &=\frac{\mathrm{d}}{\mathrm{d}t}\left( (t-1)f_{n-1}(t)\right)\end{align}$

が成り立つので、 $g_n(t):=(t-1)f_n(t)$ とおけば

$\displaystyle g_n(t)=(t-1)\frac{\mathrm{d}}{\mathrm{d}t}(g_{n-1}(t) )$

であり、

$\displaystyle g_n(t)=\left( (t-1)\frac{\mathrm{d}}{\mathrm{d}t}\right)^ng_{0}(t)$

を得る。Bell数の母関数表示と第二種Stirling数 - INTEGERSの補題１の第二種Stirling数に関する

$\displaystyle \left(x\frac{\mathrm{d}}{\mathrm{d}x}\right)^n=\sum_{k=0}^n\left\{ {n \atop k}\right\}x^k\left(\frac{\mathrm{d}}{\mathrm{d}x}\right)^k$

という公式があるので、 $x\mapsto t-1$ と変数変換して利用すれば

$\displaystyle g_n(t) = \sum_{k=0}^n\left\{ {n\atop k}\right\}(t-1)^k\left(\frac{\mathrm{d}}{\mathrm{d}t}\right)^kg_0(t)$

なる等式を得る。右辺の微分を実行して $t=0$ を代入して $-1$ 倍すると、

$\begin{align} b_{n,0}&=-\sum_{k=0}^n\left\{ {n\atop k}\right\}(-1)^kk!(b_{0,k-1}-b_{0,k})\\ &=\sum_{k=0}^n(-1)^kk!\left( (k+1)\left\{ {n \atop k+1}\right\}+\left\{ {n\atop k}\right\}\right)b_{0,k} \\ &=\sum_{k=0}^n(-1)^kk!\left\{ {n+1\atop k}\right\}b_{0,k}\\ &=\sum_{k=0}^n\frac{(-1)^kk!\left\{ {n+1 \atop k+1} \right\}}{k+1}\end{align}$

が得られた。これは関-ベルヌーイ数の第二種Stirling数を用いた公式 - INTEGERSの(5)式より関-Bernoulli数に等しい。 Q.E.D.

最近、秋山・谷川アルゴリズムの広範な一般化が川﨑・大野によって得られています。

INTEGERS

数、特に整数に関する記事。

Feit-Thompson予想

James IvoryとEulerの定理

秋山・谷川アルゴリズム

アルゴリズム

証明(by 金子先生)