Московский десятиклассник обогнал Эрдёша в построении остроугольных треугольников

30 апреля ученик московской школы номер 179, Дмитрий Захаров, опубликовал на сервере препринтов arxiv.org новый контрпример к гипотезе Данцера и Грюнбаума. Результат юного математика оказался гораздо сильнее, чем все предыдущие контрпримеры. В частности, школьник улучшил результат Пауля Эрдёша, которого считают одним из самых известных и продуктивных математиков XX века. О результатах десятиклассника рассказал на своей странице в фейсбуке математик Арсений Акопян.

Задача Данцера и Грюнбаума формулируется очень просто — какое наибольшее число точек в пространстве можно поместить так, чтобы любые три из них образовывали остроугольный треугольник. Очевидно, что на плоскости это число равно трем (любая попытка поставить четвертую точку приведет к возникновению тупого угла). Для трехмерного пространства это число равно пяти. Для пространств высшей размерности такое число точно неизвестно. 

В 1962 году Людвиг Данцер и Бранко Грюнбаум показали, что для пространства размерности N количество таких точек может быть равно 2N-1. Гипотеза математиков состояла в том, что это и есть максимальное число точек в «остром множестве». Лишь спустя более 20 лет к гипотезе ученых был построен контрпример. Пауль Эрдёш и Золтан Фюреди показали, что можно построить «острое множество» так, что число точек в нем будет расти по экспоненте (примерно как 0,5×1,15^N). При размерности пространства больше 34 эта оценка — нижняя граница требуемого числа — оказывается «лучше», чем в гипотезе Данцера и Грюнбаума. Подробнее об этом построении можно прочесть в брошюре Андрея Райгородского «Остроугольные треугольники Данцера и Грюнбаума». В 2010 году этот результат был дополнительно улучшен Виктором Харанги. 

Как рассказывает один из участников дискуссии в фейсбуке, Александр Полянский, первоначально Дмитрий Захаров независимо от Харанги получил то же самое улучшение (примерно до c×1,2^N). Однако Андрей Райгородский, которому Дмитрий рассказал о результате, обнаружил статью Харанги и «расстроил Диму». Тем не менее математик не сдался и нашел принципиально другой подход к задаче. Построение, использованное школьником, позволяет создавать «острые множества» из 2^N/2 точек. Как отмечают участники дискуссии, решение Захарова довольно просто — оно занимает всего полстраницы.

В основе доказательства лежит метод математической индукции. Предположим, что для размерности N мы можем построить «острое множество» из максимального количества точек (для N=2 и 3 мы умеем это делать). Покажем, как построить «острое множество» из в два раза большего количества точек для пространства размерности N+2. Для этого аккуратно раздвоим каждую точку исходного множества так, чтобы расстояние между двумя новыми точками не превышало некоторой величины. При этом все раздвоения сделаем немного отличающимися друг от друга в проекции на плоскость двух новых размерностей. Тогда, если величина подобрана правильно (а это всегда можно сделать), новое множество тоже будет «острым». Такое удвоение можно продолжать до бесконечности.

Важно заметить, что построенный пример не отвечает на вопрос того, каково максимальное количество точек в «остром множестве» для данной размерности. Более того, это число известно лишь в плоскости и трехмерном пространстве, а для четырех-, пяти- и шестимерных пространств точного ответа нет. Известно, что «острое множество» конечно для любой размерности — число точек в нем должно быть меньше числа вершин в кубе соответствующей размерности (2^N). 

Среди задач, над которыми работал Пауль Эрдёш, одна из самых известных — задача о расходимости. Ее можно сформулировать так. Представьте, что вы стоите на первом этаже башни, бесконечно уходящей ввысь и вглубь. Каждую минуту приходит лифт, который может отвезти вас на один этаж вверх или вниз — направления движения лифтов заранее известны, но вам неподвластны. Допустим, вы хотите убраться как можно дальше от поверхности, скажем, на С этажей — не важно, в каком направлении. По правилам, вы можете выбрать любое число d, и входить в каждый d-й приходящий лифт. Можно ли выбрать такое d и такое k, что через k поездок вы уедете как минимум на C этажей от первоначального? Интересно, что решить ее удалось благодаря комментарию в интернете.

Ранее мы сообщали о британском школьнике, открывшем в пятнадцать лет новую экзопланету на основе анализа данных астрономического обзора WASP. 

Владимир Королёв