Assuming that $x$ is a sequence of $l$ bits (i.e. a binary word of length $l$) and $0 \le m < l$, let $R(x, m)$ denote the result of the left bitwise rotation (i.e. the left [circular shift](https://en.wikipedia.org/wiki/Circular_shift)) of $x$ by $m$ bits. For example, if $x = 0100110001110000$, then $l = 16$ and $$\begin{array}{l}
R(x,0) = x = {\rm{0100110001110000}},\\
R(x,1) = {\rm{1001100011100000}},\\
R(x,2) = {\rm{0011000111000001}},\\
 \ldots \\
R(x,15) = {\rm{0010011000111000}}.
\end{array}$$


Let $A \oplus B$ denote the result of the bitwise [“exclusive or”](https://en.wikipedia.org/wiki/Exclusive_or) operation for two sequences of $l$ bits. For example, $$0100110001110000 \oplus 1010010001000010 = 1110100000110010.$$


Let $H(x)$ denote the number of non-zero bits in $x$ (i.e. the [Hamming weight](https://en.wikipedia.org/wiki/Hamming_weight) of $x$).


Assuming that $x$ is an $l$-bit word, let $f(x)$ denote the minimal element (the smallest number) in the tuple $$\begin{array}{l}
(H(x \oplus R(x, 1)),\\
H(x \oplus R(x, 2)),\\
 \ldots, \\
H(x \oplus R(x, l - 2)),\\
H(x \oplus R(x, l - 1))).
\end{array}$$


For example, $$\begin{array}{l}
f(10011110100010010011) = 10,\\ 
f(11111111111111111111111111111111) = 0,\\
f(10000000000000000000000000000000) = 2,\\
f(10011100001111100000011111110000) = 8,\\
f(01000110111111100011100100100101) = 16.
\end{array}$$


Question: assuming that for any even natural number $n \ge 2$ there exists a $2n$-bit word $x$ such that $f(x) = n$ and $H(x) = n$, what can be a *time- and space-efficient* algorithm which, given an arbitrary (even) $n \ge 2$, allows to find *at least one* such $x$? For example, if $n = 10$, it is easy to check all $20$-bit words and find (in the lexicographic order) $$\begin{array}{l}
x\_0 = 00000101011011001111,\\ 
x\_1 = 00000101011110011011,\\
x\_2 = 00000101101110011101,\\
x\_3 = 00000101110011101101,\\
\ldots,\\
x\_{718} = 11111010100001100100,\\
x\_{719} = 11111010100100110000.
\end{array}$$


But as the value of $n$ grows, it becomes infeasible to check the huge amount of elements, even if one skips any element $x$ such that $H(x) \neq n$. For example, how can one find a $256$-bit word $x$ such that $f(x) = H(x) = 128$?


Let $S\_n (n = 2, 4, 6, \ldots)$ denote cardinality of the set of solutions for the corresponding $n$. Note that each solution $x$ is an element of the *family* of solutions, and this family contains exactly $2n$ elements, namely, $x$ and $(2n-1)$ its rotations. So we can pick a single (e.g. lexicographically first) element of a family and call it a *canonical solution* (all other elements of the corresponding family can be generated from this solution in a trivial way). Then let $C\_n (n = 2, 4, 6, \ldots)$ denote cardinality of the set of canonical solutions for the corresponding $n$. If my computations are correct, we have


$$\begin{array}{l}
S\_2 = 4 = 2^2,\\
C\_2 = 1 = 2^0,\\
S\_4 = 48 = 2^5 + 2^4,\\
C\_4 = 6 = 2^2 + 2^1,\\
S\_6 = 144 = 2^7 + 2^4,\\
C\_6 = 12 = 2^3 + 2^2,\\
S\_8 = 768 = 2^9 + 2^8,\\
C\_8 = 48 = 2^5 + 2^4,\\
S\_{10} = 720 = 2^9 + 2^7 + 2^6 + 2^4,\\
C\_{10} = 36 = 2^5 + 2^2,\\
S\_{12} = 5376 = 2^{12} + 2^{10} + 2^8,\\
C\_{12} = 224 = 2^7 + 2^6 + 2^5,\\
S\_{14} = 3360 = 2^{11} + 2^{10} + 2^8 + 2^5,\\
C\_{14} = 120 = 2^6 + 2^5 + 2^4 + 2^3,\\
S\_{16} = 4096 = 2^{12},\\
C\_{16} = 128 = 2^7.
\end{array}$$


Interestingly, six of the first eight elements of the tuple $(C\_2, C\_4, \ldots)$ are [highly composite numbers](https://en.wikipedia.org/wiki/Highly_composite_number): $1, 6, 12, 48, 36, 120$. I cannot explain the fact that $S\_{16}$ and $C\_{16}$ are powers of two, but it does not look like a random coincidence.



Is there an efficient generalized algorithm to find at least one binary word with the maximum rotational imbalance and the full $\{0, 1\}$-balance?
The function $f(x)$ is closely related to the notion of *autocorrelation*, which for a binary sequence $x$ of length $|x|=N$ and shift $w$ can be expressed as
$$\textbf{AC}\_x(w) := N - 2H(x\oplus R(x,w)).$$
The values of $\textbf{AC}\_x(w)$ for various non-trivial shifts (i.e. $1\leq w\leq N-1$) are called *out-of-phase autocorrelation values*.


So,
$$f(x) = \min\_{1\leq w\leq N-1} H(x\oplus R(x,w)) = \frac{N}2 - \frac12\max\_{1\leq w\leq N-1} \textbf{AC}\_x(w).$$


For the known constructions for optimal binary sequence w.r.t. autocorrelation, I refer to the paper [Cai and Ding (2009)](https://doi.org/10.1016/j.tcs.2009.02.021).


In particular, for $N=q-1\equiv 0\pmod{4}$, where $q$ is a power of prime, the Sidelnikov–Lempel–Cohn–Eastman construction produces a sequence $x$ with $H(x)=\frac{N}2$ and out-of-phase autocorrelation values $\{0,-4\}$, thus giving $f(x)=\frac{N}2$ as requested in the question. The value $N=256$ well fits into this construction since $q=257$ is prime. Here is one such 256-bit word:



```
0011101101010000101000110101100110101001111011001111111100011111010110011111100000100000011011001011011001110001000001000011110100001011010001010001001001100011110011100101011101011010100110000010100100101010110011101001111110011000001101111101000000111011

```

