Суровый канадский лесоруб

Вдали от столичной суеты

Возьмём квадратную матрицу размера n x n и заполним её случайным образом плюс-минус единицами. Определитель такой матрицы - целое число между -n! и +n!. С какой вероятностью он окажется нулём? Ответ зависит от n: при n=1 ответ - нуль, при n=2 эта вероятность равна 1/2, если n=3, то посчитайте сами ;-)

Для произвольного n матрица будет вырожденной, если у неё есть две одинаковых строки или два одинаковых столбца. Это случается с вероятностью n(n-1) x 2^-n(1+...), - многоточие здесь и ниже означает выражение, стремящееся к нулю при больших n (в данном случае это вероятность одновременного наступления двух таких маловероятных событий). Верно ли, что это - правильная асимптотика, и ответ имеет вид (1/2+...)ⁿ? Казалось бы, с чего? помимо перечисленных причин для вырождения, есть масса более сложных линейных зависимостей, неужели они все вместе дают пренебрежимую поправку?

Задачу начали ковырять больше полувека назад, - первым (нетривиальным!) результатом было то, что вероятность убывает до нуля с ростом n. После этого почти тридцать лет было потрачено на то, чтобы понять, с какой скоростью она убывает: прорывной результат был получен в 1995-м и утверждал, что вероятность убывает быстрее, чем некоторая убывающая геометрическая прогрессия. Но какая прогрессия! Было доказано, что ответ стремится к нулю не медленнее, чем (0.999+...)ⁿ. Константу 0.999 удалось затем уменьшить, сначала до 0.75, потом до корня из двух пополам, 0.7071...

И только совсем недавно, в 2018-м, удалось-таки додавить жадину и доказать, что в самом деле там, где должна стоять не больше, чем половина, можно поставить ровно половину. Комментарии относительно того, с какими нетривиальными явлениями это связано, можно найти у Гиля Каллаи, чей пост я и попытался воспроизвести выше.

Для читателей "ХВ" будет небезынтересно узнать, кто же этот супермэн, которого спящая царевна-матрица ждала 50 лет.

Знакомьтесь: Константин Тихомиров, assistant professor (ассистент? скорее старший преподаватель по российским понятиям, короче, под-доцент) в Georgia Tech, Грузинский Политех. Примечательно, как Костя туда попал:

• Диплом - 2008, Самарский (б. Куйбышевский) университет, прикладная математика и информатика;
• к.ф.-м.н., 2011, Самарский ГУ (что означает, что он защищался в Воронеже, - я не понимаю, Воронеж - тоже заметное место на математической карте России).
• Ph. D., 2016, University of Alberta, Canada. Я затрудняюсь подобрать соответствующий российский эквивалент. Омский универ? Томский? Красноярский?
• Постдок в Принстоне (2016-2018), визитёр-постдок в Беркли (4 месяца).

Ни мехматов, ни вышек, ни гарвардов в анамнезе. Дерзайте, девушки и юноши!