Гіпотеза Сінгмастера

В теорії чисел гіпотеза Сінгмастера, названа на честь Девіда Сінгмастера, стверджує, що існує кінцева верхня межа кількості однакових чисел (крім одиниці) в трикутнику Паскаля. Зрозуміло, що одиниця міститься в трикутнику Паскаля нескінченне число разів, оскільки будь-яке інше число x може зустрітися тільки в перших x+1 рядках трикутника. Пол Ердеш вважав, що гіпотеза Сінгмастера вірна, але припускав, що довести це буде важко.

Нехай N (a) — скільки разів число a>1 з'являється в трикутнику Паскаля. Тоді в O-нотації, гіпотеза виглядає як:

$N(a)=O(1)$

Відомі результати

Сінгмастер показав:

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

Пізніше Еббот (Abbott), Ердеш, і Хансон (Hanson) (див. Посилання) поліпшили оцінку. Найкраща на сьогодні оцінка

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

отримана завдяки Даніелю Кейну (2007). Аббот Ердеш і Хансон зауважив, що умова гіпотези Крамера про відстань між послідовними простими числами

$N(a)=O\left(\log(a)^{2/3+\varepsilon }\right)$
вірно для будь-якого $\varepsilon >0$ .

Сінгмастер (1975) показав, що діофантове рівняння

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

має нескінченно багато рішень для двох змінних n, k. Звідси випливає, що мається нескінченно багато випадків входження чисел 6 і більше разів. Рішення задаються рівняннями

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

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

де F_n — n-те число Фібоначчі (згідно загальноприйнятому $F_{1}=F_{2}=1$ ).

Числові приклади

Згідно обчислень,

2 з'являється тільки один раз; всі більші ніж 2 числа з'являються більше, ніж один раз
4 та усі непарні прості числа (3, 5, 7, 11, ...) з'являються рівно 2 рази;
6 з'являється 3 рази;
Багато чисел з'являються 4 рази.
Кожне з наступних чисел з'являється 6 разів:

${120 \choose 1}={16 \choose 2}={10 \choose 3}$
${210 \choose 1}={21 \choose 2}={10 \choose 4}$
${1540 \choose 1}={56 \choose 2}={22 \choose 3}$
${7140 \choose 1}={120 \choose 2}={36 \choose 3}$
${11628 \choose 1}={153 \choose 2}={19 \choose 5}$
${24310 \choose 1}={221 \choose 2}={17 \choose 8}$

Найменше число, що з'являється 8 разів — це 3003, яке є також першим членом нескінченного сімейства чисел Сінгмастера, що зустрічаються не менше 6 разів:

${3003 \choose 1}={78 \choose 2}={15 \choose 5}={14 \choose 6}$
Наступне число в нескінченному сімействі Сінгмастера, і наступне найменше відоме число, що з'являється шість і більше разів — це 61218182743304701891431482520. Невідомо, чи з'являються які-небудь числа більш ніж вісім разів. Існує гіпотеза, що максимальне число входжень не більше 8, але Сінгмастер вважає, що воно повинно бути 10 або 12.

Чи з'являються числа точно п'ять або сім разів?

В Енциклопедії послідовностей цілих чисел вказано, що невідомо, чи має розв'язок рівняння N (a) = 5. Невідомо також, чи з'являється якесь число сім раз.

Див. також

Біноміальний коефіцієнт

Література

Д. Сінгмастер (1971), Дослідження проблеми: Як часто цілі числа виступають в ролі біноміального коефіцієнта?, American Mathematical Monthly, 78 (4): 385—386, JSTOR 2316907, MR 1536288.

Д. Сінгмастер (1975), Повторення біноміальних коефіцієнтів і числа Фібоначчі (PDF), Квартальне періодичне видання Фібоначчі^[en], 13 (4): 295—298, MR 0412095, архів оригіналу (PDF) за 11 вересня 2015, процитовано 29 жовтня 2014.

Г. Л. Еббот (1974), Скільки разів цілі числа виступають в ролі біноміального коефіцієнта?, American Mathematical Monthly, 81 (3): 256—261, JSTOR 2319526, MR 0335283.

Даніель Кейн^[en] (2007), Вдосконалені обмеження на кількість способів вираження t як біноміального коефіцієнта (PDF), Електронний журнал комбінаторної теорії чисел, 7: #A53, MR 2373115, архів оригіналу (PDF) за 24 вересня 2015, процитовано 29 жовтня 2014.