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$$


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


  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?
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jun 24, 2016 at 12:05
  • $\begingroup$ 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$. $\endgroup$
    – wwjoze
    Commented Jun 24, 2016 at 12:40
  • $\begingroup$ 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. $\endgroup$ Commented Jun 25, 2016 at 4:08
  • $\begingroup$ 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$? $\endgroup$ Commented Jun 25, 2016 at 11:47
  • 1
    $\begingroup$ 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}$. $\endgroup$ Commented Jun 26, 2016 at 1:48

1 Answer 1


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.