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

Гипотеза Сингмастера — утверждение о том, что в треугольнике Паскаля имеется конечная верхняя граница количества одинаковых чисел, бо́льших единицы.

Предложена Дэвидом Сингмастером в работе 1971 года, в которой доказано, что $N(a)=O(\log a)$ (где $N(a)$ — число появлений числа $a>1$ в треугольнике Паскаля, $O(f)$ — асимптотическое ограничение сверху) и предположено, что $N(a)=O(1)$.

Пал Эрдёш считал, что гипотеза верна, но доказать её будет трудно.

Начальную оценку Сингмастера последовательно улучшали, к 2007 году получена лучшая (по состоянию на 2024 год) оценка:

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

Кроме того, установлено, что условие гипотезы Крамера о расстоянии между последовательными простыми числами влечёт оценку:

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

для любого $\varepsilon >0$.

Сингмастер в 1975 году установил, что диофантово уравнение:

${\binom {n+1}{k+1}}={\binom {n}{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, появляются более одного раза, в том числе 3, 4, 5 появляются 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.

Неизвестно, существуют ли числа, которые появляются в треугольнике Паскаля ровно пять или ровно семь раз.

Литература

• D. Singmaster. Research Problems: How often does an integer occur as a binomial coefficient? // American Mathematical Monthly. — 1971. — Т. 78, вып. 4. — С. 385—386. — doi:10.2307/2316907. — .
• D. Singmaster. Repeated binomial coefficients and Fibonacci numbers // Fibonacci Quarterly. — 1975. — Т. 13, вып. 4. — С. 295—298.
• H. L. Abbott, P. Erdős, D. Hanson. On the number of times an integer occurs as a binomial coefficient // American Mathematical Monthly. — 2319526. — Т. 81, вып. 3. — С. 256—261. — doi:10.2307/2319526.
• Daniel M. Kane. Improved bounds on the number of ways of expressing t as a binomial coefficient // Integers: Electronic Journal of Combinatorial Number Theory. — 2007. — Т. 7. — С. #A53.

Ссылки

• последовательность A003016 в OEIS