Reconstructing subsets of \(\mathbb{Z}_n\)
Let \(\mathbb{Z}_n\) denote the cyclic group of order \(n\). Say that two subsets of \(\mathbb{Z}_n\) have the same shape if one is the translate of the other. For \(A\subset \mathbb{Z}_n\) with \(| A| \geq k\), the \(k\)-deck of \(A\) is the multiset of shapes of \(k\)-subsets of \(A\). Sets of the same shape have identical \(k\)-decks. The paper is concerned with the reconstruction of shapes: the problem is when is a shape determined by its \(k\)-deck. The results are the following: if \(n\) is prime, then every shape (with at least 3 elements) is reconstructible from its 3-deck, for every \(n\) almost all shapes are reconstructible from their 3-decks, and for every \(n\) all shapes (with at least \(9\alpha (n)\) elements) are reconstructible from their \(9\alpha (n)\)-decks, where \(\alpha (n)\) denotes the number of distinct prime factors of \(n\). Generalizations are also considered.
scientific article; zbMATH DE number 1212976