ERDOS’S CONJECTURE on
THE DISTRIBUTION OF
THE sums} 1’in 9 fl 0F n VECTORS
III d-DIMENSIONAL SPACE

Thesis for the Degree of Ph. D.
MICHIGAN STATE UNIVERSITY
ANTONIO SANTIAGO VILLANUEVA
1970

TH E S I b
wensmv am

IIIIIII‘I‘IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII III L

3 1293 00791 5378

This is to certify that the

thesis entitled
ERDOS'S CONJECTURE ON THE DISTRIBUTION OF

n
THE sums Z m 8.5a; 0? n VECTORS IN

(1- DIMENSIONAL SPEC E
presented by

Antonio Santiago Villanueva

has been accepted towards fulfillment
of the requirements for

Pho Do degree in Plath.

QM SM

Major professor

Date May 15, 1970

0-169

 

 

 

Fm”.
V BINNNG BY

“0A5 & SUNS'
300K Blllflflll ”3", ‘

  

LIBRARY BINDI ‘

 

   
  
 

9“} 7' (:
/{I’IZM’L.‘ ‘

mm Lamar

IIIIIIIIIIIIIIIIHIIIlIIlllllIllllllllIIllIllIIIIIIIIIIIIIIII

3 1293 00791

 

This is to certify that the

thesis entitled
ERDOS'S CONJECTURE ON THE DISTRIBUTION OF

n
THE SUMS Z m 5,3; 0F n VECTORS IN

d-DIMENSIONAL SPACE
presented by

 

Antonio Santiago Villanueva

has been accepted towards fulfillment
of the requirements for

Pho Do degree in Math.

 

RM SM

Major professor

 

Date May 15, 1970

0-169

 

ABSTRACT

ERDOS'S CONJECTURE ON THE DISTRIBUTION OF

THE SUMS 22:1 eiai OF n VECTORS IN

d-DIMENSIONAL SPACE
By

Antonio Santiago Villanueva

This thesis is a study of P. Erdos's conjecture for-

mulated as follows: "Let a , a , ..., a be n vectors in
l 2 n
Hilbert space, Main 2 1. Then the number of sums
29_ e.a., e. = :1, which fall in the interior of an arbi-
1-1 1 1 1

trary sphere of radius 1 does not exceed the binomial co-
eff1c1ent Cn,[n/2]°

Erdos's proof for the case where the ai's are real
numbers and E. Sperner's theorem which is used in this
proof comprises Chapter 1. Sperner's theorem states that,
"Any collection of subsets of a set S of order n cannot
have more than C elements, if for every pair of sub-

nr[n/2]

sets in the collection, neither is contained in the other.

Chapter 2 exhibits D. J. Kleitman's proof for the
case where the ai's are complex numbers and also his devel-
opment of a stronger form of Sperner's theorem which is
essential to the proof. A counterexample shows that an

extension of this stronger form of Sperner's theorem will

not prove the conjecture for the three-dimensional case.

Antonio Santiago Villanueva

Chapter 3 investigates the problem in three—
dimensional euclidean space. If the n vectors are re—
stricted within the boundaries of two arbitrary 60°-half

aperture cones, then [S] < C l' where [8] denotes the

n,[n/2
number of sums inside any unit sphere. For the general
case of k vectors lying outside the boundaries of a geo-
metrically determined pair of 60°-ha1f aperture cones, the
results are as follows:
1. If k 2 n/4, then [S] s Cn,[n/2]'
2. If 0 < k < n/4, then [S] c (/I73 +€3Cn,[n/2]' where
6+ 0 as n + co. (Exact values of .473 + E for any
such n are shown in Appendix II.)
A lemma derived in the process is the inequality,

n-k

l/2 2 C < C , n/4 4 k < n .

k,[k/2] n,[n/Z]

Kleitman's result for the d-dimensional case is as
follows: For n sufficiently large, [S] g Cn,[n/2]' Besides
an exposition, Chapter 4 includes corrections and completions
to portions of Kleitman's work. In particular, Appendix III
shows a proof of the inequality

2 (n /n)1/2 ‘ Chump]. {2 2% }
0t 0t a

n C
2 naplna/Z]

(where 2 na = n and n and na are positive integers), which
a
is used in a theorem. This proof needed deriving asymptotic

formulas for the function

 

I I
O
E"
E
to

g (m)

Antonio Santiago Villanueva

In Chapter 5, we reduce the hypothesis of Erdos's
conjecture to a normed linear space. A theorem proves it
is sufficient to consider only the cases where the number
of vectors n is odd. Results include the following:

1. For n S 7, the maximal case of Cn,[n/2] implies all
vectors lie inside a 60°-half aperture cone (as de-
fined in a normed linear space) centered about the
vector of smallest norm.

2. For 3 < n S 7, there exists only one unique position

for the max1mal number of pornts Cn,[n/2]'

The thesis includes a conjecture on the geometric distribu-

tion of these Cn,[n/2] pOlntS for any odd integer n. A re-

cursive type of formula follows. It checks numerically up
= . u ,

to C21'[21/2] 352716. A complete solution to Erdos s

conjecture may possibly be found using this approach.

ERDOS'S CONJECTURE ON THE DISTRIBUTION OF
THE SUMS Z? e.a. OF n VECTORS IN
1=l 1 1

d-DIMENSIONAL SPACE

BY

Antonio santiago Villanueva

A THESIS

Submitted to
Michigan State University
in partial fulfillment of the requirement
for the degree of

DOCTOR OF PHILOSOPHY
Department of Mathematics

1970

To Joan and Tommy

ACKNOWLEDGMENT

The author has been very fortunate to have had
Dr. Robert S. Spira as a thesis advisor. Dr. Spira has
shared his professional competence in mathematics by
conferring with the author during his doctorate studies.
He also has an untiring dedication to the academic im-
provement of his students and is a true representative
of the meaning of university professor. He is an inspi-

ration. My sincerest thanks.

iii

TABLE OF CONTENTS

INTRODUCTION I O I O O O O O D O I O O I O O O I 0

Chapter
1

APPENDIX I I I O O O O O O I O O O O I O O O O O O

SPERNER'S THEOREM AND THE ONE-DIMENSIONAL
CAS E O O I O O O O O O O O O O O O O O O

A STRONGER FORM OF SPERNER'S THEOREM AND
THE TWO-DIMENSIONAL CASE 0 o o o o o o 0

THE THREE-DIMENSIONAL CASE 0 o o o o o o 0

THE d-DIMENSIONAL CASE 0 o o o o o o o o o

ERDOS'S CONJECTURE IN'NORMED LINEAR
SPACES I O O C O O O O O O O O O O O O 0

APPENDIX II 0 O O O O O O O I O O O O O O O O O 0

APPENDIX III . . . . . . . . . . . . . . . . . . .

BIBLIOGRAPHY O O O O O O O O O O O O O O O O O O 0

iv

Page

14
26

40

62
69
72
79

107

INTRODUCT ION

The problem originated from a paper by Littlewood
and Offord [1], "On the number of real roots of a random
algebraic equation (III)"; this paper investigated the
number of zeros of a random algebraic equation within some
fixed circle. Littlewood and Offord proved the following
lemma: Let a1, a2,....,an be complex numbers with Iail 2 1.
Consider the sums {i=1 skak where 8k = :1. Then the number

of the sums [i=1 ekak which fall into a circle of radius r

is not greater than

n 1/2

or 2 (log n) n-

Erdos then considered the possibility of improving this
bound and even letting the ai's be vectors in Hilbert space.
He formulated with the following conjecture [2]: Let

a1, a2,....,an be n vectors in Hilbert space, Main 2 l.
which fall in the interior

Then the number of sums 2:: a

lekk
of an arbitrary sphere of radius 1 does not exceed Cn,[n/2].
For completeness, the thesis includes an exposition
of all previous results and auxiliary tools. The original
work includes development of exact estimates in the three-

dimensional case, the proof of a difficult inequality to

close a gap in a theorem of Kleitman, correction and

completion of other portions of Kleitman's work, and par-
tial results for the more general situation in normed
linear spaces.

Chapter 1 exhibits Erdos's proof [2] for the case
where the ai's are real numbers. A remark following the
proof shows the construction of an example where this
bound Cn,[n/2] is actually attained. Erdos's proof relies
on Sperner's theorem [3] which is also shown. Sperner's
theorem states that any collection of subsets of a finite
set of order n cannot have more than Cn,[n/2] elements if
for every pair of subsets in the collection, neither is
contained in the other.

Although Kleitman [4] and Katona [5] have given
separate proofs for the case where the ai are complex
numbers (the former of which comprises Chapter 2), they
are equivalent and both proofs rely on the development of
a stronger form of Sperner's theorem. Katona's version
[5] of this theorem is also equivalent to the one shown
in Chapter 2. This chapter ends with a counterexample
showing that an extension of this stronger form of Sperner's
theorem will not prove Erdos's conjecture for the three-
dimensional case.

Chapter 3 begins with the proof of the three-
dimensional case, the n vectors being restricted within
the region of two arbitrary 60°-half aperture cones. For

the general case, the least upper bound ultimately derived

is asymptotic tovWZ7§$ Cn,[n/2]. Appendix II gives exact
bounds for any such n vectors. It is worth noting a sec-
ondary result stated in lemma 3-3: For all non-negative

integers n and k,

n-k

1/2 2 C <

k.[k/21 Cn,[n/21

provided n/4 g k s n. Appendix I gives the exact relations
between these two terms for all k, 0 < k < n.

The contents of Chapter 4 can be summarized as fol-
lows: For any n vectors in a real space of finite dimension
d, the bound on the number of sums inside a unit d-sphere is
Cn,[n/2] provided n is sufficiently large. This chapter
constitutes a complete exposition of the proof as outlined
by Kleitman [4]. However the argument suggested by Kleitman

for the proof of the inequality

Cn,[n/2] n

2n

_7 2
C
0L nap[na/2]

 

{mm/MU2 s
(X

(where 2 na = n, and na and n are positive integers), is
not clegr. A proof of this inequality is given in Appen-
dix III.

A complete solutionto Erdos's conjecture may pos-
sibly be found by considering an entirely different approach
to the problem as initiated in Chapter 5. Only a normed

linear space need be considered instead of a Hilbert space.

It is shown that n may be taken odd. It is conjectured

that for n > 3 there exists only one unique position for

the maximal number of points C , inside an arbitrary
nr[n/2]

unit sphere. This has been proven for all n s 8. Al-

though it is possible to describe the geometric distribu-

tion of these points, formulating this rule for a general

value of n is difficult. The conjectured formula has been

checked numerically up to n = 21. 1.e. C21'[21/2] = 352716.

CHAPTER 1
SPERNER'S THEOREM AND THE ONE-DIMENSIONAL CASE

Let S be a set of n elements, n 2 l, and 2 any

collection of distinct subsets of S.

Definition 1-1. Define the order of a subset of S as its

number of elements.

Definition 1-2. Define the degree of 2 as its number of

subsets of S.

Definition 1-3. A collection 2 is called principal, if

 

for every pair of subsets in the collection, neither is

contained in the other.
Sperner's Theorem [3] can be stated as follows:

Theorem l-l. If E is a principal collection of subsets
of a set S of order n, then the degree of 2 is less than
or equal to Cn,[n/2]' Equality holds only under the fol-
lowing special cases:
1. For n even, 2 consists only of subsets of order n/2.
2. For n odd, 2 consists only of subsets of order
(n - l)/2, or 2 consists only of subsets of order

(n + l)/2.

To prove Sperner's Theorem we shall first establish the

following lemmas:

Lemma 1-1. A collection of m 2 1 distinct k order subsets
of a set S of n 2 1 elements possesses at least m + 1 dis-
tinct k - 1 order subsets provided k > (n + l)/2. This
assertion is true also in the case k = (n + l)/2 (for n

. < .
odd) prov1ded m Cn,[n/2]

Proof: Let 31' B ,..., Bm be a collection of k order sub-

2
sets of S. Each Bi' 1 S i s m possesses k distinct subsets

of order k - 1. Hence the collection possess m . k subsets

of order k - l, but now all are not necessarily distinct.

Let A1, A ,..., Ar be the distinct ones. For a

2

fixed 2 let t2 be the number of Bi sets, 1 < i < m, in

which A2 c:Bi. Note that an arbitrary k - 1 order subset
of S possesses n - (k - 1) distinct supersets of order k.

Therefore
t < n - k + 1
Hence
m - k = 2r t s r(n — k + l)
‘ 2:1 2

or

r > m k
’ n - k +.l

 

Assume k > (n + l)/2. This is equivalent to

k > n - k + l

or

 

From the above, it follows that r > m.

Assume k = (n + l)/2 and m < C In this

n,(n/21‘
case, we now have

or

 

and therefore r 2 m. Hence there are at least A1, A2,...,
Am distinct ones of order k - l. The minimal case r = m
can only occur if for any fixed 2, A2 is a subset of
n - k + 1 distinct Bi's.

We now show that there exists a k - 1 order subset

of S, A* which differs from all A1, A ,..., Am, and in

2

particular differs from some Aj’ l < j < m, in only one
element.

Let Ai be an arbitrary k - 1 order subset of S

which differs from all Al, A2,..., Am. There exists at
least one, since the number of k - 1 order subsets of S

equals

= C

Cn,k - l n,(n - l)/2 = Cn,[n/2] > m,

by hypothesis. Choose an A2 from the collection A1, A2,

..,Am such that Ai and A£ have a maximal number of common

elements p. If p = k - 2 then Ai = A*. If p < k - 2,

form a k - 1 order subset of S, A; by deleting an element
in Ai not belonging to A2 and substituting an element of

AI not belonging to Ai. Now A5 # Ai for any i, l < i < m,
since this would imply that Ai and Ai have k - 2 > p common

elements, contradicting the choice of A Clearly, the

2.
process terminates in a finite number of steps.

Now A* and Aj possess a common superset of order
k, say B'. If B' belongs to the collection B1, 82,..., Em
then clearly r > m. If not, then Aj is not a subset of
n - k + 1 distinct Bi's, i.e. the minimal case r = m does
not occur. Again r must be greater than m, proving the

lemma.

Analogously we can prove:

Lemma.1-2. A collection of m 2 1 distinct k order subsets
of a set S of n 2 1 elements possesses at least m + 1 dis-
tinct k + 1 order supersets provided k < (n - l)/2. This
assertion is true also in the case k = (n — l)/2 (for n

odd) prov1ded m < Cn,[n/2]'

An interesting problem would be to study more

exactly

f(m n k) _ min no. of k - 1 order subsets of m subsets
l I _ o
of k order of a set S of n elements.

Now we shall establish the

Proof of Theorem 1-1: If 2 is a collection of distinct
subsets of S of equal order k, then clearly 2 must be a
principal collection. If 2 consists of all the distinct
k order subsets of S, then 2 is a maximal principal col-
lection. Since, any other subset of S has order less
than k or greater than k, and clearly must be contained
in some k order subset or must contain some k order sub-
set respectively. Hence,

1. For n even, if 2 consists of distinct n/2 order

subsets, its degree has a maximal value equal to

Cnpn/Z = Cn,[n/2].

2. For n odd, if 2 consists of distinct (n - l)/2
order subsets or if 2 consists of distinct
(n - l)/2 order subsets, its degree has a maximal

value equal to

C = C

n,(n + 1)/2 n,(n - 1)/2 = Cn,[n/z].

There remains to show that every other principal

collection 2 has degree strictly less than Cn,[n/2]'

For the remaining cases we shall construct from 2

a series of principal collections

2 E 20, X1,............, 2r' r 2 l

10

with corresponding degrees

go<gl< 0......0.... ‘gr

(whereby in case r = l, g0 is always strictly less than
g1), such that 2r consists only of subsets of order n/2
if n is even or (n - l)/2 if n is odd.

Let m be the number of subsets in {0 of maximal
order k. If k > n/2 then lemma 1 applies since by hypo-
thesis m is less than Cn,[n/2]' Replacing these subsets
by p > m subsets of order k - l and forming a new collec-
tion 21 it is clear that 21 is again principal. If 21
contains all the distinct subsets of order (n + l)/2 then
construct 22,(r = 2), to contain all the distinct subsets
of order (n - l)/2. Proceeding as above, so long as the
maximal order occurring remains greater than n/2, we fin-
ally obtain 21 which therefore contains only subsets of
order less than or equal to n/2. Naturally, if k s n/2,
then 21 = X0.

Now let m' be the number of subsets in 22 of mini-
mal order k'. If k' < (n - l)/2 Lemma 2 applies. Replacing
these subsets by p' > m' supersets of order k' + l and
forming a new collection 22 + 1, it is clear 2% + 1 is
again principal. Proceeding as above, so long as the
minimal order occurring remains less than (n - l)/2, we

finally obtain Er which contains only n/2 order subsets if

n is even or (n - l)/2 order subsets if n is odd. Naturally

11

it is possible that £2 = Er’ but when by hypothesis r must
be greater than or equal to 1.

Therefore

deg X 5 9o < g1 ‘ gr ‘ Cn,[n/2]'
Therewith the theorem is proven.

ErdSS's conjecture for the one-dimensional case is

proven in [2],

Theorem 1-2: Let a1, a2,..., an be n 2 1 real numbers,

(ail 2 1. Then the number of sums

Z: = 1 Ekak' where 8k = :1,

which fall in the interior of an arbitrary interval I of

length 2 does not exceed Cn,[n/2]'

Proof: We can assume that all the ai are positive, because

a a there exists an e' = :1 such that

to every sum 2: = l k k k

Ekak E silakl, for k = l,2,.....,n,

and conversely.

Let S be the set of integers l to n. To each of
the 2n sums Z: = 1 ekak we shall correspond a subset A of
S such that k is an element of A if and only if 8k = +1.
This is a one-to-one correspondence since no two sums can
correspond to the same subset and S also contains 2n

subsets.

12

n n , .
If two sums 2k = l ekak and 2k==l ekak are both in
I, neither of the corresponding subsets A and A' can con-

tain the other, for otherwise their difference

I2:=l€kak ' 2E=1€fiakl = I 2 X ak l 2 2.

kéA-A' if ADA!
kEA'-A if A':>A

Hence the collection of subsets of S defined by the sums
Z: = l ekak which fall in the interior of I is a principal
collection.

Sperner's Theorem completes the proof.

Remark: Choose ai = l and n even. The number of distinct

choices of e for which the sum 2: = 0 (i.e., the

k = 1 ekak
number of distinct choices of ek such that there always
eXists exactly n/2 8k Wlth value + 1) equals Cn,[n/2]°
Hence the interval (-1, 1) contains Cn,[n/2] sums

2: = l ekak which shows that our theorem is best possible.

A similar result holds if we choose ai = l and n odd.

Corollary: Let r be any integer. Then the number of sums
2: = l ekak which fall in the interior of any interval of

length Zr 13 less than or equal to r Cn,[n/2]'
Proof: The proof is by induction on r.

For r = l, the theorem above clearly suffices.

13

Now consider an interval of length 2r as shown.

‘3‘ I? C'. ‘r'
L 2(r - 1) _L 2 J
r‘ ’I‘ 7|

By assumption, the number of sums 2: = l ekak which fall

in (a, b) is less than or equal to (r - l) Cn,[n/2]'

 

Suppose that [b, c) contains more than Cn,[n/2] sums. Let
c' be the farthest point in [b, c) defined by some such
sum. Then [b, c'] can be contained in an open interval of
length 2 and has more than Cn,[n/2] sums of the form

Zfi = 1 Ekak' This contradiction completes the proof.

CHAPTER 2

A STRONGER FORM OF SPERNER'S THEOREM AND

THE TWO-DIMENSIONAL CASE

To prove Erdos conjecture for the two-dimensional
case, we shall use a stronger form of Sperner's Theorem

[4] as follows:

Theorem 2-1. Let S be an n order non-empty set, X a col-
lection of subsets of S, and T an m order subset of S,

(0 s m s n). If there are no distinct A and B in X such
thatAaBandeitherA-BCTorA-BCS-Tthen the

degree of X is less than or equal to Cn,[n/2]°

The two lemmas following, will be used in the
proof of Theorem 2-1.
First let us establish some definitions which are

basic to our development.

Definition 2-1. If S is a non-empty n order set, define a
chain to be an (n + 1) element class of subsets of S that

is totally ordered by inclusion.

Each chain contains exactly one subset of S of

order j, for each j less than or equal to n.

14

15

Definition 2-2. A subset of a chain obtained by omitting
the chain's k smallest and k largest elements for 0 < k < n/2

will be called a subchain.

Thus a subchain contains n + l - 2k elements. The
smallest element is a subset of order k and the largest
element, a subset of order n - k. If n is even, subchains
will contain an odd number of elements and if n is odd
subchains will contain an even number of elements. Sub-

chains are non-empty.

Lemma 2-1. The class of all subsets of a finite set can
be expressed as the union of a collection of disjoint

subchains.
Proof: The proof will proceed by induction.

If S is a one element set, i.e. S = {a}, then the

set of all subsets of S form the subchain,

¢ <={a} .

Assume S is an n-order set and the Lemma holds for
all sets of order n - l or less. Let a be an element of S.
Then S - {a} has order n - l and hence the set of all sub-
sets of S — {a} can be expressed as the union of a collec-

tion of disjoint subchains

(1
. x.
UJ=1J

16

with each Xj (for l c j < a) a subchain of S - {a} .
Let the largest element of each Xj be denoted by

Lj' We claim that

. X. U {L. U {ai}
3 J J

%x U {a}|A e(xj - {Lj})-}

|.<
Ill

0-4
III

are subchains of S. It is clear that every element of Yj

or Ya + j is a subset of S and each Yj or Ya + j is totally
ordered by inclusion. If there are n - 2k elements in Xj,
the smallest element of Xj has order k, the largest has
order n - l — k. Therefore Yj contains n + l - 2k elements,

the smallest element has order k and the largest has order

n - k. Also Ya + j contains n - 2k - l = n + l - 2 (k + 1)

elements, the smallest element has order k + l and the larg-

est has order n - l — k = n - (k + 1). Thus Yj and Ya + j

are indeed subchains of S.
Since every subset of S is either a subset of
S - {a} or the addition of a to a subset of S - {a}, all
subsets of S are in the subchains given above.
Also, since the collection of subchains Xj of
S - {a} are disjoint, it is easily shown that the collec-

tion of subchains Yj and Ya are disjoint.

+ 3

This proves the Lemma.

For the following, we set C 0 for j < 0 or

nlj =

j > n, and Co 0 = 1. We have then for any j and any n 2 l,
I

17

C . = C

. + c
n.) n - 1.3

n- 1']. - l 0

Remark: The number of subchains containing q or more
elements, q 2 0, in a decomposition of the set of subsets

of S according to Lemma 2-1 is Cn,[(n + q)/2]°

Proof: For q > n + l, the result is clear.
If n + q - l is even, the number of subsets of S

having order (n + q - 1)/2 is

Cn,(n + q - l)/2 = Cn,[(n + q)/2]'

By Lemma 2-1, each such subset lies in one and only one
subchain in a decomposition of the set of subsets of S

into disjoint subchains. Note that if a subchain contains
j elements, its largest element has order (n + j - l)/2.
Hence every subchain of length q or greater contains an
element whose order is (n + q - l)/2. Therefore the number
of subchains containing q or more elements is Cn,[(n + q)/2]°
If n + q - l is not even, then n + q is. Similarly

as above, the number of subchains containing q + l or more

elements is

= c

Cn,[(n + q + 1)/2] n,[(n + q)/2]'

Note that in this case there does not exist a subchain con-
taining q elements since this would imply n + q - l is
even. This terminates the proof.

The second lemma is due to Erdos [2].

18

Lemma 2-2. Let X1, X2,..., Xq, q 2 1, be disjoint collec-
tions of subsets of S with the property that Xj is principal,
for j = l, 2,..., q. The number of elements in

q
\)j = 1 xj

is less than or equal to

q
23' = 1 Cn,[(n + j)/2]

Proof: As in Lemma 2-l, let M1’ M2,..., Ma be a collection
of disjoint subchains whose union is the class of all sub-
sets of S. The number of elements in the union of the X's
which lie in any subchain Mg is less than or equal to q
since if greater than q, then some Xj contains at least

two elements of M2 and this contradicts the hypothesis

that Xj is principal for j = l, 2,..., q.

Thus with

we have

[Y1 = [j = 1 [y n Mi] s 2% =1 min. (q,[M£])

where [Z] indicates the number of elements in Z.
Since the number of elements in any subchain M2 is between
1 and n + l we equivalently have

n + 1

[Y] = 2r = 1 Z: = 1 min. (q,r) . 6[M2],r '

19

From the remark above, the number of subchains

containing r elements is

Cn,[(n + r)/2] ‘ Cn,[(n + r + 1)/2] '

Therefore,

n+1 .
[Y] s Zr=1 min. (q'r)§§n,[(n+r)/2] - Cn,[(n+r+l)/2£}
min. (q'l){%n,[(n+l)/2] - Cn,[(n+2)/2]

min. (q'2){%n,[(n+2)/2] - Cn,[(n+3)/2] + .............

- min. (q,0)} + Cn’[(n+2)/2] {“1110 ((1,2) - min. (qll)}l

+ ............. + Cn,[(n+n+l)/2]{%in' (q,n+l) - min. (q,n{}

= 22:1 Cn,[(n+r)/2]{%in. (q,r) - min. (q,r-Ii} .

Note that

1 if r é q
min. (q,r) - min. (q,r - l) =
0 if r > q

Hence

[Y] s [q c

r = l n,[(n + r)/2] °

A trivial argument shows that X , X ,..., X need not be
1 2 q
disjoint.

Now we shall establish the

20

Proof of Theorem 2-1: As in Lemma 2-1, let all the sub-
sets of T be expressed as the union of a collection of

disjoint subchains. For each D c=IT, let XD denote the

set of subsets B of S - T such that DUBEX. If B and B'

both belong to X such thatI3::B5 then BUD:B'UD and BUD -

D
B'UDc:S - T, and this contradicts the hypothesis for the

elements of X. Therefore X is principal. Consider the

D
set XD , XD ,..., XD formed by a k element subchain
l 2 k
Dichca..ch in the above decomposition of T. If B belongs

to both XD and XD where D. i D., then BU D. :> BU D. and
i j 1 j 1 j
BUDi -BLJDjC=T, and this also contradicts the hypothesis

for the elements of X. Therefore x , X ,.., x

are
D1 D2

Dk

disjoint.
By Lemma 2-2, the number of elements in

k
Uj = 1 xDj

is less than or equal to

k
2r = l Cn - m,[(n - m + r)/2] ,

and this is clearly a bound for the total number of ele-
ments of X whose intersection with T lies in a k element
subchain in the decomposition of T.

Therefore the total number of elements in X, by

the remark above, must be less than or equal to

21

m+l k
Zk=l Zr=l C:n-m, [ (n-m+r)/2] {Cm [ (m+k)/2] - Cm, [ (m+k+1)/2]}

- C

= Cn-m,[(n-m+l)/2]{Cm,[(m+l)/2] m,[(m+2)/2]}

+

{Cn-m; [ (n-m+l)/2] + C:n-m, [ (n-m+2)/2]} {Cm' [ (m+2)/2]

- C + ....... +

m,[(m+3)/2]} §Cn-m,[(n-m+l)/2] + ......

- 0

+

Cn-m, [ (n-m+m+l)/2]} {C111, [ (m+m+l)/2]

= Cn-m[(n-m+l)/2] Cm,[(m+l)/2] + Cn-m,[(n-m+2)/2] Cm,[(m+2)/2]

+ ........ + C C

n-m[(n-m+(m+l))/2] m,[(m+(m+l))/2]

= Em‘f'l C

r=l n-m,[(n-m+r)/2] m,[(m+r)/2]

By induction on m, we shall show that

m+l

r=l n-m,[(n-m+r)/2] 0 S m < n -

C = C

m.[(m+r>/2] n,[n/Zl’

For m = 0,

C C

n.[<n+1)/21 o.[1/21 = Cn,[<n+1>/21 = Cmin/21 '

and a similar verification can be carried out for other small

m. Assume that if k < m,

k+l _
Zr=1 Cn—k.[(n-k+r)/21 Ck,[(k+r)/2] ‘ Cn,[n/2]

22

Then

m+l
Zr=l Cn-m,[(n-m+r)/2] Cm,[(m+r)/2]

2111+].

=1 Cn-m.[(n-m+r)/2]{Sm-1,[(m+r)/21 +

Cm-l , [ (m+r-2)/2 ]}

_ m+l
- Xr=l Cn-m,[(n-m+r)/2] Cm-1,[(m+r)/2]

m-l

+ r=-l Cn-m.[(n-m+r+2)/2] Cm-1,[(m+r)/2]

= C C + C

n-m,[(n-m+m+l)/2] m-l,[(m+m+l)/2] n-m,[n/2] Cm-l,m

m—l C C
r=l n—m+l,[(n-m+r+2)/2] m-l,[(m+r)/2]

Cn-m,[(n-m+1)/2] Cm-1,[(m-1)/21*'Cn-m.[(n-m+2)/2]Cin-1,[m/2]°
Note that

C C

Cn-m,[(n-m+l)/2] m-l,[(m-l)/2] = Cn-m,[(n-m)/2] m-l,[m/2]'

Hence

C

Cn-m,[(n—m+1)/2] m-1,[(m-1)/2]+'Cn-m.[(n-m+2)/2]chr1,[m/2]

= Cn-m+1,[(n-m+2)/2] Cm-1,[m/2]

C

= Cn- (m—l) . [ (n- (m-1)+1)/2] m'lv [ ( (WU-1V2]

23

Thus

m+l

r=l Cn-m,[(n-m+r)/2] C

m,[(m+r)/2]

= {m c c
r=l n-(m-l),[(n-(m—l)+r)/2] m-l,[«mrl)+r)/2]

Cn,[n/Zl ‘

Erdos's conjecture for the two-dimensional case is

proven in [4].

Theorem 2-2. Let a1, a2,....,an be n complex numbers of
magnitude greater than or equal to unity, n 2 1. Then the

number of sums of the form

8k = :1)

n
2k = 1 Ekak (

which lie in the interior of any circle of unit radius in

the complex plane is less than or equal to the binomial

coeffic1ent Cn,[n/2]'

Proof: For n finite, we can assume that |Im a # 0 for

kl
all ak since a rotation of the axes by half the smallest
non-zero angle subtended by some aj with the real axis
will validate this assumption.

Let S be the set of integers l to n. To each of
the 2n sums Z: = l Ekak we shall make correspond a subset

A of S such that k is an element of A if and only if

Im ekak > 0. This is a one-to-one correspondence because

24

if Im skak > 0 then Im -ekak < 0

or

a > 0 .

if Im a a < 0 then Im k

kk -€k

Denote by X the collection of all subsets A of S for which
the corresponding sum 2E = l skak lies in the interior of
a fixed unit circle. Define T to be a subset of S such
that j is an element of T if and only if aj lies in the

first or third quadrant; that is

either Re aj 2 0 and Im aj > 0

or Re aj < O and Im a. < 0

Note that the sum of two or more vectors lying in
the same quadrant of magnitudes greater than or equal to
s is also a vector in that quadrant with magnitude greater
than 3.

Suppose A and B are elements of X such that A1:> B.

If A - B CIT then the difference of their corresponding sums

| Z (s. -€!)a.

lin _ e a - n _ e'a I
k - l k k 2k — l k k jeA-B j j j

= I2 e.a.l 2 2
je§_B J J I

since each ejaj, jéA-B, lies in the first quadrant. This
implies the corresponding sums X: = 1 ekak and 2: = 1 efiak
both cannot lie in the interior of a fixed unit circle;
that is, A and B both cannot belong to X. Similarly if

A - B CIS - T then A and B both cannot belong to X.

25
Theorem 2-1 terminates the proof.

We shall show that it is not possible to prove
Erdos's conjecture for the n-dimensional case in the same
way as for n = 2 by a generalization of Theorem 2-1. See
also [5].

Analogously, "Let S be an n order non-empty set
with subsets T1 and T whose orders are ml and m2 respec-

2

tively (0 s m1, m S n). Assume X is a collection of sub-

2
sets of S such that there are no distinct A and B in X

withADBandeitherA-BCT orA-BCT or

1 2
A - B<= S - T1 - T2." We shall show that X can be greater
than Cn,[n/2]'
Consider the example S = {123} with subsets
T1 = {l} and T2 = {2} . The collection

X = ¢,{12},{13},{23} ,

clearly satisfies the above conditions yet the degree of

X is greater than 3.

CHAPTER 3

THE THREE-DIMENSIONAL CASE

We formulate this property for real inner product

spaces.

Definition 3—1. A 60°-ha1f aperture cone around the vector

 

b is the set of all vectors x satisfying

1 ‘ (x,b)
2 leflbl '

Lemma 3-l. Let the vectors x and y satisfy HI 2 s 2 0,
lyl 2 s 2 O and lie in a 60°-half aperture cone. Then

IDc+-yn 2 s and x + y lies in this cone.

Proof: Let the cone be determined by b. We have

 

 

le b ) IX!

X + b x b
= — + J’—
IX + Y! ' l5!) (IXI ' Ibl IX + YI (IYI ' IBI IX + YI

 

[I [xi + My!
’ 2 Ix + yl

 

1
2?.

So x + y is in the cone. Also, adding the inequalities

 

b l .
y , WET) 2 5- Iyl we obtain

 

b l
2hr“) 2 }- “Xfl ,

__1 1 1 1 b
Sfi§S+§S<§nXI+EHYI‘(X+Y,rB-r)

26

27

SO

llbll

s < x + y , W%F)' < [X + yI “BF.= "x + Y" .

 

The following theorem is a direct consequence of

Theorem 2-1.

Theorem 3-1. Let a1, a2,...., an be n vectors in three-
space, n 2 l, of magnitude greater than or equal to unity
and lying in four particular 60°-half aperture cones which
are pairwise symmetric through the origin. Then the

number of sums of the form

which lie in the interior of any sphere of unit radius is

less than or equal to the binomial coeffic1ent Cn,[n/2]'

Proof: Let S be a set of integers l to n. Define T to
be a subset of S such that j is an element of T if and

only if aj lies in the first 60°-half aperture cone C1+

or in its reflection with respect to the origin C1 , where
4. _

solely in the second pair of 60°-ha1f aperture cones, i.e.

If T # S, the rest of the vectors lie

. n n
in C2 - C1. To each of the 2 sums 2k = 1 ekak we make
correspond a subset A of S such that k is an element of A
if and only if

. . +
k e T and ekak lies in C1

28
or

. . +
k.e S - T and skak lies in C2 .

This is a one-to-one correspondence since if kEET either

. . + . . - .
ekak lies in C1 or ekak lies in C1 and 1f kELS - T

. . + . . -
kak lies in C2 or skak lies in C2 . Denote by X
the collection of all subsets A of S for which the cor-

either a

responding sum 2: = 1 Ekak lies in the interior of a fixed
unit Sphere.

Note that the sum of two vectors of magnitudes
greater than or equal to s, lying in the same 60°-half
aperture cone, is also a vector in that cone with magnitude
greater than or equal to s by lemma 3-1.

Suppose A and B are elements of X such that A # B
and A23 B. If A - B C=T, then the difference of their cor-

responding sums

l2“ _ 8 a - Zn _ e'a I = I 2 (e. - e!) a.
k—lkk k—lkk jam] 3 3
=I 2 s.a.I 2 2
jeA-B 3 3

since each ejaj, jEA-B lies in C1+. This implies the
corresponding sums Z: = l ekak and 2: = l ekak both cannot
lie in the interior of a fixed unit sphere; that is, A and
B both cannot belong to X. Similarly if A - B C=S - T

then A and B both cannot belong to X.

Theorem 2-1 terminates the proof.

29

Remark: If a set of n vectors a1, a2,....., an in three
space is such that any pair of vectors defines an angle
which is either less than or equal to 60° or greater than
or equal to 120°, then this set can be enclosed in two
60°-half aperture cones which are pairwise symmetric

through the origin.

Proof: This is clear if we let the axes of these cones
coincide with any vector from this set, say ai. Since if
6 is the angle defined by an arbitrary vector ak with ai
either 0° < 6 < 60° or 120° < 9 < 180°.

we now wish to find upper bounds for the number of
sums of the form

2: = 1 ekak , 8k = :1 and IakI 2 l ,

which lie in the interior of any unit sphere, where
a1, a2, ....., an cannot be enclosed in four such cones as
defined in Theorem 3-1. Thus, n > 4.
For n < 8, we claim that this bound is still
C . ' d f' d b
n,[n/2] Assume there exists an angle 6 e ine y one

0

pair of vectors, say ai and aj such that 60° < e < 120°;
otherwise the Remark above terminates our proof. If S is
the unit sphere in question whose center is e, consider
other unit spheres centered about e ‘1 Zai , e i 2aj, and

e i 2a. i 2a.. Define
1 J

30

a = max (2IaiI , 2IajI)
b=min (2IaiI , 2IajI)
0 = min (0 , 180 - 0)

The smallest distance between centers of these unit

spheres is equal to b;

 

6 7
Figure 1

because

 

 

/Q' + b2 - 2ab cos ¢ > /Q2 + b2 - 2ab cos 60°

= Vaz + b2 - ab 2 b .

 

Hence they cannot overlap. To each sum 2: = 1 ekak lying
inside S, we make correspond three others lying inside unit
spheres centered about three of e i Zai, e i 2aj, e: Zait 2a. by
inverting the signs of Si, ej and both. It is also clear

that no two distinct sums lying inside S can correspond to

31

the same sum lying inside any of the others. Therefore at

most only one-fourth of the total number of sums

n . . . . .
2k = l Ekak can lie in S itself. The inequality

n - 2

2 < Cn,[n/2] , for n < 8 ,

completes the proof.

The following theorem is another special case of

Erd6's conjecture in three-space.

Theorem 3-2. Let a1, a2,...., an be n vectors in three-
space of magnitude greater than or equal to unity. Assume
there exists at least k vectors, k 2 n/4, having n-compo~
nents greater than or equal to l/2 in magnitude where

n = a. x aj (where ai and aj define an angle 9 between 60°

1
and 120°). Then the number of sums of the form

I: = 1 €kak (8k = *1)
which lie in the interior of any unit sphere is less than

or equal to Cn,[n/2]°

To prove this theorem we shall first establish the

following lemmas:

Lemma 3-2. For all non-negative integers n divisible by 8,

- n/4

1/2 2n c < c

n/4,n/8 n,n/2

32

Proof: Let n = 8m and define the positive function

C
f(m) = 8%I'n4m I m=0’l,.......

1/2 2 C

 

2m,m

In order to show f(m) is monotone decreasing we

shall prove f(m + 1) < f(m). But note that

C8(m + 1), 4(m + 1)

 

 

 

 

 

 

 

 

f(m + l) =
6(m + 1)
1/2 2 C2(m + l), m + l
[8(m + 1)]!
= {[4<m + 1)::12
1/2 26(m + 1) 12(m + II];
[(m + l)!]
(8m+8)(8m+7)......(8m+l) (8m)!
[(4m + 4)(4m + 3)......(4m + 1)]2 [MIN]2 = kfm),
6(m + 1) (2m + 2)(2m + 1) (2m)!
1/2 2
(m+l)7 (ml?
where

(8m + 8)(8m + 7)......(8m + 1)
[(4m + 4)(4m + 3)......(4m + 1)]2

 

 

 

K = 26 (2m + 2)(2m + l)
(m+ 1)2
Hence it suffices to show
K < 1.

If we assume the contrary, i.e. K 2 l, we have

33

(8m+8)(8m+7)......(8m+1) >26(2m+2)(2m+1)
[(4m + 4)..............(4m + 1)]2 (m + 1)2

 

or

(8m + 7)(8m + 6)(8m + 5)(8m + 3)(8m + 2)(8m + l) 3 1
[(8m + 6)(8m + 4)(8m + 2)]2

or

(8m + 7)(8m + 3)] |18m + 5)(8m + 1) a 1
(am + 6)78m + I) [j8m + 4)(8m + 2)

and expanding
2 . 2
64m + 80m + 21 64m + 48m + 5

2 2 3 1
64m + 80m + 24 64m + 48m + 8

 

 

which is impossible for m a 0.
Since the function f(m) is positive monotone de-
creasing, it converges to a limit a i.e. 21m f(m) = a.

m+oo

To find a, we shall make use of Stirling's formula [6]

 

 

 

iim k! = 1
k*” /§FE kke-k
Thus,
(8m)!
£im f, ) = £im C8mL4m = 21m [(4m!]
m+00 m+00 1/2 26m C m+w 1/2 26m (2m)!

2m,m (m1):

34

 

 

 

 

 

2
(8m)! (V2n1m(4m)4me-4m) ( 28m
= Rim V2w8m(8m)8me—8m (4m)! Z/fifi _ l
mew 2 - '
6m (2m)! /2nm mme"m 221“
1/2 2 2m -2m “"
V21r2m(2m) e m! fir—m

Consequently for m = 0, l, ...

 

C
f(m) = 23'4m > 1 ,
1/2 2 C2m,m
and therefore
6m
1/2 2 C2m,m < C8m,4m '

Lemma 3-3. For all non-negative integers n and k,

1/2 2n ' k c < C

k,[k/2] n,[n/Zl

provided n/4 s k < n.

Proof: The following proof repeatedly makes use of the

relation that

+ Cr,[r/2] + 1

2Cr.[r/2] Cr.[r/2]

\V

= Cr + l,[r/2] + 1

= Cr + l,[(r + 1)/2] ,

for all non-negative integers r and equality holds if r is

odd.

35

. . , n - k
Firstly, this relation shows that 2 Ck,[k/2]

is monotone non-increasing as k increases. Thus it suf—
fices to prove the above inequality using the smallest in-

teger E which is greater than or equal to n/4. Let

n E 0 (mod 8), n 2 8

E5 = -[— l£_&_il] , j = o,1,....,7.

For n = 0, the result follows by computation.

We shall show that

-j)-k'.

(n
1/2 2 3 CE5,(E5/2] < Cn - j.[(n - j)/21

for j = 0,1,...,7.
Lemma 3-2 terminates the proof for j = 0.

Note that for j = 1, 2, 3

E5 = -[- ifl—i—ill = n/4 .

Using the above relation we have

2C C

n - l,[(n - 1)/2] 3 n,[n/2] '

Therefore

> >1/22(n-1) ‘n/4

Cn - 1.[<n - 1)/21 ’

1/2

Cn,(n/21 Cn/4.[n/81°

The proofs for j = 2, 3 now follow easily.

36

— _ (n - ') _
kj — -[— ———z—1—J — n/4 - 1 .

Again using the above relation we have

2C 2 C

n - 4,[(n - 4)/2] n - 3,[(n - 3)/2]

and since n/4 - 1 is odd,

2Cn/4 - 1.1(n/4-11/21 = Cn/4,[n/81 °

Therefore

2 1/2 c > 2(n‘4)'n/4

Cn—4,[<n—4>/21 n-3,[(n-3)/2] Cn/4.[n/8]

(n-4)-(n/4-1)

= 1/2 2 C

n/4-1,[(n/4-1)/2] .

The proofs for j = 5, 6, 7 again follow easily.

Now we shall establish the

Proof of Theorem 3-2: By hypothesis let the vectors ai and
aj define an included angle a, 60° < 6 < 120° such that
there exist k 2 n/4 vectors having n-components greater
than or equal to 1/2 in magnitude.

Let S be the unit sphere in question. It has been
previously shown that to each sum 2: = 1 ekak lying inside
S, we can always construct three new sums lying inside unit
spheres centered about three of e i Zai, e i Zaj, e i 2ai
t 2aj. Moreover, none of these spheres overlap. Conse-

quently at most only one-fourth of the sums that lie in a

37

hyperplane sheet containing S normal to n of thickness 2
can lie in S itself.

For each choice of epsilons for those vectors not
included in the set of k vectors having n-components
greater than or equal to 1/2, there can be at most
2Ck,[k/2] sums of the form 2: = 1.8kak lying inside this
hyperplane sheet. This is proven by the corollary to
Theorem 1-2 [2], applied to the projections along the
n-axis. The total number of sums lying inside this sheet
must therefore be less than or equal to 2Ck,[k/2] . 2n - k.

Hence the number of sums that can lie inside S itself is

less than or equal to

n - k
1/2 2 Ck.[k/21 < Cn,[n/zl

by an application of Lemma 3-3.

Finally consider the general case of n vectors in
three space of magnitude greater than or equal to one and
cannot be enclosed in four such cones as defined in
Theorem 3-1. This implies that there exists at least one
pair of vectors defining a plane P and an included angle
6 such that 60° < 6 < 120°. Construct two 60°-half aper—
ture cones which are pairwise symmetric through the origin
and with axis lying in the plane P. Construct two other
60°-half aperture cones similarly and whose axis now is
at right angles to the axis of the previous two cones con-

structed. See figure 2.

38

~O°-half aperture
cones

41mg

 

 

 

 

 

Plane "P"

Figure 2

If n is the normal to the plane P, it is easy to
prove geometrically that every vector outside the boundaries
of these four cones makes an angle less than 45° with n and
therefore have n-components greater than 1/2. If k is the
number of such vectors and k 2 n/4, Theorem 3-2 bounds the
number of sums 2: = 1 ekak lying inside any unit sphere to

C . .
n,[n/4] For the general case we can now establish

39

Theorem 3-3. Let a1, a2,...,an be n vectors in three-space
of magnitude greater than or equal to one. Then the number

of sums of the form

which lie in the interior of any unit sphere is less than

or equal to

k
2 Cn - k.[(n - k)/21

for some integer O < k < n/4.
If n E 0 (mod 8), a complete derivation in Appen-

dix II shows that

k 3n + 4

3114-9

2 4/3n

 

 

Cn - k,[(n - k)/2] < “373 e Cn,[n/2]°

. . k
Similar upper bounds for 2 Cn _ k,[(n _ k)/2]’ 0 < k < n/4,
if n E j (mod 8), j = 1, 2,..,7, are also shown in Appendix
II.
Therefore, givenei > 0, if n is sufficiently large,

we have

k

2 Cn - k.[(n - k)/21 ‘ ("Z73 +e’ Cn,[n/21' °<'k< “/4°

CHAPTER 4
THE d-DIMENSIONAL CASE

Analogous to Theorem 3-1 we can establish the fol-
lowing theorem, the proof of which follows the same

argument.

Theorem 4—1. Let a1, a2,.....,an be n vectors in a real
Hilbert space such that flail ; l, i = l, 2,..,n. Assume
they lie in four particular 60°half aperture cones which
are pairwise symmetric through the origin. Then at most

Cn,[n/2] sums of the form

2? - 1 Eiai (81 = :1)

can lie in the interior of any sphere of radius 1.

Also, it can be shown as in Chapter III, that any
arrangement of these n vectors in a real Hilbert space
satisfies Erdos's conjecture of C if n s 8. For

n![n/2]
any n vectors in a real space of finite dimension d, we
shall show that the bound on the number of sums inside a
unit d-sphere is still C for sufficiently large
nr[n/2]

n [4].

40

41

Lemma 4-1. Let S be ann order non-empty set, X, Y, Z dis-
joint collections of subsets of S with the property that
if A e X, B ::A then B 6 Y, and if A.e X, C c:A, then

C E Z; then

c
[X]<—n-!—[%L2-L[XUYUZ]
2

where [X] represents the number of elements of X.

Proof: For a given X, assume the smallest collections of
Y and Z. That is, B 5 Y if there exists an A E ‘X such
that B 2 A and C 6 Z if there exists an A E X such that
C c A. Therefore 32 E Y if B2 :2 B1, Ble Y and C2 6 Z if

c cc1,c ez.

2 1

Let n(j, X), n(j, Y), n(j, Z) represent the number
of elements of X, Y and Z respectively which contain
exactly j elements of S. If A is a k order element of x
or Y, there exists n - k distinct k + 1 order supersets of
A belonging to Y. Each k + 1 order element of Y contains
k + l subsets of order k, hence k + 1 represents the maxi-
mal number of times such an element of Y can be formed.

Since X and Y are disjoint, the following relation holds:
n - k
n(k + 1, Y) 3 m (n(k, X) + n(k, Y))

n - k
E+I

n - k

mn‘k'x’+ n-(k-l)

2 n(k - l, X)

 

 

 

 

 

 

 

42

 

 

 

 

 

n - k n - (k - l) n
+oooooo+m k ) 0.00.00. 1'11(0,X)
k 0 I I
= ._ n(j,X) (n-j)!j! _
23‘0 (n - (k+l))!(k+l)! ' 0 ‘ k ‘ n 1‘

Similarly, if A is a k order element of X or Z, there exists
k distinct k - 1 order subsets of A belonging to Z. Each

k - 1 order element of Z contains n - (k - l) supersets of
order k, hence n - (k - 1) represents the maximal number of
times such an element of Z can be formed. Since X and Z

are disjoint the following relation holds:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

n(k-1,2) 2 n _ §k_1) (n(k,X) + n(k,Z))
2 n _ Tk-I) n(k,X) + n -k(k-I) fiéfi~n(k+1,x)
+......+ n _k(k_17. ii: ...... % n(n,X)
= Z§=k n(j,X) (n _(?;215?1k_1y1 , 1 c k < n.

Since Y and Z were chosen minimal, then clearly for any
disjoint collections X, Y, Z satisfying the given hypo-
thesis, the above relations also hold.

For X, Y, Z disjoint, summing these relations over

k yields,

[XUYUZ] = 2:=O(n(k,X) + n(k,Y) + n(k,Z))

43
=n(o,,-,kX)+n(0Y)+n(oz)+Z; H;n(kx)+21n(k,Y)
+ 2:;in(k,2) + n(n,X) + n(n,Y) + n(n,Z)
n(0,x) + n(0,Y) + n(O,Z) + 2:;in(k,x

+ 2:32 31“” “fly-1% + 2:- =1 Zk+1n‘j'x"(—%n%r

+ n(n,X) + n(n,Y) + n(n,Z)

2:;1 2;:0n(j,X)%%Eg%Tfié-+ n(n,X)gi:i
+ 29;3n<j.x>+L<na';* '1

= 2k= —0 Zn 3:0“j x’éfiiiiifiT'

N

)(n-k) 1k!
(II-ES “E!

\V

+

n n! n . (n-')!“!
= Zk=0 THIETTET zj=on(3'x""%T‘l—

2n zg=0n(j,X)/Cn'n.
J

from which we obtain

[X] = {13:01.1(3. ,X) = Cn'[n/2] erl=on(jIX)/Cn'[n/2]

A

n .
Cn,[n/zl Zj=0“‘3'x’/Cntnj

n [x U Y U Z]

A

Cn.[n/21/2

44

The result if most vectors lie essentially in one

single direction is

Theorem 4-2. Let a1,a2,......,an be n vectors in a real
Hilbert space such that naifl 2 l, i = l, 2,...n. Assume
there exists an vectors, a 2 5/8, lying in a cone C of
half aperture 6 where 9 is determined by condition (I)

0 0

below. Then at most C sums of the form

n,[n/2]

n —
2i = 1 8131 (81 ‘ i1)

can lie in the interior of any sphere of radius 1.

We remark that Kleitman's statement of this theorem
is a little vague, and that he states it for any Hilbert
space. He also gives a > 9/16, but only obtains his result

for n sufficiently large.

Proof: Let the cone center be in the direction of the
unit vector v0.

At least one vector ak must lie outside 60°-half
aperture cones which are pairwise symmetric through the
origin and centered about v0 or Theorem 4-1 terminates the

proof. Using Gram-Schmidt orthogonalization, define

v _ ak - (ak’vo)vo
l ‘ uak - (ak,vo)vou '

 

Therefore ak may be written as

45

W
W
I
3?
§_
§‘
0
<
+
X
H
<
H

where

lth 2 l , <v£,vm) = 6 , x + xi = 1, |x0| < 1/2 .

Moreover at least one vector aj must lie outside the cones
of 60° half angle centered about v0 and similar ones cen-
tered about v1 or Theorem 4-l terminates the proof. As

above, define

;aj - (aj,vl)vl — (aj,vo)vo;
Haj - (aj,vl)vl - (aj,vo)vdfl

 

Therefore aj may be written as

aj = Ihjn<yovo + ylv1 + y2v2>

where

2 2 '
Haj" 3 1: (VZ'Vm) = 62’1“! zi=0yi = 1! IYOI< 1/21 lyll < 1/2 .

Any of the vectors ap lying in the cone C can be

written in the same notation. i.e.,

m
ll

Hapll(zovo + zlvl + 22v2 + 23pv3p)

Hap"(cos epvo + Elp sin epvl + 62p Sln epv2

+ sin 6 v
83p p

46

where
sip = zi/sin 6p , i = 1,2,3 , if 0 < 6p < 60 ,
or
61p = l , 62p = 63p = 0 , if 6p = 0 ;
i=1 sip = 1 , Hap” 2 1 .

Consider the hyperplane whose normal is
n E X1Y2Vo - xoyzvl + (Xoyl - xlyo)V2

The scalar products

(ak,”) “ak” (Xoxiyz ’ Xoxly2) = 0

(a-In)

J Haj“ (xlyoy2 - xoyly2 + XOY1Y2 - xlyoyz) = 0

imply this hyperplane contains the vectors ak and aj. The
magnitude of the scalar product of this normal with any

vector in C satisfies

I(ap,n)| 2 ley2 cos epl - Ixoyze1p Sln 6p

- onyl - xlyo)€2p Sln 6p] .

47

But

 

_/_2'_ __2_2
lxly2 cos 6 | — 1 xo /1 y0 y1 cos %>

V

(/§72)(l//2) cos 60

> .612 cos 6 .
0

Therefore we can choose a real angle 90 such that this
magnitude |(ap'n)| is always greater than or equal to 1/2.
Let S be the sphere of radius 1 in question and let
e be its center. To each sum 22 = 1 eiai lying inside S,
we can make correspond three others lying in unit spheres
centered about three of e i Zaj, e i Zak, e i Zaj i 2ak by
inverting the signs of ej, 6k, and both.
The magnitude of the cosine of the angle defined
by aj and ak,

[(aj'ak)|
"ajflflak"

 

Ixoyo + lell

 

‘ 2
1/2 Ixol + A- |xo|

A

 

 

< 1+/'3'
'_—_I_-

. /r_ 2 . .
Since the least upper bound of Ixol + - Ixol in the in-
terval 0 s Ixo| < 1/2 occurs at Ixol = l/2.

Suppose
|(a.,a )l
3 k < 1/2 .

 

Ilajlrnaklr

48

Using the same arguments as in Chapter III, we can conclude
that these unit spheres cannot overlap and consequently at
most only one-fourth of the total number of sums that lie
in a hyperplane sheet containing S normal to n of thickness
2 can lie in S itself.

By hypothesis at least an of the n vectors lie

within C and they have components

normal to this hyperplane because “n" < 1. Indeed if we

assume that "n“ > 1, then

2 2 -
IXIYZI + IXOYZ' + lxoyl " xlyol > 1
or
2 2 2 2
lxoyll + leoylxlyol + lxlyol > lxoyl - xlyol > lyol
2
+ lyll
or
o> Ixy |2-2lx le l+ Ix |2= <|x I- Ixy |>2
o o oyo 1Y1 1Y1 oyo 1 1

which is impossible.
As in the proof of Theorem 3-2, the total number

of sums lying inside this sheet must therefore be less

than or equal to 2 . 2n - an Hence the number

Can,[om/2]°

49

of sums that can lie in the interior of S itself is less

than or equal to

1/2 2n ' “n c for a 3 1/4 ,

GnI[Gn/2] < Cnr[n/2] '

by an application of Lemma 3-3.

Suppose

|(a"ak)l 1 + J?
1 2 r J .
/ ‘ Ilajnnakn < ‘T

 

Then the spheres can overlap. We divide the sphere S into
an overlap region S1 and a non-overlap region 82. Maximum
overlapping occurs when the distance between the unit

spheres is a minimum. Define

a max. (2“aj“ r Zflakfl)

min. (zuaju . zuakn>

. o _
min. (ej,k , 180 ejk)

 

Figure 3

50

We wish to show that

 

 

Jg§+ b2 - 2ab cos ¢ > Jab: - becos ¢

For a E b, this is trivial. If a > b, let k = a/b > 1 and

assume
kzb2 + b2 - 2kb2 cos o < 2b2 — 2b2 cos ¢ ,
Then
(k2 - 1) < 2(k - 1) cos ¢ .
Hence,

2 < k + 1 < 2 cos ¢ < 2

which is impossible. It is then clear that

 

 

/az +'b2 - 2ab cos (b 22/2 - ((1 + 5V2) ,

and the dimension of the overlap region normal to the

hyperplane sheet is less than

 

 

2 /1 - (2 - ((1 + /§)/2)) = /?73 - 1)/2 .
For small 6 ,

O
|ny2 cos epl > (/:/2)(1//7) cos 90 > /(/§L1)/2 .

Therefore for any vector in C, 60 can be chosen to satisfy

the following condition (I):

51

|(a n)|

-——J%hr—— 2 /(/3 - 1)/2

Using Theorem 1-2, the number of sums lying in the hyper-

plane sheet containing all overlap regions must be less

-an

than or equal to 2n C The number [81] in S

an[an/2]' 1

must be less than or equal to half of this, or

1/2 2n - an C The previous argument tells us

an,[an/2]'

that
4[32] + 2[51] < 2 ° 2n - an Can,[an/2] '
Therefore
[5] = [52] + [sl] < 1/2 2n ‘ an Can [an/2] + 1/2 [51)

n - an
< 3/4 2 Can,[an/2]

< for a 2 5/8

Cn,(n/21

by a similar Lemma to 3-3.

Theorem 4-3. Let a , a ,....,a be n vectors in a real
1 2 n

vector space of finite dimension d such that "aiH 2 l,

i = l, 2,....,n. There is a number Nd such that if n is

greater than Nd' the number of sums of the form

52

that can lie in the interior of any d-sphere of radius 1

is less than or equal to Cn,[n/2]'

Proof: Assume that the d dimensional space can be divided
into disjoint regions in a manner symmetric under inversion
through the origin such that the sum of any two vectors of
length greater than or equal to s, s 2 0, that lie in one
region is also a vector of length greater than or equal to
s lying in the same region. We shall later locate these
regions. Decompose N, the set of integers from 1 to n,
into Na subsets of order na such that j Q Na if and only
if the vector aj lies in the region R: or its image under
inversion through the origin, R;. To each of the Zn sums
29 1 s.ai we shall correspond a subset A of N such that

1: 1

k e A if and only if k.e Nd and 8 lies in the region

kak
R2. This is a one-to-one correspondence because if ekak
. . + . . - . . . -
lies in Ra then - skak lies in Ra or if ekak lies in Ra
then-skak lies in R:' Denote by S the collection of all

.a.

subsets A of N for which the corresponding sum {2 = 1 81 1

lies in the interior of a fixed d-sphere of radius 1.

For each a, partition S into disjoint collections
S3 , j = l, 2,......,ra such that A, A' belong to S3 if
n

and only if their corresponding sums Z? = 1 eiai , 2i = 1 siai

have

5:. E e]!- for all i ¢ Na.

53

Each 53 is principal. If we assume the contrary, there
exists distinct A :>A' both belonging to some 8; and the

difference of their corresponding sums

n _ n _ - I _ .

thus showing that A and A' cannot both belong to S. Define

%n NalAe 33} , j = 1, 2,....,ra.

Clearly S; is also principal and [8;] = [83].

§j
a

To each element A belonging to some fixed 83, con-
sider the collection of all A'<= A corresponding to all

distinct sums of the form

2? _ eia. E Z? _ €.a. - 2 Z s a

'
keAnN k
0!.

k

n j -
where Xi = l eiai corresponds to A. Let Sa + Ra be the
total collection of all such A' formed from all the ele-
ments of S]. Note that S3 + R; = ¢ when SJ contains only

a single element A and A lea = ¢. For each j, Sj and

83 + R; are disjoint because Sj is principal and every
element of 83 + Ra is a subset of some element of Si.

Define

j - : j - ' _.
Sa+Ra- {A' nNaIA'e SCI-FRQ} ' j-l' 2'oooo’ra o

A ' /\ A ' ..
Clearly 83 and Si + Ra are also disjoint, [8; + Ra] = [8; +Ra],

54

and if A G. éi’ A' :3. then A' 6 Si + R;'
To each element A belonging to some fixed 5; similarly
consider the collection of all A":= A corresponding to all

distinct sums of the form

n , = n _
2i = 1 Eiai ‘ 2i = 1 Eiai zzekak '
kEN -AnN
a 0.

where 29 _ e.a. corresponds to A. As above SJ and

j + . . . j +' = j + .
Sa + Ra are also d13301nt1’£§Q~:.Ra] [Sa + Ra]' and if
A 6 S3, A" D A then A" E. s; + R21“ Furthermore it can be
similarly shown that S3 + R- and S3 + R+ are disjoint.
Hence S& + R; and 8; + R: are also disjoint.

Using Lemma 4-1 for each j = l, 2,..,ra we have

the relation

 

 

 

A. C 2] A A. <’\+
[83} < ninft/ [s3 + R U 53 U 53 + R] ,
a Zna a a a a a
hence
(833} s quJna/Z] [sj + R- U sj U sj + R+]
a n a a a a a '

 

2 a

Note that if A e S]; and A' 6 Si, 2, 7! k, then their

. n n
corresponding sums Xi _ l siai and ii = 1 eiai have at

least one i‘é'Na where 8i # Si. This means that if

k f l,

Sk n Sg + R1 = ¢ and Sk + Ri n 82 + Ri = ¢.
a a a a a a a

55

Sincetj§a= 1 8g is a disjoint union of S, we can conclude

that

IS] = 2;:1

 

[sj] Cna[na/2] rc j - j j +
a < 2nd Zj=1[sa + Ra U sa U Sa + Ra]

 

C
_ natns/Zl - +
_ 2nd [5 + Ra U s U s + Ra] .

Summing over all regions Ra’ it is seen that

 

nu _
2 2 [S] g X[s + R U s U s + R+] < 2n + R ,
a C [ _/2] a a
“a “a a
where R represents the overcounting of the number of sums
in all space that takes place as a result of the overlap
of the various regions S + R; U S U S + R: for different
+
0. Also note that S + Ri and S + R‘, a # 8, need not
a B
necessarily be disjoint.
The theorem is proven if for n sufficiently large
a division into disjoint regions Ra can be found for which

we have

 

C

n.
2n + R < E 2 a
a na[na/2]

) Cn,[n/21 '

hence [S] < Cn,[n/2]'

For all positive integers nu and n a rigorous proof
of the inequality,

C n
{(nu/n)l/2 < n'[n/2] 2C 2 8 E
a Zna" a na[na/2]

 

56

where n = 2 nu is shown in Appendix III. The desired re-
a

lation can then be reduced to
1 + RZ-n < E(n./n)l/2
a
a
But

2
a;l(na/n)l/2 2 O”Elna/n = l - nl/n .

Thus

2 (nu/n)1/2 2 (nl/n)l/2 + (l - nl/n)l/2
a

Therefore it suffices to prove that

l + RZ-n < (nl/n)1/2 + (1 - nl/n)l/2 .

Choose R such that it can be contained within a

l
cone of half aperture 90 as per condition (I) of Theorem
4-2. We need only consider the case where 1 - nl/n > 3/8.
If the space is divided into k regions such that each re-
gion can be enclosed by R1, then there exists at least one

region containing n/k or more vectors. Suppose R1 is fixed

to enclose this region. Then

n1 2 n/k or nl/n 2 l/k .
Thus by a suitable orientation of regions, nl/n may always

be chosen greater than or equal to some positive number m

which depends only upon geometry and not upon n. Hence

52
1/2 1/2 2 1/2
(nl/n) + (l - nl/n) > 1 + 2(3m/8)
3(1+A)ZIA>0.

So, if RZ-n can be shown to approach zero as n increases,
the theorem is proven.
The following construction shows that indeed RZ-n
can be made to approach zero. Let the d—dimensional space
be divided into the analogue of quadrants, i.e. 2d-ants.
Let a cone C of half aperture 90 be constructed such that
one sheet lies in the center of one quadrant. Assume its
axis coincides with the vector vo E (l, 1,..,l). Within
it we shall construct a convex non-empty region R1 with
hyperplane boundaries all of which intersect at the origin
[7].

Define d vectors within the cone C as follows:

ith component
_ r-——*1

Vi: (1'1,000.00'1-11’000000’1) [i=1] 2'..°Id’

where 0 < u << 1. These vectors are linearly independent.

For consider the equation

Alvl + A2V2 +......+ Advd = 0 ,

or its equivalent

(Al + 12 +......+ Ad)vO = Aluel + Azuez +......+ Adued

58

where
ith component

51 (O'O'OOOIO’I'OOOOOIO) 0

If there exists some Aj # 0 then {i=1 Xi # 0 because

d _

This also implies then that every 1i # 0 and A1 = l =...=A
and therefore u > 1 which is a contradiction.

We have,

There exist d subspaces Li formed from every dis-
tinct collection of d - l of these basis vectors. To each
subspace Li' 1 < i < d, we can associate a hyperplane

through the origin

b. x + b. = 0
i

111 +OOOOOO+ bi

2X2 dxd

such that all vectors in Li lie in this hyperplane. Each

hyperplane divides the space into separate convex regions.
Indeed, define E1 to be the space of all x such

that (bi, x) 4 0. If x(1) and x(2) lie in E1, then for

(1)

every x E Ax + (l - A) x(2), where 1 2 A 2 0,

(bi, x) = Mbi. x‘“) + (1 - Mani. x‘”) < o;

59

that is, also lies in El'
Let the region R1 be the intersection of the convex
regions defined by these hyperplanes such that every vector

in R1 is given by the equation,

v = n(AlV1 + A2V2 +......+ Advd

where

Note that

d
(V'Vo) "Xi = 1 *1(V1'Vo)

”VII "Voll = ”V" "VON

 

d
”21 = 1 Ai COS GOHViHHVo"

a 1
(ii = 1 nkillvilflllvol

 

cos
60 ,

which shows that every vector in R1 lies within the cone
C. Since R1 is convex, (it is the intersection of convex
regions) and 60 << 60°, the sum of any two vectors in R1
of magnitude greater than or equal to s is also a vector
in R1 of magnitude greater than or equal to 3. (See lemma
3-1.)

The entire structure should then be reflected

through the origin. Choose as regions Ra all 2d-ants

60

except those containing R1 or its image under inversion
through the origin, and the various regions into which the

hyperplane boundaries of R divide the 2d-ants containing

1
R1 or its symmetry when they are extended to meet the
boundaries of these 2d-ants.

The overcounting that contributes to R is con-
fined to hyperplane sheets of thickness 2 which are
cartesian translates of the boundaries of each region.

Denote by A6 the region in R1 such that the scalar
product of every vector within it with each of the unit
normals of the hyperplane boundaries of R1 equals a number
greater than 6. By a previous argument on geometric
orientation of regions, there must exist a nonempty region
AE for some positive 6. Choose 60 such that Ago is non-
empty. Let the whole system of regions be oriented so as

to contain the maximum number of vectors within AE . As n
0

increases the number of vectors within A6 can be made ar-
bitrarily large. That is, if ni is the ngmber of vectors
in Ago then ni 2 m'n for some fixed m' > 0.
We shall show that the number of sums 22 = l eiai
lying in any hyperplane sheet of thickness 2 which is a
cartesian translate of a boundary of some region can be
made arbitrarily small compared to Zn. If the hyperplane
sheet is parallel to a boundary of R1, this number is less

than or equal to

51
(Zn - n14/60 Cni[ni/2] < 2nAgo '2;nm'n

by Appendix III. Hence

Rim n n- ~ 2
n+w 1/2 (2 nl/éo Cnl[nl/2]) < lAgo/27nm'

im
n+m l//H = 0 .

If the hyperplane sheet is parallel to a boundary of some
d ._ ith cogponent

2 -ant whose unit normal 8i = (0,0,......, ,......,0)
then the component of every vector aj 6 AG: 0 along this

normal satisfy

(aj, 5;) > 1/2 .

Similarly as above the number of sums lying in this sheet
can be made arbitrarily small. Since there are only a

finite number of these hyperplane sheets,

m’n—>0 as n——>°°.

This proves the theorem.

CHAPTER 5
ERDCS'S CONJECTURE IN NORMED LINEAR SPACES

Let a normed linear space L be a metric space by

defining the metric 6 as
€(X, y) = ”x - y|| , for every x, y EL .

We now formulate the following as Erdos's conjec-

ture in normed linear spaces.

Conjecture: If a1, a2,......,an are n vectors in L where
[bin 2 l, the number of sums counted according to their

n _ . ._
multipliCity of the form 2i = 1 eiai, ei — :1, lying in

Side an arbitrary unit sphere does not exceed Cn,[n/2]’

Definition 5-1. Define two sums to be adjacent if they

differ at exactly one ej.

Adjacent points cannot lie in the same unit Sphere. Denote

a point p corresponding to the sum 2? = l eiai by the n-tuple

(El, 82,......,€n), or by the n-tuple of + and - signs.
Suppose n = l or 2. Then it is clear that Erdos's

conjecture is satisfied because the distance adjacent

points is at least 2.

62

63

Suppose n = 3. Consider the 23 sums as shown

below.

(---) (—+-)

(--+) ('++’

 

 

(+—-) ' ‘++‘)

 

(+-+) (+++)
Figure 4
If (+-+) and (-+-) lie in a sphere then all remaining
vertices are adjacent to these. Assume (+-+) and (++-)
lie inside an arbitrary unit sphere S whose center is e.
Crossing off adjacent points, (---) and (-++) are the only

possibilities left. But both these points cannot lie in-

side S because then

2Ha2 - a3” é Hal - a2 + a3 - e” + ”-a1 - a2 + a3 + e” < 2

SO

and similarly,

64

“32 + a3” < 1 r

and hence
2"a2” < “32 ' a3" + "a2 + 33” < 2 I

which is a contradiction. The set of points defined by

n . .

Xi = 1 eiai remain unchanged even if some or all ai are
changed to -ai. Without loss of generality we can then
assume that any set of three points lying inside S can be
represented by (+-+), (++—) and (-++), hence [S] < 3. As

above, these points imply the following relations;

”ai

-aj||<l, 1<i,j<3

Definition 5-2. A 60°-half aperture cone with axis b # 0

 

is the set of elements x satisfying

x - b <1
"x” "b" '
Assuming the order of the vectors is such that "a1" s flaiH,

l S i < 3, we easily see that al, a2, and a3 lie inside a

60°-half aperture cone centered about a1. Indeed,

a2 a1 a2 a1 a1 a1
- g _ + -

 

1 l l
‘ |a1(Ha2fl - "a1” + "a2" “a2 a1H

65

‘ "a1”(m " 1:71) " fair

1 ' ”a1"

l+—|Té-;n— (1.

Theorem 5-1. If for n odd [S] s Cn,[n/2]' then for n + 1

even [3] ‘ Cn + l,[(n + 1)/2]°

Proof: For each choice of en + 1, there can be at most

n + l

cn,[n/2] sums of the form Zk = 1 aka lying inSide S, by

k
hypothesis. The total number of sums must then be less
than or equal to 2 . Cn,[n/2]' The proof then is an im-

mediate consequence of the identity

2Cmin/21 = Cn.(n-1)/2]+ Cn.<n+1)/2 = Cn+1.[(n+1)/21 °

Therefore, to prove Erdos's conjecture in normed
linear spaces, it is sufficient to consider only the cases
where n is odd.

The proofs for n = 5 and 7 have also been similarly
carried out, as for n = 3, discovering identical properties,
and the additional property that there exists only one
unique position for the maximal number of points Cn,(n/2]
inside a unit Sphere.

We shall now conjecture the following distribution

of points inside S for the maximal case C . For the
nr[n/2]

66

n—

2 points of the form (-i ...... i) assume there exists

2

. . . n - .
Cn-l,[(n-1)/2] lying inSide S and for the 2 pOlntS of

-: i .
the form (+ ... ) assume Cn-2,[(n-2)/2] For the

2n - 2 points of the form (++i ... i) assume there exists

Cn _ 4 lying inside S where Cn _ 4 is the sum total of the
following distribution: for the Zn - 4 points of the form

-_+ + n ' 4
(++ - ..... —) assume Cn _ 4,[(n _ 4)/2], for the 2

points of the form (++-+i ..... i) or the Zn - 4 points of

_+ =
the form (+++ _ ... i) assume Cn _ 6 C(n _ 2) _ 4

the Zn - 4 points of the form (++++i ,..., i) assume the

and for

following distribution: for the 2n - 6 points of the form

--+ + =
(++++ - ..... —) assume Cn _ 8 C(n _ 4) _ 4, etc. The

partioning terminates at 2(n + 1)/2 if n E 1 (mod 4) or at

2(n _ 1)/2 if n E 3 (mod 4), and in either case we assume

that there exists a set of 2(n + l)/2

points containing
only one point inside S.
An illustration is in order. See figure 5.

Our conjecture states that

A

11,[11/2] + C9 '

C13,[13/2] : C12.[6] + C

where

O)
n

9-C9'[9/2]+2C7+{C5+2{C3+l+l}+l}.

67

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ll

 

 

 

 

n = 13
1
27 C3
1
C3
1 c
5 1
1
C3
1 c5
1
1
1 3 1 23
1__C§_.,
4
c

 

 

 

Figurejfi

E Ci,[i/2]f

68
By recursive substitution

C + + 2

13.113/21 = C12,[6]+ C11.111/21 C9.19/21 C7.17/21

+ 5 + 14C + 42C

C5.15/21 3.13/21 1.11/21 '

a formula which checks numerically [8]. Similarly,

A

C13,[13/2] + C11

‘ C14.17] +

C15,[15/2]
where

C11 2 + 2c + {c7 + 2{c5 + 2{c3 + 1 + 1} + 1}

C11,[11/2] 9
+ {C3 + 1 + 1 + 1 + 1}}

and be recursive substitution

= C + + C + 2

C15,[15/2] 14,[7] C13,[13/2] 11,[11/21 C9,[9/2]

+ +
+ 5C7’[7/2] 14C5'[4/2] 42C

+ 132C

3:[3/2]

l,[1/2] ,

a formula which again checks numerically [8]. Note that
the coeffiCient for the term Ck,[k/2]' l < k < 13, in the
formula for C13,[13/2] equals the coeffiCient for the term
Ck + 2,[(k + 2)/2] in the formula for C15,[15/2]’ Numeri-
cal values [8] for this conjecture where checked up to

C = 342716.

21,[21/2]

APPENDICES

APPENDIX I

m
RELATION BETWEEN 2 CD _ m'[(n _ m/2]

+
AND Cn,[n/2] , n e I

Case 1. n and m are even.

For 0 < m < n,

Cn.[n/21 = n! 2
[(n/2)!]

 

(n-m)! (n-m+l)(n-m+2) ........... (n-m+m)
[((n-m)/2)l]2 [((n-m+2)/2)((n-m+4)/2)....n/2]2

 

 

_ 2mC n-m+l n-m+3 2:1
- n-m,[(n-m)/2] n-m+2 n-m+4 """ n
Therefore
ch Cn,[n/2] , m = o
n-m.[(n-m)/2] =4
n-m+2 n-m+4 n
L 5:511' 5:513) ----- (a=1)cn.[n/21'°<m‘n °

 

 

 

Case 2. n is even and m is odd.

For 1 < m < n,

69

70

 

= (n-m) !
n, [n/2] {fin_m-1)/2)T(Zn-m+l)/2) I}

(n-m+1)(n-m+2)....(n-m+m) :}
((n-m+l)/2)((n-m+3)/2)2....((n-m+m)/2)2

 

 

 

 

 

= 2m C n-m+2 n-m+4 n-l
n-m,[(n-m)/2] n-m+3 n-m+ °°°° n”
Therefore
C
m nl[n/2] p m: l
2 Cn'mr[(n-m)/2] =‘
n-m+3 n-m+5 n
n-m+2 n-m+4) """ H:I)Cn,[n/2]’ l<m<n

 

 

 

 

 

Case 3. n is odd and m is even.
For 0 < m < n

n!

Cn,(n/21 = ((n-17/2)!((n+1)/7Y!

 

 

(n-m)!
((n-m—l)/2)!((n-m+l)/2)!

(n-m+l)(n-m+2) ................... (n-m+m) :}
((n-nH-l) /2) z ( (n-m+3)/2)2. ( (n-m+m—1)/2)2((n-m+m+1)/2)

 

 

 

 

 

 

_ ch n—m+2 n-m+4 n
n-m,[(n-m)/2] n-m+3 n-m+5 """ n+I
Therefore
- J Cn,[n/2] , m = 0
m
2 Cn-m.[(n—m)/21 ‘
n-m+3 n-m+5 n+1
.n-m+2 n-m+4 """ n ’ 0 < m < n

 

 

 

 

 

 

 

71
Case 4. n is odd and m is odd.

For 0 < m s n,

 

 

 

 

C = (n-m)! (n-m+l)(n-m+2) ................. (n-m+m)
“' W2] <(n-m)/2): < (n-m+2)/2)7. . .((n-m+m-l)/2)2((n-m+m+1)/2)
_ 2m C n-m+l n-m+3) _g_
_ n-m, [(n- m)/2] n-m+2 5:514 """ n+1
‘Therefore
m _ n-m+2 n-m+4 n+1
2 Cn_m'[(n_m)/2] - n—I_m+ n-m+ )0... T n [II/2], 0 < m S n

 

 

 

 

 

APPENDIX II

k
ET
RELATION B WEEN 2 Cn-k,[(n'k)/2]

+

AND

Cn,[n/2] , 0 < k < n/4 , n €.I

From Appendix I we note that
m
2 C
n-ml [ (n‘m)/2]
is monotone increasing as m increases. Thus to find upper

bounds for 2k C /2], we shall consider the greatest

n’k I [ (n'k)
integer F less than n/4.

First note Stirling's inequality [6],
,5? mm+l/2 e-m < m! < ’EF'mm+l/2 e-m el/4m

which is true for all positive integers m.
Let m E 0 (mod 8). By Stirling's inequality we

derive the following relation

m/4 = 2m/4(3m/4)1

2 C3m/4,[3m/8] [(3m/8)!]2

 

2m/4/2?<3m/4)3m/4+1/2e-3m/4el/3m

<
{/Efi(3m/8)3m/8+1/2e-3m/8]2

 

72

73

el/3m (/§? min-I-l/Z e-m)el/m
(3/4)l/2 {/35(m/2)m/2+l/2e-m/2el/2m]2

 

A

4/3m
V473 e Cm,[m/2]

This relation will be used in the derivation of all cases

mentioned below.

In the following cases, let

where m E 0 (mod 8) and j

II

o
s
I—l
s

o

o

o
\1

Case 0. n E 0 (mod 8), n -

|
B
+
O

For E'= m/4 — l we have,

2m/4—l C

_ 2m/4-l 3m/4+l
3m/4+l,[(3m/4+l)/2] —

‘72“2'3m + )2C3m/4 , [3m/8]

using Case 4, Appendix I.

: k '
Thus for n _ 0 (mod 8), 2 Cn-k,[(n—k)/2] is less
than
4/3n 3n + 4
4:3 e §E—:_§’ Cn,[n/2] °

 

 

Case 1. n E 1 (mod 8), n = m + 1

For E'= m/4 we have,

 

74

2C

2m/4 < 4 3 e4/3m(3m + 4

C3m/4+1 , [Gm/4+1) /2] —'—"§3m +

 

ml [In/2]

_ 4/3m 3m+4 m+2
- “473 e (WXEFI C

 

using Case 4, Appendix I.

k

Cn-k,[(n-k)/2] is less

Thus for n E 1 (mod 8), 2
than

n + l

’37—e 4/3(n-l) 3n + 1
(3n + ) n ‘)Cn,[n/2] °

 

Case 2. n E 2 (mod 8), n = m + 2

For E'= m/4 we have,

m/4 3mé4+l 2
3m/4+2,[(3m/4+2)/2] 2 ( m + 2

3m+4 22 C
§fi:§ m,[m/2]

2m/4

C

 

3m/4,[3m/8]

’17? e4/3m

A

 

 

 

 

_ ’37? 4/3m 3m+4 m+2
- e §m+§) m+I)Cm+2,[(m+2)/2]
using Case 1, Appendix I.

k

Thus for n E 2 (mod 8), 2 Cn-k,[(n-k)/2] is less

than

n

n - I) Cn,[n/Z]

 

4/3(n-2) 3n - 2
«m (m

75
Case 3. n E 3 (mod 8), n = m + 3

For E'= m/4 we have,

m/4C _ m/4 3m 4+3 3m/4+1 3
2 C,3m/4+3 [(3m/4+3)/2] ' 2 (fim + “11137717?2 C3m/4,[3m/8]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

< /z7§e 4/3m %E:I%)2E:%)23 Cm.[m/21
= [57-3-34/3m’3ffi—fié 3'31“; 3T3 3%”) Cm+3,[(m+3)/2]
using Case 4, Appendix I.
Thus for n E 3 (mod 8), 2k Cn-k,[(n-k)/2] is less
than
mJ/“n‘” ——§::3 —:§::5 —) —— Mm-
Case 4. n E 4 (mod 8), n = m + 4
For E'= m/4 we have,
2m/4C = 2m/4(4m/4+3 4m/4+1)24C
3m/4+4,[(3m/4+4)/2] 3m/4+4 3m/4+2 3m/4,[3m/8]

 

 

e4/3m 3m + 12 3m + 4 4
< 3 ( ) 3m + 3)2Cm.Im/21

 

 

 

 

 

 

 

 

m+
= /I7§ e4/3m 3m+12 3m+4 m+2 m+4 C
3m+ 6 3m+§ m+I m+3 m+4,[(m+4)/2]

using Case 1, Appendix I.

 

76

Thus for n E 4 (mod 8), 2k C is less

n-k.[(n-k)/2]
than

3n +

/z73 e4/3(n-4)(3

 

 

3n - 8 n - 2 n C
n - 3 n - I' n,[n/2]

Case 5. n E 5 (mod 8), n = m + 5

For E'= m/4 + 1 we have,

3m+4

m/4+l 5
2 3m+8)2 Cm,[m/2]

4/3m 3m+12
3m+16

 

 

C3m/4,[(3m/4+4)/2] < “373 e

 

 

 

 

 

_ /z7§ 4/3m 3m+12 3m+4 m+2 (m+4 (m+6 C
- e 3m+I6 3m+§ miI' 513’ 5:3' m+5,[(m+5)/2]

using Case 4, Appendix I.

- k .
Thus for n = 5 (mod 8), 2 Cn-k,[(n-k)/2] is less

than

/z73 e4/3(n-5)(3n-3

 

 

n+1
§)(n —) Cn,In/21

 

 

3n-11
Case 6. n E 6 (mod 8), n = m + 6

For F’= m/4 + 1 we have,

2m/4-I-l

 

 

 

 

 

 

 

C3m/4+5,[(3m/4+5)/21
2m/4+l 3m 4+5 3m/4+3 3m/4+1 25 C
3m§4+6 3m/4+4 3m/4+2 3m/4,[3m/8]

r7r- 4/3m 3m + 20 3m + 12 3m + 4
< 4 3 e (3m + 24)(3m + I6)(3m + 3

(3:: :3]

m + 6 C
ETITE' m+6,[(m+6)/2]

 

Cm! [In/2]

 

 

= 4/3 e4/3m 3m + 20 3m + 12
3m + 24 3m + 16

m + 4
m + 3

 

 

 

 

 

m + 2
[m

using Cases 4 and 1, Appendix I.

 

 

 

 

 

 

 

 

 

 

 

 

= k .
Thus for n - 6 (mod 8), 2 Cn-k,[(n-k)/2] is less
than
/——- 4/3(n-6) 3n+2 3n-6 3n-l4 -4 n-2 n
4/3 e 3n+6 3n—2 (3n-IU (n-5 n-3 (n-I) Cn,[n/2]°
Case 7. n E 7 (mod 8), n = m + 7
For F'= m/4 + l we have,
2m/4+l C
3m/4+6,[(3m/4+6)/2]
2m/4+1 3m 4 + 5 3m 4 + 3 3m/4 + l 26 C
' 3m 4 + 6 m” + ' 3m74 + 2 3m/4,[3m/8]
< /473 e4/3m 3m + 20 3m + 12 3m + 4 27 C
3m + 24 3m + I6 3m + 5 m,[m/2]

 

/I7§ e4/3m. HBm + 20) 3m + 12

111+

m + 2
m + 1

using cases 1 and 4, Appendix I.

   

3m + 4
m +

!

3m+ +

 

 

 

 

 

$4]Cm+7,[(m+7)/21

 

 

 

78

 

 

 

 

: k .
Thus for n _ 7 (mod 8), 2 Cn-k,[(n-k)/2] is less
than
4/3(n-7) 3n-1 "3ne9 3n-l7
' 4; 3 e {in—+3 —3n"—-5) ——3n-13'):}

n-5

n-1
5:? )

n72

 

 

(ii-i)

 

n+1
TB Cn, [n/2]

APPENDIX I I I

Proof of the inequality

 

C n
2W . __ 2. 2a }
a 2 a nd[n&/2]

where 2 na = n, n and n are positive integers.

a If the number of a's equals one, this is trivially
true. Hence we shall assume the number of a's is greater
than one.

We shall try to prove the inequality using term-

wise comparison. i.e., for all nu,

C nu
—-L-—Z-—n [n 2] {CT 2 }2 (nu/ml/Z .

2n n&,[na/2]

An attempted proof using Stirling's formula [6]

reduces to the following relations

 

 

 

 

 

 

 

1 na 1/2
el/4nd+l]4 5‘ na' n even
Cn, [n/2] { Zné‘ >
2n Cna,[na/2] 1/2 n 1/2
1 n n ‘2
el/4n'd+I/(n-1) n-l n+I n
na, even
n, odd;

79

80

and in both cases the coefficient of (nd/n)l/2 is less
than 1, so a simple application of Stirling's formula
will not suffice.

Assume n is even. Since n > na for all a, it is

sufficient to show that

 

 

 

 

/2E.C2k,[k] > “QE:I.C2k-1,[2k-1)/2] k 2 1
2R 2k-1 ’

2 2
and

/7EIC2k,[k] > “2E'2 CZk-Zijk-l] k 3 1

22k 22E-2 ' °

The first relation is true because

C2k,[k] = 2C2k-1,[(2k-1)/2]' f°r k 3 1 °

The second relation is also true because

c = 22((2k-l)/2k) c

2k,[k] 2k-2,[k-l] '

and

 

 

2k ”k - 1 4k2 - 4k + l > 1 for k 2 2 '
2k - 2 4k2

and for k = 1 it also holds.
Assume n is odd. Termwise comparison does not

suffice as we shall show that

81

”ZR + I C2k+1,[(2k+1)/2] < “IflczklkJ
2k

2k+1 ' k 2 1

‘0

2

although it is still possible to show that

CZk-L[(2k-l)/2]
22k-1 '

2k+1J(2k+l)/2]

/2E‘¥‘I C /7E'=_I
22k+1 >

k 2 l .

 

To prove the first relation, substitute

C = 2(2k + 1) c
2k+1J(2k+1)/2] ifififi' 2k[k] °

But now
/2k + 1 2k + 1 =\/%k3 + 12k2 + 6k + 1
5E 2E + 2 8k3+ 16k2 + 8k

2
==JG — 4k + 2k '21 < l for k2 l .
2k(2k + 2)

 

 

 

 

For the second relation, substitute

 

 

 

C = 22 2k + 1 C
2k+lJ(2k+l)/2] ZE‘I'E' 2k-l[(2k-l)/2]
and note that
2k + 1 (2k + 1 =\/%k3+ 12k2 + 6k + 1 > 1 for k 2 1
2E ' I 2k + 2 8k3 + 12k2 - 4

 

Define the function

g(n) 5 /fi Cnlln/2],'

82

where n is a positive integer. We have shown that g(n) is
monotone increasing if the domain of the function is re-
stricted to the set of even positive integers or if the
domain of the function is restricted to the set of odd
positive integers, but that 9 increases at a faster rate
for n even than for n odd. We shall now proceed to show
that for a given n odd, the transitional point always
occurs when n* is the largest even integer less than n/3.

That is, if n* + 2 > n/3 > n*, then
g(n* + 2) > g(n) > g(n*)

where n is odd and n* is even.

First we shall derive asymptotic expansions for
the function g [9].

Assume n is an even positive integer. i.e.,

n E 2k, k 3 1. Then

 

 

___ a? ((210!)
333 (k1)2
= m: (2k I‘(2k) )
‘27]? (k rum2
_ m? { 2 , 22]“1 wk) I‘(k+l/2)}
— m
27H ,..,

 

= m I‘(k 'l' 1/2) .
(km I‘(k)

83

The asymptotic expansion [9] for 109 Pf§2+ 1/2)
k r(k)

 

equals

{k log (k+l/2) - (k+l/2) + 1/2 log 2n + I77E%I777

 

' l +....
360 (k+l/2) 3' }

_l_

-§l/2 log k + (k — 1/2) log k - k + 1/2 log 2n + 12k

= k log (1 + l/Zk) - 1/2 - l/24k(k+l/2) + El(k) ,

where the absolute value of the error term

IEl(k)| s 1/360 (1/(k+1/2)3 + l/k3) < 1/180k3 .

Since 1/2k < l for k 2 l, k log (1 + 1/2k) can be expanded

into the convergent series,

k{l/2k - 1/2(1/2k)2 + 1/3(l/2k)3 - 1/4(1/2k)4 +.........}

3

2 + E2(k), where |E2(k)| < l/64k .

= 1/2 - 1/8k + l/24k

Then

r(k + 113) _
log e -7 V - -l/8k + E (k)
kI/2F(k) 3

f(k)

or

ef(k) = r(k + 1/2)

kI/Z—T(k)

 

84

where

3 3

IE3(k)| < l/24k(l/k — l/(k+l/2)) + 1/180k + l/64k

< 121/2880k3 .

Consider the series expansion for

1 + f/l! + f2/2! + f3/3! + f4/4! + fs/S! + .......

(D
II

1 + f/l! + f2/2! + f3/3!{l + f/4 + f2/4-S +.......

Since
|f| < 1/8 + 121/2880 < 1/2 for all k 2 1,
we find
1 + f/4 + f2/4os +...... < 1 + |f| + |f|2 +......
= 1/(1 - |f|) < 2 .

Substituting f(k) in the series expansion for ef we have

Pf§2+ 1/2) = 1 - l/8k + 1/128k2 + E(k) .
k r(k)

 

(See also Formula 6.1.47, page 257 of Ref. [10]),

where

|E(k)l <|E3(k)| + 1/8klE3(k)| + 1/2|E3(k)|2

+ 1/3 §1/8k)3 + 3(1/8k)2|E3(k)I + 3(1/8k)|E3(k)|2

+ IE3(k)|3}

85

3

< l/2880k (121 + 121/8 + 1/2 (121)2/2880 + 2880/1536

+ 121/64 + 1/8 (121)2/2880 4 (121)3/3(2880)2)

< 73/1440k3 .

Therefore we have an asymtotic formula for

2

g(2k) E /2/n{1 - l/8k + 1/128k + E(k)} , k 2 1

where

IE(k)| < 73/1440k3 .

Assume n is an odd positive integer. i.e.,

n E 2k + l, k 2 1. Then

 

g(2k+l)

VZE + I (2k + l)!
ElTk + 1]]

_ /2E‘:‘T ( r(2k + 2) )
*WW

.4.

- 2E + I ¢fi FTk + 1)FKR + 2)

_ /2E‘:‘I {22k + 1F(k + l)F(k + 3/2{}
2

1/2
2k + 1 k r(k + 3/2)
'27" 2k ( 81k + 2) )

From our previous derivation for the asymptotic

r(k + 1/2)

formula of , we obtain the formula for
kl/2 r(k)

 

86

kl/2P(k+3/2)
P(k+2)

 

k + l/2)(P(k + 1/2))
k + 1 1/2F(k)

 

{1 - 1/2k + l/2k2--l/(2k2(k+l»}{l - 1/8k

+ 1/128k2 + E(k)}

1 - 5/8k + 73/128k2 + Ei(k) ,

(See also Formula 6.1.47, page 257 of Ref. [10]),

 

 

 

where
|Ei(k)| < 1/256k3 + 1/16k3 + 1/256k4 +2LWQk?(k+1» ka + 1/2)
/2
k r(k)
k + 1 2
WHIEWI
< 18/256k +1/ Qk (k+l)_) + 73/1440k < 895/1440k .

Since l/2k < l for k a l, V2k+l/2k can be expanded to the

convergent binomial series

(”215112) (l/Zk)2 + (1/2)<-1/2><—3/2>

'(1/2)
1 + “T'— (1/2k) + 1,2,3

(1/2k)3 + ......

2

= l + l/4k - l/32k + Eé(k) , where |Eé(k)| < 1/128k

Hence

1/2
k r(k+3/2) = {1 + l/4k - 1/32k2

r(k+27 + E2(k)}

 

{1 - 5/8k + 73/128k2 + Ei(k)}

87

= 1 - 3/8k + 49/128k2 + E'(k) ,

where

1/2P(k+3/2)
Plk+2Y

3 3 3

 

IE'(k)| < 73/512k + 5/256k + 73/4096k + |Eé(k)l k

+ 42k+1/2k |Ei(k)|

3

< 737/4096k + 1/128k3(9095/5760) + /372(895/1440k3)

< 1373/1440}:3 .

Therefore we obtain the asymptotic formula

g(2k+1) s /27? {1 - 3/8k + 49/128k2 + E'(k)} , k 2 1

where

3

lE'(k)| < 1373/1440k < 1/k3 .

Every positive odd integer can be represented by
6k + i, i = l, 3 or 5. Suppose n = 6k + 1. Then the
largest even integer less than n/3 equals 2k. The difference

of the functions

g(6k + l) - g(2k)

49.9. 2.

= /Z7F {1 - 1/8k + u + E'(3k)} - /27? {1 - 1/8k + 1/128k
128k
+ E(k)}

88

> J77?’{%9137- 1/27k3 - 73/1440k%}
128k

= /27F (10/288k3)(k - 379/150) > 0 for k 2 3 .
If k = 2
g(13) - g(4) = /I'3'(1716)/213 - /2r(4)/24 = .755 - .750 > 0 ,
and if k = 1,
9(7) - g(2) = /7(35)/27 - /2‘(2)/22 = .723 - .707 > 0 .
Also, the difference of the functions

g(2k+2) — g(6k+1) = /27F {1 -a/18(k+1» +1/{128(k+1)2)+ E(k+1)}

_ “i: -;.é.'£+ ”9 +E'(3k)}
128k

/Z7E'{1/8(1/k - 1/(k+l)) + 1/128(1/(k+1)2 - 49/9k2)

f

V

- 73/(1440(k+l)3)- 1/27k3}

 

 

 

 

= /27E{: 1 _ 40k2 + 98k + 49 _ 379k3 + 480k2 + 480k + 160
8kzk+15 1152k2(k+1)2 4320k3(k+1)3
= /77? Pik) *3
17280k (k+l)
where
4 3 2

P(k) = 1560k + 734k - 1965k - 2655k - 640 .

89

Note that

P'(x) = 6240::3 + 2202::2 - 3930x - 2655 > 0 for all x 2 1 .

This means that no local maximal-minimal point exists for

the polynomial P(x) in the interval [1, + 00). Now since

P(2) = 24960 + 5872 - 7860 - 5310 - 640 > 0 ,

the polymonial P(x) is positive in the interval [2, + 00).

i.e., P(k) > 0 for all k 3 2. Therefore
g(2k + 2) - g(6k + l) > 0 for k 2 2

If k = 1, then as above g(4) - g(7) = .750 - .723 > 0.
Following similar proofs as above we obtain identi-
cal results if n = 6k + 1 were replaced by 6k + 3 or 6k + 5.

The conclusion then that

'2E+2 C2k+ng+l1 > '6E+1 C6k+L[(6k+i)/2] > ’Zk C

22k+2 26k+1

21‘:ka
2k

 

 

2

where i = l, 3, 5 and k 2 l, proves our statement about the
transition point.

Continuing with the proof of the inequality

C 1 _.. {.4na , _
X (nu/n)l/2 < —2Ll%121- {} C 2 :} I
a 2 ' a na,[na/2] '
there remains to show the cases where n is odd and at least

one even integer ha is greater than n/3 for otherwise term-

wise comparison suffices. It is clear that at most only

90

two such na's can exist.

Case I. Assume only one 2n > (2n+l)/3 where

 

 

 

l
2n+l = E 2nd + g 2nB + 1, n > 0, na > 0, n8 2 0.
We wish to prove that
2 V2na + X/inB + I
a B
‘ '2n+I C2n+1,[(2n+1)/2] 2 2 + 2 2
22n+l a C B C
Zna,[na] 2nB+ l,[2nB+l)/2

First we will show that it is sufficient to prove

only the inequality

 

 

[in— + m ‘ n C2n+l,[(2n+l)/2] (22111
l 2 22n+1
anlnll
+ 22n2+1
C2n2+L[(2n2+l)/2]
where 2n2 + 1 = 2 Zna + 2 2nB + 1 .
afil B

The statement on sufficiency will now be proven.

Note that for all a # 1,

2n
’2n+1 C2n+1,[(2n+1)/2] 2 a _ ,55— > 0
2n+1 a

2 C
anlna]

91

because g(2n + 1) > g(2na); and for all 8,

’2n+I C2ntL[(2n+l)/2] 22n8+1 _ /Efi‘$I > 0

* 22n+1 C2nB+L.[(2nB+1)/2] B

 

because g(2n+1) > g(2n8+l). Thus there remains to prove

that the relation,

 

 

 

 

 

211+ C2n+ll[ (2n+l)/2] 22n2+1 _ m
2n+l C 2
2 2n2+L[(2n2+1)/2]
< ’2n+I C2n+1,[(2n+1)/2] 22n8+1 _ +
2n+1 E’ "Ens I
2 2nB+LI(2nB+l)/2]
is true for any 8 from the sum X 2nB + 1. If 2n2 + l
B
= 2nB + 1, there is nothing to prove. If not, the proof
will follow if
'2n+I C2n+l,j(2n+l)/2] 22n2+1 _ fifi‘iI
2n+1 C 2
2 2n2+l,[(2n2+l)/2]
'§n+I C2n+1,[(2n+1)/2] 2’12"1
< 2n+1 c —.2n2 ' I
2 2n2-1,[(2n2-l)/2]
or equivalently using Appendix I, if
g(2n2+1)
g(2n+1) < ———————— (2n2 + 2)(./2n2 + I - /2n2 - I) .
V2n + l

2

92

A proof of this last inequality can be obtained
by using a stronger Wallis' formula given in Ref. [11].
We give a more elementary proof.

Using the convergent binomial series expansion for

 

 

/1 + l/2n2 and /l - l/2n2 , n2 2 l ,

(/2n2 + — /2n2 - I) > l/v/Zn2 > 1/V2n2 + l

 

 

Therefore assuming n2 2 3,

g(2n2+1) 2n2+2
m— (2n2+2) (V 2112+]. - v2n2-l) 7 g(2n2+l) 511—21-1-
' 2

= V270 {l - 3/8n2 + 49/128n2 + E'(n2)}{l + l/an - l/4ng

2

+ l/(4n§(2n2+D)}

V

V270 {1 + l/8n2 - 7/128n2 + 73/256n3 - 49/512n:

2

- (1373/1440n3)(8/7) -1/{4n§(2n2+1n(/27Fg(3))}

V

/27? {1 + 1/8n2 - 7/128n§ - 180/256ng - 49/512ng} > /27F ,

g > 7/16n + 180/32 + 49/64n for all n 2 3.

because n 2 2

2

If n2 = 2,

g(5)//§ (6)(/§ - /3) = .9450 > J27n ,

and if n2 = l,

93
g(3)//3 (4)(/3 - 1) = 1.0981 > 07? .

But for increasing n, g(2n + 1) is monotone increasing

and zim g(2n+1) = V27fl. i.e., V270 > g(2n+1) for all

n-HJO
n > O. This terminates the sufficiency proof.

Now we shall prove that

V2n+l C

2n+L[(2n+l)/2]
V2111 + V2n2+1 i {21143; C

22n1

 

2n1[n1]

22n2+l

2n2+L[(2n2+1)/2]

+

 

C

This proof will be in two parts. The first part proves
this relation for all n satisfying (2n+l)/3 < an < n. The
second part for all n satisfying n < 2nl < 2n + l.

The desired relation shown above is equivalent to

showing,

Vinl g(2n2+l){g(2nl) - g(2n+1)} <V2n2+I'g(2nl) {g(2n+1)
- g(2n2+1)}

But by assumption and the monotonicity of g for odd integers,
g(2n1) > g(2n + l) > g(2n2 + l) .

Therefore it is sufficient to prove that

V2n1{g(2nl) - g(2n+1)} <v§n2+I{g(2n+l) - g(2n2+1)}

94

Suppose 2n + l = 6k + 1. Define 2n1 E 2k + 2j,

l s j s k/2 and 2n + l = 4k - 2j + 1. Substituting for

2
9 its asymptotic representation with extremal errors, it

suffices to show that

/2E:23/27E{1/8(1/k - 1/(k+j)) + 1/128(1/(k+j)2 - 49/9k2)

1/1440(73/(k+j)3 + 1373/27k3)}

< /IE=2§:I/277{1/8<3/(2k-j) - l/k) + 49/128(l/9k2 - 1/(2k-j)2)

 

- 1373/1440(1/27k3 + 1/(2k-j)3)} ,
0r
"ZEEZJ 3 {l9440k2(k+j)2j + 135k(k+j)(-40k2 - 98kj - 49j2)
155520k (k+j)
+ 4(3344k3 + 4ll9k2j + 4119kj2 + 1373j3)}
< V4E-2J+I 2

 

3 3{l9440k2(2k—j)2(k+j) + 6615k(2k-j)(-5k
155520k (2k-j)

3 2

- 4kj + jz) + 5492(35k - 12k j + 6kj2 - j3)}

or

4 3 2 4

/2E:2§(2k-j)3{(19440k j + 38880k j + l9440k2j3) - (5400k

3 2

3 2 2 + 16476k j

+ 18630k j + 1984Sk j + 6615kj3) + (13376k

2

+16476kj - 5492j3)}

< /IE:ZT¥I(k+j)3{(77760k5 - 58320k3j2 + l9440k2j3) —(66150k4

3 2 2

+ l9845k j - 39690k j 3 3

+ 6615kj3) - 092220k - 65904k j

+ 32952kj2 - 5492j3)}

95

The difference between these two terms equals,

/IE=231I{(77760k8+.233280k7j + 174960k6j2 - 77760ij3

4.4 2 6

- 116640k j + l9440k j )

(66150k7 + 218295k6j + 218295ij2 + 13230k4j3 - 79380k3j4

- 19845ij5 + 6615kj6)

092220k6 + 510756k5j + 411900k4j2 + 87872k3j3 + 16476ij4

+ 16476kj5 - 5492j6)}

6 2 5 3 4 4

/2K:23{(155520k7j + 77760k - l94400k j - l9440k

j 3'

+ 77760k3j5 - l9440k2j6)

7 - 84240k6j + 32400ij2 + 78840k4j3 - 21060k3j4

....

{-43200k

- 19845ij5 + 6615kj6)j

6 5 4 2 3 3 2 4

+ (107008k - 28704k j + l4352k j - 68296k j + 16476k j

+ 16476kj5 - 5492j6)}

For 1 < j < k/2,

 

 

'\/4k ' 3 + 1 < /2E‘I‘2j < /4k - 2j + 1

Therefore the actual difference for k 2 3 is greater

than

8 7 6 2 5 3

77760k + 77760k j + 97200k j + 59702k j - 102894k4j4-77760k3j5

+ 33186ij6 - 35603k7 - 158728k6j - 250695ij2 - 92070k4j3

96

+ 94271k3j4 + 33877ij5 - 13230kj6 - 299228k6 - 490459k5j

- 426252k‘4j2 - 39580k3j3 - 32952ij4 - 32952kj5 + 9375j6
> 32434k6 + 29k5j + 15k4j2 + 2k3j3 + 249903ij4 + 68679kjS
.6

+ 268359]

using the property that k 2 2j.

If k = 1 or 2 the proof of the inequality

V2E:2§'+ «zktfjir c g(6k+l){%%§§$§%T-+§%%§E§%$%%}

can be shown to be true by actual substitution.

The second part of the proof will consist in show-

 

 

 

 

ing that
('§n+I C2n+l,[(2n+l)/2] 22n2+l _ /§fi‘:f)
22n+1 02 2
n2+l[(2n2+l)/2]
_ /7fi_ _ ’2n+I C2n+lJ(2n+l)/2] 22nl
1 22n+1 C2n [n ]
r 1
V2n+I C 2n -1
< _ 2n;1i£2n+l)/2] C 2 2 _ “752—:I
2 “ 2n2-1J(2n2-1)/2]
_ (VIE—:2 _ “2n+I C2n+1,[(2n+1)/2] 22nl+2 )
1 22n+1 C2nl+2,[n1+l]

96

+ 94271k3j4 + 33877ij5 - 13230kj6 - 299228k6 - 490459k5j

- 426252k‘4j2 - 39580k3j3 - 32952ij4 - 32952kj5 + 9375j6
> 32434k6 + 29k5j + 15k4j2 + 2k3j3 + 249903ij4 + 68679kj5
.6

+ 2683593

using the property that k 2 2j.

If k = l or 2 the proof of the inequality

V2k+2j + VIE-23+]: < g(6k+1) W)- +. WW}

can be shown to be true by actual substitution.

The second part of the proof will consist in show-

 

 

 

 

ing that
('§n+I C2n+L1(2n+l)/2] 22n2+1 _ /ZH‘II)
22n+1 c2 2
n2+l[(2n2+l)/2]
_ ,73— _ '2n+I C2n,+-1,[(2n+1)/2] 22n1
1 22fi+1 C2n [n l
r 1
< '2n+I C2n+1,[(2n+1)/2] 221‘2'1 _ VEE“=I
22n+1 C2n2-1.[(2n2-1)/2] 2
_ (VZH‘if _ '2n+I C2n+1,[(2n+1)/2] 22n1+2 )
1 22n+i C2n1+2,[n1+1]

97

where 2n1 varies from the largest even integer less than
or equal to n up to a maximal value of Zn - 2. i.e.,
n < 2nl + 2 < 2n + 1.

If 3k is even the minimal an = 3k. i.e., n1 = n2.

Substituting n = n in the above relation, the proof for

2 1
these values reduces to showing

V2n1 + 2 + V2nl - I < V2n1 + I + V2nl ,

and

because 2C +l,[(2n2+l)/2]

2n c2n +2,[n1+l]

2 1

2C

2n = C

. But the difference of

2-1,[<2n1-1>/21 2nl.[n11

the squares

(VEHE'I‘I + VEHI)2 - (VZHIV$_2 + VifiI‘Z‘I)2

 

 

= 2{V4n + 2n - V4n + 2n - 2} > 0 ,

l 1 1 1

for all n1 > 0. This proves the inequality for 111 = n2.
If 3k is odd the minimal 2n1 = 3k - l, i.e.,

n + l = n Substituting n = + 1 in the above rela-

1 2° 2 n1
tion, the proof for these values, using Appendix I, reduces

to showing
(V2nl + 2 - V2n1) - (V2n1 + - V2n1 + I)

'§n+I C2n+1,[(2n+1)/2] 22n1+1

22n+1 CZn

 

(l/(2n1+2) - l/(2n1+3))

1+1,[(2n+1)/2]

98

or equivalently,

 

g(2n+1) > g(2nl+1)(2n1+2)(2n1+3){{V1 +l/(2nl+I)

 

- VFW “1'" ~)+{.'(f+ ‘2/(2n1+1'-'-‘1}}

Using the convergent binomial series expansion for each of

the radical terms

 

 

 

{/1 + 1/(2n1+1) - V1 - l/(2n1+1)}-{Vl + 2/(2nl+l) - 1}
_ 1 2 3 . 4
- /(2(2n1+l) )- 3/(8(2nl+1) )+ 5/(8(2n1+l) )- . . . . . . . . .

This is a convergent alternating series of the form

n+1
E (-1) on, where cn+1

of the series must be less than l/Cfi2n1+l)2) Now if we

< cn for every n; hence the sum

assume

(2n + 2) (2n + 3)
1 l 2 1 '

 

2(2nl + 1)2

then

2
4nl - 2nl - 4 z 0 ,

and this is not the case for all n1 2 2. Therefore

 

 

g(2nl + 1)(2n1 + 2)(2n1 + 3){{/1 j 1/(2nl1I) - V1 - l/(2n1+l)}

 

- {/1 + 2/(2n1+l) - 1}}

99

< g(2n1+l) é g(2n+1) for all n 2 2 .

1
If n1 = l,
3/8(4)(5){(/4 - V2) - f(V- - /§)} = .613 < g(2n+1) , n 2 1 .

This proves the inequality for nl + l = n2.

Using Appendix I, define

 

 

 

 

 

 

 

A a (/§fi‘:§ _ “I C2n+L'[(2n+1)/2] 2291+2
an l 22n+l €2n1+21n1+lJ
_ (/§3- _ '2n+I C2n+lJ(2n+l)/2] 2291 )
1 22n+I c2
n,[nl]
V211
- _ _ g32n+l) .. 1
- (V2n1+ V2n1) g(2nl) 2n1:1 .
and
A' E ('2n+I C2n+L[(2n+1)/2] 22n2-1 _ n - )
2n2+l 22n+l C2n2-1[(2n2-1)/2] 2
- ( n+ C2n+1.[(2n+1)/2] 22n2+1 _ in + )
22n+1 CZnZHflKZn2+l)/2] 2
(2n+l) '2n2+I
= (VT—Tn2+ .. @5211) -g_fifiz_+fy'—2—fi-2-q .

u o n I
If an is minimal we have shown that A2nl< A2n2+l'
We would like to show that the chain of inequalities

100

. . , .
continues, (i.e. A2n1+2 < A2n2-1)' by prov1ng that

A2n +2 < A 2n +1 < A2n _1. Using Appendix I and

l 1 2 2

binomially expanding the radical terms, the difference

2n and A'

 

Aan - A2n1+2 = (V2n1+2 - V2nl) - (V2nl+4 - V2n1+2
V25I12 2n1+1 1 1
‘ 9‘2n+1’ 572n1+2) 2n1+2 (23;:I ‘ 23:13

 

 

l + 5 + . ...
(2n1+2)3/2 4(2n1+2)372

 

g(2n+1) l
9 2nl + ) V2n1+2(2n1+3)

By assumption, g(2n1+2) > g(2nl) > g(2n+1) hence

 

 

l (2n+l) 1
2 > .
(2nl-1-2)3/2 g(2%”) V2n1+2(2n1+3)

Therefore Aan - A2n1+2 > 0. Also the d1fference
u _ I = __ _, _ _ _ ..
A2n2-1 A2n2+1 ("inz i ”in2 3) (’2n2+ ”inz I

V2n -I 2n +2
(2n+l) 2 1 - 2 l
g gIZnZ-l) 23; 2n2¥I 2n2+2

— l + 5 +
(2n2-l)372 4(2n2-1)5/2

 

 

101

_ g(2n+1) 2112-l
gl2n2-1)2n2(2n2-I)’

 

. , _ , . .
The des1red result, A2n2_1 A2n2+1 > 0, Will follow if
V2n -l

 

 

g(2n+1) 2 < 1 .
g n2- 2n2(2n2+1) (2n2-1)3/2

But as previously proven,

2n2 2n +1 2n

2 2
g(ZnZ-l) 533:1' 23;:I' > g(2n2-1) 53;:I

 

> V270 > g(2n+1),

for n2 2 2. Repeating the same argument we can prove that

l l ° '
A2n1+4 < A2n2-3’ A2n1+6 < Aan-S , etc. This terminates

the second part of the proof for 2n+l = 6k+l.
If 2n+l = 6k+i, i = 3 or 5, the proofs are similar

to what has been shown above.

Case II. Assume 2nd and Zna are both greater than
1 ‘ 2

(2n+l)/3 where 2n + 1 = 2 2nd + 2 2n

+1, n > O, n > 0,
a
a B

B

n 2 0.

8
Similarly as in the proof of Case I, it is sufficient

to prove only the inequality

102

 

 

 

 

V2n+l C Znal
VT+ ‘63—+ ”___-IZn + ‘ 2n+L[(2n+l)/2] 2
a a 2 2n+l C
l 2 2 2nd,[n ]
1 1
Zna
2 2 22n2+l
+ c + c
2nd,[na ] 2n2+lJ(2n2+l)/2]
2 2
where 2n2 + l = 22nd + 2 2nB + 1 .

' B
a¢al,a2
Now we shall show that the sufficiency condition can

further be reduced to proving only the inequality

V2n+I C 22n1

2n+l,[ (2n+1)/2]
V2nl + V2n2+I < 22n+l C

 

2n1,[nl]

22n2+1

2n2+L[(2n2+l)/2]

+c

where 2nl = 2n + 2n and this is exactly Case I again.
0‘1 0‘2

Suppose nal + no‘2 E 0(mod 2} Then we claim

V2n+I

 

2(/fi—_ C2n+jl[(2n+l)/2] _ 2’11 )
1

2n+l C

2n
0
2 /"—2n _ 2n+1C2n+l.[(2n+1)/2] 2 -1
al 22n+l C2na,[n ]

103

 

2n
,———— '2n+I C2n+1,[(2n+1)/2] 2 “2
+ 2nd - 2n+1 C
2 2 2n ,Cn ]
0‘2 0"2
because if n = n equality holds and if n < n ,

this relation can be rewritten as

which is true (in fact strict inequality) since we have

already proven that for all 2m > (2n+l)/3, A > A

2m+2°
There remains to show the following relation:

2m

 

 

 

/§H— _ '2n+I C2n+1,[(2n+1)/2] 22nl
l 22n+l C2 [ ]
“I 91
> 2 /fi— _ '2n+I C2n+],[(2n+1)/2] _2n1
1 2n+1 C
2 nrlnl/Zl

First note that if ni and nj are even integers

‘where n 2 ni > nj > (2n+l)/3 then

 

 

V257 - n+ C2n+l,[(2n+l)/2] 22ni
1 22n+1 C2n.,[n,]
1 J.
_ 2 /—— _ '2“+I C2n+1,[(2n+1)/2] zni
ni 2n+1 C,
2 nil[ni/2]

104

 

 

 

< /§37 - n+ C2n+l,[(2n+1)/2] zznj )
j 22n+l C2n.,[n.]
J J
'2“+I C2n+1,[(2n+1)/2] znj'
- 2 /KT - 27+1 c
J 2 n nj,[nj/2]

because again the above relation can be rewritten as

Azn.-2+..........+A2n.+..........+An
1 3

< A2nj_2 + ........ + An. + 2(An. + ...... + A:_) .

It is always the case that 2nj> ni. If we assume
the contrary, an < ni < n, then, (2n+l)/3 < nj < n/2 or
n < -2, an impossibility.

2k.

Define 2n + l E 4k + i, i = 1 or 3 and n1

It then suffices to show

 

 

r—' ’1E+1 C4k+i,[(4k+i/2] 24k
4k ' 4k+' C
2 1 4k,[2k]
,—— 'ZE+1C4k+i,[(4k+i)/2] 22k
> 2 2 ' 4k+i C
2 2k,[k]

Assuming i = l, k 2 3 and using Appendix I, the desired

B-

relation above reduces to

4k+l

4k+2

 

g(4k+1) > g(2k) {1 - 1/V2 {1 - V(4k+l)/4k

¥

 

 

105

Substituting for g(2k) its asymptotic representation and

l}

< 2/n {1 - l/8k + 1/128k2 + 73/1440k§}{1 - 1/8/2k (4k_1)

binomially expanding VI 1 I7ZE we have

4k + 1
4k + 2

 

 

 

g(2k) {1 - 1//2 {1 - /(4k+l)/4k

 

 

 

 

 

 

 

 

 

 

2 4k+l 3 4k+l
l/lZB/Ek 4k+2 + 1/1024/Ek ZE$§:}
< /2/n {1 - l/8k 1 + 1//§ (4k_1 + 1/128k2 1 + 1//'(4k_ 3 )

4k+3

IE1? + 73/1440ké}

+ 1/1024/Ek3

 

 

Also

2 - l414/1440ké} .

}}

g(4k+l) > V27n {1 - 3/l6k + 49/4x128k
The difference

4k+1
1k+2

 

 

 

g(4k+1) - g(2k) {1 - 1//7 {1 -/14k+1)/4k

4k-1 4k- 1

Zk+2 ' 1

   

           

 

 

> f27fi 1/16k(/7 + 1/128k3 (

 

 

4k+3
112+?

}

 

 

- l/k3(830/8xl440 + 1/1024/3

 

and using k 2 3,

21/2 ( 1 14/30 1/30 )
> fz7_ + > 0 .
{133k128k2 H33 144k2 128k2

"I"

 

106
If k = 2,
g(9) - g(4){1 - 1//§{1 - /§7§ (9/10)}} = .738 - .726 > o
and if k = l,
g(5) - g(2){l - 1//2{1 - /§7I (5/6)}} = .699 - .673 > o .
This proves the inequality for i = 1. Similarly for i = 3.
If n + n E 1 (mod 2), the proof is similar to

0‘1 0‘2

the proof given above.

BIBLIOGRAPHY

10.

11.

BIBLIOGRAPHY

Littlewood, J. E., and Offord, A. C.: On the number
of real roots of a random algebraic equation (III),
Math. Sbornik (Rec. Math.) N.S. 12 (1943) 277-285.

Erdos, P.: On a lemma of Littlewood and Offord, Bull.
Am. Math. SOC. 51 (1945) 898-902.

Sperner, E.: Ein Satz fiber Untermengen einer endlichen
Menge, Mathematische Zeitschrift 27 (1928) 544-548.

Kleitman, D. J.: On a lemma of Littlewood and Offord
on the distribution of certain sums, Mathematische
Zeitschriff 90 (1965) 251-259.

Katona, G. Y.: On a conjecture of Erdos and a stronger
form of Sperner's theorem, Studia Scientiarum
Mathematicarum Hungarica 1 (1966) 59-63.

Courant, R.: Vorlesungen uber Differential-und In-
tegral rechnung, (1927) 180-181, 287-290.

Schreier, O. and Sperner, E.: Introduction to Modern
Algebra and Matrix Theory, Second Edition, Chelsea
Publishing Company, (1959).

Davis, H. T. and Fisher, V. J.: Tables of the Mathema-
tical Functions, Arithmetic Tables, Vol. III, The
Principia Press of Trinity University, (1962).

Whittaker, E. T. and Watson, G. N.: A course of Modern
Analysis, Fourth Edition, Cambridge University
Press, (1963).

Abramowitz, M., and Stegun, I. A.: Handbook of Mathe-
matical Functions, AMS 55, National Bureau of
Standards, (1968).

Gurland, J.: On Wallis' Formula, The American Mathe-
matical Monthly, Vol. 63 (1956) 643-645.

107

       

HICHIGRN S T

1111111111111“