о точках, точности и Гауссе
Dec. 3rd, 2002 08:05 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaВот интересная математическая проблема с очень простым условием, решение которой до сих пор неизвестно.
Возьмём плоскость и нарисуем на ней координатную сетку. Посмотрим на все точки с целочисленными координатами (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, что и требовалось доказать.
Возьмём плоскость и нарисуем на ней координатную сетку. Посмотрим на все точки с целочисленными координатами (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, что и требовалось доказать.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2002-12-03 10:26 am (UTC)То есть мы можем узнать значение функции в любой точке, и проблема в том, что мы не можем найти её аналитическую форму.
Re:
Date: 2002-12-03 10:30 am (UTC)no subject
Date: 2002-12-03 10:37 am (UTC)до сих пор неизвестно, рациональна ли постоянная Эйлера-Машерони.
no subject
Date: 2002-12-03 10:50 am (UTC)Приведенная выше просто подкупает кажущейся простотой: сначала кажется, что задача для учебника пятого класса.
no subject
Date: 2002-12-03 11:25 am (UTC)Re:
Date: 2002-12-03 11:31 am (UTC)no subject
Date: 2002-12-03 11:33 am (UTC)no subject
Date: 2002-12-03 11:48 am (UTC)A iz problemy podscheta sobstvennyh znacehij laplaciana, mne smutno kazhetsja chto t^(1/2) popravka est.
Re:
Date: 2002-12-03 11:50 am (UTC)Поэтому если O(t^1/2) верно, это не значит, что O(t^1/3) не может быть верным.
no subject
Date: 2002-12-03 12:02 pm (UTC)Utverzhdenie bylo ne O(t^1/2) a c*t^1/2 (to est tochanaj ocenka) chto, konechno ne
soglasuetsja s utverzhdeniem chto krome linejnogo chlena vse ostal'noe O(t^1/3).
Za iskljucheniem, kak ukazano, c=0
no subject
Date: 2002-12-03 11:54 am (UTC)no subject
Date: 2002-12-03 11:53 am (UTC)Интересно было вычислить второй терм разложения. Допускаю, что он представляет собой некую осциллирующую функцию. Надо Иваньца спросить, у него наверняка есть идеи.
no subject
Date: 2002-12-03 12:22 pm (UTC)Ne ochevidno, tak kak razumno predpolozhit' poverhnostnyj
clen, sledyjushij posle objemnogo. To chto on sokrazhaetsja -
simmetrija tora.
Formula ja vspominal - O(r^{n-2+2/(n+1)}) v kachestve popravki k
chislu sobstvennyh znachenij na tore, gde r=radius, n-chislo izmerenij.
dlja n=2 r=t^(1/2) eto dajet t^(1/3)
Interesno, chto eta ocenka byla uluchshena !
немножко офф...
Date: 2002-12-04 12:15 am (UTC)Недавно у Вас в журнале обсуждалась формула Пика и ее многомерные аналоги. Существуют довольно забавные штуки про это.
Будем искать даже не количество целых точек в многограннике, а сумму многочлена по целым точкам, лежащим внутри многогранника (если этот многочлен -- константа, то получим количество целых точек). Ясно, что главный член
здесь, как и в задаче Гаусса и проч. это интеграл многочлена по многограннику. Будем считать, что многогранник зависит от многих параметров -- высот hi --
расстояний от какой-то точки до граней многогранника. Пусть всё дело происходит в такой области пораметров, где комбинаторный тип многогранника не меняется, т.е. "выглядит" он так же. Другими словами, меняем высоты
так мало, что перестроек в многограннике не происходит. Тогда интергар многочлена по многограннику -- многочлен (назовём его P) от высот hi. Оказывается,
что количество целых точек, это дифференциальный оператор бесконечного порядка, зато явно выписываемый, от этого многочлена. Впрочем, от многочлена можно и бесконечного порядка посчитать, не страшно.
Оператор строится так. Рассмотрим функцию F(x)=x/(1-exp(-x)).
Она в нуле вполне себе хорошая, даже в ряд раскладывается. Разложим.
Получили ряд F(x)=a0 +a1 x +a2 x2+...
Теперь заменим x на d/dhi для каждого i и перемножим получившиеся операторы. Применим получ. оператор к P. Получим количество целых точек.
Да, конечно, главный член будет -- 1 , второй -- ну, сами знаете, из формулы Пика...
Забавно, что всё это еще и связано с теоремой Римана-Роха-и проч.
Re: немножко офф...