Recovery from Power Sums

Abstract

We study the problem of recovering a collection of n numbers from the evaluation of m power sums. This yields a system of polynomial equations, which can be underconstrained (m < n), square (m = n), or overconstrained (m > n). Fibers and images of power sum maps are explored in all three regimes, and in settings that range from complex and projective to real and positive. This involves surprising deviations from the Bézout bound, and the recovery of vectors from length measurements by p-norms.

Keywords:

• p-norms
• solving polynomial systems
• images and fibers
• power sums

1 Introduction

This article offers a case study in solving systems of polynomial equations. Our model setting reflects applications of nonlinear algebra in engineering, notably in signal processing [15], sparse recovery [7], and low rank recovery [8]. Suppose there is a secret list of complex numbers $z_1,z_2,\dots ,z_n$. Our task is to find them. Measurements are made by evaluating the m power sums $c_j={\sum }_{i=1}^n{z}_i^{a_j}$, where $\mathcal{A}=\{a_1,a_2,\dots ,a_m\}$ is a set of m distinct positive integers. Our aim is to recover the multiset $z=\{z_1,\dots ,z_n\}$ from the vector $c=(c_1,\dots ,c_m)$.

To model this problem, for any given pair $(n,\mathcal{A})$, we consider the polynomial map(1) $${\varphi }_{\mathcal{A},\mathbb{C}} : {\mathbb{C}}^n\to {\mathbb{C}}^m,\hspace{1em}\text{where} {\varphi }_j = x_1^{a_j}+x_2^{a_j}+\cdots +x_n^{a_j}\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}\text{for} j=1,2,\dots ,m.$$(1)

We are interested in the image and the fibers of the map ${\varphi }_{\mathcal{A},\mathbb{C}}$. The study of these complex algebraic varieties addresses the following questions: Is recovery possible? Is recovery unique? This problem is especially interesting when $z_1,z_2,\dots ,z_n$ are real, or even positive. Hence, we also study the maps ${\varphi }_{\mathcal{A},\mathbb{R}}$ and ${\varphi }_{\mathcal{A},\ge 0}$ that are obtained by restricting ${\varphi }_{\mathcal{A},\mathbb{C}}$ to ${\mathbb{R}}^n$ and ${\mathbb{R}}_{\ge 0}^n$, respectively. For any of these, we study the following system of m equations in n unknowns:(2) $${\varphi }_{\mathcal{A},•}(x) = c.$$(2)

There are three different regimes. If m > n then (2) is overconstrained and has no solution, unless $c={\varphi }_{\mathcal{A},\mathbb{C}}(z)$ for some $z\in {\mathbb{C}}^n$, and we anticipate unique recovery of $\{z_1,\dots ,z_n\}$. If m = n then (2) is expected to have finitely many solutions, at most the Bézout number $a_1{a}_2\dots a_n$. If m < n then the solutions to (2) form a variety of expected dimension n – m.

Example 1

(n = 3). We illustrate the three regimes. Consider the multiset $z=\{6,8,13\}$. We first allow m = 4 measurements, with $\mathcal{A}=\{2,5,7,8\}$. Then the system (2) equals(3) $$\begin{array}{cccccccc}{x}_1^2+x_2^2+x_3^2& =& 269,& & & x_1^5+x_2^5+x_3^5& =& 411837,\\ x_1^7+x_2^7+x_3^7& =& 65125605,& & & x_1^8+x_2^8+x_3^8& =& 834187553.\end{array}$$(3)

For the lexicographic term order with $x_1>x_2>x_3$, we compute the reduced Gröbner basis$$\{ x_1+x_2+x_3-27 , x_2^2+x_2{x}_3+x_3^2-27(x_2+x_3)+230 , (x_3-6)(x_3-8)(x_3-13) \}.$$

This is a 0-dimensional radical ideal, having six zeros, so $z=\{6,8,13\}$ is recovered uniquely.

We next take m = 3 with $\mathcal{A}=\{2,5,7\}$. Here, we solve the first three equations in (3). This square system has 66 complex solutions, four less than the Bézout number $70=2\times 5\times 7$. Finally, we allow only m = 2 measurements, with $\mathcal{A}=\{2,5\}$. The first two equations in (3) define a curve of degree 10 = 2 × 5 in ${\mathbb{C}}^3$. Its closure in ${\mathbb{P}}^3$ is a singular curve of genus 14.

Remark 2.

In applications, noise in the data is a concern. This makes our problem interesting even for $\mathcal{A}=\{1,2,\dots ,m\}$. However, from the perspectives of algebraic geometry and exact computations, the dense case is solved. The power sums reveal the elementary symmetric functions, via Newton’s identities. Our recovery problem amounts to finding the roots of a polynomial of degree n in one variable. For related work see [1]. The recent article [15] studies a more general version of the dense problem: The authors consider the composition γ of the map ${\varphi }_{\mathcal{A}}$ with a linear map $T:{\mathbb{C}}^m\to {\mathbb{C}}^n$ where $m\le n$ and $\mathcal{A}=\{1,\dots ,m\}$. Their Theorem 1 states that, if T is generic, then ${\gamma }^{-1}(\gamma (x))$ is finite for every $x\in {\mathbb{C}}^m$.

In this paper, $\mathcal{A}$ is any set of m distinct positive integers. Our presentation is organized as follows. In Section 2 we show that, for $m\le n$, the fiber of ${\varphi }_{\mathcal{A},\mathbb{C}}$ above a generic point in ${\mathbb{C}}^m$ has the expected dimension n – m. For m > n we expect the recovery of complex multisets from power sums to be unique when $\gcd (a_1,\dots ,a_m)=1$. This is stated in Conjecture 6. In Section 3, we study the case m = n. We propose a formula for the number of solutions of (2). This number is generally less than the Bézout number $a_1{a}_2\dots a_n$. For instance, in Example 1, the drop is from 70 to 66. We shall explain this. This issue is closely related to the question, put forth in [3], for which sets $\mathcal{A}$ the power sums form a regular sequence. We present supporting evidence for the conjectures made in [3] and we offer generalizations.

In Section 4 we turn to the images of the power sum maps ${\varphi }_{\mathcal{A},\mathbb{C}},{\varphi }_{\mathcal{A},\mathbb{R}}$, and ${\varphi }_{\mathcal{A},\ge 0}$. The image of ${\varphi }_{\mathcal{A},\mathbb{C}}$ is constructible and has the expected dimension $\text{min}(m,n)$, but it is generally not closed in ${\mathbb{C}}^m$. In the overconstrained case (m > n), we study the degree and equations of the closure of the image. For instance, the image of ${\varphi }_{\mathcal{A},\mathbb{C}}:{\mathbb{C}}^3\to {\mathbb{C}}^4$ in Example 1 is defined by a polynomial of degree 45 with 304 terms. The image of the real map ${\varphi }_{\mathcal{A},\mathbb{R}}$ is semialgebraic in ${\mathbb{R}}^m$. It is closed if some a_i is even. Moreover, the orthant ${\mathbb{R}}_{\ge 0}^n$ is mapped to a closed subset of ${\mathbb{R}}_{\ge 0}^m$. It is a challenging task to find a semi-algebraic description of the image. We take first steps by exploring its algebraic boundary. Delineating the real image involves the ramification locus in ${\mathbb{C}}^n$ and its image in ${\mathbb{C}}^m$, which is the branch locus of ${\varphi }_{\mathcal{A},\mathbb{C}}$.

In Section 5, we examine our problem over the positive real numbers. Here, the recovery from power sums is equivalent to recovery from length measurements by various p-norms. This enables a better understanding of the map ${\varphi }_{\mathcal{A},\ge 0}$. We prove that recovery is unique in the square case n = m, see Proposition 24. The image of ${\varphi }_{\mathcal{A},\ge 0}$ is expressed as a compact subset in the probability simplex ${\Delta }_{m-1}$. Theorem 27 characterizes the structure of this set.

2 Fibers

Consider the map $\varphi ={\varphi }_{\mathcal{A},\mathbb{C}}$ from ${\mathbb{C}}^n$ to ${\mathbb{C}}^m$ whose coordinates are ${\varphi }_j={\sum }_{i=1}^n{x}_i^{a_j}$. In this section we examine the fibers of $\varphi$ and we show that they have the expected dimension. We conclude with a discussion concerning the uniqueness of recovery in the case $m=n+1$.

Given a point $c=(c_1,\dots ,c_m)$ in ${\mathbb{C}}^m$, the defining ideal of the fiber ${\varphi }^{-1}(c)$ equals$$I_c = 〈 {\varphi }_1(x)-c_1,\dots ,{\varphi }_m(x)-c_m 〉 \subset \mathbb{C}[x_1,\dots ,x_n].$$

Our recovery problem amounts to computing the variety $V(I_c)={\varphi }^{-1}(c)$ defined by I_c in ${\mathbb{C}}^n$.

Proposition 3.

Assume $m\le n$. Then the following hold:

1. The map $\varphi$ is dominant, i.e., the image of $\varphi$ is dense in ${\mathbb{C}}^m$.

2. For generic c, the ideal I_c is radical, and its variety $V(I_c)$ has dimension n – m.

Proof.

The fiber of $\varphi$ above a point c is the variety $V(I_c)\subset {\mathbb{C}}^n$. By [14, Lemma 054Z], the fibers of $\varphi$ are generically reduced. This implies that the ideal I_c is radical for all points c outside a proper closed subset of ${\mathbb{C}}^m$. The Jacobian of the map $\varphi$ is the m × n matrix(4) $$\mathcal{I} = {\left(\begin{array}{c}\frac{\partial {\varphi }_j}{\partial x_i}\end{array}\right)}_{\stackrel{1\le i\le n}{1\le j\le m}} = {\left(\begin{array}{c}{a}_j{x}_i^{a_j-1}\end{array}\right)}_{\stackrel{1\le i\le n}{1\le j\le m}}.$$(4)

Up to multiplication by a positive integer, each m × m minor of this matrix is the product of a Vandermonde determinant and a Schur polynomial; see (8). In particular, none of these minors of $\mathcal{I}$ is identically zero. Thus, the Jacobian matrix $\mathcal{I}$ has rank m over the field $\mathbb{C}(x_1,\dots ,x_m)$. By [9, I.11.4], this implies that the polynomials ${\varphi }_1,\dots ,{\varphi }_m$ are algebraically independent over $\mathbb{C}$. From this we conclude that the associated ring homomorphism$${\varphi }^{*} : \mathbb{C}[y_1,\dots ,y_m]\to \mathbb{C}[x_1,\dots ,x_n], y_i\mapsto {\varphi }_i(x)$$is injective. Hence, our map $\varphi$ is dominant, by [14, Lemma 0CC1]. The statement in (i) that the image is dense refers either to the Zariski topology or to the classical topology. Both have the same closure in this situation, by [10, Corollary 4.20].

It now follows from [11, Theorem 9.9 (b)] that, for all points c outside a proper Zariski closed subset of ${\mathbb{C}}^m$, the fiber ${\varphi }^{-1}(c)$ has dimension n – m. This finishes the proof. □

The condition that the point c is generic is crucial in Proposition 3. The following example shows that the fiber dimension can jump up for special points $c\in {\mathbb{C}}^m$.

Example 4

(n = 3). Let m = 3 and $\mathcal{A}=\{3,5,7\}$. The generic fiber of the map $\varphi$ consists of 60 points in ${\mathbb{C}}^3$. Interestingly, that number would increase to 66 if the number 3 in our set $\mathcal{A}$ were replaced with the number 2, as we saw in Example 1. Now, consider the fiber over $c=(0,0,0)$. It is defined by the homogeneous ideal $I_0=〈x_1^a+x_2^a+x_3^a : a\in \mathcal{A}〉$. This ideal defines three lines of multiplicity three, with an embedded point at the origin. The radical of this ideal equals $〈x_1+x_2,x_3〉\cap 〈x_1+x_3,x_2〉\cap 〈x_2+x_3,x_1〉$.

Let us assume m > n, so we are in the overconstrained case. The following statement is derived from the m = n case in Proposition 3, namely by adding additional constraints:

Corollary 5.

For m > n, the fiber of $\varphi$ above a generic point in ${\mathbb{C}}^m$ is empty. The closure of the image of $\varphi$ is an irreducible variety of dimension n in ${\mathbb{C}}^m$. The same holds over $\mathbb{R}$.

Describing the image of $\varphi$ will be our topic in Sections 4 and 5. A generic point c in that image can be created easily, namely by setting $c=\varphi (z)$ where $z=(z_1,\dots ,z_n)$ is any generic point in ${\mathbb{C}}^n$. We are interested in the fiber ${\varphi }^{-1}(c)$ over such a point c. By construction, that fiber is nonempty: it contains all $n!$ points that are obtained from z by permuting coordinates. For the remainder of this section, assume $\gcd (a_1,\dots ,a_m)=1$. Then we conjecture that there are no other points in that fiber. This would mean that the set $\{z_1,\dots ,z_n\}$ can be recovered uniquely from any m of its power sums, provided $m\ge n+1$.

Conjecture 6. The recovery of a set of n complex numbers from n + 1 power sums with coprime powers is unique. To be precise, for $m=n+1$, the map $\varphi$ is generically injective. This means that, for generic points $z\in {\mathbb{C}}^n$, the fiber ${\varphi }^{-1}(\varphi (z))$ coincides with the set of $n!$ coordinate permutations of z.

We are also interested in the following more general conjecture. Let $\tau =({\tau }_1,\dots ,{\tau }_n)$ be in ${\mathbb{R}}_{>0}^n$ and consider the map $\psi :{\mathbb{C}}^n\to {\mathbb{C}}^m$, where ${\psi }_j={\sum }_{i=1}^n{\tau }_i{x}_i^{a_j}$. Let $\text{Stab}(\tau )$ be the subgroup of the symmetric group S_n consisting of all coordinate permutations that fix τ.

Conjecture 7. For generic points $z\in {\mathbb{C}}^n$, the fiber ${\psi }^{-1}(\psi (z))$ is precisely the set of all coordinate permutations of z. The cardinality of this set is equal to $|\text{Stab}(\tau )|$.

By computing Gröbner bases, we confirmed Conjectures 6 and 7 for a range of small cases: Conjecture 6 holds for n = 4 and $\sum _{a\in \mathcal{A}}a\le 52$, and for n = 5 and $\sum _{a\in \mathcal{A}}a\le 49$. Conjecture 7 holds for $(n,m)=(2,3)$ and $\sum _{a\in \mathcal{A}}a\le 100$, for $(n,m)=(3,4)$ and $\sum _{a\in \mathcal{A}}a\le 69$, and for $(n,m)=(4,5)$ and $\sum _{a\in \mathcal{A}}a\le 49$. In all cases we took random integers $1\le {\tau }_i\le 100$.

3 Square Systems

We here fix n = m, so we study the square case. By Proposition 3, our system (2) has finitely many solutions in ${\mathbb{C}}^n$. Our aim is to find their number. We study this for n = 2 (Proposition 10) and n = 3 (Conjecture 14). This generalizes a conjecture of Conca, Krattenthaler and Watanabe [3, Conjecture 2.10]. We conclude with a discussion of the general case $n\ge 4$.

Our point of departure is a result which links Proposition 3 with Bézout’s Theorem.

Proposition 8.

For general measurements $c\in {\mathbb{C}}^n$, the square system (2) has finitely many complex solutions $x\in {\mathbb{C}}^n$. The number of these solutions is bounded above by $a_1{a}_2\dots a_n$.

We now define the homogenized system (HS) to be the system (2), where c_j is replaced by $c_j{x}_0^{a_j}$. Note that (HS) has its solutions in ${\mathbb{P}}^n$. What we are interested in for our recovery problem are the solutions that do not lie in the hyperplane at infinity $\{x_0=0\}$. Next, we define the system at infinity (SI) to be (2) with c = 0. The solutions of (SI) are in ${\mathbb{P}}^{n-1}$. The cone over that projective scheme is the zero fiber of the map $\varphi$. We will use the notations (HS) and (SI) both for the systems of equations and the projective schemes defined by them.

Remark 9.

The scheme (HS) is in general not the projective closure of the affine part defined by (2), as it can contain higher-dimensional components. For example, set $n=m=4$, and let $\mathcal{A}$ consist of four odd coprime integers. The variety in ${\mathbb{C}}^4$ defined by the system (2) is zero-dimensional by Lemma 3. However, the scheme (HS) is not zero-dimensional in ${\mathbb{P}}^4$, since it contains the lines defined by $x_i=-x_j,x_k=-x_l,x_0=0$ for $\{i,j,k,l\}=\{1,2,3,4\}$.

The solutions of (HS) that lie in the hyperplane $\{x_0=0\}$ are precisely the solutions to (SI). However, the multiplicities are different. If the variety (SI) in ${\mathbb{P}}^{n-1}$ is finite, then the number of solutions to (2) in ${\mathbb{C}}^n$ equals $a_1{a}_2\dots a_n$ minus the total length of (HS) along (SI). For n = 2, this observation fully determines the number of solutions to (2) in terms of $\mathcal{A}$.

Proposition 10

(n = 2). Assume $a_1<a_2$. For generic $(c_1,c_2)\in {\mathbb{C}}^2$, the number of common solutions in ${\mathbb{C}}^2$ to the equations $x_1^{a_1}+x_2^{a_1}=c_1$ and $x_1^{a_2}+x_2^{a_2}=c_2$ equals $a_1(a_2-\text{gcd}(a_1,a_2))$ if both $a_1/\text{gcd}(a_1,a_2)$ and $a_2/\text{gcd}(a_1,a_2)$ are odd. It equals the Bézout number $a_1{a}_2$ otherwise.

Proof.

First assume $\text{gcd}(a_1,a_2)=1$. The binary forms $x_1^{a_1}+x_2^{a_1}$ and $x_1^{a_2}+x_2^{a_2}$ are relatively prime, unless both a₁ and a₂ are odd, so $x_1+x_2$ divides both forms. In the former case, (SI) has no solutions, so the number of solutions to (2) equals the Bézout number $a_1{a}_2$. If a₁ and a₂ are odd, then (SI) $=\{x_1+x_2=0\}$ defines the point $(1:-1)$ on the line ${\mathbb{P}}^1$, corresponding to the point $P=(1:-1:0)$ of the scheme (HS). The multiplicity of (HS) at P can be computed locally in the chart $\{x_2\ne 0\}$ by setting $x_2=-1$. It is the multiplicity at the point (0, 1) of the affine scheme in ${\mathbb{C}}^2$ defined by the ideal $I = 〈 x_1^{a_1}-x_0^{a_1}-1, x_1^{a_2}-x_0^{a_2}-1〉$.

Write $m_{P\prime }=〈x_0,x_1-1〉$ for the maximal ideal of $P\prime =(0,1)$ in the local ring ${\mathcal{O}}_{P\prime }$ of the curve $V(x_1^{a_1}-x_0^{a_1}-1)\subset {\mathbb{C}}^2$. In ${\mathcal{O}}_{P\prime }$ we have $x_1-1=\frac{x_1^{a_1}-1}{u}=\frac{x_0^{a_1}}{u}$, where u is a unit. In fact, u is a certain product of cyclotomic polynomials in x₁. Therefore, x₀ is a uniformizer, i.e., $m_{P\prime }=〈x_0〉$, and $x_1-1$ is contained in $m_{P\prime }^{a_1}\setminus m_{P\prime }^{a_1+1}$. From this we conclude$$x_1^{a_2}-x_0^{a_2}-1 = ({((x_1-1)+1)}^{a_2}-x_0^{a_2}-1) = \sum _{i=1}^{a_2}\left(\begin{array}{c}{a}_2\\ i\end{array}\right){(x_1-1)}^i-x_0^{a_2} \in m_{P\prime }^{a_1}\setminus m_{P\prime }^{a_1+1}.$$

Hence, $x_1^{a_2}-x_0^{a_2}-1$ vanishes to order a₁ at $P\prime$. We conclude that the multiplicity of (HS) in P is a₁. Therefore, the system (2) has $a_1(a_2-1)=a_1(a_2-\gcd (a_1,a_2))$ solutions in ${\mathbb{C}}^2$.

Finally, suppose that a₁ and a₂ are not relatively prime, and set $g=\text{gcd}(a_1,a_2)$. We replace x₁, x₂ by $x_1^g,x_2^g$, and we apply our previous analysis to the two equations(5) $${\left(x_1^g\right)}^{a_1/g}+{\left(x_2^g\right)}^{a_1/g} = c_1\hspace{1em}\text{and}\hspace{1em}{\left(x_1^g\right)}^{a_2/g}+{\left(x_2^g\right)}^{a_2/g} = c_2.$$(5)

The system (5) has solutions at infinity if and only if $a_1/g$ and $a_2/g$ are both odd. In that case, we have (SI) $=\{x_1^g+x_2^g=0\}$, which defines the g points ${({\zeta }^i:1)}_{i=1,\dots ,g}$ in ${\mathbb{P}}^1$, where ζ is a primitive gth root of –1. Each of the corresponding points in (HS) has multiplicity a₁. This can be computed analogously to what we did for P in the argument above. □

We turn to n = 3, and we assume $\gcd (a_1,a_2,a_3)=1$. Our problem is now much harder. It is unknown when (SI) has any solutions in ${\mathbb{P}}^2$. No solutions means that the power sums ${\varphi }_1,{\varphi }_2,{\varphi }_3$ form a regular sequence. Conca, Krattenthaler and Watanabe [3, Conjecture 2.10] suggest that this holds if and only if $a_1{a}_2{a}_3\equiv 0 \text{mod} 6$; we call this the CKW conjecture. They prove the “only if” part in [3, Lemma 2.8]. Another proof for this part is given by the next lemma. Set ${\mathcal{A}}_p=\{a_1 \text{mod} p,a_2 \text{mod} p,a_3 \text{mod} p\}$ for p = 2, 3. Thus, ${\mathcal{A}}_2\subseteq \{0,1\}$ and ${\mathcal{A}}_3\subseteq \{0,1,2\}$. We assumed ${\mathcal{A}}_p\cancel{=}\left\{0\right\}$ for p = 2, 3. Let ζ be a primitive cube root of unity.

Lemma 11.

The points $(1:-1:0),(1:0:-1),$ and $(0:1:-1)$ are in (SI) if and only if $0\notin {\mathcal{A}}_2$, and the points $(1:\zeta :{\zeta }^2)$ and $(1:{\zeta }^2:\zeta )$ are in (SI) if and only if $0\notin {\mathcal{A}}_3$.

Proof.

If n is a prime, ξ is a primitive nth root of unity, and a is a multiple of n, then the power sum $x_1^a+x_2^a+\cdots +x_n^a$ does not vanish at $(1,\xi ,\dots ,{\xi }^{n-1})$, but rather it evaluates to n. We obtain the assertion by specializing to n = 2 and n = 3. □

The CKW conjecture states that (SI) has no solutions when $0\in {\mathcal{A}}_2\cap {\mathcal{A}}_3$. It is shown in [3, Theorem 2.11] that this holds if $\{1,n\}\subset \mathcal{A}$ with $2\le n\le 7$, or if $\{2,3\}\subset \mathcal{A}$. The proof rests on the expression of power sums in terms of elementary symmetric polynomials.

In what follows we present conjectures that imply the CKW conjecture. We begin with a converse to Lemma 11. Theorems 13 and 15 verify all conjectures for some new cases.

Conjecture 12. We have $(\text{SI})\subseteq \{(1\mathrm{}:\mathrm{}-1:0),(1:0:\mathrm{}-1),(0:1:\mathrm{}-1),(1\mathrm{}:\mathrm{}\zeta \mathrm{}:\mathrm{}{\zeta }^2),(1\mathrm{}:\mathrm{}{\zeta }^2\mathrm{}:\mathrm{}\zeta )\}$.

This generalizes [3, Conjecture 2.10] since the five possibilities for points on (SI) do not occur if $0\in {\mathcal{A}}_2\cap {\mathcal{A}}_3$. We show some new cases of the conjecture using computational tools.

Theorem 13.

Conjecture 12 holds for all $a_1<a_2<a_3$ with $a_1+a_2+a_3\le 300$.

Proof.

Let $P\prime =(\alpha :\beta :\gamma )$ be a point on (SI), corresponding to $P=(\alpha :\beta :\gamma :0)$ on (HS). After permuting coordinates, we may assume $\alpha \ne 0$. Then $P\prime$ is in the affine chart ${\mathbb{C}}^2$ of ${\mathbb{P}}^2$ given by $x=x_2/x_1$ and $y=x_3/x_1$. The restriction of (SI) to that plane ${\mathbb{C}}^2$ is defined by(6) $$x^{a_1}+y^{a_1}+1 = x^{a_2}+y^{a_2}+1 = x^{a_3}+y^{a_3}+1 = 0.$$(6)

Conjecture 12 states that the number of solutions to the system (6) is 0, 2 or 4, as follows:

Table

${\mathcal{A}}_2$ and ${\mathcal{A}}_3$	Number of solutions to (6)	Possibilities for $P\prime$ in Conjecture 12
$0\in {\mathcal{A}}_2,0\in {\mathcal{A}}_3$	0	–
$0\notin {\mathcal{A}}_2,0\in {\mathcal{A}}_3$	2	$(1:-1:0),(1:0:-1)$
$0\in {\mathcal{A}}_2,0\notin {\mathcal{A}}_3$	2	$(1:\zeta :{\zeta }^2),(1:{\zeta }^2:\zeta )$
$0\notin {\mathcal{A}}_2,0\notin {\mathcal{A}}_3$	4	$(1\mathrm{}:\mathrm{}-1\mathrm{}:\mathrm{}0),(1\mathrm{}:\mathrm{}0\mathrm{}:\mathrm{}-1)$, $(1\mathrm{}:\mathrm{}\zeta \mathrm{}:\mathrm{}{\zeta }^2),(1\mathrm{}:\mathrm{}{\zeta }^2\mathrm{}:\mathrm{}\zeta )$

We verified the counts in the second column for all $a_1<a_2<a_3$ with $a_1+a_2+a_3\le 300$. We did this using the Gröbner basis implementation in the computer algebra system magma. The same would be doable with other tools for bivariate equations. □

Conjecture 14. For n = 3 and $\text{gcd}(a_1,a_2,a_3)=1$, the following holds for the system (2):

If $0\in {\mathcal{A}}_3$, then we have $\hspace{1em}\#\text{Solutions} = \{\begin{array}{cc}{a}_1{a}_2{a}_3\hfill & \mathrm{ }\text{if}\mathrm{ }{\mathcal{A}}_2=\{1,0\};\hfill \\ a_1{a}_2{a}_3-3a_1{a}_2\hfill & \mathrm{ }\text{if}\mathrm{ }{\mathcal{A}}_2=\left\{1\right\}.\hfill \end{array}$

If ${\mathcal{A}}_3=\left\{1\right\}$ or {2}, then we have $\#\text{Solutions} = \{\begin{array}{cc}{a}_1{a}_2{a}_3-4a_1\hfill & \mathrm{ }\text{if}\mathrm{ }{\mathcal{A}}_2=\{1,0\};\hfill \\ a_1{a}_2{a}_3-4a_1-3a_1{a}_2\hfill & \mathrm{ }\text{if}\mathrm{ }{\mathcal{A}}_2=\left\{1\right\}.\hfill \end{array}$

If ${\mathcal{A}}_3=\{1,2\}$, then we have $\#\text{Solutions} = \{\begin{array}{cc}{a}_1{a}_2{a}_3-2i_{\mathcal{A}}\hfill & \mathrm{ }\text{if}\mathrm{ }{\mathcal{A}}_2=\{1,0\};\hfill \\ a_1{a}_2{a}_3-2i_{\mathcal{A}}-3a_1{a}_2\hfill & \mathrm{ }\text{if}\mathrm{ }{\mathcal{A}}_2=\left\{1\right\}.\hfill \end{array}$

Here $i_{\mathcal{A}}$ is the index of nilpotency of the zero-divisor x₀ in the homogeneous system (HS).

At present we do not have a simple formula for the number $i_{\mathcal{A}}$ in all cases. Computationally, it can be found from the homogeneous ideal $I=〈f_1,f_2,f_3〉$ that is generated by $f_j=x_1^{a_j}+x_2^{a_j}+x_3^{a_j}-c_j{x}_0^{a_j}$ for j = 1, 2, 3. Using ideal quotients, the definition is as follows:$$(I:x_0^{i_{\mathcal{A}}-1}) ⊊ (I:x_0^{i_{\mathcal{A}}}) = (I:x_0^{i_{\mathcal{A}}+1}).$$

From our computations it seems that $i_{\mathcal{A}}$ is always either a₁ or a₂ or $2a_1$.

Theorem 15.

Conjecture 14 holds for all $a_1<a_2<a_3$ with $a_3\le 20$ or $a_1+a_2+a_3\le 40$.

Proof.

Our approach is to compute the multiplicity in (HS) for each point that is known (by Theorem 13) to lie in (SI). We conjecture that these multiplicities are as follows:

1. If ${\mathcal{A}}_2=\left\{1\right\}$, then the point $(1:-1:0:0)$ has multiplicity $a_1{a}_2$ in (HS);

2. if ${\mathcal{A}}_3=\{1,2\}$, then the point $(1:\zeta :{\zeta }^2:0)$ has multiplicity $i_{\mathcal{A}}$ in (HS);

3. if $\left|{\mathcal{A}}_3\right|=1$, then $2i_{\mathcal{A}}=2a_1$ and this is the multiplicity of $(1:\zeta :{\zeta }^2:0)$ in (HS).

These claims imply Conjecture 14, by our previous analysis. Indeed, if $0\in {\mathcal{A}}_2\cap {\mathcal{A}}_3$, then (SI) is empty and the number of solutions to (2) is the Bézout number $a_1{a}_2{a}_3$. Otherwise, we need to subtract the multiplicities above, according to the various cases. Here the number in (i) is multiplied by 3 since the S₃-orbit of $(1:-1:0:0)$ has three points, and the numbers in (ii) and (iii) are multiplied by 2 since the S₃-orbit of $(1:\zeta :{\zeta }^2:0)$ has two points.

For our computations, we fix $P\in \{(1:-1:0:0),(1:\zeta :{\zeta }^2:0)\}$, we focus on the affine chart ${\mathbb{C}}^3=\{x_1=1\}$, and we consider the ideal $I=〈f_1,f_2,f_3〉$ in the local ring ${\mathcal{O}}_{P,{\mathbb{C}}^3}$. The quotient $V={\mathcal{O}}_{P,{\mathbb{A}}^3}/I$ is a vector space over $\mathbb{C}$, and its dimension is the multiplicity of (HS) at P. We computed this dimension for all values of $a_1,a_2,a_3$ in the stated range, and we verified that (i), (ii), and (iii) are satisfied. This was done using Gröbner bases in magma. □

Extending Conjecture 14 to $n\ge 4$ seems out of reach at the moment, for two reasons. First of all, the conditions on $\mathcal{A}$ for (SI) to have no solutions are less simple. For n = 4 with $\text{gcd}(a_1,a_2,a_3,a_4)=1$, Conca, Krattenthaler and Watanabe [3, Conjecture 2.15] state three conditions on $\mathcal{A}$ under which (SI) has no solutions. They show that all three conditions are necessary. We verified their conjecture using Gröbner bases in magma for $a_1+a_2+a_3+a_4\le 100$. Secondly, in the event that (SI) does have solutions, it is not at all obvious what these should be. In general, they are not given only by points whose coordinates are roots of unity, as was the case for n = 3. This happens already for n = 4 as the following example shows:

Example 16.

Set n = 4 and $\mathcal{A}=\{2,4,9,10\}.$ The system (2) has 576 solutions which is 144 less than the Bézout number 720. The scheme (SI) in ${\mathbb{P}}^3$ which is defined by the ideal $〈x_1^2+x_2^2+x_3^2+x_4^2,x_1^4+x_2^4+x_3^4+x_4^4,x_1^9+x_2^9+x_3^9+x_4^9,x_1^{10}+x_2^{10}+x_3^{10}+x_4^{10}〉$ contains 72 distinct points. The minimal polynomial of each of the coordinates of the points in (SI) has degree 36. Every root of this polynomial occurs in each coordinate in exactly two points.

4 Images

We now study the images of the power sum maps ${\varphi }_{\mathcal{A},\mathbb{C}}$, ${\varphi }_{\mathcal{A},\mathbb{R}}$, and ${\varphi }_{\mathcal{A},\ge 0}$. The recovery problem (2) has a solution if and only if the measurement vector c lies in that image. We know from Chevalley’s Theorem [10, Theorem 4.19] that $\text{im}({\varphi }_{\mathcal{A},\mathbb{C}})$ is a constructible subset of ${\mathbb{C}}^m$. Over the real numbers, the Tarski-Seidenberg Theorem [10, Theorem 4.17] tells us that $\text{im}({\varphi }_{\mathcal{A},\mathbb{R}})$ is a semialgebraic subset of ${\mathbb{R}}^m$ and $\text{im}({\varphi }_{\mathcal{A},\ge 0})$ is a semialgebraic subset of ${\mathbb{R}}_{\ge 0}^m$. It follows from Proposition 3 that, for each of these images, the dimension equals $\text{min}(n,m)$.

We first examine whether the images are closed. We use the classical topology on ${\mathbb{R}}^m$ or ${\mathbb{C}}^m$. This makes sense not just over $\mathbb{R}$, but also over $\mathbb{C}$, since the Zariski closure of the image of any complex polynomial map coincides with its classical closure [10, Corollary 4.20].

Proposition 17.

The constructible set $\text{im}({\varphi }_{\mathcal{A},\mathbb{C}})$ is generally not closed in ${\mathbb{C}}^m$. The semialgebraic set $\text{im}({\varphi }_{\mathcal{A},\mathbb{R}})$ is closed in ${\mathbb{R}}^m$ when $0\in {\mathcal{A}}_2$, but it is generally not closed otherwise. Finally, the semialgebraic set $\text{im}({\varphi }_{\mathcal{A},\ge 0})$ is always closed in ${\mathbb{R}}_{\ge 0}^m$.

Proof.

Let $m=n=2,a_1=1$ and $a_2\ge 3$ odd. Fix any $c=(c_1,c_2)\in {\mathbb{C}}^2$, with $c_1=0$ and $c_2\cancel{=}0$. Then (2) has no complex solution because ${\varphi }_1(x)$ divides ${\varphi }_2(x)$. Thus, c does not belong to the image of ${\varphi }_{\mathcal{A},\mathbb{C}}$ or ${\varphi }_{\mathcal{A},\mathbb{R}}$. However, c is in the closure of $\text{im}({\varphi }_{\mathcal{A},\mathbb{C}})$ because that closure is ${\mathbb{C}}^2$ by Proposition 3 (i). The same counterexample works over the real numbers. Let us now set $c_1=ϵ$ for $ϵ>0$ very small and solve ${\varphi }_1(x)=ϵ$ by setting $x_2=ϵ-x_1$. This substitution in ${\varphi }_2(x)=c_2$ gives a polynomial equation in one variable x₁ of odd degree a₂. Such an equation always has a real solution $x_1(ϵ)$. The image of the point $(x_1(ϵ),ϵ-x_1(ϵ))$ converges to c in ${\mathbb{R}}^2$ as $ϵ\to 0$ from which we conclude that c lies in the closure of $\text{im}({\varphi }_{\mathcal{A},\mathbb{R}})$.

We are left with the cases where the image is closed. First suppose $0\in {\mathcal{A}}_2$. Then there is an even element in $\mathcal{A}$, say a_i. Let $c\in {\mathbb{R}}^m$ be in the closure of $\text{im}({\varphi }_{\mathcal{A},\mathbb{R}})$. There exists a sequence ${\left\{x^{(\mathcal{l})}\right\}}_{\mathcal{l}\ge 0}$ of points in ${\mathbb{R}}^n$ such that ${\varphi }_{\mathcal{A},\mathbb{R}}(x^{(\mathcal{l})})$ converges to c as $\mathcal{l}\to \infty$. Since a_i is even, we have ${\varphi }_i(x^{(\mathcal{l})})=\left|\right|x^{(\mathcal{l})}|{|}_{a_i}^{a_i}$, which converges to $c_i\ge 0$ as $\mathcal{l}\to \infty$. Hence, the sequence ${\left\{x^{(\mathcal{l})}\right\}}_{\mathcal{l}\ge 0}$ is bounded in the norm $\left|\right|·|{|}_{a_i}$. There is a subsequence that converges to some point $x^{(\infty )}$ in ${\mathbb{R}}^n$. Since the power sum map ${\varphi }_{\mathcal{A},\mathbb{R}}$ is continuous, the image of $x^{(\infty )}$ is equal to c. Therefore, $c\in \text{im}({\varphi }_{\mathcal{A},\mathbb{R}})$, and we conclude that the real image is closed. Finally, take $\mathcal{A}$ arbitrary and consider the nonnegative power map ${\varphi }_{\mathcal{A},\ge 0}$. Let $c\in {\mathbb{R}}_{\ge 0}^m$ be in the closure of $\text{im}({\varphi }_{\mathcal{A},\ge 0})$ and let ${\left\{x^{(\mathcal{l})}\right\}}_{\mathcal{l}\ge 0}$ be a sequence of nonnegative points whose images ${\varphi }_{\mathcal{A},\ge 0}(x^{(\mathcal{l})})$ converge to c as $\mathcal{l}\to \infty$. Now, for any index i, the norm $\left|\right|x^{(\mathcal{l})}|{|}_{a_i}={\varphi }_i{(x^{(\mathcal{l})})}^{1/a_i}$ is bounded, so there exists a convergent subsequence of ${\left\{x^{(\mathcal{l})}\right\}}_{\mathcal{l}\ge 0}$. Let $x^{(\infty )}\in {\mathbb{R}}_{\ge 0}^n$ be its limit. Again, by the continuity of the power map, we have ${\varphi }_{\mathcal{A},\ge 0}(x^{(\infty )})=c$. From this we conclude that $\text{im}({\varphi }_{\mathcal{A},\ge 0})$ is closed. □

Example 18.

Set $n=m=2$ and $\mathcal{A}=\{1,3\}$. The image of ${\varphi }_{\mathcal{A},\mathbb{R}}$ is the nonclosed set$$\{(0,0)\} \cup \{ c\in {\mathbb{R}}^2 : (c_1<0 \text{and} c_1^3\ge 4c_2) \text{or} (c_1>0 \text{and} c_1^3\le 4c_2) \}.$$

On the other hand, the image of the map restricted to the nonnegative orthant is closed:(7) $$\text{im}({\varphi }_{\mathcal{A},\ge 0}) = \{ c\in {\mathbb{R}}_{\ge 0}^2 : c_2\le c_1^3\le 4c_2 \}.$$(7)

In Section 5 we generalize this description of the image of ${\varphi }_{\mathcal{A},\ge 0}$ to other power sum maps.

We next examine our images through the lens of algebraic geometry. Let $c_1,\dots ,c_m$ be variables with $\text{degree}(c_i)=a_i$. These are coordinates on the weighted projective space $\mathbb{W}{\mathbb{P}}^{m-1}$ with weights given by $\mathcal{A}$. We regard $\varphi ={\varphi }_{\mathcal{A},\mathbb{C}}$ as a rational map from ${\mathbb{P}}^{n-1}$ to $\mathbb{W}{\mathbb{P}}^{m-1}$. The following features of the image will be characterized in Theorem 21: (i) For $m=n+1$, the closure of the image $\text{im}(\varphi )$ is an irreducible hypersurface in $\mathbb{W}{\mathbb{P}}^{m-1}$. We give a formula for its degree, which is the weighted degree of its defining polynomial in the unknowns $c_1,\dots ,c_m$. (ii) For $m\le n$, we describe the positive branch locus of the map $\varphi$. This is a hypersurface in ${\mathbb{C}}^m$. By reasoning as in the proof of [8, Theorem 3.13], this hypersurface represents the algebraic boundary of the image of ${\varphi }_{\mathcal{A},\ge 0}$.

To study the branch locus of $\varphi$, we start with the ramification locus $\mathcal{R}$. This consists of points in ${\mathbb{C}}^n$ where $\varphi$ is not smooth [2, Section 2.2, Proposition 8]. Set ${\varphi }_j={\sum }_{i=1}^n{x}_i^{a_j}$ and $\mu =\min \{n,m\}$. Let $I\subset \mathbb{C}[x_1,\dots ,x_n]$ be the ideal generated by the $\mu \times \mu$ minors of the Jacobian matrix $\mathcal{I}$ as in (4); this is an ideal of height $\le |m-n|+1$. Its variety $\mathcal{R}=V(I)$ is the set of points where $\mathcal{I}$ has rank less than μ. Each maximal minor of $\mathcal{I}$, up to multiplication with a positive integer, has the form(8) $${\left(x_{i_1}{x}_{i_2}\dots x_{i_{\mu }}\right)}^{a_{i_1}-1}·\mathrm{}\mathrm{}\prod _{1\le j<k\le \mu }\text{}(x_{i_j}-x_{i_k}) · S\left(x_{i_1},x_{i_2},\dots ,x_{i_{\mu }}\right),$$(8) for some $1\le i_1<\cdots <i_{\mu }\le n$. The last factor is a Schur polynomial.

In the square case m = n, the variety $\mathcal{R}$ is a reducible hypersurface in ${\mathbb{C}}^n$, given by the vanishing of one polynomial (8). Write $g=\text{gcd}(a_1-1,\dots ,a_m-1)$. By [4, Theorem 3.1], the Schur polynomial S is either constant, which happens when $(a_i-1)/g=i-1$ for $1\le i\le n$, or it is irreducible. Let $\mathcal{R}\prime$ be the closure in ${\mathbb{C}}^n$ of $\mathcal{R}\setminus ({\cup }_{i\ne j}V(x_i-x_j)\cup V(x_k))$. Thus, $\mathcal{R}\prime$ is the nontrivial component in the ramification locus. Our discussion implies the following:

Proposition 19.

Assume m = n. The ramification variety $\mathcal{R}\prime$ is either empty, in which case we have $(a_i-1)/g=i-1$ for $1\le i\le n$, or it is an irreducible hypersurface of degree $$\sum _{i=1}^n(a_i-1)-\left(\begin{array}{c}n\\ 2\end{array}\right)-n(a_1-1).$$

Example 20.

For $\mathcal{A}=\{3,6,7\}$ and n = 3, the ideal I is principal. Its generator factors as$$x_1^2{x}_2^2{x}_3^2(x_1-x_2)(x_1-x_3)(x_2-x_3)(x_1^2{x}_2^2+x_1^2{x}_2{x}_3+x_1{x}_2^2{x}_3+x_1^2{x}_3^2+x_1{x}_2{x}_3^2+x_2^2{x}_3^2).$$

The variety $\mathcal{R}\prime$ is the quartic surface in ${\mathbb{C}}^3$ defined by the Schur polynomial in the last factor.

In the overdetermined regime (m > n), there are partial results by Fröberg and Shapiro [5], who study the closure of $\mathcal{R}\setminus ({\cup }_{i\ne j}V(x_i-x_j))$ in ${\mathbb{C}}^n$ which we denote by $\mathcal{R}″$. Notably, it remains an open problem to find the dimension of $\mathcal{R}″$. Assuming $a_1=g=1$, the first interesting case is n = 3, m = 5. Proving the dimension of $\mathcal{R}″$ to be the expected one is equivalent to showing that three complete homogeneous polynomials form a regular sequence. This brings us back to Conca, Krattenthaler and Watanabe [3, Conjecture 2.17].

Now assume $m\le n$. Then $\mathcal{R}$ contains all linear spaces defined by $n-m+1$ independent equations of the form x_i = x_j or x_k = 0. We call these positive ramification components. This name is justified as follows. The Schur polynomial S in (8) has positive coefficients, and therefore cannot vanish at nonzero points in the nonnegative orthant ${\mathbb{R}}_{\ge 0}^n$. Hence, only these components contribute to the ramification locus of the positive map ${\varphi }_{\mathcal{A},\ge 0}$. A positive branch hypersurface is any irreducible hypersurface in weighted projective space in $\mathbb{W}{\mathbb{P}}^{m-1}$ that is the closure of the image of a positive ramification component under the power sum map $\varphi$.

Theorem 21.

The following hypersurfaces in $\mathbb{W}{\mathbb{P}}^{m-1}$ are relevant for the image of our map.

1. If $m=n+1$, then the image of $\varphi$ is an irreducible hypersurface in $\mathbb{W}{\mathbb{P}}^{m-1}$ whose weighted degree is at most $(a_1{a}_2\dots a_m)/(m-1)!$. If this ratio is an integer, then this bound can be attained. Specifically, if m = 3 and $a_1{a}_2{a}_3$ is even, then it can be attained.

2. If $m\le n$, then the weighted degree of any positive branch hypersurface of $\varphi$ is at most the Bézout number $a_1{a}_2\dots a_m$.

Proof.

Let $m\le n$. The restriction of $\varphi$ to any positive ramification component is a rational map from ${\mathbb{P}}^{m-2}$ to $\mathbb{W}{\mathbb{P}}^{m-1}$. After renaming the x_i if needed, we can write its coordinates as(9) $$\sum _{i=1}^{m-1}{\tau }_i{x}_i^{a_j}\text{\hspace{1em}\hspace{1em} for}\mathrm{ }j=1,\dots ,m,$$(9) where ${\tau }_1,\dots ,{\tau }_{m-1}$ are positive integers. Let $H_{\tau }$ denote the image of this map in $\mathbb{W}{\mathbb{P}}^{m-1}$. This also covers the case $m=n+1$ in (i) since $\varphi$ has coordinates as in (9) with ${\tau }_1=\cdots ={\tau }_{m-1}=1$. Hence, all hypersurfaces in (i) and (ii) have the form $H_{\tau }$. Our aim is to compute their degrees.

Fix positive integers ${\tau }_1,\dots ,{\tau }_{m-1}$ and set $z_j=c_j^{1/a_j}$. Consider the projective space ${\mathbb{P}}^{2m-2}$ with coordinates $x_1,\dots ,x_{m-1},z_1,\dots ,z_m$. Let Z denote the variety in ${\mathbb{P}}^{2m-2}$ defined by the homogeneous polynomials ${\sum }_{i=1}^{m-1}{\tau }_i{x}_i^{a_j}-z_j^{a_j}$, for $j=1,\dots ,m$. By the same reasoning as in Proposition 3, this variety is irreducible and it is a complete intersection of degree $a_1{a}_2\dots a_m$.

We consider the image of Z under the coordinate projection(10) $$\pi :{\mathbb{P}}^{2m-2}\mathrm{ }--\to {\mathbb{P}}^{m-1}, (x_1:\cdots :x_{m-1}:z_1:\cdots :z_m)\mapsto (z_1:\cdots :z_m).$$(10)

The closure of $\pi (Z)$ is essentially the hypersurface $H_{\tau }$ we care about, but it lives in ${\mathbb{P}}^{m-1}$. Its degree in ${\mathbb{P}}^{m-1}$ with coordinates $(z_1:\cdots :z_m)$ coincides with the degree of $H_{\tau }$ in $\mathbb{W}{\mathbb{P}}^{m-1}$ with coordinates $(c_1:\cdots :c_m)$. Indeed, these two hypersurfaces have the same defining polynomial, up to the substitution $c_j=z_j^{a_j}$. The Refined Bézout Theorem [6, 12.3] implies(11) $$\mathrm{deg}(\pi (Z)) \le \frac{\mathrm{deg}(Z)}{\mathrm{deg}(\pi {|}_Z)} = \frac{a_1{a}_2\dots a_m}{\mathrm{deg}(\pi {|}_Z)},$$(11) where equality holds if π has no base locus. This immediately proves (ii).

We proceed with proving (i). The degree of $\pi {|}_Z$ is the size of its generic fiber. This equals the size of the generic fiber of the map given by (10). Conjecture 7 states that the size of the generic fiber of π is the size of the stabilizer of $\tau =({\tau }_1,\dots ,{\tau }_{m-1})$ in the symmetric group $S_{m-1}$. In particular, it would follow that the generic fiber is a single point if and only if the τ_i are all distinct, and it consists of $(m-1)!$ points if and only if the τ_i are identical. We do not know yet whether this conjecture holds. But, in any case, the number $|\text{Stab}(\tau )|$ furnishes a lower bound for the size of a generic fiber and thus for $\mathrm{deg}(\pi )$.

Since the hypersurface $\text{im}(\varphi )$ in (i) equals $H_{\tau }$ for ${\tau }_1=\cdots ={\tau }_{m-1}=1$Z${\tau }_1=\cdots ={\tau }_{m-1}=1$, we conclude from (11) that its weighted degree is at most $(a_1{a}_2\dots a_m)/(m-1)!$. Equality can only hold when the base locus of π on the variety $V({\varphi }_j(x)-z_j^{a_j} : j=1,\dots ,m)$ is empty. This happens precisely when the system at infinity (SI) is the empty set. A necessary condition for this to happen is that $(m-1)!$ divides the Bézout number $a_1{a}_2\dots a_m$. One checks that this is also sufficient when m = 3: we saw in Proposition 10, that (SI) is empty when $a_1{a}_2$ is even. □

Example 22

(m = 3). Suppose $\text{gcd}(a_1,a_2,a_3)=1$ and $B=a_1{a}_2{a}_3$ is even. If n = 2, then the image of $\varphi$ is a curve of expected degree $B/2$ in $\mathbb{W}{\mathbb{P}}^2$. If $n\ge 3$, then every positive branch curve has expected degree $B/2$ or B. For instance, if n = 4, then the ramification component $\{x_1=0,x_3=x_4\}$ should give a branch curve of degree B, while $\{x_1=x_2,x_3=x_4\}$ should give a branch curve of degree $B/2$. We shall see pictures of such curves in the next section.

Example 23

(m = 4). If n = 3 and 6 divides $B=a_1{a}_2{a}_3{a}_4$, then we expect the image of $\varphi$ to have weighted degree $B/6$. This would follow from the conjectures in Sections 2 and 3. The positive branch surfaces for $n\ge 4$ should have degrees $B/6,B/2$ or B. If 6 does not divide B, then the weighted degrees of the image and branch surfaces in $\mathbb{W}{\mathbb{P}}^3$ are determined by the base loci. This takes us back to Conjecture 14. To be very explicit, let $\mathcal{A}=\{2,5,7,8\}$ as in Example 1. Here $B/6=560/6=93.333\dots$. The image of our map $\varphi :{\mathbb{P}}^2--\to \mathbb{W}{\mathbb{P}}^3$ is defined by a homogeneous polynomial of weighted degree 90 with 304 terms, namely$$9c_1^{45}-1050c_1^{41}{c}_4-3724c_1^{40}{c}_2^2+22400c_1^{39}{c}_2{c}_3-31000c_1^{38}{c}_3^2+\cdots -1966899200c_1{c}_4^{11}+1258815488c_2^2{c}_4^{10}.$$

By contrast, consider $\mathcal{A}=\{2,5,7,9\}$. Now, $B/6=105$ is an integer, and this equals the weighted degree of the image surface. Its defining polynomial has 388 terms, and it looks like$$59049c_1^{35}{c}_2^7-459270c_1^{34}{c}_2^6{c}_3-59049c_1^{35}{c}_3^5+255150c_1^{33}{c}_2^6{c}_4+\cdots +6350400c_2{c}_3^4{c}_4^8-324000c_3^6{c}_4^7.$$

5 Recovery from p-norms

Focusing on the positive region, we now investigate the properties of the map ${\varphi }_{\mathcal{A},\ge 0}$. The key fact to be used throughout is that the power sum of degree p represents the p-norm:(12) $$\left|\right|x|{|}_p = {( \sum _{i=1}^n{x}_i^p )}^{\mathrm{}1/p} \text{for} \text{all} x=(x_1,\dots ,x_n)\in {\mathbb{R}}_{\ge 0}^n.$$(12)

Hence, our recovery problem for nonnegative vectors $x\in {\mathbb{R}}_{\ge 0}^n$ is equivalent to recovery of x from values of the p-norms $\left|\right|·|{|}_p$, where p runs over a prespecified set $\mathcal{A}$ of positive integers. We are interested in existence and uniqueness of vectors with given p-norms for $p\in \mathcal{A}$.

Let us begin with the basic identifiability question: How many different p-norms are needed to reconstruct a vector in ${\mathbb{R}}_{\ge 0}^n$ from their values up to permuting the n coordinates? Conjecture 6 together with (12) would imply that n + 1 different norms suffice. On the other hand, it follows from Proposition 3 that at least n different p-norms are necessary. But are these n measurements already sufficient? We start by showing that this is indeed the case.

Proposition 24.

For m = n, recovery from p-norms is always unique. Given any set $\mathcal{A}$ of n positive integers, the map ${\varphi }_{\mathcal{A},\ge 0}:{\mathbb{R}}_{\ge 0}^n\to {\mathbb{R}}_{\ge 0}^n$ is injective up to permuting coordinates.

Proof.

Write $\varphi ={\varphi }_{\mathcal{A},\ge 0}$. We proceed by induction on n. For n = 1, the map $\varphi$ is obviously injective as it is strictly increasing. Thus, we have unique recovery for n = 1. Let us now prove the statement for arbitrary n. Our argument is based on the calculus fact that a differentiable function from a real interval to $\mathbb{R}$ is injective if its derivative has constant sign.

Consider the cone of decreasing vectors, $C=\{x\in {\mathbb{R}}^n:x_1>x_2>\cdots >x_n\ge 0\}$. Let X₁, X₂ be two arbitrary distinct points from this cone. Our claim states that they map to two different points under the map $\varphi$, i.e., that $\varphi$ is injective on C. Let L be the line segment from X₁ to X₂ and consider the restriction $\varphi {|}_L:\mathbb{R}\to {\mathbb{R}}^n$ of $\varphi$ to L that is now a function in one variable. Its derivative is given by the product of the Jacobian matrix of $\varphi$, which we denote by ${\mathcal{I}}_{\varphi }$, evaluated at L, and the vector $(X_2-X_1)$. First notice that if $X_{1,n}=X_{2,n}=0$, then we are in the case where the induction hypothesis applies. Let us now w.l.o.g. assume $X_{2,n}>0$. Then ${\mathcal{I}}_{\varphi }$ is an n × n matrix whose determinant is of the form (8).

The Schur polynomial S does not vanish on $\mathit{L\setminus }\left\{X_1\right\}$, and neither do the linear factors. Hence, the coordinates of the vector ${\mathcal{I}}_{\varphi }·(X_2-X_1)$ do not vanish at any point on $\mathit{L\setminus }\left\{X_1\right\}$. Each coordinate is a function of constant sign on the whole segment L. This shows that $\varphi$ is injective on the line L. As X₁ and X₂ were chosen to be arbitrary points, we conclude that $\varphi$ is injective on the whole cone C. For a much more general version of this argument, we refer to the equivalence of conditions (inj) and (jac) in [12, Theorem 1.4]. □

The proof above is not algorithmic. It does not tell us how to invert $\varphi$. Our current method of choice for recovery is solving the equations using numerical algebraic geometry.

The next goal is to characterize the semialgebraic set $\text{im}({\varphi }_{\mathcal{A},\ge 0})$ inside the nonnegative orthant ${\mathbb{R}}_{\ge 0}^m$. Starting with m = 2, we first present a generalization of the formula (7).

Proposition 25.

Set $m=2\le n$ and $\mathcal{A}=\{a_1<a_2\}$. Then the nonnegative image equals (13) $$\text{im}({\varphi }_{\mathcal{A},\ge 0}) = \{ c\in {\mathbb{R}}_{\ge 0}^2 : c_2^{a_1} \le c_1^{a_2} \le n^{a_2-a_1}{c}_2^{a_1} \}.$$(13)

Proof.

At any point $x\in {\mathbb{R}}_{\ge 0}^n$, our map evaluates the norms $\left|\right|x|{|}_{a_j}={\varphi }_j{(x)}^{1/a_j}$ for i = 1, 2. The first norm is larger than or equal to the second one: $\left|\right|x|{|}_{a_1}\ge |\left|x\right|{|}_{a_2}$. They agree at coordinate points. Their ratio is maximal at $e=(1,1,\dots ,1)$. This gives the inequalities$$1 \le \frac{\left|\right|x|{|}_{a_1}}{\left|\right|x|{|}_{a_2}} \le \frac{\left|\right|e|{|}_{a_1}}{\left|\right|e|{|}_{a_2}} = \frac{n^{1/a_1}}{n^{1/a_2}}.$$

All values in this range are obtained by some point $x\in {\mathbb{R}}_{\ge 0}^n$. We now raise both sides to the power $a_1{a}_2$ and thereafter we clear denominators. This gives the inequalities in (13). □

The proof of Proposition 25 suggests that the study of the nonnegative image $\text{im}({\varphi }_{\mathcal{A},\ge 0})$ can be simplified by replacing the power sum map by the normalized map into the simplex(14) $${\psi }_{\mathcal{A}} : {\mathbb{R}}_{\ge 0}^n --\to {\Delta }_{m-1} : x \mapsto \frac{1}{\sum _{j=1}^m\left|\right|x|{|}_{a_j}}·( |\left|x\right|{|}_{a_1},\left|\right|x|{|}_{a_2},\dots ,|\left|x\right|{|}_{a_m}).$$(14)

Here, ${\Delta }_{m-1}=\{u\in {\mathbb{R}}_{\ge 0}^m : u_1+u_2+\cdots +u_m=1\}$ is the standard probability simplex. If we know the image of this map then that of the power sum map can be recovered as follows:(15) $$\text{im}({\varphi }_{\mathcal{A},\ge 0}) = \{ c\in {\mathbb{R}}_{\ge 0}^m : \frac{1}{\sum _{j=1}^m{c}_j^{1/a_j}}( c_1^{1/a_1}, c_2^{1/a_2},\dots , c_m^{1/a_m} ) \in \text{im}({\psi }_{\mathcal{A}}) \}.$$(15)

We next consider the case m = 3. For every $n\ge 3$, the image is a nonconvex region in the triangle ${\Delta }_2$. These regions get larger as n increases. We illustrate this for an example.

Example 26.

Set $\mathcal{A}=\{2,3,4\}$. For $n\ge 3$, the image of the norm map ${\psi }_{\mathcal{A}}$ into the triangle ${\Delta }_2$ is an n-gon with curvy boundary edges that lies inside the subtriangle $\{c_1>c_2>c_3\}$. The edges and diagonals of this n-gon are the following $(\begin{array}{c}n\\ 2\end{array})$ curvy segments for $1\le i<j\le n$:$$B_{ij} = {\psi }_{\mathcal{A}}(\{x\in {\mathbb{R}}_{\ge 0}^n : x_1=\cdots =x_i\ge x_{i+1}=\cdots =x_j,\mathrm{ }\text{and}\mathrm{ }{x}_k=0\mathrm{ }\text{for}\mathrm{ }k>j\}).$$

The Zariski closure of B_ij is an irreducible curve. There are $\lfloor n/2\rfloor$ distinct sets B_ij with i = j. For $i\ne j$, the Zariski closures of B_ij and $B_{j-i,j}$ are the same. Hence, we obtain$$\frac{\left(\begin{array}{c}n\\ 2\end{array}\right)-\lfloor \frac{n}{2}\rfloor }{2}+\lfloor \frac{n}{2}\rfloor = \lfloor \frac{n^2}{4}\rfloor$$distinct complex algebraic curves as Zariski closures of these curvy segments.

For n = 3, there are two distinct branch curves: one curve of degree 12, given by the segment B₁₂, and one of degree 24, given by the two segments B₁₃ and B₂₃. For n = 6, Figure 1 shows the curvy hexagon $\text{im}({\psi }_{\mathcal{A}})$. Its 15 curvy segments form nine distinct branch curves, six of degree 24 and three of degree 12. The latter are given by $B_{12},B_{24},B_{36}$. The curvy segment B₁₂ is red in both pictures. For n = 2, we have $B_{12}=\text{im}({\psi }_{\mathcal{A}})$. For $n\ge 3$, the curvy segment B₁₂ is one of the n boundary edges of $\text{im}({\psi }_{\mathcal{A}})$. The Zariski closure of the curvy segment B₁₂ is the branch curve $\{c_1^{12}-4c_1^6{c}_2^6-4c_2^{12}+12c_1^2{c}_2^6{c}_3^4-3c_1^4{c}_2^8-2c_3^{12}=0\}$.

Fig. 1 The image of the norm map ${\psi }_{\mathcal{A}}$ for $n=6,m=3$ is a curvy hexagon in a triangle. The color coding on the left shows the progression of images for $n=3,4,5,6$. The color coding on the right shows the algebraic degrees 12 (red) and 24 (blue) of the curvy segments.

We now state a theorem which generalizes our observations in Example 26 to $m\ge 4$. We fix $n\ge m$ and $\mathcal{A}=\{a_1<\cdots <a_m\}$ as before. For $1\le \mathcal{l}\le m$ and any ordered set $\nu =({\nu }_1,\dots ,{\nu }_{\mathcal{l}})\in (\begin{array}{c}[n]\\ \mathcal{l}\end{array})$, let $R_{\nu }$ denote the set of vectors $x\in {\mathbb{R}}_{\ge 0}^n$ that satisfy $x_i=x_{i+1}$ if $i<{\nu }_1$ or ${\nu }_r\le i<{\nu }_{r+1}$ for some r, and x_i = 0 for all $i>{\nu }_{\mathcal{l}}$, and $x_i\ge x_{i+1}$ otherwise. Its image $B_{\nu }={\psi }_{\mathcal{A}}(R_{\nu })$ is a semialgebraic subset of dimension $\mathcal{l}-1$ in ${\Delta }_{m-1}$. Proposition 25 tells us that $B_{\nu }$ is a curvy simplex with vertices $B_{{\nu }_1},\dots ,B_{{\nu }_{\mathcal{l}}}$. We define the type of ν to be the multiset $\{{\nu }_1,{\nu }_2-{\nu }_1,{\nu }_3-{\nu }_2,\dots ,{\nu }_{\mathcal{l}}-{\nu }_{\mathcal{l}-1}\}$. We can view $\tau =\text{type}(\nu )$ as a partition with precisely $\mathcal{l}$ parts of an integer between $\mathcal{l}$ and n. Let $T_{n,\mathcal{l}}$ denote the set of such partitions τ. We use the notation $\text{Stab}(\tau )$ from Conjecture 7. In analogy to the proof of Theorem 21, we denote by $H_{\tau }$ the image in the simplex ${\Delta }_{m-1}$ of a positive ramification component of type τ.

Theorem 27.

Assume $m\le n$. The norm map ${\psi }_{\mathcal{A}}$ in (14) has the following properties:

1. The image of ${\psi }_{\mathcal{A}}$ in ${\Delta }_{m-1}$ is the union of the curvy $(m-1)$-simplices $B_{\nu }$ where $\nu \in (\begin{array}{c}[n]\\ m\end{array})$. The curvy facets of these curvy simplices are $B_{\mu }$ where $\mu \in (\begin{array}{c}[n]\\ m-1\end{array})$. Some of these curvy $(m-2)$-simplices form the boundary of the semialgebraic set $\text{im}({\psi }_{\mathcal{A}})$.

2. Two curvy $(m-2)$-simplices $B_{\mu }$ and $B_{\mu \prime }$ have the same Zariski closure if $\text{type}(\mu )=\text{type}(\mu \prime )$. Thus, the irreducible branch hypersurfaces $H_{\tau }$ are indexed by $\tau \in T_{n,m-1}$.

Proof.

For $\mathcal{l}\in \{1,\dots ,m\}$ and $\nu \in (\begin{array}{c}[n]\\ \mathcal{l}\end{array})$, the set $R_{\nu }$ is a convex polyhedral cone, spanned by linearly independent vectors in a linear subspace of dimension $\mathcal{l}\le m$ in ${\mathbb{R}}^n$. By Proposition 24, the map ${\varphi }_{\mathcal{A},\ge 0}$ is injective on $R_{\nu }$. Therefore, by the transformation in (15), the map ${\psi }_{\mathcal{A}}$ is injective on $R_{\nu }$ up to scaling. This means that the image $B_{\nu }={\psi }_{\mathcal{A}}(R_{\nu })$ is a curvy simplex of dimension $\mathcal{l}-1$ inside the probability simplex ${\Delta }_{m-1}$. We also conclude that the boundary of $\text{im}({\psi }_{\mathcal{A}})$ equals the union of the images $B_{\nu }={\psi }_{\mathcal{A}}(R_{\nu })$, where ν runs over a certain subset of $(\begin{array}{c}[n]\\ m-1\end{array})$. These specify the algebraic boundary of $\text{im}({\varphi }_{\mathcal{A},\ge 0})$. This proves (i).

To see that part (ii) holds, we write the restriction of ${\varphi }_{\mathcal{A},\ge 0}$ to the cone $R_{\mu }$ as a polynomial function in only $\mathcal{l}$ distinct variables x_i. The jth coordinate of that restriction has the form ${\sum }_{i=1}^{\mathcal{l}}{\tau }_i x_i^{a_j}$, where $\tau =\text{type}(\mu )$. Different cones $R_{\mu }$ of the same type τ are distinguished only by the orderings of the parameters $x_1,x_2,\dots ,x_{\mathcal{l}}$. However, they have the same linear span in ${\mathbb{R}}^n$. Hence, after we drop the distinguishing inequalities x_i > x_j, the maps are the same. In particular, their images $B_{\mu }$ have the same Zariski closures $H_{\tau }$ in the simplex ${\Delta }_{m-1}$. □

Example 26 illustrates Theorem 27 for $m=3$, where $\left|T_{n,2}\right|=\lfloor n^2/4\rfloor$ and $|\text{Stab}(\tau )|\in \{1,2\}$. We found it more challenging to understand the geometry of our image in higher dimensions.

Example 28

($n=8,m=4$). The image of ${\psi }_{\mathcal{A}}$ in the tetrahedron is a curvy 3-polytope. It is partitioned by $56=(\begin{array}{c}8\\ 3\end{array})$ curvy triangles $B_{\nu }$. Their types τ identify 16 clusters: two singletons, ten triples, and four of size six. These determine $16=\left|T_{8,3}\right|$ branch surfaces $H_{\tau }$.

Based on computational experiments, we believe that, for all pairs $m\le n$ and all exponents $\mathcal{A}$, the image of ${\psi }_{\mathcal{A}}$ has the combinatorial structure of the cyclic polytope of dimension m – 1 with n vertices. In particular, the boundary is formed by the curvy $(m-2)$-simplices $B_{\mu }$ where μ runs over all sequences that satisfy Gale’s Evenness Condition [16, Theorem 0.7]. This predicts that the boundary in Example 28 is subdivided into 12 curvy triangles $B_{\mu }$, namely those indexed by $\mu \in \{123,128,134,145,156,167,178,238,348,458,568,678\}$. Our belief is supported by related results for the moment curve, where $\mathcal{A}=\{1,2,\dots ,m\}$, due to Bik, Czapliński and Wageringel [1]. Their figures show curvy cyclic polytopes in dimension 3.

The theory of triangulations of cyclic polytopes [13] now suggests an approach to unique recovery even when m < n. Each triangulation consists of a certain subset of $(\begin{array}{c}[n]\\ m\end{array})$. If our belief is correct, then this should induce a curvy triangulation of $\text{im}({\psi }_{\mathcal{A}})$. A general point c in the image is contained in a unique simplex $B_{\nu }$ of the triangulation. There is a unique z in the locus $R_{\nu }$ with ${\psi }_{\mathcal{A}}(z)=c$. The assignment $c\mapsto z$ serves as a method for unique recovery.

We conclude with a natural generalization of the problem discussed in this section. Let $\mathcal{K}=\{K_1,\dots ,K_m\}$ be a set of centrally symmetric convex bodies in ${\mathbb{R}}^n$. Each of these defines a norm $\left|\right| · |{|}_{K_i}$ on ${\mathbb{R}}^n$. The unit ball for that norm is the convex body K_i. Consider the map (16) $${\psi }_{\mathcal{K}} : {\mathbb{R}}_{\ge 0}^n--\to {\Delta }_{m-1} : x \mapsto \frac{1}{\sum _{j=1}^m\left|\right|x|{|}_{K_j}}·( |\left|x\right|{|}_{K_1},\left|\right|x|{|}_{K_2},\dots ,|\left|x\right|{|}_{K_m}).$$(16)

Problem 29. Study the image and the fibers of the map ${\psi }_{\mathcal{K}}$. Identify the branch loci of ${\psi }_{\mathcal{K}}$.

Additional information

Funding

Hana Melánová was supported by Supported by START-Prize Y-966 of the Austrian Science Fund.