О свободных полугруппах целочисленных матриц и связанных с ними вопросах

Доклад посвящён алгоритмической задаче проверки, является ли данный набор квадратных целочисленных матриц базисом свободной полугруппы. Доказано, что эта задача алгоритмически неразрешима уже для матриц размера $3\times 3$, а для матриц $2\times 2$ этот вопрос открыт. Эта задача также тесно связана с вопросом Эрдёша–Грэхэма о плотностях орбит целочисленных линейных функций одной переменной, который возник из исследования существования латинских квадратов чётных размеров, и которая также остаётся нерешённой уже более 40 лет. Будет рассказано о результатах докладчика в этих двух направлениях.