シングマスターの推測

数学における未解決問題

パスカルの三角形の各要素 (1 を除く) がN回未満しか出現しないような定数N は存在しますか?

数学におけるさらなる未解決問題

シングマスター予想は、組合せ論的整数論における予想の一つで、1971年に提唱したイギリスの数学者デイヴィッド・シングマスターにちなんで名付けられました。パスカルの三角形の要素の重複回数には有限の上限が存在するというものです（ただし、無限回出現する数1は例外です）。パスカルの三角形に無限回出現する数は1のみであることは明らかです。なぜなら、他の数xは三角形の最初のx  + 1行にしか出現できないからです。

声明

パスカルの三角形において、a > 1 となる数 a が現れる回数をN ( a ) とする。大文字の O 記法で表すと、この予想は次のようになる。

${\displaystyle N(a)=O(1).}$

既知の境界

シンマスター（1971）は、

${\displaystyle N(a)=O(\log a).}$

Abbott、Erdős、Hanson（1974）（参考文献を参照）は推定値を次のように精緻化した。

${\displaystyle N(a)=O\left({\frac {\log a}{\log \log a}}\right).}$

現在知られている最良の（無条件の）境界は

${\displaystyle N(a)=O\left({\frac {(\log a)(\log \log \log a)}{(\log \log a)^{3}}}\right),}$

これはケイン（2007）によるものである。アボット、エルデシュ、ハンソンは、クラメールの連続する素数間のギャップに関する予想を条件として、

${\displaystyle N(a)=O\left((\log a)^{2/3+\varepsilon }\right)}$

あらゆる に対して成り立ちます。 ${\displaystyle \varepsilon >0}$

シングマスター（1975）は、ディオファントス方程式

${\displaystyle {n+1 \choose k+1}={n \choose k+2}}$

2つの変数n、kに対して、無限に多くの解が存在する。したがって、少なくとも6の重複度を持つ三角形の要素は無限に存在する。任意の非負のiに対して、パスカルの三角形に6回現れる数aは、上記の2つの式のいずれかで与えられる。

${\displaystyle n=F_{2i+2}F_{2i+3}-1,}$

${\displaystyle k=F_{2i}F_{2i+3}-1,}$

ここで、F _jはj番目のフィボナッチ数（ F ₀  = 0、F ₁ = 1という規則に従って添え字が付けられる ）である。上記の2つの式は、2つの出現の位置を示している。他の2つの出現は、三角形内でこれら2つの出現に対して対称的に現れる。そして、残りの2つの出現は、${\displaystyle {a \choose 1}}$ ${\displaystyle {a \choose a-1}.}$

基本的な例

• 2 は 1 回だけ出現します。これより大きい正の整数は複数回出現します。
• 3、4、5 はそれぞれ 2 回出現します。無限の数の数字が正確に 2 回出現します。
• すべての奇数の素数は 2 回出現します。
• 6は3回出現し、1と2を除くすべての中心二項係数
  も同様である。 （原理的には、このような係数が5回、7回、あるいはそれ以上出現することも排除されないが、そのような例は知られていない。）
• 素数の形式で表されるすべての数は4 回出現します。${\displaystyle {p \choose 2}}$ ${\displaystyle p>3}$
• 無限に多く出現するものは、次のそれぞれを含めて、正確に 6 回出現します。

${\displaystyle 120={120 \choose 1}={120 \choose 119}={16 \choose 2}={16 \choose 14}={10 \choose 3}={10 \choose 7}}$

${\displaystyle 210={210 \choose 1}={210 \choose 209}={21 \choose 2}={21 \choose 19}={10 \choose 4}={10 \choose 6}}$

${\displaystyle 1540={1540 \choose 1}={1540 \choose 1539}={56 \choose 2}={56 \choose 54}={22 \choose 3}={22 \choose 19}}$

${\displaystyle 7140={7140 \choose 1}={7140 \choose 7139}={120 \choose 2}={120 \choose 118}={36 \choose 3}={36 \choose 33}}$

${\displaystyle 11628={11628 \choose 1}={11628 \choose 11627}={153 \choose 2}={153 \choose 151}={19 \choose 5}={19 \choose 14}}$

${\displaystyle 24310={24310 \choose 1}={24310 \choose 24309}={221 \choose 2}={221 \choose 219}={17 \choose 8}={17 \choose 9}}$

シングマスターの無限族（フィボナッチ数列で表す）の次の数であり、6回以上出現する次に小さい数は次の通りである：^[1]${\displaystyle a=61218182743304701891431482520}$

${\displaystyle a={a \choose 1}={a \choose a-1}={104 \choose 39}={104 \choose 65}={103 \choose 40}={103 \choose 63}}$

• 8 回出現する最小の数字 (実際には 8 回出現することが知られている唯一の数字) は 3003 であり、これは少なくとも 6 回の重複を持つシングマスターの無限数族のメンバーでもあります。

${\displaystyle 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}}$

無限の数の数字が 8 回出現するかどうかは不明であり、3003 以外の数字が 8 回出現するかどうかも不明です。

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

∞、1、2、2、2、3、2、2、2、4、2、2、2、2、4、2、2、2、2、2、3、4、2、2、2、2、2、2、2、4、2、2、2、2、2、2、2、2、4、4、2、2、2、2、2、2、2、2、2、2、4、2、2、2、2、2、2、2、2、2、4、2、2、2、2、2、2、2、2、2、2、4、4、2、2、2、2、2、2、2、2、2、2、2、2、4、2、2、2、2、2、2、2、2、2、4、2、2、2、2、2、2、2、2、2、4、2、2、2、2、2、2、2、2、2、4、2、2、2、2、2、2、2、2、4、2、2、2、2、2、2、2、2、4、2、2、2、2、3、2、2、2、2、2、2、2、2、2、2、4 ...2、2、2、2、4、2、2、2、2、2、3、2、2、2、2、2、2、2、2、2、2、4、2、2、2、2、2、2、2、2、4、 2、2、4、2、2、2、2、2、2、2、4、2、2、2、2、2、2、2、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、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、2、6、2、2、2、2、2、2、2、4、2、2、... (OEISのシーケンスA003016 )

Abbott、Erdős、Hanson (1974) によれば、パスカルの三角形に 2 回以上現れるx以下の整数の数はです。 ${\displaystyle O(x^{1/2})}$

パスカルの三角形に （少なくとも）n回現れる1より大きい最小の自然数は

2、3、6、10、120、120、3003、3003、…（OEISのシーケンスA062527）

パスカルの三角形に少なくとも5回現れる数字は

1、120、210、1540、3003、7140、11628、24310、61218182743304701891431482520、…（OEISのシーケンスA003015）

これらのうち、シングマスターの無限の家族に属するものは

1, 3003, 61218182743304701891431482520、…（OEISの配列A090162）

未解決の質問

8回以上出現する数が存在するかどうかは不明であり、3003以外の数も8回以上出現するかどうかは不明である。推定される有限の上限は8回程度である可能性もあるが、シンマスターは10回か12回かもしれないと考えていた。また、5回または7回正確に出現する数が存在するかどうかも不明である。

参照

• 二項係数

参考文献

1. De Weger, Benjamin MM (1995年8月). 「Equal binomial coefficients: some elementary considerations」(PDF) . Econometric Institute Research Papers : 3. 2024年9月6日閲覧.

• シングマスター, D. (1971)、「研究課題：整数が二項係数として現れる頻度」アメリカ数学月刊誌、78 (4): 385– 386、doi :10.2307/2316907、JSTOR  2316907、MR  1536288。

• シングマスター, D. (1975)、「繰り返し二項係数とフィボナッチ数」(PDF)、フィボナッチ・クォータリー、13 (4): 295– 298、doi :10.1080/00150517.1975.12430610、MR  0412095。

• アボット, HL;エルデシュ, P .; ハンソン, D. (1974)「整数が二項係数として現れる回数について」アメリカ数学月刊誌, 81 (3): 256– 261, doi :10.2307/2319526, JSTOR  2319526, MR  0335283。

• Kane, Daniel M. (2007)、「t を二項係数として表す方法の数の改良された境界」(PDF)、INTEGERS: The Electronic Journal of Combinatorial Number Theory、7 : #A53、MR  2373115。