The combinatorial Radon transform modulo the symmetric group (Q1190146)

The farmer's malicious apprentice, when asked to weigh \(n\) sacks of grain, weighed them two at a time and reported the resulting \(n(n-1)/2\) combined weights with no indication of the pairs that produced them. Can the weights of the sacks be recovered? Of course, attaching weights to particular sacks is impossible. The best that can be hoped for is to recover the weights modulo permutation of the sacks. That suggests the following more formal version of the problem. Let \(X_ n=\mathbb{R}^ n/S_ n\), real \(n\)-space modulo the action of the symmetric group determined by permuting \(n\)-tuples in the obvious way. There seems to be no universally acknowledged name for the elements of \(X_ n\) (not sets, since duplicates are allowed). They are sometimes called multisets, sometimes bags. We use the latter term, identifying an element of \(X_ n\) as an \(n\)-bag when the prefix signaling the dimension is helpful. We will often write \(n\)-bags as \(n\)-tuples, trusting that the reader will remember that how the indices are matched to the elements is irrelevant. We generally use \(x,y,\dots\) for bags and \(\alpha,\beta,\dots\) for the elements they contain. Consider the function \(R=R_{n,k}\) defined on \(n\)-bags by \[ R_{n,k} (x)= \sum_{\alpha \in y} \{\alpha \mid y \text{ a } k \text{-subbag of } x\}. \] \(R_{n,k}\) maps \(X_ n\) to \(X_{{n \choose k}}\). We sometimes abbreviate \(R_{n,2}\) as \(R_ n\). The problem is to determine when \(R\) is injective, and to invert it when it is. After we had worked on this problem for some time, Persi Diaconis pointed us to the literature: Moser's papers [Can. Math. Bull. 2, 85-89 (1959; Zbl 0089.266), Am. Math. Mon. 507 (1957)] and those of E. G. Straus and his co-workers [Pac. J. Math. 12, 187-196 (1962; Zbl 0104.270), Pac. J. Math. 8, 847-856 (1958; Zbl 0084.022)], where many of our results had been anticipated. Nevertheless, we think the area is worth reviving. In this paper we analyze the nature of some of the known nonuniqueness of \(R_{n,2}\) and provide a new algorithm for inverting \(R_{n,k}\) in time \(O(n^{k^ 2-k+1} \log (n))\). The algorithm is usually much more efficient than this worst case upper bound and may help settle some open problems.