Когда «много» начинается с двух, занятие 3

Эта история случилась более 50 лет назад, когда два будущих великих математика Жан-Карло Рота (в то время — студент) и Гилберт Стрэнг (в то время — молодой ученый) решили задачу и написали по ней небольшую статью. Им было ясно, что этот результат мало кого заинтересует, и они опубликовали его в периферийном голландском журнале. В течение 30 лет им действительно никто не заинтересовался, и о нем забыли даже сами авторы. И вдруг, в конце 80-х годов прошлого века, три группы математиков, работающих в разных областях, одновременно пришли к той же самой задаче. Задача следующая (немного упростим фомулировку). Есть два линейных преобразования плоскости. Существует ли метрика (норма) на плоскости, в которой оба эти преобразования являются сжатиями? Для одного преобразования это легко выяснить, ответ был известен давно. А для двух? Оказывается, если научиться решать для двух преобразований, то можно решить и для любого конечного числа. Главная проблема — справиться с двумя. Задача эта нашла огромное количество приложений: дискретная математика, теория чисел, динамические системы, фракталы, … Мы рассмотрим некоторые приложения в курсе. А как решить? В 2000 г. Блондель и Цициклис доказали, что эта задача NP сложна, т.е. хороших методов для нее, видимо, нет. Но впоследствии выяснилось, что все не так плохо. С помощью выпуклой геометрии и многогранников такие методы были построены.