Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

о точках, точности и Гауссе

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

Возьмём плоскость и нарисуем на ней координатную сетку. Посмотрим на все точки с целочисленными координатами (a,b), так что сумма квадратов координат меньше или равна заданному фиксированному числу: a2+b2 <= t.

Сколько есть таких точек?

Вспомним, что множество всех точек на плоскости (не только с целочисленными координатами), удовлетворяющих этому условию - это как раз круг с центром в точке (0,0) и радиусом, равным sqrt(t) (квадратному корню из t). Нам нужно найти количество "целочисленных" точек, лежащих внутри этого круга (или на окружности). Площадь этого круга равна числу пи умножить на квадрат радиуса, т.е. в данном случае pi*t. Но каждой точке с целочисленными координатами мы можем поставить в соответствие квадратик сетки размером 1x1 - тот, в котором эта точка является южно-западной вершиной (например). Тогда количество наших точек будет равно суммарной площади этих квадратиков (ведь площадь каждого квадратика - 1), которые почти точно покрывают этот самый круг.

(ниже есть иллюстрация, к-я это прояснит лучше, если непонятно)

Таким образом, что примерно количество наших точек должно быть равно pi*t - площади круга. Примерно потому, что для точек, лежащих совсем рядом с окружностью или прямо на ней, их квадратики не полностью лежат внутри круга и могут выходить за него; и наоборот, некоторая часть площади круга попадает в квадратики, принадлежащие точкам вне круга (но близко к нему).

Вопрос состоит в том, чтобы уточнить это "примерно". По мере роста t, насколько растёт расхождение между pi*t и настоящим количеством точек?


Вот картинка, которая иллюстрирует проблему. Она немножко убогая, но это потому, что я в принципе не умею общаться с графическими редакторами.



В левой части красным отмечены точки, как раз попадающие внутрь круга и удовлетворяющие условию. В правой верхней части показано, как каждой точке ставится в соответствие квадратик размером 1x1 и продемонстрировано, что около границы не все квадратики попадают внутрь круга; за счёт таких квадратиков кол-во точек "увеличивается" по сравнению с площадью круга. В правой нижней части показано, как, наоборот, точка, к-ю мы не считаем, "крадёт" часть площади круга; за счёт таких квадратиков кол-во точек "уменьшается" по сравнению с площадью круга. В результате мы знаем, что кол-во точек примерно равно площади круга, но не знаем размер "погрешности".

Первым эту задачу сформулировал Гаусс в 19-м веке. Он же показал, что размер погрешности не более, чем пропорционален t1/2 (т.е. sqrt(t) - квадратному корню от t). Это доказательство очень простое и приводится ниже. Но доказательство Гаусса не означает, что невозможно найти ещё меньший предел для погрешности. В начале 20-го века было доказано, что погрешность можно оценить как O(t1/3) (что означает, несколько упрощая, что она не более чем пропорциональна кубическому корню от t). Потом в течение 20-го века разные математики всё более и более уменьшали степень α в оценке погрешности O(tα). Например, это было доказано для таких α как 37/112, 12/37 и 7/22+ε (где ε - сколь угодно малое число больше 0). А в данный момент наилучший известный результат - это α=23/73+ε . При этом ещё в 1915-м году Харди доказал, что α обязано быть больше 1/4.

Эксперты в этой области считают, что точная оценка погрешности - O(t1/4+ε), но никто пока не может этого доказать. Задача остаётся нерешённой до конца.

А вот простое доказательство для α=1/2, т.е. того, что размер погрешности можно ограничить функцией, пропорциональной квадратному корню от t.

Обозначим искомое число целочисленных точек R(t). Разделим все интересующие нас целочисленные точки на три группы. "Нормальными" назовём те, чьи квадратики полностью находятся в нашем круге с радиусом t1/2. "Хорошими" назовём те, которые сами находятся внутри круга или на окружности, но их квадратики не находятся целиком внутри круга, а частично из него вылезают (пример в правом верхнем квадранте рисунка). "Плохие" - это те, которе сами находятся вне круга, а их квадратики частично в него входят (пример в правом нижнем квадранте рисунка). Число, которое мы ищем - R(t) - есть сумма количества "нормальных" точек и кол-ва "хороших" точек, или, иными словами, сумма площадей их квадратиков.

Пусть A - хорошая точка. Тогда расстояние от O (центра координат) до A меньше или равно t1/2, т.к. A попадает в круг этого радиуса. При этом расстояние от A до любой точки внутри её квадратика не больше, чем 21/2, квадратный корень из 2 (самое большое расстояние в квадрате такого размера - его диагональ). Значит, расстояние от O до любой точки C внутри квадратика A не больше, чем t1/2+21/2 (по неравенству треугольника OC <= OA + AC). Но из этого следует, что все квадратики "хороших" точек вроде A полностью находятся внутри круга с радиусом (t1/2+21/2), с радиусом ровно на 21/2 большим, чем первоначальный круг. Квадратики "нормальных" точек тем более остаются внутри этого круга. Значит, общая площадь квадратиков "хороших" и "нормальных" точек - равная интересующему нас числу R(t) - меньше площади этого круга, равной произведению пи и квадрата радиуса, т.е. pi*(t1/2+21/2)2. Это верхний предел.

Теперь посмотрим на "плохую" точку B. Она находится вне круга, но её квадратик "заходит" частично в круг. Предположим, что какая-то из точек этого квадратика, скажем, C, находится на расстоянии (t1/2-21/2) или меньше от O, т.е. входит в круг радиусом (t1/2-21/2). Но тогда, учитывая тот факт, что расстояние от C до B не больше, чем 21/2 (см. выше), мы получили бы, опять по неравенству треугольника, что расстояние от O до B меньше t1/2, и точка B попадала бы в первоначальный круг и не была бы "плохой". Значит, ни один "плохой" квадратик не входит даже одной точкой в круг радиусом (t1/2-21/2). Но это значит, что площадь этого круга полностью состоит из "хороших" и "нормальных" квадратиков, и поэтому сумма площадей этих квадратиков, равная R(t), больше или равна площади этого маленького круга, т.е. pi*(t1/2-21/2)2. Это нижний предел.

Мы получили два неравенства:

1) R(t) <= pi*(t1/2+21/2)2
2) R(t) >= pi*(t1/2-21/2)2

Раскрывая скобки и переводя pi*t влево, получаем:

R(t) - pi*t <= 2*pi*(1 + (2t)1/2)
R(t) - pi*t >= 2*pi*(1 - (2t)1/2)

Абсолютное величина (модуль) (1 + (2t)1/2) больше, чем абсолютная величина (1 - (2t)1/2), поэтому мы можем ограничить абсолютную величину погрешности так:

| R(t) - pi*t | <= 2*pi(1 + (2t)1/2)

т.е. погрешность не более чем пропорциональна t1/2, что и требовалось доказать.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 15 comments