Об орбитах наборов линейных функций и свободных полугруппах целочисленных матриц (Алексей Таламбуца)

Математический семинар ФКН Доклад посвящён двум задачам из разных областей, которые сравнительно просто формулируются, остаются нерешёнными уже несколько десятилетий и оказываются тесно связанными друг с другом. Первый вопрос относится к арифметической комбинаторике и возник в 1970-х годах в связи с решением проблемы Эйлера о существовании латинских квадратов нечётных размеров. А именно, пусть f1, f2, ..., fk — набор линейных функций с неотрицательными целыми коэффициентами. При каких условиях на набор функций, множество всех образов числа 1, к которому итерированно применяются функции f1, f2, ..., fk, имеет положительную плотность как подмножество натурального ряда? Этой задачей занимались такие известные специалисты как П. Эрдёш, Д. Кнут, Р. Радо, Р. Ривест, Д. Кларнер и Д. Копперсмит, однако полного её решения до сих пор не найдено. Другая задача относится к области алгоритмических проблем в алгебре. В 1991 году Д. Кларнер, Ж.-К. Бирже и У. Саттерфилд рассмотрели задачу проверки, является ли данный на вход набор квадратных целочисленных матриц базисом свободной полугруппы. Они доказали, что эта задача алгоритмически неразрешима для размера 3x3 и больше, а вот для матриц 2x2 этот вопрос с тех пор открыт. Интересным образом, для большого числа других алгоритмических вопросов про полугруппы матриц, в случае размера 3x3 также установлена неразрешимость, а для размера 2x2 проблема является открытой. Будет рассказано о том, почему эти задачи связаны, а также о результатах, полученных в направлении их решения. Докладчик: Алексей Таламбуца, доцент департамента больших данных и информационного поиска ФКН. 9 июня 2023 Математический семинар ФКН: https://cs.hse.ru/seminatfkn/ ФКН: https://cs.hse.ru Подписывайтесь на нас в социальных сетях: 📍 https://vk.com/cshse/ 📍 https://t.me/fcs_hse 📍 https://twitter.com/CS_HSE/