Lorenzo Baldi
email: lorenzo.baldi@inria.fr

Bernard Mourrain

On the Effective Putinar's Positivstellensatz and Moment Approximation

We analyse the representation of positive polynomials in terms of Sums of Squares. We provide a quantitative version of Putinar's Positivstellensatz over a compact basic semialgebraic set S, with a new polynomial bound on the degree of the positivity certificates. This bound involves a Łojasiewicz exponent associated to the description of S. We show that if the gradients of the active constraints are linearly independent on S (Constraint Qualification condition), this Łojasiewicz exponent is equal to 1. We deduce the first general polynomial bound on the convergence rate of the optima in Lasserre's Sum-of-Squares hierarchy to the global optimum of a polynomial function on S, and the first general bound on the Hausdorff distance between the cone of truncated (probability) measures supported on S and the cone of truncated pseudomoment sequences, which are positive on the quadratic module of S.

Introduction

A fundamental question in Real Algebraic Geometry is how to describe effectively the set of polynomials which are positive1 on a given domain.

Clearly, the set of positive polynomials on R n contains the Sums of Squares of real polynomials (SoS). Let R[X] = R[X 1 , . . . , X n ] be the R-algebra of polynomials in the indeterminates X 1 , . . . , X n with real coefficients. The convex cone of SoS polynomials

Σ 2 := Σ 2 [X] = f ∈ R[X] | ∃r ∈ N, g i ∈ R[X] : f = g 2 1 + • • • + g 2 r is a subset of the convex cone of positive polynomials Pos(R n ) := { p ∈ R[X] | ∀x ∈ R n , p(x) ≥ 0 }.
But it is known since Hilbert [START_REF] Hilbert | Ueber die Darstellung definiter Formen als Summe von Formenquadraten[END_REF], that these cones differ: not all positive polynomials are SoS. A famous counter-example is Motzkin polynomial [START_REF] Motzkin | The arithmetic-geometric inequality[END_REF] of degree 6 in 2 variables, which is positive on R 2 but not a SoS. Such polynomials exists for any dimension n ≥ 2, but not in dimension 1 since univariate positive polynomials are SoS. For a domain S = S(g) = S(g 1 , . . . , g r ) = { x ∈ R n | g i (x) ≥ 0 for i = 1, . . . , r }, defined by inequalities g i ≥ 0 with g i ∈ R[X], that is, a basic closed semialgebraic set, the set Pos(S) of positive polynomials on S contains the quadratic module generated by the tuple of polynomials g = (g 1 , . . . , g r ), and defined by

Q = Q(g) := Σ 2 + Σ 2 • g 1 + • • • + Σ 2 • g r
and also the preordering O = O(g 1 , . . . , g r ) Q( j∈J g j : J ⊂ {1, . . . , r}).

A complete description of positive polynomials on S is given by the Krivine-Stengle Positivstellensatz:

Theorem 1.1 ( [START_REF] Krivine | Anneaux préordonnés[END_REF], [START_REF] Stengle | A nullstellensatz and a positivstellensatz in semialgebraic geometry[END_REF]). Let g be a tuple of polynomials and S = S(g). Then:

Pos(S) = {p ∈ R[X] | ∃s ∈ N, q 1 ,
q 2 ∈ O(g) s.t. q 1 p = p 2s + q 2 } This result is an extension of Artin's theorem [START_REF] Artin | Über die Zerlegung definiter Funktionen in Quadrate[END_REF], stating that globally positive polynomials are ratio of two SoS polynomials. But it induces a denominator in the representation of a positive polynomial.

Since for a general tuple g and n > 1, positive polynomials on S(g) do not all belong to the quadratic module Q(g) or even to the preordering O(g), it is natural to ask whether the convex cone Q(g) (resp. O(g)) is a good inner-approximation of Pos (S). A partial answer is given by two important results due to Schmüdgen and Putinar, and also known as denominator free Positivstellensatz. They require the following assumption:

Definition 1.2. Denote X 2 2 = X 2 1 + • • • + X 2 n .
We say that a quadratic module Q is Archimedean if there exists r ∈ R such that r 2 -X 2 2 ∈ Q. We recall these two results, which are central in the paper: Theorem 1.3 (Schmüdgen's Positivstellensatz [START_REF] Schmüdgen | The K-moment problem for compact semi-algebraic sets[END_REF]). Let S(g) be a compact basic semialgebraic set. Then f > 0 on S(g) implies f ∈ O(g).

Theorem 1.4 (Putinar's Positivstellensatz [START_REF] Putinar | Positive Polynomials on Compact Semi-algebraic Sets[END_REF]). Let S(g) be a basic closed semialgebraic set. If Q(g) is Archimedean, then f > 0 on S(g) implies f ∈ Q(g).

As a consequence of the first result, notice that S(g) compact implies that O(g) is Archimedean. On the other hand there are examples with S(g) compact but Q(g) not Archimedean (see e.g. [PD01, ex. 6.3.1]).

Since a positive polynomial f ∈ Pos(S) on a compact basic semialgebraic set S can be approximated uniformly on S by the polynomial f + ε, which is strictly positive on S for ε > 0, these results show that any f = lim ε→0 f + ε positive on S is the limit of polynomials in Q(g) (resp. O(g)).

Unfortunately, the degree of the representation of f + ε in Q(g) goes to infinity as ε → 0, see [START_REF] Stengle | Complexity Estimates for the SchmüDgen Positivstellensatz[END_REF].

In this paper, we provide quantitative versions of Theorem 1.4. We give new bounds on the degree of the representation in Q(g), which control the quality of approximation of positive polynomials by elements in Q(g). For this problem, also known as Effective Putinar Positivstellensatz, our main result is Theorem 1.7, which provides the first polynomial bounds in the intrinsic parameters associated to g and f .

The proof of Theorem 1.7 is developed in Section 2 and Section 3. In the proof and in the bound of the theorem a special role is played by the Łojasiewicz exponent Ł, comparing the distance and the algebraic distance from S, see Definition 2.4. In Theorem 2.11 we prove that Ł = 1 in regular cases, i.e. when a regularity condition coming from Optimization is satisfied, see Definition 2.7. To our best knowledge this is the first analysis of the Łojasiewicz exponent under regularity assumptions of any kind. Corollaries to our main results in regular cases with Ł = 1 are described in Corollary 3.9, Corollary 4.4 and Corollary 5.9.

Polynomials whose representation in the quadratic module Q(g) is of degree bounded by 2 , ∈ N, are used to define a hierarchy of convex optimization problems, also known as Lasserre's hierarchy, whose optimum value converges to the global optimum of a polynomial f ∈ R[X] on S under the Archimedean assumption [START_REF] Lasserre | Global Optimization with Polynomials and the Problem of Moments[END_REF]. We describe these hierarchies in Section 4. In Theorem 4.2 and Theorem 4.3, we deduce from Theorem 1.7 new polynomial bounds on the convergence rate of this hierarchy to the global optimum, in terms of the order of the hierarchy.

Considering the dual problem, we also analyse the quality of approximation of measures by truncated pseudo-moment sequences used in Lasserre moment hierarchy. In Theorem 1.8, we provide new bounds on the Hausdorff distance between the cone of truncated probability measures (supported on S) and the outer convex set of truncated positive pseudo-moment sequences of unit mass, and on the rate of convergence when the order goes to infinity. The proof of Theorem 1.8 is developed in Section 5. The bounds involve intrinsic parameters associated to g and the degree t of truncation. As an intermediate step, in Theorem 5.7 we also bound the Hausdorff distance between truncated positive pseudo-moment sequences and non-normalized measures.

Truncated quadratic modules and positive polynomials

To analyse the degree in these SoS representations, we introduce the truncated quadratic modules at degree (or level) ∈ N, i.e. the polynomials in Q(g) that are generated in degree ≤ :

Q (g) = s 0 + r i=1 s i g i | s j ∈ Σ 2 , deg s 0 ≤ , deg s i g i ≤ ∀i = 1, . . . r ⊂ Q(g) ∩ R[X] .
(1)

where R[X] is the vector space of polynomials of degree ≤ . Effective versions of Schmüdgen and Putinar's Positivstellensatz, that give degree bounds for the representation in truncaded preorderings and quadratic modules, have been proved by Schweighofer and Nie.

Theorem 1.5 ([Sch04]). For all g = g 1 , . . . g r ⊂ R[X] = R[X 1 , . . . , X n ] defining ∅ S(g) = S ⊂ (-1, 1) n there exists 0 < c ∈ R (depending on g and n) such that, if f ∈ R[X] d is strictly positive on S with minimum f * = min x∈S f (x) > 0, we have f ∈ O (g) if ≥ cd 2 1 + d 2 n d f X f * c . Theorem 1.6 ([NS07]). For all g = g 1 , . . . g r ⊂ R[X] = R[X 1 , . . . , X n ] defining an Archimedean quadratic module Q = Q(g) and ∅ S(g) = S ⊂ (-1, 1) n , there exists 0 < c ∈ R (depending on g and n) such that, if f ∈ R[X] d is strictly positive on S with minimum f * = min x∈S f (x) > 0, we have f ∈ Q (g) if ≥ c exp d 2 n d f X f * c .
The norm • X used in [START_REF] Schweighofer | On the complexity of Schmüdgen's Positivstellensatz[END_REF] and [START_REF] Nie | On the complexity of Putinar's Positivstellensatz[END_REF] is the max norm of the coefficients of the polynomial f w.r.t. the weighted monomial basis { |α|! α 1 !...α n ! X α : |α| ≤ d}, while the one we will use is the max norm on [-1, 1] n . We describe this norm and fix some notation. Notation. Throughout the article:

• f ∈ R[X] is a polynomial in n variables of degree d = d(f );
• S = S(g) = S(g 1 , . . . , g r ) is the basic closed semialgebraic set defined by g = g 1 , . . . , g r ;

• d(g) = max i deg g i is the maximum degree of the inequalities defining S;

• f * = min x∈S f (x) is the minimum of f on S, and unless otherwise stated f * > 0;

• • denotes the max norm of a polynomial on [-1, 1] n , i.e. h = max x∈[-1,1] n |h(x)|; • ε(f ) = f * f is a measure of how close is f to have a zero on S.
For convenience we will prove our theorem in a normalized setting. Normalisation assumptions. In the following, we assume that

• 1 -X 2 2 ∈ Q(g), • g i ≤ 1
2 ∀i ∈ {1, . . . , r}.

(2)

We can always be in this setting by a change of variables if we start with an Archimedean quadratic module: if r 2 -X 2 ∈ Q(g) then 1 -X 2 ∈ Q(g(rX)) (i.e. the quadratic module generated by g i (rX 1 , . . . , rX n )). By replacing g i with g i 2 g i , we can also assume without loss of generality that the second point is satisfied.

The main result of the paper is the following theorem. It is an effective, general version of Putinar's Positivstellensatz with polynomial bounds for fixed n.

Theorem 1.7. Assume n ≥ 2 and let g 1 , . . . , g r ∈ R[X] = R[X 1 , . . . , X n ] satisfying the normalization assumptions (2). Let f ∈ R[X] such that f * = min x∈S f (x) > 0. Let c, Ł be the Łojasiewicz coefficient and exponent given by Definition 2.4. Then f ∈ Q (g) if ≥ O(n 3 2 5nŁ r n c 2n d(g) n d(f ) 3.5nŁ ε(f ) -2.5nŁ ) = γ(n, g) d(f ) 3.5nŁ ε(f ) -2.5nŁ ,
where γ(n, g) ≥ 1 depends only on n and g.

Notice that the only parameters in the bound that depend on f are d(f ) and ε(f ). We also remark that exponents in Theorem 1.7 have been simplified for the sake of readability and are not optimal: see Equation (21) for sharper bounds, especially for the case n 0. Moreover we remark that the assumption n ≥ 2, only used to do this simplification, is not a serious limitation since the univariate case is already well studied, see for instance [START_REF] Powers | Polynomials that are positive on an interval[END_REF].

In the definition of ε(f ) we use the max norm

• on [-1, 1] n instead of • X used in [NS07]
, because it does not depend on the choice of a basis and on the representation of the polynomials. However, for polynomials of bounded degree, the two norms are equivalent. Using [NS07, lem. 7] to express our bound with • X would result in an extra factor 22.5nŁ n 2.5d(f )nŁ d(f ) 2.5nŁ , while keeping the exponent of ε(f ).

In Section 3 we develop in detail the proof of Theorem 1.7. The ingredients for the proof are introduced in Section 2. The main differences with the one of [START_REF] Nie | On the complexity of Putinar's Positivstellensatz[END_REF] is the use of an effective Schmüdgen's Positivstellensatz on the unit box [START_REF] Laurent | An effective version of Schmüdgen's Positivstellensatz for the hypercube[END_REF], and an effective approximation of regular functions on the unit interval, see Theorem 2.12. Moreover in Section 2.2 we prove that the main exponent of the bound, i.e. the Łojasiewicz exponent Ł, is equal to 1 for regular polynomial optimization problems, see Definition 2.7 and Theorem 2.11. The corollary of Theorem 1.7 in these regular cases is Corollary 3.9.

As a corollary of Theorem 1.7 we analyse the convergence of Lasserre hierarchies used in polynomial optimization. In Section 4 we focus on the optimum of the hierarchy, proving in Theorem 4.2 and Theorem 4.3 a new, general polynomial convergence as corollary of our main result (see Corollary 4.4 for regular Polynomial Optimization Problems). On the other hand in Section 5 we focus on the convergence of the feasible truncated pseudo-moment sequences of the moment hierarchy to truncated moment sequences of measures supported on S: we prove in Theorem 1.8 that we can bound their Hausdorff distance using Theorem 1.7.

Truncated pseudo-moment sequences and measures

Dualizing our point of view, we consider the convex cone M(S) of Borel measures supported on S, which is dual to Pos(S). We denote by M (1) (S) the set of Borel probability measures supported on S.

The dual of polynomials is described as follows (see [START_REF] Mourrain | Polynomial-Exponential Decomposition From Moments[END_REF] for more details). For L ∈

(R[X]) * = hom R (R[X], R), we denote L|f = L(f ) the application of L to f ∈ R[X], to emphasize the dulity pairing between R[X] and (R[X]) * . Recall that (R[X]) * R[[Y]] R[[Y 1 , . . . , Y n ]],
with the isomorphism given by:

(R[X]) * L → α∈N n L|X α Y α α! ∈ R[[Y]],
where

{ Y α α! } is the dual basis 2 to {X α }, i.e. Y α X β = α! δ α,β
. With this basis we can also identify L ∈ (R[X]) * with its sequence of coefficients (pseudo-moments of L) (L α ) α , where L α = L|X α . Among all the linear functionals of special importance are the ones coming from a measure, i.e. L ∈ R[X] * such that there exists a Borel measure µ ∈ M(S) with L|f = f dµ for all f ∈ R[X]. In this case the sequence (µ α ) α associated with µ is the sequence of moments: µ α = X α dµ. We are interested in the case when S is compact. In such a case the moment problem is determinate, i.e. the sequence of moments (µ α ) α determines uniquely µ ∈ M(S), see for instance [START_REF] Schmüdgen | The Moment Problem[END_REF]ch. 14]. Therefore we will identify µ with its associated linear functional acting on polynomials (or equivalently with its sequence of moments), so that M(S) ⊂ (R[X]) * .

We will work in the truncated setting, i.e. when we restict our linear functionals to a fixed, finite dimensional subspace of R[X]. In particular we denote (•) [t] the restriction of a linear functional (or of a family of linear functionals) to R[X] t , i.e. to polynomials of degree at most t. In coordinates, if t] is the truncation of the pseudo-moment sequence to degree t.

L = (L α ) |α|≤d ∈ R[X] * d then L [t] = (L α ) |α|≤t ∈ R[X] * t , i.e. L [
We are interested in the dual algebraic objects to truncated quadratic modules: the truncated positive linear functionals

L (g) = { L ∈ (R[X] ) * | ∀q ∈ Q (g) L|q ≥ 0 } = Q (g) ∨ ,
i.e. L (g) is the dual convex cone to Q (g). See [START_REF] Rockafellar | Convex Analysis[END_REF] for more about convex cones and convex duality, and [START_REF]Semidefinite Optimization and Convex Algebraic Geometry[END_REF] for their use in Optimization and Convex Algebraic Geometry. We define the affine section

L (1) (g) = L ∈ L (g) | L|1 = 1 .
Let t = 2 . We verify that for L ∈ L (g), L|1 = 0 implies L [t] = 0, in order to prove that L (1) (g) [t] is a generating section of L (g) [t] . Assume that L|1 = 0. For all h ∈ R[X] t and x ∈ R, we have

0 ≤ L (1 + xh) 2 = L|1 +2x L|h +x 2 L h 2 . If L|1 = 0, then the polynomial x → 2x L|h +x 2 L h 2
is positive on R and has a zero at x = 0. Thus x = 0 is a double root and L|h = 0. This implies that L restricted to polynomials of degree ≤ t is zero, i.e. L [t] = 0. Therefore if L [t] 0 then L|1 > 0 and

L [t] = L|1 L [t] L|1 , with L [t]
L|1 ∈ L (1) (g) [t] . This shows that L (1) (g) [t] is a generating section of L (g) [t] .

Truncated positive linear functionals are an outer approximation of measures supported on S. They are used in Polynomial Optimization Problems (POP) to compute lower approximations of the minimum of a polynomial function f on S, see Section 4. Under the Archimedean assumption, convergence to measures of the linear functionals realizing the lower approximations have been proved in [START_REF] Schweighofer | Optimization of Polynomials on Compact Semialgebraic Sets[END_REF]th. 3.4] for POP.

However nothing is said about the rate of convergence. We use Theorem 1.7, quantifying how good is the inner approximation of positive polynomials by truncated quadratic modules, to answer the question we are interested in: how good is the outer approximation of (probability) measures by truncated positive linear functionals (of total mass one)? Theorem 1.8 gives the answer. In the theorem we bound the Hausdorff distance d H (•, •) between the outer approximation and the measures supported on S, where d

H (A, B) = max sup a∈A d(a, B), sup b∈B d(A, b) .
Theorem 1.8. Assume n ≥ 2 and that the normalisation assumptions (2) are satisfied, and in particular that 1-

X 2 2 = q ∈ Q 0 (g). Let 0 < ε ≤ 1 2 , t ∈ N + and ∈ N such that ≥ γ(n, g) 6 2.5nŁ t 6nŁ n+t t 2.5nŁ ε -2.5nŁ
and ≥ 2t + 0 , with γ(n, g) given by Theorem 1.7. Then

d H (M (1) (S) [2t] , L (1) (g) [2t] ) ≤ ε.
The proof of Theorem 1.8 is developed in Section 5. The corollary of Theorem 2.11 in regular cases with Ł = 1 is Corollary 5.9.

Related works

Complexity analysis in Real Algebraic Geometry is an active area of research, where obtaining good upper bounds is challenging. See for instance [START_REF] Lombardi | An elementary recursive bound for effective Positivstellensatz and Hilbert 17-th problem[END_REF] for elementary recursive degree bounds in Kivrine-Stengle Positivstellensatz, and [START_REF] Safey El Din | On the complexity of computing real radicals of polynomial systems[END_REF] for computation complexity of real radicals. Among all the Stellensätzen, we consider Putinar's Positivstellensatz, which allows a denominator free representation of strictly positive polynomials and has well-know applications in Polynomial Optimization. The representation of strictly positive polynomials has a long history. For instance Pölya [START_REF] Pólya | Über positive Darstellung von Polynomen[END_REF] gave a representation of homogeneous polynomials f strictly positive on the simplex ∆ as ratio of a polynomial with positive coefficients and X k 2 , for some k. It is interesting to notice that, although no explicit degree bounds were presented, the degree of the representation depends on the sup norm of f on ∆ and on its minimum f * > 0, i.e. on ε(f ), in analogy with Theorem 1.7. Another representation for homogeneous polynomials has been proved by Reznick [START_REF] Reznick | Uniform denominators in Hilbert's seventeenth problem[END_REF], where it is shown that an homogeneous polynomial f strictly positive on R n \ {0} (a positive definite form) can be written as ratio of even powers of linear forms and X k 2 , for some k. Degree bounds for the representation are provided, and again we find a dependence on ε(f ) (defined restricting f to the n -1 hypersphere) with exponent equal to -1.

A general, effective version of Putinar's Positivstellensatz have been proved in [START_REF] Nie | On the complexity of Putinar's Positivstellensatz[END_REF] (see also [START_REF] Schweighofer | On the complexity of Schmüdgen's Positivstellensatz[END_REF] for a general effective Schmüdgen's Positivstellensatz). This result is used in [START_REF] Magron | On Exact Reznick, Hilbert-Artin and Putinar's Representations[END_REF] to give bounds on the degree of rational SoS positivity certificates, which are exponential in the bit-size of the input polynomials f , g. Compared to [START_REF] Nie | On the complexity of Putinar's Positivstellensatz[END_REF], Theorem 1.7 gives degree bounds, which are polynomial and not exponential in ε(f ). This implies a polynomial rate convergence of Lasserre hierarchies, see Theorem 4.2, and not logarithmic as in [START_REF] Nie | On the complexity of Putinar's Positivstellensatz[END_REF]. For special semialgebraic sets, the bounds on the convergence rate can be improved: see for instance [START_REF] Laurent | An effective version of Schmüdgen's Positivstellensatz for the hypercube[END_REF] for convergence on the unit box and [START_REF] Fang | The sum-of-squares hierarchy on the sphere and applications in quantum information theory[END_REF] for the unit sphere. The convergence rate of the upper bounds of Lasserre SoS density hierarchy over the sphere has been studied in [START_REF] De | Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere[END_REF].

The proof of Theorem 1.7 is based on the construction of a perturbation polynomial q ∈ Q(g) and the reduction to a simpler semialgebraic set. This construction of the perturbation polynomial q using univariate SoS, has already been used in [START_REF] Schweighofer | On the complexity of Schmüdgen's Positivstellensatz[END_REF], [START_REF] Schweighofer | Optimization of Polynomials on Compact Semialgebraic Sets[END_REF], [START_REF] Nie | On the complexity of Putinar's Positivstellensatz[END_REF], [START_REF] Averkov | Constructive Proofs of some Positivstellensätze for Compact Semialgebraic Subsets of R d[END_REF], [START_REF] Kurdyka | Convexifying Positive Polynomials and Sums of Squares Approximation[END_REF]. In [START_REF] Hoang | On the complexity of Putinar-Vasilescu's Positivstellensatz[END_REF] Mai and Magron investigate with a similar technique the representation of strictly positive polynomials on arbitrary semialgebraic sets as ratio of polynomials in the quadratic module and (1 + X 2 2 ) k for some k, giving degree bounds for the representation. These bounds are polynomial on f * (and thus on ε(f )), but the exponent and the constant are not explicit in the general case. Moreover they remark that they were not able to derive a polynomial Effective Putinar's Positvstellensatz using their perturbation polynomials, defined recursively.

Our main improvements in the proof are the generalisation from univariate SoS or recursively defined perturbation polynomials to a positive polynomial echelon function, see Section 2.3, and the use of an Effective Schmüdgen's Positivstellensatz on the unit box from [START_REF] Laurent | An effective version of Schmüdgen's Positivstellensatz for the hypercube[END_REF]. Moreover in Section 2.2 we analyse regular cases that result in very simple exponents, see Corollary 3.9. Corollary 3.9 can be applied in particular in the case of a single ball constraint, that was analysed in [START_REF] Hoang | On the complexity of Putinar-Vasilescu's Positivstellensatz[END_REF] for the Putinar-Vasilescu's Positivstellensatz, that introduces a denominator: the exponent in this case is equal to -65, while Corollary 3.9 gives -2.5n. We conjecture that it is possible to remove the dependence on n in the exponent of the Effective Putinar's Positivstellensatz.

This approach with a perturbation polynomial q has also been used in [START_REF] Kurdyka | Convexifying Positive Polynomials and Sums of Squares Approximation[END_REF] to prove a Weierstrass Approximation theorem on compact sets for positive polynomials, where the approximation is done with polynomials in the quadratic module Q(g). We obtain an equivalent result with our polynomial echelon functions in Theorem 4.1 with bounds on the degree of q.

Convergence of pseudo-moments sequences to measures in Lasserre's hierarchies has been studied in [START_REF] Schweighofer | Optimization of Polynomials on Compact Semialgebraic Sets[END_REF] for Polynomial Optimization Problems and more generally in [START_REF] Tacchi | Convergence of Lasserre's hierarchy: the general case[END_REF] for Generalized Moment Problems (GMP). The convergence rates of moment hierarchies in GMP over the simplex and the sphere have been studied in [START_REF] Kirschner | Convergence rates of RLT and Lasserre-type hierarchies for the generalized moment problem over the simplex and the sphere[END_REF]. To our best knowledge there is no analysis of the convergence rate for general compact basic semialgebraic sets in the literature. In Theorem 1.8 we prove such a rate of convergence for the pseudo-moment sequences used in Polynomial Optimization, deducing this speed from Theorem 1.7.

The ingredients of the proof

To prove the polynomial bound for the Effective Putinar's Positivstellensatz (Theorem 1.7), we proceeds as follows, refining the approach in [START_REF] Schweighofer | Optimization of Polynomials on Compact Semialgebraic Sets[END_REF], [START_REF] Nie | On the complexity of Putinar's Positivstellensatz[END_REF], [START_REF] Averkov | Constructive Proofs of some Positivstellensätze for Compact Semialgebraic Subsets of R d[END_REF]:

• We perturb f into a polynomial p such that p is strictly positive on the box [-1, 1] n and fp is in the quadratic module Q(g);

• We compute an SOS representation of p in Q(1 -X 2 2 ) to deduce the representation of f ∈ Q(g).
Notice that if f > 0 on [-1, 1] n then we can directly apply Theorem 3.8 and Lemma 3.4 to conclude the proof. Therefore in the following we always assume that there exists

x ∈ [-1, 1] n \ S such that f (x) ≤ 0.
To compute the perturbed polynomial p, we use a univariate echelon-like polynomial, which shape and degree depends on the distance between a level-set of f and S and on a lower bound of the algebraic distance to S. We detail these ingredients hereafter.

Distance between level sets of f and S

We define the complementary in [-1, 1] n of a neighbourhood of S, where f is strictly smaller than f * :

A = { x ∈ [-1, 1] n | f (x) ≤ 3f * 4
} that is a sublevel set of the function f . We are going to bound the distance from A to S in terms of ε(f ). We recall first a Markov inequality theorem, bounding the norm of the gradient of a polynomial function on a convex body, in the special case of the box

[-1, 1] n . Theorem 2.1 ([KR99, th. 3]). Let p ∈ R[X] d be a polynomial of degree ≤ d. Then: ∇p 2 ≤ (2d 2 -d) p .
Recall that the Lipschitz constant L f of f is the smallest real number such that f (x)f (y) ≤ L f xy 2 for all x, y in the domain of f . Using Theorem 2.1 to bound the Lipschitz constant of f on [-1, 1] n , we can lower bound the distance between A and S. Proposition 2.2. Let A and S be as above. Then d H (A, S)

≥ ε(f ) 8d 2 . Proof. We first relate the Lipschitz constant L f of f on [-1, 1] n with f .
From the mean value theorem we deduce that for all x, y ∈ [-1, 1] n we have f (x)f (y) ≤ ∇f 2 xy 2 . Then from the definition of Lipschitz constant and Theorem 2.1:

L f ≤ ∇f 2 ≤ (2d 2 -d) f ⇒ 1 L f ≥ 1 (2d 2 -d) f . (3) Now let x ∈ A and y ∈ S. By definition of L f we have f (x) -f (y) ≤ L f x -y 2 . Since x ∈ A we have f (x) ≤ 3f * 4 ; since y ∈ S we have f (y) ≥ f * : thus f (x) -f (y) ≥ f * 4 and x -y 2 ≥ f * 4L f
. As the inequality hold for all x ∈ A and y ∈ S we can use Equation (3) to conclude:

d H (A, S) ≥ f * 4L f ≥ f * 4(2d 2 -d) f = ε(f ) 4(2d 2 -d) ≥ ε(f ) 8d 2 .

Bounds on the algebraic distance to S

The algebraic distance to the set S is the continuous semialgebraic function defined by

G(x) = |min{g 1 (x), . . . , g r (x), 0}|.
Clearly, G(x) = 0 if and only if x ∈ S, and G(x) > 0 if x S. We are going to bound from below the function

G on A, that is find δ ∈ R >0 such that ∀x ∈ A, G(x) ≥ δ (4)
(such a δ exists since A is compact and G(x) > 0 on A).

To express such a δ in terms of ε(f ), we use Łojasiewicz inequalities, introduced by Łojasiewicz in [Łoj59], following and expanding the approach in [NS07, lem. 13].

Theorem 2.3 ([Łoj59], [BCR98, cor. 2.6.7]). Let B be a closed and bounded semialgebraic set and let f , g be two continuous semialgebraic functions from B to R such that f -1 (0) ⊂ g -1 (0). Then there exists c, Ł ∈ R >0 such that ∀x ∈ B:

|g(x)| Ł ≤ c|f (x)|.
We use now Theorem 2.3 and Proposition 2.2 to bound δ in terms of ε(f ).

Definition 2.4. Let c, Ł be the constant and exponent of Łojasiewicz inequalities (Theorem 2.3) for the functions

G : x ∈ [-1, 1] n → G(x) = |min{g 1 , . . . , g r (x), 0}| and D : x ∈ [-1, 1] n → D(x) = d(x, S), that is, for x ∈ [-1, 1] n D(x) Ł ≤ c G(x).
(5)

These constant and exponent are well-defined by Theorem 2.3, since the functions D and G are continuous semialgebraic and

S = D -1 (0) = G -1 (0). Lemma 2.5. We can choose δ = 1 c ε(f ) 8d 2 Ł
in Equation (4), where c, Ł are defined in Definition 2.4. Proof. By Proposition 2.2, we have

D(x) = d(x, S) ≥ ε(f ) 8d 2 for x ∈ A. Then from Equation (5), we deduce that for x ∈ A, ε(f ) 8d 2 Ł ≤ cG(x) ⇒ G(x) ≥ 1 c ε(f ) 8d 2 Ł . Therefore, we can choose δ = 1 c ε(f ) 8d 2 Ł .
The exponent Ł in Definition 2.4 will play an important role in the bounds of the Effective Putinar's Positivstellensatz. We show now that, under generic assumptions, we can choose Ł = 1, as suggested in the following example.

Example 2.6. Consider the univariate polynomial g(X) = ε 2 -X 2 and let

S = S(g) = [-ε, ε] ⊂ [-1, 1]. Now let x ∈ [-1, 1]
and D, G be as in Definition 2.4. It is easy to show that:

D(x) ≤ 1 2ε G(x). Indeed, if for example ε ≤ x ≤ 1, we have D(x) = x -ε and G(x) = x 2 -ε 2 = (x + ε)(x -ε) and D(x) = 1 x+ε G(x) ≤ 1 2ε G(x)
. This shows that we can choose Ł = 1 for all ε > 0. On the other hand if ε = 0, i.e. g(X) = -X 2 and S = {0}, we have a singular equation. A simple computation shows that it is not possible to choose Ł = 1 in this case. The minimum Ł satisfying the inequality is Ł = 2.

We introduce a regularity condition needed to prove Ł = 1, generalizing Example 2.6. This is a standard condition in optimization (see [Ber99, sec. 3.3.1]), which implies the so-called Karush-Kuhn-Tucker (KKT) conditions [Ber99, prop. 3.3.1].

Definition 2.7. Let x ∈ S(g). The active constraints at x are the constraints g i 1 , . . . , g i m such that g i j (x) = 0. We say that the Constraint Qualification condition (CQC) holds at x if for the active constraints g i 1 , . . . , g i l at x, the gradients ∇g i 1 (x), . . . , ∇g i m (x) are linearly independent.

Lemma 2.8. Let y ∈ R n \ S(g), and let z be a point in S = S(g) minimizing the distance of y to S, that is d(y, S) = yz 2 . If { g i : i ∈ I } are the active constraints at z and the CQC holds, then there exist

λ i ∈ R ≥0 such that: y -z = i∈I λ i ∇(-g i )(z). Proof. Fix y ∈ R n . Notice that y -x = - ∇ y-x 2 2 2
, where the gradient is take w.r.t. x. Moreover z ∈ S such that d(y, S) = yz 2 is a minimizer of the following Polynomial Optimization Problem:

min x y -x 2 2 2 : g i (x) ≥ 0 ∀i ∈ {1, . . . , r}.
Since the CQC holds at z, we deduce from [Ber99, prop. 3.3.1] that the KKT conditions hold. In particular:

∇ y -z 2 2 2 = i∈I λ i ∇g i (z)
For some

λ i ∈ R ≥0 . Therefore y -z = - ∇ d(y,z) 2 2 = i∈I λ i ∇(-g i )(z).
We first fix a point z ∈ S and consider the points y such that the closest point to y on S is z. We prove that Ł = 1 in the sector of these y where all the active constraints at z are strictly negative at y. Lemma 2.9. Let D, G as in Definition 2.4 and let z ∈ S(g) with active constraints g i : i ∈ I. Then there exists ε = ε (z) > 0 and constant c = c (z) > 0 such that for all y with:

• D(y) = d(y, S) = y -z 2 ; • D(y) ≤ ε ; • g i (y) < 0 for all i ∈ I, we have D(y) ≤ c G(y).
Proof. Let z ∈ S and y ∈ R n be such that D(y) = yz 2 . Consider the Taylor expansion of g i at z for the active constraints { g i : i ∈ I }: there exists h i (y) = (h i,1 (y), . . . , h i,n (y)), where lim y→z h i,j (y) = 0, such that:

g i (y) = ∇g i (z) • (y -z) + n j=1 h i,j (y)(y i -z i ) = ∇g i (z) • (y -z) + h i (y) • (y -z). ( 6
)
In other words, the h i (y) • (yz) is the remainder of the first order Taylor approximation. Since the CQC is satisfied at z we can apply Lemma 2.8: there exists λ = (λ i : i ∈ I) with y-z = i∈I λ i ∇(-g i )(z).

Substituting we obtain ∀i ∈ I:

g i (y) = - j∈I λ j (∇g i (z) • ∇g j (z)) + h i (y) • (y -z).
We denote:

• g I (y) = (g i (y) : i ∈ I);

• J I (z) = Jac(g I )(z) = (∇g i (z)) i∈I the Jacobian matrix;

• N I (z) = (∇g i (z) • ∇g j (z)) i,j = J I (z) t J I (z) the Gram matrix of ∇g i (z); and

• h(y) = (h i,j (y)) i,j .

With this notation we get:

g I (y) = -N I (z)λ + h(y)(y -z).
Since CQC hold at z, the ∇g i (z) are linearly independent and thus N I (z) is invertible. Indeed, if

N I (z) is not invertible then there exists 0 v ∈ R |I| such that N I (z)v = 0. Therefore 0 = v t N I (z)v = (J I (z)v) t J I (z)v = J I (z)v 2 2 .
Hence J I (z)v = 0, contradicting the linear independence of ∇g i (z) : i ∈ I. Thus we can solve for λ: λ = -N I (z) -1 g I (y) + N I (z) -1 h(y)(yz).

(7)

Recall from Lemma 2.8 that we have:

y -z = i∈I λ i ∇(-g i )(z) = -J I (z)λ.
Substituting λ from Equation (7) we obtain:

y -z = J I (z)N I (z) -1 g I (y) -J I (z)N I (z) -1 h(y)(y -z).
Taking the norm we deduce that:

y -z 2 = J I (z)N I (z) -1 g I (y) -J I (z)N I (z) -1 h(y)(y -z) 2 ≤ J I (z) 2 N I (z) -1 2 g I (y) 2 + J I (z) 2 N I (z) -1 2 h(y) 2 y -z 2
where • 2 denotes the 2-norm (resp. operator norm) of vectors (resp. matrices). Therefore:

1 -J I (z) 2 N I (z) -1 2 h(y) 2 y -z 2 ≤ J I (z) 2 N I (z) -1 2 g I (y) 2 (8)
Notice that:

• g I (y) 2 = i∈I g i (y) 2 ≤ √ |I| max i∈I g i (y) ≤ √ r G(y), since G(y) = min{0, g i (y) : i ∈ {1, . . . , r}} = max{0, g i (y) : g i (y) < 0}
and g i (y) < 0 for all i ∈ I by hypothesis;

• 1 -J I (z) 2 N I (z) -1 2 h(y) 2 ≥ 1 2 if y is close enough to S. Indeed h i,j → 0 when y → z, i.e. when yz 2 = d(y, S) = D(y) is going to zero. Thus we can choose ε such that D(y) ≤ ε

implies 1 -J I (z) 2 N I (z) -1 2 h(y) 2 ≥ 1 2 .
Then we deduce from Equation (8):

D(y) = y -z 2 ≤ 2 √ r J I (z) 2 N I (z) -1 2 G(y)
when D(y) ≤ ε , that proves the lemma with c = 2

√ r J I (z) 2 N I (z) -1 2 .
We generalize the previous lemma, removing the assumption that all the active constraints are negative at y. Lemma 2.10. Let D, G as in Definition 2.4 and assume that the CQC hold at z ∈ S = S(g). Then there exists ε = ε (z) > 0 and constant c = c (z) > 0 such that for all y with:

• D(y) = d(y, S) = y -z 2 ; • D(y) ≤ ε ; we have D(y) ≤ c G(y).
Proof. Let y and z be as in the hypothesis and let g i : i ∈ I be the active constraints at z. Notice that if y = z ∈ S then D(y) = G(y) = 0 and there is nothing to prove. So we assume that y S: there exists i ∈ {1, . . . , r} s.t. g i (y) < 0. Moreover, from Lemma 2.9 we only need to consider the case where there exists i ∈ I such that g i (y) ≥ 0. If we consider the Taylor expansion of g i at z, we obtain:

i ∈ I -⇒ 0 > g i (y) = ∇g i (z) • (y -z) + h i (y) • (y -z),
with the same notation as in Equation ( 6). This implies that there exists δ > 0 such that ∇(-g i )(z) • (yz) ≥ δ, for all i ∈ I -, when y is close enough to z. We want to reduce to the case of only negative inequalities. We define:

• G -(y) = min{0, g i (y) : i ∈ I -} ;

• S -= S(g i : i ∈ I -);

• D -(y) = d(y, S -);

• T z S -the (affine) tangent space of S -at z.

Notice that, since the gradients are linearly independent, T z S -is the affine subspace passing through z and orthogonal to ∇(-g i )(z) for i ∈ I -. In particular, since ∇(-g i )(z)•(y -z) ≥ δ, y -z T z S - the angle between yz and T z S -is lower bounded by a strictly positive angle φ > 0 for all y close enough to z. For a geometric intuition of the following discussion, see Figure 1. Let z be the projection of y on T z S -. By definition of φ we have yz 2 ≤ y-z 2 sin φ . Now let z be the projection of y on S -. Since y is close to z, z is close to z , i.e. the projection of y on S -is close to the projection of y on T z S -. Thus there exists a constant c such that yz 2 ≤ c y-z 2 sin φ . More precisely, let z be the projection of z on T z S -. Thus zz = (zz ) + (zz), and since we project z on T z S -we have:

• z -z = i∈I -γ i ∇g i (z) = J I -(z)γ for some γ = (γ i : i ∈ I -); • z -z is orthogonal to ∇g i (z) for i ∈ I -.
By definition of z we have yz 2 ≤ yz 2 ≤ yz 2 + zz 2 . We show now that zz 2 is small compared to yz 2 . Expanding at z for i ∈ I -we obtain:

0 = g i (z ) = ∇g i (z) • (z -z) + h i (z ) • (z -z) = ∇g i (z) • (z -z ) + h i (z ) • (z -z).
Proceeding as in Equation ( 7), we have γ = N I -(z) -1 h(z )(zz). Now, since z is the projection of y on S -and z ∈ S -we have zz 2 ≤ 2 yz 2 . Thus we deduce:

y -z 2 ≤ y -z 2 + z -z 2 ≤ y -z 2 + J I -(z) 2 γ 2 ≤ y -z 2 + J I -(z) 2 N I -(z) -1 h(z )(z -z) 2 ≤ y -z 2 + 2 J I -(z) 2 N I -(z) -1 2 h(z ) 2 y -z 2 . Therefore y -z 2 ≤ y -z 2 sin φ ≤ y -z 2 sin φ + 2 J I -(z) 2 N I -(z) -1 2 h(z ) 2 y -z 2 sin φ ,
and finally 1 -

2 J I -(z) 2 N I -(z) -1 2 h(z ) 2 sin φ y -z 2 ≤ y -z 2 sin φ .
As z → z if y → z, h(z ) 2 → 0 for y → z. Then there exists ε > 0 such that D(y) ≤ ε implies 1 -

2 J I -(z) 2 N I -(z) -1 2 h(z ) 2 sin φ ≥ 1 2 and thus y -z 2 ≤ 2 y -z 2 sin φ . ( 9
)
In other words, we just proved in Equation (9) that

D(y) ≤ ε ⇒ D(y) ≤ 2 sin φ D -(y).
Since D -is the distance function to S -, that is defined by inequalities negative at y, we can apply Lemma 2.9: there exists c such that if ε is small enough, D -(y) ≤ ε implies D -(y) ≤ c G -(y) (notice that this is possible because D(y) → 0 implies D -(y) → 0). Moreover observe that G(y) = G -(y) since only the g i that are negative at y contribute to G(y). Then, if we set c = 2c sin φ we can conclude:

D(y) ≤ ε ⇒ D(y) ≤ c G(y).
We can now show that if the CQC hold at every point of the semialgebraic set the Łojasiewicz exponent is equal to 1. Remark. In Theorem 2.11 we prove that in regular cases the Łojasiewicz exponent is 1. On the other hand we don't give a precise estimate for the constant c, even if we can revisit the proof of Lemma 2.9, Lemma 2.10 and Theorem 2.11 to bound it in terms of the following parameters:

D(y) ≤ 2 √ n = 2 √ n G * G * ≤ 2 √ n G * G(y) for all y ∈ C.
• the max norm of the Jacobian of the g: we could bound this parameter bounding the norm of g;

• the min norm of the Gram matrix of the ∇g: this measures how close are the gradients to be linearly dependend;

• the minimum of G(y) on the complementary in [-1, 1] n of a small neighbourhood of S: this measures how close are the g to have a common zero outside of S;

• the convergence rate to 0 of the Taylor remainder h(z).

A detailed analysis of these parameters would also give an upper bound for c, but we don't develop it for the sake of simplicity.

Remark. On the contrary when the problem is not regular the bounds on the exponent Ł can be large. We have:

Ł ≤ d(g)(6d(g) -3) n+r-1 see [KS15, sec. 3.1] and [KSS16].

Construction of a polynomial echelon function

In this section, we describe the polynomial echelon function h k,m used to perturb f . This echelon polynomial depends on a parameter δ ∈ R >0 controlling the width of the step (and defined in Section 2.2) and on a parameter k ∈ R >0 controlling the minimum of the function. To show that the degree and the norm of the perturbation polynomial depend polynomially on ε(f ) (in Section 3.1), we are going to bound the degree of the echelon polynomials in terms of δ and k.

Consider the following function:

H(t) =                        1 t ∈ [-1, -δ] - 9(k-1) 2d 3 k t 3 - 27(k-1) 2d 2 k t 2 - 27(k-1) 2dk t -7k-9 2k t ∈ [-δ, -δ + δ 3 ] 9(k-1)
d 3 k t 3 + 27(k-1) 2d 2 k t 2 + 9(k-1) 2dk t + k+1 2k t ∈ [-δ + δ 3 , -δ + 2δ 3 ] - 9(k-1) 2d 3 k t 3 + 1 k t ∈ [-δ + 2δ 3 , 0] 1 k t ∈ [0, 1] (10)
The piecewise polynomial function H(t) is a C 2 cubic spline on [-1, 1]. Indeed an explicit computation shows that the functions H, H (1) , H (2) are absolutely continuous, and moreover the piecewise constant function H (3) is of total variation V = 216(k-1)

δ 3 k . Finally notice that H is non-increasing on [-1, 1].
We approximate this function by a polynomial ∈ R[T ], using Chebyshev approximation (see Figure 2): Theorem 2.12 (Chebyshev approximation on [-1, 1] [START_REF] Trefethen | Approximation Theory and Approximation Practice[END_REF]). For an integer u, let h : [-1, 1] → R be a function such that its derivatives through h (u-1) be absolutely continuous on [-1, 1] and its u-th derivative h (u) is of bounded variation V . Then its Chebyshev approximation p m of degree m satisfies:

h -p m ≤ 4V πu(m -u) u .
• deg h k,m = m with m = 6 δ 3 4(k-1) 3π + 3 ; • for t ∈ [-1, -δ] we have 1 -1 k ≤ h k,m (t) ≤ 1 + 1 k ; • for t ∈ [0, 1] we have h k,m (t) ≤ 2 k ; • for t ∈ [-1, 1] we have 0 ≤ h k,m (t) ≤ 1 + 1 k . Proof. We construct a degree m Chebyshev approximation h k,m ∈ R[T ] of H such that H -h k,m ≤ 1 k , ( 11
)
so that the last three points of the proposition are satisfied. As H, H (1) and H (2) are absolutely continuous and H (3) has total variation V = 216(k-1) δ 3 k , by Theorem 2.12, it suffices to take m such

4V 3π(m-3) 3 ≤ 1 k , i.e. m ≥ 3 4V k 3π + 3 = 6 δ 3 4(k -1) 3π + 3,
which proves the first point.

The other points follow from Equation ( 11) and the definition of H in (10).

Effective Putinar's Positivstellensatz

This section is devoted to the proof of Theorem 1.7.

From S to [-1, 1] n

Let h k,m be as in Proposition 2.13. We want to show that, for a suitable choice of k, m and s ∈ R >0 , the polynomial:

p = f -s r i=1 h k,m (g i )g i (12) is such that p ≥ f * 2 on [-1, 1] n .
Remark. Our construction of the perturbed polynomial p is similar to the one in [START_REF] Schweighofer | Optimization of Polynomials on Compact Semialgebraic Sets[END_REF], [START_REF] Nie | On the complexity of Putinar's Positivstellensatz[END_REF], or [START_REF] Averkov | Constructive Proofs of some Positivstellensätze for Compact Semialgebraic Subsets of R d[END_REF] where the polynomial h is a univariate (sum of) squares. That choice is simpler, but it results in worst bounds for the degree and the norm of s r i=1 h k,m (g i )g i , than the one we obtain using the polynomial echelon function h k,m .

These univariate SoS coefficients have also been used in [START_REF] Kurdyka | Convexifying Positive Polynomials and Sums of Squares Approximation[END_REF], to prove that one can uniformly approximate positive polynomials on compact sets, using the proper subcone of the quadratic module Q(g) where the SoS coefficient of g i is of the form j (h j (g i )) 2 , for h j univariate. They derive a Putinar's Positivstellensatz and apply it to Polynomial Optimization problems. We describe the equivalent of the uniform approximation result in Theorem 4.1, with our coefficients

h k,m ∈ Q(1 + T , 1 -T ).
Proposition 3.1. Assume that the normalisation assumptions (2) are satisfied. If

s > 6 f δ ; (13) k > 2r -2 δ + 1; (14) k > 4rs f * ; ( 15
)
then p = f -s r i=1 h k,m (g i )g i ≥ f * 2 on [-1, 1] n .
Proof. Let x ∈ A so that G(x) ≥ δ, i.e. min{g 1 (x), . . . , g r (x), 0} ≤ -δ (see Section 2), and WLOG assume g 1 (x) ≤ -δ. Notice that from Proposition 2.13 we have

h k,m (g 1 (x)) ≥ 1 -1 k and, if g i (x) ≥ 0, h k,m (g 1 (x)) ≤ 2 k .
Moreover recall that g i ≤ 1 2 from the normalisation assumptions (2). Then:

p(x) = f (x) -s r i=1 h k,m (g i (x))g i (x) ≥ f (x) + sδ(1 - 1 k ) -s r i=2 h k,m (g i (x))g i (x) ≥ f (x) + sδ(1 - 1 k ) -s r -1 k = f (x) + s δ 2 (1 - 1 k ) + s( δ 2 (1 - 1 k ) - r -1 k ).
From Equation (13) and Equation ( 14), we have respectively

f (x) + s δ 2 (1 -1 k ) > f 2 ≥ f * 2 and δ 2 (1 -1 k ) -r-1 k > 0, so that p(x) > f * 2 for x ∈ A. By Equation (15), 3f * 4 -sr k > f *
2 . By the normalization assumptions (2) and as h k,m is upper bounded by 2 k on [0, 1] (see Proposition 2.13), we therefore deduce that for

x ∈ [-1, 1] n \ A p(x) = f (x) -s r i=1 h k,m (g i (x))g i (x) ≥ 3f * 4 -sr 2 k 1 2 = 3f * 4 - sr k > f * 2 . This shows that p(x) > f * 2 for x ∈ [-1, 1] n = A ∪ ([-1, 1] n \ A).
Proposition 3.2. Let p be as in (12), with (13), ( 14), (15) and the normalization assumptions (2)

satisfied. Let d(g) = max i deg g i . Then p = O( f 2 3Ł rcd(f ) 2Ł ε(f ) -Ł ), (16)
deg p = O(2 4Ł r 1 3 c 4 3 d(g)d(f ) 8Ł 3 ε(f ) -4Ł+1 3 ). ( 17
)
Lemma 3.4 implies that we have a Putinar-like representation of polynomials strictly positive on the box as elements of the quadratic module of the ball. Lemma 3.5. Let Q(g) be a quadratic module such that 1 -X 2 2 ∈ Q(g), and let f be a polynomial such

that f > 0 on [-1, 1] n . Then f ∈ Q(g). Proof. Since f > 0 on [-1, 1] n , then f ∈ Q(1-X 2
) by Schmüdgen's Positivstellensatz and Lemma 3.4. Now by hypothesis Q(1 -X 2 ) ⊂ Q(g) and thus f ∈ Q(g).

Lemma 3.5 shows that we can use a Schmüdgen theorem on [-1, 1] n , for instance Theorem 3.8, to prove that f ∈ Q(g), without having proved a general Putinar's Positivstellensatz for Q(g) yet.

Another alternative to prove the result would have been to notice that f > 0 on [-1, 1] n implies f > 0 on the unit ball, and then apply a Schmüdgen/Putinar theorem for Q(1 -X 2 ).

We are ready to show that the addenda h(g i )g i belong to Q(g), with degree bounds for the representation.

Lemma 3.6. Let h ∈ Pos([-1, 1]) m be a univariate polynomial of degree m. If the normalization assumptions (2) are satisfied and d(g

) = max i deg g i , then h(g i )g i ∈ Q d(g)m+ 0 +2 (g), where 0 = min{k : 1 -g i ∈ Q k (g) ∀i = 1, . . . , r}. Proof. By Theorem 3.3, h ∈ Q m+1 (1 + T , 1 -T ), i.e. h = s 0 + s 1 (1 + T ) + s 2 (1 -T ), where s i is a SoS where deg s 0 , deg s 1 + 1 and deg s 2 + 1 are ≤ m + 1. Let d i = deg g i . Notice that: • s 0 (g i )g i ∈ Q d i (m+1)+d i (g) = Q d i (m+2) (g) since s 0 is a SoS of degree ≤ m + 1; • s 1 (g i )(1 + g i )g i = s 1 (g i )g i + s 1 (g i )g 2 i ∈ Q d i m+2 d i (g) since s 1 is a SoS of degree ≤ m; • s 2 (g i )(1 -g i )g i = s 2 (g i )(g i -g 2 i ) ∈ Q(g). Indeed g i -g 2 i = (1 -g i ) 2 g i + g 2 i (1 -g i ),
and since g i ≤ 1 2 we have (1g i ) ∈ Q(g) by Lemma 3.5. In particular let 0 be minimal such that for all i we have 1 -

g i ∈ Q 0 (g). Then g i -g 2 i ∈ Q 0 +2 (g) and finally s 2 (g i )(g i -g 2 i ) ∈ Q d i m+ 0 +2 (g).
This shows that h(g i )

g i = s 0 (g i )g i + s 1 (g i )(1 + g i )g i + s 2 (g i )(1 -g i )g i ∈ Q d(g)m+ 0 +2 (g), where d(g) = max i d i .
We now apply Lemma 3.6 to p to determine the degree of the representation of fp ∈ Q(g).

Proposition 3.7. Let s r i=1 h k,m (g i )g i = fp be as in (12). If the normalization assumptions (2) are satisfied, then

f -p ∈ Q (g) when = O(2 4Ł r 1 3 c 4 3 d(g)d(f ) 8Ł 3 ε(f ) -4Ł+1
3 ), where c, Ł are given by Lemma 2.5.

Proof. It is enough to prove that for all i we have h k,m (g i )g i ∈ Q (g). Notice that h k,m (g i )g i ∈ Q d(g)m+ 0 +2 (g) for all i, see Lemma 3.6. From Equation (20) we can choose m = O(c

4 3 r 1 3 2 4Ł d 8Ł 3 ε(f ) -4Ł+1 3 ) and thus if = O(2 4Ł r 1 3 c 4 3 d(g) d(f ) 8Ł 3 ε(f ) -4Ł+1 3 ) we have s r i=1 h k,m (g i )g i = f -p ∈ Q (g).

The Polynomial Effective Positivstellensatz

We will use an effective version of Schmüdgen's Positivstellensatz for the box [-1, 1] n .

Theorem 3.8 ([LS21]). Let f ∈ R[X], deg f = d and f > 0 on [-1, 1] n . Let f min = min x∈[-1,1] n f (x) and f max = max x∈[-1,1] n f (x).
Then there exists a constant C(n, d) (depending only on n and d) such that f ∈ O nr (1 ± X i : i ∈ {1, . . . , n}), where:

r ≥ max        πd √ 2n, C(n, d)(f max -f min ) f min        . Moreover the constant C(n, d) is a polynomial in d for fixed n: C(n, d) ≤ 2π 2 d 2 (d + 1) n n 3 = O(d n+2 n 3 )
Our assumption is that Q(1 -X 2 2 ) ⊂ Q(g), while Theorem 3.8 involves O(1 ± X i : i ∈ {1, . . . , n}). But we have already shown in Lemma 3.4 that we can move from the latter to the former with a constant degree shift.

We are now ready to prove the main theorem.

Proof of Theorem 1.7. Let p = fs r i=1 h k,m (g i )g i be as in Equation (12), with s, k, m satisfying Equation (13), Equation (14), Equation (15) and h k,m as in Proposition 2.13. In particular:

• p ≥ f * 2 on [-1, 1] n from Proposition 3.1; • p = O(2 3Ł r c d(f ) 2Ł f ε(f ) -Ł ) from Equation (16); • deg p = O(2 4Ł r 1 3 c 4 3 d(g) d(f ) 8Ł 3 ε(f ) -4Ł+1
3 ) from Equation (17).

We ). We now deduce the asymptotic order of 0 :

C(n, deg p)(p max -p min ) p min =O n 3 (deg p) n+2 ( 2 p f * + 1) =O n 3 (2 4Ł r 1 3 c 4 3 d(g) d(f ) 8Ł 3 ε(f ) -4Ł+1 3 ) n+2 f 2 3Ł rcd(f ) 2Ł ε(f ) -Ł f * =O (n 3 2 (4n+11)Ł r n+5 3 c 4n+11 3 d(g) n+2 d(f ) 2(4n+11)Ł 3 ε(f ) -(4Ł+1)n+11Ł+5 3 ) 1 2 =O n 3 2 2 (4n+11)Ł 2 r n+5 6 c 4n+11 6 d(g) n+2 2 d(f ) (4n+11)Ł 3 ε(f ) -(4Ł+1)n+11Ł+5 6 , so we can choose 0 = O(n 3 2 2 (4n+11)Ł 2 r n+5 6 c 4n+11 6 d(g) n+2 2 d(f ) (4n+11)Ł 3 ε(f ) -(4Ł+1)n+11Ł+5 6
) and p ∈ O n 0 (1 ± X i : i ∈ {1, . . . , n}). Now, from Lemma 3.4 we have O n 0 (1±X i : i ∈ {1, . . . , n} ⊂ Q n 0 +n (1-X 2 2 ). Moreover from Equation (2) we have that 1-X 2 2 ∈ Q(g). In particular if 1-X 2 2 ∈ Q 1 (g) and thus

Q n 0 +n (1-X 2 2 ) ⊂ Q n 0 +n+ 1 (g), i.e. choosing = nO( 0 ) = O(n 5 2 2 (4n+11)Ł 2 r n+5 6 c 4n+11 6 d(g) n+2 2 d(f ) (4n+11)Ł 3 ε(f ) -(4Ł+1)n+11Ł+5 6
) we have p ∈ Q (g). Finally notice that f = (fp) + p and • p ∈ Q (g) from the discussion above;

• fp ∈ Q (g) from Proposition 3.7, since the degree of the truncated quadratic module in Proposition 3.7 is smaller than .

Then f ∈ Q (g) with = O(n 5 2 2 (4n+11)Ł 2 r n+5 6 c 4n+11 6 d(g) n+2 2 d(f ) (4n+11)Ł 3 ε(f ) -(4Ł+1)n+11Ł+5 6 ). ( 21
)
We simplify the exponents for readibility. Recall that Ł ≥ 1 and c ≥ 1, and assume n ≥ 2. Under these assumptions the inequalities (4n + 11)Ł ≤ 10nŁ, n + 5 ≤ 6n, 4n + 11 ≤ 10n, n + 2 ≤ 2n and (4Ł + 1)n + 11Ł + 5 ≤ 14nŁ hold. Therefore we deduce that f ∈ Q (g) if

≥ O(n 3 2 5nŁ r n c 2n d(g) n d(f ) 3.5nŁ ε(f ) -2.5nŁ ) = γ(n, g)d(f ) 3.5nŁ ε(f ) -2.
) (4n+11)Ł 3 ε(f ) -(4Ł+1)n+11Ł+5 6
), where c, Ł are defined in Definition 2.4. The exponents in Theorem 1.7 have been simplified for the sake of readability and are not optimal.

If the inequalities defining S satisfy a regularity condition we can simplify the bound, since Ł = 1 in this case (see Section 2.2).

Corollary 3.9. Assume n ≥ 2 and let g 1 , . . . , g r ∈ R[X] = R[X 1 , . . . , X n ] satisfying the normalization assumptions (2) and such that the CQC (Definition 2.7) hold at every point of S(g). Let

f ∈ R[X] such that f * = min x∈S f (x) > 0. Then f ∈ Q (g) if = O(n 3 2 5n r n c 2n d(g) n d(f ) 3.5n ε(f ) -2.5n ),
where c is given by Theorem 2.11.

Proof. Apply Theorem 1.7 and Theorem 2.11.

Convergence of Lasserre's relaxations optimum

We begin with a short description of Polynomial Optimization Problems (POP) and of the Lasserre hierarchies to approximately solve them, and refer to [START_REF] Lasserre | Global Optimization with Polynomials and the Problem of Moments[END_REF], [START_REF] Bernard | An Introduction to Polynomial and Semi-Algebraic Optimization[END_REF] for more details.

Let f , g 1 , . . . , g s ∈ R[X]. The goal of Polynomial Optimization is to find:

f * inf f (x) ∈ R | x ∈ R n , g i (x) ≥ 0 for i = 1, . . . , s = inf x f (x) : g i (x) ≥ 0 ∀i ∈ {1, . . . , r}, (22)
that is the infimum f * of the objective function f on the basic closed semialgebraic set S = S(g). It is a general problem, which appears in many contexts and with many applications, see for instance [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF].

We define the SoS relaxation of order of problem (22) as Q 2 (g) and the supremum:

f * SoS, sup λ ∈ R | f -λ ∈ Q 2 (g) . ( 23
)
Now we want to define the dual approximation of the polynomial optimization problem. We are interested in an affine hyperplane section of the cone L (g) = Q (g) ∨ :

L (1) (g) = L ∈ L (g) | L|1 = 1 .
With this notation we define the MoM relaxation of order of problem (22) as L 2 (g) and the infimum:

f * MoM, inf L|f ∈ R | L ∈ L (1) 2 (g) . ( 24
)
It is easy to show that the relaxations (23) and ( 24) are lower approximations of f * . Their convergenge to f * as the order goes to infinity is deduced from Putinar's Positivstellensatz. In particular the rate of convergence can be deduced from the Effective Putinar's Positivstellensatz: see Theorem 4.3. The proof of this result is the purpose of Section 4.

Remark. We have that f * SoS, ≤ f * MoM, ≤ f * for all . Thus the results of this section, stated for the SoS relaxations f * SoS, , are also valid for the MoM relaxations f * MoM, . A first step for the proof of Theorem 4.3 is to recognise Theorem 1.7 as a quantitative result of approximation of polynomials with polynomials in the truncated quadratic module.

Theorem 4.1. Assume n ≥ 2 and let g satisfy the normalization conditions (2). Let Ł be the Łojasiewicz exponent defined in Definition 2.4 and let f ≥ 0 on S(g). Then for 0

< ε ≤ f , we have f -f * + ε = q ∈ Q (g) for ≥ γ (n, g) d(f ) 3.5nŁ f 2.5nŁ ε -2.5nŁ (25)
where γ (n, g) = 3 2.5nŁ γ(n, g) ≥ 1 depends only on n and g and γ(n, g) is given by Theorem 1.7.

Proof. Notice that ff * + ε > 0 on S(g) and

ε(f -f * + ε) = ε f -f * + ε ≥ ε f + |f * | + ε ≥ ε 3 f for ε ≤ f . Moreover deg f -f * + ε = deg f = d(f ). By Theorem 1.7, we have f -f * + ε = q ∈ Q (g) if ≥ O(n 3 2 5nŁ r n c 2n d(g) n d(f ) 3.5nŁ ( ε 3 f ) -2.5nŁ ) = γ (n, g) d(f ) 3.5nŁ f 2.5nŁ ε -2.5nŁ
where γ (n, g) = 3 2.5nŁ γ(n, g) = O(n 3 2 5nŁ 3 2.5nŁ r n c 2n d(g) n ) ≥ 1 depends only on n and g, and not on f , and γ(n, g) is given by Theorem 1.7.

Remark. From Equation (21), we have γ(n, g) = O(n

3 2 2 4Łn+11Ł 2 r n+5 6 c 4n+11 6 d(g) n+2
2 ), where c, Ł are defined in Definition 2.4. The exponents of γ (n, g) = 3 2.5nŁ γ(n, g) in the proof have been simplified for the sake of readability and are not optimal.

Remark. Theorem 4.1 is a quantitive version of Weierstrass approximation theorem for positive polynomials on S, showing that a polynomial f ∈ Pos(S(g)) can be approximated uniformly on

[-1, 1] n (within distance ε) by an element f * + q ∈ Q (g) for ≥ γ (n, g) d(f ) 3.5nŁ f 2.5nŁ ε -2.5nŁ .
We are now ready to prove the rate of convergence for Lasserre hierarchies.

* -f * SoS, ≤ ε for ≥ γ (n, g) d(f ) 3.5nŁ f 2.5nŁ ε -2.5nŁ . ( 26
)
Proof. Notice that

f * SoS, = sup{ λ ∈ R | f -λ ∈ Q 2 (g) } = inf{ ε ∈ R ≥0 | f -f * + ε ∈ Q 2 (g) }.
By Theorem 4.1, for ≥ γ (n, g) d(f ) 3.5nŁ f 2.5nŁ ε -2.5nŁ , ff * + ε ∈ Q (g). This implies that f *f * SoS, ≤ ε and concludes the proof.

Theorem 4.3. With the same hypothesis of Theorem 4.2 and γ (n, g) = γ (n, g) 1 2.5nŁ , we have

0 ≤ f * -f * SoS, ≤ γ (n, g) f d(f ) 7 5 -1 2.5nŁ . Proof. We apply Theorem 4.2 with ε ≤ f such that = γ (n, g)d(f ) 3.5nŁ f 2.5nŁ ε -2.5nŁ and γ (n, g) = γ (n, g) 1 2.5nŁ .
In conclusion Theorem 1.7 allows to prove Theorem 4.3, a polynomial convergence of the Lasserre's lower approximations to f * . In comparison with [NS07, th. 8], where the convergence is logarithmic in level of the hierarchy, Theorem 4.3 gives a polynomial convergence to f * .

In regular POP we can simplify the bound, since Ł = 1 in this case (see Section 2.2).

Corollary 4.4. With the same hypothesis of Theorem 4.2 and γ (n, g) = γ (n, g) 1 2.5n , we have

0 ≤ f * -f * SoS, ≤ γ (n, g) f d(f ) 7 5 -1 2.5n
if the CQC (Definition 2.7) hold at every point of S(g).

Proof. Apply Theorem 4.3 and Theorem 2.11.

Lemma 5.5. Let ≥ γ (n, g) t 3.5nŁ n+t t 5nŁ 4 ε -2.5nŁ , where g satisfy assumption (2) and γ (n, g) is given by Equation (25). Then L (1) (g) [t] ⊂ C(ε).

Proof. By Lemma 5.1, for all f ∈ P we have f ≤ n+t t 1 2 . From Theorem 4.1, we deduce that for ≥ γ (n, g) t 3.5nŁ n+t t 5nŁ 4 ε -2.5nŁ , we have ff * + ε = q ∈ Q (g). Thus for L ∈ L (1) (g) [t] we obtain L|f + ε = L|q + f * ≥ 0. Therefore L|f ≥ -ε: this shows that L (1) (g) [t] ⊂ C(ε).

The convex set C(ε) can be seen as a tubular neighborhood of M(S) [t] . We are going to bound its Hausdorff distance to the measures. We state and prove the result in the general setting of convex geometry, and finally use it to prove Theorem 5.7. with γ (n, g) given by Equation (25). Then d H (M(S) [t] , L (1) (g) [t] ) ≤ ε.

Proof. By Corollary 5.3 we have:

M(S) [t] = { L ∈ R[X] * t | ∀f ∈ P , L|f ≥ 0} = ∩ f ∈P H f ,
where H f = {L ∈ R[X] * t | L|f ≥ 0} with f 2 = 1 and f ∈ Pos(S) t . We check that the hyperplanes H f with f ∈ P defining M(S) [t] satisfy the hypothesis of Lemma 5.6:

• The half-space H f has a unit normal since f 2 = 1;

• Any supporting hyperplane of M(S) [t] defines an half-space H f = {L ∈ R[X] * t | L|f ≥ 0 with f ∈ P . Indeed if f defines a supporting hyperplane of M(S) [t] , then µ f = f dµ ≥ 0 for all µ ∈ M(S) [t] . In particular for all x ∈ S we have f (x) = f dδ x ≥ 0 (where δ x denotes the dirac measure concentred at x). This proves that f ∈ Pos(S) t and, normalizing it, we can assume f ∈ P .

Then from Lemma 5.6 we have d H (M(S) [t] , C(ε)) ≤ ε.

Finally by Lemma 5.5 we deduce that L (1) (g) [t] ⊂ C(ε) and conclude that d H (M(S) [t] , L (1) (g) [t] ) ≤ d H (M(S) [t] , C(ε)) ≤ ε.

Notice that in Theorem 5.7 we are bounding the distance between normalized linear functionals and measures that may be not normalized (i.e. not a probability measure). In the following we solve this problem.

We recall and adapt to our context [START_REF] Josz | Strong duality in Lasserre's hierarchy for polynomial optimization[END_REF]lem. 3] to obtain a bound on the norm of pseudomoment sequences. In particular we do not assume that the ball constraint is an explicit inequality, but only that the quadratic module is Archimedean.

Lemma 5.8. Assume that r 2 -X 2 2 = q ∈ Q 0 (g). Then for all t ∈ N and ≥ 2t -2 + 0 , if L ∈ L

X 2α ) ∈ Q 2t-2+ 0 (g) ⊂ Q (g).
we have

0 ≤ L (r 2 -X 2 2 )( |α|≤k-1 X 2α ) = r 2 L |α|≤k-1 X 2α -L X 2 2 ( |α|≤k-1 X 2α ) = r 2 tr H k-1 L -L |α|≤k X 2α -L|1 = r 2 tr H k-1 L + 1 -tr H k L ,
that is, tr H k L ≤ r 2 tr H k-1 L + 1. Since tr H 0 L = L 0 = 1, we deduce by induction on k that tr H t L ≤ t k=0 r 2k and thus

L [2t] 2 ≤ H t L F ≤ rank(H t L ) H t L 2 ≤ n + t t tr H t L ≤ n + t t t k=0 r 2k .
Finally we are ready to prove Theorem 1.8, where we obtain the bound of the distance between normalized linear functionals and probability measures.

Proof of Theorem 1.8. Let ε = 1 2 εt -1 n+t t -1 2 ≤ 1 4 , L ∈ L (1) (g) [2t] and µ ∈ M(S) [2t] be the closest point to L. We first bound the norm of µ. As ≥ γ(n, g) 6 2.5nŁ t 6nŁ n + t t 5nŁ 2 ε -2.5nŁ = γ (n, g) t 3.5nŁ n + t t 5nŁ 4

(ε ) -2.5nŁ , by Theorem 5.7 we have d(L, µ) ≤ ε .

Figure 1 :

 1 Figure 1: Proof of Lemma 2.10

  Theorem 2.11. Let D, G as in Definition 2.4 and assume that the CQC holds at every point of S = S(g) ⊂ [-1, 1] n . Then there exists a constant c ∈ R >0 such that:D(y) ≤ cG(y) for all y ∈ [-1, 1] n .Proof. Let ε = min z∈S ε (z) and c = max z∈S c (z), with ε (z) and c (z) as in Lemma 2.10. Notice that ε > 0 and c < ∞ exist because S is compact and 0 < ε (z), c (z) < ∞ are respectively lower and upper semicontinuous functions of z.Let U = {y ∈ [-1, 1] n | d(y, S) < ε} ⊂ [-1, 1] n (an open set containing S): by definition of ε and c we have D(y) ≤ c G(y) for all y ∈ U from Lemma 2.10. Now consider the compact set C = [-1, 1] n \ U and let G * > 0 be the minimum of G on C. Moreover since S ⊂ [-1, 1] n we have D(y) ≤ 2 √ n for y ∈ [-1, 1] n . Then:

Finally, taking

  c = max(c , 2 √ n G * ) we obtain: D(y) ≤ cG(y)for all y ∈ [-1, 1] n .

Figure 2 :

 2 Figure 2: Polynomial Echelon Function

  5nŁ ,where γ(n, g) = O(n 3 2 5nŁ r n c 2n d(g) n ) ≥ 1.Remark. From Equation (21), we have = O(n

Theorem 4. 2 .

 2 With the same hypothesis of Theorem 4.1, let f * SoS, be the Lasserre SoS (lower) approximation. Then f

•

  Lemma 5.6. Let C = H∈H H be a closed convex set described as intersection of half spacesH = {x ∈ R N | c H • x + b H ≥ 0}, where • c H 2 = 1 for all H ∈ H; • H is the set of all the half-spaces containing C (of unit normal). If H(ε) = {x ∈ R N | c H • x + b H ≥ -ε} and C(ε) = H∈H H(ε), then d H (C, C(ε)) ≤ ε.Proof. By definition C ⊂ C(ε).Assume that this inclusion is proper, otherwise there is nothing to prove, and let ξ ∈ C(ε) \ C. Consider the closest point η in C of ξ on C, and the half spaceH = {x ∈ R N | η-ξ η-ξ 2 • x + b ≥ 0} ∈ Hdefined by the affine supporting hyperplane orthogonal to ηξ passing through η (and thusη-ξ η-ξ 2 • η = -b). Notice that H ∈ H since H is defined by a normalized supporting hyperplane of C. Finally notice that ηξ 2 = (η-ξ)•(η-ξ) ξ + b). Since ξ ∈ C(ε)and H ∈ H, we have (η-ξ η-ξ 2 • ξ + b) ≥ -ε,and thus 0 < ηξ 2 ≤ ε. Then the distance between any ξ ∈ C(ε) \ C and its closest point η ∈ C is ≤ ε, which implies d H (C, C(ε)) ≤ ε.Theorem 5.7. Let Q(g) be a quadratic module where g satisfy assumption (2) and let ≥ γ (n, g) t 3.5nŁ n + t t 5nŁ 4 ε -2.5nŁ

  apply Theorem 3.8 to p: p ∈ O n 0 (1 ± X i : i ∈ {1, . . . , n}), if 0 ≥

	C(n,deg p)(p max -p min ) p min	. Recall also
	from Theorem 3.8 that C(n, m) = O(n 3 m n+2

  For L ∈ L (1) (g), let H k L be the Moment matrix of L in degree ≤ 2k, which is semi-definite positive. Let H k L F be its Frobenius norm, i.e. H k L F = |α|,|β|≤k L 2 α+β , and H k L 2 its 2 operator norm, i.e. the maximal eigenvalue of H k L . Notice that by definition we haveL [2k] 2 ≤ H k L F and H k L 2 ≤ tr H k L , Moreover recall H k L F ≤ rank(H k L ) H k L 2 .To obtain a bound on L[2k] 2 , we are going to use trH k L = |α|≤k L 2α = L [2k] |α|≤k X 2α . As for k ≤ t,

			(1) (g) we
	have L [2t]	2 ≤ n+t t	t k=0 r 2k .
	Proof. (r 2 -X 2 2 )(
			|α|≤k-1

We follow the French tradition, and call a function f positive on a domain D if f ≥ 0 on D and strictly positive on D if f > 0 on D.

To be more precise, basis means here a Schauder basis of R[[Y]] equipped with the (Y 1 , . . . Y n )-adic topology.

This work has been supported by European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Actions, grant agreement 813211 (POEMA)

Proof. Let d = d(f ) = deg f . We start bounding m in terms of ε(f ).

We can choose m = 6 δ 3 4(k-1) 3π + 3 from Proposition 2.13, thus it is enough to bound k and δ. From Lemma 2.5 we can choose δ = 1 c (

. From Equation (13) we deduce that:

From Equation ( 14) we deduce that k = O( r δ ), while from Equation (15) (together with Equation ( 13)) we deduce that k = O( r ε(f )δ ): the latter has an higher order in terms of ε(f ), and finally:

Now we plug Equation ( 19) in m = 6 δ 3 4(k-1) 3π + 3 and obtain:

By the normalization assumptions (2), the properties of h k,m (Proposition 2.13) and Equation (18) we obtain:

Similarly, using Equation (20) we have:

where d(g) = max i deg g i .

We now show that fp = s r i=1 h k,m (g i (x))g i (x) is in Q (g), giving degree bounds for the degree that is necessary to represent fp (see Proposition 3.7).

Proof. From [START_REF] Powers | Polynomials that are positive on an interval[END_REF] (see also [START_REF] Pólya | Problems and Theorems in Analysis II: Theory of Functions[END_REF]part VI,[46][47]) there exists polynomials

, where the degree of every addendum is

Our assumption is that Q(1 -X 2 2 ) ⊂ Q(g), while we are trying to reduce to the case of [-1, 1] n . We show that we can move from the latter to the former with a constant degree shift in Lemma 3.4.

Lemma 3.4. The preordering associated with the box

Proof. Notice that:

5 Convergence of pseudo-moment sequences to measures

We are interested in the study of the truncated positive linear functionals L (g) = Q (g) ∨ , i.e. the dual convex cone of the truncated quadratic modules, and in particular of its section L

(1) d (g). This cone is used to define the Lasserre MoM relaxations (24). In the following we often restrict the linear functionals to polynomials of degree ≤ t, that is we consider the cones L (g) [t] .

Notice in particular that, if µ ∈ M(S) [t] and q ∈ Q (g) ∩ R[X] t then µ q = q dµ ≥ 0, since q ≥ 0 on S. In other words: M(S) [t] ⊂ L (g) [t] for all , i.e. our dual cone is an outer approximation of the cone of measures supported on S. To compare quantitatively these cones we consider their affine sections M (1) (S) [t] and L

(1) (g) [t] . Recall that L (1) (g) [t] is a generating section of L (g) [t] when t ≤ 2 , see Section 1.2. In this section, we prove Theorem 1.8, which shows the convergence of the outer approximation as goes to infinity, and deduce the speed rate from Theorem 1.7. To measure this convergence we use the Hausdorff distance of sets d H (•, •).

Before the proof of the main theorem, recall that in the finite dimensional vector space R[X] t , all the norms are equivalent: we specify in Lemma 5.1 a constant that we will need in the proof of Theorem 5.7, for the following norms.

and

using the Cauchy-Schwarz inequality. Finally notice that |x α | ≤ 1 for all α since x ∈ [-1, 1] n , and

We recall a version of Haviland's theorem that characterize linear functionals that are represented by measures supported on a compact set.

Theorem 5.2 ([Sch17, th.17.3]). Let S ⊂ R n be compact and let Pos(S) [t] if and only if L|f ≥ 0 for all f ∈ Pos(S) t .

We slightly modify Theorem 5.2 in order to consider only polynomials of unit norm.

Corollary 5.3.

We interpret Corollary 5.3 in terms of convex geometry. The convex set

is the convex cone dual to P . Any f ∈ P is defining an hyperplane L|f = 0 in R[X] * t , and an associated halfspace

We consider a relaxation of the positivity condition to prove our convergence.

Definition 5.4. For ε ≥ 0 and P as in Corollary 5.3, we define

Notice that by definition and Corollary 5.3 we have C(0) = M(S) [t] .

We show now that C(ε) contains the truncated positive linear functionals of total mass one for a large enough order of the hierarchy.

Let µ 0 = 1 dµ. We want to bound the distance between L and µ µ 0 ∈ M (1) (S) [2t] . Notice that

Since L 0 = 1, d(L, µ) ≤ ε implies 1ε ≤ µ 0 ≤ 1 + ε , and therefore 1-µ 0 µ 0 ≤ ε 1-ε . Moreover, using Lemma 5.8 we have

Then from Equation ( 27) we conclude that

Corollary 5.9. With the hypothesis of Theorem 1.8 and the CQC (Definition 2.7) satisfied at every point of S(g), then d H (M (1) (S) [2t] , L

(1) (g) [2t] ) ≤ ε if ≥ γ(n, g) 6 2.5n t 6n n+t t 2.5nŁ ε -2.5n .

Proof. Apply Theorem 1.8 and Theorem 2.11.

In Theorem 1.8 we prove a bound for the convergence of Lasserre truncated pseudo-moments to moments of measures. The convergence, without bounds, can be deduced from [START_REF] Schweighofer | Optimization of Polynomials on Compact Semialgebraic Sets[END_REF]th. 3.4] by taking as objective function a constant. On the other hand, we can deduce [Sch05, th. 3.4] from Theorem 1.8, by considering the sections of L

(1) (g) [t] given by L|f = f * MoM,k . In the context of Generalized Moment Problems (GMP), general convergence to moments of measures has been studied in [START_REF] Tacchi | Convergence of Lasserre's hierarchy: the general case[END_REF]. The uniform bounded mass assumption in [START_REF] Tacchi | Convergence of Lasserre's hierarchy: the general case[END_REF] is trivially satisfied in the context of Polynomial Optimization, since L 0 = L|1 = 1: the convergence result of [START_REF] Tacchi | Convergence of Lasserre's hierarchy: the general case[END_REF] is thus more general than [Sch05, th. 3.4] and the one implied by Theorem 1.8. But we conjecture, and leave it for future exploration, that it is possible to extend the proof technique of Theorem 1.8 to the GMP and give bounds on the rate of convergence also in this extended context.

Aknowkedgments. The authors thank M. Laurent and L. Slot for the discussion about Schmüdgen's theorem on [-1, 1] n , A. Parusiński and K. Kurdyka for the useful suggestions on the Łojasiewicz and Markov inequalities and F. Kirschner for discussions on half space descriptions of convex bodies. The authors thank the anonymous referees for their suggestion, that helped improving the presentation and pointed out errors present in previous versions of the article.