The multidimensional truncated moment problem: Carathéodory numbers from Hilbert functions [original]

Mathematische Annalen (2021) 380:267–291

https://doi.org/10.1007/s00208-021-02166-x

Mathematische Annalen

The multidimensional truncated moment problem:

Carathéodory numbers from Hilbert functions

Philipp J. di Dio1·Mario Kummer2

Received: 18 May 2019 / Revised: 8 January 2021 / Accepted: 11 March 2021 / Published online: 24 March 2021

Abstract

In this paper we improve the bounds for the Carathéodory number, especially on

algebraic varieties and with small gaps (not all monomials are present). We provide

explicit lower and upper bounds on algebraic varieties, Rn, and [0,1]n. We also treat

moment problems with small gaps. We find that for every ε>0 and d∈Nthere is

an∈Nsuch that we can construct a moment functional L:R[x1,··· ,xn]≤d→R

which needs at least (1−ε) ·n+d

natoms lxi. Consequences and results for the

Hankel matrix and flat extension are gained. We find that there are moment functionals

L:R[x1,··· ,xn]≤2d→Rwhich need to be extended to the worst case degree 4d,

L:R[x1,··· ,xn]≤4d→R, in order to have a flat extension.

Mathematics Subject Classification 44A60 ·14P99 ·30E05 ·65D32 ·35R30

Contents

1 Introduction .............................................268

2 Preliminaries .............................................269

2.1 Truncated moment problem ...................................269

2.2 Algebraic geometry .......................................272

3 Carathéodory numbers for moment sequences with small gaps ...................275

4 Carathéodory numbers for measures supported on algebraic varieties ...............278

5 Lower bounds on the Carathéodory number .............................283

Communicated by Andreas Thom.

BPhilipp J. di Dio

[email protected]

Mario Kummer

[email protected]

1Technische Universität Berlin, Institut für Mathematik, Straße des 17. Juni 136, 10623 Berlin,

Germany

2Technische Universität Dresden, Fakultät Mathematik, Institut für Geometrie, Zellescher Weg 12-14,

01062 Dresden, Germany

123

268 P. J. di Dio, M. Kummer

6 Hankel matrices and flat extension ..................................287

References ................................................289

1 Introduction

The theory of (truncated) moment sequences is a field of diverse applications and

connections to numerous other mathematical fields, see e.g. [1,22,29–31,33,34,36,38,

48,50,52], and references therein. For more on recent advances in the reconstruction

of measures from moments see e.g. [6,10,11,14,20,21,23,26,35,40,41], and references

therein.

A crucial fact in the theory of truncated moment sequences is the Richter (Richter–

Rogosinski–Rosenbloom) Theorem [43–45] which states that every truncated moment

sequence is a convex combination of finitely many Dirac measures, see also Theo-

rem 2.2. The Carathéodory number is the minimal number Nsuch that every truncated

moment sequence (with fixed truncation) is a sum of Natoms, i.e., Dirac measures.

It has been studied in several contexts but in most cases the precise value of the

Carathéodory number is not known [15,16,32,39,42,43,46,53].

In this work we proceed the study of Carathéodory numbers. We treat moment

sequences with small gaps (see Sect. 3), moment sequences of measures supported

on algebraic varieties (Sect. 4), and the multidimensional polynomial case on Rnand

[0,1]n(Sect. 5). For moment functionals with small gaps we find explicit lower and

upper bounds for dimension n=1 based on Descartes’ rule of signs, see Theorem 3.7.

For moment functionals L:R[X]≤2d→Ron polynomial functions on an algebraic

set X⊂Rnand for sufficiently large d, Theorem 4.5 yields an upper bound of

P(2d)−1 and a lower bound of

P(2d)−k·P(d)+k

2,

where Pis the Hilbert polynomial and kthe dimension of X. In the case X=Rnand

L:R[x1,...,xn]≤2d→R, this gives the lower bound

n+2d

n−n·n+d

n+n

2

(Theorem 5.2). We obtain similar bounds for odd degrees and the case X=[0,1]nin

Sect. 5. In Sect. 6we discuss implications of these bounds, when n→∞and d→∞.

We show that there are moment functionals L:R[x1,...,xn]≤2d→Rthat behave

as bad as possible under flat extensions, see Theorem 6.2 for the precise statement. For

literature on flat extensions in this context see [8,9,36,48] and the references therein.

123

Carathéodory numbers from Hilbert functions 269

2 Preliminaries

2.1 Truncated moment problem

Let Abe a (finite dimensional) real vector space of measurable functions on a mea-

surable space (X,A). Denote by L:A→Ra continuous linear functional. If there

is a (positive) measure μon (X,A)such that

L(a)=X

a(x)dμ(x), for all a∈A,(1)

then Lis called a moment functional. If Ais finite dimensional, it is a truncated

moment functional. By A={a1,...,am}we denote a basis of the m-dimensional real

vector space Aand by

si:= L(ai)

the ai-th (or simply i-th) moment of L(or μfor a μas in (1)). Given a sequence

s=(s1,...,sm)∈Rmwe define the Riesz functional Lsby setting Ls(ai)=si

for all i=1,...,mand extending it linearly to A, i.e., the Riesz functional induces

a bijection between moment sequences s=(s1,...,sm)and moment functionals

L=Ls.ByMAwe denote the set of all measures on (X,A)such that all a∈Aare

integrable and by MA(s)or MA(L)we denote all representing measures of the moment

sequence sresp. moment functional L. Even though moment sequences and moment

functionals are the same, when we apply techniques from algebraic geometry it is

easier to work with moment functionals L:A→Ron e.g. A=R[x1,...,xn]≤2d

or R[X]≤2dwhile when we work with Hankel matrices it is easier to work with

moment sequences sinafixedbasisAof A. Since the polynomials R[x1,...,xn]≤2d

are of special importance, we denote by

An,d:= {xα|α∈Nn

0∧|α|=α1+···+αm≤d}

the monomial basis, where we have xα=xα1

1···xαn

nwith α=(α1,...,α

n)∈Nn

On Nn

0we work with the partial order α=(α1,...,α

n)≤β=(β1,...,β

n)if

αi≤βifor all i=1,...,n.

Definition 2.1 Let A={a1,...,am}be a basis of the finite dimensional vector space

Aof measurable functions on the measurable space (X,A). We define sAby

sA:X→Rm,x→ sA(x):= ⎛

⎜

⎝

a1(x)

am(x)

⎞

⎟

⎠.

Of course, sA(x)is the moment sequence of the Dirac δxmeasure and the cor-

responding moment functional is the point evaluation lxwith lx(a):= a(x).Bya

123

270 P. J. di Dio, M. Kummer

measure we always mean a positive measure unless it is explicitly denoted as a signed

measure.

The fundamental theorem in the theory of truncated moments is the following.

Theorem 2.2 (Richter Theorem [43, Satz 11]) Let A={a1,...,am},m ∈N,be

finitely many measurable functions on a measurable space (X,A). Then every moment

sequence s ∈SAhas a k-atomic representing measure



i=1

ci·sA(xi)

with k ≤m, c1,...,ck>0, and x1,...,xk∈X.

The theorem can also be called Richter–Rogosinski–Rosenbloom Theorem [43–

45], see the discussion after Example 20 in [15] for more details. That every truncated

moment sequence has a k-atomic representing measure ensures that the Carathéodory

number CAis well-defined.

Definition 2.3 Let A={a1,...,am}be linearly independent measurable functions on

a measurable space (X,A).Fors∈SAwe define the Carathéodory number CA(s)of

sby

CA(s):= min{k∈N0|∃μ∈MA(s)k-atomic}.

We define the Carathéodory number CAof SAby

CA:= max

s∈SA

CA(s).

The same definition holds for moment functionals L:A→R.

The following theorem turns out to be a convenient tool for proving lower bounds

on the Carathéodory number CA.

Theorem 2.4 ([16, Thm. 18]) Let A={a1,...,am}be measurable functions on a

measurable space (X,A),s∈SA, and a ∈Awith a ≥0on X,Z(a)={x1,...,xk}

and Ls(a)=0. Then

CA≥CA(s)=dim lin {sA(xi)|i=1,...,k}.

Remark 2.5 Note that in Theorem 2.4 it is crucial that the zero set of ais finite: Take

a=0 and X=Rnfor a simple example where the statement fails when the zero set

is not finite.

It is well-known that in general not every sequence s∈Rmor linear functional

L:A→Rhas a positive representing measure. But of course it always has a signed

k-atomic representing measure with k≤m.

123

Carathéodory numbers from Hilbert functions 271

Lemma 2.6 ([15, Prop. 12]) Let A={a1,...,am}be a basis of the finite dimensional

space Aof measurable functions on a measurable space (X,A). There exist points

x1,...,xm∈Xsuch that every vector s ∈Rmhas a signed k-atomic representing

measure μwith k ≤m and all atoms are from {x1,...,xm}, i.e., every functional

L:A→Ris the linear combination L =c1lx1+···+cmlxm,c

i∈R.

It is well-known that in dimension n=1 the atom positions xiof a moment

sequence can be calculated from the generalized eigenvalue problem, see e.g. [24]. To

formulate this and other results we introduce the following shift.

Definition 2.7 Let n,d∈Nand s=(sα)α∈Nn

0:|α|≤d.Forβ∈Nn

0with |β|≤dwe

define Mβs:= (Mβsα)α∈Nn

0:|α+β|≤dby Mβsα:= sα+β, i.e., (MβL)(p)=L(xβ·p).

For a space Aof measurable functions with basis A={a1,a2...}the Hankel matrix

Hd(L)of a linear functional L:A2→Ris given by Hd(L)=(L(aiaj))d

i,j=1.The

atom positions of a truncated moment sequence s(resp. moment functional L)are

then determined by the following result from a generalized eigenvalue problem.

Lemma 2.8 Let n,d∈N,X=C, and s =(s0,s1,...,s2d+1)∈R2d+2with



i=1

ci·sA1,2d+1(zi)

for some zi∈C,c

i∈C, and k ≤d. Then the ziare unique and are the eigenvalues

of the generalized eigenvalue problem

Hd(M1s)vi=ziHd(s)vi.(2)

Proof That the ziare the eigenvalues of (2) and therefore uniqueness follows from

Hd(s)=(sA1,d(z1),...,sA1,d(zk)) ·diag (c1,...,ck)·(sA1,d(z1), . . . , sA1,d(zk))T

and

Hd(M1s)

=(sA1,d(z1),...,sA1,d(zk)) ·diag (c1z1,...,ckzk)·(sA1,d(z1),...,sA1,d(zk))T.



We gave here only the 1-dimensional formulation, but a similar result holds also for

n>1. But as seen from the Carathéodory number and the flat extension in Sects. 5and

6, the size of the Hankel matrix of the flat extension can be very large. For numerical

reasons it is therefore advisable to reduce n-dimensional problems to 1-dimensional

problems.

123

272 P. J. di Dio, M. Kummer

2.2 Algebraic geometry

Consider the polynomial ring R[x0,...,xn]with the natural grading and let I⊂

R[x0,...,xn]be a homogeneous ideal. Let

R=R[x0,...,xn]/I

be the quotient ring which is a graded ring itself. Recall that the Hilbert function of R

is given by HF

R(d)=dim Rdwhere Rdis the degree dpart of R.Fordlarge enough

one has HF

R(d)=HP

R(d)for some polynomial HP

Rof degree kwhich is called

the Hilbert polynomial of R.

In this article, we will always denote by Pn=Pn

Cthe complex projective space.

Areal projective variety is the zero set V⊂Pnof some homogeneous ideal I⊂

R[x0,...,xn]. In particular, a real projective variety can contain nonreal points but

it is defined by real polynomial equations. We will denote by V(R)the set of real

points of V. The Zariski closure of any subset W⊂Pn, that consists only of real

points, is an example for a real projective variety Vwith the additional property that

V(R)is Zariski in V.IfV⊂Pnis a real projective variety and Iis its homogeneous

vanishing ideal, then the Hilbert function/polynomial HF

Vresp. HP

Vof Vis the

Hilbert function/polynomial of R[x0,...,xn]/I. In this case, the leading coefficient

of HP

Vis e

k!where eis the degree of V.

Now we consider the dehomogenization map

R[x0,...,xn]→R[x1,...,xn],f→ f|x0=1.

Let I⊂R[x1,...,xn]be an ideal and Ih⊂R[x0,...,xn]the homogenization

of I, i.e., the ideal generated by the homogenizations fhof all f∈I. Then the

dehomogenization map induces an isomorphism of vector spaces

(R[x0,...,xn]/Ih)d→(R[x1,...,xn]/I)≤d

for all d≥0. Here (R[x1,...,xn]/I)≤dis the subspace of R[x1,...,xn]/Iconsisting

of the residue classes of polynomials of degree at most d. The main application of this

observation will be the case when Iis the vanishing ideal of finitely many points in

Rn. In this case the dimension

dim lin {sAn,d(x)|x∈}

of the span of the point evaluations sAn,d(x)in R[x1,...,xn]∗

≤dat the points from 

needed Theorem 2.4 is

dim(R[x1,...,xn]/I)≤d=dim(R[x0,...,xn]/Ih)d=HF

I(d).

The Hilbert function HF

Iof an ideal Ican be easily calculated if it is generated by a

regular sequence.

123

Carathéodory numbers from Hilbert functions 273

Definition 2.9 Let Abe a commutative ring. A sequence f1,..., fr∈Ais a regu-

lar sequence if for all i=1,...,rthe residue class of fiis not a zero divisor in

A/( f1,..., fi−1).

The following is a consequence of Krull’s Principal Ideal Theorem. We include a

proof since we are not aware of a good reference.

Lemma 2.10 Let I ⊂R[x0,...,xn]be a homogeneous radical ideal and V ⊂Pnits

zero set. If each irreducible component of V has the same dimension d ≥1, then for

any homogeneous f ∈R[x0,...,xn]the following are equivalent:

(i) f is not a zero divisor in R[x0,...,xn]/I.

(ii) f is not in a minimal prime ideal of R[x0,...,xn]/I.

(iii) f is not identically zero on an irreducible component of V .

(iv) Each irreducible component of V ∩V(f)has dimension at most d −1.

(v) Each irreducible component of V ∩V(f)has dimension d −1.

Furthermore, if f is not constant and V nonempty, then V ∩V(f)is nonempty.

Proof The minimal prime ideals of the homogeneous coordinate ring

A=R[x0,...,xn]/I

of Vare exactly the vanishing ideals of irreducible components of V. Thus we have

(ii)⇔(iii).If fis a zero divisor in A, then there is a nonzero g∈Asuch that fg =0.

Let Vibe an irreducible component of Von which gdoes not vanish identically. Then

Vi⊂V(f)∪V(g)implies Vi⊂V(f)because Viis irreducible. Thus (iii)implies

(i).By[3, p. 44, Ex. 9] every minimal prime ideal contains only zero divisors. This

shows (i)⇒(ii).If fvanishes entirely on an irreducible component Viof V, then

Viis an irreducible component of V∩V(f).Byassumptionwehavedim(Vi)=d,

so we cannot have (iv). Thus (iv) ⇒(iii).

Since (v) clearly implies (iv), it remains to show (v) under the assumption of

(i)−(iii).If fis a unit in A, then V∩V(f)=∅and (v) is trivially true as there are

no irreducible components. Thus we can assume that fis neither a zero divisor nor a

unit in A. Thus by Krull’s Principal Ideal Theorem [3, Cor. 11.17] every minimal prime

ideal over (f)⊂Ahas height one. This implies that every irreducible component W

of V∩V(f)has codimension one. Since Vis of pure dimension d, this means that

the dimension of Wis d−1. The additional statement follows for example by [49,

Cor. 1.7] because we have dim(V)>0. 

Corollary 2.11 Let I0⊂R[x0,...,xn]be a homogeneous prime ideal such that

dim V(I0)≥k. Let f1,..., fk∈R[x0,...,xn]homogeneous elements of positive

degree such that for all i =1,...,k we have:

(i) Ii:= I+(f1,..., fi)is radical.

(ii) dim V(Ii)=dim V(Ii−1)−1.

Then f1,..., fkis a regular sequence modulo I0.

123

274 P. J. di Dio, M. Kummer

Proof For i=0,...,klet Vi=V(Ii)⊂Pnand let d=dim(V0). First we show

that each irreducible component of Vihas dimension d−iby induction on i.The

claim is clear for i=0 because Iis a prime ideal. Assume the claim is true for

0≤i<k. Then we can apply Lemma 2.10 to the ideal Ii.Byassumptionwehave

dim V(Ii+1)=dim V(Ii)−1=d−i−1sowehave(iv). Thus we also have (v)

which says that each irreducible component of Vi+1has dimension d−i−1. Then by

the same lemma we also have that fi+1is not a zero divisor modulo Iiwhich shows

that f1,..., fkis a regular sequence modulo I0.

Lemma 2.12 Let I ⊂R[x0,...,xn]be a homogeneous ideal and R =R[x0,...,xn]/I

with Hilbert function H FR. Let f1,..., fr∈R be a regular sequence of homogeneous

elements of degree d. The Hilbert function H FR/( f1,..., fr)of R/( f1,..., fr)is

R/( f1,..., fr)(j)=



i=0

(−1)i·r

i·HF

R(j−id).

Proof We prove the statement by induction on r. The case r=0 is trivial. In order to

prove the induction step, let Ri=R/( f1,..., fi)for i=0,...,r. For all j∈Zwe

have the exact sequence

0→Rr−1

j−d→Rr−1

j→Rr

j→0

where the first map is given by multiplication with fr. Therefore

Rr(j)=HF

Rr−1(j)−HF

Rr−1(j−d).

By induction hypothesis this implies that

Rr(j)=

r−1



i=0

(−1)ir−1

iHF

R(j−i·d)

−

r−1



i=0

(−1)ir−1

iHF

R(j−(i+1)d)



i=0

(−1)i(r−1

i+r−1

i−1)HF

R(j−i·d)



i=0

(−1)ir

iHF

R(j−i·d).



At various places we will make use of the following version of Bertini’s Theorem.

Theorem 2.13 Let X⊂Pnbe a real projective variety of dimension k. Then the fol-

lowing statements hold for generic homogeneous forms f1,..., fr∈R[x0,...,xn],

123

Carathéodory numbers from Hilbert functions 275

r≤k, of degree d >0in the sense that the set of exceptions is contained in a lower

dimensional algebraic subset of R[x0,...,xn]r

i) The homogeneous vanishing ideal of X∩V(f1,..., fr)is generated by the homo-

geneous vanishing ideal of Xand f1,..., fr.

ii) If Xis irreducible and r <k, then X∩V(f1,..., fr)is irreducible as well.

iii) We have dim(X∩V(f1,..., fr)) =k−r.

iv) If the singular locus of Xhas dimension at most r −1, then X∩V(f1,..., fr)is

smooth.

Proof Bertini’s Theorem in its usual formulation says that the above listed statements

hold for generic homogeneous forms f1,..., fr∈C[x0,...,xn],r≤k,ofdegree

d>0. As a reference for this see for example [28, Thm. 6.10, Cor. 6.11]. This

means that the set Uof exceptions is contained in a lower dimensional algebraic

subset W⊂C[x0,...,xn]r

d.ThesetUof tuples (f1,..., fr)∈R[x0,...,xn]r

dof

real polynomials for which one of our statements does not hold is thus contained in

the algebraic subset W=W∩R[x0,...,xn]r

dof R[x0,...,xn]r

d. Since the set of

real points R[x0,...,xn]r

dis Zariski dense in the vector space C[x0,...,xn]r

d,we

see that Wdoes not contain R[x0,...,xn]r

d. Thus Wis a strict algebraic subset of

R[x0,...,xn]r

d. This shows the claim. 

For more on Hilbert functions and polynomials see e.g. [51], or standard text books

on commutative algebra like [18,19], or [5].

3 Carathéodory numbers for moment sequences with small gaps

We want to start our investigation of the Carathéodory number in the 1-dimensional

case with gaps, i.e., not all monomials are present.

Let d1,...,dr∈Nbe some natural numbers whose greatest common divisor is

one. We consider the subring R=R[td1,...,tdr]of R[t].ByR≤dwe denote the

vector space of polynomials in Rof degree at most d. By the assumption on the greatest

common divisor there is a constant csuch that td∈Rfor all d≥c. We choose c

minimal with this property and denote it by c. We observe that one has

dim R≤d=d+1−gfor d≥c

where c+1−gis the number of monomials in Rof degree at most c. In other words,

gis the number of monomials that are not in R(i.e., the number of gaps).

Definition 3.1 The k-th Descartes number Dkof Ris the maximal number of different

real zeros that a polynomial f∈R≤kcan have.

Recall that Descartes’ rule of signs says that the number of positive real zeros

(counted with multiplicities) of a polynomial f=n

k=0cktkis bounded from above

by the number Var(c0,...,cn)of sign changes in the sequence c0,...,cnafter erasing

all zeros. The number of negative zeros (again counted with multiplicities) of fis then

bounded by Var(c0,−c1,...,(−1)ncn). Conversely, Grabiner [25] constructed for all

123

276 P. J. di Dio, M. Kummer

sequences of signs (σ0,...,σ

n),σi∈{0,±1}, a polynomial f=n

k=0cktkwith

only simple positive and negative zeros and sgn(ci)=σi, that realizes both bounds.

Thus Descartes’ rule of signs gives a purely combinatorial way to determine an upper

bound on the k-th Descartes number from the numbers d1,...,dr. This also shows

that Dkis the maximal number of different real zeros that a polynomial f∈R≤kwith

f(0)= 0 can have since adding a small constant of appropriate sign does not decrease

the number of real zeros of a polynomial whose only possibly multiple real root is 0.

Example 3.2 (a) Let R=R[t4,t6,t7]. Then the Descartes number D7is the maximal

number of real roots that a polynomial of the form a+bt4+ct6+dt7can have.

By trying out all possible signs on the coefficients, we find by Descartes’ rule of

signs that such a polynomial can have at most five real zeros and by [25] there

actually is such a polynomial. Thus D7=5.

(b) The Descartes number does not only depend on the number of involved monomials

but also on their parities. For example if R=R[t5,t6,t9], then D9=3.

Proposition 3.3 For all k ≥0we have Dc+k=Dc+k.

Proof We prove the claim by induction on k. The case k=0 is trivial. Let k≥

1 and assume that the claim is true for k−1. Then there is a sequence of signs

(σ0,...,σ

c+k−1),σi∈{0,±1},σ0= 0, of coefficients of a polynomial in Rwith

Dc+k−1 different real zeros. In particular,

Var(σ0,...,σ

c+k−1)+Var(σ0,...,(−1)c+k−1σc+k−1)=Dc+k−1.

Letting σc+k=−σc+k−1we get that

Var(σ0,...,σ

c+k−1,σ

c+k)+Var(σ0,...,(−1)c+k−1σc+k−1,(−1)c+kσc+k)=Dc+k

and another choice of σc+kwould not result in a larger sum, so Dc+k=Dc+k.

Proposition 3.4 Let k ≥c. The maximal number of real zeros that a nonnegative

polynomial f ∈R≤2kcan have is between k −(c−Dc)and k −c−Dc−1

2. Here the

lower bound is realized by a polynomial that is the square of an element of R.

Proof For the lower bound just take the square of a polynomial of degree kwith

Dk=Dc+k−creal zeros. On the other hand, if f∈Ris a nonnegative polynomial

with Nreal zeros, then tf∈Rhas at least 2N−1 zeros. Therefore, 2N−1≤D2k

implies

N≤D2k+1

2=Dc+2k−c+1

2=k−c−Dc−1

2.



Lemma 3.5 The point evaluations lp1,...,lpn:R≤e→Rare linearly independent

for any pairwise distinct points p1,...,pn∈Rand e ≥c+n−1.

123

Carathéodory numbers from Hilbert functions 277

Proof We consider the map ψ:R≤e→Rn,g→ (g(pi))1≤i≤n. The polynomial

tcn

i=1,i= j(t−pi)is mapped to a nonzero multiple of the j-th unit vector except

for the case when pj=0. Thus we have at least all unit vectors but one in the image

and the constant polynomial 1 is mapped to the vector (1,...,1). Thus ψis surjective

which implies the claim. 

The following lemma generalizes [12, Thm. 3.68] and [16, Thm. 45].

Lemma 3.6 Let A⊂R[x]be the vector space of polynomials on Rgenerated by the

monomials A={xd1,xd2,...,xdm},m,di∈N, such that d1=0<d2<··· <dm

and dmis even. If all non-negative polynomials in Ahave at most C zeros, then

CA≤C+1.

Proof Let s∈SAbe a moment sequence.

Step i): If sis in the boundary of the moment cone, there exists a p∈Awith

p≥0 and Ls(p)=0, i.e., all point evaluations are located at the zeros of p. Hence,

srequires at most Cpoint evaluations.

Step ii): Assume now sis in the interior of the moment cone.

Homogenize A, i.e., B:= {ydm,xd2ydm−d2,...,xdm}. Since sis a moment

sequence, we have s=l

i=1ci·sA(xi)=l

i=1ci·sB((xi,1)). Since xdm,ydm∈B,

we have xdm+ydm>0onP1and the moment cone SBis closed. Hence, by

[16, Prop. 8] there exists an ε>0 such that

cq(x,y):= sup{r≥0|q−r·sB(x,y)∈SB}(∗)

is attained and continuous for all q∈Bε(s),(x,y)∈P1,wehaveBε(s)⊂int S,

and

:= sup

q∈Bε(s)

cq((0,1)) < ∞.(∗∗)

Let

T:= 

c∈[0,+1]

Bε(s−c·sB(0,1))

be the ε-tube around the line s−[0,+1]·sB((0,1)). Write T=T1∪T2∪T3with

T1:= T∩int SB,T2:= T∩∂SB, and T3:= T\(T1∪T2). I.e., T1is the part of the

ε-tube inside the moment cone, T2is the intersection of the ε-tube with the boundary

of the moment cone, and T3is the part of the ε-tube outside the moment cone.

Since the moment cone is closed (and convex), also T2is closed and every path

starting in T1and ending in T3contains at least one point in T2. We define

t:= t−cq((0,1)) ·sB((0,1))

123

278 P. J. di Dio, M. Kummer

for all t∈Bε(s).By(∗) and (∗∗) we have for all t∈Bε(s)that tis a moment sequence

without an atom at (0,1)(by maximality of cq((0,1))), i.e., tis a moment sequence

on Rand in the boundary of SA.Bystep(i)trequires at most kpoint evaluations.

Since sB((x,y)) is continuous in (x,y), there exists a δ=δ(ε) > 0 such that

s:= s−cs((δ, 1)) ·sB((δ, 1)) ∈T2,

i.e., also sis a moment sequence on Rwith at most kpoint evaluations. Hence,

s=s+cs((δ, 1)) ·sB((δ, 1)) is a moment sequence on Rwith CA(s)≤C+1.

Finally, since s∈SAwas arbitrary we have CA≤C+1. 

Theorem 3.7 Let R =R[td1,...,tdr]and k ≥c. Every moment functional L :

R≤2k→Ris a conic combination of at most k +1−c−Dc−1

2point evaluations.

There are moment functionals L :R≤2k→Rthat are not a conic combination of less

than k −(c−Dc)point evaluations.

Proof For the upper bound we combine Proposition 3.4 and Lemma 3.6.Wehave

1∈R≤2kand since k≥cwe have by the minimality of c(see second paragraph at the

beginning of this section) that x2k∈R≤2k. So the monomial basis Aof R≤2kfulfills

the conditions in Lemma 3.6 and by Proposition 3.4 every non-negative polynomial

in R≤2khas at most C=k−c−Dc−1

2zeros. Lemma 3.6 implies that every moment

sequence/functional is represented by at most C+1=k+1−c−Dc−1

2point

evaluations.

The lower bound follows from Proposition 3.4, Lemma 3.5, and Theorem 2.4.

Example 3.8 a) Let R=R[t2,t2r+1]with r≥0. In this case we have c=Dc=

2r+1. Thus for k≥2r+1 every moment functional L:R≤2k→Ris a conic

combination of at most k+1 point evaluations and there are moment functionals

which are not a conic combination of less than kpoint evaluations.

b) Let R=R[tr,tr+1,tr+2,...]. Then c=rand Dc=1ifris odd and Dc=2

if ris even, so the difference between upper and lower bound in Theorem 3.7

grows linearly in r. This situation is in sharp contrast to the results from Sect. 4

on smooth curves.

4 Carathéodory numbers for measures supported on algebraic

varieties

Now for any subset X⊂Rnwe are interested in the ring R[X]of polynomial

functions X→R. The finite dimensional vector space of all functions X→R

that can be represented by a polynomial of degree at most dis denoted by R[X]≤d.

If I⊂R[x1,...,xn]is the ideal of all polynomials vanishing on X, then R[X]=

R[V0]=R[x1,...,xn]/Iwhere V0⊂Rnis the Zariski closure of X.LetV⊂Pn

be the Zariski closure of V0in the complex projective space. Then one has

V(d)=dim R[X]≤d.(3)

123

Carathéodory numbers from Hilbert functions 279

From Richter’s Theorem we thus immediately get the following.

Proposition 4.1 Every moment functional L :R[X]≤2d→Ris a conic combina-

tion of at most H FV(2d)point evaluations lxiwith xi∈X.IfXconsists of less

than H FV(2d)path-connected components, then H FV(2d)−1point evaluations are

sufficient. In particular, for large d this upper bound grows like a polynomial whose

degree is the dimension of the Zariski closure of X.

Proof In (3) we already established that dim R[X]≤2d=HF

V(2d). Since Xis a mea-

surable space and monomials are measurable functions, Richter’s Theorem 2.2 implies

that Lcan be represented by at most dim R[X]≤2d=HF

V(2d)point evaluations.

Since Xis a topological space which consists of at most HF

V(2d)−1 path-

connected components, 1 ∈R[X], and R[X]consists of continuous functions we

have that sA(X)consists of at most HF

V(2d)−1 path-connected components. All

conditions of [13, Thm. 12] are fulfilled which implies the upper bound. 

In order to provide lower bounds as well, we will need the following lemma.

Lemma 4.2 Assume that V is irreducible with homogeneous vanishing ideal I and

that its singular locus has codimension at least 2.Ifk=dim(V), then, for all d large

enough, there are k real homogeneous polynomials f1,..., fkof degree d whose

common zero set Z on V consists of dk·deg(V)different points that are all real and

contained in V0. Furthermore, one can choose the f1,..., fkto be a regular sequence

with the property that they generate the homogeneous vanishing ideal of Z modulo I .

Proof By Bertini’s theorem, for a generic choice of k−1 real linear forms l1,...,lk−1

the set V∩V(l1,··· ,lk−1)⊂Pnis a real smooth irreducible curve X. Since the real

points of Vare Zariski dense in Vwe can furthermore assume that X(R)is nonempty.

Now by [47, Cor. 2.10, Rem. 2.14], for large enough d, there is a homogeneous

polynomial fof degree dall of whose zeros on Xare real, simple and do not lie at

the hyperplane at infinity. Since deg X=deg V=: e, these are de many points. The

same is true for the zeros of fon Xwhere Xis the intersection of Vwith linear

forms l

1,...,l

k−1that are sufficiently small perturbations of l1,...,lk−1. Therefore,

for sufficiently small >0, the common zero set on Vof fwith the polynomials

fi=d

j=1(li+j·x0),i=1,...,k−1, consists of exactly dkereal, simple points

that do not lie in the hyperplane at infinity. Thus these dkepoints lie in V0.

In order to obtain the additional properties, we can perturb f1,..., fka little bit so

that each Ii=I+(f1,..., fi)is a radical ideal by Bertini’s Theorem. Finally, since

the dimension of V(Ii)is exactly k−i,the f1,..., fkhave to form a regular sequence

modulo Iby Corollary 2.11.

Remark 4.3 In the proof of the preceding lemma lies the reason why, in this section,

we get lower bounds only for sufficiently large d. Namely, Scheiderer’s result in [47],

which states that for every smooth algebraic curve Xthere are polynomials of degree

dthat have only real zeros on X, is only true for sufficiently large d. To find an explicit

lower bound on d, that ensures the existence of such polynomials, is an open problem,

except for the case of M-curves where a good lower bound has been provided by

Huisman [27].

123

280 P. J. di Dio, M. Kummer

Example 4.4 The assumption on the singular locus in Lemma 4.2 is necessary. Consider

for example the singular plane curve V0=V(x4−y3)⊂R2. It is the image of the

map R→R2,t→ (t3,t4). Now the zeros of a polynomial f∈R[x,y]of degree d

on V0correspond to the roots of the univariate polynomial f(t3,t4). But by Descartes’

rule of signs this can not have 4ddifferent real zeros. We dealt with curves of this kind

in Sect. 3.

From this we get our main theorem on the Carathéodory numbers for measures

supported on an algebraic set.

Theorem 4.5 Let X=V0⊂Rnbe Zariski closed of dimension k >0such that its

projective closure V ⊂Pnis irreducible and its singular locus has codimension at

least 2. Let P ∈Q[t]be the Hilbert polynomial of V . For large enough d >0, every

moment functional L :R[X]≤2d→Ris a conic combination of at most P(2d)−1

point evaluations lxiwith xi∈X. On the other hand, there are moment functionals

L:R[X]≤2d→Rthat are not a conic combination of fewer than

P(2d)−k·P(d)+k

2

point evaluations lxi.

Proof For large enough dwe have P(2d)=HF

V(2d). Therefore, by Proposition 4.1,

in order to prove the upper bound, it suffices to show that P(2d)exceeds the number

mof path-connected components of Xfor large enough d. Since mis finite by [4,

Thm. 2.4.5, Prop. 2.5.13], this is clear because Phas positive degree k. For the lower

bound we consider the polynomials f1,..., fkof degree dfrom Lemma 4.2 whose

common zero set Zon Xconsists of dk·deg Vsimple points. The polynomial

f1(1,x1,...,xn)2+...+fk(1,x1,...,xn)2

is non-negative and has the same zero set Zon X. By Theorem 2.4 a lower bound

is then given by the dimension of the span of the point evaluations of polynomials

of degree at most 2din Z. This is the same as the dimension of the vector space

(R[x0,...,xn]/J)2dwhere Jis the homogeneous vanishing ideal of Zconsidered as

a subset of Pn. This is by definition HF

Z(2d). Since Jis given by I+(f1,..., fk)

where Iis the homogeneous vanishing ideal of V, and since the fiform a regular

sequence, we have

Z(2d)=HF

I+(f1,..., fk)(2d)=



i=0

(−1)ik

iHF

I(d·(2−i))

by Lemma 2.12. It follows immediately from the definition of the Hilbert function that

I(m)=0form<0 and HF

I(0)=1. Therefore, only the first three terms of the

above sum are nonzero and we obtain:

Z(2d)=HF

I(2d)−kHFI(d)+k

2.

123

Carathéodory numbers from Hilbert functions 281

For large dthe Hilbert function coincides with the Hilbert polynomial which shows

the claim. 

Example 4.6 This example is to demonstrate that both upper and lower bound from

Theorem 4.5 are false when dis not large enough. Consider the plane curve X⊂R2

defined as the zero set of the polynomial x8+y8−1. It is path-connected and its

Zariski closure C⊂P2is smooth with Hilbert polynomial P(d)=8d−20. Thus

for d=1wehave

P(2d)−1=P(2)−1=−5<0

which cannot be an upper bound. However, by Proposition 4.1 an upper bound in the

case d=1 is given by

C(2d)−1=HF

C(2)−1=5.

Finally, again for d=1, we have

P(2d)−k·P(d)+k

2=P(2)−P(1)=8

which exceeds the upper bound and thus cannot be a lower bound.

Example 4.7 Let X⊂Rn,n≥2, be the boundary of the unit ball, i.e., the zero set of

1−(x2

1+...+x2

n). Its Zariski closure

V=V(x2

0−(x2

1+...+x2

n)) ⊂Pn

is irreducible and smooth. A direct computation gives its Hilbert polynomial:

P(d)=n+d−1

d+n+d−2

d−1

It agrees with its Hilbert function for d≥0. By Theorem 4.5 there is a d0such that

for all d≥d0, every moment functional L:R[X]≤2d→Ris a conic combination

of at most

n+2d−1

2d+n+2d−2

2d−1−1

point evaluations with points in X. Moreover, there are moment functionals L:

R[X]≤2d→Rthat are not a conic combination of fewer than

n+2d−1

2d+n+2d−2

2d−1−(n−1)n+d−1

d+n+d−2

d−1

+n−1

2

123

282 P. J. di Dio, M. Kummer

point evaluations. We claim that in this case we can even choose d0=1. Indeed, since

Xis path-connected, P(2d)exceeds the number of connected components whenever

d>0. Moreover, letting li=xithe curve Xin the proof of Lemma 4.2 is the Zariski

closure of the unit circle in the plane. Then clearly for any d≥1 there is a polynomial

of degree dall of whose zeros on Xare real, simple and do not lie at the hyperplane

at infinity: Consider for example the union of ddistinct lines through the origin. Thus

the proof of Theorem 4.5 shows that we can choose d0=1. In the case n=3the

Carathéodory number Cis thus bounded by

2d2≤C≤4d(d+1).

Let us examine the ratio of the lower and upper bound from Theorem 4.5 as dgoes

to infinity:

P(2d)−k·P(d)+k

2

P(2d)=1−kP(d)

P(2d)+k

2

P(2d)

d→∞

−−−→1−k

2k.(4)

Thus if the dimension kof Xis not too small, our bounds are rather tight – at least

for large d. On the other hand, if k=1, i.e., Xis a smooth algebraic curve, using a

refined argument, we obtain bounds that are even better, namely they differ only by

one.

Theorem 4.8 Let X=V0⊂Rnbe a compact algebraic set of dimension 1such that

its projective closure V ⊂Pnis a smooth irreducible curve of degree e. For large

enough d >0, every moment functional L :R[X]≤2d→Ris a conic combination

of at most d ·e+1point evaluations lxiwith xi∈X. On the other hand, there are

moment functionals L :R[X]≤2d→Rthat are not a conic combination of fewer

than d ·e point evaluations lxi.

Proof The Hilbert polynomial of Vis of the form HP

V(t)=e·t+a. Thus the lower

bound from Theorem 4.5 is just d·e.

In order to prove the upper bound we use a similar technique as in Lemma 3.6.

At first we show that a non-negative polynomial fon Xof degree 2dcan have at

most d·edifferent zeros on X(or vanishes on all of X). Indeed, the zero set of fon

Xis contained in V(fh)∩Vwhere fhis the homogenization of f. Since V(fh)is

a hypersurface of degree 2dand Va curve of degree e, the intersection V(fh)∩V

consists of 2de points counted with multiplicity. But because fis non-negative on X,

each zero of fon Xmust have even multiplicity as otherwise there would be a sign

change. This shows that fhas at most d·edifferent zeros on X.

Now we show the upper bound d·e+1. Let Abe a basis of R[X]≤2dand s∈SA

be the moment sequence of L. Since 1 ∈R[X]≤2dand Xis compact, SAis closed

and pointed, i.e.,

cs(x):= sup{c≥0|s−c·sA(x)∈SA}<∞

is attained for every x∈X. Hence, s=s−cs(x)·sA(x)∈∂SAand there exists

an f∈R[X]≤2dsuch that f≥0onXand Ls(f)=0 holds. Since fhas at most

123

Carathéodory numbers from Hilbert functions 283

d·ezeros, sis represented by at most d·epoint evaluations. s=s+cs(x)·sA(x)

requires therefore at most d·e+1 point evaluations in X.

Remark 4.9 As we have seen in Sect. 3, the smoothness assumption in Theorem 4.8

is crucial.

In the next section we use the techniques and results from this and the preceding

sections to obtain new lower bounds for the cases X=Rnand X=[0,1]n.

5 Lower bounds on the Carathéodory number

Several lower bounds on the Carathéodory number are known, see e.g. [17]. For

bivariate polynomials of odd degree A=R[x1,x2]≤2d−1Möller [39] proved

d+1

2+d

2≤CA2,2d−1.

In [16] the first author and K. Schmüdgen gave a very general lower bound improving

Möllers lower bound to

1

32d+1

2 ≤CA2,2d−1and 1

32d+2

2 ≤CA2,2d.

In [46] C. Riener and M. Schweighofer further improved the lower bound to

(d−1)2≤CA2,2d−1.(5)

They used [46, Prop. 8.5], a polynomial version of Theorem 2.4, applied to f2

1+f2

where

f1(x)=(x−1)(x−2)···(x−d)and f2(y)=(y−1)(y−2)···(y−d)

and found dim R[x,y]/( f1,f2)=d2, i.e., dim lin {sA(xi,yj)|xi,yj=1,...,d}=

d2and therefore the moment functional L:R[x,y]≤2d→Rwith L=d

i,j=1l(i,j)

has Carathéodory number d2.In[15] this was extended to higher dimensions by

investigating the linear (in)dependence of sA(xi)on the grid G={1,...,d}n(for

X=Rn) and G={0,1,...,d}n(for X=[0,d]n). As in the previous section the

main idea is that the dimension of point evaluations

dim lin {sAn,d(x)|x∈Z(f)}(6)

can be translated into

dim(R[x0,...,xn]/I)d,(7)

i.e., the dimension of the homogeneous part of R[x0,...,xn]/Iof degree dfor some

homogeneous ideal I.

123

284 P. J. di Dio, M. Kummer

Lemma 5.1 Let n,d∈Nand set

pi=(xi−x0)···(xi−dx0)and qi=xi(xi−x0)···(xi−dx0)

for i =1,...,n. The following holds:

(i) The sequences p1,...,pnand q1,...,qnare regular.

(ii) The ideals generated by p1,...,pnresp. q1,...,qnare radical.

(iii) Let f1,..., fnbe a regular sequence of homogeneous functions fiof degree d.

The Hilbert function H FRnof Rn:= R[x0,...,xn]/( f1,..., fn)is

Rn(k)=



i=0

(−1)i·n

i·HF

Pn(k−i·d).

In particular, we have

Rn(2d−2)=n+2d−2

n−n·n+d−2

n,

Rn(2d−1)=n+2d−1

n−n·n+d−1

n,

Rn(2d)=n+2d

n−n·n+d

n+n

2,

and

Rn(2d+1)=n+2d+1

n−n·n+d+1

n+3·n+1

3.

Proof Part (i) follows directly from the fact that each piresp. qiis a monic polynomials

over R[x0]in the single variable xi. Part (ii) is a direct consequence of [2,Thm.1.1].

Finally, since HF

Pn(k)=n+k

kfor k≥0 and HF

Pn(k)=0 otherwise, Lemma 2.12

directly implies (iii). 

From this lemma we derive the following lower bounds for the Carathéodory num-

ber CAn,2dand CAn,2d+1on X=Rn.

Theorem 5.2 Let n,d∈Nand X⊆Rnwith non-empty interior. For even degree

A=R[x1,...,xn]≤2dwe have

CAn,2d≥n+2d

n−n·n+d

n+n

2

and for odd degree A=R[x1,...,xn]≤2d+1we have

CAn,2d+1≥n+2d+1

n−n·n+d+1

n+3·n+1

3.

123

Carathéodory numbers from Hilbert functions 285

Proof Since X⊆Rnhas non-empty interior there is a ε>0 and y∈Rnsuch that

y+ε·{1,...,d}n⊂X. The affine map T:X→X,x→ y+ε·xshifts the moment

problem on Xto X=ε−1·(X−y)with R[x1,...,xn]≤dD =R[x1,...,xn]≤D◦T,

D=2d,2d+1, and {1,...,d}n⊂X. So w.l.o.g. we can assume that {1,...,d}n⊂

X. Then we can proceed as in the proof of Theorem 4.5 by choosing the fito be the

pifrom Lemma 5.1. We have already calculated the concrete resulting values of the

Hilbert function in Lemma 5.1.

These lower bounds coincide with the numerical results in [15, Tab. 2]. Note that for

n=1 we get for the even and odd degree cases the bound d. This is the maximal number

of zeros of a non-zero and non-negative univariate polynomial, i.e., the Carathéodory

number of moment sequences on the boundary of the moment cone SAn,2dor SAn,2d+1,

respectively. In fact, we proved the following.

Proposition 5.3 Let n,d∈N,k∈{0,1},X=Rn, and G ={1,...,d}n. Then

s=

x∈G

sAn,2d+k(x)resp. L =

x∈G

lx:R[x1,...,xn]≤2d+k→R

supported on the grid G with L(p)=0,p=p2

1+···+ p2

n≥0from Lemma 5.1,

and the representing measure μ=x∈Gδxhas the Carathéodory number

CAn,2d+k(s)=n+2d

n−n·n+d

n+n

2for k =0,

n+2d+1

n−n·n+d+1

n+3·n+1

3for k =1.

We get the following lower bounds for the case X=[0,1]n(or equivalently

X=[0,d]n) which serves as an example of a compact set X.

Theorem 5.4 Let n,d∈Nand X=[0,1]n. For even degree A=R[x1,...,xn]≤2d

we have

CAn,2d≥n+2d

n−n·n+d−1

n

and for odd degree A=R[x1,...,xn]≤2d+1we have

CAn,2d+1≥n+2d+1

n−n·n+d

n.

Proof The proof follows the same arguments as in Theorem 5.2. Since we work on

[0,1]nwe can choose the fi’s to be the qi’s as in Theorem 4.5. Then Lemma 5.1

provides the explicit values of the Carathéodory numbers. 

Additionally, note the difference between the lower bounds from Theorem 5.2 and

Theorem 5.4. In the one-dimensional case a non-negative polynomial pof degree 2d

has at most dzeros by the fundamental theorem of algebra:

p(x)=(x−x1)2···(x−xd)2.

123

286 P. J. di Dio, M. Kummer

However, on the interval [0,1]a non-negative polynomial qof degree 2dcan have up

to d+1 zeros

q(x)=(x−x1)·(x−x2)2···(x−xd−1)2·(xd−x)

when x1=0 and xd=1 holds. So interior zeros count twice, zeros on the bound-

ary only once. This concept appeared already in the classical works of Kre˘ın and

Nudel’man about T-systems, see [31, Ch. 2]. So in higher dimensions for Rnall zeros

are interior points but for [0,1]nwe can place zeros on the boundary.

Note that for n=1 we get for the even and the odd case the lower bound d+1.

This is the maximal number of zeros of a non-zero and non-negative polynomial on

[0,1].Forn=2 we get the following.

Corollary 5.5 For d ∈Nand X=[0,1]2(n =2) we have

CA2,2d≥(d+1)2and CA2,2d+1≥(d+1)2.

Theorems 5.2 and 5.4 give lower bounds on the Carathéodory number of SAn,k

by constructing one specific boundary moment sequence sand calculating its Cara-

théodory number CAn,k(s). But from the following considerations it will be clear

that Theorems 5.2 and 5.4 already show that in higher dimensions and degrees the

Carathéodory numbers behave very badly, see Theorem 5.6. Previous results in [16]

and [46] show that for n=2wehave

2≤lim inf

d→∞

CA2,d

|A2,d|≤lim sup

d→∞

CA2,d

|A2,d|≤3

4.(8)

From Theorems 5.2 and 5.4 we get the following limits.

Theorem 5.6 For X⊆Rnwith non-empty interior we have

lim inf

d→∞

CAn,d

|An,d|≥1−n

2nfor all n ∈N

and

lim

n→∞

CAn,d

|An,d|=1for all d ∈N.

Proof Follows by a direct calculation as in Equation (4). 

In (8), i.e., [16] and [46], we have seen that for n=2 the upper bound on the

Carathéodory number is considerably smaller than |A2,d|, namely 3

4·|A2,d|is an

upper bound. But Theorems 5.2,5.4, and 5.6 confirm the apprehensions in [15]onthe

Carathéodory numbers and their limits. Note that for X=[0,1]nthe following was

proved already in [15].

123

Carathéodory numbers from Hilbert functions 287

Theorem 5.7 ([15, Thm. 59]) For R[x1,...,xn]≤2on X=[0,1]nwe have

n+2

2−n≤CAn,2≤n+2

2−1.

Thus for higher dimensions n, even with fixed degree d, it is not possible to give

upper bounds CAn,d≤c·|An,d|with c<1 for all n.

Corollary 5.8 Let X⊆Rnwith non-empty interior and d ∈N.Forε>0there is

an N ∈Nsuch that for every n ≥N there is a moment sequence s ∈SAn,dresp. a

moment functional L :R[x1,...,xn]≤d→Rwith

CAn,d(s)≥(1−ε) ·n+d

n,

i.e., Lsis the conic combination of at least (1−ε) ·n+d

npoint evaluations lxi.

Proof Choose sresp. Las in Proposition 5.3. This has the desired property. 

So even when we work with the probably most well behaved moment problem,

i.e., polynomials, the Carathéodory number is cursed by high dimensionalities. In the

next section we study the consequences of these new lower bounds and their limits

for Hankel matrices and flat extension.

6 Hankel matrices and flat extension

Recall that for a finite dimensional space Aof measurable functions with basis A=

{a1,...,am}the Hankel matrix H(L)of a linear functional L:A2→Ris given by

H(L)=(L(aiaj))m

i,j=1, i.e.,

H(L)=X⎛

⎜

⎝

a1(x)a1(x) ... a1(x)am(x)

.....

a1(x)am(x) ... am(x)am(x)

⎞

⎟

⎠dμ(x)=X

sA(x)·sA(x)Tdμ(x)(9)

if μis a (signed) representing measure of L. Hence we have the following.

Lemma 6.1 Let Abe a finite dimensional vector space of measurable functions with

basis A={a1,...,am}.ForL:A2→Rwith L =k

i=1ci·lxi(ci∈R) we have

H(L)=



i=1

ci·sA(xi)·sA(xi)Tand rank H(L)≤k.

The following are equivalent:

(i) rank H(L)=k.

123

288 P. J. di Dio, M. Kummer

(ii) sA(x1), . . . , sA(xk)are linearly independent.

Proof By replacing xα,xβ, and xα+βby ai,aj, and ai,j=ai·aj, respectively, with

(9) the proof is verbatim the same as in [48, Prop. 17.21]. 

Note that the previous result holds for signed representing measures.

It is very hard to check whether a linear functional Lis a moment functional. If

Xis compact and A2contains an e>0onXthen one has to check the following

condition:

Ls(p)≥0∀p∈Pos(A2,X):= {a∈A2|a≥0}.

But the set of non-negative functions Pos(A2,X)on Xis in general hard to describe.

For example deciding, whether a polynomial p∈R[x1,...,xn]≤2dis non-negative,

is an NP-hard problem (for fixed d≥2 as a function of n), see e.g. [7, p.56]. One

approach to overcome this problem is to approximate non-negative polynomials with

sums of squares (SOS): Checking whether a given polynomial is a sum of squares is

equivalent to deciding whether a certain semidefinite program (SDP) is feasible, see

[7, §4.1.4], and (under some mild assumptions) one can solve an SDP up to a fixed

precision in time that is polynomial in the program description size [7, §2.3.1]. The

connection between the truncated moment problem and non-negative polynomials

run deep and can be found in a large number of publications on the truncated moment

problem, see e.g. [1,31,34,36,38,48].

Flat extension is another method to determine whether a linear functional L:

R[x1,...,xn]≤2d→Ris a moment functional, see e.g. [8,9,36,37,48]. Let D≥d

and L0:R[x1,...,xn]≤2D→Rbe a linear functional that extends L. An extension

L1:R[x1,...,xn]≤2D+2of L0is called flat with respect to L0if rank H(L1)=

rank H(L0). Then by the flat extension theorem, see [8,9]ore.g.[48, Thm. 17.35],

there are linear functionals Li:R[x1,...,xn]≤2D+2iwith rank (L0)=rank (Li)

such that Liextends Li−1for all i∈N. These determine a linear functional L∞:

R[x1,...,xn]→Rwhich is called a flat extension of L0(to all R[x1,...,xn]), i.e.,

every restriction L∞|R[x1,...,xn]≤2D+2is a flat extension of L∞|R[x1,...,xn]≤2Dfor all

D≥D. Exists such a flat extension L∞, then by the flat extension theorem L0is a

moment functional if L0(a2)≥0 for all a∈R[x1,...,xn]≤D. In this case Lis of

course a moment functional as well. It was open to which degree 2Dthe functional L

must be extended in order to have a flat extension. The upper bound of D≤2dfollows

immediately from the Carathéodory bound [8,9]. Part one of the following theorem is

due to Curto and Fialkow. Our new lower bounds on the Carathéodory number show

that D=2dis attained and is stated in part two of the following theorem.

Theorem 6.2 (i) For every moment functional L :R[x1,...,xn]≤2d→Rthere is a

D≤2d and an extension to a moment functional L0:R[x1,...,xn]≤2D→R

that admits a flat extension L∞:R[x1,··· ,xn]→R.

(ii) For every d ∈Nthere is an N ∈Nsuch that for every n ≥N there is a moment

functional L on R[x1,··· ,xn]≤2dsuch that D =2d in (i) is required.

123

Carathéodory numbers from Hilbert functions 289

Proof (i): By [16, Cor. 14] we have C:= CAn,2d(L)≤n+2d

n−1, i.e.,



i=1

ci·lxiwith ci>0

and the lxiare linearly independent on R[x1,...,xn]≤2d. Then L∞:R[x1,...,xn]

→Rdefined by L∞(f):= C

i=1ci·f(xi)is a flat extension of L0:= L|R[x1,...,xn]≤4d.

(ii): Let s∈SAn,2dresp. Ls:R[x1,...,xn]≤2d→Ras in Proposition 5.3 and

assume D=2d−c,c∈N. From the condition CAn,2d(s)≤n+D

nthat the Hankel

matrix of the flat extension must be at least the size of the Carathéodory number of s

we find that

1≤lim

n→∞ n+2d−c

n

CAn,2d(s)=lim

n→∞ n+2d−c

n

n+2d

n·n+2d

n

CAn,2d(s)

 

→1byThm.5.6

=lim

n→∞

(2d−c+1)···(2d)

(n+2d−c+1)···(n+2d)=0.

This is a contradiction, i.e., c=0 must hold. 

Example 6.3 Consider the moment sequences s=(sα)α∈Nn

0:|α|≤2dresp. functionals

L:R[x1,...,xn]≤2d→Rfrom Proposition 5.3 supported on the grid {1,...,d}n.

The condition CAn,2d(s)≤n+D

n, meaning that the size of the Hankel matrix must be

at least the size of Carathéodory number of s, shows that (n,d)=(9,2),(7,3),(6,4),

(6,5), and (n,6), for all n≥6, are small examples where the worst case extension

to degree D=2dis attained. Even for d=1015 the worst case extension is already

necessary for n=51.

Funding Open Access funding enabled and organized by Projekt DEAL.

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which

permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give

appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence,

and indicate if changes were made. The images or other third party material in this article are included

in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If

material is not included in the article’s Creative Commons licence and your intended use is not permitted

by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the

References

1. Akhiezer, N.I.: The classical moment problem and some related questions in analysis. Oliver & Boyd,

Edinburgh (1965)

2. Alon, N.: Combinatorial Nullstellensatz. Combin. Probab. Comput. 8, 7–29 (1999)

123

290 P. J. di Dio, M. Kummer

3. Atiyah, M.F., Macdonald, I.G.: Introduction to commutative algebra. Addison-Wesley Publishing Co.,

Reading, Mass.-London-Don Mills, Ont., (1969)

4. Bochnak, J., Coste, M., Roy, M.-F.: Real Algebraic Geometry. Springer-Verlag, Berlin (1998)

5. Bruns, W., Herzog, J.: Cohen-Macaulay rings. Cambridge University Press, Cambridge (1993)

6. Bréhard, F., Joldes, M., Lasserre, J.-B.: On a moment problem with holonomic functions. ISSAC ’19:

Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation, pp.

66–73 (2019)

7. Blekherman, G., Parrilo, P.A., Thomas, R.R. (eds.), Semidefinite optimization and convex algebraic

geometry, MOS-SIAM Series on Optimization, vol. 13, Society for Industrial and Applied Mathematics

(SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA (2013)

8. Curto, R., Fialkow, L.A.: Solution of the truncated moment problem for flat data. Mem. Amer. Math.

Soc. 119(568), (1996)

9. Curto, R., Fialkow, L.A.: Flat extensions of positive moment matrices: recursively generated relations.

Mem. Amer. Math. Soc. 136(648), (1998)

10. Curto, R., Fialkow, L.A.: Truncated K-moment problems in several variables. J. Op. Theory 54, 189–

226 (2005)

11. Dai, M., Baylou, P., Najim, M.: An efficient algorithm for computation of shape moments from run-

length codes or chain codes. Pattern Recognit. 25, 1119–1128 (1992)

12. di Dio, P.J.: The truncated moment problem, Ph.D. thesis, University of Leipzig (Jan 2018)

13. di Dio, P.J.: The multidimensional truncated Moment Problem: Gaussian and Log-Normal Mixtures,

their Carathéodory Numbers, and Set of Atoms. Proc. Am. Math. Soc. 147, 3021–3038 (2019)

14. di Dio, P.J.: The multidimensional truncated Moment Problem: Shape and Gaussian Mixture Recon-

struction from Derivatives of Moments. arXiv:1903.00790

15. di Dio, P.J., Schmüdgen, K.: The multidimensional truncated moment problem: The moment cone

(2018). arXiv:1809.00584

16. di Dio, P.J., Schmüdgen, K.: The multidimensional truncated Moment Problem: Carathéodory Num-

bers. J. Math. Anal. Appl. 461, 1606–1638 (2018)

17. Davis, P.J., Rabinowitz, P.: Methods of Numerical Integration, 2nd edn. Academic Press, Orlando, FL

(1984)

18. Eisenbud, D.: Commutative algebra: With a view toward algebraic geometry. Springer-Verlag, New

York (1995)

19. Eisenbud, D.: The geometry of syzygies: A second course in commutative algebra and algebraic

geometry. Springer-Verlag, New York (2005)

20. Fialkow, L.A.: The truncated K-moment problem: a survey. Theta Ser. Adv. Math. 18, 25–51 (2016)

21. Fialkow, L.A.: The core variety of a multi-sequence in the truncated moment problem. J. Math. Anal.

Appl. 456, 946–969 (2017)

22. Fialkow, L.A., Nie, J.: Positivity of Riesz functionals and solutions of quadratic and quartic moment

problems. J. Funct. Anal. 258, 328–356 (2010)

23. Gravin, N., Lasserre, J., Pasechnik, D.V., Robins, S.: The inverse moment problem for convex polytopes.

Discrete Comput. Geom. 48, 596–621 (2012)

24. Golub, G.H., Milfar, P., Varah, J.: A stable numberical method for inverting shape from moments.

SIAM J. Sci. Comput. 21(4), 1222–1243 (1999)

25. Grabiner, D.J.: Descartes’ rule of signs: another construction. Amer. Math. Monthly 106, 854–856

(1999)

26. Helton, J.W., Nie, J.: A Semidefinite Approach for Truncated K-Moment Problems. Found. Comput.

Math. 12, 851–881 (2012)

27. Huisman, J.: On the geometry of algebraic curves having many real components. Rev. Mat. Complut.

14, 83–92 (2001)

28. Jouanolou, J.-P.: Théorémes de Bertini et applications. Birkhäuser Boston Inc, Boston (1983)

29. Kemperman, J.H.B.: The General Moment Problem, a Geometric Approach. Ann. Math. Stat. 39,

93–122 (1968)

30. Kemperman, J.H.B.: Geometriy of the moment problem. Proc. Sym. Appl. Math. 37, 16–53 (1987)

31. Kre˘ın, M.G., Nudel’man, A.A.: The Markow Moment Problem and Extremal Problems. American

Mathematical Society, Providence, Rhode Island (1977)

32. Kunert, A.: Facial Structure of Cones of non-negative Forms, Ph.D. thesis, Universtity of Konstanz

(2014)

123

Carathéodory numbers from Hilbert functions 291

33. Landau, H.J. (ed.): Moments in Mathematics, Proceedings of Symposia in applied Mathematics, vol.

37. RI, American Mathematical Society, Providence (1980)

34. Lasserre, J.-B.: An introduction to polynomial and semi-algebraic optimization. Cambridge University

Press, Cambridge (2015)

35. Laurent, M.: Revisiting two theorems of Curto and Fialkow on moment matrices. Proc. Am. Math.

Soc. 133, 2965–2975 (2005)

36. Laurent, M.: Sums of Squares, Moment Matrices and Polynomial over Optimization, Emerging appli-

cation of algebraic geometry, IMA Vol. Math. Appl., vol. 149, Springer, New York, pp. 157–270

(2009)

37. Laurent, M., Mourrain, B.: A generalized flat extension theorem for moment matrices. Arch. Math.

(Basel) 93(1), 87–98 (2009)

38. Marshall, M.: Positive Polynomials and Sums of Squares. Mathematical Surveys and Monographs, no.

146, American Mathematical Society, Rhode Island, (2008)

39. Möller, H.M.: Kubaturformeln mit minimaler Knotenzahl. Numer. Math. 25, 185–200 (1976)

40. Milanfar, P., Verghese, G., Karl, W., Willsky, A.: Reconstructing polygons from moments with con-

nections to array processing. IEEE Trans. Signal Proc. 43, 432–443 (1995)

41. Nie, J.: The A-truncated K-moment problem. Found. Comput. Math. 14, 1243–1276 (2014)

42. Reznick, B.: Sums of even powers of real linear forms. Mem. Amer. Math. Soc., vol. 96, American

Mathematical Society, (1992). MEMO/0463

43. Richter, H.: Parameterfreie Abschätzung und Realisierung von Erwartungswerten. Bl. Deutsch. Ges.

Versicherungsmath. 3, 147–161 (1957)

44. Rogosinski, W.W.: Moments of non-negative mass. Proc. R. Soc. Lond. A 245, 1–27 (1958)

45. Rosenbloom, P.C.: Quelques classes de problème extrémaux. II. Bull. Soc. Math. France 80, 183–215

(1952)

46. Riener, C., Schweighofer, M.: Optimization approaches to quadrature: new characterizations of Gaus-

sian quadrature on the line and quadrature with few nodes on plane algebraic curves, on the plane and

in higher dimensions. J. Compl. 45, 22–54 (2018)

47. Scheiderer, C.: Sums of squares of regular functions on real algebraic varieties. Trans. Am. Math. Soc.

352, 1039–1069 (2000)

48. Schmüdgen, K.: The Moment Problem. Springer, New York (2017)

49. Shafarevich, I.R.: Basic algebraic geometry. Springer-Verlag, Berlin-New York, 1977, Translated from

the Russian by K. A. Hirsch, Revised printing of Grundlehren der mathematischen Wissenschaften,

Vol. 213 (1974)

50. Shohat, J.A., Tamarkin, J.D.: The Problem of Moments. Am. Math. Soc, Providence, R.I. (1943)

51. Stanley, R.P.: Hilbert functions of graded algebras. Adv. Math. 28, 57–83 (1978)

52. Stieltjes, T.J.: Recherches sur les fractions continues. Ann. Fac. Sci. Toulouse 8(4), J1–J122 (1894)

53. Stroud, A.H.: Approximate Calculation of Multiple Integrals. Prentice Hall, Prentice (1971)

Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps

and institutional affiliations.

123