Is there an efficient generalized algorithm to find at least one binary word with the maximum rotational imbalance and the full $\{0, 1\}$-balance?

Question

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) 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” 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 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: $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.

Answer 1

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).

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

Answer 2

Suppose x contains n 1’s, and y is a cyclic shift of x. Suppose that there are exactly m positions where both x and y have 1’s. Then x XOR y has 2(n-m) 1’s. Thus f(x) is always even. Thus a necessary condition for H(x) = f(x) = n is that n is even.

Consider the length 4 sequence x = 0110. The cyclic shifts are x_1=1100, and x_2=1001, and x_3 = 0011, so that x XOR x_1 = 2, and x XOR x_2 = 4, and x XOR x_3 = 2. Thus f(x) = 2.

Now consider a sequence y = (0110)^m =0110 0110 ... (m times) … 0110. The cyclic shifts of y are y_1=(1100)^m y_2=(1001)^m, and x_3 = (0011)^m, so that y XOR y_1 = 2m y XOR y_2 = 4m y XOR y_3 = 2m. Thus f(y) = 2m =H(y).

This gives explicit solutions to f(x)= H(x) wherever solutions exist.