BOUNDS FOR REPRESENTATIONS OF POLYNOMIALS

POSITIVE ON COMPACT SEMI-ALGEBRAIC SETS

ALEXANDER PRESTEL∗

Dedicated to Murray Marshall on the occasion of his 60-th birthday

In this paper we deal with ‘effectivity problems’ in connection with the following theorem proved by K. Schmüdgen in [Sch].

Let ℝ[X] = ℝ[X_{1}, …, X_{n}] be the ring of real polynomials in X_{1}, …, X_{n}. For h_{1}, …, h_{m} ∈ ℝ[X], the set

S(h) = S(h_{1}, …, h_{m}) = {a ∈ ℝ^{n}|h_{1}(a) ≥ 0, …, h_{m}(a) ≥ 0}

is a basic closed semi-algebraic subset of ℝ^{n}. Schmüdgen’s Theorem states that if S(h) is bounded, then every f ∈ ℝ[X] that is strictly positive on S(h) admits a representation

(∗) f = ∑_{ν∈{0,1}^{m}} h_{1}^{ν_{1}} · . . . · h_{m}^{ν_{m}}σ_{ν}

with σ_{ν} from Σℝ[X]^{2}, the set of sums of squares of polynomials from ℝ[X].

Hilbert’s 17-th Problem dealt with the non-compact case h_{1} = ⋯ = h_{m} = 1. In this case, by E. Artin’s well-known solution, f ∈ Σℝ(X)^{2}, i.e., f is a sum of squares of rational functions. Using a classical result of Pfister,

f = ∑_{i=1}^{2^{n}} (\frac{p_{i}}{q_{i}} )^{2} with p_{i}, q_{i} ∈ ℝ[X].

Since this result also holds for every real closed field R replacing ℝ, the Compactness Theorem from model theory yields recursive bounds for the degree of p_{i} and q_{i}, depending only on the degree of f (and, of course, on n).

If one tries to find similar results of the Schmüdgen Theorem, one runs into trouble. First of all, for n ≥ 2 there is no bound possible for the length of sums of squares in ℝ[X] (see [CDLR], Theorem 4.1). Secondly, even in case n = 1 (where every sum of squares equals a sum of 2 squares from ℝ[X]), there does not exist a bound on deg σ_{ν} depending only on deg f and deg h_{i} (1 ≤ i ≤ m). This was first published in [St]. The reason for this defect being that Schmüdgen’s Theorem does not hold for non-archimedean real-closed fields R. Thus, if one wants to find upper bounds on the ‘length’ of σ_{ν} (= minimum number of squares such that their sum represents σ_{ν}) and deg σ_{ν} in a representation (∗), then the bounds have to depend also on invariants of f and the h_{i}’s other than just their degrees.

∗) This work was done during the author’s stay at the University of Stellenbosch.

Financial support from Stellenbosch University is gratefully acknowledged.

Our first theorem treats the case where the h_{i}’s are fixed (i.e. we treat all coefficients of h_{1}, …, h_{m} as invariants) and gives a bound depending also on deg f, ||f||, and the minimum of f on the compact set S(h). By ||f|| we mean any norm of the coefficient vector of f, e.g., the maximal absolute value.

THEOREM 1 There exists δ ∈ ℕ depending only on the coefficients of h_{1}, …, h_{m} and on n, d, and N ∈ ℕ such that for all f ∈ ℝ[X] = ℝ[X_{1}, …, X_{n}], if

(i) deg f ≤ d and ||f|| ≤ N, (ii) ||S(h)|| ≤ N, (iii) f(S(h)) > \frac{1}{N}, then f admits a representation (∗) where δ bounds the length and the degree of each σ_{ν}.

Remark: If in addition to the assumptions of the theorem we let h_{1}, …, h_{m} ∈ ℤ[X_{1}, …, X_{n}], the function δ may be chosen to be recursive in n, d, N, and the coefficients of the h_{i}’s.

In the next theorem we also allow the h_{i}’s to vary. As the example below shows, however, this theorem does not cover all h_{i}’s with S(h) bounded.

THEOREM 2 There exists a recursive bound δ = δ(n, m, d, N) such that for all f, h_{1}, …, h_{m} ∈ ℝ[X] = ℝ[X_{1}, …, X_{n}], if

(i) deg f, deg h_{i} ≤ d and ||f||, ||h_{i}|| ≤ N (1 ≤ i ≤ m), (ii) for all h′_{1}, …, h′_{m} ∈ ℝ[X] with deg h′_{i} ≤ deg h_{i},

if ||h′_{i} − h_{i}|| < \frac{1}{N} (1 ≤ i ≤ m) then ||S(h′)|| ≤ N, and (iii) f(S(h′)) > \frac{1}{N}, then f has a representation (∗) with length and degree of each σ_{ν} bounded by δ.

Example: (n = 2, m = 3) Let h_{1} = X_{1} − 1, h_{2} = X_{2} − 1, and h_{3} = 2 − X_{1}X_{2}. Then S(h) is bounded. If we now slightly change h_{1} to h′_{1} = X_{1} − 1 + εX_{2} with ε > 0, the set S(h′) is unbounded - it acquires new points coming from +∞ along with X_{2}-line.

The detailed proof of both theorem’s will be found in our forthcoming book “Positive polynomials”, co-authored by Ch. N. Delzell. Let us briefly indicate the method.

In both cases we prove that f admits a representation (∗) even when we replace ℝ by any real closed extension R of ℝ. After having achieved this, the Compactness Theorem of model theory gives the existence of bounds and the Completeness Theorem implies recursiveness. The reader may consult [P], Chap. 5 and 6 for a detailed exposition of such arguments.

The crucial step in the proof of (∗) for a real closed field R ⊇ ℝ is the following. Let O be the convex hull of ℝ in R. By (i), f, h_{1}, …, h_{m} ∈ O[X_{1}, …, X_{n}] =: A. Now let T (h) be the preordering of A generated by h_{1}, …, h_{m}. Then (ii) allows one to show that T (h) is archimedean. Now the Kadison-Dubois Representation Theorem applied to (A, T (h)), together with (iii) yields that f ∈ T (h).

At the end of this note let us consider also a ‘linear’ representation of f:

(∗∗) f = σ_{0} + h_{1}σ_{1} + ⋯ + h_{m}σ_{m}

with σ_{i} ∈ Σℝ[X]^{2}. Such linear representations do not always exist even when S(h) is bounded. The example above, for instance, does not allow a representation (∗∗) for every f, strictly positive on S(h) (see [JP], Example 4.5). Under certain conditions, however, linear representations are always possible. One such condition is (compare [JP], Theorem 4.1):

∀x ≠ 0 (h_{1}^{∗}(X) < 0 or ⋯ or h_{m}^{∗}(X) < 0)

(where h_{i}^{∗} denotes the homogeneous part of h_{i} of highest degree) together with

deg h_{1} ≡ ⋯ ≡ deg h_{m} mod 2.

This condition in particular holds if h_{1}, …, h_{m} are linear polynomials and S(h) is bounded.

Replacing (ii) in Theorem 2 by a “bounded” version of that condition and using the same method as above, yields recursive bounds for the σ_{i}’s in a representation (∗∗) for f.

REFERENCES

[CDLR] M.D. Choi, Z.D. Dai, T.Y. Lam, B. Reznick: The Pythagoras number of some affine algebras and local algebras. J. reine angew. Math. 336, 45-82 (1982).

[JP] Th. Jacobi, A. Prestel: On special representations of strictly positive polynomials. J. reine angew. Math (to appear).

[P] A. Prestel: Model Theory for the real algebraic geometer, Pisa 1998.

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

[St] G. Stengle: Complexity estimates for the Schmüdgen Positivstellensatz. J. Complexity 12, No 2, 167-174 (1996).