Przypuszczenie Singmastera

Nierozwiązany problem z matematyki :

Czy każdy wpis (oprócz 1) trójkąta Pascala pojawia się mniej niż N razy dla jakiejś stałej N ?

(więcej nierozwiązanych problemów z matematyki)

Hipoteza Singmastera to hipoteza w kombinatorycznej teorii liczb , nazwana na cześć brytyjskiego matematyka Davida Singmastera , który zaproponował ją w 1971 roku. Mówi ona, że ​​istnieje skończona górna granica krotności wpisów w trójkącie Pascala (inna niż liczba 1, która pojawia się nieskończenie wiele razy). Jest oczywiste, że jedyną liczbą, która pojawia się nieskończenie wiele razy w trójkącie Pascala, jest 1, ponieważ każda inna liczba x może pojawić się tylko w pierwszym x + 1 rzędy trójkąta.

Oświadczenie

Niech N ( a ) będzie liczbą wystąpień liczby a > 1 w trójkącie Pascala. W notacji dużego O hipoteza jest następująca:

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

Znana granica

Pokazał to Singmaster (1971).

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

Abbot, Erdős i Hanson (1974) (patrz Literatura ) udoskonalili oszacowanie do:

${\ Displaystyle N (a) = O \ lewo ({\ Frac {\ log a} {\ log \ log a}} \ prawo).}$

Najlepszym obecnie znanym (bezwarunkowym) ograniczeniem jest

${\ Displaystyle N (a) = O \ lewo ({\ Frac {(\ log a)(\log \log \log a)}{(\log \log a)^{3}}}\right),}$

i jest wynikiem Kane'a (2007). Abbot, Erdős i Hanson zauważają, że uwarunkowane przypuszczeniem Craméra o przerwach między kolejnymi liczbami pierwszymi, które

${\ Displaystyle N (a) = O \ lewo ((\ log a) ^ {2/3 + \ varepsilon} \ prawej)}$

obowiązuje dla każdego ${\ displaystyle \ varepsilon > 0}$ .

Singmaster (1975) wykazał, że równanie diofantyczne

${\ Displaystyle {n + 1 \ wybierz k + 1} = {n \ wybierz k + 2}}$

ma nieskończenie wiele rozwiązań dla dwóch zmiennych n , k . Wynika z tego, że istnieje nieskończenie wiele trójkątów o krotności co najmniej 6: Dla dowolnego nieujemnego i , liczba a z sześcioma występami w trójkącie Pascala jest dana przez jedno z dwóch powyższych wyrażeń z

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

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

₀ gdzie F _j jest j -tą liczbą Fibonacciego (indeksowaną zgodnie z konwencją, że F = 0 i F ₁ = 1). Powyższe dwa wyrażenia lokalizują dwa z występów; dwa inne pojawiają się symetrycznie w trójkącie w stosunku do tych dwóch; a pozostałe dwa występy są w ${\ Displaystyle {a \ wybierz 1}}$ i ${\ Displaystyle {a \ wybierz a-1}.}$

Elementarne przykłady

• 2 pojawia się tylko raz; wszystkie większe dodatnie liczby całkowite pojawiają się więcej niż raz;
• 3, 4, 5 pojawiają się dwa razy; nieskończenie wiele pojawia się dokładnie dwa razy;
• wszystkie nieparzyste liczby pierwsze pojawiają się dwa razy;
• 
  6 pojawia się trzy razy, podobnie jak wszystkie centralne współczynniki dwumianowe z wyjątkiem 1 i 2; (w zasadzie nie jest wykluczone, że taki współczynnik pojawi się 5, 7 lub więcej razy, ale żaden taki przykład nie jest znany)
• $p> 3}$ postaci dla liczby pierwszej $p$ razy;
• Nieskończenie wiele pojawia się dokładnie sześć razy, w tym każdy z poniższych:

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

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

${\ Displaystyle 1540 = {1540 \ wybierz 1} = {1540 \ wybierz 1539} = {56 \ wybierz 2} = {56 \ wybierz 54} = {22 \ wybierz 3} = { 22 \wybierz 19}}$

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

${\ Displaystyle 11628 = {11628 \ wybierz 1} = {11628 \ wybierz 11627} = {153 \ wybierz 2}={153 \wybierz 151}={19 \wybierz 5}={19 \wybierz 14}}$

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

Następna liczba w nieskończonej rodzinie Singmastera (podana za pomocą liczb Fibonacciego) i następna najmniejsza liczba, o której wiadomo, że występuje sześć lub więcej razy, to za = 61218182743304701891431482520 {\ $61218182743304701891431482520$ :

${\ Displaystyle a = {a \ wybierz 1} = {a \ wybierz a-1} = {104 \ wybierz 39} = {104 \ wybierz 65} = {103 \ wybierz 40} = {103 \ wybierz 63}}$

• Najmniejsza liczba, która pojawia się osiem razy – właściwie jedyna znana liczba, która pojawia się osiem razy – to 3003, która również należy do nieskończonej rodziny liczb Singmastera o krotności co najmniej 6:

${\ Displaystyle 3003 = {3003 \ wybierz 1} = {78 \ wybierz 2} = {15 \ wybierz 5} = {14 \ wybierz 6 }={14 \choose 8}={15 \choose 10}={78 \choose 76}={3003 \choose 3002}}$

Liczba wystąpień n w trójkącie Pascala wynosi

∞, 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, ... (sekwencja A003016 w OEIS )

Według Abbotta, Erdősa i Hansona (1974) liczba liczb całkowitych nie większych niż x , które pojawiają się więcej niż dwa razy w trójkącie Pascala, wynosi O ( x ^1/2 ).

Najmniejszą liczbą naturalną (powyżej 1), która pojawia się (co najmniej) n razy w trójkącie Pascala jest

2, 3, 6, 10, 120, 120, 3003, 3003, ... (sekwencja A062527 w OEIS )

Liczby, które występują co najmniej pięć razy w trójkącie Pascala to:

1, 120, 210, 1540, 3003, 7140, 11628, 24310, 61218182743304701891431482520, ... (sekwencja A003015 w OEIS )

Wśród nich są te z nieskończonej rodziny Singmastera

1, 3003, 61218182743304701891431482520, ... (sekwencja A090162 w OEIS )

Otwarte pytania

Nie wiadomo, czy jakakolwiek liczba pojawia się więcej niż osiem razy, ani czy jakakolwiek liczba poza 3003 pojawia się tak często. Przypuszczalna skończona górna granica może wynosić zaledwie 8, ale Singmaster pomyślał, że może to być 10 lub 12.

Czy jakieś liczby pojawiają się dokładnie pięć lub siedem razy? Z pokrewnej sekwencji (sekwencja A003015 w OEIS ) wynikałoby , że nikt nie wie, czy równanie N ( a ) = 5 można rozwiązać dla a . Nie wiadomo również, czy istnieje liczba, która pojawia się siedem razy.

Zobacz też

• Współczynnik dwumianowy

•    Singmaster, D. (1971), „Problemy badawcze: jak często występuje liczba całkowita jako współczynnik dwumianowy?”, American Mathematical Monthly , 78 (4): 385–386, doi : 10,2307/2316907 , JSTOR 2316907 , MR 1536288 .

• Singmaster, D. (1975), „Powtórzone współczynniki dwumianowe i liczby Fibonacciego” (PDF) , Fibonacci Quarterly , 13 (4): 295–298, MR   0412095 .

•    Abbott, HL; Erdős, P. ; Hanson, D. (1974), „O liczbie przypadków, w których liczba całkowita występuje jako współczynnik dwumianowy”, American Mathematical Monthly , 81 (3): 256–261, doi : 10,2307/2319526 , JSTOR 2319526 , MR 0335283 .

• Kane, Daniel M. (2007), „Poprawione granice liczby sposobów wyrażania t jako współczynnika dwumianowego” (PDF) ,   INTEGERS: The Electronic Journal of Combinatorial Number Theory , 7 : # A53, MR 2373115 .