This question is about an example in an article of Dekking and Mendez France:

For an integer $n$ let $s(n)$ be the number of ones in the binary expansion, so that $s(2k)=s(k)$ and $s(2k+1)=s(2k)+1$, $\alpha \in (0,1/2)$ is fixed, $x = 2\pi i \alpha$ and $$ z_n= \sum_{k=0}^{n-1} \exp(xs(k)).$$ The authors claim that for all $n,m \in\mathbb N$ the following can be shown by induction: $$ z_n=z_m \text{ and } z_{n+1}=z_{m+1} \Longrightarrow n=m.$$ I see this if $n,m$ have the same parity: One has $\exp(xs(n))=\exp(xs(m))$ and if $n,m$ are both odd this gives $\exp(xs(n-1))=\exp(xs(m-1))$ which rather quickly implies $z_{n-1}=z_{m-1}$.

If $n,m$ are both even one can use the identity $$z_{2n}=(1+e^x)z_n$$ (each term $e^{xs(k)}$ for $k\in \lbrace n,\ldots,2n-1\rbrace$ corresponds to a term $e^{xs(j)}$ with $0\le j \le n-1$ such that $s(k)=s(j)+1$) to obtain $z_{n/2}=z_{m/2}$ and $z_{n/2-1}=z_{m/2-1}$.

However, I do not see how to proceed if $n$ and $m$ have different parity.


1 Answer 1


Always look for the counterexample would be a worthwhile motto it seems.

For $\alpha = 1/3$ (so that $e^x$ is a complex cube root of unity), $n = 6$ and $m = 9$ provide one. This is because $s(6) = s(9)$ and $s(6), s(7), s(8)$ are all distinct modulo 3.

For the record the first search for a counterexample was with $\alpha = 1/4$ and that failed (but without a proof -- certainly there are no examples less than $10^6$).

I suspect there may well be other counterexamples with $\alpha$ rational.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .