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 R+
n
\ {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