Проблема круга Гаусса

В круге в ${\displaystyle \mathbb {R} ^{2}}$с центром в начале координат радиусом ${\displaystyle r\geqslant 0}$ необходимо определить количество точек внутри круга, имеющих вид (m,n), где m и n — целые числа. Поскольку в декартовых координатах уравнение круга задаётся формулой: x² + y² = r², эквивалентной формулировкой задачи станет вопрос: какое количество пар целых чисел m и n удовлетворяет неравенству

${\displaystyle m^{2}+n^{2}\leqslant r^{2}.}$

Если для заданного r обозначить искомое значение через N(r), то следующий список даёт значения N(r) для значений целого радиуса r между 0 и 10:

1, 5, 13, 29, 49, 81, 113, 149, 197, 253, 317 (последовательность A000328 в OEIS).

Поскольку площадь круга радиуса r задаётся формулой πr², то следовало бы ожидать, что число точек будет около πr². На самом деле значение слегка больше этой величины на некоторую поправку E(r)

${\displaystyle N(r)=\pi r^{2}+E(r)}$

Поиск верхней границы этой поправки и составляет суть проблемы.

Гаусс показал^[1], что

${\displaystyle E(r)\leqslant 2{\sqrt {2}}\pi r.}$

Харди^[2] и, независимо, Эдмунд Ландау нашли меньшее значение границы, показав, что

${\displaystyle E(r)\neq o\left(r^{1/2}(\log r)^{1/4}\right),}$

в нотации o-малое. Существует гипотеза^[3], что истинное значение равно

${\displaystyle E(r)=O\left(r^{1/2+\varepsilon }\right).}$

Если переписать последнее выражение в виде ${\displaystyle \|E(r)\|\leqslant Cr^{t}}$, то текущие границы числа t равны

${\displaystyle {\frac {1}{2}}<t\leqslant {\frac {131}{208}}=0{,}6298\ldots ,}$

где нижняя граница выведена Харди и Ландау в 1915 году, а верхняя доказана Мартином Хаксли (Martin Huxley) в 2000 году^[4].

В 2007 году Силвейн Кэппелл (Sylvain Cappell) и Юлиус Шейнисон (Julius Shaneson) выложили в arXiv статью, содержащую доказательство границы ${\displaystyle O(r^{{\frac {1}{2}}+\epsilon })}$^[5].

Значение N(r) можно представить как сумму некоторых последовательностей. Если использовать функцию округления вниз, то значение может быть выражено как^[6]

${\displaystyle N(r)=1+4\sum _{i=0}^{\infty }\left(\left\lfloor {\frac {r^{2}}{4i+1}}\right\rfloor -\left\lfloor {\frac {r^{2}}{4i+3}}\right\rfloor \right).}$

Много проще выглядит представление с использованием функции r₂(n), которая определяется как количество способов представить число n в виде суммы двух квадратов. В этом случае^[1]

${\displaystyle N(r)=\sum _{n=0}^{r^{2}}r_{2}(n).}$

Хотя начальная формулировка задачи говорила о целочисленных решётках в круге, нет причин останавливаться только на круге. Можно ставить задачу нахождения числа точек решётки в других фигурах или конусах. «Проблема делителей» Дирихле эквивалентна данной задаче при замене круга гиперболой^[3]. Можно также распространить задачу на большие размерности, и говорить о числе точек внутри n-мерной сферы или другого объекта. Можно отказаться от геометрического представления проблемы и перейти к диофантовым неравенствам.

Другим обобщением может служить вычисление количества взаимно простых целых решений m и n уравнения

${\displaystyle m^{2}+n^{2}\leqslant r^{2}.}$

Эта задача известна как проблема круга для взаимно простых чисел или проблема круга для примитивных чисел^[7] Если обозначить число таких решений через V(r), то V(r) для малых целых значений радиуса r равны

0, 4, 8, 16, 32, 48, 72, 88, 120, 152, 192, … последовательность A175341 в OEIS.

Используя те же самые идеи, что и для обычной проблемы Гаусса, и исходя из факта, что вероятность взаимной простоты двух чисел равна 6/π², относительно легко показать, что

${\displaystyle V(r)={\tfrac {6}{\pi }}r^{2}+O(r^{1+\varepsilon }).}$

Как и в обычной постановке, задача для взаимно простых чисел заключается в уменьшении показателя экспоненты в поправке. На настоящее время лучшим известным показателем является ${\displaystyle {\tfrac {221}{304}}+\epsilon }$, если принять гипотезу Римана^[7]. Без принятия гипотезы Римана наилучшей верхней границей является

${\displaystyle V(r)={\tfrac {6}{\pi }}r^{2}+O(r\exp(-c(\log r)^{3/5}(\log \log r^{2})^{-1/5}))}$

для некоторой положительной постоянной c^[7].

В частности, неизвестны границы поправки вида ${\displaystyle 1-\epsilon }$ для любого ${\displaystyle \epsilon >0}$, если не принимать гипотезу Римана.