Статистика больших бинарных последовательностей, графы Кэли и автоморфизмы Вершика

Рассматриваются двоичные последовательности длины $n$, представляющие целые числа от $0$ до $2^n-1$. Пусть $s_2(x)$ — число единиц в двоичной записи $x$. Решается следующая задача: для фиксированного натурального $a$ найти все $x$, такие, что $s_2(x+a) = s_2(x)$ (здесь сложение понимается в самом обычном смысле). Множество $X(a)$ решений данного уравнения может быть описано в терминах деревьев, накрывающих граф Кэли группы $BS(1,2) = < x \to 2x, x \to x+1 >$. Оказывается, для каждого $a$ множество $X(a)$ задаётся конечным числом префиксов, кодирующих специальные пути в упомянутом накрывающем дереве. Далее исследуется распределение $p(z)$ вероятностей событий $s_2(x+a)-s_2(x) = z$, и снова параметр дисперсии в центральной предельной теореме для $p(z)$ определяется длиной кратчайшей геодезической на группе $BS(1,2)$ относительно некоторой специальной метрики. Наше исследование мотивированно возникновением асимптотического «эффекта Такаги» для класса автоморфизмов Вершика, благодаря которому возникает исследуемое уравнение.