4. Theorems of Radon and Helly 17 Let p be a real homogeneous polynomial of degree k in n real variables x = (ξ1, . . . , ξn) and let R+ n = (ξ1, . . . , ξn) : ξi 0 for i = 1, . . . , n be the non-negative orthant in Rn. Suppose that p(x) 0 for all x Rn + \ {0}. Then there exists a positive integer s such that the coefficients λa} of the polyno- mial (ξ1 + . . . + ξn)sp(ξ1,... , ξn) = a=(α1,... ,αn) α1+...+αn=s+k λaξ1 α 1 . . . ξn αn are non-negative. We discuss the structure of the set of non-homogeneous non-negative univariate polynomials in Chapter II see Section II.11. The results there can be translated in a more or less straightforward way to homogeneous non-negative bivariate polynomi- als by applying the following “homogenization trick”: if p(t) is a non-homogeneous polynomial of degree d, let q(x, y) = ydp(x/y). Some interesting metric properties of the set of non-negative multivariate polynomials are discussed in exercises of Chapter V see Problems 8 and 9 of Section V.2.4. 4. Theorems of Radon and Helly The following very useful result was first stated in 1921 by J. Radon as a lemma. (4.1) Radon’s Theorem. Let S Rd be a set containing at least d + 2 points. Then there are two non-intersecting subsets R S (“red points”) and B S (“blue points”) such that conv(R) conv(B) = ∅. Proof. Let v1,... , vm, m d+2, be distinct points from S. Consider the following system of d + 1 homogeneous linear equations in variables γ1,... , γm: γ1v1 + . . . + γmvm = 0 and γ1 + . . . + γm = 0. Since m d + 2, there is a non-trivial solution to this system. Let R = vi : γi 0 and B = vi : γi 0 . Then R B = ∅. Let β = i:γi 0 γi. Then β 0 and i:γi 0 γi = −β, since γ’s sum up to zero. Since γ1v1 + . . . + γmvm = 0, we have i:γi 0 γivi = i:γi 0 (−γi)vi.
Previous Page Next Page