Число целых точек в круге

Vikuschechka9

Дан круг радиуса R на плоскости и в нём есть T целых точек из решётки Z^2. Доказать, что

Для O(R) это ещё более-менее понятно , но с о(R) что делать?

Lika25

ну, например, o(R) = O(r^{2/3})
такую оценку в начале прошлого века кто-то доказал про круг, хотя я слышал, что есть поточнее
как доказывать про o(R) - не знаю

Vikuschechka9

Это у нас Мощевитин на первом семинаре давал в обзоре -- типа уже доказано, что для 1, 2/3, 7/11, 46/73 этот закон верен, а для 1/2 под баааальшим вопросом... Так наскока я понял если найти для 2/3 то задача решена... Тока вот где ж её найти?! Хотя бы как проблема называется?! А то я что-то туплю не по детски.
Мне сказали что есть какая-то книжка (гм, не уверен в первой фамилии) Горшков, Чубариков -- "Алгоритмы. Вычисления. ..." Где-то тут, в "научной библиотеке"... Что-то я не нашёл такого.

Vikuschechka9

Эхх, люди, ну почему я так попадаю вечно с задачами, а?!

Xephon

прочти приват

Vikuschechka9

Снова ап... Может кто знает хоть что-нить...

Lika25

а ты в инете искал?
для облегчения поиска: кажись, это Серпинский доказал, про 2/3
про книгу: сходи в читалку посмотри
почему попал-то с этой задачей?

Vikuschechka9

Ну так получилось... Мне сначала совсем сложную дали (Чубариков а потом я его убедил, что в ней лажа. Он дал похожую
Я посмотрю в читалке и порою в инете, спасибо за советы

Vikuschechka9

Тока в инете чё-то ничё нету пока...

Sanych

ну если ничего другого нету, можешь посмотреть это;

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

Vikuschechka9

Хмммм... Блин, ничо не ясно Если не сложно, лучше начни с плана...

a10036

Слушай, если не сложно напиши поподробнее, а то я тоже так и не понял что там происходит

Vikuschechka9

Копирайт -- Автор: (респект!)
Итак, план решения:
1. Разбиваем весь круг на 4 части кривыми $x=\pm y$
осталось: доказать для каждой части, что площадь отличается от количества точек на $o(R)$.
2. Берём верхнюю часть и доказываем для неё. Площадь такой фигуры приближается с точностью порядка $O(1)$ суммой по целым $x$ от ее настоящей ширины по вертикали. А ширина по вертикали отличается от количества целых точек на дробную часть.
осталось: показать, что средняя дробная часть отличается от 1/2 на o(1)
3. Делим фигуру на полосы ширины $\sqrt[3]{R}$ и доказываем оценку $o(\sqrt[3]{R})$ почти в каждой полосе, остальных мало и поэтому в них нам достаточно $O(\sqrt[3]{R})$.
3.1 Для такой полосы значения дробных частей можно приблизить значениями дробных частей линейной функции
3.2 Для линейной функции $y=a+kx$ на отрезке длины $\sqrt[3]{R}$ погрешность бывает более $\eps\sqrt[3]{R}$ только при вполне определённых коэффициэнтах $k$. А именно, они должны быть близки к рациональному числу с маленьким знаменателем.
3.3 Показываем, что таких $k$ у нас действительно мало. [Для этого рассматриваем производную, и используем, что вторая производная меняется на рассматриваемом промежутке несильно.]
План формализации:
Лемма: если сумма $\sum_{x=1}^m \{a+kx\}$ отличается от $m/2$ более, чем на $m\eps$, то $\exists p,q\le c/\eps: |k-p/q|<\frac{c}{m\eps}$
Следствие: $\forall\eps\exists N \forall R>N$ в сумме по полосам лишь число слагаемых, ограниченное $\eps \sqrt[3]{R^2}/2$ могут не удовлетворять оценке $\sqrt[3]{R}\eps/2$.
(Но они всё равно удовлетворяют оценке $\sqrt[3]{R}$ )
Таким образом, для каждого из типов слагаемых получаем ошибку вида $\eps R/2$, для произвольного $\eps$.
Таким образом, $W=\sum_{x=-[R\sqrt{0.5}]}^{[R\sqrt{0.5}]}\{ \sqrt{R^2-x^2} \}=L/2+o(R)$, где $L=R\sqrt{2}$ -- ширина фигуры.
Утверждение: площадь фигуры отличается от суммы по целым $x$ её вертикальных ширин на $o(R)$
Утверждение: сумма вертикальных ширин отличается от количества точек внутри и на границе на $W - L+o(R)$
Утверждение: во всём круге целых точек $4(S-(W-L+o(R) -2L$
схема
(12)
Во второй задаче можно рассмотреть криволинейный треугольник y>x,y>-x,x^2+y^2<R^2 и далее сравнивать площадь с количеством точек. При этом удобно сначала приблизить площадь по формуле трапеций, тогда остаётся только показать малость суммы дробных частей сдвинутых на 1/2: $\sum_{x=0}^{[R\sqrt{0.5}]}\{ \sqrt{R^2-x^2} \}-0.5= o(R)$.
(примечание -- сдвиг на 0,5 возникает, потому что точки нижней границы мы должны считать по 1/2 раза в каждом из 4 наших треугольников)
(3)
Нам надо откуда-то брать равномерную распределённость. Вроде можно сделать так: сгруппировать участки длиной \sqrt[3]{R},
(3.1)
потом на каждом заменить границу линейной, что на дробные части влияет как o(1) и потом заметить, что из всех блоков плохое направление (т.е. допускающее ошибку более фиксированного \eps в дробных частях) бывает только в o(1) блоках.
(3.2)
Действительно, есть у нас линейная с коэффициэнтом k функция. И пусть так вышло, что сумма \sum_{n=0}^{m-1}{c+kn} не является m\eps - близкой к m/2.
Тогда хотим показать, что есть {kn}, очень близкая к 0 для n от 1 до 4/eps. Действительно, там есть {kn}\le \eps/4 либо {kn}>1-\eps/4
Тогда так как она на каждом своём "периоде" даёт среднюю ошибку не более 2\eps/3, значит непериодическая часть даёт вклад не менее \eps/3.
Но тогда длина непериодической части не менее m\eps/3;
а значит и длина периода T \ge m\eps/3; но длина периода есть 1/\delta.
В общем, \delta порядка O(\eps/m). И хотя возможных n есть 4/\eps, а соответственно чисел от которых мы отходим на \delta есть O(\eps^{-2}) -- тем не менее \eps фиксировано, а m стремится к бесконечности. Значит получаем, что доля плохих не просто мала, но все они сосредоточены в малых интервалах вокруг фиксированного числа точек.(3.3) И можно убедиться, что в такие интервалы не попадает слишком много наших k, которые задают линейную функцию. (Фактически, k меняется от 0 до 1 с шагом порядка $1/m^2$)
Оставить комментарий
Имя или ник:
Комментарий: