シングマスター予想

テンプレート:Unsolved シングマスター予想 (シングマスターよそう、テンプレート:Lang-en-short) は、「パスカルの三角形において1以外の数字の出現回数には上限が存在する」という組み合わせ数学の予想である。名前の由来は1971年にこの予想を提唱したイギリスの数学者テンプレート:仮リンクに由来する。

1より大きい任意の整数テンプレート:Mvar について、この数はパスカルの三角形において上からテンプレート:Math 行までにしか出現しないため、1より大きい数の出現が有限であることは明らかである。シングマスター予想は、この出現回数がある有限の数を越えないことを主張している。

なお、1は明らかにパスカルの三角形において無限回出現し、上記の事実から1はパスカルの三角形で無限回出現する唯一の数である。

主張

整数テンプレート:Math に対して、テンプレート:Math をパスカルの三角形におけるテンプレート:Mvar の出現回数とする。シングマスター予想の主張は、ある (テンプレート:Mvar に依存しない) 有限の数テンプレート:Mvar が存在してテンプレート:Math が成り立つことである。

ランダウのOを用いると、予想の主張は以下の通りになる。

N (a) = O (1)

既知の上限

パスカルの三角形における出現数テンプレート:Math について、以下のことがすでに知られている。

テンプレート:Harv $N (a) = O (\log a)$ すなわち、ある係数テンプレート:Mvar が存在して、十分大きなテンプレート:Mvar について $N (a) < K \log a$ が成り立つ。
テンプレート:Harv $N (a) = O (\frac{\log a}{\log \log a})$
テンプレート:Harv $N (a) = O (\frac{(\log a) (\log \log \log a)}{(\log \log a)^{3}})$
テンプレート:Harv $0 < ε < 1$ に対して、十分大きいテンプレート:Mvar を取る (このときテンプレート:Mvar はテンプレート:Mvar に依存して取る)。このとき、 $(\binom{n}{m}) = a$ を満たすテンプレート:Math の組は、次の不等式で制限される範囲内には高々4個しか存在しない。 $\exp (\log (n)^{\frac{2}{3} + ε}) \leq m \leq n - \exp (\log (n)^{\frac{2}{3} + ε})$
テンプレート:Harv 「テンプレート:Mvar が十分大きいとき、テンプレート:Mvar とテンプレート:Math の間に素数が存在する」というテンプレート:仮リンクを仮定すると、任意の $ε > 0$ について $N (a) = O (\log (a)^{\frac{2}{3} + ε})$

シングマスターの無限族

シングマスターは、テンプレート:Mvar とテンプレート:Mvar に関するディオファントス方程式 $(\binom{n + 1}{k + 1}) = (\binom{n}{k + 2})$ について、これが無限に多くの解を持つことを証明した。この方程式の解は、非負整数テンプレート:Mvar を用いて次のように表される。 $\begin{matrix} n & = F_{2 i + 2} F_{2 i + 3} - 1 \\ k & = F_{2 i} F_{2 i + 3} - 1 \end{matrix}$ ここでテンプレート:Math はテンプレート:Mvar 番目のフィボナッチ数 (テンプレート:Math) である^[1]。

このとき、等しくなる両辺の値をテンプレート:Mvar とおくと、 $a = (\binom{a}{1}) = (\binom{n + 1}{k + 1}) = (\binom{n}{k + 2}) = (\binom{n}{n - k - 2}) = (\binom{n + 1}{n - k}) = (\binom{a}{a - 1})$ となり、パスカルの三角形に (少なくとも) 6回登場する数の族を得る。これをシングマスターの無限族と呼ぶ。

例

2 は1回だけ現れる。それより大きい整数は2回以上現れる。
3, 4, 5 はそれぞれ2回現れる。ちょうど2個現れる整数は無限にある。
全ての奇素数は2回現れる。
6 は3回現れる。3回現れる整数も無限個ある。
$(\binom{p}{2})$ (pは、 $p > 3$ を満たす素数)の形で表せる数は4回現れる。
以下の例のようにちょうど6回現れる数も無限にある。 $120 = (\binom{120}{1}) = (\binom{120}{119}) = (\binom{16}{2}) = (\binom{16}{14}) = (\binom{10}{3}) = (\binom{10}{7})$ $210 = (\binom{210}{1}) = (\binom{210}{209}) = (\binom{21}{2}) = (\binom{21}{19}) = (\binom{10}{4}) = (\binom{10}{6})$ $1540 = (\binom{1540}{1}) = (\binom{1540}{1539}) = (\binom{56}{2}) = (\binom{56}{54}) = (\binom{22}{3}) = (\binom{22}{19})$ $7140 = (\binom{7140}{1}) = (\binom{7140}{7139}) = (\binom{120}{2}) = (\binom{120}{118}) = (\binom{36}{3}) = (\binom{36}{33})$ $11628 = (\binom{11628}{1}) = (\binom{11628}{11627}) = (\binom{153}{2}) = (\binom{153}{151}) = (\binom{19}{5}) = (\binom{19}{14})$ $24310 = (\binom{24310}{1}) = (\binom{24310}{24309}) = (\binom{221}{2}) = (\binom{221}{219}) = (\binom{17}{8}) = (\binom{17}{9})$

3003は8回現れる最小かつ現在唯一知られている数である。 $3003 = (\binom{3003}{1}) = (\binom{78}{2}) = (\binom{15}{5}) = (\binom{14}{6}) = (\binom{14}{8}) = (\binom{15}{10}) = (\binom{78}{76}) = (\binom{3003}{3002})$ 3003はシングマスターの無限族によって求められる数でもある。シングマスターの無限族における次の数は $a_{3} = 61218182743304701891431482520$ である (OEIS: テンプレート:OEIS2C)。 $a_{3} = (\binom{a_{3}}{1}) = (\binom{a_{3}}{a_{3} - 1}) = (\binom{104}{39}) = (\binom{104}{65}) = (\binom{103}{40}) = (\binom{103}{63})$
Benjamin　M. M. de Wegerは、上記の120、210、1540、7140、11628、24310およびシングマスターの無限族以外にパスカルの三角形で5回以上出現する数は存在しないと予想している^[2]^[3]テンプレート:Efn。

n がパスカルの三角形に現れる回数は、

∞, 1, 2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 2, 4, 2, 2, 2, 2, 3, 4, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 2, 2, 2, 2, 2, 4, 2, 2, ... テンプレート:OEIS

Abbott, Erdős, and Hanson (1974)は、 x 以下のパスカルの三角形に3回以上現れる整数の数は、O(x^1/2)であることを示した。

未解決問題

9回以上現れる数、3003以外の8回現れる数が存在するかどうかは知られていない。上限は8と予想できるが、シングマスターは10または12と予想していた。

また、5回または7回現れる数が存在するかどうかも未解決である。関連する数列テンプレート:OEIS において等式N(a) = 5 をみたす aがあるかどうかわからないことが言及されている。

シングマスター予想

目次

主張

既知の上限

シングマスターの無限族

例

未解決問題

脚注

脚注

出典

参考文献

関連項目

ナビゲーションメニュー

シングマスター予想

主張

既知の上限

シングマスターの無限族

例

未解決問題

脚注

脚注

出典

参考文献

関連項目

ナビゲーション メニュー

検索

ナビゲーションメニュー