Там вообще что-то происходит, в математике?
Хорошо забытое старое
Собственные векторы и собственные значения – исключительно полезные алгебраические понятия, через них особенно удобно описывать многие объекты.
Математики и физики давным-давно с ними работают. В этом году три физика, изучавших нейтрино, наткнулись на новое тождество в этой области, которое сильно упрощало их работу. Они обратились к Теренсу Тао за помощью, и тот сперва не поверил, что такая красивая формула в исхоженной области математики до сих пор не замечена. Однако никаких ее следов не нашел, и они вчетвером написали статью с доказательством и обобщениями этого тождества. После публикации все же выяснилось, что ее уже несколько раз открывали и забывали. Теперь физики знают, куда ее приложить, и она больше не забудется.
Мораль: идеи в математику приходят из реального мира, и могут потеряться, если в реальном мире не нашлось им применения.
Чувствительные функции
Булевы функции — мощный инструмент для описания компьютерных схем. Они всегда дают на выходе только 0 или 1; и их входные переменные тоже могут принимать только значения 0 или 1.
Так может быть устроено предварительное тестирование при приеме на работу. Вы заполняете анкету, отвечая на вопросы «да» или «нет» (для булевой функции – 0 или 1), вопросов много (у булевой функции много переменных). Программа (булева функция) выдает ответ: да или нет, допустили вас до личного собеседования или отсеяли на этом этапе (это один выходной бит булевой функции). В этом примере хорошо, если функция не сильно чувствительна. Скажем, два человека на 99 вопросов ответили одинаково, а на 1 по-разному: даже если мы не знаем, как устроена функция, мы ожидаем, что она даст одинаковый ответ на их запросы. Сильно чувствительная функция может давать разные ответы при изменении любого бита; работодателю трудно оценивать претендентов.
Можно и так сказать: чувствительность – это показатель (один из многих) сложности булевой функции.
С 1992 года известна гипотеза о чувствительности: существует постоянная C такая, что для любой булевой функции f
Список попыток доказать эту гипотезу напоминает список «кто есть кто в современной теоретической информатике». В этом году в коротенькой статье ее доказал Hao Huang. Специалисты восторгаются изяществом этого доказательства.
Раскраски графов
Многие слышали про задачу о четырех красках: что можно раскрасить в 4 цвета плоскую карту так, что соседние страны будут разных цветов. Эта задача сводится к задаче о раскраске графов: каждую страну можно обозначить вершиной графа, а раскрашивать требуется вершины, они должны быть разного цвета, если соединены ребром (если у стран есть общая граница). Результат коротко формулируется так: «хроматическое число любого планарного графа не больше 4».
Раскраски графов очень важны для приложений, и сейчас речь пойдет о раскраске произведения графов.
Что это? (На примере.) В музыкальной школе будет концерт дуэтов. Есть два графа: один граф – это ученики, две вершины соединены ребром, если ученики ладят друг с другом и могут выступать вместе. Другой граф – музыкальные инструменты, две вершины соединены ребром, если имеются ноты для такого инструментального дуэта. Произведение этих двух графов – тоже граф, его вершины – пары (ученик, инструмент). Две вершины соединяются ребром, если в исходных графах были связаны и ученики, и инструменты.
Более 50 лет просуществовала гипотеза о том, что хроматическое число произведения графов не может быть меньше хроматического числа любого сомножителя-графа. В этом году ее опроверг Ярослав Шитов, построив контрпример.
Быстро как только можно
Когда мы умножаем N-значное число на N-значное в столбик, то мы каждую цифру одного числа умножаем на каждую цифру второго – всего N² произведений; и еще несколько суммирований, которые по меркам компьютеров гораздо дешевле. Показатель N² постепенно улучшали. В этом году достигнута граница N log (N) простых операций. Существует гипотеза, что это нижняя граница, быстрее умножить не получится, но она до сих пор не доказана.
Сумма трех кубов
Есть прогресс в разложении натуральных чисел в сумму трех кубов. В этом году построили разложение для 33
И в этом же году для 42:
Самое маленькое число, для которого пока не придумали разложения в сумму кубов – 114.
Прорыв в гипотезе Коллатца
Об этом результате Теренса Тао я недавно рассказывала
Это был вольный пересказ статьи из журнала Quantamagazine