Том 13, серия 1, номер 2, 2006 г., Стр. 38-58

УДК 519.7
В. В. Кочергин
Об асимптотике сложности аддитивных вычислений систем целочисленных линейных форм

Аннотация:
Изучается сложность вычисления систем целочисленных линейных форм. Для системы из $p$ линейных форм от $q$ переменных $x_1,x_2,\dots,x_q$, заданной целочисленной матрицей $A$ размера $p\times q$, обозначим через $l_2(A)$ минимальное число операций сложения и вычитания, достаточное для вычисления по переменным $x_1,x_2,\dots,x_q$ заданной системы линейных форм (при этом разрешается многократное использование промежуточных результатов вычислений). Получена (теорема 1) нижняя оценка этой величины:
$$ l_2(A)\geqslant\log D(A), $$
где $D(A)$ — максимум абсолютных величин миноров матрицы $A$, взятый по всем минорам, начиная с миноров порядка 1 и заканчивая минорами порядка $\min(p,q)$. Кроме того, доказано (теорема 2), что для любой последовательности матриц $A(n)$ размера $p(n)\times q(n)$, удовлетворяющей условию $p+q=o((\log\log D(A))^{1/2})$ при $n\to\infty$, справедлива оценка
$$ l_2(A)\leqslant\log D(A)+o(\log D(A)). $$
Таким образом, для любых фиксированных (и даже слаборастущих) размерах матрицы, задающей систему целочисленных линейных форм, верхняя оценка сложности вычисления этой системы асимптотически совпадает с нижней.
Библ. 8.

Кочергин В. В. ¹
1. МГУ, мех.-мат. факультет, Воробьёвы горы,
119992 Москва, Россия
е-mail: vvkoch@yandex.ru, koch@procenter.net.ru

Статья поступила 19 января 2006 г.