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

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


Your Answer

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