Zvi Rosen

AND Georgy Scholten
email: ghscholt@ncsu.edu

Cynthia Vinzant
email: clvinzan@ncsu.edu

SPARSE MOMENTS OF UNIVARIATE STEP FUNCTIONS AND ALLELE FREQUENCY SPECTRA

We study the univariate moment problem of piecewise-constant density functions on the interval [0, 1] and its consequences for an inference problem in population genetics. We show that, up to closure, any collection of n moments is achieved by a step function with at most n -1 breakpoints and that this bound is tight. We use this to show that any point in the nth coalescence manifold in population genetics can be attained by a piecewise constant population history with at most n -2 changes. Both the moment cones and the coalescence manifold are projected spectrahedra and we describe the problem of finding a nearest point on them as a semidefinite program.

.

In this paper we study moments coming from piecewise-constant density functions with the idea of minimizing the number of pieces needed. Formally, we consider the set M k (A) as the closure of the set of moments (m a ) a∈A where m a = 1 0 x a f (x)dx and f is a nonnegative step function with at most k discontinuities. Our main theorem is the following:

This is the content of Theorem 1.5 and Corollary 1.12. The proof involves studying the convex algebraic boundary of these cones and in particular showing that they are simplicial (Corollary 1.9). When restricting to the moments of monotone density functions, only half as many break points are needed (see Propositions 2.4 and 2.5).

. The coalescence manifold C n,k , formally defined in Section 3, is a set of summary statistics in population genetics, derived from observing n genomes with a population history consisting of k + 1 different population sizes. Our last main theorem, appearing as Theorem 3.5, is that the coalescence manifold C n,k coincides with an affine section of the moments M k (A) for A = {0, 2, . . . , n 2 -1}. Main Theorem 3. The coalescence manifold C n,k is the intersection of M k (A) with the affine hyperplane of points with coordinate sum equal to one for

 show that the manifold C n,k stabilizes at k = 2n -2, i.e. C n,2n-2 = C n,k for all k ≥ 2n -2. Together, the main theorems above improve this bound by a factor of two, showing that the coalescence manifolds stabilize at k = n -2 and this bound is tight.

The connection with the moment problem also provides a description of C n,n-2 as the projection of a spectrahedron. The problem of finding the nearest point in C n,n-2 to a given point in R n-1 can then be formulated as a semidefinite program.

This paper is organized as follows. In Section 1, we introduce formal definitions of the moment sets M k (A), study their convex and algebraic structure, and prove Theorem 1. In Section 2, we analyze analogous questions for moment problems coming from monotone step functions. The definitions and connections with the coalescence manifold C n,k are given in Section 3. Semidefinite descriptions of these sets are discussed in Section 4. Finally we end with a discussion of open problems surrounding these interesting sets in Section 5.

Moments of step functions

For k ∈ N, let S k denote the set of nonnegative step functions on [0, 1] of the form (1)

f = y 1 1 [0,s 1 ] + k+1 i=2 y i 1 (s i-1 ,s i ] ,
where 0 = s 0 < s 1 < . . . < s k < s k+1 = 1 and y 1 , . . . , y k+1 ∈ R ≥0 . Note that:

(1) S k is invariant under nonnegative scaling, (2) S k ⊆ S when k ≤ , and

(3) S k + S , defined as {f + g | f ∈ S k , g ∈ S }, is a subset of S k+ . Elements of S k define nonnegative measures on [0, 1]. We will be interested in the possible moments of these measures. Given a finite collection A ⊂ N, we define to be the Euclidean closure of the set moments given by density functions in S k :

M k (A) = 1 0 x a f (x)dx a∈A : f ∈ S k .
One important case is that of consecutive moments A = {0, 1, . . . , d}. For any finite collection A ⊂ N, the moment cone M k (A) can be expressed, up to closure, as the image of M k ({0, 1, . . . , max(A)}) under the coordinate projection π A : R max(A)+1 → R A given by π A (m 0 , . . . , m max(A) ) = (m a ) a∈A .

Remark 1.1. By linearity of the integral, we see that M k (A) inherits many properties of S k . That is, M k (A) is invariant under nonnegative scaling, M k (A) ⊆ M (A) when k ≤ and M k (A) + M (A) ⊆ M k+ (A) (here, in the sense of the Minkowski sum), as desired.

We will be interested in comparing this to the full moment cone: The cone M (A) is dual to the convex cone of univariate polynomials supported on A that are nonnegative on [0, 1], as will be discussed below in Proposition 1.6. When 0 ∈ A, the closure in the definition of M (A) is not necessary, and the extreme rays of M (A) are come from point evaluations. That is, we can write M (A) as the conical hull of the image of [0, 1] under the corresponding moment map:

M (A) =
M (A) = conicalHull {v A (t) : t ∈ [0, 1]} where v A (t) = (t a ) a∈A .
See, for example, [START_REF] Schmüdgen | The moment problem[END_REF]Prop. 10.5].

When 0 / ∈ A, this equality only holds up to closure, as the curve parametrized by v A (t) includes the origin. In this case, M (A) = conicalHull {v A (t) : t ∈ [0, 1]}. As we will see below, then we can still write M (A) as the conical hull of a curve segment. Specifically, M (A) = conicalHull {v B (t) : t ∈ [0, 1]} where B = {amin(A) : a ∈ A}. Proof. For t ∈ (0, 1], the point v A (t) can be rewritten as t min(A) v B (t), a scalar multiple of v B (t). It follows that the conical hulls of {v A (t) : t ∈ (0, 1]} and {v B (t) : t ∈ (0, 1]} are equal. We observe that the extreme ray v B (0) of M (B) can be attained in the closure of M (A) as the limit of the moment of the step function f = -(min(A)+1) 1 [0, ] as goes to zero: if a = min(A) 0 otherwise.

It follows that v B (0) belongs to M (A). Since M (B) can be written as the union of the cone over v A (t) for t ∈ (0, 1] and the ray over v B (0), the equality between the two cones ensues:

M (A) = conicalHull {v A (t) : t ∈ [0, 1]} = M (B). Example 1.3. Consider A = {1, 2} and B = {0, 1}. Then M (B) = conicalHull{(1, t) : t ∈ [0, 1]} = conicalHull{(t, t 2 ) : t ∈ [0, 1]} = M (A).
Here we see the need for taking closures when 0 ∈ A. The point (1, 0) = v B (0) is not contained in the the conical hull of the curve segment {(t, t 2 ) : t ∈ [0, 1]} but is contained in its closure. See Figure 1. In this case, the boundary of M (A) = M (B) consists of scalar multiples of v B (0) and v B (1), both of which belong to M 1 (A), by Proposition 1.4 below. Arguments below will then show that M (A) = M 1 (A).

Proposition 1.4. Let A ⊂ N be finite and let B = {amin(A) : a ∈ A}. The points v B (0)and v B (1) belong to M 1 (A) and for every t ∈ (0, 1), v B (t) belongs to M 2 (A).

Proof. For 0 < t < 1, and 0 < < 1t consider the step function f = -1 t -min(A) 1 (t,t+ ] in S 2 . By continuity, the integral 1 0 x a f (x)dx limits to t a-min(A) as → 0, thus M 2 (A) contains the limit point v B (t) = (t b ) b∈B . Similarly, the limit as → 0 of the A-moment vectors of step functions f = (min(A) + 1) -1-min(A) 1 [0, ] and f = -1 1 (1-,1] in S 1 are v B (0) and v B (1), respectively. Therefore these vectors belong to M 1 (A).

A corollary of this statement is that M k (A) = M (A) for k = 2|A|. By Carathéodory's Theorem, any point in M (A) is in the conical hull of at most |A| points of the form (t a ) a∈A where t ∈ [0, 1], each of which belongs to M 2 (A) by Proposition 1.4. By Remark 1.1, the sum of |A| elements from M 2 (A) belongs to M 2|A| (A), giving M (A) ⊆ M 2|A| (A). In fact, M k (A) fills out the whole moment cone much sooner:

Theorem 1.5. If k ≥ |A|-1, M k (A) = M (A).
The proof of this theorem relies on understanding the points on the boundary of M (A).

Proposition 1.6. Let A ⊂ N be finite with 0 ∈ A. If m = (m a ) a∈A belongs to the Euclidean boundary of M (A), then any representing measure µ on [0, 1] with m a = x a dµ has finite support. Specifically, the support of µ is a subset of the roots contained in [0, 1] of a polynomial nonnegative on [0, 1] and of the form p(x) = a∈A p a x a . The vector m is a conic combination of the vectors v A (r) where r ranges over the roots of p.

Proof. Let : R A → R be a linear function (v) = a∈A p a v a defining a supporting hyperplane of M (A) at m. That is, (v) ≥ 0 for all v ∈ M (A) and (m) = 0. Consider the polynomial p(x) = (v A (x)) = a∈A p a x a . Since v A (t) ∈ M (A) for all t ∈ [0, 1], p is nonnegative on [0, 1]. Furthermore, for any measure µ with moments m,

p(x)dµ = a∈A p a m a = (m) = 0.
The measure µ is nonnegative and the polynomial p is nonnegative on [0, 1]. From this we see that the support of the measure µ must be contained in the (finite) set of roots R of p(x). Specifically, µ = r∈R w r δ r for some w r ∈ R ≥0 ; therefore, m = r∈R w r v A (r).

Proof of Theorem 1.5. First, consider a point m in the boundary of M (A). By Lemma 1.2, M (A) = M (B) where B = {amin(A) : a ∈ A}, and so m also belongs to the boundary of M (B). By Proposition 1.6, m is the vector of B-moments of a measure µ supported on the roots of a nonnegative polynomial on [0, 1] of the form p(x) = a∈B p a x a . Let b be the number of distinct roots of p in the set {0, 1} and i be the number of distinct roots in of p in the open interval (0, 1). Then m is in the conical hull of the b + i points given by v B (r) where r ranges over these roots. By Proposition 1.4, m belongs to M k (A) for k = b + 2i.

By Descartes' rule of signs, the number of positive roots of p, counting multiplicity, is at most the number of sign changes in the list of coefficients {p a } a∈B . If p 0 = 0, then p has at most |B|-1 roots in R >0 . If p 0 = 0, then p is the sum of at most |B|-1 nonzero terms and its number of roots in R >0 must be smaller or equal to |B|-2. Note that every root of p in (0, 1) must have even multiplicity greater or equal to 2. All together this gives b + 2i ≤ |B|-1 = |A|-1. Now consider m in the interior of M (A). Let c = (1/(a + 1)) a∈A ∈ M 0 (A) denote the vector obtained by integrating against the constant step function of height one. Let λ * be the maximum value of λ ∈ R for which mλc belongs to M (A). From m ∈ M (A), we see that λ * ≥ 0. Moreover, since M (A) is pointed, -c does not belong to M (A), meaning that for sufficiently large λ, mλc does not belong to M (A). Since M (A) is closed, it follows that such a maximum λ * must exist.

The point mλ * c belongs to the boundary of M (A). By the arguments above, mλ * c belongs to M k (A) for k ≥ |A|-1. Since c ∈ M 0 (A) and

m = (m -λ * c) + λ * c, the point m also belongs to M k (A) for k ≥ |A|-1.
Remark 1.7. It follows from the proof of Theorem 1.5 that for all k ≥ 0, M k (A) is star convex with respect to the point c = (1/(a + 1)) a∈A , the A-moment of the constant function. Indeed, since c belongs to M 0 (A), λc + M k (A) ⊆ M k (A) for all λ ≥ 0.

We can go further in characterizing the facial structure of the boundary of M (A). Through a connection to Schur polynomials, we can deduce linear independence among sets of points from the curve of the correct size.

Proposition 1.8. For a collection A of integers 0 = a 1 < a 2 < . . . < a n and any real values 0 ≤ r 1 < r 2 < . . . < r n ≤ 1, the determinant of the matrix S A is strictly positive, where Proof. By the bialternant formula for Schur polynomials, the determinant of the matrix S A (r) can be expressed as

S A (r) =     1 1 . . . 1 r a 2 1 r a 2
(2) det(S A ) = 1≤i<j≤n (r j -r i ) s λ (r 1 , . . . , r n ) for λ = (a n -(n-1), a n-1 -(n-2), . . . , a 1 ),
where s λ (x 1 , . . . , x n ) denotes the Schur polynomial associated to the partition λ. By definition, the Schur polynomial s λ (x 1 , . . . , x n ) is the sum of monomials x T over all semistandard Young tableaux T of shape λ. One can observe, either from expanding the determinant of S A (r) along the first column, or by filling out a semistandard Young Tableau of shape λ without using the number 1, that x 1 does not appear in all the monomials of the determinant of S A . It follows that det(S A ) is strictly positive for any 0 ≤ r 1 < r 2 < . . . < r n ≤ 1.

Corollary 1.9. All proper faces of M (A) are simplicial.

Proof. By Lemma 1.2, we can assume that 0 ∈ A. Recall that M (A) is the conical hull over the curve segment {v A (t) : t ∈ [0, 1]} and any proper face F of this cone can be expressed as the conical hull of some points v A (r 1 ), . . . , v A (r k ) where 0 ≤ r 1 < r 2 < . . . < r k ≤ 1. If k > dim(F ), then there is a subset of these points of size dim(F ) + 1 ≤ n, which necessarily lie in F and are therefore linearly dependent, contradicting Proposition 1.8. Therefore k = dim(F ) and F is simplicial.

This lemma lets us assign an index to points on the boundary of M (A), following [START_REF] Schmüdgen | The moment problem[END_REF]Ch. 10.2]. Let m be a point on the boundary of M (A). By Corollary 1.9, there is a unique representation of m as k j=1 w j v A (r j ) where 0 ≤ r 1 < . . . < r k ≤ 1 and w 1 , . . . , w k ∈ R >0 . We define the index of m, denoted ind(m), to be b + 2i where b = #{j : r j ∈ {0, 1}} and i = #{j : r j ∈ (0, 1)}. By Proposition 1.4, any point m on the boundary of M (A) belongs to M ind(m) (A).

To prove the converse, we must rule out the possibility that m ∈ M k (A) for k < ind(m). In other words, it is impossible to approach a point m on the boundary of M (A) with moment vectors of step functions with fewer breakpoints than expected.

Lemma 1.10. Let m be a point on the boundary of M (A).

For k < ind(m), m ∈ M k (A). That is, if m ∈ M k (A), then ind(m) ≤ k.
Proof. Note that for any non-zero point m in M (A), m 0 > 0 and so we can rescale m to have m 0 = 1. We will write M k (A) ∩ {m 0 = 1} as the image of a compact polytope under a polynomial map and check that any point m in the image of this map and the boundary of

M (A) has index ≤ k. Any function f ∈ S k can be written as f = y 1 1 [0,s 1 ] + k+1 i=2 y i 1 (s i-1 ,s i ]
for some values 0 = s 0 < s 1 < . . . < s k < s k+1 = 1 and y i ≥ 0 for all i. We now introduce transformed w-coordinates by letting w i = y i (s is i-1 ) denote the area

s i s i-1 f (x)dx. The corresponding moment in M k (A) is given by the image of the point (s, w) = (s 1 , . . . , s k , w 1 , . . . , w k+1 ) under the polynomial map (3) µ A (s, w) = k+1 i=1 y i s a+1 i -s a+1 i-1 a + 1 a∈A = k+1 i=1 w i (s a i + s a-1 i s i-1 + • • • + s a i-1 ) a + 1 a∈A .
Note that the constraint that m 0 = 1 translates into i w i = 1. Consider the polytope

(4) P = (s, w) ∈ R k × R k+1 such that 0 ≤ s 1 ≤ . . . ≤ s k ≤ 1, w i ≥ 0, k+1 i=1 w i = 1 ,
which is a product of two simplices of dimension k. The moments of step functions f ∈ S k with f (x)dx = 1 is the image under µ A of the set of points (s, w) ∈ P with distinct 0 < s 1 < . . . < s k < 1. Its closure is M k (A) ∩ {m 0 = 1}, which necessarily coincides with the image of P under µ A , as the image of a compact set under a continuous map is closed.

If w i > 0 and s i-1 < s i for some i, then µ A (s, w) has a representing measure whose support includes the interval (s i-1 , s i ] and is therefore not finite. Then by Proposition 1.6, m belongs to the interior of M (A).

Suppose the point m belongs to M k (A). Then m = µ A (s, w) for some (s, w) ∈ P . Let I denote the collection of indices 1 ≤ i ≤ k for which w i > 0. If m belongs to the boundary of

M (A), s i-1 = s i for all i ∈ I. Then m = µ A (s, w) = i∈I w i v A (s i ).
We can bound ind(m) by bounding the number of distinct values of s i that appear. For each i ∈ I with s i ∈ (0, 1), s i equals s i-1 , hence there are at least two indices j in {1, . . . , k} for which s j = s i . Trivially, if s i ∈ {0, 1}, there is at least one j ∈ {1, . . . , k} such that s j = s i .

Together, these show that

ind(m) = #{s i ∈ {0, 1} : i ∈ I} + 2 • (#{s i ∈ (0, 1) : i ∈ I}) ≤ k. Lemma 1.11. The intersection of M k (A) with the Euclidean boundary of M (A) is a semi- algebraic set of dimension ≤ k.
Proof. By Lemma 1.10, the intersection of M k (A) with the Euclidean boundary of M (A) is the set of boundary points of index ≤ k. We can parametrize this as the union of the semialgebraic sets:

σ∈{0,1} 2 j=1 w j v A (r j ) + w +σ 1 v A (0) + w +σ 1 +σ 2 v A (1) : r ∈ (0, 1) , w ∈ (R >0 ) +σ 1 +σ 2 ,
where in each set, is chosen so that 2 + σ 1 + σ 2 ≤ k. Here we use r to denote the vector (r j ) j and w for the vector (w j ) j . Note that each set is the image of (0, 1) n × (R >0 ) m under a polynomial map where n + m ≤ k and therefore has dimension ≤ k.

Corollary 1.12. Step functions with one breakpoint and total mass one can be parametrized by f = w s 1 [0,s] + 1-w 1-s 1 (s,1] for s ∈ (0, 1) and w ∈ [0, 1]. Note that fixing w and taking the limit as s → 0 gives a weighted sum of a point mass at zero and the constant function

If k < |A|-1, M k (A) = M (A). Proof. The cone M (A) is full-dimensional in R |A| ,
wδ 0 + (1 -w)1 (0,1] . Similarly s → 1 gives w1 [0,1) + (1 -w)δ 1 .
For s = w ∈ [0, 1], the corresponding step function is constant, i.e. f = 1 [0,1] and the moment map sends this line segment to a single point. However, away from this line, the moment map is a homeomorphism to its image in M 1 ({0, 2, 5}). Example 1.14. Consider A = {0, 2, 5, 9}. To visualize the moment sets M k (A), we consider their intersections with the affine hyperplane {m 0 = 1}. Affine transformations of these intersections are shown in Figure 3. Note that the step functions with at most one breakpoint and total mass one can be written as λ1

[0,1] + (1 -λ) 1 s 1 [0,s] or λ1 [0,1] + (1 -λ) 1 1-s 1 (s,1] where λ ∈ [0, 1].
The result is a two-dimensional surface in the plane {m 0 = 1}. The set M 2 (A) is full-dimensional, but does not fill up all of M (A). As promised by Lemma 1.11, the intersection M 2 (A) with the boundary of M (A) has dimension ≤ 2, so its image in {m 0 = 1} has dimension ≤ 1. Indeed, we see this intersection is given by the curve parametrized by (t 2 , t 5 , t 9 ) for t ∈ [0, 1] and the line segment between its end points (0, 0, 0) and (1, 1, 1). Finally, by Theorem 1.5, M 3 (A) is the full cone M (A). Points on the boundary of M (A) have index ≤ 3, and so have one of the two forms

w 0 v A (0) + w r v A (r) or w 1 v A (1) + w r v A (r) where r ∈ [0, 1], w 0 , w 1 , w r ∈ R ≥0 . Figure 3. The sets M 1 (A), M 2 (A), M 3 (A) in {m 0 = 1} for A = {0, 2, 5, 9}.
We will now take a closer look at this example, paying close attention to the boundary of the domain and its image in M 2 (A). The domain is the set of step functions with two breakpoints, so it lives in the product of two 2-simplices

P = {(s 1 , s 2 ) : 0 ≤ s 1 ≤ s 2 ≤ 1} × {(w 1 , w 2 , w 3 ) ∈ R 3 ≥0 : w 1 + w 2 + w 3 = 1}.
Here the s variables parametrize the two breakpoints and the w variables parametrize the proportion of mass in each piece. So the domain is four-dimensional while the image has dimension three. Therefore the generic fiber of the moment map has dimension one.

We can however obtain a generically finite-to-one map by restricting to facets of the polytope P . The boundary is composed of six triangular prisms given by s 1 = 0, s 2 = 1, s 1 = s 2 , w 1 = 0, w 2 = 0, and w 3 = 0. We can visualize this by way of a Schlegel diagram via one of its facets, seen in Figure 4.

In observing the moment map restricted to the boundary, we make a number of observations. There are four 2-faces that the moment map collapses to a curve, namely the faces given by 0 = s 1 = s 2 , s 1 = s 2 = 1, w 1 = w 2 = 0, and w 2 = w 3 = 0. In addition to these 2-faces, the intersections of the facets of P with the hypersurfaces given by y 1 = y 2 and y 2 = y 3 sometimes drop dimension under the moment map µ A . In the (s, w) variables, these correspond to surfaces (s 2s 1 )w 1 = s 1 w 2 and (1s 2 )w 2 = s 2 w 3 , respectively. For example, in each of the facets s 1 = 0 and w 1 = 0, the equation (1s 2 )w 2 = s 2 w 3 cuts out a surface whose image under µ A is a curve. For the face s 1 = 0, the moments of this surface collapse to the line segment connecting the constant population and the point mass at 0 and for w 1 = 0, the image of this surface collapses to the curve segment of moments of step functions of a single step with w 1 = 0. Similarly, the faces s 2 = 1 and w 3 = 0 each Aside from these subsurfaces, the map on the boundary ∂P is locally nondegenerate. Interestingly, the images of these facets can overlap in full-dimensional sets. One consequence is that the fibers of the moment map can be disconnected. For example, the point (m 0 , m 2 , m 5 , m 9 ) = (1, 0.164, 0.054, 0.031) belongs to M 2 (A) for A = {0, 2, 5, 9}. Its fiber under µ A is a curve in the four-dimensional polytope P from (4). Figure 5 shows the (s 1 , s 2 )-coordinates of this curve. In particular, this fiber has at least two connected components. In a lighter shade is the two-dimensional fiber of the point (m 0 , m 2 , m 5 ) = (1, 0.164, 0.054) under the corresponding map for {0, 2, 5}.

(s 1 , s 2 ) = (0, 0) (0, 1) (1, 1) (w 1 , w 2 , w 3 ) = (1, 0, 0) (0, 1, 0) (0, 0, 1)
s 1 = 0 w 3 = 0 s 2 = 1 w 2 = 0 s 1 = s 2 w 1 = 0

Increasing and decreasing step functions

In this section, we study the moment cones of non-negative monotone functions on the unit interval [0, 1]. We define the increasing and decreasing moment cones

M ↑ (A) = 1 0
x a f (x)dx a∈A : f is nonnegative and increasing on [0, 1] and

M ↓ (A) = 1 0 x a f (x)dx a∈A : f is nonnegative and decreasing on [0, 1] . Recall that if a function f : [0, 1] → R is monotone, then it is automatically Borel-measurable.
As in the non-monotone case, all of these moment vectors can be achieved as a limit of moments of step functions with a bounded number of steps. For k ∈ N, let S ↑ k denote the set of nonnegative, increasing step functions on [0, 1] with at most k discontinuities. Similarly, let S ↓ k denote the analogous set of decreasing step functions. This corresponds to requiring y 1 ≤ y 2 ≤ . . . ≤ y k+1 or y 1 ≥ y 2 ≤ . . . ≥ y k+1 in [START_REF] Bhaskar | Descartes' rule of signs and the identifiability of population demographic models from genomic variation data[END_REF].

Similarly, for finite A ⊂ N, we consider the A-moments of these step functions,

M k (A) = 1 0 x a f (x)dx a∈A : f ∈ S k for ∈ {↑, ↓} .
Just as with M k (A), we see that the set M k (A) is invariant under nonnegative scaling,

M k (A) ⊆ M (A) when k ≤ and M k (A) + M (A) ⊆ M k+ (A).
As in the non-monotone case, we can understand the cones M (A) as the conical hull of curve segments. Definition 2.1. We define maps γ ↑ A and γ ↓ A from [0, 1] to R A where, for t ∈ [0, 1], γ ↑ A (t) and γ ↓ A (t) are the A-moment vectors of the step functions (1/(1t))1 (t,1] and (1/t min(A)+1 )1 [0,t] , respectively. For every a ∈ A, the ath coordinate of these maps are given by

γ ↑ A (t) a = 1 1 -t 1 t x a dx = 1 a + 1 a i=0 t i and γ ↓ A (t) a = 1 t min(A)+1 t 0 x a dx = 1 a + 1 t a-min(A) .
We observe that γ ↑ A (0) = γ ↓ A (1) = (1/(a + 1)) a∈A corresponds to the moment vector of constant function 1 [0,1] . The other end points correspond to point masses. Specifically,

γ ↑ A (1) = v A (1) is the moment vector of a point mass at t = 1 and γ ↓ A (0) = 1 min(A)+1 v B (0) for B = {a -min(A) : a ∈ A} corresponds to a point mass at t = 0.
Remark 2.2. The conical hull over {γ A (t) : t ∈ [0, 1]} is closed because this curve is compact and does not contain the origin. Indeed, for =↑, the ath coordinate of γ ↑ A (t) is ≥ (1/a + 1) for all t. For =↓, the min(A)-th coordinate of γ ↓ A (t) is identically 1/(min(A) + 1). Lemma 2.3. For ∈ {↑, ↓}, the cone M (A) equals the conical hull of {γ A (t) : t ∈ [0, 1]}.

Proof. Since M (A) is a convex cone containing the point γ A (t) for all t, it automatically contains the conical hull of this curve.

For the other direction, consider a monotone function f : [0, 1] → R. We can construct a sequence of step functions f n converging uniformly to f on [0, 1]. For example, we may take

f n = n i=1 M n 1 T i where M ∈ {f (0), f (1)} is the maximal value of f on [0, 1] and 1 T i is the indicator function of T i = {x ∈ [0, 1] : f (x) ≥ iM/n}. That is f n (x) = M n • n M f (x)
. Note that |f nf |≤ M/n and so f n converges uniformly to f on [0, 1]. It follows that for any a, x a f n converges uniformly to x a f and so the integral 1 0 x a f n (x)dx converges to 1 0 x a f (x)dx. Note that the set T i defined above has the form (s i , 1] or [s i , 1] if f is increasing and [0, s i ] or [0, s i ) if f is decreasing for some s i ∈ [0, 1]. The moment vector of f n therefore is a conic combination of the points γ A (s i ) for the appropriate ∈ {↑, ↓}. Taking n → ∞ shows that the moment vector of f belongs to the closure of the conical hull of {γ A (t) : t ∈ [0, 1]}.

Therefore the moment cone {( 1 0 x a f (x)dx) a∈A : f nonnegative and increasing on [0, 1]} belongs to the closure of the conical hull of {γ ↑ A (t) : t ∈ [0, 1]}. By definition, M ↑ (A) is the closure of this set and so also belongs to the closure of this conical hull. Similarly M ↓ (A) belongs to the closure of the conical hull of {γ ↓ A (t) : t ∈ [0, 1]}. By Remark 2.2, both of these conical hulls are already closed.

Proposition 2.4. If k ≥ |A| 2 , then we have M ↑ k (A) = M ↑ (A) and M ↓ k (A) = M ↓ (A).
Proof. Our proof proceeds similarly to that of Theorem 1.5. Let m be a point of the boundary of M (A). We want to express m as the A-moment of an increasing step function of the fewest steps possible. Let : R A → R define a supporting hyperplane of M (A) at m, so that ≥ 0 on M (A) and (m) = 0. By Lemma 2.3, M (A) is the conical hull of a curve, hence m will lie in the conical hull of points on this curve with = 0. We use this to show that m belongs to Proof. The cone M k (A) ⊂ R |A| is a conic combination of k points on the boundary curve γ A , each contributing two degrees of freedom, and the point corresponding to the image of the constant step function γ ↑ A (0) = γ ↓ A (1), contributing a single degree of freedom. Therefore, the semialgebraic set M k (A) has dimension at most min {2k + 1, |A|}. The cone M (A) is full-dimensional in R |A| . Let n = |A|/2 so that |A| is 2n or 2n + 1. In either case, we observe that for k ≤ n -1, the dimension of M k (A) is less than or equal to 2n -1, hence it cannot fill up all of M (A).

M k (A) for k ≥ |A| 2 . (↓) Let p(x) = γ ↓ A (x) =
Example 2.6. For A = {0, 2, 5, 9}, M 1 (A) is a union of M ↑ 1 (A) and M ↓ 1 (A), shown on the left in Figure 3. Since 1 < 2 = |A|/2 , these sets are not full dimensional and so cannot fill up

M ↑ (A) or M ↓ (A). For k = 2 = |A|/2 , M ↑ 2 (A) = M ↑ (A) and M ↓ 2 (A) = M ↓ (A)
. These form parts of the full dimensional set M 2 (A) shown in the middle of Figure 3.

Connection with coalescence manifold

The motivation for studying moments of step functions comes from the field of population genetics. A central problem in this area is: Question 3.1. Given a sample of n genomes from a present-day population, what inferences can be drawn regarding the history of that population?

Our approach to the problem is to fix a function p(t) describing effective population size at time t before the present. We then compute, as a function of p, a vector of invariants c associated to the genome sample. Understanding the relationship between p and c will allow us to infer likely values of p based on measured data.

Following [START_REF] Bhaskar | Descartes' rule of signs and the identifiability of population demographic models from genomic variation data[END_REF], we model the natural process of the production of a sample of n genomes as follows:

• The genealogical tree connecting n individuals will be formed by taking coalescence of each pair of lineages as a Poisson point process with rate parameter 1/p(t), where p(t) is the effective population size at time t before present. (Heuristically, looking at the previous generation and picking parents at random, there is a 1/p(t) chance that two lineages will pick the same parent.) • After the tree is specified, mutations are distributed on the tree as a Poisson point process with constant rate relative to branch length. The infinite-sites model is used, so that repeated mutation at a given site is disallowed, which is a good model for large genomes.

Definition 3.2. Fixing a population history, and defining the random process as above, we define random variables:

• The sample frequency spectrum (also known as the site or allele frequency spectrum), abbreviated SFS, is the vector of random variables (X n,b ) b=1,...,n-1 where X n,b denotes the number of mutations that are shared by exactly b out of the n individuals. • The coalescence vector is the vector (T i,i ) i=2,...,n-1 of the time at which a sample of size i has exactly i distinct lineages, i.e. the time until the first coalescence. For a fixed population function p, taking expectations gives the population invariants

ξ n,b = E[X n,b ] and c i = E[T i,i ].
In practice, the SFS is more frequently discussed as a summary statistic, but the coalescence vector is simpler to use in computations. Fortunately, Polanski and Kimmel [START_REF] Polanski | New explicit expressions for relative frequencies of single-nucleotide polymorphisms with application to statistical inference on population growth[END_REF] proved that they are related by a linear transformation A n , a matrix entirely determined by sample size n. Therefore, we focus on the coalescence vectors (c i ). Fact 3.3. We make the reasonable assumption that p(t) is bounded below by 0 and bounded above by a fixed P . Applying integration by parts and change of variables to the expected value of an exponential distribution yields the following expression for c i in terms of p(t):

(5)

c i (p) = ∞ 0 p(τ ) exp - i 2 τ dτ,
where p(τ ) = p(R -1 p (τ )) and R p (t) = t 0 1 p(x) dx. Because 0 < p(t) < P , the function R p is strictly increasing and unbounded; thus, it is a bijection from R ≥0 → R ≥0 , so the inverse is well-defined. We call p(τ ) the transformed population history.

The coalescence vector can thus be considered a function from the space of (bounded) population history functions to R n-1 . Since the former space is infinite-dimensional and the latter is finite-dimensional, it is natural to restrict our attention to a finite-dimensional space of population history functions. A common choice for this, motivated by injectivity considerations in [START_REF] Bhaskar | Descartes' rule of signs and the identifiability of population demographic models from genomic variation data[END_REF], is Sk = {nonnegative step functions on R ≥0 with at most k breakpoints}. 5.

Because the vectors are normalized to have sum one, the coalescence manifold lives in the simplex ∆ n-1 . Note that this definition deviates slightly from the definition in [START_REF] Zvi | Geometry of the sample frequency spectrum and the perils of demographic inference[END_REF] by allowing k breakpoints instead of k epochs (i.e. constant intervals). This shifts the index down by one. We now connect back to the moment cones studied above. Theorem 3.5. Let A = { i 2 -1 : i = 2, . . . , n}. The coalescence manifold C n,k equals the intersection of the cone M k (A) with the affine hyperplane of points with coordinate sum equal to one:

C n,k = m ∈ M k (A) : a∈A m a = 1 .
Before we prove the theorem, we demonstrate two lemmas that will simplify the proof. Lemma 3.6. Define p(τ ) as in Equation 5. Then p(t) ∈ Sk if and only if if p(τ ) ∈ Sk .

Proof. Let 0 = s 0 < • • • < s k-1 < s k be the sequence of breakpoints of p(t). The function R p (t) is a monotone increasing function, so the conditions below are equivalent:

s j < t ≤ s j+1 ⇐⇒ R p (s j ) < R p (t) ≤ R p (s j+1 ).
Since p is constant on (s j , s j+1 ], the transformed history p(τ ) = p(R -1 p (τ )) is constant on (R p (s j ), R p (s j+1 )]. This implies that there are still at most k breakpoints.

For the reverse direction, repeat the argument with R -1 p in place of R p .

Lemma 3.7. Let q be a strictly positive step function in Sk . Then, there exists p in Sk such that q(τ ) = p(R -1 p (τ )) where R p (t) = t 0 1 p(x) dx as above.

Proof. Let Q(t) = t 0 q(x)dx. We claim the desired function is p(t) = q(Q -1 (t)). First, note that because q is strictly positive and takes only finitely many values, it is bounded away from zero. Therefore Q is strictly increasing and takes all values in [0, ∞). Its inverse Q -1 therefore exists and is also increasing with range [0, ∞). It follows that p takes the same values in the same order as q. In particular, p ∈ Sk .

To check that q(t) = p(R -1 p (t)), we first show that R p (Q(t)) = t for all t ≥ 0. By definition,

R p (Q(t)) = Q(t) 0 1 p(x) dx = Q(t) 0 1 q(Q -1 (x)) dx = t 0 1 q(w) q(w)dw = t,
where the penultimate equation comes from substituting x = Q(w) and dx = q(w)dw. Since both Q and R p are invertible, we see that

t = Q -1 (R -1 p (t)
) for all t. Applying q to both sides then gives the claim.

Proof of Theorem 3.5. We show that the set of coalescence vectors coming from population histories in Sk is equal to the set of moments in M k (A) summing to 1. The equality of the two closures is then automatic.

Assume p ∈ Sk . From Lemma 3.6, p is also in Sk . Starting with Equation 5, we substitute u = e -τ to obtain:

c i (p) = 1 0 p * (u)u ( i 2 )-1 du, where p * (u) = p(R -1 p (-ln(u))).
The function p * is piecewise-constant on [0, 1] with at most k breakpoints, so is in S k ; therefore, the quantity c i is the ( i 2 -1)-th moment of p * . This implies that c is in M k (A) where A = { i 2 -1 : i = 2, . . . , n}. Normalizing c is equivalent to scaling p * so we may assume its sum is already equal to 1.

Conversely, up to closure, any moment vector in M k (A) summing to 1 comes from some f ∈ S k . Changing our domain to R ≥0 gives q(τ ) = f (e -τ ) in Sk . By Lemma 3.7, we can produce p ∈ Sk that gives transformed population history q.

(t) = p 1 • 1 [0,b 1 ) + p 2 • 1 [b 1 ,b 2 ) + p 3 • 1 [b 2 ,∞) where p 1 , p 2 , p 3 , b 1 , b 2 ∈ R >0 with b 1 < b 2 . The function R p (t) is piecewise linear, given by R p (t) = t 0 1 p(x) dx = t p 1 1 [0,b 1 ) + t -b 1 p 2 + b 1 p 1 1 [b 1 ,b 2 ) + t -b 2 p 3 + b 2 -b 1 p 2 + b 1 p 1 1 [b 2 ,∞) .
This function is unbounded and strictly increasing with R p (0) = 0, so it has an inverse R -1 p that is also increasing and unbounded on R ≥0 . The function p(τ

) = p(R -1 p (τ )) is still piecewise constant with two break points R p (b 1 ) = b 1 /p 1 and R p (b 2 ) = (b 2 -b 1 )/p 2 + b 1 /p 1 , obtained by solving R -1 p (τ ) = b i .
The ith entry of the coalescence vector is then Remark 3.9. Note that because p(t) denote the population size at time t before the present, a population increasing over time corresponds to the function p(t) decreasing as a function of t, i.e. p 1 > p 2 > p 3 in the example above. Note that p(t) is decreasing in t if and only if p(τ ) is decreasing in τ . The parametrization u = e -τ reverses direction and so the function p * (u) is then increasing as a function of u. In these coordinates, u = 0 corresponds "infinitely long ago" (t = ∞) and u = 1 corresponds to the present (t = 0). Therefore coalescence vectors of populations growing over time are moments of increasing step functions on [0, 1].

c i = ∞ 0 p(τ )e ( i 2 )τ dτ = 1 0 p * (u)u ( i 2 )-

Connections with semidefinite programming

In this section, we describe how to write the moment cone M (A) and coalescence manifold C n,n-2 as projections of spectrahedra. This gives rise to natural algorithms for testing membership and finding nearest points in these sets based on semidefinite programming. Formally, a spectrahedron is a set of the form {x ∈ R n : A 0 + n i=1 x i A i 0} where A 0 , . . . , A n are real symmetric matrices and X 0 denotes that the matrix X is positive semidefinite. These are the feasible sets of semidefinite programs. See e.g. [START_REF] Blekherman | Semidefinite optimization and convex algebraic geometry[END_REF]Ch. 5 and 6]. Python code for computing the nearest point in C n,n-2 to an arbitrary point in R n-1 is available at: https://github.com/gescholt/DistanceToCoalescenceManifold is the projection of the points in M ({0, 1, . . . , d}) satisfying the affine linear equation a∈A m a = 1. The intersection of a spectrahedron with an affine linear space is again a spectrahedron and so C n,k is the projection of a spectrahedron.

The spectrahedron M ({0, 1, . . . , d}) is defined by two linear matrix inequalities of size ≤ d/2 + 1 ≤ n 2 /4. There are at most d + 1 = n 2 ≤ n 2 /2 variables. Similarly, given a point p ∈ R n-1 , we can use a semidefinite program to find the nearest point in C n,k for sufficiently large k. This comes from the description of C n,k above and the fact that distance minimization can be phrased as a semidefinite program (see, e.g. [START_REF] Boyd | Convex optimization[END_REF]). Specifically, given x ∈ R n-1 , the matrix n × n matrix λ xp (xp)

      λ m 0 -a m 2 -b m 5 -c m 9 -d m 0 -a 1 0 0 0 m 2 -b 0 1 0 0 m 5 -c 0 0 1 0 m 9 -d 0 0 0 1       0.
If (λ * , m * ) denotes the points achieving this minimum, then (m * 0 , m * 2 , m * 5 , m * 9 ) is the closest point in C 5,k to p with distance √ λ * .

Discussion and open questions

One takeaway from Section 1 is that the points on the boundary of C n,k for k ≥ n -2 correspond to moment vectors of point evaluations on [0, 1]. However these do not correspond to biologically meaningful population functions! Similarly, a point in the interior of C n,k can come from several different population functions, some of which are more biologically plausible than others. One natural question from this standpoint is how to pick the right population history from the fiber of a coalescence vector. Question 5.1. Given a point m in the interior of M k (A), how can we find the "best" step function f ∈ S k with moment vector m?

Here there is some natural flexibility in the notion of "best". Ideally it should be biologically plausible and also easy to compute. For plausibility, it might be reasonable to try to bound or minimize the ratios y i+1 /y i of consecutive population sizes. One step towards this would be to understand the structure of the fibers of the moment map µ A .

For k = 2 and A = {0, 2, 5}, the (s 1 , s 2 )-coordinates of the fibers of some points in M 2 (A) are shown below. To understand the fibers, it may also help to relate the combinatorial structure of the polytope P (which is a product of two k-dimensional simplices) to the semi-algebraic and combinatorial structure of M k (A). For example, the boundary of M 2 ({0, 2, 5, 9}), seen in Figure 3, comes from some of the two-dimensional faces of the four-dimensional polytope P . Question 5.2. How does the facial structure of P relate to the algebraic boundary of M k (A)? Finally, Section 4 gives an algorithm for testing membership in M (A), which coincides with M k (A) for k ≥ |A|-1. It would be desirable to be able to test membership for smaller k as well.

Question 5.3. Is there an effective method membership in M k (A) for < |A|-1?

These are may have complicated semialgebraic structure (Figure 3). One possibility is the following connection to low rank matrix completion would be interesting to explore further.

Consider a step function f = y 1 1 [0,s 1 ] + k+1 i=2 y i 1 (s i-1 ,s i ] in S k . In a slight abuse of notation, we define its derivative to be f = k i=1 (y i+1y i )δ s i , which is a signed weighted sum of delta functions. For j ∈ A, let m j denote the jth moment of the signed measure given by f :

m j = 1 0 x j f (x)dx = k i=1 (y i+1 -y i )(s i ) j .
One can check that for any j, m j = f (1)jm j-1 . In particular, we can write differences of consecutive moments of f in terms of moments of f , namely m j -m j+1 = (j +1)m j -jm j-1 .

In the case of full moments A = {0, 1, . . . , d}, this lets us bound the value of k by the rank of the moment matrix corresponding to the moments of (xx 2 )f (x). Specifically, for m ∈ R A , define the matrix This shows that M(m) is a sum of k rank-one matrices k i=1 (y i+1y i )(s is 2 i )v e (s i )v e (s i ) T , where e = (d -1)/2 and v e (t) = (1, t, t 2 , . . . , t e ) T . Therefore M(m) has rank ≤ k.

Note that if the values of y i are increasing then this is a sum of positive semidefinite rank one matrices, in which case the rank of M(m) will equal k, but if the values y i+1y i have different signs, this might not be the case. Regardless, this suggests the following approach. Question 5.5. Given (m a ) a∈A ∈ M (A), when does the following low-rank matrix completion find the minimum k for which (m a ) a∈A belongs to M k (A)?:

Minimize rank(M(m)) such that A(m) 0, B(m) 0.

Here A and B are the matrices introduced in Theorem 4.1 and the minimization is taken over all m ∈ R {0,1,...,max(A)} for which m a = m a for all a ∈ A.

While it seems unlikely that this will always give the correct value, it would be interesting to know how far off this value might be from the true minimal value of k.

1 0

 1 x a dµ a∈A : µ is a nonnegative Borel measure on [0, 1] .

Figure 1 .

 1 Figure 1. The cone M (A) along with the curve segments v A ([0, 1]) and v B ([0, 1]) for A = {1, 2} and B = {0, 1}.

Lemma 1 . 2 .

 12 If A ⊂ N is finite and B = {amin(A) : a ∈ A}, then M (A) = M (B).

2 . . . r a 2 n

 22

  in consequence, the cone's boundary is a hypersurface of dimension |A|-1. By Lemma 1.11, the dimension of the intersection of M k (A) with the boundary of M (A) has dimension ≤ k, so for k < |A|-1, this cannot be the entire boundary of M (A). Example 1.13. For A = {0, 2, 5}, Theorem 1.5 and Corollary 1.12 imply that M k (A) = M 2 (A) for all k ≥ 2 but not for k = 1. Affine transformations of their intersections with the affine hyperplane {m 0 = 1} are shown in Figure 2. See also [7, Figure 6]. The intersection of M 1 (A) with the boundary of M 2 (A) consists of just two rays, which appear as points in the hyperplane {m 0 = 1}. The set M 1 (A) consists of moments of functions with just one breakpoint.

Figure 2 .

 2 Figure 2. The parameter space of M 1 (A) and M 1 (A), M 2 (A) for A = {0, 2, 5}.

Figure 4 .

 4 Figure 4. Schlegel diagram for the boundary of P , together with the image of each facet under the moment map.

Figure 5 .

 5 Figure 5. A disconnected fiber of µ A for A = {0, 2, 5, 9}.

a∈A p a a + 1 x

 1 a-min(A) . The polynomial p is nonnegative on [0, 1].By Descartes' rule of signs, p has at most |A|-1 positive roots, counting multiplicity, and if p min(A) = 0, then it has at most |A|-2. Let i denote the number of distinct roots of p in (0, 1) and b = 1 if p(0) = 0 and 0 otherwise. Since each interior root of p must have multiplicity ≥ 2, this gives 2i+ b ≤ |A|-1. Note that γ ↓ A (t) ∈ M ↓ 1 (A) for all t ∈ [0, 1) and belongs to M ↓ 0 (A) for t = 1. Therefore m belongs to M ↓ k (A) for k = i + b ≤ 1 2 (|A|-1 + b). The bound follows from the integrality of i + b and b ∈ {0, 1}. (↑) Let p(x) = γ ↑ A (which is a polynomial nonnegative on [0, 1].Again, by Descartes' rule of signs, p has at most |A|-1 positive roots, counting multiplicity. If i is the number of distinct roots of p in (0, 1) and b = 0 if p(1) = 0 and 0 otherwise, this gives that 2i + b ≤ |A|-1. As before, γ ↑ A (t) ∈ M ↑ 1 (A) for all t ∈ (0, 1] and belongs to M ↑ 0 (A) for t = 0. Therefore m belongs toM ↓ k (A) for k = i + b ≤ 1 2 (|A|-1 + b) ≤ 1 2|A|. Now consider m in the interior of M (A) and let c be the moment vector of the constant function 1 [0,1] . Let λ * be the maximum value of λ ∈ R for which mλc belongs to M (A). Since m ∈ M (A), we know that λ * ≥ 0, and for sufficiently large λ, mλc / ∈ M (A). Thus mλ * c belongs to the boundary of M (A), which is equal to the boundary of M k (A) by the argument above. Hence, m also belongs to M k (A).

Proposition 2 . 5 .

 25 For all k < |A| 2 , the cone M k (A) is a proper subset of M (A).

Definition 3 . 4 .

 34 Let n, k be integers with n ≥ 2 and k ≥ 0. The coalescence manifold C n,k is the Euclidean closure of the set of vectors c(p) = c(p)/||c(p)|| 1 for all p ∈ Sk . Here, c(p) = (c 2 (p), . . . , c n (p)) where c i (p) is defined as in Equation

Figure 6 . 8 . 3 . 8 .

 6838 Figure 6. The functions p, p * , and R p from Example 3.8.

1

 1 du where p * (u) = p(-ln(u)).The second equality comes from the change of coordinates u = e -τ . Note that p * is the step function given byp * = p 3 • 1 (0,s 1 ] + p 2 • 1 (s 1 ,s 2 ] + p 1 • 1 (s 2 ,1]where s 1 = e -Rp(b 2 ) and s 2 = e -Rp(b 1 ) .The graphs of p and p * for the values (p 1 , p 2 , p 3 ) = (2, 3, 1) and (b 1 , b 2 ) = (2, 5) are shown in Figure6. In this case, the break points of p * are e -Rp(b 2 ) = e -2 and e -Rp(b 1 ) = e -1 .

Theorem 3 .

 3 5 allows us to apply our results from Mk (A) to C n,k . Corollary 3.10. C n,n-2 = C n,k for all k ≥ n -2 and C n,n-3 C n,n-2 . Proof. For A = i 2 : i = 2, . . . , n , |A| equals n -1. By Theorem 1.5, M k (A) = M (A) for all k ≥ n -2. In particular, M n-2 (A) = M k (A) for all k ≥ n -2.Intersecting with the hyperplane {m : a∈A m a = 1} gives that C n,n-2 = C n,k for all k ≥ n -2. By Corollary 1.12, M k (A) = M (A) for k < |A|-1 = n -2. Hence M n-3 (A) = M (A). Since M (A) = M n-2 (A), intersecting with the hyperplane {m : a∈A m a = 1} gives that C n,n-2 = C n,n-3 . Affine transformations the sets C 5,1 , C 5,2 and C 5,3 are show in Figure 3. As promised, C 5,3 is convex and C 5,k is a strict subset for k < 3.

Theorem 4 . 1 (

 41 Theorems 10.1 and 10.2[START_REF] Schmüdgen | The moment problem[END_REF]). For any d ∈ Z + , the cone M ({0, 1, . . . , d}) is a spectrahedron. If d = 2e is even, then M ({0, 1, . . . , d}) = m ∈ R d+1 : (m i+j ) 0≤i,j≤e 0 and (m i+j+1m i+j+2 ) 0≤i,j≤e-1 0 , and if d = 2e + 1 is odd, then M ({0, 1, . . . , d}) = m ∈ R d+1 : (m i+j+1 ) 0≤i,j≤e 0 and (m i+jm i+j+1 ) 0≤i,j≤e 0 .

Corollary 4 . 2 .

 42 For any finite set of integers A ⊂ N, the convex cones M (A), M ↑ (A) and M ↓ (A) are projections of the spectrahedron M ({0, 1, . . . , max(A)}).Proof. Let d = max(A). Note that by definition, M (A) equals the closure of the projection of M ({0, 1, . . . , d}) under the map (m 0 , m 1 , . . . , m d ) → (m a ) a∈A . For 0 ∈ A, this projection is closed and otherwise, we replace A with B = {amin(A) : a ∈ A} as in Lemma 1

Corollary 4 . 6 .Example 4 . 7 .

 4647 Given p ∈ R n-1 , the problem of finding the closest point to p in C n,k for sufficiently large k is equivalent to solving a semidefinite program in ≤ n 2 /2 variables with three matrices of size ≤ n 2 /4. For n = 5 and k ≥ 3, C 5,k equals the set of points in M ({0, 2, 5, 9}) with m 0 + m 2 + m 5 + m 9 = 1. Projecting from M ({0, 1, . . . , 9}), we see thatC 5,k = (m 0 , m 2 , m 5 , m 9 ) ∈ R 4 : m 0 + m 2 + m 5 + m 9 =1 and ∃(m 1 , m 3 , m 4 , m 6 , m 7 , m 8 ) ∈ R 6 such that (m j ) j=0,...,9 ∈ M ({0, 1, . . . , 9}) Let A(m) and B(m) denote the two 5 × 5 matrices appearing in Example 4.3. Then M ({0, 1, . . . , 9}) is the set of points m ∈ R 10 for which A(m) 0 and B(m) 0. Given a point p = (a, b, c, d) ∈ R 4 , we can find the closest point in C 5,k by solving the following semidefinite program with 10 parameters and three 5 × 5 linear matrix constraints: min λ,m 0 ,...,m 9 λ such that m 0 + m 2 + m 5 + m 9 = 1, A(m) 0, B(m) 0, and

Figure 7 .

 7 Figure 7. The central image depicts M 2 (A) in yellow. The orange region is M ↑ (A) and the green region M ↓ (A); their union is M 1 (A). The triangle above each point depicts the fiber as a subset of the (s 1 , s 2 )-simplex.

( 6 )Proposition 5 . 4 . 1 0

 6541 M(m) = (j + + 2)m j+ +1 -(j + + 1)m j+ 0≤j, ≤ (d-1)/2 . If for some f ∈ S k , m j = x j f (x)dx for all j, then rank(M(m)) ≤ k. Proof.As noted above, we can rewrite the (j, )th entry of M(m) asM(m) j, = (j + +2)m j+ +1 -(j + +1)m j+ = m j+ +1 -m j+ +2 = k i=1 (y i+1 -y i )(s i -s 2 i )s j+ i .

  .2. By Theorem 4.1, M ({0, 1, . . . , d}) is a spectrahedron.More generally, consider any finite collection of polynomials p 1 , . . . , p n ∈ R[x] ≤d . We claim that the conical hull of the curve parameterized by p(t) = (p 1 (t), . . . , p n (t)) for t ∈ [0, 1] is the image of M ({0, 1, . . . , d}) under a linear map. Specifically, consider the linear mapπ : R d+1 → R n taking (m 0 , m 1 , . . . , m d ) to ( d j=0 p ij m j ) i∈[n] where p i (x) = d j=0 p ij x j . For any t ∈ [0, 1], p(t) equals π(v d (t)) where v d (t) = (1, t, t 2 , . . . , t d ). Since M ({0, 1, . . . , d}) is the conical hull of {v d (t) : t ∈ [0, 1]}, the conical hull of {p(t) : t ∈ [0, 1]} is the image of M ({0,1, . . . , d}) under π. Testing membership any of the cones M (A), M ↑ (A) or M ↓ (A) is equivalent to testing the feasibility of a semidefinite program in ≤ d + 1 variables with two matrix constraints, each of size ≤ d/2 + 1, where d = max(A). For k ≥ n -2, the coalescence manifold C n,k is the projection of a spectrahedron. Testing membership in C n,k is equivalent to testing the feasibility of a semidefinite program in ≤ n 2 /2 variables with two matrix constraints, each of size ≤ n 2 /4. Proof. By Theorem 3.5 and Corollary 3.10, for all k ≥ n -2, coalescence manifold C n,k equals in the intersection of M (A) with the affine hyperplane given by a∈A m

	Note that the coordinates of both γ ↑ ,	m 9 10	.
	Corollary 4.4. Corollary 4.5.

a = 1 where A = { i 2 -1 : i = 2, . . . , n}. By Corollary 4.2, M (A) is the projection of M ({0, 1, . . . , d}) where d = n 2 -1. It follows that C n,k

T

  Id n-1 is positive semidefinite if and only if ||x -p||2 2 ≤ λ, where Id n-1 denotes the (n -1) × (n -1) identity matrix. Given a set S ⊂ R n-1 , suppose that λ * and x * obtain the minimum is (one of) the nearest points in S to p and the distance ||x * -p|| 2 is √ λ * . In particular, if the set S is the projection of a spectrahedron, then this minimization problem is a semidefinite program.

	min λ∈R,x∈S	λ such that	λ (x -p) T Id n-1 x -p	0.
	Then x

*

Acknowledgements. Author Rosen thanks Dr. Yun S. Song for introducing him to this topic. Authors Scholten and Vinzant were partially supported by NSF-DMS grants #1620014 and #1943363. This material is based upon work directly supported by the National Science Foundation Grant No. DMS-1926686, and indirectly supported by the National Science Foundation Grant No. CCF-1900460.