Binary weight of shifted integers

Question

Suppose $n_2$ denotes the binary representation of the integer number $n$. Let $X_2(n)=[1_22_2\ldots n_2]$,$n\geq3$, be a binary vector which is obtained by concatenating of binary representation of the numbers from $1$ to $n$. Also, let $X_2^m(n)$,$0\leq m\leq n-1$,denotes the cyclically $m$ shift of the entries of the vector $X_2(n)$. For example, we have $$X_2^0(n)=X_2(n)$$ $$X_2^1(n)=[n_21_22_2\ldots(n-1)_2]$$ $$X_2^2(n)=[(n-1)_2n_21_22_2\ldots(n-2)_2]$$ and so on.

For two binary vectors $X$ and $Y$ (with same length), suppose $|X\cap Y|$ denotes the number of ones common to both $X$ and $Y$.

The conjecture is:

Let $n\geq 3$ be a natural number. For all $m$ and $k$, we have $|X_2^m(n)\cap X_2^k(n)|\cong 0 \mod 2$ if and only if $n=2^s-1$, for some integer number $s$.

Note: I use $\lfloor \log_2n\rfloor +1$ bits for binary representation of each integer number from $1$ to $n$. So, fedja's example is as follows:

$X_2(3)=[011011]$, $X_2^1(3)=[110110]$ and $X_2^2(3)=[101101]$. We can see the claim is true.

The conjecture is tested for many integer numbers. I appreciate any helpful comments and answers.

$\textbf{Added later}(19/09/2017)-9:03:$ The other easy way to see the problem is as follows:

For the natural number $n\geq 3$, let $G$ be a graph with $n$ vertices such that the vertices of $G$ are labeled by numbers $1$ to $n$. Then we represent each vertex label in uniform binary form and we connect the vertex $i$ to the vertex $j$ with the edge weight equal to the number of ones common to both $i_2$ and $j_2$. Note that the resulting graph is complete and each edge has a weight between $0$ to $\lfloor \log_2n\rfloor$. See the below example:

By this representation, we have an equivalent graph theory problem. In this context we must show that the summation of the weights of edges of some special subgraphs are even or odd.

Answer 1

This is not a full answer, just the easy implication that if $n=2^{s}-1$ with $s\ge 2$, then, indeed, all overlaps are even.

We will think of our binary representations of length $s$ as written on the circle. We'll look at each digit sequence separately, so we get (starting with the right bit) $$ 1010101\dots101, \\ 01100110011\dots0011, \\ 000111100001111\dots00001111 $$ etc. Let's do elementary Fourier analysis on $\mathbb Z_n$. The $r$-th sequence $(r=0,\dots,s-1)$ has the Fourier coefficients (up to conjugation, which I'm too lazy to write at 11:15PM) $$ F_r(z)=\frac 1n z^{2^r-1}(1+z+z^2+\dots+z^{2^r-1})(1+z^{2^{r+1}}+z^{2\times 2^{r+1}}+\dots +z^{n+1-2^{r+1}}) \\ =\frac 1nz^{2^r-1}\frac{z^{2^r}-1}{z-1}\frac{z^{n+1}-1}{z^{2^{r+1}}-1} =\frac 1nz^{2^r-1}\frac 1{z^{2^r}+1} $$ for $z^n=1, z\ne 1$. $F(1)=\frac{n+1}{2n}$ regardless of $r$.

The cardinality of the intersection of the $r$-th sequence with the shift of itself by $m$ can be written as $$ n\sum_{z:z^n=1}|F_r(z)|^2z^m=n\sum_{z:z^n=1}\frac{z^m}{|z^{2^r}+1|^2} $$ (Plancherel) This looks pretty useless for determining the individual parities but it shows immediately ($z\mapsto z^{2^r}$ is just a rearrangement of the $n$th roots of unity) that the number of overlaps in the $r$-th position for $m$ is the same as the number of overlap in the $0$-th position for $m/2^r$ where the division is understood in the sense of $\mathbb Z_n$. Thus, instead of asking what happens for the individual $m\ne 0$ in all positions, we can ask what happens in the $0$-th position for $m,m/2,\dots, m/2^{s-1}$ ($m=0$ is a trivial case because the self-overlap in each position is $\frac{n+1}2=2^{s-1}$, which is even when $s>1$ and $n=2^1-1=1$ is, indeed, problematic).

Now we forget all high-tech and just keep this conclusion in mind. Of course, once we know it, we can show it in an elementary way too.

If $m\in\{1,\dots,n-1\}$, then we need to count the pairs of odd numbers in $\{1,2,\dots,n\}$ at distance either $m$ or $n-m$. But that is easy: if $m$ is even, they are $\frac{n+1-m}2=2^{s-1}-\frac m2\equiv \frac m2\mod 2$. Otherwise they are $\frac{m+1}2\equiv_2 \frac{m+1}2+2^{s-1}=\frac{m+n}2+1$.

Thus, if we consider the full cycle $m_r=m/2^r$ ($r=0,\dots,r-1$) in $\mathbb Z_n$ using the representatives $m_r\in\{1,\dots,n-1\}$ (some numbers may repeat, that's OK), then the parity of the number of overlaps in the $0$-th position for the shift by $m_r$ is the parity of $m_{r+1}=\frac{m_r}2$ if $m_r$ is even and of $1+m_{r+1}=1+\frac{m_r+n}2$ if $m_r$ is odd. This means that to get the parity of the full sum over the cycle, we should add the number of odd members of the cycle and the number of $+1$ corrections. But these two numbers are the same because the corrections are generated exactly by the odd members of the cycle, so the final result is always even.

This is quite simple and relatively clean. It is the other implication that seems to be a headache. Any bright ideas?