2
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\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$
    – Jason Gaitonde
    Nov 21, 2020 at 16:46

0

Reset to default

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.