シングマスター予想のソースを表示

{{unsolved|数学|1以外の任意の自然数について、パスカルの三角形に現れる回数がN未満となるような定数Nは存在するか？}}
'''シングマスター予想''' (シングマスターよそう、{{Lang-en-short|Singmaster's conjecture}}) は、「[[パスカルの三角形]]において1以外の数字の出現回数には上限が存在する」という[[組合せ数学|組み合わせ数学]]の[[数学上の未解決問題|予想]]である。名前の由来は1971年にこの予想を提唱したイギリスの数学者{{仮リンク|デヴィッド・シングマスター|en|David Singmaster}}に由来する。

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

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

== 主張 ==
整数 {{Math|''a'' > 1}} に対して、{{Math|''N''(''a'')}} をパスカルの三角形における {{Mvar|a}} の出現回数とする。 シングマスター予想の主張は、ある ({{Mvar|a}} に依存しない) 有限の数 {{Mvar|M}} が存在して {{Math|''N''(''a'') < ''M''}} が成り立つことである。

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

: <math>N(a) = O(1)</math>
== 既知の上限 ==
パスカルの三角形における出現数 {{Math|''N''(''a'')}} について、以下のことがすでに知られている。
* {{Harv|Singmaster|1971}} <math display="block">N(a) = O(\log a)</math>すなわち、ある係数 {{Mvar|K}} が存在して、十分大きな {{Mvar|a}} について <math display="inline">N(a)<K\log a</math> が成り立つ。
* {{Harv|Abbott|Erdős|Hanson|1974|loc=Theorem 3}}<math display="block">N(a) = O\left(\frac{\log a}{\log \log a}\right)</math>
*{{Harv|Kane|2007}}<math display="block">N(a) = O\left(\frac{(\log a)(\log \log \log a)}{(\log \log a)^3}\right)</math>
*{{Harv|Matomäki et al.|2022|loc=Theorem 1.3}} <math display="inline"> 0 < \varepsilon < 1 </math> に対して、十分大きい {{Mvar|a}} を取る (このとき {{Mvar|a}} は {{Mvar|ε}} に依存して取る)。このとき、<math display="inline">\tbinom{n}{m}=a</math> を満たす {{Math|(''n'', ''m'')}} の組は、次の不等式で制限される範囲内には高々4個しか存在しない。<math display="block">\exp \left(\log(n)^{\tfrac{2}{3}+\varepsilon} \right) \le m \le n - \exp \left(\log(n)^{\tfrac{2}{3}+\varepsilon} \right) </math>
*{{Harv|Abbott|Erdős|Hanson|1974|p=259}} 「{{Mvar|x}} が十分大きいとき、{{Mvar|x}} と {{Math|''x'' + (log ''x'')<sup>2</sup>}} の間に素数が存在する」という{{仮リンク|クラメールの予想|en|Cramér's conjecture}}を仮定すると、任意の <math display="inline">\varepsilon > 0 </math> について<math display="block"> N(a) = O\left( \log(a)^{\tfrac{2}{3}+\varepsilon}\right) </math>

==シングマスターの無限族==

シングマスターは、{{Mvar|n}} と {{Mvar|k}} に関する[[ディオファントス方程式]]<math display="block">{n+1 \choose k+1} = {n \choose k+2}</math>について、これが無限に多くの解を持つことを証明した。この方程式の解は、非負整数 {{Mvar|i}} を用いて次のように表される。<math display="block">\begin{align}
n &= F_{2i+2} F_{2i+3} - 1\\
k &= F_{2i}F_{2i+3}-1
\end{align}</math>ここで {{Math|''F''<sub>''j''</sub>}} は {{Mvar|j}} 番目の[[フィボナッチ数]] ({{Math|1=''F''<sub>0</sub> = 0, ''F''<sub>1</sub> = 1}}) である<ref>{{Harvtxt|Singmaster|1975}}</ref>。


このとき、等しくなる両辺の値を {{Mvar|a}} とおくと、<math display="block">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}</math>となり、パスカルの三角形に (少なくとも) 6回登場する数の族を得る。これをシングマスターの無限族と呼ぶ。

== 例 ==

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

* 3003は8回現れる最小かつ現在唯一知られている数である。<math display="block">3003 = {3003 \choose 1} = {78 \choose 2} = {15 \choose 5} = {14 \choose 6} = {14 \choose 8} = {15 \choose 10} = {78 \choose 76} = {3003 \choose 3002} </math>3003はシングマスターの無限族によって求められる数でもある。シングマスターの無限族における次の数は <math display="inline">a_3 = 61218182743304701891431482520</math> である ([[オンライン整数列大辞典|OEIS]]: {{OEIS2C|id=A090162}})。<math display="block">a_3 = {a_3 \choose 1} = {a_3 \choose a_3-1} = {104 \choose 39} = {104 \choose 65} = {103 \choose 40} = {103 \choose 63}</math>
* Benjamin　M. M. de Wegerは、上記の120、210、1540、7140、11628、24310およびシングマスターの無限族以外にパスカルの三角形で5回以上出現する数は存在しないと予想している<ref>{{Harvtxt|Matomäki et al.|2022}}</ref><ref>{{Cite journal|last=de Weger|first=Benjamin M. M.|date=1997-04-01|title=Equal Binomial Coefficients: Some Elementary Considerations|url=https://www.sciencedirect.com/science/article/pii/S0022314X97921090|journal=Journal of Number Theory|volume=63|issue=2|pages=373–386|language=en|doi=10.1006/jnth.1997.2109|issn=0022-314X}}</ref>{{Efn|正確には、すでに知られた形以外で異なる二項係数が一致することはないと主張している。従って予想が正しいならば、パスカルの三角形に出現する回数の最大値は8である。}}。

* ''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|id=A003016}}

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

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

また、5回または7回現れる数が存在するかどうかも未解決である。関連する数列 {{OEIS|id=A003015}} において等式''N''(''a'') = 5 をみたす&nbsp;''a''があるかどうかわからないことが言及されている。

== 脚注 ==
{{脚注ヘルプ}}

=== 脚注 ===
{{Notelist}}

=== 出典 ===
<references />

== 参考文献 ==
* {{citation|洋書|ref=harv|title=Research Problems: How often does an integer occur as a binomial coefficient?|last=Singmaster|first=D.|year=1971|journal=American Mathematical Monthly|volume=78|issue=4|pages=385–386|doi=10.2307/2316907|jstor=2316907|mr=1536288}}.
* {{citation|洋書|ref=harv|title=Repeated binomial coefficients and Fibonacci numbers|last=Singmaster|first=D.|year=1975|url=http://www.fq.math.ca/Scanned/13-4/singmaster.pdf|journal=Fibonacci Quarterly|volume=13|issue=4|pages=295–298|mr=0412095}}.
* {{citation|洋書|ref=harv|title=On the number of times an integer occurs as a binomial coefficient|last1=Abbott|first1=H. L.|last2=Erdős|first2=P.|author2-link=Paul Erdős|last3=Hanson|first3=D.|year=1974|journal=American Mathematical Monthly|volume=81|issue=3|pages=256–261|doi=10.2307/2319526|jstor=2319526|mr=0335283}}.
* {{citation|洋書|ref=harv|title=Improved bounds on the number of ways of expressing ''t''  as a binomial coefficient|last=Kane|first=Daniel M.|year=2007|url=http://www.emis.de/journals/INTEGERS/papers/h53/h53.pdf|journal=INTEGERS: The Electronic Journal of Combinatorial Number Theory|volume=7|number=A53|format=PDF|mr=2373115}}.
* {{Cite journal|last=Matomäki|first=Kaisa|last2=Radsiwiłł|first2=Maksym|last3=Shao|first3=Xuancheng|last4=Tao|first4=Terence|last5=Teräväinen|first5=Joni|year=2022|title=Singmaster's Conjecture in the Interior of Pascal's Triangle|journal=The Quarterly Journal of Mathematics|volume=73|issue=3|pages=1137–1177|accessdate=2023-03-21|ref={{Harvid|Matomäki et al.|2022}}|arxiv=2106.03335|doi=10.1093/qmath/haac006}}

== 関連項目 ==
* [[二項係数]]
* [[パスカルの三角形]]

{{DEFAULTSORT:しんくますたあよそう}}
[[Category:数学に関する記事]]
[[Category:予想]]
[[Category:数学のエポニム]]
[[Category:組合せ論]]