1
$\begingroup$

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?
$\endgroup$
  • 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$ – Peter Taylor Jun 24 '16 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 Jun 24 '16 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$ – Andrew Morgan Jun 25 '16 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$ – Igor Shinkar Jun 25 '16 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$ – Igor Shinkar Jun 26 '16 at 1:48
1
$\begingroup$

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.

$\endgroup$
  • $\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 Jun 25 '16 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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