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
= (ξ1, . . . , ξn) : ξi ≥ 0 for i = 1, . . . , n
be the non-negative orthant in
p(x) 0 for all x ∈ R+
Then there exists a positive integer s such that the coeﬃcients λa} of the polyno-
(ξ1 + . . . +
, ξn) =
. . . ξn
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 ⊂
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. Then β 0 and
γi = −β, since γ’s sum up to zero.
Since γ1v1 + . . . + γmvm = 0, we have