MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question did not get anything from math.stackexchange. Therefore, and although probably very elementary, I pose it here. It 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.

share|cite|improve this question
The reference is to where there is an open bounty on the question. – Gerry Myerson Mar 11 '13 at 23:04
I'm not sure if the $z_{2n}$ identity is correctly explained (it is correct) -- it seems rather to follow from the fact that in general the sum of consecutive even and odd terms in $z_{2n}$ is equal to $(1 + e^x)$ times a single term contributing to $z_n$ rather than a matching between the first half and the second half. But perhaps I'm missing something. – Michael Albert Mar 12 '13 at 2:52
Your way to prove the identity is certainly better. – Jochen Wengenroth Mar 12 '13 at 7:17
up vote 4 down vote accepted

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.

share|cite|improve this answer
Very good. Thank you very much. There is a bounty on this question on – Jochen Wengenroth Mar 12 '13 at 7:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.