<p>Given parameters <span class="math-container">$n,k\in \mathbb N^+$</span>, I'm interested in finding a set of binary vectors <span class="math-container">$V_{n,k}=\{v_1,\ldots,v_n\}$</span> of length that satisfies:</p>
<ul>
<li><span class="math-container">$\forall i: v_i\in\{0,1\}^{z_{n,k}}$</span>.</li>
<li>The bitwise xor of any subset of <span class="math-container">$V_{n,k}$</span> that consists up to <span class="math-container">$k$</span> elements is unique. That is, if <span class="math-container">$V_1,V_2\subseteq V_{n,k}$</span> and <span class="math-container">$|V_1|,|V_2|\le k$</span>, then <span class="math-container">$V_1$</span> and <span class="math-container">$V_2$</span> have different bitwise xors.</li>
</ul>
<blockquote>
<p>What is the smallest <span class="math-container">$z_{n,k}$</span> that allows such a construction?</p>
</blockquote>
<blockquote>
<p>Can we give an explicit construction of such a set <span class="math-container">$V_{n,k}$</span>?</p>
</blockquote>
<p>It seems that using the probabilistic method, it's possible to get an upper bound on <span class="math-container">$z_{n,k}$</span>. Can we do better?</p>
<hr />
<p>For example, <span class="math-container">$\{0001, 0011, 0110, 1011, 1111\}$</span> is an optimal construction for <span class="math-container">$n=5,k=2$</span>.</p>

CC BY-SA 4.0
2020-11-21T03:19:50.227Z
By pigeon hole principle the probabilistic construction is off by a factor at most 2... are the constant factors that important for your application?
daniello
CC BY-SA 4.0
2020-11-21T13:29:50.163Z
@daniello-somewhat important, yes.
R B
CC BY-SA 4.0
2020-11-21T16:46:04.767Z
Sorry if I am missing something, but isn't this equivalent to asking the minimal value of $m$ such that a $[m,\log_2 n, 2k]_2$ linear code exists? If so, one could appeal to the various known bounds from coding theory--I thought that the random construction is not known to be beatable for binary alphabets, and that there isn't yet an explicit construction matching the probabilistic method, but I don't know what the best known binary codes are for various $n,k$...
Jason Gaitonde
<ds.algorithms><co.combinatorics><combinatorics><extremal-combinatorics>
$k$-XOR collision free families
R B
# $k$-XOR collision free families

(Asked by: username_0 on 2020-11-20)

Given parameters $n,k\in \mathbb N^+$, I'm interested in finding a set of binary vectors $V\_{n,k}=\{v\_1,\ldots,v\_n\}$ of length that satisfies:

* $\forall i: v\_i\in\{0,1\}^{z\_{n,k}}$.
* The bitwise xor of any subset of $V\_{n,k}$ that consists up to $k$ elements is unique. That is, if $V\_1,V\_2\subseteq V\_{n,k}$ and $|V\_1|,|V\_2|\le k$, then $V\_1$ and $V\_2$ have different bitwise xors.

> What is the smallest $z\_{n,k}$ that allows such a construction?

> Can we give an explicit construction of such a set $V\_{n,k}$?

It seems that using the probabilistic method, it's possible to get an upper bound on $z\_{n,k}$. Can we do better?

---

For example, $\{0001, 0011, 0110, 1011, 1111\}$ is an optimal construction for $n=5,k=2$.

**Tags:** ds.algorithms, co.combinatorics, combinatorics, extremal-combinatorics
> **Comments:**
> **username_1**: By pigeon hole principle the probabilistic construction is off by a factor at most 2... are the constant factors that important for your application?  
> **username_0**: @daniello-somewhat important, yes.  
> **username_2**: Sorry if I am missing something, but isn't this equivalent to asking the minimal value of $m$ such that a $[m,\log_2 n, 2k]_2$ linear code exists? If so, one could appeal to the various known bounds from coding theory--I thought that the random construction is not known to be beatable for binary alphabets, and that there isn't yet an explicit construction matching the probabilistic method, but I don't know what the best known binary codes are for various $n,k$...  

---

## 0 answers

