Гипотеза Singmasters - Singmasters conjecture

Нерешенная проблема в математике: Кажется ли, что каждая запись (кроме 1) в треугольнике Паскаля меньше, чем N раз для некоторой постоянной N? (больше нерешенных задач по математике)

Гипотеза певца это догадка в комбинаторная теория чисел в математика, названный в честь британского математика Дэвид Сингмастер кто предложил это в 1971 году. В нем говорится, что существует конечная верхняя граница на множественность записей в Треугольник Паскаля (кроме числа 1, которое встречается бесконечно много раз). Понятно, что единственное число, которое встречается бесконечно много раз в Треугольник Паскаля равно 1, потому что любое другое число Икс может появиться только в пределах первого Икс + 1 ряд треугольника.

Заявление

Позволять N(а) быть числом, умноженным на а > 1 появляется в треугольнике Паскаля. В нотация большой O, гипотеза:

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

Известная граница

Singmaster (1971) показал, что

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

Настоятель, Erds, и Хэнсон (1974) (см. Рекомендации ) уточнил оценку до:

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

Наилучшая известная на данный момент (безусловная) граница:

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

и это связано с Кейн (2007). Эббот, Эрдеш и Хэнсон отмечают, что при условии Гипотеза Крамера на промежутках между последовательными простыми числами, которые

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

справедливо для каждого ${\displaystyle \varepsilon >0}$.

Singmaster (1975) показал, что Диофантово уравнение

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

имеет бесконечно много решений для двух переменных п, k. Отсюда следует, что существует бесконечно много элементов треугольника кратности не менее 6: для любого неотрицательного я, число а с шестью появлением в треугольнике Паскаля задается любым из двух вышеупомянутых выражений с

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

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

куда F_j это jth Число Фибоначчи (проиндексировано в соответствии с соглашением, что F₀ = 0 и F₁ = 1). Приведенные выше два выражения определяют два появления; два других появляются в треугольнике симметрично по отношению к этим двум; и два других выступления в ${\displaystyle {a \choose 1}}$ и ${\displaystyle {a \choose a-1}.}$

Элементарные примеры

• 2 появляется только один раз; все большие положительные целые числа встречаются более одного раза;
• 3, 4, 5 появляются по два раза; бесконечно много появляется ровно дважды;
• все нечетные простые числа встречаются два раза;
• 6 появляется трижды, как и бесконечно много чисел;
• все числа формы ${\displaystyle {p \choose 2}}$ для премьер ${\displaystyle p>3}$ четыре раза;
• Бесконечно много появляется ровно шесть раз, включая каждое из следующих:

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

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

${\displaystyle 1540={1540 \choose 1}={1540 \choose 1539}={56 \choose 2}={56 \choose 54}={22 \choose 3}={22 \choose 19}}$

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

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

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

Следующее число в бесконечной семье Сингмастера и следующее наименьшее число, которое, как известно, встречается шесть или более раз, - это ${\displaystyle a=61218182743304701891431482520}$:

${\displaystyle a={a \choose 1}={a \choose a-1}={104 \choose 39}={104 \choose 65}={103 \choose 40}={103 \choose 63}}$

• Наименьшее число, которое встречается восемь раз - действительно, единственное число, которое, как известно, встречается восемь раз - это 3003, которое также является членом бесконечного семейства чисел Singmaster с кратностью не менее 6:

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

Количество раз п появляется в треугольнике Паскаля

∞, 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, ... (последовательность A003016 в OEIS )

По Эбботту, Эрдешу и Хэнсону (1974) количество целых чисел не более Икс которые появляются более чем дважды в треугольнике Паскаля, О(Икс^1/2).

Наименьшее натуральное число (больше 1), которое появляется (как минимум) п раз в треугольнике Паскаля

2, 3, 6, 10, 120, 120, 3003, 3003, ... (последовательность A062527 в OEIS )

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

1, 120, 210, 1540, 3003, 7140, 11628, 24310, 61218182743304701891431482520, ... (последовательность A003015 в OEIS )

Из них в бесконечной семье Сингмастера

1, 3003, 61218182743304701891431482520, ... (последовательность A090162 в OEIS )

Открытые вопросы

Неизвестно, встречается ли какое-либо число более восьми раз и встречается ли какое-либо число, кроме 3003, такое количество раз. Предполагаемая конечная верхняя граница могла быть всего 8, но Сингмастер полагал, что это может быть 10 или 12.

Встречаются ли какие-либо числа ровно пять или семь раз? Это будет видно из соответствующей записи (последовательность A003015 в OEIS ) в Интернет-энциклопедия целочисленных последовательностей, что никто не знает, действительно ли уравнение N(а) = 5 можно решить дляа. Также неизвестно, встречается ли какое-нибудь число, которое встречается семь раз.

Смотрите также

• Биномиальный коэффициент

Рекомендации

• Певец, Д. (1971), «Проблемы исследования: как часто целое число встречается как биномиальный коэффициент?», Американский математический ежемесячный журнал, 78 (4): 385–386, Дои:10.2307/2316907, JSTOR  2316907, МИСТЕР  1536288.

• Певец, Д. (1975), «Повторяющиеся биномиальные коэффициенты и числа Фибоначчи» (PDF), Ежеквартальный отчет Фибоначчи, 13 (4): 295–298, МИСТЕР  0412095.

• Abbott, H.L .; Эрдеш, П.; Hanson, D. (1974), "О том, сколько раз целое число встречается как биномиальный коэффициент", Американский математический ежемесячный журнал, 81 (3): 256–261, Дои:10.2307/2319526, JSTOR  2319526, МИСТЕР  0335283.

• Кейн, Дэниел М. (2007), "Улучшены границы количества способов выражения т как биномиальный коэффициент " (PDF), INTEGERS: Электронный журнал комбинаторной теории чисел, 7: # A53, МИСТЕР  2373115.