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 coeﬃcients λ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.