Равномерное распределениt xor-а единичных битов в посл-ти

[fractalon]

Здравствуйте, уважаемые форумчане! Я уже косвенно поднимал однажды этот вопрос в какой-то теме, но он там не получил обсуждения, и, кроме того, мне пришло на ум обобщение, и результаты первых просчётов на компьютере просто пугающи (постановка задачи не столь сложна чтобы я мог несколько раз допустить ошибку в написании программы и не заметить её при многих перепроверках).
Небогатая любительская интуиция наводит меня на мысль, что если теорема оказывается доступной для чрезмерных обобщений, то её доказательство кроется в чём-то достаточно общем, и должно быть просто. А я такого доказательства найти не могу, поэтому обращаюсь к вам.
Мне не знакомы даже по наслышке какие-то математические техники, которые можно здесь применить, поэтому мой интерес к проблеме обсуловлен результатами просчёта на компьютере для первого миллиона чисел, а для сложных функций типа $x^x$ - для первых 500-700 (понимаю, что это смешно, но погрешность, которую дают даже эти первые числа потрясающе мала)

Это было вступление.
Теперь математика.

Итак, рассмотрим арифметическую функцию $f$ такую, что $f(n)=0$ если количество единиц в двоичной записи $n$ чётно и $f(n)=1$ в ином случае. Формально говоря, $f(\sum \limits_{k=0}^{n} {a_k 2^k}) = \left({ \sum \limits_{k=0}^{n} {a_k}}\right) \mod 2$ для $a_i \in \left\{ {0, 1} \right\}$. Это xor всех единичных битов $n$. Вся эта тема об этой функции, а точнее, о последовательности $f(0), f(1), \dots, f(n), \dots$ и её подпоследовательностях, о плотностях распределения единиц в них.
Легко видеть, что в самой последовательности $f(0), f(1), \dots, f(n), \dots$ нулей и единиц асимптотически (да и вообще на префиксах длины $2^k$) поровну.

Первый вопрос, который меня заинтересовал - равномерно ли (асимптотически, конечно) распределены единицы в последовательности $\left( {f(a+qn)} \right)_{n=1}^{\infty}$ для произвольных $a,q$. То есть плотность единиц в ней стремится ли к $\frac{1}{2}$? Эксперименты на первом миллионе чисел для самых разных $q$ - простых, составных, маленьких больших - наводят на мысль, что да. В первом миллионе плотность отличается от $\frac{1}{2}$ на сотые доли, а то и на тысячные.

Дальше - больше. Взбрело мне в голову проверить плотность единиц в $\left( {f(n^2)} \right)_{n=1}^{\infty}$. То же самое. И для $\left( {f(n^3)} \right)_{n=1}^{\infty}$. И вообще, какие полиномы $p$ (с целочисленными коэффициентами, конечно, и не всегда отрицательными (ну, я делал отрицательные коэффициенты меньших степений по абсолютной величине меньше чем положительные коэффициенты больших степеней, чтоб отрицательного результата не получалось)), так вот, какие полиномы $p$ я ни подставлял, всегда доля единиц в первом миллионе элементов последовательности $\left( {f(p(n))} \right)_{n=1}^{\infty}$ поразительно мало отличается от $\frac{1}{2}$. И даже для $p(n)=C_n^k$ при $k=1,\dots,10$ (для больших $k$ не проверял)

И тут я проверил плотность единиц в $\left( {f(n^n)} \right)_{n=1}^{\infty}$. И тут-то я точно решил написать на форум, потому что результат был сами понимаете какой (буквально: тот же самый, отличие от $\frac{1}{2}$ на тысячные доли). Вот тут как раз проверялись не миллион, а первые 700 элементов (ну, большие степени напряжно на домашнем компьютере считать).
А потом пошло-поехало - для произвольных $a$ и $b$ в последовательностях $\left( {f({(n+a)}^{(n+b)})} \right)_{n=1}^{\infty}$ то же самое.
Пробовал подставлять разные полиномы $p$ второй и третьей степени в $\left( {f(p(n)^n)} \right)_{n=1}^{\infty}$, но это уже маразм - там тоже всё колеблется где-то в окрестности $\frac{1}{2}$, но не понять (по первой тысяче элементов-то...), стремится ли к чему-то. Для примера, среди первых $1100$ элементов $\left( {f((2 n^2 + 7 n - 3)^{(n+9)})} \right)_{n=1}^{\infty}$ доля единиц составляет $0.52545$ (то есть отличие от половины только на $30$ элементов).
Но сэр знает толк в извращениях, поэтому представитель конструкции $a x^x + p(x)$ тоже был проверен. Результат примерно тот же самый. Конкретнее, для первой $1000$ элементов последовательности $\left( {f(5 n^n + 10 n^6 - 3 n^3 + 2 n^2 - 5)} \right)_{n=1}^{\infty}$ доля единиц составляет $0.516$ (да, отклонения именно в большую сторону от $\frac{1}{2}$ для таких извращённых конструкций довольно характерны, что наводит всё-таки на сомнения).

В общем, не понимаю, то ли тайна великая мне открылась, то ли в трёх соснах карты вселенной выискиваю. Когда речь шла об арифметических прогрессиях, думал, что тут модульная арифметика так или иначе шалит, но $n^n$ и собратья там в закономерностях, кажется, замечены не были.

-- 29.03.2017, 01:17 --

И кортежи типа $(f(n),f(n^2),f(n^3))$ тоже равномерно практически распределены по всем значениям...

[slavav]

Вы заново открыли Последовательность Морса — Туэ.

[fractalon]

Я же не о последовательности, а о подпоследовательностях...

[slavav]

Я думаю, что статистические свойства полиномиальных подпоследовательностей Морса-Туе хорошо изучены. Думаю, что можно доказать что предел всегда $\frac{1}{2}$.
Что касается степенных функций, тут сложнее. Первое что приходит в голову $2^n$.

-- 29.03.2017, 18:41 --

Тут есть похожие результаты: Thue–Morse along two polynomial subsequences

[Nik_Nikols]

slavav в сообщении #1204684 писал(а):

Я думаю, что статистические свойства полиномиальных подпоследовательностей Морса-Туе хорошо изучены.

Ну, не так чтобы очень:-) Интерес к этой последовательности (и всяким похожим) регулярно возобновляется, и время от времени появляются новые результаты. Рекомендую хорошего специалиста: http://www.mathnet.ru/rus/person17650
Вероятно, он сможет поддержать наиболее содержательную беседу по этому вопросу (если захочет).

[fractalon]

В работе на два поста выше указана интересная формула для погрешности распределения $t(3n)$. А для других множителей, кроме тройки, не указана.
Может быть, я что-то пропустил или не дочитал, но на всякий случай оставлю здесь гипотезу, полученную, опять же, экспериментально (для десятка небольших чисел), но очень явно напрашивающуюся (эксперименты были для первых примерно $2^{64}$ чисел, а где-то и для $2^{1024}$ через рекуррентные последовательности и возведение матриц в степень, то есть для $n$ вида $2^{2^s}$).
Итак, пусть $N_k^{(i)} (n)$ - количество целых $x < n$ таких, что $t(kx)=i$. Тогда $N_k^{(i)} (n) = \frac{n}{2} + \Theta( {n^{c_p}} )$, где $p$ - наименьший простой делитель $k$ и $c_p=\frac{\log{p}}{(p-1) \log{2}}$