Set Reconstruction on the Hypercube

Abstract

Given an action of a group $G$ on a set $S$, the $k$-deck of a subset $T$ of $S$ is the multiset of all subsets of $T$ of size $k$, each given up to translation by $G$. For a given subset $T$, the {\em reconstruction number} of $T$ is the minimum $k$ such that the $k$-deck uniquely identifies $T$ up to translation by $G$, and the {\em reconstruction number} of the action $G:S$ is the maximum reconstruction number of any subset of $S$. The concept of reconstruction number extends naturally to multisubsets $T$ of $S$ and in~\cite{CPC:257539}, the author calculated the multiset-reconstruction number of all finite abelian groups. In particular, it was shown that the multiset-reconstruction number of ${\mathbb{Z}}_2^n$ was $n+1$. This provides an upper bound of $n+1$ to the reconstruction number of ${\mathbb{Z}}_2^n$. The author also showed a lower bound of $\lfloor \frac{n+1}{2}\rfloor$ in the same paper. The purpose of this note is to close the gap. The reconstruction number of ${\mathbb{Z}}_2^n$ is $\lfloor n+1-{\log }_2(n+1-{\log }_2(n))\rfloor .$

10 pages