Max Home IndustryЭто не такие уж важные теоретические новости, как NP = P или что-то подобное, но идея захватывающая. Около 80 лет назад замечательный и странный математик Пол Эрдош сформулировал, казалось, простой вопрос о числовых последовательностях, и это только что было доказано.
Гипотеза Эрдоша о несоответствии — одна из тех хороших идей, которые легко сформулировать, но очень сложно доказать. Это касается очень простых последовательностей чисел, состоящих только из -1 и 1. Проблема в том, что последовательности бесконечны, и часто именно здесь начинаются трудности в математике.
Пол Эрдош 1913–1996
Гипотеза состоит в том, что если вы выберете интервал d и длину n, то вы можете сделать сумму сколь угодно большой, выбрав d и a соответствующим образом.
Например, учитывая последовательность с довольно очевидным шаблоном:
1, -1, 1,1, -1, -1, 1,1,1 -1, -1, -1, 1,1,1,1, -1, -1, -1, -1 и скоро
затем, начиная с третьего элемента, a 1, с интервалом d = 2 и длиной 6, расхождение составляет 1-1 + 1 + 1-1 + 1 + 1, т.е. 3.
Очевидно, что несоответствие подпоследовательности измеряет степень, в которой элементы 1 и -1 распределены неравномерно, и гипотезу можно интерпретировать как утверждающую, что независимо от того, как сильно вы пытаетесь создать последовательность, которая равномерно распределена, вы обречены на неудачу, поскольку всегда быть подпоследовательностями с неравномерным распределением 1 и -1, чтобы дать вам любое несоответствие, которое вы хотите назвать.
Математически гипотеза состоит в том, что для последовательности xn для любого целого числа C> 0 существует подпоследовательность xd, x2d, x3d, … xkd для некоторого выбора натуральных чисел k и d
Вы также можете присвоить исходной бесконечной серии оценку несоответствия как максимальное несоответствие содержащейся в ней подпоследовательности. В этом случае гипотеза утверждает, что каждая бесконечная последовательность имеет бесконечное несоответствие.
В 1993 году было доказано, что бесконечный ряд не может иметь несоответствие 1. Это было сделано путем демонстрации того, что серия длины 12 всегда имеет подпоследовательность с несоответствием больше 1. Поскольку это верно для любой серии длины 12, она должна быть быть верным для любой бесконечной серии, содержащей любое количество подпоследовательностей длины 12.
Таким образом, теорема доказана для C = 1.
В прошлом году совместный проект на вики Polymath увеличил этот показатель до C = 2 с помощью решателя SAT. Проблема заключалась в том, что сложность возрастала по мере того, как C становится больше, и доказательство для C = 2 было настолько долго, что считалось самым длинным математическим доказательством на сегодняшний день.
Казалось, что этот компьютерный подход увяз в тупике. Однако эта работа действительно побудила Теранса Тао взглянуть на проблему по-разному, что в конечном итоге привело к опубликованию им доказательства гипотезы. Его доказательство еще не прошло экспертную оценку, но, скорее всего, оно верное.
Тао был вундеркиндом и, когда ему было 10 лет, какое-то время учился у Эродоса.
Тао (10 лет) с Эрдошем
За это решение Эрдос предложил приз в размере 500 долларов. Не похоже, что Тао действительно получит чек от кого-либо, но, вероятно, он не беспокоится.
Итак, теперь мы знаем, что вы не можете построить бесконечную последовательность чисел, которая была бы однородной в том смысле, что всегда есть подпоследовательности, сумма которых больше любого заданного числа, которое вы хотите указать.
Но математика всегда идет своим чередом — теперь вопрос в том, как долго должна длиться подпоследовательность, чтобы добраться до C? Если C = 2 k <1161, как насчет C = 3?