Приближение квадратичных алгебраических решёток и сеток целочисленными решётками и рациональными сетками

Abstract

Данная работа посвящена вопросам приближения квадратичных алгебраических решёток и сеток целочисленными решётками и рациональными сетками.

Даётся общая постановка вопроса о приближении алгебраических решёток и соответствующих сеток целочисленными решётками и рациональными сетками.

В случае простого $p$ вида $p=4k+3$ или $p=2$ рассматривается целочисленная решётка, заданная $m$-й подходящей дробью к числу $\sqrt{p}$. В явном виде выписана соответствующая алгебраическая решётка и обобщённая параллелепипедальная сетка.

Для определения качества соответствующей обобщённой параллелепипедальной сетки определена функция качества, которая для своего вычисления требует $O(N)$ арифметических операций, где $N$ --- количество точек сетки. Центральным результатом является алгоритм вычисления функции качества за $O\left(\sqrt{N}\right)$ арифметических операций.

Сформулирована гипотеза о существовании алгоритма, требующего $O\left(\ln{N}\right)$ арифметических операций. Намечен подход для вычисления сумм с целыми частями линейных функций.