Как математик Хао Хуанг доказал «Гипотезу чувствительности»

Он сделал то, чего другие не смогли

Хао Хуан, доцент математики в Университете Эмори в Атланте, доказал математическую идею, называемую гипотезой чувствительности, которая в невероятно грубых терминах утверждает, что вы можете изменять входные данные для функции без изменения выходных данных (это ее чувствительность).

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

Что примечательно в доказательстве Хуанга, по мнению других экспертов в названной области, это не только то, что Хуан справился с задачей, но и элегантный и простой способ, которым он все сделал. Его доказательство не было официально проверено или опубликовано ни в одном математическом журнале. Но вскоре после того как Хуан обнародовал его 1 июля, его коллеги быстро приняли это как факт.

«Всякий раз, когда есть такое объявление, - писал в своем блоге специалист по компьютерным наукам в Остине Скотт Ааронсон, - примерно в 99 % случаев это либо неверное доказательство, либо, во всяком случае, это слишком сложно для посторонних, чтобы оценить решение. Это один из оставшихся 1 % случаев. Я сильно уверен, что доказательства верны. Почему? Потому что я прочитал и понял это. Это заняло у меня около получаса».

Райан О'Доннелл, профессор компьютерных наук, изучающий теорию чисел в Университете Карнеги-Меллона в Питтсбурге, отметил, что доказательство Хуанга можно обобщить в одном твите:

«Что на самом деле доказал Хуан? Для простоты представьте трехмерный куб с гранями, каждая из которых имеет длину 1 единицу. Если вы поместите этот куб в трехмерную систему координат (то есть, у него есть измерения в трех направлениях), один угол будет иметь координаты (0,0,0), а следующий за ним может быть (1,0,0), один над ним может быть (0,1,0) и так далее. Вы можете взять половину углов (четыре угла), не имея пары соседей: (0,0,0), (1,1,0), (1,0,1) и (0,1,1). Вы можете показать это, посмотрев на куб, но мы также знаем это, потому что все углы отличаются более чем на одну координату».

Суть гипотезы

«Гипотеза о чувствительности заключается в том, чтобы определить, сколько у фигуры "соседей", когда вы берете более половины углов многомерного куба или гиперкуба, - сказал математик Еврейского университета Гил Калай. - Координаты гиперкуба можно записать в виде строк 1 и 0, где число измерений - это длина строки. Например, для 4-мерного гиперкуба имеется 16 различных точек, что означает 16 различных строк из 1 и 0, длина которых составляет четыре цифры.

Теперь выберите половину плюс 1 отдельную точку в гиперкубе (для четырехмерного гиперкуба это означает, что нужно выбрать девять - или 8 + 1 - разных точек из 16.

Из этого меньшего набора найдите точку с наибольшим количеством соседей - какое минимальное количество соседей может быть? (Соседи отличаются только одним числом. Например, 1111 и 1110 являются соседями, потому что вам нужно поменять местами только одну цифру, чтобы превратить первую во вторую).

Хуан доказал, что этот угол должен иметь как минимум столько же соседей, сколько квадратный корень из числа цифр - в данном случае квадратный корень из 4 - это 2.

Для низких размеров вы можете сказать, что это правда, просто проверив. Например, не сложно проверить 16 координат куба (или «строки») для соседей. Но каждый раз, когда вы добавляете измерение в куб, количество строк удваивается. Так что проблему очень сложно проверить быстро.

Набор строк длиной 30 цифр - координаты углов 30-мерного куба - содержит более 1 миллиарда различных строк, то есть куб имеет более 1 миллиарда углов. Со строками длиной в 200 цифр их число превышает миллиард. Это миллион миллиардов миллиардов миллиардов миллиардов миллиардов, или 1, за которым следуют 60 нулей.

Вот почему математики любят доказательства: они показывают, что что-то верно в каждом случае, а не только в простых.

«Если n равно миллиону - это означает, что у нас есть строки длиной 1 миллион - тогда гипотеза состоит в том, что если вы возьмете 2 ^ 1 000 000-1 и добавите 1, то есть строка, которая имеет 1000 соседей - квадратный корень из миллиона», - сказал Калай.

Заключение

«Последнее значительное продвижение в гипотезе о чувствительности произошло в 1988 году, - заметил Калай. - Когда исследователи доказали, что одна строка должна иметь хотя бы логарифм n соседей. Это намного меньшее число; логарифм 1 000 000 - только 6. Таким образом, доказательство Хуанга только что обнаружило, что по крайней мере 994 других соседей там еще есть».