# Structured set of binary words

Definitions:

Let $n\in \mathbb N$ be an integer, and consider the field $\mathbb K=GF(2^n)$.

For $c\in \mathbb N$, let $S_c$ be a set of $n$ elements from $\mathbb K$ such that:

1. Every element $e$ from $S$ is balanced: its weight $|e|=n/2$ (there are as many $1$s as $0$s).
2. Every pair of distinct elements $e,e'\in S, e\neq e'$ are at distance a multiple of $c$. That is: $$\forall (e,e')\in S^2, e\neq e', \exists k \in \mathbb N, |e\oplus e'|=k\cdot c$$

Observations:

• If the set $S_c$ could contain 0, 1, or 2 elements, its construction is trivial.
• For some values of $c$, there are no solutions.

Questions:

1. Does this set structure has a name?
2. Are there algorithms to construct $S_c$?
3. For fixed $(n,c)$, how many sets $S_c$ exist?
4. This question seems related to binary coding theory where the minimal distance is replaced by codewords evenly located in the space. Is there a way to express the problem into a code problem?
• I think you've made a typo in the problem statement, because as written $|S_c| = |\mathbb{K}|$ and hence $S_c = \mathbb{K}$ and can never meet the constraint that all of its elements are balanced. – Peter Taylor Jun 24 '16 at 12:05
• You are right, sorry, I meant a field size exponentially larger than the set size. So there should be $n$ elements in the set $S_c$. – wwjoze Jun 24 '16 at 12:40
• If you take the nonzero vectors in the Hadamard code, you get a solution with $c = n/2$ (and all divisors thereof), when $n$ is a power of 2. – Andrew Morgan Jun 25 '16 at 4:08
• Why do you only care about "small" sets? Does it make sense to ask about existence of large sets with this property, say, size $1.1^n$? – Igor Shinkar Jun 25 '16 at 11:47
• By looking at wright of code words modulo 2, for odd $c$ there are no such sets. For $c$ and $n$ even it is possible to construct such sets of size $2^{n/c}$. Just take $n/c$ blocks of the form $0^{c/2} \circ 1^{c/2}$ or $1^{c/2} \circ 0^{c/2}$. – Igor Shinkar Jun 26 '16 at 1:48

## 1 Answer

If there exists a solution for $(n,c)$, there exists a solution for $(4n,2c)$ (assuming $n \ge 4$): e.g., take $T = \{x||x||y||y : x,y \in S\}$, where $S$ is the solution for $(n,c)$. This works since $n^2 \ge 4n$ for $n \ge 4$.

This implies that $c = \Omega(n^{1/2})$ should be a sufficient condition to imply existence of such a set (and this is constructive; i.e., there is an algorithm to construct such sets that achieves this bound).

More generally, if there is a solution for $(n,c)$ and $n$ is even, there is a solution for $(n^2,cn/2)$. Here we let $T = \{x||\cdots ||x||y||\cdots || y : x,y \in S\}$, where we repeat $x$ $n/2$ times and repeat $y$ $n/2$ times.

This implies that, asymptotically, $c = \Omega(n/\lg n)$ is sufficient to ensure the existence of such a set (and again this is constructive).

I don't know whether $c = \Omega(n)$ is sufficient to ensure the existence of such a set.

• Thanks for sharing. Another idea: being given one solution for $(n,c)$, is it possible to deduce more solutions for $(n,c)$? – wwjoze Jun 25 '16 at 12:30