Программирование, 2021, № 1, стр. 65-72

1. ВВЕДЕНИЕ

Гиперповерхностью называется проективное многообразие, определяемое одной формой (однородным многочленом). Кривая на плоскости и поверхность в трехмерном пространстве – это гиперповерхности. Предполагается, что гиперповерхность задана свободной от квадратов формой над полем характеристики нуль, в котором арифметические операции вычислимы за полиномиальное число битовых операций, например, над полем рациональных чисел [1]. Точка называется особой, если все первые частные производные этой формы обращаются в нуль. Поиск особой точки сводится к поиску нетривиального решения системы однородных алгебраических уравнений. В малых размерностях эта задача легко решается посредством символьных вычислений, например, в Maple или MathPartner [2]. Однако в больших размерностях задачи распознавания гладкости и поиска особой точки на кубической гиперповерхности алгоритмически трудные.

Обсуждая вычислительную сложность, мы рассматриваем символьные вычисления, где не происходит ни округления числовых значений, ни приближения мероморфных функций рациональными. Работая над расширением поля рациональных чисел, методы компьютерной алгебры нельзя заменить численными методами. Если не оговорено противное, временем работы алгоритма называется число арифметических операций над полем, операций сравнения и копирования чисел, а также операций над индексами. Более формально, мы рассматриваем вычисления на обобщенных регистровых машинах над некоторым полем [3]. Если каждая арифметическая операция над полем вычислима за полиномиальное число битовых операций, вычислимость за полиномиальное время на обобщенной регистровой машине над этим полем, вообще говоря, не влечет вычислимость за полиномиальное число битовых операций, поскольку запись ответа может иметь экспоненциальную длину. Например, этот эффект возникает при многократном возведении в степень ${{( \ldots {{({{x}^{2}})}^{2}} \ldots )}^{2}}$.

Если в худшем случае задача трудна, то в типичном случае решить ее может быть легче [4]. Поэтому интересны так называемые генерические алгоритмы, когда для почти всех входов – на большой доле входов данной длины – быстро вычисляется правильный ответ, но для небольшой доли входов результатом служит лишь предупреждение о невозможности вычисления [5, 6]. Генерический алгоритм не ошибается в отличие от эвристического алгоритма, который для почти всех входов дает правильный ответ, но для некоторых входов ответ может быть ложным. Алгоритм с односторонней ошибкой может допускать ошибку только одного рода. Тривиальный алгоритм, принимающий все входы, служит примером эвристического алгоритма с односторонней ошибкой для задачи распознавания гладкости кубической гиперповерхности, поскольку общая форма определяет гладкую гиперповерхность. Трудно предложить для этой задачи эвристический алгоритм с односторонней ошибкой другого рода, безошибочно распознающий особые кубические гиперповерхности.

Вероятностные алгоритмы используют в ходе работы случайные биты [4]. Примером служит вероятностное сведение задачи о поиске двоичного решения системы алгебраических уравнений к поиску двоичного решения одного уравнения [7]. Замена случайных битов псевдослучайной последовательностью превращает вероятностный алгоритм в эвристический (но, вообще говоря, не в генерический) алгоритм.

Существует несколько методов поиска особых точек. Поиск решения системы алгебраических уравнений посредством вычисления базиса Гребнера реализован во многих системах компьютерной алгебры, но требует больших затрат времени и памяти [8, 9]. Исследование свойств особой точки вовлекает многогранник Ньютона [10]. Впервые этот многогранник был применен А.Д. Брюно для поиска асимптотики решений систем дифференциальных уравнений [11], а его обобщение – многогранник Адамара – для параметризации [12, 13]. Для общей гиперповерхности с единственной особой точкой, которая служит обыкновенной двойной точкой, координаты этой особой точки выражаются рациональными функциями от коэффициентов некоторой формы, определяющей эту гиперповерхность [14].

Гиперповерхность степени d в ${{\mathbb{P}}^{n}}$ соответствует гиперплоскому сечению многообразия Веронезе. Гиперповерхность особая, если секущая гиперплоскость касается многообразия Веронезе, то есть служит точкой двойственного многообразия. Степень этого двойственного многообразия равна $(n + 1){{(d - 1)}^{n}}$. Это степень дискриминанта формы степени d от n + 1 переменной [15]. Например, дискриминант квадратичной формы пропорционален определителю матрицы Гессе, а его степень равна числу переменных n + 1. Если бинарная форма служит гомогенизацией неоднородного многочлена от одной переменной, то дискриминант формы обращается в нуль, когда этот многочлен имеет кратный корень.

Гладкость плоских кривых может быть проверена специальными методами [16]. Кубическая кривая проективно эквивалентна кривой в форме Вейерштрасса. Ее аффинная часть задана уравнением ${{y}^{2}} = {{x}^{3}} + px + q$. Эта кривая особая, когда дискриминант многочлена в правой части, равный $ - 4{{p}^{3}} - 27{{q}^{2}}$, обращается в нуль. Приведение к форме Вейерштрасса сводится к поиску точки перегиба, которая существует на каждой неприводимой плоской кубической кривой [17]. Алгоритм приведения к форме Вейерштрасса реализован в системе Maple в пакете algcurves [18].

Проверка гладкости или вычисление сингулярного локуса кубической поверхности может применяться для моделирования и визуализации сложных поверхностей [19]. Кубическая поверхность в ${{\mathbb{P}}^{3}}$, заданная над некоторым полем K и содержащая некоторую K-точку, унирациональна над K, то есть некоторое всюду плотное в топологии Зарисского множество K-точек на этой поверхности допускает рациональную параметризацию [20, 21]. Поэтому кубические поверхности удобнее для моделирования, чем поверхности больших степеней [22, 23]. С другой стороны, гладкие вещественные кубические поверхности с двумя компонентами связности унирациональны, но иррациональны над полем вещественных чисел.

2. ПРЕДВАРИТЕЛЬНЫЕ РЕЗУЛЬТАТЫ

Мы предполагаем, что в каждой размерности фиксировано проективное пространство ${{\mathbb{P}}^{n}}$ с однородными координатами $({{x}_{0}}: \cdots :{{x}_{n}})$. Значения однородных координат не обращаются в нуль одновременно, а два набора координат, отличающиеся общим ненулевым множителем, определяют одну и ту же точку в ${{\mathbb{P}}^{n}}$. Свободная от квадратов форма $f({{x}_{0}}, \ldots ,{{x}_{n}})$ определяет гиперповерхность, в точках которой форма f обращается в нуль. Если после некоторой линейной замены координат форма зависит от меньшего числа переменных, то она определяет конус в ${{\mathbb{P}}^{n}}$.

Матрица Гессе многочлена – это симметричная матрица вторых частных производных. Элементами матрицы Гессе многочлена третьей степени служат линейные функции. Определитель матрицы Гессе называется гессианом. Гессиан определяется гиперповерхностью с точностью до ненулевого множителя, что позволяет говорить о гессиане гиперповерхности. След матрицы Гессе называется лапласианом. В системе Maple матрица Гессе, гессиан и лапласиан вычисляются в пакете VectorCalculus. Команды называются Hessian с опцией determinant для вычисления гессиана и Laplacian, соответственно.

Вычислительная сложность определителя матрицы имеет тот же порядок роста, что и для матричного умножения. Известны алгоритмы, асимптотически более эффективные, чем метод Гаусса [24, 25]. Определитель легко вычислить, например, над полем рациональных чисел или полем рациональных функций от одной переменной с рациональными коэффициентами. Но для матриц над кольцом многочленов от многих переменных, вообще говоря, определитель нельзя вычислить за время, ограниченное многочленом от числа переменных. В этом случае для проверки отличия определителя от тождественно нулевого обычно используют лемму Шварца–Зиппеля [26].

Лемма 1 (Шварц–Зиппель). Дан многочлен $f({{x}_{0}}, \ldots ,{{x}_{n}})$ положительной степени $d > 0$ над некоторым полем. Для любого конечного множества S элементов этого поля и для независимых случайных величин ${{\xi }_{0}}$, …, ${{\xi }_{n}}$, равномерно распределенных на множестве S, вероятность обращения многочлена в нуль $f({{\xi }_{0}}, \ldots ,{{\xi }_{n}}) = 0$ не превосходит отношения $\tfrac{d}{{{\text{|}}S{\text{|}}}}$.

Для конуса в ${{\mathbb{P}}^{n}}$ гессиан обращается в нуль, поскольку строки матрицы Гессе линейно зависимы над полем коэффициентов. Однако гессиан может обращаться в нуль и в случаях, когда строки матрицы Гессе линейно зависимы лишь над полем рациональных функций [27]. Как показали в 1876 г. П. Гордан и М. Нётер (P. Gordan, M. Noether), это выполнено для кубической формы ${{x}_{0}}x_{3}^{2} + {{x}_{1}}{{x}_{3}}{{x}_{4}} + {{x}_{2}}x_{4}^{2}$, которая определяет отличную от конуса гиперповерхность в ${{\mathbb{P}}^{4}}$.

Тернарные формы с тождественно нулевым гессианом рассмотрены П.В. Бибиковым [28]. Мы рассмотрим лишь кубические формы, но от многих переменных.

Если гиперповерхность X особая, то множество особых точек на X образует подмногообразие, называемое сингулярным локусом. Мы рассмотрим гиперповерхности, у которых сингулярный локус содержит достаточно большие линейные подпространства.

Обозначим через ${{E}_{0}}$, …, ${{E}_{n}}$ точки в ${{\mathbb{P}}^{n}}$, где однородные координаты точки ${{E}_{k}}$ равны нулю за исключением $k$-й координаты.

Теорема 1. Дана кубическая форма $f({{x}_{0}}, \ldots ,{{x}_{n}})$, которая определяет особую проективную гиперповерхность $X \in {{\mathbb{P}}^{n}}$. Если линейное координатное подпространство, заданное уравнениями ${{x}_{{m + 1}}} = 0$, …, ${{x}_{n}} = 0$, вложено в сингулярный локус на X, то

где ${{q}_{k}}$ – некоторые квадратичные формы, а $c$ – кубическая форма.

Доказательство. Предположим, что форма f содержит моном $x_{k}^{2}{{x}_{j}}$ для индексов $k \leqslant m$ и некоторого j, возможно, равного k. Тогда частная производная $\tfrac{{\partial f}}{{\partial {{x}_{j}}}}$ отлична от нуля в точке E_k, что противоречит условию, что точка ${{E}_{k}}$ особая. Следовательно, для каждого индекса $k \leqslant m$ форма f не содержит мономов $x_{k}^{2}{{x}_{j}}$ и, в частности, мономов $x_{k}^{3}$.

Предположим, что для некоторых индексов, удовлетворяющих условиям $k < \ell \leqslant m$, $j \ne k$ и $j \ne \ell $, форма  f содержит моном ${{x}_{k}}{{x}_{\ell }}{{x}_{j}}$. Тогда частная производная $\frac{{\partial f}}{{\partial {{x}_{j}}}}$ отлична от нуля в точке, где только k-я и $\ell $-я однородные координаты отличны от нуля. Но по условию эта точка особая. Противоречие доказывает, что такого монома нет. □

Существование сингулярного локуса малой размерности не влечет обращение в нуль гессиана. Например, зонтик Уитни, заданный формой ${{x}_{0}}x_{2}^{2} + {{x}_{1}}x_{3}^{2}$, служит примером поверхности, чей сингулярный локус содержит прямую. Эта прямая определяется двумя уравнениями ${{x}_{2}} = 0$ и ${{x}_{3}} = 0$. Но гессиан этой формы равен $16x_{2}^{2}x_{3}^{2}$. Другая форма ${{x}_{0}}x_{3}^{2} + {{x}_{1}}x_{4}^{2} + {{x}_{2}}x_{5}^{2}$ определяет гиперповерхность в ${{\mathbb{P}}^{5}}$, сингулярный локус которой содержит плоскость. Гессиан этой формы равен $ - 64x_{3}^{2}x_{4}^{2}x_{5}^{2}$.

Как обычно [29], для данного множества форм, коэффициенты которых зависят от параметров ${{\xi }_{0}}$, …, ${{\xi }_{m}}$, некоторое свойство $\Phi ({{\xi }_{0}}, \ldots ,{{\xi }_{m}})$ выполнено для почти каждой формы этого множества, если существует такой многочлен $p({{\xi }_{0}}, \ldots ,{{\xi }_{m}})$, не обращающийся в нуль тождественно, что для каждого допустимого набора значений параметров ${{\xi }_{0}}$, …, ${{\xi }_{m}}$ если свойство $\Phi ({{\xi }_{0}}, \ldots ,{{\xi }_{m}})$ не выполнено, то многочлен обращается в нуль $p({{\xi }_{0}}, \ldots ,{{\xi }_{m}}) = 0$. Свойство, которое выполнено для почти каждого набора значений параметров, не выполняется лишь на нигде не плотном множестве меры нуль. Но в общем случае множество наборов значений, на которых свойство $\Phi $ не выполняется, может быть собственным подмножеством множества нулей многочлена p.

Для некоторой матрицы A обозначим через ${{A}^{T}}$ транспонированную матрицу.

Теорема 2. Дано нечетное число $n = 2m + 1$. Для почти каждой кубической формы $f({{x}_{0}}, \ldots ,{{x}_{n}})$, определяющей проективную гиперповерхность в ${{\mathbb{P}}^{n}}$, чей сингулярный локус содержит линейное подпространство, заданное уравнениями ${{x}_{{m + 1}}} = 0$, …, ${{x}_{n}}$ = 0, гессиан формы f – многочлен степени n + 1, который не зависит от переменных ${{x}_{0}}$, …, ${{x}_{m}}$.

Доказательство. Из теоремы 1 следует, что матрица Гессе формы  f – это блочная матрица вида

где A и $B$ – квадратные матрицы порядка m + 1, причем элементами матрицы A служат линейные формы, которые не зависят от переменных ${{x}_{0}}$, …, ${{x}_{m}}$. Гессиан формы f, равный detH, не зависит от блока B, но только от A.

Форма ${{x}_{0}}x_{{m + 1}}^{2} + \cdots + {{x}_{m}}x_{n}^{2}$ удовлетворяет условиям теоремы и ее гессиан равен ${{( - 4)}^{{m + 1}}}x_{{m + 1}}^{2} \cdots x_{n}^{2}$. Согласно теореме 1, все рассматриваемые кубические формы параметризуются наборами коэффициентов квадратичных форм ${{q}_{k}}$ и кубической формы c. Следовательно, существует многочлен p от этих коэффициентов, значение которого равно коэффициенту при мономе $x_{{m + 1}}^{2} \cdots x_{n}^{2}$ гессиана соответствующей формы f. И степень многочлена p положительная. Следовательно, для почти каждой рассматриваемой формы f гессиан содержит моном $x_{{m + 1}}^{2} \cdots x_{n}^{2}$ степени n + 1. Но мономов большей степени в этом гессиане нет. □

Напомним достаточное условие обращения в нуль гессиана кубической формы [27].

Теорема 3 ([27]). Дана кубическая форма $f({{x}_{0}}, \ldots ,{{x}_{n}})$, которая определяет проективную гиперповерхность $X \in {{\mathbb{P}}^{n}}$. Если для некоторого $m\, > \,\tfrac{1}{2}(n\, - \,1)$ линейное подпространство, заданное уравнениями ${{x}_{{m + 1}}} = 0$, …, ${{x}_{n}} = 0$, вложено в сингулярный локус на X, то гессиан формы f тождественно обращается в нуль.

Доказательство. Согласно теореме 1, матрица Гессе формы  f содержит в первых строках и столбцах нулевую подматрицу порядка m + 1. Порядок матрицы Гессе равен n + 1. При условии $m + 1 > \tfrac{1}{2}(n + 1)$ определитель матрицы Гессе тождественно обращается в нуль. □

3. ОСНОВНЫЕ РЕЗУЛЬТАТЫ

Теорема 4. Существует вероятностный алгоритм полиномиального времени, который получает на вход рациональное число $\varepsilon > 0$, целое число $n$ и заданную списком коэффициентов кубическую форму $f({{x}_{0}}, \ldots ,{{x}_{n}})$. Если форма f определяет гиперповерхность в ${{\mathbb{P}}^{n}}$, чей сингулярный локус содержит некоторое линейное подпространство размерности больше $\frac{1}{2}n$, то вход всегда отвергается. Однако для почти каждой кубической формы f вход принимается с вероятностью больше 1 – ε.

Доказательство. На первом шаге вычисляется матрица Гессе формы f. На втором шаге посредством вероятностного алгоритма, основанного на лемме Шварца–Зиппеля [26], проверяется отличие гессиана формы f от тожественно нулевого. Если сингулярный локус гиперповерхности достаточно большой, то в силу теоремы 3 гессиан обращается в нуль при любой оценке переменных. Алгоритм вычисляет значение гессиана на случайно и независимо выбранных из отрезка от нуля до $\left\lceil {(n + 1){\text{/}}\varepsilon } \right\rceil $ целочисленных оценок для переменных ${{x}_{0}}$, …, ${{x}_{n}}$. Если вычисленное значение нулевое, то вход отвергается, иначе вход принимается. □

Замечание. Матрица порядка n + 1, элементами которой служат линейные формы от переменных ${{x}_{0}}$, …, ${{x}_{n}}$, содержит не более ${{(n + 1)}^{3}}$ числовых коэффициентов. Используя симметричность матрицы Гессе, достаточно хранить в памяти меньшее количество чисел. Поэтому алгоритм из теоремы 4 выполняет $O({{n}^{3}})$ операций над полем коэффициентов. Алгоритм основан на вычислении определителя матрицы над этим полем. Если кубическая форма f определена над полем рациональных чисел или над конечным расширением этого поля, этот вероятностный алгоритм имеет полиномиальную битовую сложность.

Теорема 5. Существует вероятностный алгоритм полиномиального времени, который получает на вход рациональное число $\varepsilon > 0$, нечетное целое число $n = 2m + 1$ и заданную списком коэффициентов кубическую форму $f({{x}_{0}}, \ldots ,{{x}_{n}})$. Если форма f определяет гиперповерхность в ${{\mathbb{P}}^{n}}$, чей сингулярный локус содержит некоторое m-мерное линейное подпространство, то вход всегда отвергается. Однако для почти каждой кубической формы f вход принимается с вероятностью больше $1 - \varepsilon $.

Доказательство. Сначала вычисляется матрица Гессе формы  f. Затем посредством вероятностного алгоритма, основанного на лемме Шварца–Зиппеля [26], проверяется линейная независимость градиента гессиана формы  f в случайно выбранных точках.

Пусть ${{\xi }_{0}} = 1$. Алгоритм выбирает случайные оценки ${{\xi }_{1}}$, …, ${{\xi }_{n}}$ для переменных ${{x}_{1}}$, …, ${{x}_{n}}$, которые равномерно и независимо выбираются из набора целых чисел из отрезка от нуля до $\left\lceil {n(n + 1){\text{/}}\varepsilon } \right\rceil $. Поскольку ${{\xi }_{0}} = 1$, это однородные координаты некоторой точки в ${{\mathbb{P}}^{n}}$. Для вычисления в выбранной точке частной производной по переменной ${{x}_{k}}$ сделаем подстановку

и вычислим значение гессиана над полем рациональных функций от одной переменной $y$. Первая частная производная гессиана по переменной ${{x}_{k}}$ равна коэффициенту при линейном члене по переменной y. Так вычисляется градиент в выбранной точке. Все вычисления повторяются для n + 1 независимо от выбранной точки. Вычисления частных производных по разным переменным и в разных точках могут быть выполнены параллельно.

После этого вычисляется определитель матрицы порядка n + 1, составленной из первых частных производных гессиана в n + 1 точке. Если гессиан не зависит от некоторой переменной, то этот определитель обращается в нуль тождественно. Поэтому если он обращается в нуль в ходе вычислений, то вход отвергается, иначе вход принимается.

Гессиан формы f – это многочлен степени не выше n + 1 от переменных ${{x}_{0}}$, …, ${{x}_{n}}$. Первая частная производная гессиана – однородный многочлен степени не выше $n$. Определитель, составленный из таких производных в n + 1 точке, имеет степень не выше $n(n + 1)$. Согласно лемме Шварца–Зиппеля, вероятность обращения в нуль этого многочлена, если он не обращается в нуль тождественно, меньше $\varepsilon $. □

Если ограничиться ортогональными преобразованиями координат, можно использовать не только гессиан, но и лапласиан. Рассмотрим гиперповерхность в ${{\mathbb{P}}^{n}}$, чей сингулярный локус может быть нульмерным, но содержит точки ${{E}_{0}}$, …, ${{E}_{n}}$, где однородные координаты точки ${{E}_{k}}$ равны нулю за исключением $k$-й координаты. Примером служит поверхность Кэли, заданная формой ${{x}_{0}}{{x}_{1}}{{x}_{2}} + {{x}_{0}}{{x}_{1}}{{x}_{3}} + {{x}_{0}}{{x}_{2}}{{x}_{3}} + {{x}_{1}}{{x}_{2}}{{x}_{3}}$.

Теорема 6. Существует алгоритм полиномиального времени, который получает на вход целое число $n$ и заданную списком коэффициентов кубическую форму $f({{x}_{0}}, \ldots ,{{x}_{n}})$. Если форма f определяет особую гиперповерхность в ${{\mathbb{P}}^{n}}$, чей сингулярный локус содержит образ точек ${{E}_{0}}$, …, ${{E}_{n}}$ при некотором ортогональном преобразовании, то вход всегда отвергается. Однако для почти каждой кубической формы f вход принимается.

Доказательство. Лапласиан (след матрицы Гессе) инвариантен относительно ортогональных преобразований координат. Поэтому без ограничения общности можно считать, что форма f определяет гиперповерхность с особыми точками ${{E}_{0}}$, …, ${{E}_{n}}$. Повторяя рассуждения из доказательства теоремы 1, получаем, что форма f мультилинейная, то есть никакая переменная не входит ни во второй ни в третьей степени. Следовательно, лапласиан тождественно обращается в нуль. Напротив, для почти каждой кубической формы лапласиан равен линейной форме.

Алгоритм отвергает вход, если лапласиан обращается в нуль тождественно, иначе принимает вход. □

4. ОБСУЖДЕНИЕ

Рассмотрено проверяемое за полиномиальное время вероятностным алгоритмом достаточное условие отсутствия достаточно большого сингулярного локуса на кубической гиперповерхности. В общем случае это не позволяет судить о гладкости этой гиперповерхности. Более того, поскольку гладкость эквивалентна отличию от нуля дискриминанта – неприводимого многочлена степени $(n + 1){{2}^{n}}$ от коэффициентов кубической формы от n + 1 переменной, это свойство в типичном случае не может быть выражено многочленом меньшей степени. Тогда как степень гессиана такой кубической формы не превышает n + 1. Поэтому рассмотренный метод не позволяет распознавать сингулярные локусы малых размерностей. Также не известен детерминированный алгоритм проверки обращения гессиана в нуль.

В вероятностных алгоритмах из теорем 4 и 5 границы отрезка, из которого выбираются оценки для переменных, можно расширить так, чтобы случайные числа взаимно однозначно соответствовали наборам случайных битов. При этом вероятность ошибки не увеличится.

Алгоритмы из теорем 4–6 легко преобразовать в генерические алгоритмы, которые либо принимают вход, либо выдают предупреждение о невозможности дать точный ответ, но никогда не отвергают вход и не делают ошибок. Действительно, общая гиперповерхность гладкая, а гиперповерхности с особыми точками определяются формами с обращающимся в нуль дискриминантом. С другой стороны, при использовании псевдослучайной последовательности вместо случайных битов долю входов, которые не допускаются, но вызывают сообщение об отказе от вычисления ответа генерическим алгоритмом, можно сделать достаточно низкой, увеличивая длину отрезка, из которого выбираются случайные числа, или посредством повторения теста.

Автор благодарен М. Спиваковскому (Mark Spivakovsky) за обсуждение темы работы, а также С.А. Абрамову и А.Б. Батхину за полезные замечания.