Аннотация:
Доклад будет посвящён двум задачам из разных областей, которые сравнительно просто формулируются, остаются нерешёнными уже несколько десятилетий и оказываются тесно связанными друг с другом.
Первый вопрос относится к арифметической комбинаторике и возник в 1970-х годах в связи с решением проблемы Эйлера о существовании латинских квадратов нечётных размеров. А именно, пусть f1, f2, ..., fk — набор линейных функций с неотрицательными целыми коэффициентами, и пусть n - некоторое натуральное число. При каких условиях на набор функций, множество всех образов числа 1, к которому итерированно применяются функции f1, f2, ..., fk, имеет положительную плотность как подмножество натурального ряда? Этой задачей занимались такие известные специалисты как П.Эрдёш, Д.Кнут, Р.Радо, Р.Ривест, Д.Кларнер и Д.Копперсмит, однако полного её решения до сих пор не найдено.
Другая задача относится к области алгоритмических проблем в алгебре. В 1991 году Д.Кларнер, Ж.-К. Бирже и У.Саттерфилд рассмотрели задачу проверки, является ли данный на вход набор квадратных целочисленных матриц базисом свободной полугруппы. Они доказали, что эта задача алгоритмически неразрешима для размера 3x3 и больше, а вот для матриц 2x2 этот вопрос с тех пор открыт. Интересным образом, для большого числа других алгоритмических вопросов про полугруппы матриц, в случае размера 3x3 также установлена неразрешимость, а для размера 2x2 проблема является открытой.
Будет рассказано о том, почему эти задачи связаны, а также о результатах, полученных в направлении их решения.
Обратная связь: