<p>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$.</p>

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

<p>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.</p>

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

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

CC BY-SA 3.0
2016-06-25T12:30:08.733Z
Thanks for sharing. Another idea: being given one solution for $(n,c)$, is it possible to deduce more solutions for $(n,c)$?
wwjoze
CC BY-SA 3.0
2016-06-25T00:39:19.970Z
2016-06-25T00:39:19.970Z
D.W.
<p><strong>Definitions:</strong></p>

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

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

<ol>
<li>Every element $e$ from $S$ is balanced: its weight $|e|=n/2$ (there are as many $1$s as $0$s).</li>
<li>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$$</li>
</ol>

<p><strong>Observations:</strong></p>

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

<p><strong>Questions:</strong></p>

<ol>
<li>Does this set structure has a name?</li>
<li>Are there algorithms to construct $S_c$?</li>
<li>For fixed $(n,c)$, how many sets $S_c$ exist?</li>
<li>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?</li>
</ol>

CC BY-SA 3.0
2016-06-24T12:05:53.333Z
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
CC BY-SA 3.0
2016-06-24T12:40:24.190Z
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
CC BY-SA 3.0
2016-06-25T04:08:13.100Z
If you take the nonzero vectors in the [Hadamard code](https://en.wikipedia.org/wiki/Hadamard_code), you get a solution with $c = n/2$ (and all divisors thereof), when $n$ is a power of 2.
Andrew Morgan
CC BY-SA 3.0
2016-06-25T11:47:35.673Z
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
CC BY-SA 3.0
2016-06-25T12:13:18.853Z
@AndrewMorgan: True, I forgot to mention that in the observations. That's actually one motivation for this question: try to find a different solution than Hadamard in the case n is a power of 2.
wwjoze
CC BY-SA 3.0
2016-06-25T12:13:44.133Z
@IgorShinkar: It makes sense to ask about this as long as the set is of size at least $n$. The size does not have to be exponential in $n$, simply linear would be already good.
wwjoze
CC BY-SA 3.0
2016-06-25T16:47:22.607Z
@wwjoze, when saying that linear would be good, I suppose you have some concrete application in mind..
Igor Shinkar
CC BY-SA 3.0
2016-06-25T17:03:22.023Z
@IgorShinkar: Yes, but it boils down to this theoretical problem, which is more interesting for CS.SE. When I say linear is good, it's because I believe that finding $n$ such vectors is significantly harder than finding say $n/4$.
wwjoze
CC BY-SA 3.0
2016-06-26T01:48:11.000Z
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
CC BY-SA 3.0
2016-06-26T01:56:14.793Z
Also, based on Hadamard code, for any $c \leq n/2$ you can get such a set of size $4^c$ (for even $c$ and $n$ divisible by 4)
Igor Shinkar
CC BY-SA 3.0
2016-06-26T02:00:34.803Z
Regarding your question 3, there are $exp(n \log (n)) $ many linear sets of this kind. Probably, if we don't focus of linear subsets, the number will be $exp (n^2) $.
Igor Shinkar
<co.combinatorics><coding-theory>
Structured set of binary words
wwjoze
# Structured set of binary words

(Asked by: username_0 on 2016-06-24)

**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?

**Tags:** co.combinatorics, coding-theory
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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$.  
> **username_2**: If you take the nonzero vectors in the [Hadamard code](https://en.wikipedia.org/wiki/Hadamard_code), you get a solution with $c = n/2$ (and all divisors thereof), when $n$ is a power of 2.  
> **username_3**: 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$?  
> **username_0**: @AndrewMorgan: True, I forgot to mention that in the observations. That's actually one motivation for this question: try to find a different solution than Hadamard in the case n is a power of 2.  
> **username_0**: @IgorShinkar: It makes sense to ask about this as long as the set is of size at least $n$. The size does not have to be exponential in $n$, simply linear would be already good.  
> **username_3**: @wwjoze, when saying that linear would be good, I suppose you have some concrete application in mind..  
> **username_0**: @IgorShinkar: Yes, but it boils down to this theoretical problem, which is more interesting for CS.SE. When I say linear is good, it's because I believe that finding $n$ such vectors is significantly harder than finding say $n/4$.  
> **username_3**: 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}$.  
> **username_3**: Also, based on Hadamard code, for any $c \leq n/2$ you can get such a set of size $4^c$ (for even $c$ and $n$ divisible by 4)  
> **username_3**: Regarding your question 3, there are $exp(n \log (n)) $ many linear sets of this kind. Probably, if we don't focus of linear subsets, the number will be $exp (n^2) $.  

---

## 1 answers

### Answer by username_4 on 2016-06-25. Score: 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.

> **Comments:**
> **username_0**: Thanks for sharing. Another idea: being given one solution for $(n,c)$, is it possible to deduce more solutions for $(n,c)$?  

---

