Is there an efficient generalized algorithm to generate a set of binary words satisfying a particular cross-correlation property?

Question

In this question, the term “word” implies a binary word, i.e. a sequence of bits.

Let $W(w)$ denote the number of non-zero bits in a word $w$.

Assuming that $l \geq 2$ is even, an $l$-bit word $w$ is balanced if and only if $W(w) = l/2.$

Assuming that $w$ is an $l$-bit word and $0 \le k < l$, let $R(w, k)$ denote the result of the left bitwise rotation (i.e. the left circular shift) of $w$ by $k$ bits. For example, if $w = 0100110001110000$, then $l = 16$ and $$\begin{array}{l} R(w,0) = w = {\text{0100110001110000}},\\ R(w,1) = {\text{1001100011100000}},\\ R(w,2) = {\text{0011000111000001}},\\ \ldots \\ R(w,15) = {\text{0010011000111000}}. \end{array}$$

Let $w_0 \oplus w_1$ denote the result of the bitwise “exclusive or” operation for two words. For example, $$0100110001110000 \oplus 1010010001000010 = 1110100000110010.$$

Assuming that $w_0$ and $w_1$ are two words of length $l$, let $f(w_0, w_1)$ denote the minimal element (the smallest number) in the tuple $$\begin{array}{l} (W(w_0 \oplus w_1),\\ W(w_0 \oplus R(w_1, 1)),\\ W(w_0 \oplus R(w_1, 2)),\\ \ldots \\ W(w_0 \oplus R(w_1, l - 1))). \end{array}$$

Given an arbitrary natural number $n \geq 4$ which is a multiple of $4$, I want to generate a set $T$ (if it exists) such that:

1. Cardinality of $T$ is $2$;
2. Each element of $T$ is a balanced $2^n$-bit word;
3. For any pair $(w_0, w_1)$ of elements of $T$ we have $f(w_0, w_1) \geq n$.

In other words, I need two balanced $2^n$-bit words $(w_0, w_1)$ such that $f(w_0, w_1) \geq n$. Is there an efficient algorithm to solve the problem? The word “efficient” here means that it should take significantly less than $2^{2n}$ operations to generate a single element of $T$: for example, if $n=32$, it is infeasible to perform $2^{64}$ operations for a single word.

Answer 1

If $m = 2^a b$ where $b$ is odd, the words $(0^{2^k} 1^{2^k})^{2^{a-k-1}b}$ for $k < a$ have cross-correlation $2^{a-1}b$. This appears to give a (potentially one of many) set of maximum size which achieves the upper bound on cross-correlation (since the average Hamming distance over all rotations of two balanced words of the same length is half the length), and is far stronger than required by the current version of the question.