| Успехи математических наук |
|
|
|
|
|
Эта публикация цитируется в 11 научных статьях (всего в 11 статьях) О тензорном ранге умножения в конечных расширениях конечных полей и о связанных с этим вопросах алгебраической геометрии С. Баллеa, Ж. Пьетанb, М. Рамбоc, У. Рандриамбололонаd, Р. Ролланa, Ж. Шоминe a Aix-Marseille Université, CNRS, Centrale Marseille, Institut de Mathématiques de Marseille, Marseille, France b Équipe en émergence Sécurité-Défense, Conservatoire National des Arts et Métiers, Paris, France c LTCI, Télécom ParisTech, Institut Polytechnique de Paris, Paris, France d Laboratoire de Cryptographie, Agence Nationale de Sécurité des Systèmes d'Information, Paris, France e Laboratoire Géométrie Algébrique et Applications à la Théorie de l'Information, Université de la Polynésie Française, Tahiti, France
Англоязычная версия:
Russian Mathematical Surveys, 2021, Volume 76, Issue 1, Pages DOI: https://doi.org/10.1070/RM9928 
Реферативные базы данных:
      1. ВведениеЭта статья предлагает обзор результатов о тензорном ранге умножения в конечных полях. Она обновляет предыдущий обзор [25], опубликованный около пятнадцати лет назад. Глубокие улучшения, достигнутые с тех пор, потребовали полной переработки обзора, освещающей современное состояние этой области. В частности, мы обсуждаем новые методы, разработанные в последние годы. Возрастающая важность данной области привлекла внимание многих математиков, информатиков и программистов, которые развили новые идеи и получили новые результаты. Кроме того, мы описываем целый ряд неочевидных ошибок и их исправлений, свидетельствующих о ходе развития данной области и об активности её исследователей. Конечные поля являются важным разделом математики. Они возникают и во многих прикладных областях, особенно в областях, связанных с теорией информации. В частности, одна из центральных проблем – это проблема сложности умножения в конечных полях. Она является частью теории алгебраической сложности, для которой наилучшей общей ссылкой является монография [35]. Оказывается, что изучение этой проблемы поднимает немало вопросов в теории чисел и алгебраической геометрии. Примечательно, что оно обнаружило глубокие связи между этими различными областями. И одна из целей данной статьи – выявление этих связей и относящихся к ним современных открытых проблем. В то же время мы доказываем и некоторые новые, ещё не опубликованные результаты. Опишем нашу проблему более точно: предположим, что имеется алгоритм умножения в конечном поле ${\mathbb F}_q$ и мы хотим построить алгоритм умножения в расширении ${\mathbb F}_{q^n}$, который наименее трудоёмок в смысле числа операций в ${\mathbb F}_q$. Заметим, что с этой точки зрения умножение в ${\mathbb F}_{q^n}$ есть перемножение двух многочленов степени $<n$ с коэффициентами в ${\mathbb F}_q$. Мы выделяем в алгоритме два типа операций: те, что линейны относительно перемножаемых переменных, и те, что билинейны относительно двух переменных. Точнее, пусть $\mathcal{B}=\{e_1,\dots,e_n\}$ – базис поля ${\mathbb F}_{q^n}$ над ${\mathbb F}_q$. Если $x=\displaystyle\sum_{i=1}^{n}x_ie_i$ и $y=\displaystyle\sum_{i=1}^{n}y_ie_i$, то прямое вычисление даёт
$$
\begin{equation}
z=xy=\sum_{h=1}^{n}z_he_h= \sum_{h=1}^{n}\biggl(\,\sum_{i,j=1}^{n}t_{ijh}x_ix_j\biggr)e_h,
\end{equation}
\tag{1}
$$
где а $t_{ijh}\in {\mathbb F}_q$ – константы. Тогда проблема алгебраической сложности заключается в нахождении минимального числа элементарных операций в ${\mathbb F}_q$, требуемых для вычисления произведения двух элементов $x,y \in {\mathbb F}_{q^n}$. Можно выделить следующие операции:
Билинейная сложность алгоритма умножения определяется числом использованных билинейных умножений. Заметим, что билинейная сложность – это не полная сложность алгоритма и нужно также учитывать сложность линейной части алгоритма. Однако полезно иметь низкую билинейную сложность. Действительно, она вносит намного более заметный вклад во время работы алгоритма, чем скалярная сложность. Умножение на известный фиксированный элемент может обрабатываться особым образом и требовать меньше времени, чем умножение в общем случае (например, в тривиальных случаях, когда константы – это $0$ или $1$, или когда используются таблицы предвычислений). Это подтверждается конкретными ситуациями в криптографии. Известно, что для вычисления спариваний требуется много умножений. Например, Н. Эстибалс в своей диссертации [54; с. 177–179] приводит алгоритм, реализация которого значительно сокращает время счёта благодаря формуле умножения, полученной Р. Барбулеску, Ж. Детри, Н. Эстибалсом и П. Циммерманом в [28], билинейная сложность которой равна $11$ вместо $12$. Как будет объяснено в следующем пункте, эта билинейная сложность соответствует рангу тензора алгоритма умножения в ${\mathbb F}_{q^n}$, рассматриваемого как векторное пространство над ${\mathbb F}_{q}$. Поэтому, независимо от практической проблемы сложности умножения, возникает теоретическая математическая задача нахождения ранга этого тензора. Данная работа посвящена изучению этой проблемы тензорного ранга умножения в конечных полях. Мы приведем результаты, полученные в этой части теории алгебраической сложности и теории чисел, и обсудим другие относящиеся к этой тематике вопросы. 1.1. Тензорный ранг и алгоритм умноженияНапомним понятия алгоритма умножения и его билинейной сложности. Определение 1.1. Пусть $K$ – поле, а $E_0,\dots,E_s$ – конечномерные $K$-векторные пространства. Ненулевой элемент $t\in E_0 \otimes \cdots \otimes E_s$ называется элементарным (или неразложимым) тензором или тензором ранга 1, если его можно записать в виде $t=e_0 \otimes \cdots \otimes e_s$ для некоторых $e_i \in E_i$. Более общо, рангом произвольного $t\in E_0 \otimes \cdots \otimes E_s$ называется минимальная длина разложения $t$ в сумму элементарных тензоров. Определение 1.2. Если – $s$-линейное отображение, то $s$-линейной сложностью отображения $\alpha$ называется тензорный ранг элемента естественным образом определяемого величиной $\alpha$, где $E_i^{\vee}$ обозначает двойственное пространство пространства $E_i$ как векторного пространства над $K$ для каждого $i$. В частности, $2$-линейная сложность называется билинейной сложностью. Определение 1.3. Пусть $\mathcal A $ – конечномерная $K$-алгебра. Обозначим через билинейную сложность отображения умножения рассматриваемого как $K$-билинейное отображение. В частности, если $\mathcal{A}=\mathbb{F}_{q^m}$ и $K=\mathbb{F}_q$, то полагаем Конкретнее, $\mu(\mathcal A/K)$ – наименьшее целое число $n$ такое, что существуют линейные формы $\phi_1,\dots,\phi_n, \psi_1,\dots,\psi_n\colon\mathcal A \to K$ и элементы $w_1,\dots,w_n \in \mathcal A$ с тем свойством, что для всех $x,y\in \mathcal A$ выполняется равенство
$$
\begin{equation}
xy=\phi_1(x)\psi_1(y)w_1+\cdots+\phi_n(x)\psi_n(y)w_n;
\end{equation}
\tag{2}
$$
действительно, такое выражение – это то же самое, что разложение
$$
\begin{equation}
t_M=\sum_{i=1}^{n}w_i\otimes \phi_i\otimes \psi_i \in \mathcal{A} \otimes \mathcal{A}^{\vee} \otimes \mathcal{A}^{\vee}
\end{equation}
\tag{3}
$$
для тензора умножения алгебры $\mathcal{A}$. Определение 1.4. Алгоритмом умножения длины $n$ для $\mathcal A/K$ называется набор линейных форм $\phi_i$, $\psi_i$ и элементов $w_i$ такой, что выполнено (2) или, эквивалентно, имеет место тензорное разложение для тензора умножения алгебры $\mathcal{A}$. Такой алгоритм называется симметричным, если $\phi_i=\psi_i$ для всех $i$ (это возможно, только если $\mathcal A$ коммутативна). Поэтому, когда $\mathcal{A}$ коммутативна, интересно изучать минимальную длину симметричного алгоритма умножения. Определение 1.5. Пусть $\mathcal A$ – конечномерная коммутативная $K$-алгебра. Симметричная билинейная сложность – это минимальная длина симметричного алгоритма умножения. В частности, если $\mathcal{A}=\mathbb{F}_{q^m}$ и $K=\mathbb{F}_q$, то полагаем Приведём некоторые основные свойства этих величин, взятые из [74; лемма 1.10]. Лемма 1.6. (a) Если $\mathcal{A}$ – конечномерная $K$-алгебра, а $L$ – расширение поля $K$, причём $\mathcal{A}_L=\mathcal{A}\otimes_K L$ рассматривается как $L$-алгебра, то Более того, если $\mathcal{A}$ коммутативна, то справедливо также неравенство (b) Если $\mathcal{A}$ – конечномерная $L$-алгебра, где $L$ – расширение поля $K$, то она может также рассматриваться как $K$-алгебра, причём
$$
\begin{equation*}
\mu(\mathcal{A}/K)\leqslant\mu(\mathcal{A}/L)\mu(L/K).
\end{equation*}
\notag
$$
Более того, если $\mathcal{A}$ коммутативна, то справедливо также неравенство
$$
\begin{equation*}
\mu^{\rm sym}(\mathcal{A}/K)\leqslant \mu^{\rm sym}(\mathcal{A}/L)\mu^{\rm sym}(L/K).
\end{equation*}
\notag
$$
(c) Если $\mathcal{A}$ и $\mathcal{B}$ – две конечномерные $K$-алгебры, то
$$
\begin{equation*}
\mu(\mathcal{A}\times\mathcal{B}/K)\leqslant \mu(\mathcal{A}/K)+\mu(\mathcal{B}/K).
\end{equation*}
\notag
$$
Более того, если $\mathcal{A}$ и $\mathcal{B}$ коммутативны, то справедливо также неравенство
$$
\begin{equation*}
\mu^{\rm sym}(\mathcal{A}\times\mathcal{B}/K)\leqslant \mu^{\rm sym}(\mathcal{A}/K)+\mu^{\rm sym}(\mathcal{B}/K).
\end{equation*}
\notag
$$
(d) Если $\mathcal{A}$ и $\mathcal{B}$ – две конечномерные $K$-алгебры, то Более того, если $\mathcal{A}$ и $\mathcal{B}$ коммутативны, то справедливо также неравенствоВ частности, особенно полезна следующая лемма И. Шпарлинского, М. Цфасмана и С. Влэдуца (см. [80; лемма 1.2]). На самом деле правое неравенство леммы было сформулировано уже в первоначальной работе Д. В. Чудновского и Г. В. Чудновского [43], так что новым вкладом И. Шпарлинского, М. Цфасмана и С. Влэдуца является левое неравенство. Оно пригодится нам при рассмотрении асимптотической сложности в лемме 8.1. На самом деле то же справедливо для симметричной сложности. Доказательство.$\!\!\!$ Левые неравенства $\mu_{q}(n)\leqslant\mu_q(mn)$ и $\mu^{\rm sym}_{q}(n)\leqslant\mu^{\rm sym}_q(mn)$ следуют из включения $\mathbb{F}_{q^n}\subseteq\mathbb{F}_{q^{mn}}$. Далее, для вывода правых неравенств $\mu_q(mn)\leqslant \mu_q(m)\mu_{q^m}(n)$ и $\mu^{\rm sym}_q(mn)\leqslant \mu^{\rm sym}_q(m)\mu^{\rm sym}_{q^m}(n)$ применим лемму 1.6, (b), при $\mathcal{A}=\mathbb{F}_{q^{mn}}$, $L=\mathbb{F}_{q^m}$ и $K=\mathbb{F}_q$. 1.2. Содержание обзораВ разделе 2 мы излагаем классические результаты, опираясь на подход, использующий умножение при помощи полиномиальной интерполяции. В разделе 3 приводится исторический очерк результатов, полученных в пионерских работах Д. В. и Г. В. Чудновскими [43] и позднее И. Шпарлинским, М. Цфасманом и С. Влэдуцом [80]. В частности, мы приводим исходный алгоритм. Этот современный подход использует интерполяцию на алгебраических кривых, определённых над конечным полем. Указанный подход (мы описываем его первые успехи, а также подводные камни, с которыми столкнулись первооткрыватели) позволил С. Балле [6] дать первое полное доказательство линейности билинейной сложности умножения. В разделе 4 описывается подход к билинейной сложности, основанный на теории кодирования, и объясняется связь между билинейной сложностью умножения и так называемыми (точными) суперкодами или, что эквивалентно, дружественными умножению кодами в терминологии некоторых авторов. Затем в разделе 5 мы приводим различные обобщения исходного алгоритма Д. В. и Г. В. Чудновских и, в частности, наиболее успешную к настоящему времени версию алгоритма типа Чудновского–Чудновского, принадлежащую У. Рандриамбололоне [74]. В этом разделе объясняются связи с алгебраической геометрией. В разделе 6 наша цель – найти семейства алгебраических кривых, адаптированных к алгоритму Чудновского–Чудновского (башни алгебраических полей функций, семейства кривых Шимуры, а также их уплотнение и спуск). Раздел 7 посвящен проблеме существования и нахождения дивизоров, определяющих пространства Римана–Роха, связанные с алгоритмом Чудновского–Чудновского (проблема нульмерных дивизоров и $2$-кручения). В разделе 8 мы напоминаем известные результаты об асимптотических границах для симметричной и асимметричной билинейной сложности, полученные за последние тридцать лет. Далее в разделе 9 мы приводим равномерные границы для симметричной и асимметричной билинейной сложности. Наконец, в разделе 10 мы излагаем методы эффективного построения алгоритмов билинейного умножения в конечных полях. 2. Старые классические результатыПусть – неприводимый приведённый многочлен степени $n$ с коэффициентами в поле $F$. Пусть
$$
\begin{equation*}
R(u)=\sum_{i=0}^{n-1}x_iu^i\quad\text{и}\quad S(u)=\sum_{i=0}^{n-1}y_iu^i
\end{equation*}
\notag
$$
– два многочлена степени $\leqslant n-1$, где $x_i$ и $y_i$ – неопределённые коэффициенты. Ч. Фидуччиа и Й. Залкстейн (см. [55], [35; с. 367, предложение 14.47]) изучали общую проблему вычисления коэффициентов произведения $R(u) \times S(u)$ и показали, что там требуется не менее $2n-1$ умножений. Когда поле $F$ бесконечно, алгоритм, на котором эта граница в точности достигается, был ранее предложен А. Тоомом [82]. Ш. Виноград [90] описал все алгоритмы, на которых достигается граница $2n-1$. Более того, в [91] он доказал, что, с точностью до некоторых преобразований, всякий алгоритм вычисления коэффициентов многочлена $R(u) \times S(u)\!\! \mod P(u)$, имеющий билинейную сложность $2n-1$, с необходимостью вычисляет коэффициенты многочлена $R(u) \times S(u)$ и, следовательно, использует один из алгоритмов, описанных в [90]. Эти алгоритмы используют интерполяционную технику и не могут работать, если мощность поля $F$ меньше $2n-2$. Подытоживая, имеем следующий результат. Теорема 2.1. Если мощность поля $F$ меньше $2n-2$, то каждый алгоритм вычисления коэффициентов многочлена $R(u) \times S(u)\!\! \mod P(u)$ имеет билинейную сложность $>2n-1$. Применяя результаты Ш. Винограда и Х. Де Гроота [46] и теорему 2.1 к умножению в конечном расширении $\mathbb{F}_{q^n}$ конечного поля $\mathbb{F}_q$, получаем следующее утверждение. Теорема 2.2. Билинейная сложность $\mu_q(n)$ умножения в конечном поле $\mathbb{F}_{q^n}$ над $\mathbb{F}_q$ удовлетворяет неравенству причём равенство выполняется тогда и только тогда, когда Этот результат не даёт никакой верхней границы для $\mu_q(n)$, когда $n$ велико. А. Лемпел, Г. Серусси и Ш. Виноград [64] доказали, что $\mu_q(n)$ обладает квазилинейной верхней границей. Точнее, справедливо следующее утверждение. Теорема 2.3. Билинейная сложность умножения в конечном поле $\mathbb{F}_{q^n}$ над $\mathbb{F}_q$ удовлетворяет неравенству где $f_q(n)$ – очень медленно растущая функция, рекурсивно определённая равенством для $n\geqslant 4$ и $q\geqslant 2$. При $n<4$ функция $f_q(n)$ определена следующим образом: Кроме того, распространяя и более эффективно используя технику, развитую в [34], Н. Бшоути и М. Камински показали, что при $q \geqslant 3$. Доказательство вышеприведённой нижней границы сложности прямых алгоритмов для перемножения многочленов основано на анализе матриц Ганкеля, представляющих билинейные формы, определяемые линейными комбинациями коэффициентов произведения многочленов.3. Подход с использованием алгебраических кривыхМы видели в предыдущем разделе, что если количество точек основного поля слишком мало, то мы не можем выполнять умножение интерполяционным методом Ш. Винограда. Д. В. и Г. В. Чудновские [43] разработали алгоритм, в котором интерполяция производится на (схемных замкнутых) точках алгебраической кривой над основным полем с достаточным количеством рациональных точек. Заметим, что идея использования отображения значения на точках алгебраической кривой вдохновляется теорией кодов Гоппы, введённых В. Гоппой [59], [60], которая развивалась М. Цфасманом [83] и М. Цфасманом, С. Влэдуцом и Т. Цинком [86]. Мы будем обозначать этот алгоритм умножения Чудновского и Чудновского через АУЧЧ. Используя этот алгоритм, Д. В. и Г. В. Чудновские утверждали, что билинейная сложность умножения в конечных расширениях конечного поля асимптотически линейна, однако позднее И. Шпарлинский, М. Цфасман и С. Влэдуц [80] заметили, что Чудновские доказали только, что величина $m_q=\liminf_{k \to \infty}(\mu_q(k)/k)$ ограничена, что не позволяет доказать линейность. Чтобы доказать линейность, надо также доказать, что величина $M_q=\limsup_{k \to \infty}(\mu_q(k)/k)$ ограничена, что и было основной целью работы [80]. Однако И. Каскудо, Р. Крамер и Ч. Син недавно обнаружили ошибку в доказательстве И. Шпарлинского, М. Цфасмана и С. Влэдуца. К сожалению, эта ошибка, как мы подробно объясняем в данном разделе, повлияла также на их улучшенные оценки величины $m_q$. После вышеописанных пионерских исследований С. Балле [6] (см. также [5]) получил первые верхние границы для $\mu_q(n)$, равномерные по $q$. Так как АУЧЧ очевидным образом симметричен, эти первые равномерные оценки также относятся к $\mu^{\rm sym}_q(n)$. Более того, эти оценки, в которых удается избежать аналогичных ошибок, позволили в то же время доказать линейность билинейной сложности умножения в конечных расширениях конечного поля, поскольку из них очевидным образом следует, что величина $M_q$ конечна. Впоследствии были получены кардинальные улучшения: С. Балле [5], [6] предложил простые численные условия на алгебраические кривые произвольного рода $g$, дающие достаточные условия для применимости АУЧЧ (существование точек определённой степени, неспециальных дивизоров степени $g-1$), обобщающие результат А. Шокроллахи [79] для эллиптических кривых; С. Балле [5], [6] впервые использовал башни алгебраических полей функций и их уплотнения [8]; С. Балле и Р. Роллан [24] впервые использовали точки высших степеней; С. Балле и Р. Роллан [24] ввели понятие спуска над $\mathbb{F}_q$ поля определения $\mathbb{F}_{q^2}$ уплотнённой башни, определённой над $\mathbb{F}_{q^2}$, для любого конечного поля $\mathbb{F}_q$ характеристики $p=2$, а в [19] С. Балле, Д. Ле Бриган и Р. Роллан обобщили этот метод для любого конечного поля; С. Балле [9] вывел оптимальные критерии для прямого построения дивизоров, удовлетворяющих требуемым условиям, а Ж. Шомин [41], [42] доказал, что эти критерии всегда выполняются в эллиптическом случае, тем самым улучшив результат А. Шокроллахи [79]; благодаря теореме существования неспециальных дивизоров степени $g-1$ С. Балле и Д. Ле Бриган [18] улучшили достаточные условия для применения АУЧЧ к расширениям произвольных конечных полей; Н. Арно в диссертации [1] впервые использовал локальное разложение, называемое производным отображением значения; опираясь на результат о существовании, полученный С. Балле, К. Ритценталером и Р. Ролланом в [23], С. Балле и Ж. Пьетан [20], [68] начали использовать дивизор нулевой степени и связали его с локальным разложением. Дальнейшие усовершенствования были сделаны М. Сенком и Ф. Озбудаком [39] и У. Рандриамбололоной [74] с использованием локального разложения и точек высших степеней. Эти усовершенствования можно объединить с другими независимыми ингредиентами, также предложенными в [74], а именно с интерполяционной процедурой, допускающей асимметрию и устанавливающей анонсированные И. Шпарлинским, М. Цфасманом и С. Влэдуцом границы для $m_q$ и $M_q$, и рекурсивным подходом к наилучшей билинейной сложности, идея которого была затем также использована в [15]. Наконец, для работы с симметричными сложностями можно использовать две идеи: границы, включающие $2$-кручение [92], [72], [36], [37], и прямое построение дивизоров, удовлетворяющих требуемым условиям [75], [73], [74]. В конечном счёте это позволило в большинстве случаев получить границы Шпарлинского–Цфасмана–Влэдуца и для $m^{\rm sym}_q$ и $M^{\rm sym}_q$, а также вывести другие относящиеся к делу оценки симметричной сложности. 3.1. Алгоритм умножения Д. В. Чудновского и Г. В. Чудновского (АУЧЧ)В этом пункте мы напомним блестящую идею Д. В. Чудновского и Г. В. Чудновского и приведём их основной результат. Сначала сформулируем исходный АУЧЧ, предложенный в 1987 г. в [43]. Теорема 3.1. Пусть Предположим, что $Q$, $P_1,\dots,P_N$ не лежат в носителе дивизора ${\mathcal{D}}$ и что выполняется следующее: (a) отображение значения
$$
\begin{equation*}
Ev_Q\colon \bigg|\begin{aligned} \, \mathcal{L}(\mathcal{D}) &\to \mathbb{F}_{q^n}\simeq F_Q, \\ f & \mapsto f(Q) \end{aligned}
\end{equation*}
\notag
$$
сюръективно (здесь $F_Q$ – поле вычетов поля $Q$); (b) отображение
$$
\begin{equation*}
Ev_{\mathscr P}\colon\bigg|\begin{aligned} \, \mathcal{L}(2\mathcal{D}) & \to \mathbb{F}_{q}^{N}, \\ f & \mapsto (f(P_1),\dots,f(P_{N})) \end{aligned}
\end{equation*}
\notag
$$
инъективно. Тогда Мы приводим этот результат в том виде, в каком он был сформулирован в [43], в терминах билинейной сложности $\mu_q(n)$. Однако более внимательное рассмотрение этого метода показывает, что он дает симметричные алгоритмы, так что заключение выполняется также для симметричной билинейной сложности: 3.2. Линейность билинейной сложности умноженияКак мы уже видели, И. Шпарлинский, М. Цфасман и С. Влэдуц [80] сделали много интересных замечаний об АУЧЧ и о билинейной сложности. В частности, они рассматривали асимптотические границы1 билинейной сложности, чтобы доказать линейность этой сложности с помощью АУЧЧ. Следуя этим авторам, определим
$$
\begin{equation*}
M_q= \limsup_{k \to \infty}\frac{\mu_q(k)}{k}\quad\text{и}\quad m_q=\liminf_{k \to \infty}\frac{\mu_q(k)}{k}\,.
\end{equation*}
\notag
$$
Более того, нам также нужно рассматривать симметричные варианты этих величин, которые не рассматривались И. Шпарлинским, М. Цфасманом и С. Влэдуцом, но были впервые введены У. Рандриамбололоной [74] и стали с тех пор в равной степени важными:
$$
\begin{equation*}
M^{\rm sym}_q= \limsup_{k \to \infty}\frac{\mu^{\rm sym}_q(k)}{k} \quad\text{и}\quad m^{\rm sym}_q=\liminf_{k \to \infty}\frac{\mu^{\rm sym}_q(k)}{k}\,.
\end{equation*}
\notag
$$
Ясно, что
$$
\begin{equation*}
M_q\leqslant M^{\rm sym}_q\quad\text{и}\quad m_q\leqslant m^{\rm sym}_q.
\end{equation*}
\notag
$$
Совсем не очевидно, что какое-то из этих значений конечно. Заметим, что если $M_q$ (или $M^{\rm sym}_q$) конечно, то билинейная сложность (соответственно симметричная билинейная сложность) умножения линейна относительно степени расширения, а именно, существует такая константа $C_q\geqslant M_q$ (соответственно $C^{\rm sym}_q\geqslant M^{\rm sym}_q$), что для любого целого $n>1$ выполняется неравенство
$$
\begin{equation*}
\mu_q(n)\leqslant C_qn \quad (\text{соответственно } \mu^{\rm sym}_q(n)\leqslant C^{\rm sym}_qn).
\end{equation*}
\notag
$$
Из теоремы 3.1 Д. В. и Г. В. Чудновские выводят такой результат2 [43; теорема 7.7]: если $q\geqslant 25$ является квадратом, то при $n\to\infty$ имеем
$$
\begin{equation}
\mu^{\rm sym}_q(n)\leqslant 2\biggl(1+\frac{1}{\sqrt{q}-3}\biggr)\cdot n+o(n).
\end{equation}
\tag{4}
$$
Однако, как отметили И. Шпарлинский, М. Цфасман и С. Влэдуц, приведённое доказательство оценки (4) очень схематично и некоторые важные подробности в нём отсутствуют. Это заставило их сомневаться в его справедливости. Точнее, основываясь на работе Я. Ихары [63], Д. В. и Г. В. Чудновские рассмотрели модулярные кривые Шимуры, обладающие асимптотически максимальным числом точек над $\mathbb{F}_q$, и на последнем шаге своего рассуждения они утверждали, что для некоторой заданной константы $C$ и для всех достаточно больших целых $n$ в этом семействе можно выбрать кривые рода $g=Cn+o(n)$. Хотя из [63] следует, что это возможно для бесконечного числа значений $n$, тем не менее Д. В. и Г. В. Чудновским нужно было, чтобы это выполнялось при всех $n$, чего они не обосновали. По этой причине И. Шпарлинский, М. Цфасман и С. Влэдуц разъяснили, что, хотя Д. В. и Г. В. Чудновские сформулировали границу для верхнего предела $M_q$, их доказательство следует считать справедливым только для нижнего предела $m_q$. Но затем И. Шпарлинский, М. Цфасман и С. Влэдуц в [80; Claim, с. 163] дали точное описание семейства кривых Шимуры, удовлетворяющих условиям, требующимся для Д. В. и Г. В. Чудновских, что по существу завершило доказательство соотношения (4). К сожалению, там же И. Шпарлинский, М. Цфасман и С. Влэдуц предложили заменить (4) более точной оценкой и при этом использовали в доказательстве необоснованное рассуждение. Пробел в их доказательстве был обнаружен И. Каскудо, Р. Крамером и Ч. Сином (см. частную переписку 2009 г. и [37; § V]). Они описали этот пробел следующим образом: <<Ошибка в статье [80] 1992 г. содержится в доказательстве леммы 3.3 на с. 161, в абзаце после формул о степенях дивизора. Там написано: “Таким образом, число классов линейной эквивалентности степени $a$, для которых не выполняется либо условие $\alpha$, либо условие $\beta$, не превосходит $D_{b'}+D_b$”. Это неверно; следует умножить $D_b$ на кручение. Отсюда следует, что их доказательство асимптотической границы неверно>>. Заметим, что синтез, позволяющий заполнить пробел в доказательстве Д. В. и Г. В. Чудновских с помощью подхода И. Шпарлинского, М. Цфасмана и С. Влэдуца, возможен, но не очевиден. В любом случае независимым образом, с помощью стратегии Д. В. и Г. В. Чудновских, применённой к первой башне3 Гарсии–Штихтенота [57], для которой достигается граница Дринфельда–Влэдуца, в сочетании с результатом о существовании неспециальных дивизоров степени $g-1$ С. Балле [6] дал первое полное доказательство линейности билинейной сложности умножения. Точнее, это было сделано с помощью непосредственного нахождения верхних оценок для $C^{\rm sym}_q$. С тех пор были выполнены разнообразные исследования по улучшению асимптотических оценок (см. раздел 8) и равномерных оценок (см. раздел 9). 4. Подход через кодыПервоначально, сразу после пионерской работы Д. В. и Г. В. Чудновских [43], И. Шпарлинский, М. Цфасман и С. Влэдуц [80] указали на связь между некоторыми кодами и тензорами умножения. Затем они ввели понятие точных суперкодов (также называемых кодами, дружественными умножению). 4.1. Связь с кодами и асимптотические нижние границыСначала напомним связь между линейными кодами, исправляющими ошибки, и разложением тензоров умножения. Напомним следующее классическое определение. Определение 4.1. Исправляющий ошибки линейный код $C$ над $\mathbb{F}_q$ длины $N$, размерности $n$ и с расстоянием Хэмминга $d$ называется $[N,n,d]_q$-кодом. Скорость $n/N$ такого кода обозначается через $R$, а его относительное минимальное расстояние $d/n$ – через $\delta$. Согласно [80] код можно построить, используя разложение тензора $t_M$ в сумму тензоров ранга 1. Действительно, если где $a_l \in \mathbb{F}_{q^n}^*$, $b_l \in \mathbb{F}_{q^n}^*$, $c_l \in \mathbb{F}_{q^n}$, то определим $\mathbb{F}_q$-линейное отображение
$$
\begin{equation*}
\phi\colon \bigg|\begin{aligned} \, \mathbb{F}_{q^n} & \to \mathbb{F}_q^N, \\ x & \mapsto (a_1(x),\dots,a_N(x)). \end{aligned}
\end{equation*}
\notag
$$
Из [80] вытекает следующий результат. Предложение 4.2. $\mathbb{F}_q$-векторное пространство $\operatorname{Im}\phi$ является $[N,n,d]_q$-кодом, для которого $d\geqslant n$. Следствие 4.3. Любое разложение длины $N$ тензора умножения в конечном поле $\mathbb{F}_{q^n}$ даёт $[N,n,d]_q$-код, для которого $d\geqslant n$. В частности, если $N_q(n)$ – минимальная длина линейного $[N,n,n]_q$-кода, то тензорный ранг $\mu_q(n)$ умножения в конечном поле $\mathbb{F}_{q^n}$ удовлетворяет неравенству $\mu_q(n)\geqslant N_q(n)$. Напомним, что существует непрерывная убывающая функция $\alpha^{\rm lin}_q(\delta)$ на отрезке $[0,1-1/q]$, которая соответствует оценке скорости $R$ линейных кодов над $\mathbb{F}_q$ с относительным минимальным расстоянием не менее $\delta$ (см. [85; п. 1.3.1]). Отсюда вытекает следующее утверждение. Следствие 4.4. Справедливо неравенство где $\delta_q$ – единственное решение уравнения $\alpha^{\rm lin}_q(\delta)=\delta$. Любая верхняя граница для $\alpha^{\rm lin}_q(\delta)$ даёт верхнюю границу для $\delta_q$ и тем самым нижнюю границу для $m_q$. Таким образом, из этого следствия вытекает, что можно получать нижние оценки асимптотической величины $m_q$ из асимптотических параметров кодов. Теперь приведём известные нижние границы, относящиеся к этой величине, а именно нижнюю границу для величины $m_2$, полученную Р. Брокетом, М. Брауном и Д. Добкином [31], [30] с использованием “границы четырёх” [85; п. 1.3.2] для асимптотических параметров бинарных кодов, и нижнюю границу величины $m_q$ при $q>2$, данную И. Шпарлинским, М. Цфасманом и С. Влэдуцом [80] с использованием асимптотической границы Плоткина [85; п. 1.3.2]. Заметим, что эта последняя граница является непосредственным следствием предложения 4.3 из [43], установленного Д. В. и Г. В. Чудновскими. 4.2. СуперкодыНапомним понятие суперкода, введённое И. Шпарлинским, М. Цфасманом и С. Влэдуцом [80]. Сначала напомним идею, которая привела к возникновению понятия суперкода. В соответствии с п. 4.1 любое разложение тензора $t_M$ в сумму $N$ слагаемых ранга 1 позволяет получить $[N,n,d]_q$-код. На самом деле понятие суперкода вытекает из обратного вопроса о том, когда можно построить такое разложение из линейного $[N,n,\geqslant n]_q$-кода. Определение 4.6. Пусть $S \subseteq \mathbb{F}_{q^n} \oplus \mathbb{F}_q^{N}$ есть $\mathbb{F}_q$-линейное подпространство. Подпространство $S$ называется $[N,n]_q$-суперкодом, если выполняются следующие условия: (a) ограничение первой проекции
$$
\begin{equation*}
\pi_1\colon \mathbb{F}_{q^n} \oplus \mathbb{F}_q^N \to \mathbb{F}_{q^n}
\end{equation*}
\notag
$$
на $S$ сюръективно; (b) пусть ${S^2=\{s_1s_2\mid s_1, s_2 \in S\}}$, где под умножением подразумевается умножение в $\mathbb{F}_q$-алгебре ${\mathbb{F}_{q^n} \oplus \mathbb{F}_q^{N}}$, и пусть $\langle S^2\rangle$ – подпространство в ${\mathbb{F}_{q^n} \oplus \mathbb{F}_q^{N}}$, натянутое на $S^2$; тогда ограничение второй проекции на $\langle S^2\rangle$ инъективно.Из определения 4.6 можно получить следующее, более ограничительное понятие, которое почти эквивалентно понятию симметричного разложения тензора умножения. Определение 4.7. $[N,n]_q$-суперкод $S$ называется точным, если $\pi_1$ – изоморфизм, т. е. если $\dim S=n$. Предложение 4.8. Пусть $S$ есть $[N,n]_q$-суперкод, и пусть $C=\pi_2(S)$; тогда выполняется следующее: 1) $C$ является $[N,\geqslant n,\geqslant n]$-кодом; 2) если $S$ точен, то $C$ является $[N, n, \geqslant n]$-кодом; 3) любой суперкод содержит точный подсуперкод. На самом деле понятие точного суперкода эквивалентно понятию симметричного разложения тензора $t_M$ в сумму $N$ тензоров ранга 1 с точностью до представления поля $\mathbb{F}_{q^n}$ (т. е. по модулю следующего отношения эквивалентности). Определение 4.9. Пусть – два симметричных разложения тензора $t_M$. Будем говорить, что $\sigma_1$ и $\sigma_2$ эквивалентны, если $u_i=v_i$ для каждого $i$. Теперь, рассматривая отношение эквивалентности из определения 4.9, получаем следующий результат. Теорема 4.10. Имеется биективное отображение между множеством точных суперкодов и множеством классов эквивалентности симметричных разложений тензора $t_M$. Далее, в силу [80; предложение 1.11, следствие 1.13] получаем следующее. Следствие 4.11. 1) Любой точный суперкод $S\subset \mathbb{F}_{q^n}\oplus \mathbb{F}_q^N$ даёт симметричный алгоритм умножения билинейной сложности $N$, и наоборот. 2) Любой суперкод $S\subset \mathbb{F}_{q^n}\oplus \mathbb{F}_q^N$ даёт симметричный алгоритм умножения билинейной сложности $\leqslant N$. Заметим, что И. Шпарлинский, М. Цфасман и С. Влэдуц [80] привели явное построение симметричного тензора $t_M$ длины $N$, выполняющего умножение в конечном поле $\mathbb{F}_{q^n}$, из точного суперкода $S\subset \mathbb{F}_{q^n}\oplus \mathbb{F}_q^N$. Наоборот, из произвольного симметричного разложения они явным образом получили точный суперкод в силу [80; предложение 1.11]. Замечание 4.12. Некоторые авторы используют понятие дружественного умножению кода, которое эквивалентно понятию точного суперкода. В частности, результаты, полученные с использованием понятия дружественного умножению кода, относятся только к симметричной билинейной сложности. Открытая проблема 4.13. Как можно охарактеризовать те $[N,\geqslant k,\geqslant k]$-коды, что являются проекциями суперкодов? 5. Обобщения алгоритма Д. В. Чудновского и Г. В. Чудновского5.1. МотивацияПри использовании оригинального метода Д. В. Чудновского и Г. В. Чудновского видно, что границы, которые можно получить для билинейной сложности, а также их эффективность или практическая реализация соответствующих алгоритмов умножения сильно зависят от выбора геометрических данных, к которым применяется теорема 3.1. Например, чтобы получить неулучшаемые границы, нужны кривые, имеющие достаточно много рациональных точек и наименьший возможный род. Это хорошо работает, когда рассматривается основное поле, которое не слишком мало, причём его порядок – полный квадрат, так что может достигаться знаменитая граница Дринфельда–Влэдуца (см. детали в разделе 6). Но в других ситуациях исходный метод Чудновского–Чудновского сталкивается с определёнными ограничениями. Чтобы их преодолеть, был предложен ряд усовершенствований. Чтобы лучше понять эти усовершенствования, выделим два шага в построении алгоритмов умножения. Первый шаг заключается в формулировке АУЧЧ “общего вида”, который принимает в качестве входных данных некоторые геометрические данные (поле функций или кривую, какие-то точки на них, а также какие-то дивизоры, удовлетворяющие подходящим условиям) и выдаёт в качестве выходных данных эффективный алгоритм умножения или по меньшей мере верхнюю оценку некоторой билинейной сложности. Второй шаг заключается в указании геометрических объектов, на которых этот АУЧЧ общего вида будет применяться: выбор кривых, существование дивизоров и т. д. Что касается первого шага (формулировка АУЧЧ общего вида), многие авторы последовательно предлагали обобщения с использованием различных ингредиентов, среди которых отметим следующие:
В этом разделе мы обсудим подробнее эти способы усовершенствования с упором на первые два (в пп. 5.2 и 5.3), мы также приведём наилучшую конечную версию АУЧЧ [74; теорема 3.5], которая объединяет их все. Затем мы объясним, каким образом промежуточные исторические вклады могут быть извлечены из неё как частные случаи. Что касается второго шага (спецификация геометрических объектов), то наиболее важные ингредиенты следующие:
Конечно, эти два различаемых нами шага тесно переплетаются: подходящим образом обобщённый АУЧЧ общего вида позволяет иметь более широкий выбор геометрических объектов и потому приводит к лучшим границам или к более эффективной реализации. В другом направлении может случиться, что некоторые геометрические условия (например, существование точек данной степени или подходящих дивизоров) могут быть заменены на простые числовые критерии и включены в формулировку АУЧЧ общего вида. 5.2. Отображение значения на точках высшей степени и с кратностямиЗдесь можно выделить несколько последовательных достижений. $\bullet$ Сначала С. Балле и Р. Роллан [24] обобщили алгоритм, используя точки степени 1 и 2. $\bullet$ Затем Н. Арно [1] ввёл, как в интерполяции Лагранжа–Сильвестра, использование производных (отображение значения с кратностями) для улучшения интерполяционного процесса. $\bullet$ Эти идеи были объединены и обобщены в работе М. Сенка и Ф. Озбудака [39]. Это обобщение использует несколько коэффициентов (а не только самый первый) в локальном разложении в каждой точке $P_i$. Благодаря способу, которым в [39] получена оценка билинейной сложности, она включает сумму локальных вкладов, каждый из которых записывается в виде произведения двух отдельных сомножителей: один сомножитель отражает степень точки, а другой отвечает за кратность. $\bullet$ Наконец, У. Рандриамбололона [74] усовершенствовал этот метод путём введения единой величины, которая сочетает одновременно степень и кратность и приводит к наиболее точным границам, известным к настоящему времени. Эту введённую в [74] величину можно определить двумя способами, одним для билинейной сложности, другим для симметричной билинейной сложности. Определение 5.1. Для любых целых чисел $m,\ell\geqslant 1$ рассмотрим $\mathbb{F}_q$-алгебру $\mathbb{F}_{q^m}[t]/(t^\ell)$ многочленов от одной переменной с коэффициентами в $\mathbb{F}_{q^m}$, обрезанных по степени $\ell$. Обозначим через её билинейную сложность над $\mathbb{F}_q$ и через её симметричную билинейную сложность над $\mathbb{F}_q$. Заметим, что при $\ell=1$ выполняются равенства
$$
\begin{equation*}
\mu_q(m,1)=\mu_q(m)\quad\text{и}\quad \mu^{\rm sym}_q(m,1)=\mu^{\rm sym}_q(m).
\end{equation*}
\notag
$$
В то же время при $m=1$ имеем $\mu_q(1,\ell)=\widehat{M}_q(\ell)$ в соответствии с определением М. Сенка и Ф. Озбудака [39], а именно: для натурального $\ell$ пусть $\widehat{M}_q(\ell)$ обозначает мультипликативную сложность вычисления коэффициентов произведения двух $\ell$-членных многочленов по модулю $x^{\ell}$ над $\mathbb{F}_q$. Другими словами, $\widehat{M}_q(\ell)$ – это минимальное число умножений в $\mathbb{F}_q$, необходимых для того, чтобы получить первые $\ell$ коэффициентов произведения двух произвольных $\ell$-членных многочленов из $\mathbb{F}_q[x]$ (мы могли бы таким же образом определить $\mu^{\rm sym}_q(1,\ell)=\widehat{M}_q^{\rm sym}(\ell)$, хотя эта величина в [39] не рассматривалась). Обобщённое отображение значения, возникающее в обобщённом АУЧЧ, может быть описано либо на языке современной алгебраической геометрии, как это сделано в [74], либо на языке алгебраических полей функций, как в предшествующих работах. В действительности эти два языка эквивалентны, так что мы объясним, как переходить от одного к другому. Предположим, что заданы
Теперь для любого дивизора $\mathcal{D}$ на $X$ можно определить обобщённое отображение значения, которое принимает значения сечений дивизора $\mathcal{D}$ в точке $P$ с кратностью $\ell$. В геометрических терминах это просто естественное отображение ограничения
$$
\begin{equation*}
\varphi_{\mathcal{D},P,\ell}\colon\mathcal{L}(\mathcal{D})\to \mathcal{O}_X(\mathcal{D})\big|_{P^{[\ell]}}.
\end{equation*}
\notag
$$
Заменяя, если нужно, дивизор $\mathcal{D}$ на линейно эквивалентный дивизор, мы будем считать, что $P$ не лежит в носителе дивизора $\mathcal{D}$. Тогда имеем естественное отождествление $\mathcal{O}_X(\mathcal{D})\big|_{P^{[\ell]}}=\mathcal{O}_{P^{[\ell]}}$. Затем, благодаря лемме 3.4 из [74], получаем изоморфизм алгебр
$$
\begin{equation*}
\mathcal{O}_{P^{[\ell]}}\simeq\mathbb{F}_{q^m}[t]/(t^\ell),
\end{equation*}
\notag
$$
где $t$ соответствует локальному параметру $t_P$ в точке $P$, а $\mathbb{F}_{q^m}$ отождествляется с полем вычетов точки $P$. Наконец, чтобы представить всё в явном виде для вычислений, можно использовать естественный линейный изоморфизм $\mathbb{F}_{q^m}[t]/(t^\ell)\simeq(\mathbb{F}_{q^m})^\ell$, отождествляющий многочлен $a_0+a_1t+\cdots+a_{\ell-1}t^{\ell-1}$ с его коэффициентами $(a_0,a_1,\dots,a_{\ell-1})$. Объединяя всё это, получаем обобщённое отображение значения в виде
$$
\begin{equation}
\varphi_{\mathcal{D},P,\ell}\colon\bigg|\begin{aligned} \, \mathcal{L}(\mathcal{D}) & \to (\mathbb{F}_{q^m})^\ell, \\ f & \mapsto (f(P),f'(P),\dots,f^{(\ell-1)}(P)), \end{aligned}
\end{equation}
\tag{5}
$$
где $f^{(k)}(P)$ – коэффициенты локального разложения функции $f$ в точке $P$ относительно $t_P$:
$$
\begin{equation*}
f=f(P)+f'(P)t_P+f''(P)t_P^2+\cdots+f^{(k)}(P)t_P^k+\cdots\,.
\end{equation*}
\notag
$$
Иногда это отображение также называют производным отображением значения, хотя нужно проявлять осторожность, так как при $k\geqslant2$ эти функции $f^{(k)}(P)$ не являются в точности производными в обычном смысле слова (в лучшем случае они есть “производные, умноженные на $1/k!$”). 5.3. Обсуждение симметрииВ более широком контексте билинейных алгоритмов над конечными полями различие между (общей) билинейной сложностью и симметричной билинейной сложностью, а также некоторые математические вопросы, специфически связанные с построением симметричных алгоритмов, впервые обсуждались в 1984 г. в работе Г. Серусси и А. Лемпеля [78]. Сосредоточимся теперь на работах, основанных на методе Чудновского–Чудновского. Оказывается, что до 2011 г. все результаты (включая полученные в [43], [80], [25], [39], [73]) формулировались только в терминах $\mu_q$ (а не $\mu^{\rm sym}_q$), хотя этот метод по построению всегда выдавал симметричные алгоритмы. Конечно, это не означает, что авторы не знали об этом различии: действительно, например, И. Шпарлинский, М. Цфасман и С. Влэдуц в явном виде упоминали об этом, когда отмечали в [80; с. 154], что их понятие суперкода соответствует только симметричным алгоритмам. Однако ситуация стала неудовлетворительной, когда И. Каскудо, Р. Крамер и Ч. Син обнаружили пробел в построении дивизора в [80], что уже обсуждалось в разделе 3. Действительно, оказалось, что трудность этого построения, которое они анализировали в терминах $2$-кручения в группе классов дивизоров кривой (см. п. 7.1), тесно связана с симметрией, требующейся для алгоритма. Наконец, дело было прояснено в работе У. Рандриамбололоны [74]. Наряду со вкладом, уже обсуждавшимся в п. 5.2, эта работа привнесла два дальнейших улучшения метода:
Имея в виду эти усовершенствования, всегда, когда возможно, следует формулировать обобщённый АУЧЧ в двух вариантах, один – для билинейной сложности, другой – для симметричной билинейной сложности. Точно так же и численные оценки следует формулировать в двух соответствующих вариантах. В дополнение к билинейной сложности $\mu_q$ и симметричной билинейной сложности $\mu^{\rm sym}_q$, некоторые другие усовершенствования были введены и изучены в работах [78] и [76; приложение A]: это трисимметричная билинейная сложность $\mu^{\rm tri}_q$ и нормализованная трисимметричная билинейная сложность $\mu^{\rm nrm}_q$. Следует отметить, что может случиться так, что эти величины нельзя корректно определить для некоторых значений $q$ и $n$. Точнее, предложение A.14 в [76] показывает, что $\mu^{\rm tri}_q(n)$ определена корректно для всех значений $q$ и $n$, кроме $q=2$, $n\geqslant3$. Аналогично, предложение A.19 в [76] показывает, что $\mu^{\rm nrm}_q(n)$ определена корректно для всех значений $q$ и $n$, за исключением $q=2$, $n\geqslant3$ и $q=4$, $n\geqslant2$. В любом случае, когда эти величины определены корректно, выполняются неравенства
$$
\begin{equation*}
\mu_q(n)\leqslant\mu^{\rm sym}_q(n)\leqslant \mu^{\rm tri}_q(n)\leqslant\mu^{\rm nrm}_q(n).
\end{equation*}
\notag
$$
Кроме того, теорема 2 из [78] даёт
$$
\begin{equation*}
\mu_q^{\rm tri}(n)\leqslant4\mu_q^{\rm sym}(n),\quad\text{если } q\ne2\text{ и } \operatorname{char}(\mathbb{F}_q)\ne3,
\end{equation*}
\notag
$$
а предложение A.19 из [76] даёт
$$
\begin{equation*}
\mu_q^{\rm nrm}(n)\leqslant 2\mu_q^{\rm tri}(n),\quad\text{если } q\ne7, \quad\text{и}\quad \mu_7^{\mathrm{nrm}}(n)\leqslant 3\mu_7^{\rm tri}(n).
\end{equation*}
\notag
$$
В сочетании с линейностью $\mu^{\rm sym}_q$ это даёт линейность $\mu_q^{\mathrm{nrm}}$ и $\mu_q^{\rm tri}$ для большинства значений $q$. Однако, кроме упомянутых фактов, об этих величинах известно очень мало. Открытая проблема 5.2. (i) Каковы точные значения $\mu_q^{\mathrm{nrm}}(n)$ и $\mu_q^{\rm tri}(n)$ для малых $q$ и $n$? (ii) Могут ли быть строгими какие-то из неравенств между $\mu_q(n)$, $\mu^{\rm sym}_q(n)$, $\mu^{\rm tri}_q(n)$ и $\mu^{\rm nrm}_q(n)$? Если да, то для каких значений $n$? (iii) Можно ли улучшить асимптотические границы для этих величин? 5.4. Текущая версия обобщённого АУЧЧТеперь мы можем сформулировать результат У. Рандриамбололоны [74; теорема 3.5], который даёт наиболее общую на настоящий момент версию АУЧЧ. Он использует наиболее продвинутую форму производного отображения значения и даёт оценки как для асимметричной сложности, так и для симметричной сложности. Как уже объяснялось, этот результат в оригинале был представлен на языке современной алгебраической геометрии, но здесь мы приводим его эквивалентный перевод на язык полей функций. Теорема 5.3. Пусть Существование объектов, удовлетворяющих этим условиям, обеспечивается следующими числовыми критериями: $\bullet$ достаточным условием существования точки $Q$ степени $n$ является выполнение неравенства где $g$ – род поля $F$;$\bullet$ достаточным условием для (a) является неспециальность дивизоров $\mathcal{D}_1-\ell Q$ и $\mathcal{D}_2-\ell Q$: где $i$ обозначает индекс специальности;$\bullet$ необходимым и достаточным условием для (b) является нульмерность дивизора $\mathcal{D}_1+\mathcal{D}_2-\mathcal{G}$: где $\mathcal{G}=u_1P_1+\cdots+u_NP_N$.Тот факт, что $\mu_q(n,\ell)$ (соответственно $\mu^{\rm sym}_q(n,\ell)$) появляется в левой части неравенства, позволяет применять результат рекурсивно. При $n=1$ он также даёт границы М. Сенка и Ф. Озбудака для величины $\widehat{M}_q(\ell)$ (соответственно для $\widehat{M}_q^{\rm sym}(\ell)$). Однако в большинстве приложений нас в основном интересует случай $\ell=1$. Если переформулировать результат в этом частном случае и сконцентрироваться только на симметричной части, то эта обобщённая версия АУЧЧ специализируется в следующий результат (частный случай теоремы 3.5 из [74]), который достаточен для большинства приложений. Следствие 5.4. Пусть Это можно специализировать ещё сильнее. Действительно, заметим сначала, что для всех $d$, $u$ выполняется несложное неравенство
$$
\begin{equation}
\mu^{\rm sym}_q(d,u)\leqslant \mu^{\rm sym}_q(d)\widehat{M}_{q^d}^{\rm sym}(u).
\end{equation}
\tag{6}
$$
Оно непосредственно вытекает из леммы 1.6, (b), применённой к $\mathcal{A}=\mathbb{F}_{q^d}[t]/(t^u)$, $L=\mathbb{F}_{q^d}$ и $K=\mathbb{F}_q$. Получаем следующее. Следствие 5.5. При тех же условиях, что в следствии 5.4, имеем Следствие 5.5 может рассматриваться как симметричный вариант версии АУЧЧ М. Сенка и Ф. Озбудака [39]. Оно слабее следствия 5.4, поскольку неравенство $\mu^{\rm sym}_q(d,u)\leqslant \mu^{\rm sym}_q(d)\widehat{M}_{q^d}^{\rm sym}(u)$ может быть строгим. Чтобы получить эту симметричную переформулировку, нужно в исходной формулировке из [39] аккуратно заменить все билинейные сложности (в том числе для кратностей) на симметричные билинейные сложности. Обращаясь к более далёкому прошлому, заметим, что алгоритм, приведенный Д. В. и Г. В. Чудновскими в [43], соответствует случаю $d_i=1$ и $u_i=1$ при $i=1,\dots,N$. Первое обобщение, предложенное С. Балле и Р. Ролланом [24], относится к случаю, когда $d_i$ равно 1 или 2, а $u_i$ равно 1 при $i=1,\dots,N$. Далее, обобщение, предложенное Н. Арно [1], касается случая, когда $d_i$ равно 1 или 2 и $u_i$ равно 1 или 2 при $i=1,\dots,N$. В частности, из теоремы 5.3 вытекает следующий результат, полученный Н. Арно [1] путём группировки точек, используемых с той же кратностью; а именно, он полагал ${\ell_j:=|\{P_i\mid \deg P_i=j \text{ и } u_i=2\}|}$, $j=1,2$, для $\mathcal{D}=\mathcal{D}_1=\mathcal{D}_2$. Следствие 5.6. Пусть 6. Выбор кривых6.1. Мотивация и обозначенияКак мы видели в разделах 3 и 5, на сегодняшний день наилучшим методом оценки билинейной сложности умножения в конечных полях является АУЧЧ, основанный на интерполяции над алгебраическими кривыми, определёнными над конечным полем. Таким образом, в этом контексте, чтобы получать наилучшие оценки верхних пределов сложностей $M_q$ и $M^{\rm{sym}}_q$ или верхние оценки $C_q$ и $C^{\rm sym}_q$ (определения см. в п. 3.2), необходимо использовать достаточно много различных кривых, с тем чтобы справляться с наихудшими случаями. Введём термин для требующегося нам свойства, формализованного в [80; с. 163, Claim]. Определение 6.1. Пусть $X_s/k$ – семейство кривых рода $g_s$ над полем $k$. Будем говорить, что семейство $(X_s)_s$ плотно, тогда и только тогда, когда род $g_s$ стремится к бесконечности, а отношение двух последовательных родов $g_{s+1}/g_s$ стремится к 1. Введённые в предыдущем разделе алгоритмы умножения, основанные на интерполяции на алгебраических кривых, зачастую требуют много точек высших степеней $r\geqslant 2$. Поэтому изучим неулучшаемые асимптотические отношения $\beta_r$ числа точек степени $r$ к роду кривой. Первое определение принадлежит М. Цфасману [84] (см. также [26; определения 1.1, 1.2 и 1.3]). Определение 6.2. Пусть ${\mathcal X}/\mathbb{F}_q=(X_s/\mathbb{F}_q)_s$ – последовательность кривых $X_s/\mathbb{F}_q$ рода $g_s=g(X_s/\mathbb{F}_q)$, определённых над конечным полем $\mathbb{F}_q$. Предположим, что последовательность родов $g_s$ – возрастающая последовательность, растущая к бесконечности. Тогда последовательность ${\mathcal X}/\mathbb{F}_q$ называется асимптотически точной, если для всех $r\geqslant 1$ существует предел $\beta_r({\mathcal X})=\lim_{s\to\infty}(B_r(X_s)/g_s)$, где $B_r(X_s)$ обозначает число замкнутых точек степени $r$ кривой $X_s$. Определение 6.3. Пусть $r\geqslant 1$ – целое число и $q$ – степень простого числа. Для кривой $X$ над $\mathbb{F}_q$ пусть $B_r(X)$ обозначает число замкнутых точек степени $r$. Для асимптотически точной последовательности кривых ${\mathcal X}=(X_s)_s$ определим Положим где ${\mathcal X}$ пробегает все асимптотически точные последовательности кривых, и где ${\mathcal X}$ пробегает все плотные асимптотически точные последовательности кривых. Замечание 6.4. Величина $A_1(q)$ – это классическая константа Ихары $A(q)$, определённая Й. Ихарой в работе [63]. Константы Ихары $A_r(q)$ порядка $r$ были, в частности, определены в [26; определение 1.3]. Что касается величин $A'_r(q)$, отметим, что плотная константа Ихары $A'_1(q)$ была впервые введена (и обозначена $A'(q)$) У. Рандриамбололоной [73] (см. также [77]). Плотные константы Ихары $A'_r(q)$ порядка $r$ были впервые введены (и обозначены $\widetilde{A}_r(q)$) М. Рамбо [71]. Следующий результат, по-видимому, хорошо известен. По существу, он вытекает из леммы IV.3 в [38], которая сама основана на обобщённой границе Дринфельда–Влэдуца (см. [84; теорема 1], а также [26; определения 1.2, 1.3]). Теорема 6.5. Пусть $(X_s/\mathbb{F}_q)_s$ – семейство кривых над конечным полем $\mathbb{F}_q$, род $g_s$ которых стремится к бесконечности. Пусть $r\geqslant 1$ – целое число, $B_r(X_s)$ – число замкнутых точек степени $r$, а $|X_s(\mathbb{F}_{q^r})|$ – число точек кривой $X_s$ в расширении $\mathbb{F}_{q^r}$. Тогда следующие утверждения эквивалентны: Из теоремы 1 работы [84] вытекает следующее утверждение. 6.2. Явные башни, уплотнение и спускВ пионерских работах [43], [80], целью которых было доказательство линейности (см. п. 3.2) билинейной сложности умножения относительно степени расширения, требовалось использование бесконечных семейств кривых с большим по отношению к роду числом рациональных точек. Однако первые использованные семейства кривых (типа модулярных кривых и кривых Шимуры) позволили получить в этих работах только чисто асимптотические границы. Поэтому целью работы [5] (см. также [6] и подстрочное примечание 1 на с. 41) было дать первые верхние оценки, равномерные относительно $q$. Для этого было необходимо использовать более явные семейства кривых. Первая башня алгебраических полей функций Гарсии–Штихтенота [57] удовлетворяла требуемым условиям: были известны фундаментальные инварианты, а именно род и число рациональных точек каждого этажа башни, для которых достигается граница Дринфельда–Влэдуца. С общей точки зрения, чтобы получить наилучшие границы с помощью АУЧЧ, нужно использовать семейства кривых рода, растущего как можно медленнее (см. п. 5.1 и теорему 9.5 в п. 9.2). Однако башня алгебраических полей функций составлена из последовательных алгебраических полей функций, роды которых возрастают согласно формуле Гурвица вместе со степенью расширения между двумя последовательными этажами. Например, первая башня Гарсии–Штихтенота, определённая над $\mathbb{F}_{q^2}$, является башней Артина–Шрайера, у которой отношение двух последовательных родов есть $g_{i+1}/g_i\geqslant q$, где $q$ – произвольная степень простого числа. В этом случае интересная стратегия улучшения границ, получаемых с помощью башен такого типа, состояла в уплотнении такой башни путём добавления промежуточных этажей (см. [7]). Это легко осуществимо в данном случае, даже без знания рекуррентного уравнения для промежуточных этажей, поскольку башня является башней Галуа. Когда используемые башни ${\mathcal X}/\mathbb{F}_q$ таковы, что значение $\beta_1({\mathcal X})$ недостаточно велико (это имеет место, когда конечные поля определения малы или когда наилучшая известная нижняя граница для константы Ихары $A_r(q)$, связанной с полем определения $\mathbb{F}_q$, недостаточно велика), ввиду границы Дринфельда–Влэдуца необходимо использовать точки степени $>1$ (см. [24], [20]). Таким образом, нам нужны семейства кривых, для которых достигается граница Дринфельда–Влэдуца порядка $r>1$ (см. [25] и утверждение (I2) в теореме 6.5). На сегодняшний день единственным способом получения таких семейств является введённая в [24] техника спуска семейств алгебраических полей функций, определённых над $\mathbb{F}_{q^r}$, на поле определения $\mathbb{F}_{q}$. Конечно, спуск исходной башни Гарсии–Штихтенота всегда возможен, так как коэффициенты рекуррентного уравнения лежат в $\mathbb{F}_q$. Однако, как только мы вводим в рассмотрение промежуточные этажи, возникают трудности. Так, в [24] спуск был осуществлён явным образом только для характеристики 2 и $r=2$, поскольку в этом случае спускаемая башня сохраняет свойство быть башней Галуа. Обобщение на любую характеристику при $r=2$ было затем реализовано в [19] с помощью двух различных методов: теоретически, используя действие группы Галуа расширения $\mathbb{F}_{q^2}/\mathbb{F}_q$ на промежуточных этажах башни, определённой на $\mathbb{F}_{q^2}$, или путём нахождения явных уравнений промежуточных этажей. Когда все возможности башен были использованы, возникла необходимость использовать семейства алгебраических полей функций, более плотных, чем башни. Для этой цели было естественно вернуться к изучению семейств модулярных кривых и кривых Шимуры, что и является предметом следующего пункта. 6.3. Модулярные кривые и кривые ШимурыВ предыдущем пункте дана мотивировка для поиска плотных семейств кривых, становящихся оптимальными после расширения основного поля (небольшой) степени $r$. Сначала заметим, что башни Гарсии–Штихтенота [57], [58] на самом деле определены над своим простым полем $\mathbb{F}_p$, а для любого расширения основного поля степени $r$ существуют неплотные башни, для которых достигается предыдущая граница (см. п. 6.2):
$$
\begin{equation}
A_r(q)=\frac{\sqrt{q^r}-1}{r}\,, \quad \text{если } q^r \text{ - квадрат.}
\end{equation}
\tag{8}
$$
В частном случае квадратичных расширений $r=2$ знаменитые результаты из работ [63] и [86] (см. также [80]) утверждают, что (см. также два оригинальных подхода, предложенных в [48; теорема IV.4.5]) для всех степеней простого числа $q$ существуют плотные семейства модулярных кривых Шимуры над $\mathbb{F}_q$, которые становятся оптимальными над $\mathbb{F}_{q^2}$. См. также работу [88], где изложено введение в теорию кривых Шимуры (в характеристике нуль). Заметим, что классические модулярные кривые над простыми полями $\mathbb{F}_p$ являются частным случаем кривых Шимуры. Подытоживая, отметим, что вышеупомянутые кривые Шимуры согласуются с границей Дринфельда–Влэдуца над $\mathbb{F}_{q^2}$, согласно которой Принимая во внимание, что эти кривые определены над $\mathbb{F}_q$, из теоремы 6.5 получаем равенство6.3.1. Сплетение двух рекурсивных башен в плотное семействоРекуррентная конструкция плотного семейства кривых заключается в сплетении двух башен модулярных кривых, определённых над одним и тем же базисом. Проиллюстрируем это на примере классических модулярных кривых $X_0(N)$. Пусть $l$ – простое число; тогда мы знаем из работ Игусы, что для любого $i\geqslant 0$ существуют – канонические – модели $X_0(l^i)_{\mathbb{Q}}$ над $\mathbb{Q}$, которые обладают хорошей редукцией при любом $p\ne l$ и которые асимптотически оптимальны над $\mathbb{F}_{p^2}$. Кривые $X_0(l^i)_{\mathbb{Q}}$ образуют башню над $\mathbb{Q}$, которая рекурсивно определяется двумя первыми этажами. Точнее, башня строится итерацией расслоенных произведений из следующей пары данных:
Замечание 6.7. В действительности достаточно первого этажа, чтобы рекурсивно построить всю башню (см. исторические замечания и ссылки в п. 6.3.3 ниже). А именно, нужно только накрывающее отображение $X_0(l)\to X_0(1)$ и инволюции Аткина–Ленера $w_i$ при $i=0,1$. Следует проявлять осторожность, так как расслоённое произведение первого этажа $X_0(l)$ с его скрученной копией Аткина–Ленера (вдобавок к тому, что оно очень сингулярно) содержит вторую неприводимую компоненту помимо $X_0(l^2)$. Это вытекает из соображений о степени [71; гл. VI, § 2.3, 3.2] (или, если угодно, из соображений модулярной интерпретации). Для любого $p$ роды в одной башне $X_0(l^i)_{\mathbb{F}_p}$ жёстко определяются степенями $l^i$ простого числа $l$:
$$
\begin{equation}
\frac{1}{12}l^i\biggl(1+\frac{1}{l}\biggr)+o(g_i)\leqslant g_i \leqslant \frac{1}{12}l^i\biggl(1+\frac{1}{l}\biggr)
\end{equation}
\tag{11}
$$
(см. [85; п. 4.1] или [47; теорема 3.1.1 и с. 107]). Значит, в одиночку эта башня не образует плотного семейства. Пусть теперь $l'\ne l$ – другое простое число; рассмотрим рекурсивную башню $X_0(l'^j)_{\mathbb{Q}}$. Обе башни определены над одним и тем же базисом $X_0(1)$, и, беря расслоённые произведения над $X_0(1)$, получаем
$$
\begin{equation*}
X_0(l^i)_{\mathbb{Q}}\times X_0(l'^j)_{\mathbb{Q}}=X_0(l^il'^j)_{\mathbb{Q}}
\end{equation*}
\notag
$$
для любых $i$ и $j$. Поступая таким образом для каждой пары индексов $i$ и $j$, получим семейство $\{X_0(l^il'^j)_{\mathbb{Q}}\}_{i,j}$; назовём это семейство “сплетением” двух рекурсивных башен. Это семейство имеет хорошую редукцию при любом простом $p\ne l,l'$ и является асимптотически оптимальным. Роды в этом семействе жёстко определяются произведениями $l^il'^j$ степеней простых чисел $l$ и $l'$, как видно из неравенств
$$
\begin{equation}
\frac{1}{12}l^il'^j\biggl(1+\frac{1}{l}\biggr)\biggl(1+\frac{1}{l'}\biggr)+ o(g_{i,j})\leqslant g_{i,j} \leqslant \frac{1}{12}l^il'^j\biggl(1+\frac{1}{l}\biggr)\biggl(1+\frac{1}{l'}\biggr).
\end{equation}
\tag{12}
$$
Ключевое наблюдение заключается в том, что семейство целых чисел $l^il'^j$ плотно, т. е. его скорость роста стремится к нулю. Значит, сплетённое семейство $\{X_0(l^il'^j)_{\mathbb{Q}}\}_{i,j}$ плотно. 6.3.2. Проблемы спуска на кривых Шимуры и открытые вопросыПерейдём к кривым Шимуры и рассмотрим три специальные рекурсивные башни $X_0(\mathfrak{p}^i)$, определённые над одним и тем же базисом $X_0(1)$ рода нуль. Пусть $F=\mathbb{Q}[\cos(2\pi/7)]$ – вполне вещественное числовое поле степени три, $\mathfrak{p}_2$ и $\mathfrak{p}_3$ – простые идеалы над инертными простыми идеалами (2) и (3), а $\mathfrak{p}_7$ – простой идеал над полностью разложимым простым идеалом (7). Пусть $B$ – кватернионная алгебра над $F$, которая разветвляется в точности в двух из трёх вещественных точек и ни в одной конечной точке. Алгебра $B$ содержит единственный класс сопряжённых порядков Эйхлера заданного уровня. В частности, для максимального порядка $\mathcal{O}$ его группа единиц $\mathcal{O}^1$ вкладывается в $\operatorname{PSL}_2(\mathbb{R})$ и имеет образом знаменитую треугольную группу $(2,3,7)$ (это гиперболическая группа наименьшего кообъёма). Кривая Шимуры $X_0( 1)_{\mathbb{C}}$, униформизированная этой группой, имеет каноническую модель над $F$ рода нуль с тремя рациональными точками, которые однозначно возникают из эллиптических точек порядков 2, 3 и 7. Примечательно, что над этой базисной кривой имеются три башни $X_0(\mathfrak{p}^i)$, где $\mathfrak{p}=\mathfrak{p}_2$, $\mathfrak{p}_3$ или $\mathfrak{p}_7$, которые обладают каноническими моделями над $F$. Они обладают хорошей редукцией при каждом простом $\mathfrak{p}'$ из поля $F$, отличном от $\mathfrak{p}_2$, $\mathfrak{p}_3$ и $\mathfrak{p}_7$, а если вдобавок $\mathfrak{p}'=(p)$ получен из инертного простого идеала, то редукции $X_0(\mathfrak{p}^i)_{\mathbb{F}_{p^3}}$ по модулю $\mathfrak{p}$ имеют асимптотически оптимальные количества точек над $\mathbb{F}_{p^6}$ (см. теорему IV.4.5 в [48], которая установлена двумя независимыми методами). Теперь ясно, что сплетение двух башен $X_0(\mathfrak{p}_2^i)$ и $X_0(\mathfrak{p}_7^j)$ над $X_0(1)$ даёт плотное семейство $\{X_0(\mathfrak{p}_2^i\mathfrak{p}_7^j)_F\}_{i,j}$ над $F$ с родами, жёстко контролируемыми произведениями $8^i\cdot 7^j$:
$$
\begin{equation}
g_{i,j}=7^{j-2}\biggl(\frac{8^{i-1}\cdot 6}{7}+\frac{1}{7}\biggr)\quad \text{при } i\geqslant 1 \text{ и } j\geqslant 2
\end{equation}
\tag{13}
$$
(аналогичные формулы выполняются и для меньших $i$ или $j$: см. [71; следствие IV.2.12]). В частности, оно имеет хорошую редукцию по модулю $p_3=(3)$ и даёт асимптотически оптимальное плотное семейство $X_0(\mathfrak{p}_2^i\mathfrak{p}_7^j)_{\mathbb{F}_{3^3}}$ над $\mathbb{F}_{3^3}$ с большим числом точек в $\mathbb{F}_{3^6}$. Возникает интересная проблема для билинейного умножения над $\mathbb{F}_3$: можно ли спустить это семейство над $\mathbb{F}_3$? В этом направлении уже проделана большая работа, так как в [71; гл. VI, § 5.2] доказано, что два первых этажа редукций по модулю $\mathfrak{p}'=p_3$ этих двух башен спускаются над $\mathbb{F}_3$. Напомним, однако, что над $F$ этих двух первых этажей достаточно для того, чтобы построить всё семейство. Таким образом, проблема спуска семейства над $\mathbb{F}_3$ сводится к следующему общему вопросу. Гипотеза 6.8.1. Ответ на вопрос открытой проблемы 6.8 утвердительный. Мы уверены, что этот вопрос сводится к модулярной интерпретации целочисленных моделей кривых Шимуры (а не только моделей над числовыми полями, такими как $F$), которая также должна бы быть хорошо известна специалистам. Имеются и другие свидетельства в пользу положительного ответа на вопрос о спуске: в теореме V.5.14 из [71] установлено, что семейство $\{X_0(\mathfrak{p}_2^i\mathfrak{p}_7^j)_F\}_{i,j}$ спускается над $\mathbb{Q}$, и есть веские числовые свидетельства (о количестве точек) в пользу того, что каноническая редукция третьих этажей ($i=3$ и/или $j=3$) над $\mathbb{F}_{3^3}$ также спускается над $\mathbb{F}_3$ [71; гл. VI, § 5.2]. Резюмируем: спуск предыдущего семейства, который следовал бы, например, из гипотезы 6.8.1, дал бы плотное семейство над $\mathbb{F}_3$ с большим числом точек степени 6 и, таким образом, установил бы равенство справедливость которого (преждевременно) утверждалась как “теорема B” в [71].Аналогично, сплетение двух башен $X_0(\mathfrak{p}_3^i)$ и $X_0(\mathfrak{p}_7^j)$ над $X_0(1)$ даёт плотное семейство $\{X_0(\mathfrak{p}_3^i\mathfrak{p}_7^j)_F\}_{i,j}$ над $F$ с родами, жёстко контролируемыми произведениями $27^i\cdot 7^j$, с хорошей редукцией по модулю $p_2=(2)$ над $\mathbb{F}_{2^3}$ и с асимптотически большим числом точек в $\mathbb{F}_{2^6}$. Открытая проблема 6.9. Аналогичным образом нас интересует спуск указанного выше плотного семейства над $\mathbb{F}_2$, который, в случае своей справедливости, давал бы значение $A'_6(2)=(2^3-1)/6$. В предположении, что предыдущая гипотеза 6.8.1 верна, отсюда уже следовало бы, что башня $X_0(\mathfrak{p}_7^j)$ спускается над $\mathbb{F}_2$. Значит, нам осталось бы показать, что два первых этажа башни $X_0(\mathfrak{p}_3^i)$ также спускаются. Точнее, сформулируем следующую гипотезу. Гипотеза 6.9.1. Следующие морфизмы спускаются над $\mathbb{F}_2$: каноническое разветвлённое накрытие $X_0(\mathfrak{p}_3^2)_{\mathbb{F}_{2^3}} \to X_0(\mathfrak{p}_3)_{\mathbb{F}_{2^3}}$ и инволюция Аткина–Ленера на $X_0(\mathfrak{p}^{2}_3)_{\mathbb{F}_{2^3}}$. Наконец, заметим, что первый этаж этой башни $X_0(\mathfrak{p}_3)_{\mathbb{Q}} \to X_0(1)_{\mathbb{Q}}$ был явным образом вычислен над $\mathbb{Q}$ в [53]: это отображение Белого степени 27. Значит, если бы хорошая редукция башен кривых Шимуры также была рекурсивна начиная с первого этажа (см. замечание 6.7), то оставалось бы решить более лёгкую задачу нахождения хорошей редукции по модулю (3) этого отображения Белого степени 27. Открытая проблема 6.10. С более общей точки зрения все известные к настоящему времени семейства кривых, для которых достигается граница Дринфельда–Влэдуца над $q$, определены над полями мощности $q=p^{2t}$, являющейся полным квадратом. Следующая гипотеза утверждает (в эквивалентной форме), что для любого $q$, являющегося квадратом, существует плотное оптимальное семейство над $\mathbb{F}_q$, которое спускается над простым полем $\mathbb{F}_p$. Гипотеза 6.10.1. Пусть $p$ – простое число, а $2t\geqslant 4$ – чётное целое число. Тогда выполняется равенство Другими словами, существует такое семейство $(X_s/\mathbb{F}_{p^{2t}})_{s\geqslant1}$ кривых над $\mathbb{F}_p$ с (возрастающими) родами $g_s$, стремящимися к бесконечности, что (i) $X_s$ в действительности определена над простым полем $\mathbb{F}_p$; (ii) $\lim_{s \to \infty}(g_{s+1}/g_s)=1$ (условие максимальной плотности); (iii) $\lim_{s \to \infty}(|X_s(\mathbb{F}_{p^{2t}})|/g_s)=p^t-1$ (константа Ихары над $\mathbb{F}_{p^{2t}}$). Открытая проблема 6.11. Следующая гипотеза была предложена в [72]; мы добавили к ней требование плотности. Гипотеза 6.11.1. Пусть $p>2$ – нечётное простое число. Тогда существует такая последовательность чисел $(N_s)_s$, удовлетворяющая условию $\lim_{s\to \infty}(N_{s+1}/N_s)=1$ (условие плотности), что оператор Гекке $T_p(N_s)$, действующий на пространстве параболических форм $S_2(\Gamma_0(N_s))$ веса 2, имеет нечётный определитель. Следствием справедливости этой гипотезы было бы асимптотическое исчезновение 2-кручения в классических модулярных кривых. Предложение 6.11.2. В предположении справедливости гипотезы 6.11.1 существует плотное семейство $\{X_0(N_s)/\mathbb{F}_p\}_s$ (классических модулярных) кривых, для которых (т. е. кривые не имеют 2-кручения в своих группах классов). Это предложение сформулировано в [71] как гипотеза I.2.8. В [71] также приводится подробное доказательство того, что оно следует из гипотезы 6.11.1 – см. обсуждение перед гипотезой I.2.8, а также § II.5 (для ключевой формулы (2.6)). Следующее практическое следствие будет доказано в приложении (раздел 11). Предложение 6.11.3. Пусть $p$ – простое число, для которого выполняется гипотеза 6.11.1, и пусть $r$ – такое целое число, что $\{q=p$ и $r=2\}$ или $\{q=p^2$ и $r=1\}$. Тогда также выполняется формула утверждения (a) в теореме 8.21. 6.3.3. Ссылки и исторические замечания к разделу 6Рекурсивные модулярные башни. Рекурсивность башен классических модулярных кривых была отмечена в основополагающей работе Н. Элкиса [50], где можно найти дальнейшие подробности и доказательство над $\mathbb{C}$. Доказательство переносится на канонические модели над $\mathbb{Q}$, поскольку их модулярная интерпретация в терминах эллиптических кривых такая же. Н. Элкис также утверждает (и использует) следующее: башни кривых Шимуры рекурсивны. Доказательство этого факта формально аналогично: см. [48; предложение IV.5.1]. Но на самом деле необходимо соблюдать особую осторожность с неприводимостью участвующих тензорных произведений (см. [71; гл. VI, §§ 2.3, 3.2]), поскольку их модулярная интерпретация гораздо сложнее. Сплетение двух башен над одним и тем же базисом: эта конструкция уже упоминалась в [50]. Ключевое наблюдение о том, что получающееся семейство плотно, было сообщено нам Н. Элкисом в августе 2015 г. Рекурсивность начиная с первого этажа. Тот факт, что первый этаж модулярных башен на самом деле достаточен для их рекурсивного построения, был уже отмечен в [50; сноска 4] и [52], на что обратил наше внимание Н. Элкис в 2017 г. О гипотезе 6.10.1. Эта гипотеза была по существу сформулирована в [38] как лемма IV.4. В своем доказательстве авторы утверждали, что некоторые специальные кривые Шимуры с Галуа-инвариантными параметрами спускаются над рациональными числами. Это утверждение, к сожалению, неверно: в [22; § 3] мы привели контрпримеры к этому утверждению, которые в более общей ситуации показывают, что кривые Шимуры не спускаются над своими полями модулей. Следствия из гипотезы 6.10.1 о верхних пределах асимптотических сложностей приведены М. Рамбо в [71; табл. 2.2, строки “Conj Y”]. Заметим, что они несколько улучшают утверждения из [38], приводимые здесь в подстрочном примечании 11 на с. 72. Дальнейшая информация о явных вычислениях. После основополагающих работ [86] и [63] о кривых Шимуры с большим числом точек многие уравнения кривых рода 0 и 1 были вычислены в [51], [61] и [81]. Дальнейшие примеры рекурсивных башен кривых Шимуры можно найти в [48; гл. IV, пример 5.3], [62], [71; гл. VI, § 3] (определённые над вполне вещественным полем, с узким числом классов два и с рекордным числом точек над $F_{5^4}$ в роде 5). Список (в неявном виде) кривых Шимуры рода меньше 2 можно найти в [89]. С помощью этих данных и недавно разработанных в [67] инструментов анализа отображения Белого можно получить доступ к дюжине рекурсивных башен, у которых первый этаж – накрывающее отображение пространства $\mathbb{P}^1$ степени $\leqslant 9$, разветвлённое над тремя точками. Наконец, в случае, когда первый этаж определён над кривой рода 1, первый пример был вычислен в магистерской диссертации К. Леврата [65]. 7. Получение дивизора оптимальной степени для симметричных алгоритмовИспользуя численные критерии, приведённые в конце теоремы 5.3, в симметричном случае $\mathcal{D}_1=\mathcal{D}_2$ мы сталкиваемся со следующей проблемой: если заданы
Ясно, что ответ будет зависеть от $n$ и $N$. По теореме Римана–Роха из условия (16) следует, что $\deg\mathcal{D}-n\geqslant g-1$, а из условия (17) следует, что $2\deg\mathcal{D}-N\leqslant g-1$, так что, объединяя эти два утверждения, получаем, что неравенство является необходимым условием для существования решения.Заметим, что для того, чтобы получить алгоритм наилучшей сложности для данного $n$, нужно, чтобы число $N$ было как можно меньше. В своей исходной работе [43] Д. В. Чудновский и Г. В. Чудновский предложили простое рассуждение в терминах мощности и степени, в более явном виде позже изложенное С. Балле [6], который доказал существование решения при менее оптимальном условии Как объяснялось в п. 3.2, И. Шпарлинский, М. Цфасман и С. Влэдуц попытались улучшить исходную границу Чудновского–Чудновского путём доказательства существования дивизора $\mathcal{D}$ при оптимальном условии (18) вместо (19). Для этого им нужно было модифицировать рассуждение о мощности, но они не заметили последствий наличия $2$-кручения в группе классов при работе с (17). Чтобы исправить их доказательство, было разработано два подхода:
7.1. Оценки $2$-крученияОценки кручения в группе классов впервые появились в очень похожем контексте, а именно для разделяющих кодов (также называемых линейными пересекающимися кодами и frameproof codes), в работе Ч. Сина [92]. Действительно, чтобы получить $s$-разделяющий код высокой скорости, нужно для заданного дивизора $\mathcal{G}$ доказать существование такого дивизора $\mathcal{D}$ высокой степени, что Ч. Син доказал существование такого дивизора $\mathcal{D}$, используя рассуждение о мощности, подобное рассуждениям Чудновского–Чудновского и Шпарлинского–Цфасмана–Влэдуца, при этом правильно осознавая трудности, возникающие с $s$-кручением. Поэтому его результат о скорости $s$-кратно пересекающихся кодов включает член, отвечающий за размер подгруппы $s$-кручения. На самом деле Ч. Син использовал хорошо известную верхнюю границу $s^{2g}$ размера подгруппы $s$-кручения в якобиане кривой рода $g$.Естественно задать вопрос о лучших границах, особенно в асимптотическом случае $g\to\infty$. Эта проблема была независимо формализована и изучена в работах
Один из вопросов, поставленных в [72], состоит в следующем: можно ли для заданных $q$ и $s$ найти бесконечную последовательность кривых, обладающих большим числом рациональных точек (в идеале соответствующим константе Ихары $A(q)$), но у которых группа классов имеет малое $s$-кручение? Мерой того, насколько асимптотически малым может быть это $s$-кручение, служит следующая величина. Определение 7.1. Пусть $\delta_s^-(q)$ – наименьшее вещественное число такое, что существует последовательность $(\mathcal{X}_k)_{k\geqslant1}$ кривых над $\mathbb{F}_q$ возрастающего рода $g_k=g(\mathcal{X}_k)$, асимптотически обладающих числом рациональных точек и таких, что мощность подгруппы $s$-кручения $\mathcal{J}_k(\mathbb{F}_q)[s]$ группы рациональных точек над $\mathbb{F}_q$ якобиана $\mathcal{J}_k=\mathcal{J}(\mathcal{X}_k)$ удовлетворяет соотношению Открытая проблема 7.2. Оценить величину $\delta_s^-(q)$ для бесконечной последовательности кривых, для которых достигается граница Дринфельда–Влэдуца. У. Рандриамбололона выдвинул гипотезу, что $\delta_s^-(q)=0$ для всех $s$ и $q$, т. е. что существуют кривые с асимптотически максимальным числом точек над $\mathbb{F}_{q}$, группы классов которых обладают асимптотически пренебрежимым $s$-кручением. Особенно важен случай $s=2$, т. е. случай $2$-кручения. В работе [72] У. Рандриамбололона сосредоточивается на классических модулярных кривых, имеющих асимптотически максимальное число точек над $\mathbb{F}_{p^2}$ (для простого $p$). Размер группы классов такой кривой даётся определителем оператора Гекке. Это приводит к глубоким теоретико-числовым вопросам о чётности этих определителей, что в настоящее время остаётся гипотезой. В работе [37] И. Каскудо, Р. Крамер и Ч. Син обобщили условия, подобные (16), (17) или (20), превратив их в то, что они назвали системами уравнений Римана–Роха. Они адаптировали рассуждения в терминах мощности из [43], [80], [92] к этому более общему контексту. Для поля функций $F/\mathbb{F}_q$ пусть $\mathcal{J}_F$ – его группа классов дивизоров степени нуль. Далее, пусть $\mathcal{J}_F[r]$ – её подгруппа $r$-кручения, имеющая мощность $J_F[r]=|\mathcal{J}_F[r]|$. Основной результат работы [37] (см. [37; теорема 3.2]) состоит в следующем. Предложение 7.3. Пусть Для оценки размера подгрупп кручения в [37] вводится понятие предела кручения. Определение 7.4. Для каждого семейства $\mathcal{F}=\{F/\mathbb{F}_q\}$ полей функций с растущим родом $g(F)$ определим асимптотический предел Для $q$, являющегося степенью простого числа, целого числа $r>1$ и вещественного числа $a \leqslant A(q)$ пусть $\Upsilon$ обозначает множество семейств $\{\mathcal{F}\}$ полей функций над $\mathbb{F}_q$ таких, что род в каждом семействе стремится к $\infty$, а предел Ихары удовлетворяет неравенству $A(\mathcal{F}) \geqslant a$ для каждого $\mathcal{F}\in \Upsilon$. Определим асимптотическую величину $J_r(q,a)$ равенством Благодаря эквивалентности между кривыми и полями функций, при которой группа рациональных точек якобиана соответствует группе классов дивизоров нулевой степени, мы видим, что этот предел кручения связан с константой $\delta_r^-(q)$ соотношением Как мы увидим в п. 8.2, этот предел кручения может входить в качестве поправочного члена в знаменатель границы, справедливость которой утверждали И. Шпарлинский, М. Цфасман и С. Влэдуц. Однако возможен и другой подход, а именно прямое построение. 7.2. Прямое построениеПрямое построение заключается в нахождении наилучших дивизоров $D$ для применения АУЧЧ, т. е. дивизоров $D$, удовлетворяющих условиям (16) и (17) для заданных $q$ и $n$. Эта идея была в явном виде предложена С. Балле в [9; теорема 2.2], как будет отчетливо видно в п. 9.2. Ж. Шомин доказал в диссертации [41] (см. также [42]), что прямое построение оптимально в эллиптическом случае. Тем самым, как мы увидим в п. 9.1, он улучшил результат А. Шокроллаи из [79]. Затем У. Рандриамбололона предложил новые идеи, которые впервые были опубликованы в его работе [75] в связи с построением разделяющих кодов. Эта техника была развита далее в [73] с целью решения более общих систем уравнений Римана–Роха. В случае системы Римана–Роха, связанной с АУЧЧ, она позволяет эффективно построить решения, в большинстве случаев вплоть до оптимальной степени. Ключевым моментом является следующий результат [75; лемма 9], который можно рассматривать как численный вариант обобщённой формулы Плюккера. Лемма 7.5. Пусть $X$ – кривая рода $g$ над совершенным полем $K$, и пусть $\mathcal{A}$ – такой дивизор на $X$ степени $\deg\mathcal{A}\leqslant g-3$, что Тогда для всех точек $P\in X(K)$, кроме, возможно, не более $4g$ из них, имеем В [73] показано, как можно немного улучшить оценку $4g$ в случае, когда $K$ – конечное поле. Однако уже исходной леммы 7.5 достаточно для доказательства следующего результата [73; следствие 20]. Предложение 7.6. Пусть Предположим, что число точек степени $1$ поля $F$ удовлетворяет неравенству Тогда если то существует такой дивизор $\mathcal{D}$ поля $F/\mathbb{F}_q$, что $\mathcal{D}-\mathcal{Q}$ – неспециальный дивизор степени $g-1$, а $2\mathcal{D}-\mathcal{G}$ – нульмерный дивизор: Заметим, что для дивизора степени $g-1$ неспециальность и нульмерность эквиваленты, так что здесь равенства $i(\mathcal{D}-\mathcal{Q})=0$ и $\dim\mathcal{L}(\mathcal{D}-\mathcal{Q})=0$ эквивалентны. Заметим также, что при $N=2n+g-1$, $\mathcal{Q}=Q$ и $\mathcal{G}=P_1+\cdots+P_N$ предложение 7.6 даёт в точности то, что требуется в подходе И. Шпарлинского, М. Цфасмана и С. Влэдуца, описанном в п. 3.2. Единственным недостатком является условие, что $F$ должно иметь достаточно много рациональных точек. Кроме работы [73], доказательство этого предложения 7.6 можно также найти внутри доказательства теоремы 5.2, (c), из [74]. 8. Асимптотические верхние границыАсимптотическое изучение билинейной сложности умножения заключается в оценивании величин $m_q$, $M_q$, $m^{\rm sym}_q$, $M^{\rm sym}_q$. Это важно, поскольку в общем случае для этих величин имеются лучшие границы, чем для констант $C_q$ и $C^{\rm sym}_q$. Действительно, наилучшие известные семейства кривых, подходящих для применения алгоритма Д. В. и Г. В. Чудновских, известны асимптотически; в частности, таковы семейства кривых Шимуры, использованные И. Шпарлинским, М. Цфасманом и С. Влэдуцом [80]. Последние авторы установили следующий общий результат, который можно рассматривать как прямое следствие леммы 1.7 (или леммы 1.2 из [80])4. На самом деле неравенство (22) для величины $m_q$ неявно содержится уже в исходной работе Д. В. и Г. В. Чудновских (см. [43; (6.2)]). Таким образом, здесь важным новым вкладом И. Шпарлинского, М. Цфасмана и С. Влэдуца является неравенство (23) для величины $M_q$. Заметим, что эти неравенства верны также в симметричном случае, как следует из леммы 1.8. Используя теорему 2.2 вместе с леммой 8.1 или с леммой 8.2, мы легко получаем следующий полезный результат. Следствие 8.3. Для каждой степени простого числа $q$ справедливы неравенства Если ${q \geqslant 4}$, то Напомним, что $A(q)$ обозначает предел Ихары, определённый равенством где $N_q(g)$ – максимальное число рациональных точек над всеми алгебраическими полями функций над $\mathbb{F}_q$ рода $g$ (см. также определение 7.1).8.1. Верхние границы для $m_q$ и $M_q$Благодаря асимметричной интерполяции, которую допускает обобщённый АУЧЧ (см. п. 5.3), У. Рандриамбололона [74; теоремы 6.3, 6.4] получил границы для величин $m_q$ и $M_q$. Для $m_q$ граница такова. Для $M_q$ граница такова. В сочетании с леммой 8.1 и равенством $\mu_q(2)=3$ отсюда сразу вытекает следующее утверждение. Более того, из теоремы 9.18 Ж. Пьетан и У. Рандриамбололона вывели следующие асимптотические границы в общем случае. На настоящий момент это наилучшие опубликованные асимптотические границы в общем случае. Они выводятся из наилучших известных равномерных границ. Действительно, чисто асимптотические границы, приведённые в [69; теорема 5.3 и следствия 5.4, 5.5], не доказаны, как показано в [22].5 В дополнение к этому, в качестве следствия равномерных границ в предложении 9.19 (см. п. 9.3) У. Рандриамбололона недавно получил следующий результат. Наконец, М. Рамбо [71] получил наилучшую на настоящий момент асимптотическую границу для верхнего предела; а именно, верна следующая теорема. Теорема 8.9. Пусть $q$ – степень простого числа, a $r\geqslant 1$ и $l\geqslant 1$ – два натуральных числа. Тогда при условии $rlA'_r(q)-1>0$ выполняется неравенство В частности, этот результат позволяет получить следующую оценку (полагаем $(r,l)=(4,1)$ и используем тот факт, что $\mu_q(r,l)\leqslant \mu^{\rm sym}_q(r,l)=9$ в соответствии с таблицей 1 в п. 9.1 и $A'_r(2)=3/4$ по формуле (7)). 8.2. Верхние границы для $m^{\rm sym}_q$ и $M^{\rm sym}_q$Первоначально, используя исходные результаты Д. В. и Г. В. Чудновских, И. Шпарлинский, М. Цфасман и С. Влэдуц [80] получили верхние границы на $m^{\rm sym}_q$ и $M^{\rm sym}_q$ для любого $q$,6 которые не вполне доказаны из-за пробела, упомянутого в п. 3.2. В теоремах 6.3 и 6.4 из [74] У. Рандриамбололона получил следующие результаты, которые доказывают границы Шпарлинского–Цфасмана–Влэдуца с небольшим ограничением на диапазоны значений $A(q)$ и $q$. Для $m^{\rm sym}_q$ граница такова. Для $M^{\rm sym}_q$ граница такова. В сочетании с леммой 8.2 и равенством $\mu^{\rm sym}_q(2)=3$, из этого сразу вытекает следующее. С. Балле, Ж. Шомин и Ж. Пьетан [17] получили границы, которые немного менее точны, чем границы в вышеприведённых результатах, но выполняются для несколько большего множества значений $A(q)$ и $q$. Они доказали следующее. Предложение 8.14. Пусть $q$ – степень простого числа такая, что выполняется неравенство $A(q)>2$. Тогда Заметим, что это следствие несколько улучшает диапазон применимости границы (4), доказанной Д. В. и Г. В. Чудновскими. Далее, в случае произвольного $q$ в работе [17] доказано следующее утверждение. Более того, для $M^{\rm sym}_q$ в [17] получено то же значение для того же диапазона, что и для $m^{\rm sym}_q$ в следствии 8.15. Замечание 8.19. Для $q$, являющегося квадратом, граница (34) лучше, чем граница (35), кроме случая $q=16$. Когда $q$ – простое число, равномерные границы из предложения 9.14, полученные в [27; предложение 10] С. Балле и А. Зыкиным, дают асимптотическую оценку симметричной сложности, приведённую в следующем предложении. Следующая теорема М. Рамбо [71] по существу обобщает все известные формулы, предлагая наилучшие на сегодняшний день симметричные асимптотические границы для верхнего предела. Теорема 8.21. Пусть $q$ – степень простого числа, а $r\geqslant 1$ и $l\geqslant 1$ – два натуральных числа. Тогда при условии, что соответствующие знаменатели положительны, выполняется следующее: (a) если $r=1$ и $q$ таково, что $A'_1(q)>5$, то
$$
\begin{equation*}
M^{\rm sym}_q\leqslant \frac{2\mu^{\rm sym}_q(r,l)}{rl} \biggl(1+\frac{1}{rlA'_r(q)-1}\biggr);
\end{equation*}
\notag
$$
(b)
$$
\begin{equation*}
M^{\rm sym}_q\leqslant \frac{2\mu^{\rm sym}_q(r,l)}{rl} \biggl(1+\frac{2}{rlA'_r(q)-2}\biggr);
\end{equation*}
\notag
$$
(c) если $2\mid q$, то
$$
\begin{equation*}
M^{\rm sym}_q\leqslant \frac{2\mu^{\rm sym}_q(r,l)}{rl} \biggl(1+\frac{1+\log_q 2}{rlA'_r(q)-1-\log_q 2}\biggr);
\end{equation*}
\notag
$$
(d) если $2 \nmid q$, то Замечание 8.22. Сравнение с другими известными результатами показывает следующее. $\bullet$ Граница (a) включает в себя границы для верхних пределов из теоремы 8.4 и следствия 8.6, к которым она добавляет учёт кратности отображения значения. Этот инструмент был введён в [1] и усовершенствован в [39], а затем в [74; лемма 3.4]. $\bullet$ Граница (b) по сравнению с предложением 11 в [17] позволяет рассматривать отображения значения в точках произвольной степени. $\bullet$ Границы (c) и (d) позволяют рассматривать отображения значения в теореме 5.18 из [37] в точках нечётной степени $r$ и добавляют учёт кратности отображения значения. Кроме того, вместо формулы $A'_r(q)=(\sqrt{q^r}-1)/r$ из той же работы, которая не доказана в общем случае, в этих границах используется величина $A'_r(q)$. Заметим, что границы (b) и (c) дают строго лучшие числовые значения, чем предложение 8.18, для тех $q$, для которых предложение 8.18 имеет место.7 Действительно, достаточно положить $r=2$ (и $l=1$) и воспользоваться известным значением (10) величины $A'_2(q)$ из раздела 6. Следующие границы выводятся из теоремы 8.21, кроме случая $q=25$. Мы указываем критерии (a), (b) и т. д., из которых они выводятся, и используемые параметры $(r,l)$. Значения $A'_r(q)$ берутся напрямую из числа известных значений, приведённых в п. 6.3. Мы подробно излагаем, как выводились верхние границы для $\mu^{\rm sym}_q(r,l)$, поскольку многие из них не были опубликованы явным образом. Так как эти границы представляют большой интерес, мы дадим их сводку в п. 9.2. Для получения этих верхних границ мы зачастую используем формулу (58) из [74; лемма 3.2], вытекающую из неравенства (6) в п. 5.4:
$$
\begin{equation}
\mu^{\rm sym}_q(r,l)\leqslant \mu^{\rm sym}_{q^r}(1,l)\mu^{\rm sym}_{q}(r);
\end{equation}
\tag{37}
$$
в частности,
$$
\begin{equation*}
\mu^{\rm sym}_q(2,2)\leqslant \mu^{\rm sym}_{q^2}(1,2)\mu^{\rm sym}_{q}(2) \leqslant 3\cdot 3=9
\end{equation*}
\notag
$$
(как показал Ш. Виноград, обе последние величины действительно равны 3). Основной акцент должен быть сделан на верхней границе которая выводится из формулы (37) и из верхней границы которая была опубликована только в [70; табл. 2] при обосновании компоненты $(1,10)$. Вызывает сожаление, что эта рекордная граница не была заметнее выделена в [70]; эта ситуация была исправлена в [71; приложение к § 2.3], где приведена явная формула, доказывающая эту границу. Ещё большее сожаление вызывает тот факт, что компонента $(1,10)$ в таблицах 1 и 2 из [70] совершенно неверна: следует читать не $\mu^{\rm sym}_q(1,10)\leqslant 30$, а $\mu^{\rm sym}_q(2,5)\leqslant 30$, как можно заключить из формулы (37) выше. Эта ошибка была исправлена в [71; табл. 3.1]. Ошибки в таблицах 1 и 2 в [70] возникли из-за неверного применения формулы (37).Определим значения величин $\mu^{\rm sym}_q(r,l)$ и $\mu_q(r,l)$, требуемые для получения предложения 8.23. Все эти значения будут собраны воедино в пп. 9.2 и 9.3. Для $q=2$: из (b) при $(r,l)=(2,5)$ с $\mu^{\rm sym}_q(2,5)\leqslant 30$, как подчёркнуто выше. Для $q=3$: из (b) при $(r,l)=(2,3)$ с
$$
\begin{equation*}
\mu_3(2,3)\leqslant \mu^{\rm sym}_9(1,3)\mu^{\rm sym}_3(2,1)\leqslant \mu^{\rm sym}_3(1,3)\mu^{\rm sym}_3(2,1)\leqslant 5\cdot 3=15,
\end{equation*}
\notag
$$
где последнее значение 3 даётся алгоритмом Карацубы, а предыдущее значение 5 взято из [40; табл. 1, столбец (2.4)] (заметим, что 5 на самом деле равно асимметричной сложности в силу [28; табл. 3]). Для $q=4$: из (c) при $(r,l)=(2,2)$ с $\mu_4(2,2)\leqslant 8$ из [74; (88)] (заметим на полях: мы утверждаем, что это соотношение является даже равенством, как следует из неопубликованного полного перебора, выполненного во время работы над [70; § 1]). Для $q=5$: из (d) при $(r,l)=(2,2)$ с $\mu_5(2,2)\leqslant 8$ [74; (88)]. Для $q=7$: из (d) при $(r,l)=(2,1)$.8 Для $q=8$: из (c) при $(r,l)=(2,1)$. Для $q=9$: из (d) при $(r,l)=(2,1)$. Для $q=11$: из (d) при $(r,l)=(2,1)$. Для $q=25$ применяем предложение 8.17 (полученное в [17; предложение 2]9). Предложение 8.23. Выполняются следующие неравенства: Эти асимптотические границы – наилучшие на данный момент опубликованные числовые границы в симметричном случае10. Далее, если бы выполнялось равенство (14), т. е. $A'_6(3)=(3^3-1)/6=13/3$, что следовало бы, например, из справедливости гипотезы 6.8.1, то, применяя критерий (b) к случаю $(6,1)$ и используя неравенство $\mu^{\rm sym}_3(6,1)\leqslant 15$ из [39; табл. 1], мы получили бы $M^{\rm sym}_3\leqslant 65/12\simeq 5.41$. Подобные же соображения применимы к паре других границ, упомянутых в [71; табл. 2.2, строки “Adding theorem B”]. Аналогично, из справедливости гипотез 6.9.1, 6.10.1 и 6.11.1 следовали бы границы для соответствующих строк в [71; табл. 2.2]. Далее, используя величины общего характера, связанные с $2$-кручением (см. п. 7.1), И. Каскудо, Р. Крамер и Ч. Син в [37; теорема 6.27] (см. также [36]) получили следующий общий результат. Теорема 8.24. Пусть $\mathbb{F}_q$ – конечное поле. Если существует вещественное число $a \leqslant A(q)$, удовлетворяющее неравенству $a \geqslant 1+J_2(q,a)$, то В частности, если $A(q) \geqslant 1-J_2(a,A(q))$, то На самом деле И. Каскудо, Р. Крамер и Ч. Син сформулировали свой результат в терминах $m_q$, а не $m_q^{\rm sym}$ (см. подстрочное примечание 2 в п. 3.2). Здесь мы сформулировали его в терминах $m_q^{\rm sym}$, поскольку, как уже объяснялось, $2$-кручение существенным образом влияет на ситуацию, только когда мы ограничиваемся рассмотрением симметричных алгоритмов. Чтобы этот результат был полезным, его надо комбинировать с верхними оценками предела кручения. Некоторые верхние границы такого сорта можно без труда вывести из классических результатов А. Вейля о кручении в абелевых многообразиях. Однако И. Каскудо, Р. Крамер и Ч. Син получили впечатляющее улучшение, используя теорему Дойринга–Шафаревича. Это позволило им дать верхнюю оценку предела $2$-кручения некоторых явно заданных башен (таких как башня Гарсии–Штихтенота), а также установить следующий общий результат (см. [37; теорема 2.3, (iii)]). Несмотря на эти важные достижения, на данный момент этот подход не позволяет получить заявленные границы Шпарлинского–Цфасмана–Влэдуца для симметричной сложности. Действительно, для этого нужно показать, что предел $2$-кручения равен $0$ или, эквивалентным образом, что $\delta_2^-(q)=0$, а это – открытая проблема 7.2. Заметим, что все верхние границы для величины $M_q^{\rm sym}$, полученные И. Каскудо с соавторами в [38] и [37], не доказаны, так как их доказательства основаны на лемме IV из [38], которая не вполне верна, как показано в [22; § 3] (см. также [71]). Однако эти границы верны, если справедлива гипотеза 6.10.1. 11 9. Равномерные границы9.1. Некоторые точные значения для $\mu^{\rm sym}_{q}(n)$Напомним, что по теореме 2.2 имеем $\mu^{\rm sym}_q(n)=\mu_q(n)=2n-1$ тогда и только тогда, когда $n\leqslant q/2+1$. Следующее утверждение было установлено, с использованием АУЧЧ с хорошо подобранными эллиптическими кривыми, А. Шокроллаи [79] (в части строгого неравенства) и Ж. Шомином [42]. Теорема 9.1. Предположим, что Открытая проблема 9.2. До сих пор неизвестно, верно ли обратное. Более точно, вопрос состоит в следующем: предположим, что $\mu_q(n)=2n$; верны ли неравенства 39? Более того, для $n$, не охваченных теоремами 2.2 и 9.1, известно очень мало точных значений сложности, и все они получены в [43] – см. таблицу 1. Замечание 9.3. Билинейная сложность $\mu_2(4)=9$ была получена в [43; пример 6.1] с помощью вычислений на персональном компьютере. Легко проверить, что это значение может быть получено с помощью симметричного тензора, соответствующего итерации алгоритма Карацубы. Тогда Билинейная сложность $\mu_2(6)=15$ была получена в [43; пример 6.2] благодаря неравенству (1.7) из леммы 8.1 и нижней границе для длины бинарных кодов размерности 6, равной минимальному расстоянию. Открытая проблема 9.4. Найти точные значения для $\mu^{\rm sym}_q(n)$ и $\mu_q(n)$. Найти примеры, когда $\mu_q(n)<\mu^{\rm sym}_q(n)$. 9.2. Верхние границы для $\mu^{\rm sym}_{q}(n)$ и $\mu^{\rm sym}_{q}(l,r)$Результаты работы [6] и алгоритм из следствия 5.6 при $\ell_1=\ell_2=0$ позволяют получить следующее (см. [6], [24]). Теорема 9.5. Пусть $q$ – степень простого числа, и пусть $n$ – целое число, большее 1. Пусть $F/\mathbb{F}_q$ – поле алгебраических функций рода $g$, а $N_k$ – число точек степени $k$ в $F/\mathbb{F}_q$. Если $F/\mathbb{F}_q$ таково, что существует точка степени $n$ (что всегда выполняется при $2g+1 \leqslant q^{(n-1)/2}(q^{1/2}-1)$), то справедливы следующие утверждения. 1) Если $N_1 +a> 2n+2g-2$ для некоторого целого $a\geqslant 0$, то 2) Если существует неспециальный дивизор степени $g-1$ (что всегда выполняется при $q\geqslant 4$) и $N_1+a_1+2(N_2+a_2)>2n+2g-2$ для некоторых целых $a_1\geqslant 0$ и $a_2\geqslant 0$, то
$$
\begin{equation*}
\mu^{\rm sym}_q(n)\leqslant 3n+2g+\frac{a_1}{2}+3a_2-1.
\end{equation*}
\notag
$$
3) Если $N_1+2N_2>2n+4g-2$, то Замечание 9.6. Предыдущая теорема позволяет получать общие границы для билинейной сложности умножения в $\mathbb{F}_{q^n}$ над $\mathbb{F}_q$, используя бесконечные семейства алгебраических полей функций, определённых над $\mathbb{F}_q$. Но для фиксированного конечного поля $\mathbb{F}_q^n$, если мы хотим получить неулучшаемую границу, можно искать наилучшее поле алгебраических функций, определённое над $\mathbb{F}_q$ (т. е. с наименьшим возможным родом), удовлетворяющее условиям этой теоремы. Наконец, с использованием хороших башен алгебраических полей функций, удовлетворяющих теореме 9.5, границы для симметричной билинейной сложности были последовательно улучшены в [6], [8], [24], [19], [9], [16], [1], [21] и [22]; см. следующую теорему. Теорема 9.7. Пусть $q=p^r$ – степень простого числа $p$, и пусть $n$ – целое число, большее 1. Тогда симметричная билинейная сложность умножения в любом конечном поле $\mathbb{F}_{q^n}$ линейна относительно степени расширения $n$; точнее, существует такая константа $C^{\rm sym}_q$, что для любого $n>1$ выполняется неравенство Наилучшие на данный момент значения констант $C^{\rm sym}_q$ таковы: 1) если $q=2$, то (см. [21; следствие 29]);2) если $q=3$, то (см. [21]);3) если $q=p \geqslant 7$, то (см. [22; теорема 1.6, (ii)]);4) если $q=p^2 \geqslant 25$, то (см. [22; теорема 1.7, (ii)]);5) если $q=p^{2k} \geqslant 64 $ $(k \geqslant 2)$, то
$$
\begin{equation*}
C^{\rm sym}_q=2\biggl(1+\frac{p} {\sqrt{q}-3+(p-1)\sqrt{q}/(\sqrt{q}+1)}\biggr)
\end{equation*}
\notag
$$
(см. [1] и [22; теорема 1.7, (i)]); 6) если $q \geqslant 4$, то
$$
\begin{equation*}
C^{\rm sym}_q=3\biggl(1+\frac{4p/3}{q-3+2(p-1)q/(q+1)}\biggr)
\end{equation*}
\notag
$$
(см. [22; теорема 1.6, (i)]). Замечание 9.8. Заметим, что с помощью следствия 5.6, применённого к башне Гарсии–Штихтенота, Н. Арно в неопубликованной диссертации [1] получил границу 5) из теоремы 9.7. В работе [22] приведено подробное доказательство границы 5). В [22] также доказаны пересмотренные границы 3) и 4) для $\mu_{p^2}(n)$ и $\mu_p(n)$.12 Заметим также, что оценки сверху13, последовательно полученные в работах [11] и [10], выведены с использованием ошибочных формулировок И. Шпарлинского, М. Цфасмана и С. Влэдуца [80], упомянутых выше в п. 3.2. Вдобавок для некоторых конечных полей (в частности, для случаев $\mathbb{F}_2$, $\mathbb{F}_3$ и $\mathbb{F}_4$) для некоторых расширений имеются уточнённые границы, полученные в [39; табл. 1]. Мы напоминаем эти границы в виде таблицы 2. Таблица 2.Наилучшие известные границы для сложности в случае малых полей
Кроме того, в [15; табл. 3, 4] приведены границы для некоторых отдельных случаев расширений, улучшающие результаты в [39] и [74; пример 4.7]: Границы, приведённые в предыдущих таблицах, являются на данный момент наилучшими опубликованными оценками величины $\mu^{\rm sym}_q(n)$. Для $\mu_q(r,l)$ при $l>1$ различные значения были приведены М. Рамбо [71]; они объясняются в п. 8.2. Соберём эти значения для $q=2$ (включая случай $l=1$) в таблице 3. Таблица 3.Верхние границы для сложности $\mu^{\rm sym}_2(r,l)$
Для других значений $q$ приведём известные результаты, полученные в п. 8.2:
$$
\begin{equation*}
\begin{gathered} \, \mu^{\rm sym}_q(2,2)\leqslant 9, \qquad \mu^{\rm sym}_q(2,5)\leqslant 30; \\ \mu^{\rm sym}_4(1,5) \leqslant 10. \end{gathered}
\end{equation*}
\notag
$$
Недавно С. Балле и А. Зыкин [27] смогли улучшить все известные равномерные верхние границы для величин $\mu^{\rm sym}_{p^2}(n)$ и $\mu^{\rm sym}_{p}(n)$ в случае простого $p\geqslant 5$. Их подход заключается в использовании плотных семейств модулярных кривых, которые получены не асимптотически, а благодаря использованию теорем типа Хохайзеля о плотности простых чисел, в частности результата А. Дудека [49]. Заметим, что одна из основных идей, использованных в работе [27], была выдвинута С. Балле [11], использовавшим теорему Чебышёва (также называемую постулатом Бертрана) для оценки промежутков между простыми числами с целью построения как можно более плотных семейств модулярных кривых. В дальнейшем мотивированный работой [11] подход, основанный на подобных оценках промежутков между простыми числами (например, на оценке Бейкера–Хармана–Пинтца в [4]), был использован в препринте У. Рандриамбололоны [73] с целью улучшения верхних границ для величины $\mu^{\rm sym}_{p^2}(n)$, где $p$ – простое число. Подытоживая, приведём новые равномерные границы, полученные в этом препринте (и повторённые в [77]). Чтобы изложить эти границы, напомним следующие обозначения. Для любого бесконечного подмножества ${\mathcal A}$ натуральных чисел $\mathbb{N}$ и для любого вещественного $x>0$ пусть
$$
\begin{equation*}
\lceil x \rceil_{{\mathcal A}}=\min {\mathcal A}\cap [x,+\infty [
\end{equation*}
\notag
$$
обозначает наименьший элемент множества ${\mathcal A}$, больший или равный $x$. Положим также
$$
\begin{equation*}
\epsilon_{{\mathcal A}}(x)= \sup_{y\geqslant x}\frac{\lceil y \rceil_{{\mathcal A}}-y}{y}\,.
\end{equation*}
\notag
$$
Теперь мы можем сформулировать эти результаты. Предложение 9.9. Пусть $p\geqslant 7$ – простое число. Тогда справедливо следующее: 1) для всех $k\geqslant (p^2+p+1)/2$
$$
\begin{equation*}
\frac{1}{k}\mu^{\rm sym}_{p^2}(k)\leqslant 2\biggl(1+\frac{1+\epsilon_{{\mathcal P}}(24k/(p-2))}{p-2}\biggr),
\end{equation*}
\notag
$$
где $\mathcal{P}$ – множество простых чисел; 2) для всех $k\geqslant 1$
$$
\begin{equation*}
\frac{1}{k}\mu^{\rm sym}_{p^2}(k)\leqslant 2\biggl(1+\frac{1+10/139}{p-2}\biggr);
\end{equation*}
\notag
$$
3) для всех $k\geqslant e^{50}p$
$$
\begin{equation*}
\frac{1}{k}\mu^{\rm sym}_{p^2}(k)\leqslant 2\biggl(1+\frac{1.000000005}{p-2}\biggr);
\end{equation*}
\notag
$$
4) для всех $k\geqslant 16531(p-2)$
$$
\begin{equation*}
\frac{1}{k}\mu^{\rm sym}_{p^2}(k)\leqslant 2\biggl(1+\frac{1}{p-2}\biggl(1+\biggl(25\log^2 \frac{24k}{p-2}\biggr)^{-1}\biggr)\biggr);
\end{equation*}
\notag
$$
5) для достаточно больших $k$ Недавно, объединив свои результаты из [73] с результатами А. Дудека [49], как в [27], У. Рандриамбололона [77] улучшил почти все эти границы из [27], кроме случая $q=p^2=25$. Подытоживая, приведём новые равномерные границы для симметричной билинейной сложности, полученные соответственно в [77; следствие 10] и [27; предложение 7]. Предложение 9.10. Пусть $p\geqslant 7$ – простое число. Тогда 6) для всех $k\geqslant (p-2)e^{e^{33.217}}/24$ Предложение 9.11. Пусть $x_{\alpha}$ – константа из теоремы 6 в [27] (воспроизводимой в нашей теореме 9.12). Для любого целого $n\geqslant x_\alpha+3$ имеем Напомним следующий ключевой результат, являющийся прямым следствием результатов Р. Бейкера, Г. Хармана и Я. Пинтца [4] и А. Дудека [49], на котором существенным образом основаны утверждение 5) предложения 9.9, предложение 9.10, а также предложение 9.11. Их результаты относятся к явным теоремам о плотности простых чисел, обычно называемым теоремами типа Хохайзеля. В частности, приводимая ниже теорема [27; теорема 6] напрямую выводится из результата Р. Бейкера, Г. Хармана и Я. Пинтца (см. [4; теорема 1]), установленного в 2001 г., и недавнего результата А. Дудека 2016 г. (см. [49; теорема 1.1]). Теорема 9.12. Обозначим $k$-е простое число через $l_k$. Тогда существуют такие вещественные числа $\alpha<1$ и $x_{\alpha}$, что разность между двумя последовательными простыми числами $l_k$ и $l_{k+1}$ удовлетворяет неравенству для любого простого $l_k\geqslant x_{\alpha}$. В частности, можно взять $\alpha=2/3$ и $x_{\alpha}=\exp(\exp(33.217))$. Более того, можно взять $\alpha=21/40$ с некоторым значением $x_{\alpha}$, которое в принципе может быть эффективно найдено. Открытая проблема 9.13. Весьма нетривиальная проблема заключается в том, чтобы эффективно найти $x_{\alpha}$ для $\alpha=21/40$. Эта типичная задача аналитической теории чисел относится к так называемым проблемам типа Хохайзеля. Приводимое ниже предложение 9.14 относится к случаю простых полей. Оптимальный метод, использованный У. Рандриамбололоной [77] для решения систем Римана–Роха (см. п. 7.1), плохо работает для симметричных алгоритмов над простыми полями. Вместо этого для доказательства предложения 10 в [27] С. Балле и А. Зыкин использовали субоптимальный метод из работы [26], связанный с техникой спуска (см. п. 6.2), и получили следующее утверждение. Предложение 9.14. Пусть $p\geqslant 5$ – простое число, и пусть $x_{\alpha}$ – число из теоремы 9.12. 1) Если $p\ne 11$, то для любого целого $ n\geqslant (p-3)/2 x_\alpha+(p+1)/2$ имеем
$$
\begin{equation*}
\mu^{\rm sym}_{p}(n) \leqslant 3\biggl(1+ \frac{4(1+\epsilon_p(n))/3}{p-3}\biggr)n- \frac{2(1+\epsilon_p(n))(p+1)}{p-3}\,,
\end{equation*}
\notag
$$
где $\epsilon_p(n)=(2n/(p-3))^{\alpha-1}$. 2) Для $p=11$ и $ n\geqslant (p-3)x_\alpha+p-1=8x_\alpha+10$ имеем где $\epsilon_p(n)=(2n/(p-3))^{\alpha-1}$.9.3. Верхние границы для $\mu_{q}(n)$ и $\mu_{q}(l,r)$Используя асимметричную часть теоремы 5.3, Ж. Пьетан и У. Рандриамбололона [69] получили результаты для не обязательно симметричной билинейной сложности. В частности, они получили наилучшие границы в расширениях поля $\mathbb{F}_2$, полей $\mathbb{F}_p$, $\mathbb{F}_{p^2}$ для всех $p \geqslant 3$ и полей $\mathbb{F}_q$, $\mathbb{F}_{q^2}$ для всех $q \geqslant 4$. Предложение 9.15. Пусть $q$ – степень простого числа и $d$ – натуральное число, все собственные делители которого удовлетворяют неравенству $j < (q+1+\epsilon(q))/2$, если $q \geqslant 4$, и неравенству $j \leqslant q/2+1$, если $q \in \{2,3\}$. Пусть $F/\mathbb{F}_q$ – поле алгебраических функций рода $g \geqslant 2$ с $N_i$ точками степени $i$, и пусть $\ell_i$ – такие целые числа, что $0 \leqslant \ell_i \leqslant N_i$ для всех $i\mathrel{|}d$. Предположим, что (i) в поле $F/\mathbb{F}_q$ существует точка степени $n$, (ii) $\displaystyle\sum_{i\mathrel{|}d} i(N_i+\ell_i) \geqslant 2n+g+\alpha_q$, где $\alpha_2=5$, $\alpha_3=\alpha_4=\alpha_5=2$ и $\alpha_q=-1$ при $q > 5$. Тогда гдеВыбирая $d=1,2$ или 4, они получили два приводимых ниже следствия. Следствие 9.16. Пусть $q \geqslant 3$ – степень простого числа, а $F/\mathbb{F}_q$ – поле алгебраических функций рода $g \geqslant 2$ с $N_i$ точками степени $i$. Пусть $\ell_i$ – такие целые числа, что $0 \leqslant \ell_i \leqslant N_i$. Предположим, что (i) в поле $F/\mathbb{F}_q$ есть точка степени $n$, (ii) $N_1+\ell_1+2(N_2+\ell_2) \geqslant 2n+g+\alpha_q$, где $\alpha_3=\alpha_4=\alpha_5=2$ и $\alpha_q=-1$ при $q > 5$. Тогда
$$
\begin{equation*}
\begin{aligned} \, \mu_3(n) &\leqslant 3n+\frac{3}{2}g+\frac{3}{2}(\ell_1+2\ell_2)+ \frac{9}{2}\,, \\ \mu_q(n) &\leqslant 3n+\frac{3}{2}g+\ell_1+2\ell_2+\frac{9}{2}\quad\textit{при } q=4\textit{ или } 5, \end{aligned}
\end{equation*}
\notag
$$
а при $q > 5$ и, в частном случае, когда $N_2=\ell_2=0$, Следствие 9.17. Пусть $F/\mathbb{F}_2$ – поле алгебраических функций рода $g \geqslant 2$ с $N_i$ точками степени $i$, и пусть $\ell_i$ – такие целые числа, что $0 \leqslant \ell_i \leqslant N_i$. Предположим, что (i) в поле $F/\mathbb{F}_2$ есть точка степени $n$, (ii) $\displaystyle\sum_{i\mathrel{|}4}i(N_i+\ell_i) \geqslant 2n+g+5$. Тогда Далее они установили новые асимметричные равномерные границы. Теорема 9.18. Пусть $n \geqslant 2$. Тогда: 1) если $q=2$, то 2) если $q=3$, то 3) если $q=4$, то 4) если $q=5$, то 5) если $q \geqslant 4$, то
$$
\begin{equation*}
\mu_{q^2}(n) \leqslant 2\biggl(1+\frac{p}{q-2+(p-1)q/(q+1)}\biggr)n-1;
\end{equation*}
\notag
$$
6) если $p \geqslant 3$, то
$$
\begin{equation*}
\mu_{p^2}(n) \leqslant 2\biggl(1+\frac{2}{p-1}\biggr)n-1;
\end{equation*}
\notag
$$
7) если $q>5$, то
$$
\begin{equation*}
\mu_q(n) \leqslant 3\biggl(1+\frac{p}{q-2+(p-1)q/(q+1)}\biggr)n;
\end{equation*}
\notag
$$
8) если $p>5$, то Недавно с помощью тех же определённых над $\mathbb{F}_p$ плотных семейств модулярных кривых, что используются для доказательства предложения 9.9 в п. 9.2, У. Рандриамбололона получил следующий результат. Предложение 9.19. Пусть $p\geqslant 7$ – простое число. Тогда: 1) для всех $k> (p+1)/2$
$$
\begin{equation*}
\frac{1}{k}\mu_{p}(k)\leqslant 3\biggl(1+\frac{1+\epsilon_{{\mathcal P}}(24k/(p-2))}{p-2}\biggr),
\end{equation*}
\notag
$$
где $\mathcal{P}$ – множество простых чисел; 2) для всех $k\geqslant (p-2)e^{e^{33.217}}/24$
$$
\begin{equation*}
\frac{1}{k}\mu_{p}(k)\leqslant 3\biggl(1+\frac{1}{p-2} \biggl(1+3\biggl(\frac{24k}{p-2}\biggr)^{-1/3}\biggr)\biggr);
\end{equation*}
\notag
$$
3) для достаточно больших $k$ Замечание 9.20. Заметим, что здесь удаётся обойти трудности решения систем Римана–Роха (см. п. 7.2) в контексте симметричных алгоритмов, использующих кривые без достаточного количества рациональных точек, так как предыдущий результат получен применением асимметричной версии алгоритма типа Чудновских (см. пп. 5.3 и 5.4) над точками степени 2. Напомним отдельные значения величин $\mu_q(l,r)$, полученные в п. 8.2:
$$
\begin{equation*}
\mu_3(2,3) \leqslant 15, \quad \mu_4(2,2) \leqslant 8, \quad \mu_5(2,2) \leqslant 8.
\end{equation*}
\notag
$$
10. Эффективное построение алгоритмов билинейного умноженияВ этом разделе нас интересуют вопросы эффективного построения алгоритмов билинейного умножения в конечных полях. Эффективному построению алгоритмов типа Чудновских уделялось крайне мало внимания. В основном все такие алгоритмы содержатся в статьях [29], [7], [39], [15], [2] и [3]. 10.1. Неасимптотическое построение10.1.1. Классические алгоритмы умножения(a) Пример эффективного симметричного построения, использующего эллиптическую кривую. Этот пример, приведённый У. Баумом и А. Шокроллаи [29], является первым эффективным построением алгоритма билинейного умножения, реализующим АУЧЧ. Он касается алгоритма умножения в конечном поле $\mathbb{F}_{256}$ над $\mathbb{F}_4$ (т. е. при $q=4$ и $n=4$), использующего максимальную эллиптическую кривую Ферма $y^2+y=x^3+1$. Билинейная сложность $\mu^{\rm sym}({\mathcal U})$ этого симметричного алгоритма ${\mathcal U}$ оптимальна, причем
$$
\begin{equation*}
\mu^{\rm sym}({\mathcal U})=\mu^{\rm sym}_q(n)=\mu_q(n)=2n=8.
\end{equation*}
\notag
$$
(b) Пример эффективного симметричного построения, использующего гиперэллиптическую кривую. Этот пример, приведённый С. Балле в [7], является первым эффективным построением алгоритма билинейного умножения, реализующим АУЧЧ для алгебраической кривой рода $g>1$. Он касается алгоритма умножения в конечном поле $\mathbb{F}_{16^n}$ над $\mathbb{F}_{16}$ (точнее, при $q=16$ и $n=13,14,15$), использующего максимальную гиперэллиптическую кривую $y^2+y=x^5$. Билинейная сложность этого симметричного алгоритма ${\mathcal U}$ квазиоптимальна и такова, что что доказывает неравенства $2n\leqslant\mu_q(n)\leqslant\mu^{\rm sym}_q(n)\leqslant 2n+1$.Открытая проблема 10.1. Найти точное значение билинейной сложности для упомянутых конечных полей $\mathbb{F}_{16^n}$ над $\mathbb{F}_{16}$ при $n=13,14,15$, если известно, что эта сложность равна $2n$ или $2n+1$. Оптимизировать скалярную сложность этих построений. (c) Пример эффективного симметричного построения, использующего точки высших степеней и производные отображения значения на рациональных точках на эллиптических кривых. Этот пример, приведённый М. Сенком и Ф. Озбудаком [39], является первым эффективным построением алгоритма билинейного умножения, который реализует комбинацию обобщений АУЧЧ, предложенных в работе [24] с использованием точек степени 1 и 2 и в работе [1] с использованием производных отображений значения. Заметим, что в этом примере производные отображения значения используются только на рациональных точках порядка 1. Точнее, он касается алгоритма умножения в конечном поле $\mathbb{F}_{3^9}$ над $\mathbb{F}_{3}$, использующего неоптимальную эллиптическую кривую $y^2=x^3+x+2$. В этом случае в [39] используется отображение значения на четырёх рациональных точках с производным отображением значения на двух из них, а также отображение значения на шести точках степени 2. Для билинейной сложности этого симметричного алгоритма ${\mathcal U}$ имеем (d) Пример эффективного асимметричного построения, использующего точки высших степеней на алгебраических кривых. Этот пример, приведённый С. Балле, Н. Бодру, А. Боннеказе и М. Тукумули в [12] (и анонсированный ими в [13]) и М. Тукумули в [87], является первым эффективным построением алгоритма билинейного умножения, который реализует асимметричное обобщение АУЧЧ, предложенное в [74]. Заметим, что эти примеры используют два разных пространства Римана–Роха ${\mathcal L}(D_1)$ и ${\mathcal L}(D_2)$ без производных отображений значения. Точнее, в [12] построены три алгоритма. Первый пример касается алгоритма умножения в конечном поле $\mathbb{F}_{16^{13}}$ над $\mathbb{F}_{16}$, использующего максимальную гиперэллиптическую кривую $y^2+y=x^5$ и только рациональные точки на ней. Второй пример касается алгоритма умножения в конечном поле $\mathbb{F}_{4^{4}}$ над $\mathbb{F}_{4}$, использующего оптимальную кривую $y^2+y=\dfrac{x}{x^3+x+1}$ над $\mathbb{F}_4$. Третий пример касается алгоритма умножения в конечном поле $\mathbb{F}_{2^{5}}$ над $\mathbb{F}_{2}$, использующего оптимальную кривую $y^2+y=\dfrac{x}{x^3+x+1}$ над $\mathbb{F}_4$. 10.1.2. Параллельные алгоритмы, предназначенные для умножения и возведения в степеньБлагодаря новой конструкции АУЧЧ К. Атигечи, С. Балле, А. Боннеказе и Р. Роллан [2], [3] разработали эффективные алгоритмы как для возведения в степень, так и для умножения в конечных полях. Эти алгоритмы приспособлены к аппаратной реализации и допускают параллельные вычисления, в то же время сохраняя малое число билинейных умножений. Заметим, что пока в практических реализациях алгоритмов умножения над конечными полями не удавалось одновременно оптимизировать число скалярных умножений, сложений и билинейных умножений. Что касается алгоритмов возведения в степень, представляет интерес использование нормального базиса, поскольку в нем $q$-я степень элемента получается простым циклическим сдвигом координат. Остаётся вопрос, как эффективно реализовать умножение, чтобы одновременно иметь быстрое умножение и быстрое возведение в степень. В 2000 г. С. Гао и др. [56] показали, что методы быстрого умножения можно адаптировать для нормальных базисов, построенных с гауссовскими периодами. Они показали, что если $\mathbb{F}_{q^n}$ представлено в нормальном базисе над $\mathbb{F}_q$, порождённом гауссовским периодом типа $(n,k)$, то умножение в $\mathbb{F}_{q^n}$ может вычисляться за $O(nk\log(nk)\log\log(nk))$ операций, а возведение в степень – за $O(n^2k\log k \log\log(nk))$ операций в $\mathbb{F}_q$ (при условии, что $q$ мало). Этот результат представляет ценность, когда $k$ ограничено. Однако в общем случае $k$ ограничено сверху величиной $O(n^3\log^2(nq))$. В 2009 г. Ж.-М. Кувень и Р. Лерсье построили в [45; теорема 4] два семейства базисов (называемых эллиптическим и нормальным эллиптическим) для расширений конечных полей, из которых они получили модель $\Xi$, определённую следующим образом. С каждой парой $(q,n)$ они связали модель $\Xi(q,n)$ расширения поля $\mathbb{F}_q$ степени $n$, для которой существует такая положительная константа $K$, что выполняется следующее: – элементы поля $\mathbb{F}_{q^n}$ представлены векторами, у которых число компонент из $\mathbb{F}_q$ ограничено сверху величиной $Kn(\log n)^2\log (\log n)^2$; – существует алгоритм, перемножающий два элемента за счёт умножений в $\mathbb{F}_q$;– возведение в $q$-ю степень заключается в циклическом сдвиге координат. Поэтому они показали, что для каждого расширения конечного поля существует модель, которая допускает как быстрое умножение, так и быстрое применение автоморфизма Фробениуса. Их модель обладает тем преимуществом, что она существует для всех расширений. Однако, как отмечено в [45; § 4.3.4], билинейная сложность их алгоритма не выдерживает конкуренции с наилучшими известными методами. Действительно, ясно, что для такой модели требуется по крайней мере $Kn(\log n)^2(\log\log n)^2$ билинейных умножений. Авторы работы [3] предлагают другую модель со следующими характеристиками. (a) Модель основана на АУЧЧ, так что алгоритм умножения имеет билинейную сложность порядка $O(n)$, что является оптимальной границей. (b) Модель приспособлена к параллельным вычислениям. Отсюда следует, что время счёта, используемое для выполнения умножения или возведения в любую степень, может быть легко сокращено при подходящем числе процессоров. Поскольку этот метод имеет билинейную сложность умножения порядка $O(n)$, его можно распараллелить, чтобы получить постоянную сложность по времени, используя $O(n)$ процессоров. Вышеупомянутые предшествующие работы [56] и [45] не давали никакого параллельного алгоритма (такой алгоритм сложнее придумать, чем последовательный). (c) Возведение в $q$-ю степень осуществляется циклическим сдвигом координат и может считаться не требующим затрат. Таким образом, при выполнении возведения в степень возможна эффективная параллелизация. (d) Скалярная сложность возведения в степень у этого алгоритма снижена по сравнению со стандартным возведением в степень, использующим АУЧЧ, благодаря подходящему представлению базиса пространства Римана–Роха ${\mathcal L}(2D)$ во втором отображении значения. Точнее, представление в нормальном базисе поля классов вычетов переносится в присоединённое пространство Римана–Роха ${\mathcal L}(D)$, и возведение в $q$-ю степень заключается в циклическом сдвиге $n$ первых координат векторов, лежащих в пространстве Римана–Роха ${\mathcal L}(2D)$. (e) Модель использует метод Копперсмита–Винограда [44] (обозначаемый CW) или любые его варианты для ускорения вычислений матричных произведений и уменьшения числа скалярных операций. Открытая проблема 10.2. Следовало бы более подробно изучить строение матриц, встречающихся в АУЧЧ. Однако, к сожалению, на сегодняшний день для построения наилучших матриц нет ни теоретического инструментария, ни критериев, поскольку эти матрицы зависят от геометрии кривых, от поля определения этих кривых, а также от участвующих пространств Римана–Роха. Изучение подходящих стратегий оптимизации АУЧЧ с этой точки зрения можно найти в [14]. В частности, улучшен построенный У. Баумом и А. Шокроллаи [29] АУЧЧ, использующий эллиптическую кривую для умножения в $\mathbb{F}_{256}/\mathbb{F}_4$. Остаётся открытым вопрос о том, как выбирать геометрические объекты, чтобы минимизировать число нулей в матрице отображения значения на рациональных точках кривой. 10.2. Асимптотическое построениеД. В. и Г. В. Чудновские утверждали в [43], что за полиномиальное время можно построить алгоритм билинейного умножения, реализующий билинейную сложность, для которой достигается верхняя граница для $m_q$. Затем И. Шпарлинский, М. Цфасман и С. Влэдуц [80] заметили, что аргументации Чудновских недостаточно. Действительно, построение таких алгоритмов включает некоторый случайный выбор дивизоров, обладающих заданными свойствами, из экспоненциально большого множества дивизоров. И. Шпарлинский, М. Цфасман и С. Влэдуц получили частичный результат относительно этого полиномиального по времени построения. Пусть $q=p^{2m}\geqslant 49$, и пусть либо $X_i=X_0(11l_i)$ – редукция классической модулярной кривой, где $l_i$ – $i$-е простое число (для $q=p^2$), либо $X_i=X_0(p_i)$, где $p_i$ – неприводимый многочлен над $\mathbb{F}_q$ нечётной степени, взаимно простой с $q-1$ (для $q=p^{2m}$), а $X_0(p_i)$ – редукция модулярной кривой Дринфельда. Заметим, что $\{X_i\}$ – семейство абсолютно неприводимых гладких кривых рода $g=g_i$, причём $\displaystyle\lim_{g \to \infty} \dfrac{|X(\mathbb{F}_q)|}{g}={\sqrt q}-1$. В [80] доказан следующий результат. Предложение 10.3. Предположим, что на любой кривой $X$ из описанного выше семейства $\{X_i\}$ модулярных кривых, явно задана точка $Q$ некоторой степени $n$ такой, что Пусть $Q$ задана своими координатами в некоторых проективных вложениях. Тогда для данной последовательности натуральных чисел $n\to \infty$ можно за полиномиальное время построить такую последовательность ${\mathcal U}=({\mathcal U}_i)$ алгоритмов билинейного умножения в конечных полях $\mathbb{F}_{q^n}$, что Это предложение означает, что для полиномиального построения алгоритма с линейной сложностью нужно явным образом (т. е. полиномиально) построить точки соответствующих степеней на модулярных кривых (или на других кривых с большим числом точек). К сожалению, пока неизвестно, как найти такие точки. В [74; замечание 6.6] У. Рандриамбололона улучшил этот результат при том же условии относительно построения точки степени $n$. Точнее, при условии существования такой точки он получил полиномиальное по времени (относительно $n$) построение алгоритма умножения (соответственно симметричного алгоритма умножения) в $\mathbb{F}_{q^n}/\mathbb{F}_q$ длины $2n(1+1/(\sqrt{q}-2))+o(n)$ при $q\geqslant 9$ (соответственно при $q\geqslant 49$). С. Балле, А. Боннеказе и М. Тукумули [15] предложили полиномиальное построение симметричного алгоритма умножения эллиптического типа Чудновского–Чудновского (т. е. использующего интерполяционный метод Чудновского–Чудновского на эллиптической кривой) за время
$$
\begin{equation*}
O\biggl(n\biggl(\frac{2q}{K}\biggr)^{\log^{\star}(n)}\biggr),
\end{equation*}
\notag
$$
где
$$
\begin{equation*}
\log^{\star}(n)=\begin{cases} 0, & \text{если}\ n\leqslant 1, \\ 1+\log^{\star}\log (n) & \text{в противном случае}, \end{cases}
\end{equation*}
\notag
$$
а $K=2/3$, если характеристика поля $\mathbb{F}_q$ равна 2 или 3, и $K=5/8$ в противном случае. Заметим, что длина лишь квазилинейна по $n$. Однако это построение не имеет ограничения, связанного с построением точки степени $n$. Более того, это асимптотическое построение реализуется не на бесконечном семействе подходящих кривых, как вышеприведённые результаты, а благодаря использованию последовательности $\mathcal{A}_{q,n}$ симметричных алгоритмов билинейного умножения, построенных по произвольной эллиптической кривой, определённой над $\mathbb{F}_q$, и использующих точки высокой степени на этой кривой. Н. Бшоути [32] приводит детерминистское, полиномиальное по времени построение тестера типа $(\mathcal{H}\mathcal{L}\mathcal{F}(\mathbb{F}_q,n,d), \mathbb{F}_{q^n},\mathbb{F}_q))$ и размера $\mu=O(d^{\tau(d,q)}n)$, где
$$
\begin{equation}
\tau(d,q)=\begin{cases} 3, & \text{если} \ q\geqslant cd^2, \ c>1 \text{ - константа}, q \text{ - полный квадрат}; \\ 4, & \text{если} \ q\geqslant cd, \ c>1 \text{ - константа}; \\ 5, & \text{если} \ q\geqslant d+1; \\ 6, & \text{если} \ q=d. \end{cases}
\end{equation}
\tag{41}
$$
На основе [32] в следствии 2 из [33] Н. Бшоути даёт первое полиномиальное по времени построение полилинейного алгоритма умножения с линейной мультипликативной сложностью порядка $O(d^{\tau(d,q)}n)$ для перемножения $d$ элементов в любом расширении конечного поля $\mathbb{F}_{q^n}$. Это решает открытую проблему детерминистского полиномиального по времени построения билинейного (т. е. с $d=2$) алгоритма перемножения двух элементов в конечных полях с линейной билинейной сложностью [43], [80], [9]. Однако это не решает проблему детерминистского полиномиального по времени построения билинейного алгоритма типа Чудновского–Чудновского. Действительно, метод Н. Бшоути основан только на эквивалентности между оптимальным размером тестера и полилинейной сложностью. Точнее, минимальный размер тестера для $\mathcal{H}\mathcal{L}\mathcal{F}(\mathbb{F}_q,n,d)$ оказывается эквивалентным рангу тензора перемножения $d$ элементов в $\mathbb{F}_{q^n}$ над $\mathbb{F}_q$. Минимальный размер тестера для $\mathcal{H}\mathcal{P}(\mathbb{F}_q,n,d)$ эквивалентен симметричному рангу тензора перемножения $d$ элементов. 11. Приложение: доказательства теоремы 8.21, теоремы 8.9 и предложения 6.11.3Здесь мы приводим в сжатом виде доказательства из [71; гл. II, § 1.2-3]. 11.1. Исправление (и обобщение) критерия И. Каскудо и др.Следующая теорема отслеживает 2-кручение в наихудшем случае. Она является непосредственным обобщением теоремы 5.18 из работы [37]. Параметры будут указаны в следующем пункте, где выводятся критерии для асимптотических границ. Теорема 11.1. Пусть $X$ – кривая рода $g$ над $\mathbb{F}_q$, где $q\geqslant 2$ – любая степень простого числа, и пусть $m\geqslant 1$ – целое число. Предположим, что $X$ имеет замкнутую точку $Q$ степени $\deg Q=m$ (достаточным условием для этого является выполнение неравенства $2g+1\leqslant q^{(m-1)/2}(q^{1/2}-1)$). Рассмотрим такое семейство целых чисел $n_{d,u}\geqslant 0$ (при $d,u\geqslant1$), что почти все они равны нулю и для любого $d$ выполняется равенство где $B_d(X)$ обозначает число замкнутых точек кривой $X$ степени $d$.Пусть $R$ – наименьшее целое такое, что
$$
\begin{equation}
R \geqslant g(1+\log_q 2)+2m+ 3\log_q\frac{3qg}{(\sqrt{q}-1)^2}+2, \quad \textit{если } 2\mathrel{|}q,
\end{equation}
\tag{43}
$$
Тогда при условии выполняется неравенство В следующем предложении собраны верхние границы, используемые в доказательстве. Первые две вытекают из [66; гл. II, вопрос 1 (или гл. II, § 6)], в то время как третья заимствована из [37; предложение 3.4]. Предложение 11.2. Пусть $\mathbb{F}_q$ – конечное поле и $X$ – кривая над $\mathbb{F}_q$ рода $g\geqslant 1$. Пусть $J$ – якобиан кривой $X$, а $J(\mathbb{F}_q)$ – группа рациональных классов. 1) Если $q$ нечётно, то $J(\mathbb{F}_q)[2]\leqslant 2^{2g}$. 2) Если $q$ чётно, то $J(\mathbb{F}_q)[2]\leqslant 2^g$. 3) Пусть $h$ – число классов кривой $X$, и для любого целого $i$, удовлетворяющего $0\leqslant i \leqslant g-1$, пусть $A_i$ – число $\mathbb{F}_q$-рациональных эффективных дивизоров степени $r$. Тогда Будем следовать первоначальному доказательству теоремы И. Каскудо и др. (рассматривая только случай чётного $q$; нечётный случай аналогичен, надо только использовать соответствующие верхние границы из предложения 11.2). Прибавление слагаемых $-\log_q(3qg/(\sqrt{q}-1)^2)$ и $2g(1-\log_q 2)$ к обеим частям неравенства (43) даёт
$$
\begin{equation*}
2g+2m+2\log_q\frac{3qg}{(\sqrt{q}-1)^2} \leqslant g(1-\log_q 2)+R-\log_q\frac{3qg}{(\sqrt{q}-1)^2}-2.
\end{equation*}
\notag
$$
Таким образом, между двумя частями предыдущего неравенства существует чётное целое число $2d$. Возведение $q$ в степень следующих неравенств:
$$
\begin{equation*}
\text{левая часть} \leqslant 2d \quad \text{и}\quad 2d\leqslant \text{правая часть}
\end{equation*}
\notag
$$
даёт соответственно
$$
\begin{equation}
\frac{g}{q^{g-(2g-d+m)-1 }(\sqrt{q}-1)^2} \leqslant \frac{1}{3}
\end{equation}
\tag{47}
$$
и
$$
\begin{equation}
\frac{g\cdot 2^g}{q^{g-(2d-R)-1}(\sqrt{q}-1)^2} \leqslant \frac{1}{3}\,.
\end{equation}
\tag{48}
$$
Используя верхнюю границу 3) из предложения 11.2 и объединяя неравенства (47) и (48) с верхней границей 2) из предложения 11.2, получаем
$$
\begin{equation}
h>\frac{2}{3}h\geqslant A_{2g-d+m}+J(\mathbb{F}_q)[2]A_{2d-R}.
\end{equation}
\tag{49}
$$
Теперь выберем такое семейство $\{P\}$ попарно различных утолщённых точек на кривой $X$, что для каждой пары $(d,u)$ среди них имеется в точности $n_{d,u}$ точек степени $d$ и кратности $u$ (это возможно по условию). Пусть $G$ – их сумма как дивизоров, а $Q$ – замкнутая точка степени $m$, как в условии теоремы. Из того, что по предположению (45) дивизор $G$ имеет степень больше $R$, и из общего критерия в теореме 6 из [36; § 4] вместе с неравенством (49) следует, что существует дивизор $D=X$ степени $d$, удовлетворяющий следующей системе условий зануления пространств Римана–Роха (где $K$ – канонический дивизор кривой $X$): Таким образом, для дивизоров $G$ и $D$ выполняются критерии (i$'$) и (ii$'$) теоремы 3.5 работы [74]. 11.2. Вывод границ из теоремы 8.21Пусть $(X_s)_s$ – плотная последовательность кривых над $\mathbb{F}_q$ с родом $g_s$, стремящимся к бесконечности, и с соответствующим $A'_r(q)$ отношением числа точек степени $r$ к роду. Замечая, что $A'_r=A'_r(q)$, запишем эти условия следующим образом: Сначала докажем границу (b) из теоремы 8.21, которая обобщает предложение 3 из [17], но идеи доказательства которой уже присутствовали в теореме 3.2 из [20]. Для данного целого $n$ пусть $s(n)$ – наименьшее целое число такое, что Из равенства (53) ясно (или в любом случае будет ясно из последующих эквивалентностей), что такое целое $s(n)$ существует, если знаменатель в критерии (b) теоремы 8.21 строго положителен.Более того, для достаточно большого $g$ в замечании 4.4 к предложению 4.3 из [23] в общем случае утверждается существование нульмерного дивизора степени $g-5$ на $X_{s(n)}$. Таким образом, существует неспециальный дивизор $R$ степени (ниже чем) $g+3$. Поэтому следствие из предложения 5.1 в [74] применимо к (55). Полагая все $n_{d,u}$ равными нулю, кроме $n_{r,l}$, равного $B_r(X_{s(n)})$, отсюда получаем
$$
\begin{equation}
\mu^{\rm sym}_q(n) \leqslant \mu^{\rm sym}_q(r,l) B_r(X_{s(n)}).
\end{equation}
\tag{56}
$$
Теперь свяжем асимптотическое поведение $g_{s(n)}$ с асимптотическим поведением $B_r(X_{s(n)})$. Из минимальности целого числа $s(n)$, удовлетворяющего (55), вытекает, что
$$
\begin{equation*}
rl B_r(X_{s(n)})-2g_{s(n)}\geqslant 2n+3>rlB_r(X_{s(n)-1})-2g_{s(n)-1}.
\end{equation*}
\notag
$$
Поделив эти два неравенства на $g_{s(n)-1}$ и применив асимптотические эквивалентности (53) и (54) (и (52)), получаем, что
$$
\begin{equation*}
rl A'_r-2+o(n)\geqslant \frac{2n}{g_{s(n)}}+o(1)>rlA'_r-2 +o(n).
\end{equation*}
\notag
$$
Отсюда вытекает асимптотическая эквивалентность (из которой, в частности, следует, что $o(n)=o(g_{s(n)})$). Теперь можно поделить обе части оценки сверху (56) на предыдущее равенство:
$$
\begin{equation*}
\frac{\mu^{\rm sym}_q(n)}{n} \leqslant \mu^{\rm sym}_q(r,l)\cdot 2\,\biggl(\frac{A'_r g_{s(n)}+o(n)}{(rlA'_r-2)g_{s(n)}+o(n)}\biggr).
\end{equation*}
\notag
$$
Умножая и деля скобку в правой части на $rl$, затем отнимая и прибавляя $2g_{s(n)}$ к числителю правой части и устремляя $n$ к бесконечности, получаем требуемый результат. Остальные границы выводятся аналогичным образом. А именно, для заданного целого $n$ надо рассмотреть наименьшее целое число $s(n)$ такое, что выполняются приводимые ниже неравенства, а затем применить соответствующие критерии, полагая все $n_{d,u}$, кроме $n_{r,l}=B_r(X_{s(n)})$, равными нулю:
$$
\begin{equation*}
\begin{alignedat}{2} rl B_r(X_{s(n)})-g_{s(n)} & \geqslant 2n+5,&&\quad \text{затем применяется предложение 5.7 из [74]} \\ &&&\qquad\text{ - в случае теоремы 8.9}; \\ rl B_r(X_{s(n)})-g_{s(n)} & \geqslant 2n+1,&&\quad \text{затем применяется предложение 5.2, с), из [74]} \\ &&&\qquad\text{- в случае теоремы 8.21, (a)}; \\ rl B_r(X_{s(n)})-g_{s(n)}&\geqslant 2n+1 &&\quad\text{(то же самое } s(n)) \\ &&&\qquad\text{ - в случае предложения 6.11.3} \end{alignedat}
\end{equation*}
\notag
$$
(для обоснования последнего критерия, в силу предложения 6.11.2, просто положим $\operatorname{Cl}_0(X)(\mathbb{F}_q)[2]=0$ в доказательстве теоремы 11.1);
$$
\begin{equation*}
\begin{aligned} \, rl B_r(X_{s(n)})-(1+\log_q2)g_{s(n)} & \geqslant 2n+3\log_q\frac{3qg_{s(n)}}{(\sqrt{q}-1)^2}+3 \\ &\qquad\text{ - в случае теоремы 8.21, (c)}; \\ rl B_r(X_{s(n)})-(1+2\log_q2)g_{s(n)} & \geqslant 2n+3\log_q\frac{3qg_{s(n)}}{(\sqrt{q}-1)^2}+3 \\ &\qquad\text{ - в случае теоремы 8.21, (d)}. \end{aligned}
\end{equation*}
\notag
$$
Цитирование в формате AMSBIB
\RBibitem{BalPieRam21} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|