MTNS Conference, Polynomial Inequalities and Applications.

Kyoto, July 24-28 2006.

July 20, 2006

Salma Kuhlmann ^{1} , Research Center Algebra, Logic and Computation University of Saskatchewan, McLean Hall, 106 Wiggins Road, Saskatoon, SK S7N 5E6, Canada

email: skuhlman@math.usask.ca

homepage: http://math.usask.ca/˜ skuhlman/index.html

1Partially supported by the Natural Sciences and Engineering Research Council of Canada.

Positive Polynomials and Invariant Theory.

As all roads lead to Rome so I find in my own case at least that all algebraic inquiries, sooner or later, end at the Capitol of modern algebra over whose shining portal is inscribed the Theory of Invariants.

– J. J. Sylvester 1854

The slides of this talk are available at: http://math.usask.ca/˜ skuhlman/slidesjp.pdf

*******

Positive Polynomials, Sums of Squares and the multi-dimensional

Moment Problem.

In algebraic geometry, we consider ideals of the polynomial ring and algebraic varieties in affine space. In semi-algebraic geometry, we consider preorderings of the polynomial ring and semialgebraic sets in affine space.

• Let ℝ[X] := ℝ[X_{1}, ⋯, X_{n}] be the ring of polynomials in n variables and real coefficients.

• A subset T ⊆ ℝ[X] is a quadratic preordering if f^{2} ∈ T, ∀f ∈ ℝ[X] and T is closed under addition and multiplication. The smallest preordering of ℝ[X] is the set of sums of squares of ℝ[X], denoted by ∑ ℝ[X]^{2}.

• Given a subset S of ℝ[X], there is a smallest preordering T_{S} containing S; the preordering generated by S:

T_{S} = {_{e∈{0,1}^{r}}^{∑} σ_{e}f^{e} : r ≥ 0, σ_{e} ∈ ∑ ℝ[X]^{2}, f_{1}, ⋯, f_{r} ∈ S}

where f^{e} := f_{1}^{e_{1}} ⋯ f_{r}^{e_{r}}, if e = (e_{1}, ⋯, e_{r}).

• Let S = {f_{1}, ⋯, f_{s}} ⊂ ℝ[X], S defines a basic closed semialgebraic subset of ℝ^{n}:

K = K_{S} = {x ∈ ℝ^{n} : f_{1}(x) ≥ 0, …, f_{s}(x) ≥ 0}.

Hilbert’s 17th Problem and Stengle’s Positivstellensatz are concerned with the issue of representation of positive semi-definite polynomials.

• We consider polynomials that are positive semi-definite on K_{S}:

Psd(K_{S}) := {f ∈ ℝ[X] : f(x) ≥ 0 for all x ∈ K_{S}}

• Psd(K_{S}) is a preordering in ℝ[X] containing T_{S}.

• Question: Is it true that

Psd(K_{S}) = T_{S} ?

• Say that T_{S} is saturated if Psd(K_{S}) = T_{S}.

Examples:

• n = 1, S = ∅, K_{S} = ℝ, T_{S} = ∑ ℝ[X]^{2}. It is straightforward to show that a positive semi-definite polynomial on ℝ is a sum of squares of two polynomials; so in this case, the answer to the above question is yes.

• n = 1, S = {(1 − X^{2})^{3}}, K_{S} = [−1, 1]. Consider f(X) = (1−X^{2}), f ≥ 0 on K_{S}. An elementary argument shows that f ∉ T_{S}; so T_{S} is not saturated.

• n = 1 , S = {X^{3}} , K_{S} = [0, ∞) . Consider f(X) = X, f ≥ 0 on K_{S}. An elementary argument shows that f ∉ T_{S}; so T_{S} is not saturated.

• We shall return to these examples, and give a general criterion for saturated preorderings associated to semialgebraic subsets of the real line.

• n = 2 , S = ∅ , K_{S} = ℝ^{2} , T_{S} = ∑ ℝ[X]^{2} . Hilbert knew that there exists a polynomial of degree 6 which is positive semi-definite on the real plane, but not a sum of squares. The first explicit example was given by Motzkin:

m(X_{1}, X_{2}) := X_{1}^{4}X_{2}^{2} + X_{2}^{4}X_{1}^{2} − 3X_{1}^{2}X_{2}^{2} + 1

• n ≥ 3: Scheiderer [9] shows that if dim(K_{S}) ≥ 3, then there exists a polynomial p(X) ∈ ℝ[X] such that p(x) ≥ 0 for all x ∈ ℝ^{n} but p ∉ T_{S} (so T_{S} cannot be saturated).

It follows from Scheiderer’s result that the preordering Psd(K_{S}) is seldom finitely generated. Another attempt to approximate Psd(K_{S}) by the finitely generated preordering T_{S} is related to the multi-dimensional moment problem.

• The general Moment Problem is the following: Given a linear functional L ≠ 0 on ℝ[X] and a closed subset K of ℝ^{n}, when can one find a positive Borel measure μ on K such that for all f ∈ ℝ[X]

L(f) = ∫_{K} fdμ?

• Say L is represented by a measure μ on K if ∀f ∈ ℝ[X]

L(f) = ∫_{K} fdμ .

• The following result is due to Haviland.

Theorem 0.1 Given a linear functional L ≠ 0 on ℝ[X] and a closed subset K of ℝ^{n}, L is represented by a measure μ on K if and only if L(Psd(K)) ≥ 0.

• Since Psd(K) is in general not finitely generated , we are interested in approximating it by T_{S}.

• We work with the following corresponding preordering:

\overline{T_{S}} := \{f ; L(f) ≥ 0 for all L ≠ 0 such that L(T_{S}) ≥ 0\} .

• \overline{T_{S}} is the closure of T_{S} in ℝ[X] (for the finest locally convex topology on ℝ[X]).

• We have the inclusions

T_{S} ⊆ \overline{T_{S}} ⊆ Psd(K_{S}) .

• We say that S solves the moment problem if

\overline{T_{S}} = Psd(K_{S})

that is, if T_{S} is dense in Psd(K_{S}).

• Given a basic closed semialgebraic set K, we say that the moment problem is finitely solvable for K if a finite description S of K can be found such that T_{S} is dense in Psd(K_{S}) (Say (SMP) holds).

Remarks:

• By Theorem 0.1, we see that (SMP) holds if and only if every L ≠ 0 which satisfies L(T_{S}) ≥ 0 is represented by a positive Borel measure on K = K_{S}.

• If T_{S} is closed (i.e. T_{S} = \overline{T_{S}}) then S solves the moment problem if and only if T_{S} is saturated.

• In [11] Schmüdgen shows that if K_{S} is compact, then T_{S} is dense in Psd(K_{S}) (i.e. S solves the moment problem).

• In [4], [5] and [6] Schmüdgen’s result is extended to cover many non-compact examples.

As an illustration, we discuss (as promised) in the next slide saturated preorderings and solvability of the moment problem for subsets of the real line.

The one-dimensional Moment Problem.

We state [5, Theorem 2.2]. We need to define some notions.

If K ⊆ ℝ is a non-empty closed semi-algebraic set. Then K is a finite union of intervals. It is easily verified that K = K_{N}, for N the set of polynomials defined as follows: •If a ∈ K and (−∞, a) ∩ K = ∅, then X − a ∈ N. •If a ∈ K and (a, ∞) ∩ K = ∅, then a − X ∈ N. •If a, b ∈ K, (a, b) ∩ K = ∅, then (X − a)(X − b) ∈ N.

• N has no other elements except these. We call N the natural set of generators for K.

Examples:

• n = 1, K = ℝ, N = ∅

• n = 1, K = [−1, 1], N = {1 + X, 1 − X}.

• n = 1, K = [0, ∞), N = {X}.

The theorem on the next slide ([5, Theorem 2.2]) shows that the one-dimensional moment problem for non-compact subsets of the real line is always solvable. This generalizes several well-known results (Hamburger, Stieljes, Svecov, Hausdorff, etc...). Combined with Schmüdgen’s result, we see that the one-dimensional moment problem for subsets of the real line is always solvable.

Theorem 0.2 Assume that K = K_{S} ⊆ ℝ is not compact. Then T_{S} is closed. (Therefore S solves the moment problem if and only if T_{S} is saturated). Moreover, T_{S} is saturated if and only S contains the natural set of generators of K (up to scalings by positive reals).

For the compact case, we also have a criterion. Assume that K_{S} has no isolated points :

Theorem 0.3 Let K_{S} be compact, S = {g_{1}, ⋯, g_{s}}. Then T_{S} is saturated if and only if, for each endpoint a ∈ K_{S}, there exists i ∈ {1, ⋯, s} such that x − a divides g_{i} but (x − a)^{2} does not.

• We now want to extend Schmüdgen’s result in another direction. The idea is to fix a distinguished subset B ⊂ ℝ[X] and to attempt the various approximations only for polynomials in B. That is, we want to study the inclusions

T_{S} ∩ B ⊆ \overline{T_{S}} ∩ B ⊆ Psd(K_{S}) ∩ B .

Representation of positive semi-definite invariant polynomials.

• Here, we shall embark in a particularly privileged situation when B is the subring of invariant polynomials with respect to some action of a group on the polynomial ring ℝ[X].

• We fix a group G together with

ϕ : G → GL_{n}(ℝ)

a linear representation. We let G act on ℝ^{n}.

• We define the corresponding action of G on the polynomial ring ℝ[X]: given p(X) ∈ ℝ[X], define p^{g}(X) := p(ϕ(g)X).

• Recall that p(X) ∈ ℝ[X] is G-invariant if for all g ∈ G: p^{g}(X) = p(X) .

Remarks:

• If p(X) ∈ ∑ ℝ[ \underline{X} ]^{2} then for all g ∈ G, p^{g}(X) ∈ ∑ ℝ[ \underline{X} ]^{2}; so ∑ ℝ[ \underline{X} ]^{2} is (setwise) G-invariant.

• If K ⊂ ℝ^{n} is (setwise) G-invariant and p(X) ∈ Psd(K), then for all g ∈ G, p^{g}(X) ∈ Psd(K); so Psd(K) is (setwise) G-invariant.

• If S is a set of invariant polynomials, then K_{S} and T_{S} are (setwise) G-invariant.

• Conversely, if K ⊂ ℝ^{n} is G-invariant, it can be described by a set of invariant polynomials; see [[1]; Cor. 5.4].

*******

Preorderings of the ring of invariant polynomials.

• Write ℝ[ \underline{X} ]^{G} for the ring of all G-invariant polynomials.

• We shall always assume that G is a reductive group. So G admits a Reynolds operator. The Reynolds operator is an ℝ-linear map, which is the identity on ℝ[ \underline{X} ]^{G}, and is a ℝ[ \underline{X} ]^{G}-module homomorphism.

• For such groups, Hilbert’s Finiteness Theorem is valid; namely ℝ[ \underline{X} ]^{G} is a finitely generated ℝ-algebra.

• In this talk, for simplicity, we consider the case when G is a finite group. Here, the Reynolds operator is just the average map:

∗ : ℝ[X] → ℝ[ \underline{X} ]^{G}, f ↦ f^{∗} := \frac{1}{|G|} _{g∈G}^{∑} f^{g}.

• We use the Reynolds operator as a tool to describe preorderings of ℝ[ \underline{X} ]^{G}:

• If A ⊆ ℝ[ \underline{X} ] we shall denote by A^{∗} its image in ℝ[ \underline{X} ]^{G} under the Reynolds operator.

• If A ⊆ ℝ[ \underline{X} ], let us denote A^{G} := A ∩ ℝ[ \underline{X} ]^{G}.

• Observe that if T is any preordering in ℝ[ \underline{X} ], then T^{G} is a preordering of ℝ[ \underline{X} ]^{G}. What about T^{∗}?

• We note the following important property: Lemma 0.4 let A ⊆ ℝ[ \underline{X} ]. Assume that A is closed under addition and is (setwise) invariant. Then A^{∗} = A^{G}.

• Example: the image under the Reynolds operator of ∑ ℝ[ \underline{X} ]^{2} ⊂ ℝ[ \underline{X} ] is a preordering (∑ ℝ[ \underline{X} ]^{2})^{G} of ℝ[ \underline{X} ]^{G} of invariant sums of squares.

•Remark: In general

Σ(ℝ[ \underline{X} ]^{G})^{2} ⊆ (Σℝ[ \underline{X} ]^{2})^{G}

but this inclusion may be proper. Even worse, the preordering (Σℝ[ \underline{X} ]^{2})^{G} need not be finitely generated as a preordering of ℝ[ \underline{X} ]^{G} ([3]).

• We denote by S_{0} a set of generators of (Σℝ[ \underline{X} ]^{2})^{G} (as a preordering of ℝ[ \underline{X} ]^{G}).

Proposition 0.5 Let n = 1 and G = {−1, 1}. We claim that S_{0} = \{X^{2}\} generates the preordering (∑ ℝ[ \underline{X} ]^{2})^{G} over Σ(ℝ[ \underline{X} ]^{G})^{2}.

Proof: Indeed if σ ∈ (∑ ℝ[ \underline{X} ]^{2})^{G}, then

σ = σ^{∗} = _{i}^{∑}(η_{i}^{2})^{∗} with η_{i}(X) ∈ ℝ[X] .

Now (η_{i}^{2})^{∗}(X) = η_{i}^{2}(X) + η_{i}^{2}(−X), so it suffices to prove the claim for η_{i}^{2}(X) + η_{i}^{2}(−X). By separating terms of even and odd degree, we can write

η(X) = μ(X^{2}) + Xθ(X^{2}) ,

with appropriately chosen μ(X), θ(X) ∈ ℝ[X]. Therefore

η_{i}^{2}(X)+η_{i}^{2}(−X) = (μ(X^{2})+Xθ(X^{2}))^{2}+(μ(X^{2})−Xθ(X^{2}))^{2} =

2μ(X^{2})^{2} + 2X^{2}θ(X^{2})^{2}

which is an element of the preordering of ℝ[ \underline{X} ]^{G} generated by X^{2} as required. □

In the next slide, we continue our analysis of the preorderings of ℝ[ \underline{X} ]^{G}.

• Let S = {f_{1}, …, f_{k}} ⊂ ℝ[X]^{G}, and K_{S} ⊂ ℝ^{n} the invariant basic closed semialgebraic set defined by S.

• We are particularly interested in the following three preorderings of ℝ[X]^{G}, associated to S:

• The preordering of G-invariant psd polynomials Psd^{G}(K_{S}).

• The preordering T_{S}^{G}.

• The preordering T_{S}^{ℝ[x]^{G}} of ℝ[X]^{G} which is finitely generated by S.

• We have: T_{S}^{ℝ[x]^{G}} ⊆ T_{S}^{G} ⊆ Psd^{G}(K_{S}).

• The preordering T_{S}^{G} is easy to describe: Lemma 0.6 T_{S}^{G} is the preordering of ℝ[ \underline{X} ]^{G} generated by (Σℝ[ \underline{X} ]^{2})^{G} and S. Proof: Let h ∈ T_{S}^{G}. Write

h = _{e∈{0,1}^{s}}^{∑} σ_{e}f^{e}, with σ_{e} ∈ ∑ ℝ[X]^{2}

for some {f_{1}, …, f_{k}} ⊆ S. Applying the Reynolds operator we get

h = h^{∗} = (_{e∈{0,1}^{s}}^{∑} σ_{e}f^{e})^{∗} = _{e∈{0,1}^{s}}^{∑} σ_{e}^{∗}f^{e}

(since f_{1}, ⋯, f_{s} ∈ ℝ[ \underline{X} ]^{G}). This is of the required form since σ_{e}^{∗} ∈ (∑ ℝ[ \underline{X} ]^{2})^{G} for each e. □

Semi-Algebraic Geometry in the Orbit Space.

Fix p_{1}, ⋯, p_{k} ∈ ℝ[X] generators of ℝ[X]^{G}.

• Consider the polynomial map

π : ℝ^{n} → ℝ^{k}, \underline{a} = (a_{1}, ⋯, a_{n}) ↦ (p_{1}(\underline{a}) ⋯, p_{k}(\underline{a})) .

• By [[1]; Proposition 5.1], the image of an invariant basic closed semi-algebraic set is a basic closed semi-algebraic set. In particular is π(ℝ^{n}) is basic closed semi-algebraic.

• Let ℝ[U]:= the polynomial ring ℝ[U_{1}, ⋯, U_{k}] in kvariables. Fix a finite description v_{1}, ⋯, v_{r} ∈ ℝ[U] of π(ℝ^{n}).

• For the remaining of the talk, we assume that the finite group G is a generalized reflection group. In this case, ℝ[X]^{G} is generated by k = n algebraically independent elements (see [9]).

• We let

π̃ : ℝ[X]^{G} → ℝ[U] = ℝ[U_{1}, ⋯, U_{n}]

be the induced ℝ-algebra isomorphism mapping p_{i} to U_{i}. We have

π̃^{−1}(f)(\underline{a}) = f(p_{1}(\underline{a}) ⋯, p_{k}(\underline{a})) for all \underline{a} ∈ ℝ^{n} .

G–Saturation.

We conclude this talk by a discussion of the notion of G-saturation, which illustrates our “going down” idea.

• We say that T_{S}^{G} is saturated, or that T_{S} is G-saturated if every polynomial which is positive semi-definite and invariant is represented in the preordering, that is, if

T_{S}^{G} = Psd(K_{S})^{G} .

Proposition 0.7 If T_{π̃(S)∪π̃(S_{o})∪{v_{1},··· v_{r}}} is saturated as a preordering of ℝ[U], then T_{S} is G–saturated.

Let n = 1 and G as in example 0.5. Then ℝ[X]^{G} is generated by the polynomial p_{1}(X) = X^{2} and π(ℝ) is the positive half line and is defined by v_{1} = U. Combining Proposition 0.7 with [5, Theorem 2.2] we obtain the following variant of [5, Theorem 2.2]:

Theorem 0.8 Let S ⊂ ℝ[ \underline{X} ]^{G}. Assume that K_{S} is non-compact. Assume that: if (a, b), 0 < a < b is a connected component of ℝ \ K_{S} then S contains (up to a scalar multiple) (x^{2} − a^{2})(x^{2} − b^{2}), if (−a, a) is a connected component of ℝ \ K_{S}, then S contains (up to a scalar multiple) x^{2} − a^{2}. Then T_{S} is G-saturated,

• This provides many examples of non-saturated preorderings that are G–saturated.

The End References

[1] L. Bröcker, On symmetric semialgebraic sets and orbit spaces, Singularities Symposium, Banach Center Publications, Volume 44, Polish Academy of Sciences, Warszawa 1998

[2] J. Cimpric, S. Kuhlmann and M. Marshall: Positivity and G-Invariant Sums of Squares, preprint (2006).

[3] J. Cimpric, S. Kuhlmann and C. Scheiderer: G-Invariant Moment Problems, preprint (2006).

[4] K. Gaterman and P. A. Parillo, Symmetry groups, semidefinite programs and sums of squares, J. Pure and Applied Algebra 192, 95–128 (2004).

[5] S. Kuhlmann, M. Marshall, N. Schwartz, Positivity, sums of squares and the multi-dimensional moment problem II, Adv. Geom. 5, 583-607, (2005). .

[6] C. Procesi, G. Schwarz, Inequalities defining orbit spaces, Invent. math. 81, 539-554 (1985)

[7] C. Scheiderer, Sums of squares of regular functions on real algebraic varieties, Trans. Amer. Math. Soc. 352, 1030–1069 (1999)

[8] K. Schmüdgen, The K-moment problem for compact semi-algebraic sets, Math. Ann. 289, 203–206 (1991)

[9] B. Sturmfels, Algorithms in Invariant Theory, Texts and monographs in Symbolic Computation, Springer (1993).