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



Проблема круга Гаусса — задача определения количества точек целочисленной решётки, попадающих в круг радиуса r с центром в начале координат. Первый успех в решении этой задачи был сделан Гауссом, в честь него и названа проблема.

Проблема

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

m 2 + n 2 ⩽ r 2 . {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 задается формулой πr2, то следовало бы ожидать, что число точек будет около πr2. На самом деле значение слегка больше этой величины на некоторую поправку E(r)

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

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

Гаусс показал, что

E ( r ) ⩽ 2 2 π r . {displaystyle E(r)leqslant 2{sqrt {2}}pi r.}

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

E ( r ) ≠ o ( r 1 / 2 ( log ⁡ r ) 1 / 4 ) , {displaystyle E(r) eq oleft(r^{1/2}(log r)^{1/4} ight),}

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

E ( r ) = O ( r 1 / 2 + ε ) . {displaystyle E(r)=Oleft(r^{1/2+varepsilon } ight).}

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

1 2 < t ⩽ 131 208 = 0,629 8 … , {displaystyle {frac {1}{2}}<tleqslant {frac {131}{208}}=0{,}6298ldots ,}

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

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

Точное представление

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

N ( r ) = 1 + 4 ∑ i = 0 ∞ ( ⌊ r 2 4 i + 1 ⌋ − ⌊ r 2 4 i + 3 ⌋ ) . {displaystyle N(r)=1+4sum _{i=0}^{infty }left(leftlfloor {frac {r^{2}}{4i+1}} ight floor -leftlfloor {frac {r^{2}}{4i+3}} ight floor ight).}

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

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

Обобщения

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

Проблема круга для взаимно простых чисел

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

m 2 + n 2 ⩽ r 2 . {displaystyle m^{2}+n^{2}leqslant r^{2}.}

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

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

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

V ( r ) = 6 π r 2 + O ( r 1 + ε ) . {displaystyle V(r)={ frac {6}{pi }}r^{2}+O(r^{1+varepsilon }).}

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

V ( r ) = 6 π r 2 + O ( r exp ⁡ ( − c ( log ⁡ r ) 3 / 5 ( log ⁡ log ⁡ r 2 ) − 1 / 5 ) ) {displaystyle V(r)={ frac {6}{pi }}r^{2}+O(rexp(-c(log r)^{3/5}(log log r^{2})^{-1/5}))}

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

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