Гипотеза Шольца
В математике гипотеза Шольца — это гипотеза о длине некоторых цепочек сложения .Иногда ее также называют гипотезой Шольца-Брауэра или гипотезой Брауэра-Шольца , в честь Арнольда Шольца сформулировавшего ее в 1937 году. [1] и Альфред Брауэр, который вскоре изучил ее и доказал более слабую оценку. [2]
Нил Клифт привел пример, показывающий, что граница гипотезы не всегда точна.
Заявление
[ редактировать ]Гипотеза гласит, что
- л (2 н - 1) ≤ п - 1 + л ( п ) ,
где l ( n ) — длина кратчайшей цепочки сложения, дающей n . [3]
Здесь цепочка сложения определяется как последовательность чисел, начиная с 1, такая, что каждое число после первого может быть выражено как сумма двух предыдущих чисел (оба из которых могут быть равны). Его длина — это количество сумм, необходимых для выражения всех его чисел, что на единицу меньше длины последовательности чисел (поскольку для первого числа в последовательности, 1, нет суммы предыдущих чисел). Вычисление длины кратчайшей цепочки сложения, содержащей заданное число x, может быть выполнено с помощью динамического программирования для малых чисел, но неизвестно, можно ли это сделать за полиномиальное время, измеренное как функция длины двоичного представления x . . Гипотеза Шольца, если она верна, обеспечила бы короткие цепочки сложения для чисел x особого вида — чисел Мерсенна .
Пример
[ редактировать ]Например, l (5) = 3 : у него самая короткая цепочка сложения.
- 1, 2, 4, 5
длины три, определяемой тремя суммами
- 1 + 1 = 2,
- 2 + 2 = 4,
- 4 + 1 = 5.
Кроме того, l (31) = 7 : у него самая короткая цепочка сложения
- 1, 2, 3, 6, 12, 24, 30, 31
длины семь, определяемый семью суммами
- 1 + 1 = 2,
- 2 + 1 = 3,
- 3 + 3 = 6,
- 6 + 6 = 12,
- 12 + 12 = 24,
- 24 + 6 = 30,
- 30 + 1 = 31.
И l (31) , и 5 − 1 + l (5) равны 7.Следовательно, эти значения подчиняются неравенству (которое в данном случае является равенством), и гипотеза Шольца верна для случая n = 5 .
Частичные результаты
[ редактировать ]Используя сочетание методов компьютерного поиска и математических характеристик оптимальных цепочек сложения, Клифт (2011) показал, что гипотеза верна для всех n < 5784689 . Кроме того, он проверил, что для всех n ≤ 64 неравенство гипотезы на самом деле является равенством. [4]
Граница гипотезы не всегда является точным равенством. Например, для , , с . [5] [6]
Ссылки
[ редактировать ]- ^ Шольц, Арнольд (1937), «Задачи и решения, 253» , Годовой отчет Ассоциации немецких математиков , 47 : 41–42, ISSN 0012-0456
- ^ Брауэр, Альфред (1939), «О цепочках сложения», Бюллетень Американского математического общества , 45 (10): 736–739, doi : 10.1090/S0002-9904-1939-07068-7 , ISSN 0002-9904 , MR 0000245 , Збл 0022.11106
- ^ Гай, Ричард К. (2004). Нерешенные проблемы теории чисел (3-е изд.). Спрингер-Верлаг . стр. 169–171. ISBN 978-0-387-20860-2 . Збл 1058.11001 .
- ^ Клифт, Нил Майкл (2011). «Расчет оптимальных цепочек сложения» . Вычисление . 91 (3): 265–284. дои : 10.1007/s00607-010-0118-8 .
- ^ Клифт, Нил (июль 2024 г.). «Точное равенство в гипотезе Шольца-Брауэра» . Проверено 20 июля 2024 г.
- ^ Фламменкамп, Ахим (июль 2024 г.). «Контрпример, подтверждающий гипотезу Шольца-Брауэра с равенством для всех n» . Проверено 20 июля 2024 г.