Quantum Entanglement, Symmetric Nonnegative Quadratic Polynomials and Moment Problems
Grigoriy Blekherman H. M. Bharath
  
    


G. Blekherman]Grigoriy Blekherman
Grigoriy Blekherman: School of Mathematics, Georgia Tech, 686 Cherry
  Street, Atlanta, Georgia, 30332, United States of America;
  

B.H. Madhusudhana]Bharath Hebbe Madhusudhana
Bharath Hebbe Madhusudhana: Fakultät für Physik, Ludwig-Maximilians-Universität München,
Schellingstr. 4,
80799 München, Germany;
 




 
Quantum states are represented by  positive semidefinite Hermitian operators with unit trace, known as density matrices. An important subset of quantum states is that of separable states, the complement of which is the subset of entangled states. 
We show that the problem of deciding whether a quantum state is entangled can be seen as a moment problem in real analysis. Only a small number of such moments are accessible experimentally, and so in practice the question of quantum entanglement of a many-body system (e.g, a system consisting of several atoms) can be reduced to a truncated moment problem.
By considering quantum entanglement of n identical atoms we arrive at the truncated moment problem defined for symmetric measures over a product of n copies of unit balls in ^d. We work with moments up to degree 2 only, since these are most readily available experimentally. We derive necessary and sufficient conditions for belonging to the moment cone, which can be expressed via a linear matrix inequality of size at most 2d+2, which is independent of n. The linear matrix inequalities can be converted into a set of explicit semialgebraic inequalities giving necessary and sufficient conditions for membership in the moment cone, and show that the two conditions approach each other in the limit of large n. The inequalities are derived via considering the dual cone of nonnegative polynomials, and its sum-of-squares relaxation. We show that  the sum-of-squares relaxation of the dual cone is asymptotically exact, and using symmetry reduction techniques MR2067190,BR, it can be written as a small linear matrix inequality of size at most 2d+2, which is independent of n. For the cone of symmetric nonnegative polynomials with the relevant support we also prove an analogue of the half-degree principle for globally nonnegative symmetric polynomials  MR1996126,MR2864859.   



Quantum Entanglement, Symmetric Nonnegative Quadratic Polynomials and Moment Problems
    [
    December 30, 2023
=====================================================================================



§ INTRODUCTION


We consider a problem that lies in the intersection of real analysis, real algebraic geometry and quantum entanglement.  We begin with a brief introduction to quantum entanglement, explaining how it is related to real analysis and algebraic geometry. We then define and motivate the problem considered in this paper. 

In quantum mechanics, the state of a physical system is represented by a density matrix, which is, by definition, a positive semi-definite, Hermitian operator with trace one. As a convention, we drop the trace condition so that the space of density matrices is a convex cone. Since any positive semidefinite matrix can be rescaled to have trace one, this does not affect the results of the paper. Let T_n be the convex cone of all positive semi-definite Hermitian operators acting on ℂ^n. By our convention, an element of T_n can be rescaled to an n × n density matrix. Physical systems that correspond to n=2 are known as qubits. 

A natural way to construct larger density matrices is by using tensor products.  In physics this corresponds to combining several subsystems into a large system. As an example, we will consider a system with two subsystems represented by density operators in T_m and T_n respectively.  The tensor product gives a map T_m × T_n → T_mn, where ρ_1∈ T_m and ρ_2∈ T_n are mapped to ρ_1⊗ρ_2 ∈ T_mn, for m, n ∈ℕ.  A convex subset Ω_nm of T_nm is generated by the conical hull of the image of this map:

    Ω_mn = conical.hull{ρ_1 ⊗ρ_2: ρ_1 ∈ T_m   ρ_2 ∈ T_n }.

An element ρ∈Ω_mn can be obtained from a measure μ over T_m× T_n via ρ = ∫_T_m × T_nρ_1⊗ρ_2   dμ. The density matrices in T_m are states of an m-dimensional system; the density matrices in T_n are states of an n-dimensional system, and the density matrices in T_mn are states of the composite of the two systems. The subset Ω_mn⊂ T_mn consists of separable states. That is, a density matrix in Ω_mn represents a separable state and a density matrix in T_mn∖Ω_mn represents an inseparable state, also known as an entangled state of the two subsystems. While the notion of quantum non-locality  PhysRevA.40.4277, Peres1997 is different from inseparability, the latter is used synonymously with entanglement (see for instance, the  recent review RevModPhys.81.865). Quantum entanglement is not only fundamental to quantum physics, it also has applications in quantum communications, quantum metrology and quantum computation <cit.>.  

One of the basic problems in quantum entanglement is the characterization of the cone Ω_mn. In the special case of rank-1 density matrices, also known as pure states, this problem has a complete solution <cit.>. The mn elements of the vector in the range of a rank-1 matrix ρ∈ T_mn can be written as a m× n matrix in a natural way. ρ∈Ω_mn iff this matrix also has rank-1. The general problem of deciding whether an element ρ∈ T_mn is in Ω_mn has been shown to be NP-hard in the complexity parameter mn 2003quantph3055G. However, several special instances of this problem can be solved exactly. When m=2, n=2 and when m=2, n=3, the cone Ω_mn has been completely characterized PhysRevLett.77.1413, HORODECKI19961, using positive partial transpose criterion. The general case of larger dimensions, or greater number of subsystems, is open, although there are a number of partial results Recent_Development_1, Recent_Development_2, Recent_Development_3, Recent_Development_4, Recent_Development_5, PhysRevA.89.062110.  

Our approach is to convert the study of quantum entanglement into a truncated moment problem. The relation between quantum entanglement and the truncated moment problem has been recognised rather recently <cit.> and therefore, the full potential of the state of the art in the truncated moment problem has not been utilized to address the entanglement problem.  The elements of ρ∈Ω_mn are quadratic moments of a measure over T_m× T_n, where each quadratic monomial has one variable from T_m and one variable from T_n. Therefore, characterizing the cone Ω_mn can be viewed as a truncated moment problem. In fact, this equivalence between deciding whether a quantum state is entangled and a truncated moment problem generalizes to quantum systems with arbitrary number of subsystems. Although quantum entanglement has been studied extensively over the past few decades, this formulation, which allows us to bring in the tools of real algebraic geometry, has not been sufficiently explored. In this work, we consider a class of truncated moment problems that arise from the study of quantum entanglement and show that the resulting criteria on entanglement are stronger than the existing ones.  

The most commonly studied physical system is the so-called “two-level system" or a “qubit", described by a density matrix in T_2. Theoretically, this is the simplest non-trivial example of quantum mechanical systems, and experimentally, there have been several platforms to realize such systems including trapped atoms, photons, and circuit QED systems. Therefore, we consider a truncated moment problem that arises from the study of entanglement in a system consisting of n subsystems, each described by a density matrix in T_2. The space of all density matrices of the composite system is T_2^n. The subspace of separable states is 

    Ω_2^n = conical.hull{ρ_1 ⊗ρ_2⊗⋯⊗ρ_n: ρ_i ∈ T_2 }.

From the above discussion we see that Ω_2^n is a moment cone of measures defined over T_2×⋯× T_2, where we take degree n moments, and each moment monomial has one variable from the coordinates of each T_2. We observe that T_2 has a simple description: any self-adjoint 2× 2 complex matrix can be written as 

    ρ = ([  w+z x-iy; x+iy  w-z ]),

for x, y, z, w ∈ℝ and w≥ 0. The positive semidefiniteness condition is given by w^2 -x^2-y^2-z^2 ≥ 0. Due to multilinearity of tensors, 
we may restrict ourselves to measures defined on the compact section T̃_2 of T_2 with the hyperplane w=1.  We see from above that T̃_2 is D^3, the closed unit ball in ℝ^3 also known as the Bloch sphere. Since we dehomogenized by setting w=1 we now consider moments up to degree n on T̃^n_2, where each moment monomial has at most 1 variable from the coordinates of each T̃_2.

Therefore, Ω_2^n is a moment cone of such moments for measures defined over the space K_n^3 =  D^3 ×⋯× D^3.

There are two characteristics of a real physical situation that simplify this problem. First,  in a laboratory, not every element of a density matrix ρ∈ T_2^n can be retrieved. Therefore, the decision of whether ρ can be in Ω_2^n has to be made based on a subset of the elements of ρ. In other words, the problem requires characterization of a projection of the cone of moments over K_n^3, usually consisting of very few moments. We do not consider the characterization of the cone Ω_2^n here; instead, we consider the characterization of its projection. That is, corresponding to a linear space L, we consider the decision problem of deciding whether a point in Π_L(T_2^n) is in Π_L(Ω_2^n). The linear space L is defined by taking all the relevant quadratic moments, since these are most readily measured in the lab <cit.>. And secondly, the atoms used in such experiments are called bosons, meaning, they possess an exchange symmetry. That is, the density matrix ρ is invariant under the action of the symmetric group S_n, which permutes the atoms, and so is any measure μ that generates the density matrices in Ω_2^n. Therefore, the problem is to characterize the moment cone of symmetric measures defined over K_n^3. 

We now consider a generalized version of the above problem in physics. In particular we use D^d instead of D^3, although the structure is not physically relevant for any value of d other than 3.



 §.§ Problem Statement and Results


Let D^d⊂^d be the closed unit ball in a d dimensional real vector space. That is, D^d={𝐯:   𝐯∈^d,  ||𝐯||≤ 1}. We define K^d_n as the product of n such unit balls:

    K^d_n = D^d ×⋯× D^d ⊂^nd.

Points in K_n^d can be represented by a n-tuple of d-dimensional vectors (𝐯_1, 𝐯_2, ⋯, 𝐯_n ), where, 𝐯_i = (v_i,1, v_i,2⋯ v_i,d )∈ D^d. The symmetric group S_n (i.e., the group of all permutations of the set {1, 2, ⋯, n}) acts on K_n^d by permuting the vectors 𝐯_i. For σ∈ S_n, its action on K_n^d is given by σ∘ (𝐯_1, 𝐯_2, ⋯, 𝐯_n )=(𝐯_σ(1), 𝐯_σ(2), ⋯,  𝐯_σ(n) ). We refer to a measure μ defined on K_n^d as a symmetric measure if it is invariant under the action of S_n. That is, if A⊂ K_n^d, 

    μ(A)= μ(σ∘ A),   ∀ σ∈ S_n.
 
In this work, we consider the truncated K-moment problem for symmetric measures over K_n^d. Moments of symmetric measures are also invariant under coordinate permutations.

Let V_n,d the vector space of real square-free polynomials in d· n variables 𝐱_1,⋯, 𝐱_𝐧, 𝐱_𝐢=(ξ_i,1,⋯, ξ_i,d) which is spanned by the following symmetric polynomials: 
    1,      s_α=∑_i=1^n ξ_i,α,     1≤α≤ d and s_αα=∑_i ≠ jξ_i,αξ_j,α,    1≤α≤ d.


A polynomial Q in V_n,d can be uniquely written as 

    Q(𝐱)=A_0+∑_α=1^d A_α s_α+∑_α=1^d A_ααs_αα.

The dimension of V_n,d is therefore 2d+1. This choice of basis polynomials s_α and s_αα is dictated by the underlying physics. The moments are symmetric because the particles are bosons, possessing exchange symmetry, they are square-free since tensor product of different vector spaces only include multilinear (or square-free) monomials, and we only look at quadratic moments because the corresponding moments can be measured in a laboratory <cit.>.

We sometimes refer to polynomials in V_n,d by the (2d+1)-tuple of coefficients (A_0,A_α,A_αα).

We use m_0, m_α and m_αα to denote the corresponding moments:

    m_0 = ∫_K_n^d1   dμ,      m_α= ∫_K^d_ns_α dμ,     m_αα= ∫_K^d_ns_αα  dμ.

The moment sequence β_μ=(m_0,m_α,m_αα) lies in ^2d+1. We define C_n,d⊂^2d+1 to be the set of all moment sequence coming from measures on K_n^d. Since the product of the unit balls K_n^d is compact, it follows that C_n,d is a closed convex cone (cf. <cit.>).

The dual cone of C_n,d is the cone P_n,d of symmetric polynomials in V_n,d nonnegative on K_n^d: <cit.>.

    P_n,d= {Q ∈ V_n,d:    Q(𝐱) ≥ 0  for all 𝐱∈ K_n^d  }.

We consider the problem of characterizing the cones C_n,d and P_n,d. Our main result are four explicit Linear Matrix Inequalities (LMI) of size 2d+2, which give necessary and sufficient conditions for belonging to C_n,d and P_n,d (Theorems <ref> and  <ref> for P_n,d, and Theorem <ref> for C_n,d). The linear matrix inequalities for C_n,d and P_n,d are dual to each other.  These necessary and sufficient criteria can be seen to approach the same limit as the number n of unit balls approaches infinity (see Remark <ref>). For the cone C_n,d we were able to convert the linear matrix inequality into an explicit set of 2^d+1 semialgebraic inequalities describing necessary and sufficient conditions for membership in C_n,d. 

[Theorems <ref> and <ref>]
A non zero vector (z_0, z_1,⋯, z_d, z_11, z_22,⋯, z_dd) lies in C_n,d if z_0>0 and

    ∑_α=1^dmax{z_0z_αα/n, z_α^2/n}≤  z_0^2(n-1/n)^2+ ∑_α=1^d (n-1)z_0z_αα/n^2

Moreover, if the inequalities below are violated:

    z_0>0  and∑_α=1^dmax{z_0z_αα/n-1, z_α^2/n}≤  z_0^2+ ∑_α=1^d z_0z_αα/n

Then the non zero vector (z_0, z_1,⋯, z_d, z_11, z_22,⋯, z_dd) ∉ C_n,d. Each of the above systems of inequalities may also be expressed by a linear matrix inequality of size 2d+2.


The necessary conditions in the physically relevant case of d=3 appeared in <cit.> in the language of spin moments (see Section <ref> for more details). For other related results from physics, see <cit.>, <cit.> and <cit.>. As we explain below the necessary conditions are obtained from the sum-of-squares approximation to the cone P_n,d. The sufficient conditions are new, and they allow us to estimate the tightness of approximation for large n, which was previously unknown.

We now give a more detailed description of our results. First we show that nonnegativity on K^d_n of a polynomial Q ∈ V_n,d, can be established by testing its values on much smaller subset of K^d_n. It is easy to see that Q∈ V_n,d is nonnegative on K_n^d if and only if Q is nonnegative on the product of unit spheres (S^d-1)^n. Furthermore we show that Q(𝐱)≥ 0 for all 𝐱=(𝐱_1,⋯,𝐱_𝐧)∈ (S^d-1)^n if and only if Q(𝐱)≥ 0 for all 𝐱 with at most 2d of 𝐱_𝐢 distinct.  
[Theorem <ref>] A polynomial Q ∈ V_n,d is nonnegative on S^d-1×⋯× S^d-1 if and only if Q(𝐱_1, ⋯, 𝐱_n) is nonnegative for all sets of n points 𝐱_1, ⋯, 𝐱_n on S^d-1 with at most 2d of them distinct.


The above theorem is in the spirit of the half-degree principle for globally nonnegative symmetric polynomials MR1996126,MR2864859. Our problem is different in two ways. First, we are concerned here nonnegativity of polynomials over a compact subset, K_n^d, and second, the symmetry in our problem permutes only d-tuples of coordinates. This is a smaller group of transformations, compared to the usual symmetric case. Symmetries of such type have also been considered in <cit.>, where such polynomials were called mutlisymmetric. However our bounds are sharper than those of <cit.>. 

Secondly, we provide an asymptotically tight characterization of the cones C_n,d and P_n,d using sums of squares approximations. For i=1,⋯,n define p_i=1-∑_j=1^d ξ^2_j,i.  If Q∈ V_n,d can be written as 

    Q(𝐱)=∑_i=1^r ℓ_i^2(𝐱)+∑_i=1^d λ_i(1-p_i(𝐱)),

where ℓ_i are linear polynomials and λ_i ≥ 0, then Q is clearly nonnegative on K_n^d.
Define Σ_n,d to be the cone of such polynomials, whose nonnegativity can be certified via sums of squares. One can view Σ_n,d as the first level of the Lasserre (or Sum-of Squares) hierarchy for K^d_n <cit.>. See Section <ref> for more details. We have the inclusion:

    Σ_n,d⊆ P_n,d.



As we show in Section <ref> the containment is already strict when d=1. Using this, strict containment for larger d also follows by considering polynomials with A_α and A_αα equal to 0 for α≥ 2.
For the analogous results on equality between globally nonnegative symmetric polynomials and sums of squares see <cit.>.

Using symmetry reduction techniques MR2067190,BR we show that Σ_n,d can be characterized by a linear matrix inequality (LMI), of size 2d+2, which is independent of n. Now define Σ'_n,d as a slightly expanded version of Σ_n,d:

    Σ'_n,d = {(A_0, A_α, A_αα):  A_0+n-1/n∑_α=1^dA_αs_α+  n-1/n∑_α=1^dA_ααs_αα∈Σ_n,d}.


Our main result on sum of squares approximations is that the reverse inclusion holds for Σ'_n,d and P_n,d :


[Theorem <ref>]
We have the following inclusions:

    Σ_n,d⊆ P_n,d⊆Σ'_n,d.

Moreover, both cones Σ_n,d and Σ'_n,d can be described by a linear matrix inequality of size at most 2d+2.


As the number of unit balls n grows the cones Σ_n,d and Σ'_n,d approach each other at the rate 1/n and therefore, they give an asymptotically exact characterization of P_n,d. Therefore sums of squares give an asymptotically tight approximation of nonnegative polynomials. A similar result for fully symmetric globally nonnegative polynomials of degree 4 was established in <cit.>, and for fully symmetric even degree 6 polynomials in <cit.>. Using semidefinite duality and Schur complement we derive the LMI and semialgebraic descriptions of the cone C_n,d in Theorems <ref> and <ref>.



 §.§ Relation to previous work on Lasserre/Sum of squares hierarchies.
 The cone Σ_n,d is simply the first level of the Lasserre or sum of squares hierarchy for K^d_n <cit.>. We observe that the size of the linear matrix inequalities produced by the standard hierarchy grows with the number n of unit balls. However, after we apply the symmetry reduction technique, we find an explicit LMI whose size is independent of n, and depends only on.the dimension d of the unit ball. In principle, one can use higher levels of the hierarchy to obtain a tighter inner approximation of P_n,d. Unfortunately,  symmetry reduction gets quite complicated if we go above degree 2. However, as we show, the first level of the hierarchy unexpectedly provides an asymptotically tight approximation. We note that good behavior of low-degree sum of squares relaxation is a subject of interest in theoretical computer science in relation to the Unique Games Conjecture <cit.>.

We also point out that a small LMI description does not necessarily lead to a simple set of inequalities describing a given set. For instance, some cones of sums of squares are known to have small LMI descriptions, but the semilagebraic inequalities describing them have very large degree <cit.>. Therefore, the description of Theorem <ref>
is quite fortuitous and not guaranteed from general theory.




 
The rest of the paper is structured as follows. In the next Section, we present the exact results, i.e., an analogue of the half-degree principle. In Section <ref>, we provide the asymptotic approximation results. In Section <ref>, we dualize polynomial results to get asymptotically tight criteria on moments. We conclude in Section <ref> with an application of our results to the case d=3 and recover the necessary conditions shown in <cit.>, along a set of sufficient conditions.



§ EXACT RESULTS


In this section, we provide an analogue of the half degree principle for the cone P_n,d.  More specifically, we show that to test nonnegativity of Q∈ V_n,d  on K_n^d we only need to test that it takes nonnegative values on points 𝐱=(𝐱_1, ⋯, 𝐱_n) on K_n^d with at most 2d of them distinct. Observe that such points form a submanifold of K_n^d of dimension 2d(d-1), and this is independent of n, while dimension of K_n^d is dn. As warm-up and illustration we start with the one-dimensional case d=1.



 §.§ One Dimensional Case d=1
 As a simple first step we characterize the cones C_n,1 and P_n,1. The relevant unit ball is D^1=[-1,1]. A point in K_n^1 is represented by (x_1, x_2, ⋯, x_n) where x_i ∈ [-1,1]. Quadratic polynomial Q∈ V_n,1 has the form:

    Q = A_0 + A_1 s_1 + A_11s_11.

Note that Q has only linear terms in each variable x_i. Therefore, extreme values of Q occur when x_i =± 1. In other words, Q is nonnegative on K_n^1 if and only if it is nonnegative on the discrete hypercube H_n={-1,+1}^n. For a point  𝐱=(x_1,⋯,x_n) ∈ H_n with k entries equal to -1 and  n-k entries equal to +1 we have s_1(𝐱)=n-2k and s_11(𝐱) = (n-2k)^2-n. We immediately obtain the following Proposition:


A polynomial Q=  A_0 + A_1 s_1 + A_11s_11∈ P_n,1 if and only if

    A_0+A_1(n-2k)+A_11((n-2k)^2-n)≥ 0,

holds for k=0,1,⋯,n.


Each inequality represents a side of the polygon shown in FIG1. The dual cone C_n,1 of moment sequences coming from measures is also a polyhedral cone defined by n+1 inequalities. The defining inequalities of C_n,1 follow from Proposition <ref>:


A vector 𝐦=(m_0, m_1, m_11)∈ C_n,1 if and only if

    m_0(n-1+(n-1-2k)^2)-m_1(n-1-2k)+m_11≥ 0,

holds for k=0,1,⋯,n.

Thus, when d=1, C_n,1 and P_n,1 are both basic semi-algebraic sets, and are given by n+1 linear inequalities. 



 §.§ General Dimension


When d>1, C_n,d is the conical hull of a semi-algebraic set. Indeed,

    C_n,d = ConicalHull{ (1, s_1(𝐱), ⋯, s_d(𝐱), s_11(𝐱), ⋯, s_dd(𝐱)): 
    𝐱∈ K^d_n }.

K_n^d is a basic semi-algebraic set and therefore, its image under a polynomial function is semi-algebraic. A polynomial Q∈ P_n,d is linear in each of its arguments and therefore, it is nonnegative on K_n^d if and only if it is nonnegative on its boundary, ∂ K_n^d=S^d-1×⋯× S^d-1. Therefore, membership of a polynomial Q in P_n,d is validated by verifying its non-negativity on an n(d-1) dimensional manifold. However, in theorem <ref>, we show that it suffices to verify its non-negativity on finitely many copies (O(n^2d-1)) of a 2d(d-1) dimensional manifold. This theorem is an analogue of the degree principle MR1996126, MR2864859. See also <cit.> and <cit.> for related results. 









We now state and prove the main theorem of this section:

A polynomial Q ∈ V_n,d is nonnegative on S^d-1×⋯× S^d-1 if and only if Q(𝐱_1, ⋯, 𝐱_n) is nonnegative for all sets of n points 𝐱_1, ⋯, 𝐱_n on S^d-1 with at most 2d of them distinct.



 We will prove this theorem via an application of Lagrange multipliers. Recall that Q∈ V_n,d has the form 
    Q = A_0+∑_α=1^d (A_αs_α+A_ααs_αα).

Observe that polynomials Q all of whose global minima on (S^d-1)^n contain more than 2d distinct vectors form an open subset of V_n,d, since a sufficiently small perturbation of a polynomial with all minima containing more than 2d distinct vectors results in a polynomial with all minima still containing more than 2d distinct vectors. Additionally, polynomials with all coefficients A_α and A_αα distinct also form an open subset of V_n,d. Therefore, if a counterexample to the Theorem exists, it can be chosen with A_α and A_αα distinct, and thus it suffices to prove the Theorem for polynomials Q with all coefficients A_α and A_αα distinct.

Let 𝐱^*=(𝐱_1^*, ⋯, 𝐱_n^*) be a global minimum of Q on (S^d-1)^n and let 𝐱_i^*=(ξ_i,1, ⋯, ξ_i, d). Since the global minimum is a critical point, it satisfies the following Lagrange multiplier equations for α=1,⋯,d and i=1,⋯,n:

    A_α+2A_ααs_α(𝐱^*) =(λ_i+2A_αα)ξ_i,α,

where λ_i∈ are the Lagrange multipliers. Note that the left-hand side of the above equation is independent of the index i. We therefore introduce 

    R_α=A_α+2A_ααs_α(𝐱^*), α=1,⋯, d.


and see that

    R_α=(λ_i+2A_αα)ξ_i,α

We first settle the simple case when R_α=0 for α = 1, ⋯, d.  It follows from (<ref>) that ξ_i, α=0 unless (λ_i+2A_αα)=0. The latter can hold for at most one value of α for any given i since the coefficients A_αα are distinct. Thus, ξ_i, α=0 for all but one value, α= α_i  for which we must have ξ_i, α_i= ± 1, since ∑_α(ξ_i,α)^2 = 1. Therefore, it follows that at most 2d of the vectors 𝐱_i^* can be distinct.

Without loss of generality, we may now assume that R_1  ≠ 0. This also implies that ξ_i, 1≠ 0 for i=1, ⋯, n. Eliminating λ_i from Equations (<ref>), we see that

    (R_1+2(A_αα-A_11)ξ_i,1)ξ_i,α =R_αξ_i, 1

Combining this together with the  equations ∑_α =1^d ξ_i, α^2=1, we see that t=ξ_i, 1 is a solution of following equation:

    ∑_β=1^d(R_βt)^2∏_α≠β^d (R_1+2(A_αα-A_11)t)^2  =  ∏_α=1^d (R_1+2(A_αα-A_11)t)^2∑_β=1^dξ_i, β^2 = ∏_α=1^d (R_1+2(A_αα-A_11)t)^2.

In other words, ξ_i, 1 is a root of the polynomial

    P(t)= ∑_β=1^d(R_βt)^2∏_α≠β^d (R_1+2(A_αα-A_11)t)^2  -  ∏_α=1^d (R_1+2(A_αα-A_11)t)^2

for every i. Note that the leading term of P(t) is t^2d× R_1^2Π_α=2^d4(A_αα-A_11)^2 and the constant term is -R_1^2d. Therefore, P(t) has degree 2d, and thus ξ_i,1 can take at most 2d distinct values. Next we show how a vector 𝐱_i^* can be reconstructed from ξ_i,1.

Observe from (<ref>) that ξ_i,α is determined by ξ_i,1 as

    ξ_i, α = R_αξ_i,1/R_1+2(A_αα-A_11)ξ_i,1.

unless  R_1+2(A_αα-A_11)ξ_i,1 =0 for some α. Such an α=α_0, if it exists, has to be unique for a given value of ξ_i,1 since all coefficients A_αα are distinct.  Therefore, if there is such an α_0 for a given root ξ_i, 1, the coordinate ξ_i, α is uniquely determined by ξ_i,1 for all α excluding α_0. The coordinate ξ_i, α_0 is determined up to a sign from ∑_α =1^d ξ_i, α^2=1. Therefore, every root of P(t) produces at most two distinct vectors 𝐱_i. We next show that those roots that produce two vectors are indeed double roots. 

As argued above, if ξ_i, 1 is a root of P(t) that produces two vectors then there is one α_0 for which R_1+2(A_α_0α_0-A_11)ξ_i,1 =0 and Equation (<ref>) implies that R_α_0=0. With this, we can deduce that (R_1+2(A_α_0α_0-A_11)t)^2 divides P(t) and therefore, ξ_i, α is a double root of P(t). Therefore, a simple root of P(t) produces a unique vector 𝐱_𝐢, while a multiple root of P(t) produces at most two vectors 𝐱_𝐢. Since degree of P(t) is at most 2d, it follows that at most 2d of vectors 𝐱_𝐢 are distinct.





There are n+2d-1n distinct ways of populating a set {𝐱_1, ⋯, 𝐱_n} using 2d distinct points on S^d-1. Therefore, this theorem reduces the search space of non-negativity of Q from an n(d-1) dimensional manifold to n+2d-1n copies of a 2d(d-1) dimensional manifold. 































































§ SUM OF SQUARES APPROXIMATION OF NONNEGATIVE POLYNOMIALS


In this section, we develop an asymptotic approximation of C_n, d and its dual cone P_n, d. We begin with the illustrative case of d=1, where we develop the main ideas of the proof.



 §.§ The case d=1
 
Although the case d=1 has a complete solution, i.e., membership of a quadratic Q=A_0+A_1s_1+A_11s_11 in P_n,1 can be checked by the n+1 inequalities in Proposition <ref>, it is a convenient platform to illustrate the ideas that lead us to the main result of this section. As shown in Proposition <ref>,  a quadratic Q lies in P_n,1 if and only if:

    A_0-nA_11 + √(n)A_1 (n-2k/√(n))  + nA_11(n-2k/√(n))^2  ≥ 0
 
for k=0,1,⋯, n. Note that the above expression has been cast in a way that is suggestive of introducing a new variable X to take the place of n-2k/√(n) and a polynomial 
    P_Q(X) = A_0-nA_11 + √(n)A_1X+nA_11X^2
 We may rewrite the above conditions as P_Q(X) ≥ 0 for X=-√(n), -√(n)+2/√(n), ⋯, +√(n). In other words, Q∈ P_n,1 if and only if P_Q(X)≥ 0 on n+1 evenly spaced points in [-√(n), √(n)]. Given that the spacing 2/√(n) approaches zero as n approaches infinity, we are prompted to define the following cone:

    Σ_n,1 = {(A_0, A_1, A_11):  P_Q(X) ≥ 0  for all X∈ [-√(n), √(n)]}

Clearly we have Σ_n,1⊆ P_n,1. Since Σ_n,1 is a set of univariate quadratics nonnegative on a closed interval, the cone Σ_n,1 is easily characterized and inclusion in it provides a sufficient condition for inclusion in P_n,1. We next show that a necessary condition can be obtained by slightly enlarging the cone Σ_n,1.

    Σ_n,1' = { (A_0, A_1, A_11):  (n/n-1A_0, A_1, A_11) ∈Σ_n,1}
 
Clearly, Σ_n,1⊂Σ_n,1'. Further, we show, in Proposition <ref>, that Σ_n,1' contains P_n,1. In the limit of large n, the cones Σ_n,1 and Σ'_n,1 converge.
 Σ_n,1⊆ P_n,1⊆Σ_n,1'


We show that all the extreme rays of P_n,1 are in Σ_n,1'. Let Q = (A_0, A_1, A_11) ∈ P_n,1 span an extreme ray. It follows that the corresponding polynomial P_Q(X) takes a zero value at two consecutive points in the set {-√(n), -√(n)+2/√(n), ⋯, +√(n)}. The zeros of P_Q are therefore separated by 2/√(n). Consequently, the minimum value of P_Q is -A_11. Therefore, P_Q+ A_11 is nonnegative on [-√(n), √(n)]. Also it follows from Proposition <ref> that A_11≤A_0/n-1 for any polynomial Q∈ P_n, 1.  Thus, P_Q +  A_0/n-1 is nonnegative on [-√(n), √(n)]. Thus, Q ∈Σ_n,1'.


The cones Σ_n,1 and Σ_n,1' that sandwich P_n,1 are better understood after a rescaling. Taking a cue from the definition of the polynomial P_Q, let us define 
    P̃_n,1 = {(B_0, B_1, B_11):  (B_0, B_1/√(n), B_11/n) ∈ P_n,1}
 
    Σ̃_n,1 = {(B_0, B_1, B_11):  (B_0, B_1/√(n), B_11/n) ∈Σ_n,1}
 and 
    Σ̃_n,1' = {(B_0, B_1, B_11):  (B_0, B_1/√(n), B_11/n) ∈Σ_n,1'}

This rescaling enlarges them so that we may visualize their limiting behavior. In particular, Σ̃_n,1= {(B_0, B_1, B_11):  B_0-B_11 + B_1 X + B_11X^2 ≥ 0, for all  X ∈ [-√(n), √(n)]} satisfies Σ̃_n+1,1⊆Σ̃_n, 1, i.e., they are nested and the limiting cone Σ̃ = ∩_n Σ̃_n,1 is the cone of all globally nonnegative quadratics, and has a simple characterization: (B_0,B_1,B_11) ∈Σ̃ if and only if 
    [ B_0-B_11   1/2B_1;   1/2B_1     B_11 ]≽ 0.

Figure <ref> shows the cross sections of P_n,1, as well as that of the rescaled cones P̃_n,1, Σ̃_n,1, Σ̃_n,1', Σ̃. Note that the cones Σ̃_n,1' are also nested and the corresponding limiting cone is also Σ̃. In this sense, the sufficient condition for inclusion in P_n,1, provided by Σ_n,1 and the necessary condition provided by Σ_n,1' approach each other asymptotically. In the next section we generalize the cones Σ_n,1 and Σ_n,1' to higher dimensions.



 §.§ General Dimension

We proceed along similar lines as for the d=1 case to obtain a necessary and asymptotically sufficient condition for membership in P_n, d.  We refer to the polynomial Q by its (2d+1)-tuple of rescaled coefficients. Analogous to the variable X of the previous section, we define variables X=(X_1,⋯,X_d) and Y=(Y_1,⋯,Y_d) as:

    X_α   = ∑_i=1^nξ_i,α/√(n), α=1,⋯,d,
    
    Y_α   = √(∑_i=1^nξ_i,α^2/n - X_α^2/n), α=1,⋯,d,

with 𝐱=(𝐱_1, ⋯, 𝐱_n) and 𝐱_i = (ξ_i,1, ⋯, ξ_i, d). Note that the Cauchy-Schwartz inequality ensures that Y_α are well defined real numbers. In terms of these variables, we may re-write Q as:

    Q(𝐱_1, ⋯, 𝐱_n) = A_0 + ∑_α=1^d √(n)A_αX_α + (n-1)∑_α=1^d A_ααX_α^2 - n∑_α=1^d A_ααY_α^2 = P_Q(X, Y).

Note that P_Q(X) is defined analogously to the previous section. For 𝐱∈ K_n^d the variables X_α and Y_α satisfy 
    ∑_α=1^d Y_α^2 + 1/nX_α^2 = ||Y||^2 +1/n||X||^2  ≤ 1,
 which follows from the conditions ||𝐱_i||≤ 1.  

We now consider a convex cone in V_n,d consisting of polynomials Q such that P_Q(X,Y) is nonnegative for all (X,Y) such that ||Y||^2 +1/n||X||^2  ≤ 1. From the above discussion it follows that this cone lies inside P_n,d. We show in Theorem <ref> that this cone turns out to coincide with the sum-of-squares relaxation of P_n,d, defined as Σ_n,d in the Introduction. To recall this definition, for i=1,⋯,n let p_i=1-∑_j=1^d ξ^2_j,i. We defined the cone Σ_n,d consisting of polynomials Q(𝐱) which can be written as:

    Q(𝐱)=∑_i=1^r ℓ_i^2(𝐱)+∑_i=1^d λ_i(1-p_i(𝐱)),

where ℓ_i are linear polynomials and λ_i ≥ 0. 


A polynomial Q lies in Σ_n,d if and only if P_Q(X,Y) ≥ 0 for all  X, Y such that ||Y||^2 + 1/n||X||^2 ≤ 1. 



By the S-Lemma <cit.> we can express the condition of nonnegativity of P_Q(X,Y) as a linear matrix inequality in the coefficients of P: P=A_0 + ∑_α=1^d √(n)A_αX_α + (n-1)∑_α=1^d A_ααX_α^2 - n∑_α=1^d A_ααY_α^2 is nonnegative for all  X, Y such that ||Y||^2 + 1/n||X||^2 ≤ 1 if and only if there exists c≥ 0 such that:

    [       A_0 √(n)/2A_1         ⋯ √(n)/2A_d         0         ⋯         0; √(n)/2A_1 (n-1)A_11         0         0         0         ⋯         0;         ⋮         0         ⋱         0         0         ⋯         0; √(n)/2A_d         0         0 (n-1)A_dd         0         ⋯         0;         0         0         ⋯         0    -nA_11         ⋯         0;         ⋮         0         ⋯         0         0         ⋱         0;         0         0         ⋯         0         0         0    -nA_dd;           ] +c[  -1   0   ⋯   0   0   ⋯   0;   0 1/n   0   0   0   ⋯   0;   ⋮   0   ⋱   0   0   ⋯   0;   0   0   0 1/n   0   ⋯   0;   0   0   ⋯   0   1   ⋯   0;   ⋮   0   ⋯   0   0   ⋱   0;   0   0   ⋯   0   0   0   1;     ]

is positive semidefinite.



We use symmetry reduction technique of <cit.>. Let V be the vector space of linear polynomials in d· n variables 𝐱_i=(ξ_i,1,⋯,ξ_i,d), i=1,⋯ n. The symmetric group S_n acts on V by permuting the vectors 𝐱_i, or equivalently S_n permutes n groups of α-th coordinates, ξ_i,α. Recall that irreducible S_n-modules are indexed by partitions of n. For more background on representation theory of S_n see <cit.>.

It is not hard to see that V decomposes as follows into irreducible S_n-modules:

    V=(d+1)S^(n)⊕ dS^(n-1,1).


The S_n-invariant part of V corresponding to the partition (n) is spanned by polynomials 1 and s_α for α=1,⋯, d. For the partition (n-1,1) we can split the isotypic component into d irreducible modules by considering for fixed α=1,⋯,d polynomials of the form 
    ∑_i=1^n c_i ξ_i,αwith∑ c_i=0.

We pick d isomorphic representatives f_α=nξ_1,α-s_α, i.e. these polynomials generate the above irreducible modules, and can be mapped to each other under S_n-equivariant maps.

Define polynomials p_αβ=∑_i=1^n ξ_i, αξ_i, β and q_αβ=∑_1≤ i<j≤ nξ_i,αξ_j,β, as well as p_αα=∑_i=1^n ξ_i,α^2. We will use  to denote the Reynolds operator :

    f=1/n!∑_σ∈ S_nσ(f).

We observe that  
    (∑_α=1^d λ_α(1-p_α(𝐱)))=λ_1+⋯+λ_d/n(n - ∑_α=1^d p_αα).


Now consider (d+1)×(d+1) matrix S given S_α,β= s_αs_β with s_0=1, and d× d matrix F given by F_α,β= f_αf_β. The symmetry reduction procedure tells us that p∈Σ_n,d if and only if there exist positive semidefinite symmetric matrices G, H and c ≥ 0 such that 

    p=⟨ S,G ⟩+⟨ F,H ⟩+c(n-∑_α=1^dp_αα).

Further examining matrices S and F, we have for α≠β  
    s_αs_β=p_αβ+q_αβand f_α f_β=1/n-1q_αβ-p_αβ,

while 
    s_α^2=s_αα+p_ααand f^2_α=n^2ξ_1, α^2- s_α^2=np_αα-s_α^2=(n-1)p_αα-s_αα.

We observe that in order to obtain p of the given form the coefficients of p_αβ and q_αβ must cancel. However this can only happen if the corresponding entries in G and H matrices are zero. Therefore we see that H is a diagonal matrix and G has non-zero off-diagonal entries only in the first row and column.

Let 
    G=[    g_0 1/2g_1      ⋯ 1/2g_d; 1/2g_1   g_11      0      0;      ⋮      0      ⋱      0; 1/2g_d      0      0   g_dd;        ],

and H be a diagonal matrix with entries h_αα. We now observe that p has a potentially non-zero coefficient of p_αα for α=1,⋯, d. This coefficient may be canceled only by using n-∑_α=1^d p_αα. Therefore the coefficient c must satisfy c=g_αα+(n-1)h_αα, α=1,⋯ d. Solving for h_αα we get h_αα=c-g_αα/n-1, with the additional restriction c≥ g_αα, since h_αα≥ 0.

By examining p=⟨ S,G ⟩+⟨ F,H ⟩+c(n-∑_α=1^dp_αα), we see that 

    A_0=cn+g_0,  A_α=g_α A_αα= (ng_αα/n-1-c/n-1)with c≥ g_αα.


Solving for g's we get g_0=A_0-cn, g_α=A_α and g_αα=n-1/nA_αα+c/n. The condition c≥ g_αα can be rewritten as c≥ A_αα.
Therefore p is a sum of squares if and only there exists c≥ 0 and c≥ A_αα, α=1,⋯,d such that the following matrix is positive semidefinite:


    [       A_0    1/2A_1         ⋯    1/2A_d;    1/2A_1 n-1/nA_11         0         0;         ⋮         0         ⋱         0;    1/2A_d         0         0 n-1/nA_dd;           ] +c[   -n    0    ⋯    0;    0  1/n    0    0;    ⋮    0    ⋱    0;    0    0    0 1/n.;      ]























We incorporate condition c≥ A_αα by enlarging the matrices so that the following matrix is positive semidefinite for some c≥ 0:


    [       A_0    1/2A_1         ⋯    1/2A_d         0         ⋯         0;    1/2A_1 n-1/nA_11         0         0         0         ⋯         0;         ⋮         0         ⋱         0         0         ⋯         0;    1/2A_d         0         0 n-1/nA_dd         0         ⋯         0;         0         0         ⋯         0     -A_11         ⋯         0;         ⋮         0         ⋯         0         0         ⋱         0;         0         0         ⋯         0         0         0     -A_dd;           ] +c[  -n   0   ⋯   0   0   ⋯   0;   0 1/n   0   0   0   ⋯   0;   ⋮   0   ⋱   0   0   ⋯   0;   0   0   0 1/n   0   ⋯   0;   0   0   ⋯   0   1   ⋯   0;   ⋮   0   ⋯   0   0   ⋱   0;   0   0   ⋯   0   0   0   1;     ]

We can multiply the above sum on both sides by a diagonal matrix with diagonal (1,√(n),⋯,√(n)) to see that p∈Σ_n,d if and only if there exists c≥ 0 such that the following matrix is positive semidefinite:

    [       A_0 √(n)/2A_1         ⋯ √(n)/2A_d         0         ⋯         0; √(n)/2A_1 (n-1)A_11         0         0         0         ⋯         0;         ⋮         0         ⋱         0         0         ⋯         0; √(n)/2A_d         0         0 (n-1)A_dd         0         ⋯         0;         0         0         ⋯         0    -nA_11         ⋯         0;         ⋮         0         ⋯         0         0         ⋱         0;         0         0         ⋯         0         0         0    -nA_dd;           ] +c[ -n  0  ⋯  0  0  ⋯  0;  0  1  0  0  0  ⋯  0;  ⋮  0  ⋱  0  0  ⋯  0;  0  0  0  1  0  ⋯  0;  0  0  ⋯  0  n  ⋯  0;  ⋮  0  ⋯  0  0  ⋱  0;  0  0  ⋯  0  0  0  n;    ]

The Theorem now follows from the Remark <ref> with c in the Remark replaced by nc.


In the following, we prove that the sufficient condition for membership in P_n,d provided by Σ_n,d is asymptotically necessary, following the same line of arguments as before. We define Σ_n,d', by expanding Σ_n,d:

    Σ_n,d' = {(A_0, A_α, A_αα): (n/n-1A_0, A_α, A_αα) ∈Σ_n,d}
 

We show in Theorem <ref> that, P_n,d⊆Σ_n,d' which provides a sufficient condition for membership in P_n,d. To prove this theorem, we need a technical lemma, which we prove at the end of this section:

 Let n∈ℕ and X= (X_1, ⋯ , X_d) ∈^d such that ||X||^2 = X_1^2+⋯ +X_d^2 ≤ n. There exists 𝐱=(𝐱_1, ⋯, 𝐱_n) ∈ K_n^d with 𝐱_i=(ξ_i,1, ⋯, ξ_i, d) such that:

    ∑_i=1^n ξ_i,α/√(n) = X_α for α=1,2,⋯,d
       ∑_i=1^nξ_i,α^2/n - X_α^2/n  =0  for α =1,2,⋯, d-1
       |(∑_i=1^n ξ_i,d^2/n - X_d^2/n)- (1-||X||^2/n)| ≤1/n



We are now ready to state and prove our main result of this Section.
 Σ_n,d⊆ P_n,d⊆Σ_n,d'


The first inclusion is immediate. To show the second inclusion, let Q = (A_0, A_α, A_αα)∈ P_n,d. Recall that the polynomial P_Q(X, Y) was defined as

    P_Q(X, Y) = A_0 + ∑_α=1^d √(n)A_αX_α + (n-1)∑_α=1^d A_ααX_α^2 - n∑_α=1^d A_ααY_α^2.

In order to show that P_Q+n/n-1 A_0 ≥ 0 whenever ||Y||^2 +1/n||X||^2 ≤ 1, we pick a point (X, Y) that satisfies the latter condition, and approximate it using 𝐱=(𝐱_1, ⋯, 𝐱_n) with the help of Lemma <ref>.

If A_αα≤ 0 for  all 1 ≤α≤ d, then 
we choose 𝐱=(𝐱_1,⋯,𝐱_n) with 𝐱_i = X/√(n) for all 1≤ i ≤ n. The condition ||Y||^2 +1/n||X||^2 ≤ 1 ensures that 𝐱∈ K_n^d. It follows now that

    P_Q(X, Y) ≥ A_0 + √(n)∑_α=1^d A_αX_α + (n-1)∑_α=1^d A_ααX_α^2 = Q(𝐱) ≥ 0

The last inequality follows since Q(𝐱) ∈ P_n,d. 

If A_αα> 0 for at least one α, we assume without loss of generality that A_dd≥ A_αα for α = 1, 2, ⋯ d-1. It also follows that A_dd>0. Clearly, 

    P_Q(X, Y) ≥ A_0 + √(n)∑_α=1^d A_αX_α + (n-1)∑_α=1^d A_ααX_α^2 - nA_dd(1-||X||^2/n)

We now use Lemma <ref> to pick 𝐱'=(𝐱'_1, ⋯, 𝐱'_n) such that 

    X_α'= ∑_i=1^n ξ_i,α/√(n) = X_αforα=1,2,⋯,d
       (Y_α')^2= ∑_i=1^nξ_i,α^2/n - X_α^2/n  =0 forα =1,2,⋯, d-1
       |(Y_d')^2-(1-||X||^2/n)|=|(∑_i=1^n ξ_i,d^2/n - X_d^2/n)- (1-||X||^2/n)| ≤1/n.

The above equations enable us to evaluate Q(𝐱') and we thus obtain

    Q(𝐱') = A_0 + √(n)∑_α=1^d A_αX_α + (n-1)∑_α=1^d A_ααX_α^2 - nA_dd(Y'_d)^2 ≥ 0

Finally using Equation (<ref>), we obtain 

    P_Q(X, Y) + A_dd≥ Q(𝐱')≥ 0

It follows from the d=1 case that A_dd≤A_0/n-1 and therefore, P_Q+A_0/n-1≥ 0 whenever Q ∈ P_n,d. 




It follows from Remark <ref> that (A_0,A_1,⋯ A_d,A_11,⋯ A_dd) ∈Σ_n,d' if and only if there exists c≥ 0 such that


    [  n/n-1A_0 √(n)/2A_1         ⋯ √(n)/2A_d         0         ⋯         0; √(n)/2A_1 (n-1)A_11         0         0         0         ⋯         0;         ⋮         0         ⋱         0         0         ⋯         0; √(n)/2A_d         0         0 (n-1)A_dd         0         ⋯         0;         0         0         ⋯         0    -nA_11         ⋯         0;         ⋮         0         ⋯         0         0         ⋱         0;         0         0         ⋯         0         0         0    -nA_dd;           ] +c[  -1   0   ⋯   0   0   ⋯   0;   0 1/n   0   0   0   ⋯   0;   ⋮   0   ⋱   0   0   ⋯   0;   0   0   0 1/n   0   ⋯   0;   0   0   ⋯   0   1   ⋯   0;   ⋮   0   ⋯   0   0   ⋱   0;   0   0   ⋯   0   0   0   1;     ]

is positive semidefinite.

We now prove Lemma <ref>.

We construct a point 𝐱∈ K_n^d with the claimed properties. Let

    𝐱_i=
    (X_1/√(n), X_2/√(n),⋯X_d-1/√(n), √(1-∑_α =1^d-1(X_α/√(n))^2))  for i=1, 2,⋯ k
    (X_1/√(n), X_2/√(n),⋯X_d-1/√(n), -√(1-∑_α =1^d-1(X_α/√(n))^2))  for i=k+1, k+2,⋯ n-1
    (X_1/√(n), X_2/√(n),⋯X_d-1/√(n), z)  for i=n

We make an appropriate choice of k and z in the following. We first observe that 

    √(1-∑_α =1^d-1(X_α/√(n))^2)≥|X_d|/√(n)

Each ξ_i,d is equal to ±√(1-∑_α =1^d-1(X_α/√(n))^2) we may choose k of them with the positive sign so that the sum of all the ξ_i,d's is closest to √(n)X^d. That is,

    |√(n)X_d-∑_i=1^n-1ξ_i,d| ≤√(1-∑_α =1^d-1(X_α/√(n))^2)≤ 1
 
Let us now set z=(√(n)X_d-∑_i=1^n-1ξ_i,d). It follows from the above inequality that this is a valid choice for a point on K_n^d. It also follows that ∑_i x_i^α/√(n)=X_α for α =1, 2, ⋯, d. It remains to show the last inequality in the lemma. Explicitly, 

    ∑_i ξ_i,d^2/n - (∑_iξ_i,d/n)^2=  (1-1/n||X||^2)  -1/n(1-||𝐱_n||^2).





§ NECESSARY AND SUFFICIENT CRITERIA FOR MOMENTS

In this section, using the cones Σ_n, d and Σ_n,d', we develop a necessary condition and a sufficient condition for membership of a vector (z_0, z_1,⋯, z_d, z_11, z_22,⋯, z_dd) in the moment cone C_n,d. We also show that these two conditions approach each other, i.e., the necessary condition is asymptotically sufficient and the sufficient condition is asymptotically necessary. 

Let us also define (Σ^'_n,d)^* as the dual of Σ_n,d'. It follows from Theorem <ref> that 

    Σ^*_n,d⊇ C_n,d⊇ (Σ_n,d^')^*

Thus, membership in Σ_n,d^* is a necessary condition and membership in (Σ_n,d^')^* is a sufficient condition for membership in C_n,d. In the following we develop inequality criteria to check for membership in these two cones, expressed as Linear Matrix Inequalities (LMI). 



 §.§ Dualizing Sum of Squares Cones


Recall from Remark <ref> that the cone Σ_n,d can be characterized as (A_0,A_α,A_αα)∈Σ_n,d if and only if there exists c∈ such the following matrix is positive semidefinite

    M=[         A_0-c     √(n)/2A_1             ⋯     √(n)/2A_d             0             ⋯             0             0;     √(n)/2A_1 (n-1)A_11+c/n             0             0             0             ⋯             0             0;             ⋮             0             ⋱             0             0             ⋯             0             0;     √(n)/2A_d             0             0 (n-1)A_dd+c/n             0             ⋯             0             0;             0             0             ⋯             0      -nA_11+c             ⋯             0             0;             ⋮             0             ⋯             0             0             ⋱             0             0;             0             0             ⋯             0             0             0      -nA_dd+c             0;             0             0             ⋯             0             0             0             0             c;               ]



Here the condition c≥ 0 has been absorbed into the last row and column. We observe that we can write

    M=cD+A_0M_0+∑_α=1^dA_αM_α+∑_α=1^d
    A_ααM_αα, M≽ 0,

where matrices D,M_α and M_αα are the coefficient matrices, whose entries depend on n. Standard semidefinite programming duality <cit.> tells us that the dual cone of Σ_n,d is given by:
Σ_n,d^* is the set of all points (z_0,z_1,⋯,z_d,z_11,⋯,z_dd) such that there exists a positive semidefinite (2d+2)×(2d+2) matrix X such that

    ⟨ D,X⟩=0, ⟨ M_0, X⟩=z_0,  ⟨ M_α, X⟩=z_α,  ⟨ M_αα, X⟩=z_αα.

Here ⟨ A,B⟩ is the standard trace inner product ⟨ A,B⟩=trace AB. By similar considerations and Remark <ref> the dual cone of Σ_n,d' is the set of all points (z_0,z_1,⋯,z_d,z_11,⋯,z_dd) such that there exists a positive semidefinite (2d+2)×(2d+2) matrix X satisfying

    ⟨ D,X⟩=0, n/n-1⟨ M_0, X⟩=z_0,  ⟨ M_α, X⟩=z_α,  ⟨ M_αα, X⟩=z_αα.


Therefore we obtain the following characterization of C_n,d:


A vector (z_0, z_1,⋯, z_d, z_11, z_22,⋯, z_dd) lies in C_n,d if there exists a positive semidefinite matrix X and such that:



    ⟨ D,X⟩=0, n/n-1⟨ M_0, X⟩=z_0,  ⟨ M_α, X⟩=z_α,  ⟨ M_αα, X⟩=z_αα.

Moreover, if there doesn't exist a  positive semidefinite matrix X such that:


    ⟨ D,X⟩=0, ⟨ M_0, X⟩=z_0,  ⟨ M_α, X⟩=z_α,  ⟨ M_αα, X⟩=z_αα,

then (z_0, z_1,⋯, z_d, z_11, z_22,⋯, z_dd) ∉ C_n,d.


Analyzing this formulation further and applying Schur complement <cit.>, the above conditions can be expressed as a set of 2^d algebraic inequalities giving necessary and sufficient conditions for membership in C_n,d, which asymptotically converge.


A non-zero vector (z_0, z_1,⋯, z_d, z_11, z_22,⋯, z_dd) lies in C_n,d if z_0>0 and

    ∑_α=1^dmax{z_0z_αα/n, z_α^2/n}≤  z_0^2(n-1/n)^2+ ∑_α=1^d (n-1)z_0z_αα/n^2

Moreover, if the inequalities below are violated:

    z_0>0  and∑_α=1^dmax{z_0z_αα/n-1, z_α^2/n}≤  z_0^2+ ∑_α=1^d z_0z_αα/n

Then a non-zero vector (z_0, z_1,⋯, z_d, z_11, z_22,⋯, z_dd) ∉ C_n,d.


We may write a (2d+2)× (2d+2) matrix X that satisfies ⟨ M_0, X⟩=z_0,  ⟨ M_α, X⟩=z_α and ⟨ M_αα, X⟩=z_αα as

    X = [                z_0          1/√(n)z_1                  ⋯          1/√(n)z_d                  0                  ⋯                  0                  0;          1/√(n)z_1               x_11                  ⋯               x_1d                  0                  ⋯                  0                  0;                  ⋮                  ⋮                  ⋱                  ⋮                  ⋮                  ⋮                  ⋮                  ⋮;          1/√(n)z_d               x_1d                  ⋯               x_dd                  0                  0                  0                  0;                  0                  0                  ⋯                  0 n-1/nx_11- 1/nz_11                  0                  0                  0;                  ⋮                  ⋮                  ⋯                  ⋮                  ⋮                  ⋱                  ⋮                  ⋮;                  0                  0                  ⋯                  0                  0                  ⋯ n-1/nx_dd- 1/nz_dd                  0;                  0                  0                  ⋯                  0                  0                  ⋯                  0                x_0;                    ]

Note that all the off-diagonal entries that can be chosen to be zero without disturbing the condition X≽ 0 have been chosen to be zero. The final equation, ⟨ X, D⟩ =0 eliminates the variable x_0 i.e.,  x_0 - z_0 +∑ x_αα - 1/n∑ z_αα =0.  The numbers z_0, z_α, z_αα are moments only if the numbers x_ij can be chosen that the matrix X is positive semidefinite. We list down the constraints on x_ij. Positive semidefiniteness of the lower (d+1)× (d+1) block yields the following inequalities, the last of which is an upper bound on ∑ x_αα and the rest are lower bounds on x_αα:

    x_αα   ≥1/n-1z_αα,  for α = 1, ⋯, d
    ∑ x_αα   ≤ z_0 + 1/n∑ z_αα.



The above inequalities imply that 
    1/n(n-1)∑ z_αα≤ z_0, andz_0 + 1/n∑ z_αα≥ 0.
 Additionally we know that x_αα≥ 0 for 1≤α≤ d. If z_0=0, then it is clear that z_α=0 for α=1,⋯,d, and the above inequalities taken together imply that if z_0=0, then z_αα=0 for α=1,⋯,d. Therefore we may assume that z_0>0.


Taking Schur complement with respect to z_0 (<cit.>) of the top (d+1)× (d+1) block, we see that X≽ 0 if and only if
: 
    z_0X̃-1/nzz^T ≽ 0.
 Here, X̃ is the d× d block containing the variables x_ij for i, j = 1, ⋯, d and z is the vector (z_1, ⋯, z_d). We may now choose the off-diagonals of X̃, x_ij, for i ≠ j so that the off-diagonals of z_0X̃-1/nzz^T are all zero. That leaves us with the inequalities that come from the non-negativity of the diagonal elements, providing d more upper bounds on x_αα:

    x_αα z_0≥z_α^2/n ,  for α = 1, ⋯, d

We thus have two lower bounds each on x_11, ⋯ , x_dd,  which are the only remaining variables. We also have one upper bound on ∑ x_αα. We can now eliminate the variables x_αα by setting the upper bound higher than every lower bound on ∑ x_αα. There are 2^d different lower bounds on ∑ x_αα, coming from two lower bounds each on x_αα. Thus, after eliminating these variables, we are left with the following conditions, that together form a necessary condition for membership in C_n, d:

    z_0>0 and∑_α=1^dmax{z_0z_αα/n-1, z_α^2/n}≤  z_0^2+ ∑_α=1^d z_0z_αα/n

For sufficient conditions we replace z_0 by n-1/nz_0 in the above inequality:

    z_0>0 and∑_α=1^dmax{z_0z_αα/n, z_α^2/n}≤(n-1)^2/n^2z_0^2+ ∑_α=1^d (n-1)z_0z_αα/n^2.


 

The above inequalities can be naturally written in rescaled moment coordinates z̃_α=z_α/√(n) and z̃_αα=z_αα/n as:

    z_0>0 and∑_α=1^dmax{n/n-1z_0 z̃_αα, z̃_α^2}≤  z_0^2+ ∑_α=1^d z_0z̃_αα,

for necessary conditions and:

    z_0>0 and∑_α=1^dmax{ z_0 z̃_αα, z̃_α^2}≤(n-1)^2/n^2z_0^2+ n-1/n∑_α=1^d z_0z̃_αα,

for sufficient conditions.

We observe that that as n approaches infinity the necessary and sufficient conditions approach each other, and in the (large particle) limit the cone C_n,d is given by inequalities: 

    z_0>0 and∑_α=1^dmax{ z_0 z̃_αα, z̃_α^2}≤  z_0^2+ ∑_α=1^d z_0z̃_αα.





Examining the above limit for d=1 we see that the limit of the cones C_n,1 is characterized is given by inequalities:

    z_0>0,z̃_1^2≤ z_0(z_0+z̃_11).


Thus the cone C_n,1 is dual (up to closure) to the characterization of the limit of the cones P_n,1 given in Equation (<ref>) of Section <ref>, since the above inequalities characterize positive semidefiniteness of the matrix

    [ z_0+z̃_11      z̃_1;      z̃_1       z_0 ],

up to closure.

The above results generalize conditions on moments found in <cit.>. In the next section, we show how the above equations reduce to the one found in <cit.> under the appropriate constraints.



§ A PHYSICAL EXAMPLE

As an example, we consider the case d=3 and use the conditions of Theorem  <ref> to define a semialgebraic set of moments contained in the set of moments which have a representing measure. Let z_0, z_1, z_2, z_3, z_11, z_22, z_33 be a set of numbers. From Theorem <ref> the necessary conditions for membership in C_n, 3 are given by z_0>0 and the following eight inequalities:

    z_1^2/n+z_2^2/n+z_3^2/n   ≤ z_0^2 + z_11z_0/n+z_22z_0/n+z_33z_0/n
    z_1^2/n+z_2^2/n+z_33z_0/n-1   ≤ z_0^2 + z_11z_0/n+z_22z_0/n+z_33z_0/n
    z_1^2/n+z_22z_0/n-1+z_3^2/n   ≤ z_0^2 + z_11z_0/n+z_22z_0/n+z_33z_0/n
    z_1^2/n+z_22z_0/n-1+z_33z_0/n-1   ≤ z_0^2 + z_11z_0/n+z_22z_0/n+z_33z_0/n
    z_11z_0/n-1+z_2^2/n+z_3^2/n   ≤ z_0^2 + z_11z_0/n+z_22z_0/n+z_33z_0/n
    z_11z_0/n-1+z_2^2/n+z_33z_0/n-1   ≤ z_0^2 + z_11z_0/n+z_22z_0/n+z_33z_0/n
    z_11z_0/n-1+z_22z_0/n-1+z_3^2/n   ≤ z_0^2 + z_11z_0/n+z_22z_0/n+z_33z_0/n
    z_11z_0/n-1+z_22z_0/n-1+z_33z_0/n-1   ≤ z_0^2 + z_11z_0/n+z_22z_0/n+z_33z_0/n

In the language of spins, as used in <cit.>, the moments can be expressed in terms of the spin expectation values as

    z_1    = 2⟨ J_x ⟩
    
            z_2    = 2⟨ J_y ⟩
    
            z_3    = 2⟨ J_z ⟩
    
            z_11   = 4⟨ J_x^2 ⟩ - n
    
            z_22   = 4⟨ J_y^2 ⟩-n
    
            z_33   = 4⟨ J_z^2 ⟩-n

The first of the conditions (<ref>) reads 2Δ J_x^2 + 2Δ J_y^2 + 2Δ J_z^2 ≥ n where Δ J_x^2 = ⟨ J_x^2 ⟩ - ⟨ J_x⟩^2. The last one reads  4⟨ J_x^2⟩ + 4⟨ J_y^2⟩ +4⟨ J_z^2⟩≤ n(n+2). These two conditions are trivial, i.e., satisfied by all quantum states, including entangled states. The remaining six inequalities can be viewed as two sets of permutatively related related inequalities:

    4(n-1)(Δ J_y^2 + Δ J_z^2 )   ≥ n(n-2) + 4 ⟨ J_x^2 ⟩, 
    
            4(n-1)(Δ J_x^2 + Δ J_z^2 )   ≥ n(n-2) + 4 ⟨ J_y^2 ⟩, 
    
            4(n-1)(Δ J_y^2 + Δ J_x^2 )   ≥ n(n-2) + 4 ⟨ J_z^2 ⟩,

and

    4(n-1)Δ J_x^2    ≥  4( ⟨ J_y^2 ⟩ + ⟨ J_z^2 ⟩ ) - 2n 
    
            4(n-1)Δ J_y^2    ≥  4( ⟨ J_x^2 ⟩ + ⟨ J_z^2 ⟩ ) - 2n 
    
            4(n-1)Δ J_z^2    ≥  4( ⟨ J_y^2 ⟩ + ⟨ J_x^2 ⟩ ) - 2n

This is a set of necessary conditions for non-entanglement, which appeared in <cit.>. 
Violation of at least one of the above inequalities is sufficient for entanglement. The necessary conditions for entanglement are obtained by the violation of the sufficient conditions for membership in the moment cone, which are given by replacing z_0 by n-1/nz_0. The resulting conditions can also be arranged with regards to permutative relations:

    4(n-1)(Δ J_y^2 + Δ J_z^2 )   ≥ n^2-n-1 + 4 (⟨ J_x^2 ⟩+⟨ J_y ⟩^2+⟨ J_z ⟩^2), 
    
            4(n-1)(Δ J_x^2 + Δ J_z^2 )   ≥ n^2-n-1 + 4 (⟨ J_y^2 ⟩+⟨ J_x ⟩^2+⟨ J_z ⟩^2), 
    
            4(n-1)(Δ J_y^2 + Δ J_x^2 )   ≥ n^2-n-1 + 4 (⟨ J_z^2 ⟩+⟨ J_y ⟩^2+⟨ J_x ⟩^2),

And

    4(n-1)Δ J_x^2    ≥  4( ⟨ J_y^2 ⟩ + ⟨ J_z^2 ⟩ +⟨ J_x ⟩^2 ) - (n+1), 
    
            4(n-1)Δ J_y^2    ≥  4( ⟨ J_x^2 ⟩ + ⟨ J_z^2 ⟩ +⟨ J_y ⟩^2 ) - (n+1), 
    
            4(n-1)Δ J_z^2    ≥  4( ⟨ J_y^2 ⟩ + ⟨ J_x^2 ⟩  +⟨ J_z ⟩^2) - (n+1).


In conclusion, the relation between entanglement and real algebraic geometry and the method presented in this paper are quite general and can be used to develop entanglement criteria for other settings of many-body systems <cit.>. For instance one can consider other physically relevant symmetries of the measure such as a system with 2n atoms with an S_n × S_n symmetry, also known as mode-split entanglement <cit.>.




 §.§ Acknowledgements


Grigoriy Blekherman was partially supported by NSF grant DMS-1352073. Bharath Hebbe Madhusudhana was supported by NSF grant NSF PHYS-1506294. We thank Michael Chapman and Brian Kennedy for providing insights from a physical perspective. We also thank Matthew Boguslawski, Maryrose Barrios and Lin Xin for useful discussions.


unsrt

