Reconstructing infinite sets of integers (Q696913): Difference between revisions

This paper deals with the problem of reconstructing an infinite set of integers form its collection of subsets of cardinality \(k\). This problem is related to the famous reconstruction conjectures for finite graphs; see \textit{J. A. Bondy} [Lond. Math. Soc. Lect. Note Ser. 166, 221-252 (1991; Zbl 0741.05052)]. Let \(\mathbb{Z}\) denote the set of integers, and for \(A\subseteq \mathbb{Z}\) let \(A\choose k\) denote the set of all subsets of \(A\) of cardinality \(k\). Two sets \(A,B\subseteq \mathbb{Z}\) are called isomorphic if \(A+i=\{a+i:a\in A\}=B\) for some \(i\in\mathbb{Z}\), and we write \(A\approx B\). The \(k\)-deck of \(A\) is the function \(d_{A,k}:{A\choose k}\to \mathbb{Z}\) defined by \(d_{A,k}(S)=|\{i\in \mathbb{Z}:S+i\subseteq A\}|\). The set \(A\) is said to be reconstructible from its \(k\)-deck if \(d_{A,k}=d_{B,k}\) implies that \(A\approx B\). Note that if \(A\) is an infinite set, then \(d_{A,k}\) may take infinite values. If \(d_{A,k}\) takes only finite values, then \(A\) is said to be \(k\)-finite. It is easy to see that finite sets are reconstructible from their \(k\)-decks for all \(k\geq 3\), but reconstruction of infinite sets is more interesting. The main result of this paper is that if \(k\geq 3\) and \(A\subseteq\mathbb{Z}\) is \(k\)-finite, infinite, and has the property that \(0< d_{A,k-1}(S)<\infty\) for some \(S\in{\mathbb{Z}\choose k-1}\), then \(A\) is reconstructible form its \(k\)-deck. It is also shown that a set \(A\) need not be reconstructible from its \(k\)-deck if the condition that the \((k-1)\)-deck takes at least one finite non-zero value is not satisfied. In this sense the result is the best possible.