2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Одинаковая плотность по всем арифметическим прогрессиям
Сообщение27.03.2016, 19:21 


08/09/13
210
Для всякого ли $\delta \in (0;1)$ можно построить множество натуральных чисел, плотность которого по любой бесконечной арифметической прогрессии была бы $\delta$? Иными словами, такое множество $A$, чтобы для всяких $0 \le a < m$ множество $\left\lbrace{s\ :\ ms+a \in A}\right\rbrace$ имело плотность $\delta$.

Вопрос показался интересным потому что если представить счётное количество испытаний Бернулли с вероятностью $\delta$ на принадлежность каждого числа множеству, то по каждой отдельной прогрессии требуемое, ясное дело, будет с вероятностью $1$. А вот по всем? Кажется, должно быть возможным, но как построить общую конструкцию?

Про $\delta = \frac{1}{2}$ (рассмотрел сразу как самый простой случай) возникла гипотеза, что условию будет удовлетворять множество чисел с чётным количеством единиц в двоичной записи. Простейшие эксперименты это подтверждают, да и придумалась эта конструкция в процессе попыток построения по типу "сделаем чтоб сначала для одного модуля работало, потом для следующего и т. д.". Идея была такая, что берём $0$, потом $01$, потом $0110$ и так каждый раз прибавляем инвертированную строку, и получаем последовательность индикаторов принадлежности множеству. Как бы доказать, что это работает?

Ну, и общий случай для всех $\delta$. Для иррациональных возможно, например?

 Профиль  
                  
 
 Re: Одинаковая плотность по всем арифметическим прогрессиям
Сообщение28.03.2016, 16:18 
Заслуженный участник


10/01/16
2315
Для рационального $\delta = \frac{3}{q}$ : в $q$-ичной системе счисления, отметим те числа, для которых сумма цифр по модулю $q$ равна 1,2 или 3. Если Ваша конструкция для половинки работает, то и тут должно быть...
А можно попробовать так: запустим по единичной окружности человечка с шагом $\sqrt{2}$, на окружности отметим дырку длины $\delta$. Если на шаге $n$ человечек попал в дырку - это $n$ пометим. Вроде бы, из теоремы о совпадении временного и пространственного средних, должно получиться....

 Профиль  
                  
 
 Re: Одинаковая плотность по всем арифметическим прогрессиям
Сообщение28.03.2016, 17:02 


08/09/13
210
Не слышал о такой теореме. Прогуглил - что-то из эргодической теории. В этой области я почти ноль. Что посоветуете почитать для введения и конкретно об этой теореме? Доказательство сложное?

 Профиль  
                  
 
 Re: Одинаковая плотность по всем арифметическим прогрессиям
Сообщение28.03.2016, 17:26 
Заслуженный участник


10/01/16
2315
Ну, есть книжка Каток, Хассельблат, Введение в теорию динамических систем: глава 4, п. 4.1.4, предложение 4.1.7 говорит: если мы стартуем из точки $x$ окружности, и за $n$ шагов посчитаем, какова доля попаданий на данный интервал, то предел этих доль (равномерно по $x$) равен длине интервала. Вот только теперь это надо подработать для Вашей прогрессии - и, вроде, должно получиться...

 Профиль  
                  
 
 Re: Одинаковая плотность по всем арифметическим прогрессиям
Сообщение28.03.2016, 17:34 


08/09/13
210
А, ну это, по сути, утверждение о том, что $\left\lbrace{n \xi : n \in {\mathbb N}}\right\rbrace$ равномерно распределено на $(0;1)$ для иррациональных $\xi$. Как это я забыл...
Да, работает, для прогрессий с разностью $m$ нужно брать $m \xi$ и сдвигать соответствующе требуемый интервал... Вопрос с равномерностью таким образом решается.

Теперь вот интересно, почему работает моя схема с количеством единиц в двоичной записи. И ваше обобщение (тоже о таком думал).

 Профиль  
                  
 
 Re: Одинаковая плотность по всем арифметическим прогрессиям
Сообщение28.03.2016, 17:40 
Заслуженный участник


10/01/16
2315
fractalon в сообщении #1109904 писал(а):
вот интересно, почему работает моя схема

Вот точно! Я тоже поначалу подумал, что не должно. Но, вроде, работает? Странно, да?

-- 28.03.2016, 18:41 --

fractalon в сообщении #1109904 писал(а):
А, ну это, по сути, утверждение о том, что $\left\lbrace{n \xi : n \in {\mathbb N}}\right\rbrace$ равномерно распределено

Ну да, в точности.

 Профиль  
                  
 
 Re: Одинаковая плотность по всем арифметическим прогрессиям
Сообщение29.03.2016, 01:20 


08/09/13
210
Да, работает. Более основательные проценты показывают для модулей до $10^4$ равномерность с погрешностью $10^{-63}$ уже на первых $2^{1000}$ чисел.
Я руководствовался рекуррентным выражением
$M^{(m)}_{a} (2^{k}) = M^{(m)}_{a} (2^{k-1}) + \lfloor{\frac{2^{k-1}-1-((a-2^{k-1}) \mod m)}{m}}\rfloor + 1 - M^{(m)}_{(a-2^{k-1}) \mod m} (2^{k-1})$,
где $M^{(m)}_{a} (2^k)$ - количество $n$ из нашего множества таких, что $n<2^k$ и $n \equiv a \pmod m$
$\lfloor{\frac{2^{k-1}-1-((a-2^{k-1}) \mod m)}{m}}\rfloor + 1$ - это как бы количество чисел $n$ вне нашего множества таких, что $n<2^{k-1}$ и $n \equiv a-2^{k-1} \pmod m$.

Это выражение само по себе объясняет некоторую равномерность. При переходе к следующей степени массив встречаний по каждому вычету просто сдвигается. Только прибавляются к ним разные величины, хотя и отличающиеся не больше чем на $1$. Это должно быть возможно привести к формальному доказательству - ведь единица становится всё менее и менее значимой... Хотя с другой стороны, тем непоправимее становится имеющаяся разница (в зависимости от делимости на степени $2$, конечно, потому что если вообще нечётное, то у $2^k$ будет полный цикл по модулю и всё устаканится легко общей суммой через $m$ шагов).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group