シングマスター予想 (シングマスターよそう、) は、「パスカルの三角形において1以外の数字の出現回数には上限が存在する」という組み合わせ数学の予想である。名前の由来は1971年にこの予想を提唱したイギリスの数学者に由来する。
1より大きい任意の整数 について、この数はパスカルの三角形において上から 行までにしか出現しないため、1より大きい数の出現が有限であることは明らかである。シングマスター予想は、この出現回数がある有限の数を越えないことを主張している。
なお、1は明らかにパスカルの三角形において無限回出現し、上記の事実から1はパスカルの三角形で無限回出現する唯一の数である。
主張 整数 に対して、 をパスカルの三角形における の出現回数とする。 シングマスター予想の主張は、ある ( に依存しない) 有限の数 が存在して が成り立つことである。
ランダウのOを用いると、予想の主張は以下の通りになる。
既知の上限 パスカルの三角形における出現数 について、以下のことがすでに知られている。 すなわち、ある係数 が存在して、十分大きな について が成り立つ。
に対して、十分大きい を取る (このとき は に依存して取る)。このとき、 を満たす の組は、次の不等式で制限される範囲内には高々4個しか存在しない。 「 が十分大きいとき、 と の間に素数が存在する」というを仮定すると、任意の について
シングマスターの無限族
シングマスターは、 と に関するディオファントス方程式について、これが無限に多くの解を持つことを証明した。この方程式の解は、非負整数 を用いて次のように表される。ここで は 番目のフィボナッチ数 () である。
このとき、等しくなる両辺の値を とおくと、となり、パスカルの三角形に (少なくとも) 6回登場する数の族を得る。これをシングマスターの無限族と呼ぶ。
例
2 は1回だけ現れる。それより大きい整数は2回以上現れる。 3, 4, 5 はそれぞれ2回現れる。ちょうど2個現れる整数は無限にある。 全ての奇素数は2回現れる。 6 は3回現れる。3回現れる整数も無限個ある。 (pは、 を満たす素数)の形で表せる数は4回現れる。 以下の例のようにちょうど6回現れる数も無限にある。
3003は8回現れる最小かつ現在唯一知られている数である。3003はシングマスターの無限族によって求められる数でもある。シングマスターの無限族における次の数は である (OEIS: )。 Benjamin M. M. de Wegerは、上記の120、210、1540、7140、11628、24310およびシングマスターの無限族以外にパスカルの三角形で5回以上出現する数は存在しないと予想している。
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, ...
Abbott, Erdős, and Hanson (1974)は、 x 以下のパスカルの三角形に3回以上現れる整数の数は、O(x1/2)であることを示した。
未解決問題 9回以上現れる数、3003以外の8回現れる数が存在するかどうかは知られていない。上限は8と予想できるが、シングマスターは10または12と予想していた。
また、5回または7回現れる数が存在するかどうかも未解決である。関連する数列 において等式N(a) = 5 をみたす aがあるかどうかわからないことが言及されている。
脚注
脚注
出典
参考文献 . . . .
関連項目 二項係数 パスカルの三角形