О кодах, решетках и экспандерах

Тезисы из выступления Й.Б. на семинаре в инстутите Вейцмана:

1. Новую констукцию придумать очень трудно. Нужно подобрать и использовать для приложений подходящую конструкцию из числа известных теоретической математике.

Например, если вы хотите строить решетку как подфактор стандартной решетки -- подфактропространства в математике возникают, как пространства когомологий. Если нужен граф -- можно профакторизовать дерево Брюа-Титса по арифметической подгруппе, и т.д.

Конструкции таких объектов выглядят абстрактными, но на самом деле могут быть очень эффективно имплементированы на компьютере (нужно, конечно, подумать, как это правильно сделать, но если подумать, это получится).

2. Есть разные количественные измерители неформально ощущаемого качества объектов. Например, размер конечного набора чисел (x₁, …, x_n) можно вычислять как

а. максимум абсолютных величин x_i (l_∞-норма),
б. среднее арифметическое абсолютных величин x_i (l₁-норма),
в. квадратный корень из среднего арифметического квадратов абсолютных величин x_i (l₂-норма).

Естественными с прикладной точки зрения выглядят варианты а. и б., но математически может быть гораздо удобнее работать с в. Морально, а., б., и в. по-разному измеряют одно и то же. Следует выбрать измеритель, предпочтительный с математической точки зрения (т.е., в.).

Например, вычисление длины кратчайшего вектора решетки -- NP-полная задача. Не нужно с ней связываться. Правильный измеритель качества решетки должен как-то определяться в терминах тета-функций, что математически гораздо лучше.

При правильном выборе измерителей качества, доказательство высокого качества объектов арифметического и т.п. происхождения (как в п. 1) является несложной математической задачей. Можно ожидать, в частности, что такие объекты лучше случайных (случайные тоже довольно хороши, но выбрать конкретный объект, похожий на случайный, может быть трудно).