2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Равномерное распределениt xor-а единичных битов в посл-ти
Сообщение29.03.2017, 01:38 


08/09/13
210
Здравствуйте, уважаемые форумчане! Я уже косвенно поднимал однажды этот вопрос в какой-то теме, но он там не получил обсуждения, и, кроме того, мне пришло на ум обобщение, и результаты первых просчётов на компьютере просто пугающи (постановка задачи не столь сложна чтобы я мог несколько раз допустить ошибку в написании программы и не заметить её при многих перепроверках).
Небогатая любительская интуиция наводит меня на мысль, что если теорема оказывается доступной для чрезмерных обобщений, то её доказательство кроется в чём-то достаточно общем, и должно быть просто. А я такого доказательства найти не могу, поэтому обращаюсь к вам.
Мне не знакомы даже по наслышке какие-то математические техники, которые можно здесь применить, поэтому мой интерес к проблеме обсуловлен результатами просчёта на компьютере для первого миллиона чисел, а для сложных функций типа $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))$ тоже равномерно практически распределены по всем значениям...

 Профиль  
                  
 
 Re: Равномерное распределениt xor-а единичных битов в посл-ти
Сообщение29.03.2017, 17:42 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Равномерное распределениt xor-а единичных битов в посл-ти
Сообщение29.03.2017, 17:57 


08/09/13
210
Я же не о последовательности, а о подпоследовательностях...

 Профиль  
                  
 
 Re: Равномерное распределениt xor-а единичных битов в посл-ти
Сообщение29.03.2017, 18:17 
Заслуженный участник


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

-- 29.03.2017, 18:41 --

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

 Профиль  
                  
 
 Re: Равномерное распределениt xor-а единичных битов в посл-ти
Сообщение29.03.2017, 22:23 


14/11/08
73
Москва
slavav в сообщении #1204684 писал(а):
Я думаю, что статистические свойства полиномиальных подпоследовательностей Морса-Туе хорошо изучены.

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

 Профиль  
                  
 
 Re: Равномерное распределениt xor-а единичных битов в посл-ти
Сообщение25.04.2017, 12:29 


08/09/13
210
В работе на два поста выше указана интересная формула для погрешности распределения $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}}$

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

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



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

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


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

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