Recovery from Power Sums (Q6564872)

The authors investigate the problem of recovering a collection of \(n\) numbers from the evaluation of \(m\) power sums. In detail, let \(a_1, a_2, \dots, a_m\) be \(m\) distinct positive integers and \(z_1, z_2, \dots, z_n\) be indeterminates. The objective is to determine explicit values for \(z_1, z_2, \dots, z_n\) given a list of values \(c_j = \sum_{i=1}^{n} z_i^{a_j}\) for \(1 \le j \le m\).\N\NThis problem can be modeled as follows: Given a pair \((n, A)\), where \(n\) is an integer and \(A\) is a finite set of \(m\) integers, consider the polynomial map \(\phi_{A, \Bbbk} : \Bbbk^n \to \Bbbk^m\), where \(\phi_{A, \Bbbk} = (\phi_1,\phi_2,\dots,\phi_m)\) and \N\[\N\phi_j(x_1, \dots, x_n) = x_1^{a_j} + x_2^{a_j} + \cdots + x_n^{a_j}\N\]\Nfor \(j = 1, 2, \dots, m\). Given \(c = (c_1, \dots, c_m) \in \Bbbk^m\), the goal is to investigate the fiber \(\phi_{A, \Bbbk}^{-1}(c)\).\N\NThe map \(\phi_{A, \Bbbk}\) yields in a system of polynomial equations that can be underdetermined (\(m < n\)), square (\(m = n\)), or overdetermined (\(m > n\)). The authors explore the fibers and images of power sum maps in all three regimes across various settings, including complex (\(\mathbb{C}\)), real (\(\mathbb{R}\)), and non-negative (\(\mathbb{R}_{\ge 0}\)) cases. They propose several conjectures and provide supporting propositions, demonstrating that these conjectures hold true for certain (small) cases.\N\NThis analysis reveals surprising deviations from the Bézout bound and addresses the recovery of vectors from length measurements using \(p\)-norms.