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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории чисел гипотеза Сингмастера, названная в честь Дэвида Сингмастера, утверждает, что имеется конечная верхняя граница количества одинаковых чисел в треугольнике Паскаля (больших единицы). Ясно, что только единица содержится в треугольнике Паскаля бесконечное число раз, поскольку любое другое число x может встретиться только в первых x + 1 строках треугольника. Пол Эрдёш считал, что гипотеза Сингмастера верна, но предполагал, что доказать это будет трудно.

Пусть N(a) — сколько раз число a > 1 появляется в треугольнике Паскаля.

В O-нотации, гипотеза выглядит как:

N(a) = O(1).\,

Известные результаты[править | править исходный текст]

Сингмастер (1971) показал, что

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

Позднее Аббот (Abbot), Эрдёш, и Хансон (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,\,

где Fn — n-ое число Фибоначчи (согласно общепринятому F1 = F2 = 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.

Появляются ли числа точно пять или семь раз?[править | править исходный текст]

Согласно записи A003016 в OEIS, неизвестно, имеет ли решение уравнение N(a) = 5. Неизвестно также, появляется какое-либо число семь раз.

См. также[править | править исходный текст]

Литература[править | править исходный текст]

Ссылки[править | править исходный текст]