Посетители форума улучшили оценку Эрдёша

11 сентября на сайте препринтов arxiv.org вышла статья венгерских математиков Геренчера и Харанги, в которой была принципиально улучшена оценка снизу в задаче Данцера и Грюнбаума. Интересно, что важную роль в решении этой задачи сыграло её обсуждение на математическом форуме dxdy.ru. Об этом рассказал на своей странице в фейсбуке математик Арсений Акопян.

Около 1950 года математик Пауль Эрдёш предположил, что в R^d мерном пространстве в любом множестве, содержащем более 2^d точек, обязательно найдутся три такие, которые будут определять тупой угол. Действительно, d-мерный куб содержит 2^d точек, все углы в нем прямые, и если немного пошевелить его вершины или добавить к нему хотя бы еще одну точку, возникнет тупой угол (а может быть, и не один). Естественным образом возникает вопрос: сколько точек может содержаться в множестве, чтобы все образуемые ими углы были острыми? Такие множества называются острыми (ОМ).

В пространствах небольшой размерности максимальные острые множества найти несложно. Например, очевидно, что в R² максимальным ОМ является равносторонний треугольник (3 точки), в R³ — немного сплюснутая равнобокая бипирамида (5 точек). Этот ряд легко продолжить и найти в R^d ОМ, состоящее из 2d - 1 точек. Этот результат получили в 1962 году Данцер и Грюнбаум. Тогда же они высказали гипотезу, что число N = 2d — 1 в точности равно максимальному возможному числу точек ОМ в R^d.

Долгое время эту оценку не удавалось улучшить, однако в 1983 году Пауль Эрдёшь и Золтан Фюреди построили контпример к гипотезе Данцера-Грюнбаума. С помощью методов вероятностной геометрии они получили экспоненциально растущую оценку (N ~ 0.5 × 1.15^d), которая превосходила полученное ранее значение при d = 35. (Подробнее о применении вероятностных методов к этой задаче можно прочитать в брошюре Райгородского) В 2010 году результат был дополнительно улучшен Виктором Харанги до N ~ c × 1.2^d.

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

Мы писали о первой работе Захарова, и наша новость попала на математический форум dxdy.ru, где вызвала живой интерес. Форумчанин grizzly предложил строить острое множество, отталкиваясь не от пирамиды, как Данцер и Грюнбаум, а от куба. Он рассматривал (d-1)-мерный куб, вложенный R^d, как основание некоторой пирамиды, добавлял к нему отдаленную точку и двигал вершины куба вдоль последней координаты так, чтобы полученное множество стало острым. Таким образом, ему удалось получить в R⁴ ОМ, состоящее из 9 точек, а в R⁵ — из 17. В связи с тем, что метод принципиально не меняется при переходе к большим измерениям, grizzly высказал предположение, что размер максимального ОМ можно оценить снизу как N = 2^(d — 1)+1.

Доподлинно неизвестно, что произошло дальше. Судя по всему, Геренчер и Харанги узнали о предположении grizzly и решили доказать его строго. Для этого они рассмотрели сдвиги вершины (d-1)-мерного единичного гиперкуба вдоль трех различных типов координат и нашли такие значения параметров сдвига, при которых куб переходил в острое множество. Затем, как они говорят в статье, математики также добавили «вишенку на торте» — точку, находящуюся на некотором отдалении от куба. В своей работе они ссылаются на форум, где была высказана гипотеза, и упоминают, что «математический энтузиаст пожелал остаться анонимным».

Пауль Эрдёш — один из самых известных математиков XX века. За свою жизнь он написал более 1500 статей, из которых около пятисот в соавторстве. Такая высокая продуктивность привела к возникновению полушутливого понятия о числе Эрдёша — длине кратчайшего пути между математиком и Эрдёшом через совместные статьи. Обычно выдающиеся математики имеют небольшие числа Эрдёша, например, для математика — лауреата филдсовской премии оно в среднем равно трем.

Дмитрий Трунин