Integre Technical Publishing Co., Inc. American Mathematical Monthly October 17, 2000 8:24 a.m. notes.

. notes.tex page 151

NOTES
Edited by Jimmie D. Lawson and William Adkins

b
The Multi-Dimensional Version of a x pdx
Jean B. Lasserre and Konstantin E. Avrachenkov

1. INTRODUCTION. Besides its own interest, integration of polynomials over

simple sets such as simplices has important applications. In particular, in most nite
element integration methods ([8, p. 90, p. 175]), the domain of integration is decom-
posed into elementary cells and the function is approximated by a polynomial on
each cell. The simplex-like elements (triangles, tetrahedrons,. . . ) are among the most
popular type of cells.
In this paper we obtain a new exact integration formula for a q-homogeneous poly-
nomial that is not an approximate quadrature formula ([1], [2], [7]) but rather is the
multi-dimensional version of the one-dimensional classical formula
 b
bq+1 a q+1 ba q
xq dx = = [a + a q1 b + + abq1 + bq ]. (1.1)
a 1+q 1+q
Among its nice features, the multi-dimensional analogue of (1.1) has a simple form, is
coordinate-free, and uses information at the vertices only. In addition, various simpli-
cations are possible to yield even simpler alternative formulae [4].
Since every polynomial can be represented as a sum of homogeneous polynomials,
one can easily apply our results to integrate an arbitrary polynomial over a simplex.
Another interesting feature of this formula is that it could be used efciently in a
nite-element method using simplices. For example, while building the elementary
simplices  of the mesh, it is easy to associate once and for all with each  (via
this formula), a matrix Q  , so that integrating a quadratic functional x  Qx reduces to
computing trace (Q Q  ), which requires only n 2 scalar multiplications. This may be
particularly useful when one has to integrate various quadratic functionals on the same
mesh. A similar argument is also valid for arbitrary q-homogeneous functionals.

2. MAIN RESULT. Let n Rn be an n-dimensional (non-degenerate) n simplex,

that is, x n if and only if x is a convex combination x
0 i i (with i 0
and i i = 1) of n + 1 points x0 , x1 , . . . , xn such that the vectors (xi x0 ), i =
1, 2, . . . , n, are linearly independent. We let x  denote the transpose of a vector x.
Let p(x) : Rn R be a real (positively) r -homogeneous polynomial, i.e., p(x) =
p(x) for all > 0, x Rn , and some integer r 0.
r

We are interested in computing


p(x) d x. (2.1)
n

We rst introduce some notation. With every symmetric multilinear form H :

(Rn )q R, given by

(x1 , . . . , xq )  H (x1 , . . . , xq ), x1 , . . . , xq Rn , (2.2)

February 2001] NOTES 151

 Integre Technical Publishing Co., Inc. American Mathematical Monthly October 17, 2000 8:24 a.m. notes.tex page 152

one may associate a q-homogeneous polynomial x  f (x) := H (x, x, . . . , x) and

conversely, using a polarization formula, with every q-homogeneous polynomial f :
Rn R, one may associate a symmetric q-linear form H : (Rn )q R. Therefore,
we now consider the integration of a q-linear form H over the simplex n .

Theorem 2.1. Let x0 , x1 , . . . , xn be the vertices of an n-dimensional simplex n .

Then, for a symmetric q-linear form H : (Rn )q R, one has
  
vol(n ) 
H (x, x, . . . , x) d x = n+q  H (xi1 , xi2 , . . . , xiq ) . (2.3)
n q 0i 1 i 2 ,...,i q n

Proof. We use the well-known formula for integrating a homogeneous polynomial on

the canonical simplex

1 ! . . . n !
x1 1 . . . xnn d x =  , (2.4)
n (n + i i )!
n
where n := {x Rn | i=1 xi 1; xi 0, i = 1, 2, . . . , n} ([2], [6]). Of course,
(2.4) is valid only for the canonical simplex n . The key idea is to use properties of a
symmetric q-linear form.  
n
nWrite x n as xn = i=0 i xi with i 0 and i i = 1, or equivalently, x =
i=1 i x i + (1 i=1 i )x 0 with (1 , . . . , n ) n , and where


n
n := { Rn | i 1, i 0, i = 1, 2, . . . , n, }
i=1

i.e., n is just the canonical simplex in Rn .

Therefore, noting that

n  n 
n
x = i xi + 1 i x0 = x0 + i (xi x0 ),
i=1 i=1 i=1

we have, by a change of variable x ,


H (x, x, . . . , x) d x = det(x1 x0 , x2 x0 , . . . , xn x0 )
n


n  
n 
n
H i xi + 1 i x0 , . . . , i xi + 1 i x0 d,
n i=1 i i=1 i=1

= n! vol(n )


 n 
n 
n 
n
H i xi + 1 i x0 , . . . , i xi + 1 i x0 d.
n i=1 i=1 i=1 i=1

Expanding, we get:

H (x, x, . . . , x) d x = n! vol(n )
n

0
 
n

A(0 , . . . , n ) 1 i 1 1 . . . n n d. (2.5)
n n
0 i =q
i=1

152

c THE MATHEMATICAL ASSOCIATION OF AMERICA [Monthly 108

Integre Technical Publishing Co., Inc. American Mathematical Monthly October 17, 2000 8:24 a.m. notes.tex page 153

As H is symmetric, in (2.5), we have

    n1 
q q 0 q i=0 i
A(0 , . . . , n ) = H (x0 0 , x1 1 , . . . , xnn ), (2.6)
0 1 n
n
where i=0 i = q and where the notation H (x0 0 , x1 1 , . . . , xnn ) means that x0 ap-
pears 0 times,x1 appears 1 times, . . ., xn appears n times.
n
Now, with i=0 i = q, we have
 

0
n
0 ! 1 ! n !
1 i 1 1 n n d = (2.7)
n i=1
(n + q)!

[2, (2.2)]. Therefore, using (2.6) and (2.7) in (2.5), and noting that
    n1 
q q 0 q i=0 i 0 ! 1 ! n ! q!
= ,
0 1 n (n + q)! (n + q)!
we get
 
q! n!
H (x, x, . . . , x) d x = vol(n ) H (x0 0 , . . . , xnn )
n (n + q)! n =q
0 i

vol(n ) 
= n+q  H (xi1 , xi2 , . . . , xiq )
q 0i 1 i q n

As one may see, the formula (2.3) is extremely simple. Among its nice features:
it uses only n + 1 points, the vertices x0 , . . . , xn of n .
it is coordinate-free, i.e., it is given directly for an arbitrary simplex and not only the
canonical simplex.
all coefcients in the formula are equal, positive, and with ratio to vol(n ) bounded
as n increases.

As already mentioned, every polynomial pn (x) : Rn R of degree q is the sum of

at most q + 1 homogeneous polynomials of degree 0, 1, . . . , q. To each one of them
corresponds a 0-linear, 1-linear, . . ., q-linear form, to which in turn, the formula (2.3)
may be applied. Thus, Theorem 2.1 provides a simple way to integrate an arbitrary
polynomial on a simplex.
One may see that (2.3) is the n-dimensional counterpart of the one-dimensional
formula
 b
(bq+1 a q+1 ) ba
xq dx = = 1+q  [a q + a q1 b + + abq1 + bq ], (2.8)
a q + 1 q

since (b a) = vol([a, b]).

Remark 2.2. Consider the integration of a quadratic homogeneous functional x  Qx

(with Q a (n, n) symmetric
real-valued matrix) on an n-dimensional simplex . The
functional Q   x  Qxd x may be viewed as a linear form on the n(n + 1)/2-
dimensional Hilbert space of real-valued symmetric matrices, with the Frobenius

February 2001] NOTES 153

 Integre Technical Publishing Co., Inc. American Mathematical Monthly October 17, 2000 8:24 a.m. notes.tex page 154

scalar product Q, Q  = trace(Q Q ). Therefore,


x  Qx d x = vol() Q, Q  , (2.9)


for some symmetric matrix Q  . The identication of Q  is easy from (2.3). For ex-
ample, with n = 2 and  := {(xi , yi )}, i = 0, 1, 2,
 
xi x j 1
2
[xi y j + yi x j ]
1 0i j2 0i j2
Q  =  

6 1
[x i y j + yi x j ] y i y j
2
0i j2 0i j2

and in the n-dimensional case, for a simplex n := {x0 , . . . , xn },

2  1
Q  (i, j) = [xik x jl + x jk xil ].
(n + 1)(n + 2) 0kln
2

Hence, with an arbitrary n-dimensional simplex , one may associate a symmetric

matrix Q  so that for every (symmetric) functional x  Qx, (2.9) holds. This represen-
tation is especially useful when one has to compute (2.3) for several matrices Q. For
example, the matrices Q  can be precomputed in a nite element method while build-
ing a mesh. Then, evaluating (2.3) for a functional x  Qx via (2.9), requires only n 2
scalar multiplications, in contrast to evaluating n(n + 1)/2 terms of the form xi Qx j
(each term also requires about n 2 multiplications). Of course, a similar construction
holds for q-linear symmetric forms.

REFERENCES

1. I.J. Good and T.N. Tideman, Integration over a simplex, truncated cubes, and Eulerian numbers, Numer.
Math. 30 (1978) 355367.
2. A. Grundmann and H.M. Moeller, Invariant integration formulas for the n-simplex by combinatorial meth-
ods, SIAM J. Numer. Anal. 15 (1978) 282290.
3. J.B. Lasserre, Integration and homogeneous functions, Proc. Amer. Math. Soc. 127 (1999) 813818.
4. J.B. Lasserre and K.E. Avrachenkov, Integration on a simplex, Technical report #98334, Laboratoire
dAnalyse et dArchitecture des Systemes du CNRS, Toulouse, France, 1998.
5. J. Riordan, Combinatorial Identities, Robert E. Krieger Publishing Company, New York, 1979.
6. A.H. Stroud, A fth degree integration formula for the n-simplex, SIAM J. Numer. Anal. 6 (1969) 9098.
7. A.H. Stroud, Approximate Calculation of Multiple Integrals, Prentice Hall, Englewood Cliffs, NJ, 1971.
8. O.C. Zienkiewicz and R.L. Taylor, The Finite Element Method, 4th ed., vol 1 and 2, McGraw-Hill Book
Company, London, 1988.

LAAS-CNRS, 7 Avenue du Colonel Roche, 31077 Toulouse Cedex 4, France

lasserre@laas.fr
INRIA, Sophia Antipolis, 2004 Route des Lucioles, B.P. 93, 06902 Sophia Antipolis, France
k.avrachenkov@sophia.inria.fr

154

c THE MATHEMATICAL ASSOCIATION OF AMERICA [Monthly 108

Integre Technical Publishing Co., Inc. American Mathematical Monthly October 17, 2000 8:24 a.m. notes.tex page 155

Almost Sure Escape from the Unit Interval

Under the Logistic Map
Sibylle Zeller and Maximilian Thaler

The logistic map f a (x) = ax(1 x) (x R) with a > 4 is a good starting point
for introducing symbolic dynamics as well as other basic notions in rst courses on
dynamical systems [1, (1.5)(1.7)]. The interesting part of the dynamics of f a takes
place on the Cantor set


a = f an ([0, 1]),
n=0

which has Lebesgue measure zero; see [2]. The purpose of this note is to present a
short and elementary proof of this property of a . Except for a formal modication,
the proof is taken from [7].
Since f a (1/2) = 0, for parameters a close to 4 even the proof of the Cantor prop-
erty of a is not straightforward. For a detailed discussion of this point we refer to
[3], which motivated us to publish this note. Regarding the essence of the underlying
technique, our approach is closely related to [5, Section 2.4.3].
We start with the case a = 4. The analysis of the dynamical system ([0, 1], f 4 ) is
usually based on the conjugation f 4 1 = g4 , where
2
(x) = arcsin x and g4 (x) = 1 |1 2x|, x [0, 1].

This identity has been known since the early days of iteration theory [6, p. 306]. The
map g4 is particularly nice because it is piecewise linear. The crucial point, however,
is that g4 is uniformly expanding.
Our method adapts this technique to the case a > 4, and scales the function ac-
cording to the fact that f a ([0, 1]) = [0, a/4]. The resulting maps turn out to be uni-
formly expanding, and, moreover, the degree of expansivity is high enough to yield
the desired result without effort.
For a > 4, let a (x) = a/4 (4x/a), x [0, a/4]. Dene the map ga on the in-
terval [0, a (1)] by

ga = a f a a1 ; (1)

see Figure 1.
Since

n1
a f an = gan a on f a j ([0, 1]), n 1,
j=0

escaping from [0, 1] under f a corresponds to escaping from [0, a (1)] under ga . The
a , ga ) where
map a conjugates the systems (a , f a ) and (


a =
 gan ([0, a (1)]).
n=0

February 2001] NOTES 155

 Integre Technical Publishing Co., Inc. American Mathematical Monthly October 17, 2000 8:24 a.m. notes.tex page 156

Figure 1. Graphs of the maps f a and ga for a = 4.2; c = a (1)

Drawing graphs immediately leads to the conjecture that ga is uniformly expanding

on [0, a (1)] . The following lemma makes this basic observation precise.

Lemma. Let a > 4, and let ga be dened as in (1). Then

  
|ga (y)| a for all y [0, a (1)) \ a 12 .

Proof. Let y = a (x), x (0, 1) \ { 12 }. Differentiation of the identity f 4 = g4

yields

 ( f 4 (x)) f 4 (x) = (2 sign(1 2x))  (x).

Therefore, taking into account that f a (x) = (a/4) f 4 (x) and a (x) =  (4x/a), we
obtain

ga (y) = a ( f a (a1 (y))) f a (a1 (y)) (a1 ) (y)

a ( f a (x)) f a (x) a  ( f 4 (x)) f 4 (x)
= =
a (x)
 4 a (x)

1/2
a  (x) 1 a4 x
= sign(1 2x) = sign(1 2x) a .
2 ( a x)
 4
1x

Since 4/a < 1, the assertion is proved.

Now, for a > 4, let the intervals Is0 ,...,sn1 , (s0 , . . . , sn1 ) {0, 1}n , n 1, be de-
ned in the usual way, i.e.,

n1
Is0 ,...,sn1 = f a j (Is j ), where
j=0

I0 = [0, ], I1 = [1 , 1], = (a) < 1/2 and f a () = 1,

and let Is0 ,...,sn1 denote the corresponding intervals for the map ga . Let

a (n) = max{(Is0 ,...,sn1 ) : (s0 , . . . , sn1 ) {0, 1}n }, n 1,

where denotes the Lebesgue measure. Then we have the following estimate.

156

c THE MATHEMATICAL ASSOCIATION OF AMERICA [Monthly 108

Integre Technical Publishing Co., Inc. American Mathematical Monthly October 17, 2000 8:24 a.m. notes.tex page 157

Theorem. For all a > 4,

 n1
1
a (n) , n 1. (2)
4 a

Proof. Let n 1 and let (s0 , . . . , sn1 ) be xed. In view of the lemma, the standard
mean value argument yields
 
1 n
( Is0 ,...,sn1 ) a (1) .
a

Using Is0 ,...,sn1 = a1 ( Is0 ,...,sn1 ) and (a1 ) /2 we obtain

 
1 n
(Is0 ,...,sn1 ) a (1) .
2 a

Since x arcsin x 1 /2, x 1, we get a (1) a/2, and thus (2) follows.

Corollary. (a ) = 0 for all a > 4.

Proof. Since the set f an ([0, 1]) is the union of the 2n intervals Is0 ,...,sn1 , we have

2 n1
( f an ([0, 1])) 2n a (n) ( ) , n 1,
2 a

and hence (a ) = limn ( f an ([0, 1])) = 0.

Concluding remark. In probabilistic language, escape from the unit interval occurs
with probability one if the initial value is assumed to be a random variable with a
absolutely continuous distribution.
For suitable initial distributions we easily get a rough upper estimate for the mean
escape time. Assume, for example, the initial value to be unifomly distributed on [0, 1],
and let Ta denote the number of steps needed to escape from [0, 1], i.e.,

Ta (x) = min{n 1 : f an (x)

/ [0, 1]},
x [0, 1].
 n
Then E(Ta ), the expected value of Ta , is given by n=0 ( f a ([0, 1])). Since
1
( f a ([0, 1])) = 2(a) 4/a 1/(2( a 2)) we nd, using our estimate for
the terms with n 2, that for some constant K ( 1/2 + )
K
E(Ta ) 1 + for all a > 4.
a2
In [4, pp. 647649] by means of computer experiments and a heuristic argument,
the authors are led to the conjecture that the order of E(Ta ) for a 4 is (a 4)1/2 ,
which is evidently smaller than the order of our bound.

REFERENCES

1. R. L. Devaney, An Introduction to Chaotic Dynamical Systems, Addison-Wesley, Redwood City, CA,

1989.
2. B. R. Henry, Escape from the Unit Interval under the Transformation x  x(1 x), Proc. Amer. Math.
Soc. 41 (1973) 146150.

February 2001] NOTES 157

 Integre Technical Publishing Co., Inc. American Mathematical Monthly October 17, 2000 8:24 a.m. notes.tex page 158

3. R. L. Kraft, Chaos, Cantor Sets, and Hyperbolicity for the Logistic Maps, Amer. Math. Monthly 106 (1999)
400408.
4. H.-O. Peitgen, H. Jurgens, and D. Saupe, Chaos and Fractals. New Frontiers of Science, Springer, New
York, 1992.
5. C. Robinson, Dynamical Systems. Stability, Symbolic Dynamics, and Chaos, CRC Press, Boca Raton, FL,
1995.
6. E. Schroder, Uber iterirte Functionen, Math. Annalen 3 (1871) 296-322.
7. S. Zeller, Chaosbegriffe der topologischen Dynamik, Diplomarbeit, Universitat Salzburg, Salzburg, 1991.

Siemens AG Osterreich, Program and System Engineering, Petersbrunnstrasse 19, A - 5033 Salzburg, Austria
Sibylle.Zeller@siemens.at
Institute of Mathematics, University of Salzburg, Hellbrunnerstrasse 34, A - 5020 Salzburg, Austria
Maximilian.Thaler@sbg.ac.at

Generalized Rearrangement Inequalities

Robert Geretschlager and Walther Janous

In this note, we present an inequality that yields the standard rearrangement inequality
as a special case, as well as other interesting special results.
The standard rearrangement inequality states that, if we are given two ordered
nite sets of real numbers a1 a2 an and b1 b2 bn , and if
(c1 , c2 , . . . , cn ) is a permutation of (b1 , b2 , . . . , bn ), it follows that


n 
n 
n
ai bn+1i ai ci ai bi .
i=1 i=1 i=1

In [1], we saw that the dual of this result holds (a result rst mentioned in [2]), i.e.,
the inequality resulting from inverting the inequality signs and exchanging addition
and multiplication. In other words, (for positive real numbers ai and bi ) we have


n 
n 
n
(ai + bn+1i ) (ai + ci ) (ai + bi ).
i=1 i=1 i=1

We show that both of these inequalities, as well as many other related ones are special
cases of a more general result.
First of all, in order to avoid unnecessary notation, we make the following assump-
tions. We assume as given two ordered nite sequences of n real numbers a1 a2
an and b1 b2 bn . We let the n-dimensional vectors A and B be given
as

A = (a1 , a2 , . . . , an ) and B = (b1 , b2 , . . . , bn ).

We further assume that C = (c1 , c2 , . . . , cn ) is any n-dimensional vector whose entries

are a permutation of the entries of B, and A and B are the vectors resulting from A

158

c THE MATHEMATICAL ASSOCIATION OF AMERICA [Monthly 108

Integre Technical Publishing Co., Inc. American Mathematical Monthly October 17, 2000 8:24 a.m. notes.tex page 159

and B by reversing the order of their entries, i.e.,

A = (an , an1 , . . . , a2 , a1 ) and B = (bn , bn1 , . . . , b2 , b1 ).

Let T be a real-valued function in two real variables dened on the closed intervals
determined by A and B, i.e.,

T : [a1 , an ] [b1 , bn ] R,

and let S : [a1 , an ]n [b1 , bn ]n R be the real-valued function dened by


n
S(X, Y ) := T (xk , yk )
k=1

with X = (x1 , x2 , . . . , xn ) and Y = (y1 , y2 , . . . , yn ) and all xi [a1 , an ] and yi

[b1 , bn ]. Finally, two pairs (a, b) and (c, d) of real numbers are called similarly ordered
if (a c)(b d) 0, and oppositely ordered if (a c)(b d) 0. The following
result then holds.

Theorem 1. Let A, B, C, T and S be as dened above. Assume that the rst order
partial derivatives of T exist everywhere, and that the second order partial derivative
2 T (x, y)/ x y exists for all (x, y) [a1 , an ] [b1 , bn ]. Then
2 T (x,y)
a) if x y
0 for all (x, y) [a1 , an ] [b1 , bn ], we have

S(A, B) S(A, C) S(A, B)

for all possible vectors C, and

2 T (x,y)
b) if x y
0 for all (x, y) [a1 , an ] [b1 , bn ], we have

S(A, B) S(A, C) S(A, B)

for all possible vectors C.

Since S(A, B) = S(A, B) and S(A, B) = S(A, B), the result can be stated informally
as follows:

If numbers {x1 , x2 , . . . , xn } and {y1 , y2 , . . . , yn } are put into some order in vectors X and Y ,
in case a) the value of S(X, Y ) is maximal if the coordinates of X and Y are similarly ordered,
and minimal if they are oppositely ordered. In case b), the value of S(X, Y ) is maximal if the
coordinates of X and Y are oppositely ordered, and minimal if they are similarly ordered.

Proof. Let Ci j be the vector identical to C in all entries except ci and c j , whose values
are exchanged. Thus, if

C = (c1 , . . . , ci1 , ci , ci+1 , . . . , c j1 , c j , c j+1 , . . . , cn ),

then

Ci j = (c1 , . . . , ci1 , c j , ci+1 , . . . , c j1 , ci , c j+1 , . . . , cn ).

February 2001] NOTES 159

 Integre Technical Publishing Co., Inc. American Mathematical Monthly October 17, 2000 8:24 a.m. notes.tex page 160

A computation reveals that


n i1
S(A, C) S(A, Ci j ) = T (ak , ck ) T (ak , ck ) + T (ai , c j )
k=1 k=1


j1 
n
+ T (ak , ck ) + T (a j , ci ) + T (ak , ck )
k=i+1 k= j+1

= T (ai , ci ) + T (a j , c j ) T (ai , c j ) T (a j , ci ).

If we dene the function f i j : [a1 , an ] R by

f i j (t) := T (t, c j ) T (t, ci ),

then

S(A, C) S(A, Ci j ) = f i j (a j ) f i j (ai ).

By the mean-value theorem there exist an [ai , a j ] and a [min(ci , c j ),

max(ci , c j )], such that

S(A, C) S(A, Ci j ) = f i j (a j ) f i j (ai ) = f ij ()(a j ai )

 
T T
= (, c j ) (, ci ) (a j ai )
x x
2T
= (, )(a j ai )(c j ci ).
x y

We assume 2 T (x, y)/ x y 0 for all (x, y) [a1 , an ] [b1 , bn ], and dene a se-
quence

C k = (c1k , c2k , . . . , cnk )

of vectors in the following manner.

We dene C 0 := C, and for 1 k n, if ckk1 = bk dene C k := C k1 , and if
ck = bk , dene C k := Ckr
k1 k1
with crk1 = bk . Dening the C k in this way means that
ci = bi for all 1 i k (and therefore also C n = B). Since b1 b2 bn , it
k

follows that ckk1 crk1 = bk , and we have

S(A, C k ) S(A, C k1 ) = S(A, Ckr

k1
) S(A, C k1 )
2T
= (, )(ak ak1 )(crk1 ckk1 )
x y
2T
= (, )(ak ak1 )(bk ckk1 ) 0
x y

if C k1 = C k . Of course, if C k1 = C k , we have S(A, C k ) S(A, C k1 ) = 0, and

it follows that S(A, C k ) S(A, C k1 ) 0 for all 1 k n, that is, S(A, C k )
S(A, C k1 ). Summarizing, we have

160

c THE MATHEMATICAL ASSOCIATION OF AMERICA [Monthly 108

Integre Technical Publishing Co., Inc. American Mathematical Monthly October 17, 2000 8:24 a.m. notes.tex page 161

S(A, C) = S(A, C 0 ) S(A, C 1 ) S(A, C 2 ) S(A, C n ) = S(A, B),

and for any C, we certainly have S(A, C) S(A, B).

Similarly, we can dene a sequence

D k = (d1k , d2k , . . . , dnk )

by D 0 := C, D k := D k1 if dkk1 = bn+1k and D k := Dkr

k1
with drk1 = bn+1k if
dk = bn+1k . This sequence yields
k1

S(A, C) = S(A, D 0 ) S(A, D 1 ) S(A, D 2 ) S(A, D n ) = S(A, B),

and therefore S(A, C) S(A, B), which completes the proof of part a).
Since the assumption of T (x, y)/ x y 0 reverses the orientation of all relevant
inequalities, part b) is proven analogously by dening the same sequences C k and D k .

Remarks.

Choosing T (x, y) = x y, we have

2 T (x, y)
=10
x y

for all real values of x and y, and Theorem 1 yields the standard rearrangement
inequality in this case, since we have

S(A, C) = a1 c1 + a2 c2 + + an cn .

Therefore,

S(A, B) S(A, C) S(A, B)

is equivalent to

a1 bn + a2 bn1 + + an b1 a1 c1 + a2 c2 + + an cn a1 b1 + a2 b2 + + an bn .
On the other hand, choosing T (x, y) = ln(x + y), we have

2 T (x, y) 1
= <0
x y (x + y)2

for all positive real values of x and y, and Theorem 1 yields the dual rearrangement
inequality, since we have

S(A, C) = ln(a1 + c1 ) + ln(a2 + c2 ) + + ln(an + cn )

n
= ln (ai + ci ) ,
i=1

February 2001] NOTES 161

 Integre Technical Publishing Co., Inc. American Mathematical Monthly October 17, 2000 8:24 a.m. notes.tex page 162

and

S(A, B) S(A, C) S(A, B)

is equivalent to

n n n
ln (ai + bn+1i ) ln (ai + ci ) ln (ai + bi ) ,
i=1 i=1 i=1

i.e.,

n 
n 
n
(ai + bn+1i ) (ai + ci ) (ai + bi ).
i=1 i=1 i=1

From these two examples, we see that we can expect some interesting special cases.
All we have to do is to choose appropriate functions T , such that their second-degree
partial derivatives are either non-negative or non-positive in a certain rectangle. Each
such choice then yields an inequality. Here are several examples:

Example 1. Generating function:

T1 (x, y) = f (x)g(y).

The functions f and g are both assumed to be differentiable and either increasing or
decreasing in the entire interval under consideration. We then have

2 T1 (x, y)
= f  (x)g  (y).
x y
If f and g are both increasing (or both decreasing), this expression is non-negative,
and we have

n 
n 
n
f (ai )g(bn+1k ) f (ai )g(ci ) f (ai )g(bi ).
i=1 i=1 i=1

If one of the functions f and g increases, and the other decreases, the expression is
non-positive, and the opposite inequalities hold. A few specic examples of this type
are:
1a.
1
f (x) = x and g(y) = .
y

Since f  (x) = 1 > 0 for all real values of x and g  (y) = y 2 < 0 for all real values
of y except 0, we have

n
ai 
n
ai 
n
ai

i=1
bn+1k i=1
ci i=1
bi

for any real numbers ai , and any choice of either all positive or all negative numbers
bi .

162

c THE MATHEMATICAL ASSOCIATION OF AMERICA [Monthly 108

Integre Technical Publishing Co., Inc. American Mathematical Monthly October 17, 2000 8:24 a.m. notes.tex page 163

1b.

f (x) = x p and g(y) = y q .

If p > 0, we have f  (x) = px p1 > 0 for all positive real values of x, and if p < 0,
we have f  (x) < 0 for all positive real values of x. Since the analogous result holds
for g, we have

n 
n 
n
aip bn+1i
q
aip ciq aip biq
i=1 i=1 i=1

for all positive real values of ai and bi if pq > 0; the opposite inequalities hold if
pq < 0.
If we choose p = 2m + 1 and q = 2n + 1 with positive integers m and n, we have
f  (x) = (2m + 1)x 2m and g  (y) = (2n + 1)y 2n , both of which are dened and non-
negative for all real values of x and y respectively. We therefore have

n 
n 
n
ai2m+1 bn+1i
2n+1
ai2m+1 ci2n+1 ai2m+1 bi2n+1
i=1 i=1 i=1

for all real values of ai and bi .

1c.

f (x) = p x and g(y) = q x .

If p > 1 we have f  (x) = p x ln p > 0 for all real values of x, and if 0 < p < 1 this
expression is negative. Since the same holds in an analogous way for g and q, we have

n 
n 
n
pai q bn+1i pai q ci pai q bi
i=1 i=1 i=1

if both p > 1 and q > 1 hold, or if both 0 < p < 1 and 0 < q < 1 hold. If one base
is greater than 1 and one is between 0 and 1, the opposite inequalities hold.

Example 2. Generating function:

T2 (x, y) = ln( f (x) + g(y)).

The functions f and g are again both assumed to be differentiable and either increasing
or decreasing in the entire interval under consideration. In addition, f and g can be
considered only in intervals in which f (x) + g(y) > 0 holds for any choice of x and
y. We then have

2 T2 (x, y) f  (x)g  (y)

= .
x y ( f (x) + g(y))2
If f and g are both increasing (or both decreasing), this expression is non-positive,
and we have

n 
n 
n
ln( f (ai ) + g(bn+1k )) ln( f (ai ) + g(ci )) ln( f (ai ) + g(bi )),
i=1 i=1 i=1

February 2001] NOTES 163

 Integre Technical Publishing Co., Inc. American Mathematical Monthly October 17, 2000 8:24 a.m. notes.tex page 164

i.e.,

n 
n 
n
( f (ai ) + g(bn+1k )) ( f (ai ) + g(ci )) ( f (ai ) + g(bi )).
i=1 i=1 i=1

If one of the functions increases and the other decreases, the expression is non-negative
and the opposite inequalities hold. A few specic examples of this type are:

2a. As in 1b, let

f (x) = x p and g(y) = y q .

We then have

n
 p q  n
 p  n
 p 
ai + bn+1i ai + ciq ai + biq
i=1 i=1 i=1

for all positive real values of ai and bi if pq > 0; the opposite inequalities hold if
pq < 0.

2b. As in 1c, let

f (x) = p x and g(y) = q x .

Then

n
  n 
n
 a 
pai + q bn+1i ( pai + q ci ) p i + q bi
i=1 i=1 i=1

if both p > 1 and q > 1 hold, or if both 0 < p < 1 and 0 < q < 1 hold. If one base
is greater than 1 and one is between 0 and 1, the opposite inequalities hold.

Example 3. Generating function:

T3 (x, y) = ( + x)+y ,

where and are xed real numbers. This function is dened for real numbers x >
and any real values of y. We have

2 T3 (x, y)
= ( + x)+y1 (1 + ( + y) ln( + x)).
x y

For x + 1 and y , this expression is certainly positive, and so for values

of ai not less than + 1 and values of bi not less than we have

n 
n 
n
( + ai )+bn+1i ( + ai )+ci ( + ai )+bi .
i=1 i=1 i=1

Further such examples can be derived by considering polynomial functions in the

intervals between or beyond their extreme points, or trigonometric functions in inter-

164

c THE MATHEMATICAL ASSOCIATION OF AMERICA [Monthly 108

Integre Technical Publishing Co., Inc. American Mathematical Monthly October 17, 2000 8:24 a.m. notes.tex page 165

vals in which they are strictly increasing or decreasing, or several kinds of composite
functions such as f (x  y) (where  can stand for any basic arithmetical operation) or
f (x) ln(g(y)).

REFERENCES

1. Robert Geretschlager, Deriving Some Problems in Inequalities from an Accidental Generalization, Math-
ematics Competitions 12 (1999) 2737.
2. A. Oppenheim, Inequalities Connected with Denite Hermitian Forms II, Amer. Math. Monthly 61 (1954)
463466.

Breunergasse 23, A-8051 Graz, AUSTRIA

geretsch@borg-6.borg-graz.ac.at

Schneeburggasse 169, A-6020 Innsbruck, AUSTRIA

walther.janous@nsl.asn-ibk.ac.at

A Weighted Erdos-Mordell Inequality

Seannie Dar and Shay Gueron

Let ABC be a triangle and let P be an interior point. Let d A , d B , dC , be the

distances of P from A, B, C, and let d AB , d BC , dC A be the distances of P from the
sides AB, BC, C A, respectively. Then

d A + d B + dC 2(d AB + d BC + dC A ).

The inequality is sharp: equality holds if and only if the triangle is equilateral and the
point P is its center. This is the celebrated Erdos-Mordell inequality. It was conjectured
by Erdos in 1935 [1], and was rst proved by Mordell in 1937 [2]. This theorem,
together with its clever proof is a beautiful piece of elementary mathematics. Other
elementary proofs for this theorem are known [3], and some comments on the history
of the problem appear in [4].
In this note we generalize the Erdos-Mordell theorem, and prove what we call a
weighted Erdos-Mordell inequality. In the case we treat, the inequality we obtain is
also sharp; equality holds if and only if a certain ratio between the sides of the triangle
holds and the point P is the circumcenter.
The Erdos-Mordell inequality is obtained as a special case of our weighted Erdos-
Mordell inequality, for equal weights.

Theorem. (A weighted Erdos-Mordell inequality) Let 1 , 2 , 3 be any three posi-

tive constants. Let A1 A2 A3 be a triangle with sides a1 , a2 , a3 , and angles 1 , 2 , 3 .
Let P be an interior point and let Fi be the foot of the perpendicular from P to the side
opposite Ai . Denote P Ai = ri and P Fi = di . Then


3  3
1
i ri 2 1 2 3 di . (1)
i=1 i=1 i

February 2001] NOTES 165

 Integre Technical Publishing Co., Inc. American Mathematical Monthly October 17, 2000 8:24 a.m. notes.tex page 166

Equality holds in (1) if and only if

  
a1 : a2 : a3 = 1 : 2 : 3 (2)

and P is the circumcenter of A1 A2 A3 .

Proof. The quadrilateral A1 F2 P F3 is cyclic. Therefore, F2 P F3 = 180 1 = 2 +

3 . Thus, the cosine law gives

F2 F32 = P F22 + P F32 2P F2 P F3 cos F2 P F3 = d22 + d32 2d2 d3 cos(2 + 3 )

= (sin2 3 + cos2 3 )d22 + (sin2 2 + cos2 2 )d32
+ 2(sin 2 sin 3 cos 2 cos 3 )d2 d3
= (d2 sin 3 + d3 sin 2 )2 + (d2 cos 3 d3 cos 2 )2 . (3)

A1 P is the diameter of the circumcircle of A1 F2 P F3 , so by the standard formula for

the circumradius of a triangle, we have

F2 F3 = A1 P sin 1 = r1 sin 1

and nally obtain

(r1 sin 1 )2 = (F2 F3 )2 = (d2 sin 3 + d3 sin 2 )2 + (d2 cos 3 d3 cos 2 )2

(d2 sin 3 + d3 sin 2 )2 . (4)

Hence,
   
sin 3 sin 2
r1 d2 + d3 . (5)
sin 1 sin 1

Equality in (5) holds if and only if d2 cos 3 = d3 cos 2 , i.e., if and only if
       
sin( A2 A1 P) d3 cos 3 sin(90 3 )
= = = . (6)
sin( A3 A1 P) d2 cos 2 sin(90 2 )

Since A2 A1 P + A3 A1 P = (90 3 ) + (90 2 ) it follows that equality in (5)

holds if and only if

A2 A1 P = 90 3 and A3 A1 P = 90 2 , (7)

which means that P lies on the line connecting A1 to the circumcenter of the triangle.
Similarly, we get
   
sin 1 sin 3
r2 d3 + d1 (8)
sin 2 sin 2

and
   
sin 2 sin 1
r3 d1 + d2 (9)
sin 3 sin 3

166

c THE MATHEMATICAL ASSOCIATION OF AMERICA [Monthly 108

Integre Technical Publishing Co., Inc. American Mathematical Monthly October 17, 2000 8:24 a.m. notes.tex page 167

with analogous conditions for equality. Multiplying (5), (8), and (9) by 1 , 2 , and 3 ,
respectively, and summing, we obtain
    
sin 3 sin 2
1r1 + 2r2 + 3r3 2 + 3 d1
sin 2 sin 3
    
sin 1 sin 3
+ 3 + 1 d2
sin 3 sin 1
    
sin 2 sin 1
+ 1 + 2 d3 (10)
sin 1 sin 2

and equality holds if and only if P is the circumcenter of A1 A2 A3 .

By the arithmetic mean-geometric mean inequality we have
    
sin 3 sin 2
2 + 3 2 2 3 (11)
sin 2 sin 3

with equality if and only if

   
sin 3 sin 2
2 = 3 , (12)
sin 2 sin 3

which is equivalent to
 
a2 sin 2 2
= = . (13)
a3 sin 3 3

Similarly,
    
sin 1 sin 3
3 + 1 2 3 1 (14)
sin 3 sin 1

and
    
sin 2 sin 1
1 + 2 2 1 2 (15)
sin 1 sin 2

with analogous conditions for equality. Finally, combining (10), (11), (14), and (15),
and the related conditions for equality, we get the desired result.

Remark. The special case 1 = 2 = 3 yields the celebrated Erdos-Mordell inequal-

ity. In this case, equality holds only for an equilateral triangle with center at P.

ACKNOWLEDGMENTS. We thank Ran Tessler, who initiated our study of this generalization.

REFERENCES

1. P. Erdos, Problem 3740, Amer. Math. Monthly 42 (1935) 396.

2. L. J. Mordell and D. F. Barrow, Solution 3740, Amer. Math. Monthly 44 (1937) 252254.

February 2001] NOTES 167

 Integre Technical Publishing Co., Inc. American Mathematical Monthly October 17, 2000 8:24 a.m. notes.tex page 168

3. L. Bankoff, An elementary proof of the Erdos-Mordell theorem, Amer. Math. Monthly 65 (1958) 521.
4. L. J. Mordell, On geometric problems of Erdos and Oppenheim, Math. Gazette 46 (1962) 213215.

The Academic College of Tel-Aviv Yaffo, Tel Aviv, 61161, Israel.

University of Haifa, Haifa 31905, Israel.
shay@math.haifa.ac.il

A Four-Point Set That Cannot Be Split

Jan J. Dijkstra

If n is an integer greater than one then an n-point set is a subset of the plane that meets
every line in precisely n points. A planar set is called a partial n-point set if it meets
every line in at most n points. Using a well-ordering of the real line Mazurkiewicz [5]
proved that 2-point sets exist. This result was generalized to n-point sets and beyond
by Bagemihl [1] and Sierpinski [6]. Additional information, references, and some un-
solved problems concerning these peculiar sets can be found in [3] and [4].
If X is an n-point set that is contained in an (n + 1)-point set Y then Y \ X must be a
set that meets each line in exactly one point. Since such one-point sets obviously do
not exist it is impossible for an (n + 1)-point set to contain an n-point set. In contrast,
Bouhjar et al. [2] prove that if 2 n k 2 then each n-point set is contained in some

Figure 1.

168

c THE MATHEMATICAL ASSOCIATION OF AMERICA [Monthly 108

Integre Technical Publishing Co., Inc. American Mathematical Monthly October 17, 2000 8:24 a.m. notes.tex page 169

Figure 2.

k-point set. For example, for every 2-point set one may construct another 2-point set
such that their union is a 4-point set. It is natural to ask whether every k-point set (with
k 4) contains an n-point set for some n k 2. We answer this question in the
negative:

Theorem. There exists a 4-point set that fails to contain a 2-point set.

Proof. It sufces to construct a nite partial 4-point set that cannot be partitioned into
two partial 2-point sets. To see this let F be such a partial 4-point set. Let c stand for
the cardinality of the real line. It is implicit in the proofs of the existence of n-point
sets that every partial n-point set with less than c points is extendable to an n-point set.
Let X be a 4-point set that contains F. Assume that A is a 2-point set that is contained
in X. It is obvious that X \ A is then also a 2-point set and that both F A and F \ A
are partial 2-point sets, a contradiction.
The set F is dened by

F = {1, 3}2 ({2, 4} {0}) {(0, 4), (0, 4)}.

Inspection of F in Figure 1 shows that it is a partial 4-point set. Assume that F can
be partitioned into two partial 2-point sets A and B. If we denote points in A with a
closed dot and points in B with an open dot then we have have three ways to ll in the
row {1, 3} {1} after accounting for symmetry; see Figure 2.
In the cases (b) and (c) we may choose the point (0, 4) to be in A.
The remainder of the proof consists of playing Tic-Tac-Toe with the graphs: if we
line up three dots of the same type then we have reached the desired contradiction.

Figure 3.

February 2001] NOTES 169

 Integre Technical Publishing Co., Inc. American Mathematical Monthly October 17, 2000 8:24 a.m. notes.tex page 170

Figure 4.

Figure 5.

The rule is that if we have two dots of the same type on one line then the other dots
on that line are of the other type. In case (a) we consider the two possibilities for the
point (3, 3) (indicated by the arrow). Figure 3 shows congurations that are forced
by our choices.
Figure 4 shows case (b). Finally, Figure 5 shows case (c) with the two choices for
the point (1, 3).

ACKNOWLEDGEMENTS: The author is pleased to thank the Vrije Universiteit in Amsterdam for its hos-
pitality. Research supported by a grant from the Research Advisory Committee of the University of Alabama.

REFERENCES

1. F. Bagemihl, A theorem on intersections of prescribed cardinality, Ann. of Math. 55 (1952) 3437.

2. K. Bouhjar, J. J. Dijkstra, and J. van Mill, Three-point sets, Topology Appl., to appear.
3. J. J. Dijkstra, K. Kunen, and J. van Mill, Hausdorff measures and two-point set extensions, Fund. Math.
157 (1998) 4360.
4. R. D. Mauldin, On sets which meet each line in exactly two points, Bull. London Math. Soc. 30 (1998)
397403.
5. S. Mazurkiewicz, O pewnej mnogosci paskiej, ktora ma z kazda prosta dwa i tylko dwa punkty wspolne,
C. R. Varsovie 7 (1914) 382384 (Polish); French transl. Sur un ensemble plan qui a avec chaque droite
deux et seulement deux points cummuns, in: Traveaux de Topologie et ses Applications, K. Borsuk et al.
(eds.), PWN, Warsaw, 1969, pp. 4647.
6. W. Sierpinski, Une generalisation des theoremes de S. Mazurkiewicz et F. Bagemihl, Fund. Math.
40 (1953) 12.

The University of Alabama, Box 870350, Tuscaloosa, Alabama 35487-0350, USA.

jdijkstr@obelix.math.ua.edu

170

c THE MATHEMATICAL ASSOCIATION OF AMERICA [Monthly 108