Where odious numbers meet arithmetic progressions

Question

Suggested by this problem:

Do the sets of all odious / evel numbers meet every infinite arithmetic progression?

A number is odious if it contains an odd number of digits $1$ in its binary representation; otherwise, it is evel. Alternatively, the odious numbers specify the positions of the nonzero values in the Thue–Morse sequence.

Equivalently:

Is it true that any arithmetic progression $an+b$, with $a>0$ and $b$ integers, has a term with an odd number of $1$'s and a term with an even number of $1$'s?

I expect that the answer is in the affirmative unless I am overlooking some simple obstruction.

Without loss of generality, one can assume that the progression is of the form $(an+1)b$ with $a=2^k-1$. Another potentially useful observation: the parity of the number of $1$'s in the binary representation of the integer $z$ is the same as the parity of the sum $z + \lfloor z/2\rfloor + \lfloor z/4\rfloor + \lfloor z/8\rfloor + \dotsb$

Answer 1

Yes, we even know that the density of such $n$ is the expected one.

A. O. Gelfond proved in 1968, in a short paper ("Sur les nombres qui ont des propriétés additives et multiplicatives données", Acta Arithmetica 13, pages 259-265) that, for all $b \bmod a$ and $j \bmod m$, $$(\star) \, \lim_{N \to \infty}\frac{1}{N/a}\#\{ 1 \le n \le N: n \equiv b \bmod a, \, s_q(n) \equiv j \bmod m\}=\frac{1}{m}.$$ Here $a,q,m$ are fixed positive integers, $s_q$ is the sum of digits in base-$q$, and $\gcd(m,q-1)=1$ (otherwise there are obvious obstructions, due to the congruence $n \equiv s_q(n) \bmod {q-1}$).

Now apply this with $q=m=2$ to get your answer.

Regarding the error term in $(\star)$: already Gelfond proved a power saving result. This means that the expression in the limit in $(\star)$ is $1/m$ plus $O_{a,m,q}(N^{-c})$ for some concrete $c$ depending on $m$ and $q$.

An optimal value for $c$ when $q=m=2$ was determined in 2009 by V. Shevelev ("Exact exponent in the remainder term of Gelfond's digit theorem in the binary case", Acta Arithmetica 136, pages 91-100).