Reconstructing a set from its subset sums: \(2\)-torsion-free groups

A famous conjecture in graph theory, asked by Kelly (1957) and Ulam (1960) and now known as the reconstruction conjecture, states that every graph with \(n\geq 3\) vertices is determined up to isomorphism by the multiset of induced subgraphs with \(n-1\) vertices (also given up to isomorphism). Since that conjecture was formulated, many other questions in a similar spirit have been asked: one such question was answered in a paper published in this journal.

This paper addresses a reconstruction problem concerning subsets of Abelian groups, or more precisely multisets of elements of Abelian groups. Given an Abelian group \(G\) and a finite multiset \(A\) of elements of \(G\), define the finite-sums multiset \(\text{FS}(A)\) of \(A\) to be the set of all sums of elements of \(A\), counted with appropriate multiplicity. For example, if \(A\) is the multiset \(\{1,1,2\}\) in \(\mathbb Z\), then \(\text{FS}(A)=\{0,1,1,2,2,3,3,4\}\). The reconstruction problem that results from this definition is to understand when \(A\) is determined by \(\text{FS}(A)\).

If \(G\) contains an element \(x\) of order 2, then for every other element \(y\), we have that \(\text{FS}(\{x,y\})\) and \(\text{FS}(\{x,x+y\})\) are both equal to \(\{0,x,y,x+y\}\), and more generally \(\text{FS}(A\cup\{x,0,0\})=\text{FS}(A\cup\{x,x,x\})\) for every set \(A\). (Here we have used the symbol \(\cup\) for the multiset “union” operation that adds multiplicities: for example, \(\{1,2,2\}\cup\{1,2,3\}=\{1,1,2,2,2,3\}\).) It is therefore natural to restrict attention to groups of odd order, or if one wishes to include infinite groups, to groups with no element of order 2. The main result of the paper is to characterize pairs of multisets \(A,B\) in such groups \(G\) such that \(\text{FS}(A)=\text{FS}(B)\).

To do this, the authors start by considering a modification of the problem where the aim is to characterize pairs of sets \(A,B\) such that \(\text{FS}(A)\) and \(\text{FS}(B)\) are equal up to a translation, after which it is straightforward to understand for which of those pairs the translation has to be zero.

Before we give examples of such pairs, note that if \(A\) and \(B\) are any two multisets, then \(\text{FS}(A\cup B)=\text{FS}(A)+\text{FS}(B)\), once we interpret the two sides of the equation appropriately. By \(A\cup B\) we mean the union with appropriate multiplicity: for instance, \(\{1,1,2\}\cup\{1,2,3\}=\{1,1,1,2,2,3\}\). And by the sum \(R+S\) of two multisets \(R\) and \(S\) we mean the multiset \(T\) such that \(x\) occurs in \(T\) with multiplicity equal to the number of pairs \((r,s)\in R\times S\) such that \(r+s=t\), where the pairs \((r,s)\) are themselves counted with appropriate multiplicity. For instance, \(\{0,1,1\}+\{1,2\}=\{1,2,2,2,3,3\}\). (Note that this operation is simply convolving the functions that send elements to their multiplicities.) Thus, if we can find distinct multisets \(A\) and \(B\) such that \(\text{FS}(A)=\text{FS}(B)+x\), then for every \(C\) we also have that \(\text{FS}(A+C)=\text{FS}(B+C)+x\).

With that in mind, note that for every element \(a\in G\) we have that \(\text{FS}(\{-a\})=\{0,-a\}=\text{FS}(a)-a\), and therefore more generally if \(A\) is any multiset in \(G\) and \(B\) results from replacing some element \(a\) of \(A\) by \(-a\), then \(\text{FS}(B)=\text{FS}(A)-a\).

A more interesting example is obtained as follows. Let \(x\) be an element of \(G\) of finite (and necessarily odd, given our assumptions) order \(n\), let \(k\) be minimal such that \(2^k\equiv\pm 1\pmod n\), and let \(a\) be coprime to \(n\). Let \(A\) be a multiset that contains the set \(V=\{x,2x,4x,\dots,2^{k-1}x\}\) and let \(B\) be the result of replacing this set by \(W=\{ax,2ax,4ax,\dots,2^{k-1}ax\}\). Then \(\text{FS}(V)=\{0,x,2x,3x,\dots,(2^k-1)x\}\) and \(\text{FS}(W)=\{0,ax,2ax,3ax,\dots,(2^k-1)ax\}\). If \(2^k-1\equiv 1\pmod n\), then the multiset \(\{0,x,2x,3x,\dots,(2^k-1)x\}\) consists of all multiples of \(x\) with the same multiplicity apart from 0, which has multiplicity one greater, and since \(a\) is coprime to \(n\), so does the multiset \(\{0,ax,2ax,3ax,\dots,(2^k-1)ax\}\). Therefore in this case \(\text{FS}(V)=\text{FS}(W)\). If on the other hand \(2^k\equiv -1\pmod n\), then \(\{0,x,2x,3x,\dots,(2^k-1)x\}\) contains all multiples of \(x\) with the same multiplicity apart from \(-x\), which has multiplicity one less. If we replace this by \(\{0,ax,2ax,3ax,\dots,(2^k-1)ax\}\) then the element with multiplicity one less is \(-ax\), so \(\text{FS}(W)=x-ax+\text{FS}(V)\). In both cases, by the remarks above, it follows that \(\text{FS}(A)\) and \(\text{FS}(B)\) are equal up to a translation.

This gives us two ways of converting a multiset \(A\) into another multiset with the same finite-sums multiset up to translation. Let us call these basic transformations. Of course, these methods can be composed, so if we can create \(B\) from \(A\) by a sequence of basic transformations, then \(\text{FS}(B)\) is a translate of \(\text{FS}(A)\). The main result of this paper is a converse to that statement: if \(\text{FS}(B)\) is a translate of \(\text{FS}(A)\), then one can obtain \(B\) from \(A\) by a sequence of basic transformations. To obtain a characterization of pairs \(A,B\) with \(\text{FS}(A)=\text{FS}(B)\) one then simply insists that the sum of the amounts by which one translates is zero.

As might be expected from the statement, the proof is interesting and non-obvious. The authors begin by introducing a third and more technical equivalent property. Then to prove the resulting three-way equivalence, they start by proving the two easier implications. Then for the hardest one, they begin by
using Fourier analysis to prove it for finite cyclic groups. Next, they use a discrete Radon transform (introduced by Ciprietti and Glaudo in an earlier paper) to pass from finite cyclic groups to powers of finite cyclic groups. Every finite Abelian group is a subgroup of a power of a finite cyclic group, and the implication carries over to subgroups, so they can deduce the result for all finite Abelian groups. A non-trivial further step takes them to finitely generated Abelian groups, and it is straightforward to get from this to all Abelian groups.