Одинаковая плотность по всем арифметическим прогрессиям

[fractalon]

Для всякого ли $\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$. Для иррациональных возможно, например?

[DeBill]

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

[fractalon]

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

[DeBill]

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

[fractalon]

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

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

[DeBill]

fractalon в сообщении #1109904 писал(а):

вот интересно, почему работает моя схема

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

-- 28.03.2016, 18:41 --

fractalon в сообщении #1109904 писал(а):

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

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

[fractalon]

Да, работает. Более основательные проценты показывают для модулей до $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$ шагов).