# $k$-XOR collision free families

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

• By pigeon hole principle the probabilistic construction is off by a factor at most 2... are the constant factors that important for your application? Nov 21 '20 at 3:19
• @daniello-somewhat important, yes.
– R B
Nov 21 '20 at 13:29
• 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$...
– J.G
Nov 21 '20 at 16:46