Singmasters gissning

Olöst problem i matematik :

Uppträder varje post (förutom 1) i Pascals triangel färre än N gånger för någon konstant N ?

(fler olösta problem i matematik)

Singmasters gissning är en gissning inom kombinatorisk talteori , uppkallad efter den brittiske matematikern David Singmaster som föreslog den 1971. Den säger att det finns en ändlig övre gräns för multipliciteten av poster i Pascals triangel (annat än siffran 1, som visas oändligt många gånger). Det är tydligt att det enda tal som förekommer oändligt många gånger i Pascals triangel är 1, eftersom alla andra tal x bara kan förekomma inom de första x + 1 raderna i triangeln.

Påstående

Låt N ( a ) vara antalet gånger talet a > 1 förekommer i Pascals triangel. I stor O-notation är gissningen:

$N(a)=O(1).$

Känd bunden

Det visade Singmaster (1971).

$N(a)=O(\log a).$

Abbot, Erdős och Hanson (1974) (se referenser ) förfinade uppskattningen till:

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

Den för närvarande mest kända (ovillkorliga) bunden är

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

och beror på Kane (2007). Abbot, Erdős och Hanson noterar att beroende på Cramérs gissning om klyftor mellan på varandra följande primtal som

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

gäller för varje $\varepsilon >0$ .

Singmaster (1975) visade att den diofantiska ekvationen

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

har oändligt många lösningar för de två variablerna n , k . Det följer att det finns oändligt många triangelposter med multiplicitet minst 6: För alla icke-negativa i , ges ett tal a med sex uppträdanden i Pascals triangel av något av ovanstående två uttryck med

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

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

₀ där F _j är det j: te Fibonacci-talet (indexerat enligt konventionen att F = 0 och F ₁ = 1). De två ovanstående uttrycken lokaliserar två av utseenden; två andra visas symmetriskt i triangeln med avseende på dessa två; och de andra två förekomsterna är vid ${a \choose 1}$ och ${a \choose a-1}.$

Elementära exempel

• 2 visas bara en gång; alla större positiva heltal visas mer än en gång;
• 3, 4, 5 visas vardera två gånger; oändligt många dyker upp exakt två gånger;
• alla udda primtal visas två gånger;
• 
  6 visas tre gånger, liksom alla centrala binomialkoefficienter förutom 1 och 2; (det är i princip inte uteslutet att en sådan koefficient skulle förekomma 5, 7 eller fler gånger, men inget sådant exempel är känt)
• alla tal i formen ${p \choose 2}$ för primtal $p>3$ visas fyra gånger;
• Oändligt många dyker upp exakt sex gånger, inklusive var och en av följande:

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

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

$1540={1540}={välj 1540 \choose 1539}={56 \choose 2}={56 \choose 54}={22 \choose 3}={22 \choose 19}$

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

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

$24310={24310 \choose 1}={24310 \choose 24309}={221 \choose 2}={21 välj 219}={17 \choose 8}={17 \choose 9}$

Nästa siffra i Singmasters oändliga familj (givet i termer av Fibonacci-tal), och det näst minsta talet som man vet förekommer sex eller fler gånger, är $a=61218182743304701891431482520$ :

$displaystyle a={a \ välj 1}={a \choose a-1}={104 \choose 39}={104 \choose 65}={103 \choose 40}={103 \choose 63}} Det minsta talet som visas åtta gånger –$

• faktiskt , det enda tal som man vet förekommer åtta gånger – är 3003, som också är en medlem av Singmasters oändliga talfamilj med multiplicitet på minst 6:

$3003={3003 \choose 1}={78 \choose 2}={15 \choose 5}={14 \ välj 6}={14 \choose 8}={15 \choose 10}={78 \choose 76}={3003 \choose 3002}$

Antalet gånger n förekommer i Pascals triangel är

∞, 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, ... (sekvens A003016 i OEIS )

Av Abbott, Erdős och Hanson (1974) är antalet heltal som inte är större än x som förekommer mer än två gånger i Pascals triangel O ( x ^1/2 ).

Det minsta naturliga talet (över 1) som förekommer (minst) n gånger i Pascals triangel är

2, 3, 6, 10, 120, 120, 3003, 3003, ... (sekvens A062527 i OEIS )

Siffrorna som förekommer minst fem gånger i Pascals triangel är

1, 120, 210, 1540, 3003, 7140, 11628, 24310, 61218182743304701891431482520, ... (sekvens A003015 i OEIS )

Av dessa är de i Singmasters oändliga familj

1, 3003, 61218182743304701891431482520, ... (sekvens A090162 i OEIS )

Öppna frågor

Det är inte känt om något nummer förekommer mer än åtta gånger, och inte heller om något nummer förutom 3003 förekommer så många gånger. Den förmodade ändliga övre gränsen kunde vara så liten som 8, men Singmaster trodde att det kunde vara 10 eller 12.

Uppträder några siffror exakt fem eller sju gånger? Det framgår av en relaterad sekvens (sekvens A003015 i OEIS ) att ingen vet om ekvationen N ( a ) = 5 kan lösas för a . Det är också okänt om det finns något nummer som förekommer sju gånger.

Se även

• Binomial coefficient

•    Singmaster, D. (1971), "Research Problems: How often does an integer occur as a binomial coefficient?", American Mathematical Monthly , 78 (4): 385–386, doi : 10.2307/2316907 , JSTOR 2316907 , 78 (4 ) : 1536288 .

•   Singmaster, D. (1975), "Repeated binomial coefficients and Fibonacci numbers" (PDF) , Fibonacci Quarterly , 13 (4): 295–298, MR 0412095 .

•    Abbott, HL; Erdős, P. ; Hanson, D. (1974), "On the number of times an integer occurs as a binomial coefficient", American Mathematical Monthly , 81 (3): 256–261, doi : 10.2307/2319526 , JSTOR 2319526 , MR 0335283 .

•   Kane, Daniel M. (2007), "Förbättrade gränser för antalet sätt att uttrycka t som en binomial koefficient" (PDF) , INTEGERS : The Electronic Journal of Combinatorial Number Theory , 7 : #A53, MR 2373115 .