The Mathematics of Paul Erdös I (Algorithms and Combinatorics)

192

Sergei Konyagin and Carl Pomerance

N(x,y)

;:::

1 v:5x

p$:r.

d(p,v»O

d(1J ,1I)=1

dEV(P,v) «:~;)'fJ;;)~l

L: L: 1 - L: L: 1 L: L:1- L: L:L:1 L: 7r(x, d, 1) L: L: 7r(x, dq, 1).

dEV(P, V) ,l1;~1

>

dEV(p,v) «:~;)'fl;;)l>l

dEV(P,v) JI;~l

(5.3)

dEV(p,v) qEP d:i~"'-l

dEV(P,v)

dEV(P,v) qEP

From (5.2) we have

L:

9 x 7r(x, d, 1) ;::: 10 . -1dEV(P,v) og x

'"

1 (d)

~

(5.4)

cP

dEV(P,v)

if x is sufficiently large. From the Brun-Titchmarsh inequality we have

L: L: 7r(x, dq, 1)« L: L: cp(dq) log(xj(dq)) x

dEV(P,v) qEP

dEV(P,v) qEP

x ('" «logx ~

dEV(P,v)

<

1)", 1 ~q-1

'''(d) Y

L:(

x log x log y

dEV P,v

qEP

1

) cp(d) ,

where we use (5.1) for the last inequality. Putting this estimate and (5.4) into (5.3) we have for all sufficiently large x that

N(x,y);:::

4 x "5' 10 x g

'"

~

dEV(P,v)

cp

1 (d)'

We now estimate this last sum. We have from (5.1) that 1

dE~'V) cp(d)

>

1

L:

dEV(P,v)

1 (

d;:::' V.

L:-ql)V

qEP

exp( -v log v - v log logy + O(v)) 1 1 exp( -3ulogu - 3uloglogy + O(u)) 1

exp( -"3u log log x Putting this in (5.5) we have the theorem.

+ O(u)).

(5.5)

Primes in Deterministic Polynomial Time

193

Proof (of Theorem 5.1). First note that from Theorem 5.2, if k 2: 1 is arbitrary, then the number of primes p ::; x for which p - 1 has a (log x )k-smooth divisor F with F > x l / 3 is at least XI - I /(3k)+o(l) as x -+ 00. For such primes p, Step 1 of Algorithm 5.1 takes at most O((log x)k) arithmetic steps with integers at most p. The number of arithmetic steps with integers at most p to complete Step 2 of Algorithm 5.1 is 0((logp)16/loglogp). It suffices to establish the theorem for values of 10 satisfying 0 < 10 < 1/48. In this case let K > K' > 1/(310) be arbitrary. If p > x l / 3 and c is any constant, then (logp)K > c(logX)K' for all large x. Thus if x is large, p is a prime with p ::; x and p - 1 has a (logx)K'-smooth divisor F > x l / 3, then Algorithm 5.1 takes at most (logp)K steps with integers at most p to prove p prime. By the above, the number of such primes is at least x l - I /(3K')+o(l) for x -+ 00. As 1 - I/(3K') > 1 - 10, the theorem follows.

6. More primes recognizable in deterministic polynomial time In this section we describe a deterministic algorithm that recognizes many more primes in polynomial time than our previous methods. Covered is any prime n with a divisor F of n - 1 exceeding n< and such that all of the prime factors of F are at most (logn)k. The running time is about 0((logn)2/< + (logn)k). We also show that for most such primes, the 2/10 can be reduced to 1/10. A corollary of this algorithm is an improved version of Theorem 5.1. There if we were willing to spend time (logn)k on trying to prove n prime, we would succeed for about x l -(3k)-1 primes up to x. With the methods of this section we will succeed for about x l - k - 2 primes up to x. If n is prime and the order of b in (Z/nZ)* is E, then for any a with aE == 1 mod n, there is some exponent j E {I, 2,···, E} with a == hi mod n. Thus if it is shown that no such j exists, then it is proved that n is composite. How difficult is it to do this test? If we have already_prepared the complete set {hi mod n : j = 1, 2, ... , E}, then testing if there is some j with a == hi mod n can be accomplished by a binary search in O(log E) steps. Thus we have the initial step of preparing the set of powers of b, which takes E steps, and then each subsequent test takes O(log E) steps. In the case when E = qf3 with q prime and (3 2: 1, we can do a precomputation taking q steps, with each subsequent test taking 0((32 log q) steps. Here is how. Suppose the order of b mod n in (Z/nZ)* is qf3. Assuming that we have already computed bqf3 - 1 mod n (if not, this takes an additional O((3logq) steps for the precomputation), we can compute the set

B

. 1'-1

= {lJ.1 q

mod n: j

= 1,··· ,q}

in q steps. Now suppose we are presented with some integer a with the order of a mod n in (Z/nZ)* equal to qo., with 0 ::; a ::; (3, and we wish to see if

194

Sergei Konyagin and Carl Pomerance

there is some integer j with a == fJ3 mod n. If a = 0 or 1, then if j exists it is a multiple of qf3- 1, and so we test for membership of a mod n in B by a binary search. As an induction hypothesis suppose 1 < a ::; f3 and we have already described how to find j for any a' for which the order of a' mod n in (ZjnZ)* properly divides qa. Note that the order of a q mod n is qa-1, so we may use our inductively described algorithm to search for some integer jo with aq == fJ30 mod n. Suppose we have found jo. Then it must be that qf3-(a-1) divides jo and, in particular, qljo. Then ab- jOq - 1 mod n has order dividing q. But we have. already described how in this case we may search for -1 . an integer j1 with ab- JOq == bJ1 mod n. If these searches are successful, we may take j = j1 + jOq-1. Totaling up the time spent, we have used a binary searches in the set B, we have done a-I modular multiplications, and we have done a-I modular powerings with exponents at most qf3 (in fact, at most qf3- 1). The latter computation dominates, taking O(af3logq) = O(f3 2 10gq) arithmetic steps with integers the size of n. The computation of B, which is the precomputation step of this method, we call "Set up (b, qf3)". The subsequent search for an exponent j we call "Test (b, qf3; a)". With these subroutines we are now ready to describe the main algorithm of this section. Algorithm 6.1. We are given positive integers n, F, R and a positive number to such that n > 4, 2 ::; (logn)2/f < n, n - 1 = FR, and F > nf. This algorithm decides if n is prime or composite. Let F(I) = 1. For a = 2,3, ... , f(log n)2/fl do the following. Step 1. Step 2. Step 3.

Step 4.

Step 5. Step 6.

Check if n 'is even or if n is a nontrivial power. If so, declare n composite and stop. Verify that a n - 1 == 1 mod n holds. If not, declare n composite and stop. Compute E(a), the order of a R mod n in (ZjnZ)*. Let F(a) = lcm{E(a) , F(a -I)}. For each prime qlF(a)jF(a - 1), verify that (aRE(a)/q -1,n) = 1 holds, declaring n composite and stopping if not. For each prime q and positive integers a, f3 with qall(E(a), F(a-l)) and q f3 IIF(a -1) do Test (b q ,qf3;aRE (a)q-"'). If this test proves n composite, then declare this and stop. . For each prime q and positive integer f3 with qlF(a)jF(a -1) and qf3llF(a), let bq = a RE (a)q-1i mod n and do Set up (b q , qf3). If F(a)loga > nloglogn, declare n prime and stop. Ifa < f(log n)2/fl, get the next a. If a = f(log n)2/fl, declare n composite and stop.

Proof (of correctness). Suppose we have made it to Step 6 and a = f(logn)2/fl Suppose n is prime. From Theorem 2.1 we have #gn(a) > n 1- f/ 2. Every bE gn(a) satisfies b(n-1)F(a)/F == 1 mod n, so #gn(a) ::; (n - I)F(a)jF < n 1- f F(a). Thus F(a) > nf/2, so that F(a)loga > nloglogn. Hence it is correct to declare n composite when this inequality fails.

Primes in Deterministic Polynomial Time

195

Suppose n is composite and suppose we have made it to Step 6 for a particular a. From Step 1 we know that n is divisible by at least two distinct odd primes. From Step 3 we know that each prime factor of n is 1 mod F(a). Let F = {b mod n : bn - 1 == 1 mod n}. By the Chinese remainder theorem, this subgroup of (ZjnZ)* is isomorphic to the direct product of the groups Fp = {b mod p'" : bn - 1 == 1 mod p"'} where p'" runs over the prime powers with p"'lln. Since p is an odd prime, (Zjp"'Z)* is cyclic so that #Fp = (n1,ip(p"')) = (n - 1,p - 1). Thus for each prime power q!3 with q!3IIF(a) we have q!3I#Fp. Since n has at least two distinct prime factors p, the number of b mod n E F with bqil == 1 mod n is at least q2!3. From Step 2, 9 n (a) is a subgroup of F. And from Step 4 we have that 9n(a) has exactly q!3 members b mod n with bqil == 1 mod n. Thus the index of 9n (a) in F is at least the product of the prime powers q!3 with q!3IIF(a), which is F(a). We have from Theorem 2.1 that nl-iogiogn/ioga < #9 (a) < _1_ II(n - 1 p - 1) < ~ n - F(a) , F(a)' pin

so that F(a) < niogiogn/ioga. Hence it is correct to declare n prime when F(a)ioga > niogiogn. This concludes the proof of correctness.

Analysis of runtime. For each integer k :::; log nj log 2 we can check if n is a kth power by computing [nl/k] with a binary search and seeing if [n1/k]k = n. When k 2': 3, the binary search may begin with [n1/(k-1l Thus the number of arithmetic operators to see if n is a k-th power is O( iOf log n), so the total number of arithmetic operations for Step 1 is O(log n(log log n )2). The time for Step 2 is at most O((logn)1+2/€). For each a, the time for Step 3 is 0 (log n log log n). Thus the total time for Step 3 is O((logn)1+2/€ log log n). As we have seen, each implementation of Test (b q , q!3 j a) in Step 4 takes time OCB 2 10g q). Thus the total time for Step 4 is o ((log n)2+2/€). Each time we do Set up (b q , q!3) in Step 5, it takes time O(q + ,B log q). Thus if D is the total number of prime factors of F, counted with multiplicity, and if each prime factor q of F satisfies q :::; B, then the total time for Step 5 is O(BD + D 2 10gn) = O(B logn + (log n)3). Thus the total number of arithmetic steps with integers at most n is O((logn)2+2/€ + Blogn). We have the following theorem. Theorem 6.1. On input of positive integers n, F, R and a positive number E with n > 4, 2 :S (logn)2/€ < n, n - 1 = FR and F > n€, Algorithm 6.1 correctly decides if n is prime or composite. The running time is O((logn)2+2/€ + Blogn) arithmetic steps with integers at most n, where B is the largest prime factor of F.

196

Sergei Konyagin and Carl Pomerance

We remark that the term (log n)2+2/e in the running time may be replaced with €(logn)2+2/e/loglogn if we perform Steps 2 to 4 only for prime values of a. The time bound in Theorem 6.1 is only an upper bound. With the aid of the next result we will be able to show that most primes for which Algorithm 6.1 is applicable are proved prime in a considerably shorter time.

:s :s

:s

Theorem 6.2. For 2 y x let R(x, y) denote the number of primes x such that (Z/pZ)* is not generated by the set p in the range y < p {a modp: 1:S a:S y}; that is, such that Qp([Y]) i- (Z/pZ)*. Then R(x,y) < 8x2log log(3?)/ log y • Proof. Let Z denote the set of y-smooth numbers up to x 2 • Suppose p is a prime counted by R(x,y). Then #Qp([Y]) divides (p-1)/q for some prime q. Thus the set Z occupies at most (p-1)/q residue classes mod p, so there are at least p/2 residue classes mod p free of elements of Z. Thus by the large sieve (see Theorem 3, p. 159 in [8]) we have

4x 2 . - "2' R(x,y)

#Z<

1

Thus from Theorem 2.1 we have R(x,y)

:s

8x 2

8x 2

#Z = 'ljJ(x 2 ,y) < 8x2IogI0g(x2)/logy,

(6.1)

which completes the proof of the theorem. Because of the use of Theorem 2.1 in the proof, Theorem 6.2 is only fairly good when y is a power of log x. If we let v = 2 log x/log y and use a stronger estimate for 'ljJ(x 2 , y) (see [7]) we may obtain the following result which is valid in the same range as is Theorem 6.2: R(x, y)

:s exp(v(log v + log log v - 1 + (log log v -

1)/ log v)

+ O(v(log log v/ logv)2)). This estimate is implicit in the dissertation of Pappalardi [13, Section 3.3]. The estimate has an inexplicit constant, though an actual numerical value could be provided in principle. We remark that Vinogradov, Linnik and Fridlender have discussed problems related to the estimation of R(x, y). Theorem 6.3. Let x, € > 0 be arbitrary and let E(x, €) denote the number of primes p with (logp)2/e < p x for which there is some integer F > pe with Flp - 1 and such that if Algorithm 6.1 is run on n = p, F, €, then F(a)loga ploglogp for a = r(logp)l/el. Then E(x, €) < 9x 3e + e32 .

:s

:s

Primes in Deterministic Polynomial Time

197

Proof. Suppose Algorithm 6.1 is run on n = p, F, f where Flp-1 and F > pE. If F(a) = F with a = r(logp)l/El, then F(a)loga > ploglogp. Thus we may assume that if p is counted by E(x, f), then F(a) < F with a = r(logp)l/El. Thus (Z/pZ)* is not generated by {j mod p: 1 ~ j ~ a}. We conclude from Theorem 6.2 that E(x, f) - E(xl/2, f)

< R(x, r(logx 1/ 2)1/El) < R(x, (logxl/2)1/E) < 8X2E log log(x 2)/ log log(Xl/2) .

Note that if x ~ e32 , then loglog(x2)/loglog(xl/2) ~ 3/2. Thus if k is 2- k 32 2-(k-l) that positive integer with x <e ~x then k-l

E(x, f)

I)E(x T i , f) - E(X 2- i -

1

,

f))

+ E(x 2-

k

,

f)

i=O

k-l

< L8(x 2- i )3E+E(e 32 ,f) i=O

< 9X 3E + e32 , which concludes the proof of the theorem. We remark that Theorem 6.2 can also be used in the context of Algorithm 4.1 to give a small improvement in that algorithm for most primes. We now give an algorithm similar to Algorithm 5.1.

Algorithm 6.2. Suppose we are input a positive number f and an integer n > 4 with 2 ~ (logn)2/E < n. This algorithm attempts to decide ifn is prime or composite. Step 1.

Using trial division, find the largest divisor F of n - 1 composed of primes up to (logn)l+l/E. If F ~ n E, then stop for the algorithm has failed. Step 2. Use Algorithm 6.1 on n, F, f, terminating with failure if the parameter a exceeds r(log n)l/El. From the proof of Theorem 5.2, for each number f with 0 < f < 1, there is a number X2(f), such that if x ~ X2(f), the number N of primes p ~ x for which p - 1 has a (logp)l+l/E-smooth divisor exceeding pE satisfies N > 2xl-e2 • For such primes p we make it past Step 1 of Algorithm 6.2. From Theorem 6.3 we have that if 0 < f ~ 1/4, then at least half of these primes a.re proved prime in Step 2 of Algorithm 6.2, though X2(f) may have to be adjusted. We thus have the following result.

Theorem 6.4. Let f be any number with 0 < f ~ 1/4. There is a number X2(f) such that if x 2: X2(f) then the number of primes p ~ x which Algorithm 6.2 proves prime exceeds x 1 - E2 .

198

Sergei Konyagin and Carl Pomerance

We remark that the running time of Algorithm 6.2 is O((logn)2+1/E) arithmetic steps with integers at most n. Thus Theorem 6.4 improves on Theorem 5.1 since there if one wants to prove prime x 1- E2 primes up to x, the bound for the running time is about (logn)1/(3E 2).

References 1. L. M. Adleman and M.-D. Huang, Primality testing and abelian varieties over finite fields, Lecture Notes in Mathematics 1512, (1992), Springer-Verlag, Berlin. 2. W. R. Alford, A. Granville, and C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. 140 (1994), 703-722. 3. W. Bosma and M.-P. van der Hulst, Primality proving with cyclotomy, Ph.D. thesis, Amsterdam (1990). 4. J. Brillhart, M. Filaseta, and A. Odlyzko, On an irreducibility theorem of A. Cohn, Can. J. Math. 33 (1981) 1055-1099. 5. J. Brillhart, D. H. Lehmer and J. L. Selfridge, New primality criteria and factorizations of 2m ± 1, Math. Compo 29 (1975) 620-647. 6. J. P. Buhler, R. E. Crandall and M. A. Penk, Primes of the form n! ± 1 and 2·3·5·· . p ± 1, Math. Compo 38 (1982) 639-643. 7. E. R. Canfield, P. Erdos and C. Pomerance, On a problem of Oppenheim concerning "factorisatio numerorum", J. Number Theory 17 (1983) 1-28. 8. H. Davenport, Multiplicative number theory, 2nd ed., Springer-Verlag, New York,1980. 9. P. Erdos and J. H. van Lint, On the number of positive integers :S: x and free of prime factors> y, Simon Stevin, 40 (1966/67) 73-76. 10. M. R. Fellows and N. Koblitz, Self-witnessing polynomial-time complexity and prime factorization, Designs, Codes and Cryptography, 2 (1992) 231-235. 11. A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovasz, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982) 515-534. 12. H. W. Lenstra, Jr., Miller's primality test, Information Processing Letters 8 (1979), 86-88. 13. F. Pappalardi, On Artin's conjecture for primitive roots, Ph.D. thesis, McGill University, (1993). 14. J. Pintz, W. L. Steiger and E. Szemeredi, Infinite sets of primes with fast primality tests and quick generation of large primes, Math. Compo 53 (1989) 399-406. 15. C. Pomerance, Very short primality proofs, Math. Compo 48 (1987) 315-322. 16. V. R. Pratt, Every prime has a succinct certificate, SIAM J. Comput. 4 (1975) 214-220. 17..J. B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962) 64-94. 18. R. Solovay and V. Strassen, A fast Monte Carlo test for primality, SIAM J. Comput. 6 (1977) 84-85; erratum 7 (1978), 118. 19. I. M. Vinogradov, On the bound of the least non-residue of nth powers, Bull. Acad. Sci. USSR 20 (1926) 47-58 (= Trans. Amer. Math. Soc. 29 (1927), 218226).

Ballot Numbers, Alternating Products, and the Erd8s-Heilbronn Conjecture Melvyn B. Nathanson Department of Mathematics, Lehman College (CUNY), Bronx, New York 10468

1. Introduction Let A be a subset of an abelian group. Let hA denote the set of all sums of h elements of A with repetitions allowed, and let h" A denote the set of all sums of h distinct elements of A, that is, all sums of the form al + ... + ah, where all ... ,ah E A and ai =I- aj for i =I- j. Let A be a set of k congruence classes modulo a prime p. The CauchyDavenport theorem states that 12AI ::::: min(p, 2k - 1), and, by induction, IhAI ::::: min(p, hk - h + 1) for every h ::::: 2. Erdos and Heilbronn conjectured 30 years ago that 12" AI ::::: min(p, 2k - 3). They did not include this conjecture in their paper on addition of residue classes [lOJ, but Erdos has frequently mentioned this problem in lectures and papers (for example, Erdos-Graham [9, p. 95]). Dias da Silva and Hamidoune recently prove this conjecture. They used linear algebra and the representation theory of the symmetric group to show that Ih" AI ::::: min(p, hk - h2 + 1) for every h ::::: 2. The purpose of this paper is to give a complete and elementary exposition of this proof. Instead of representation theory, we will use the combinatorics of the h-dimensional ballot numbers.

2. Multi-dimensional ballot numbers The standard basis for Rh is the set of vectors {el, ... , eh}, where

200

Melvyn B. Nathanson

e2

(1,0,0,0, ... ,0) (0,1,0,0, ... ,0)

eh

(0,0,0, ... ,0,1).

el

The lattice Zh is the subgroup of Rh generated by the set {el,'" ,eh}, so Zh is the set of vectors in Rh with integral coordinates. Let

a = (ao,al, ... ,ah-t) E Zh and b

= (bo,bl, ... ,bh-l) E Zh.

A path in Zh is a finite sequence of lattice points a

= Yo, Vl, ... , Vm = b

such that Vj -Vj-l

E {el, ... ,eh}

for j = 1, ... , m. Let Vj-l, Vj be successive points on a path. We call this a step in the direction ei if Vj

= Vj-l + ei.

The vector a is called nonnegative if ai 2:

°for i = 0,1, ... , h - 1. We write

a:Sb if b - a is a nonnegative vector. Let P( a, b) denote the number of paths from a to b. The path function P(a, b) is translation invariant in the sense that P(a + c, b

+ c) = P(a, b)

for all a, b, c E Zh. In particular, P(a, b)

= P(O, b - a).

The path function satisfies the boundary conditions

P(a,a) = 1, and P(a, b) > If a

= Yo, Vi, ... , Vm = b

°if and only if a:S b,

is a path, then

for some i = 1, ... , h, and there is a unique path from b - ei to b. It follows that the path counting function P( a, b) also satisfies the difference equation

Ballot Numbers, Alternating Products, Erdos-Heilbronn Conjecture

201

h-I

P(a, b) =

L P(a, b -

ei).

i=O Let a :::; b. For i = 0, 1, ... , k -1, every path from a to b contains exactly bi - ai steps in the direction eH I. Let h-I

m = L(bi i=O

-

ai).

Every path from a to b has exactly m steps, and the number of different paths is the multinomial coefficient

P(a, b) =

(2:~OI(bi h-I

m!

ai))!

ni=O (b i - ai)!

=

h-I

ni=o (b i - ai)!

.

(2.1)

Let h 2': 2. There are h candidates in an election. The candidates will be labelled by the integers 0,1, ... ,h - 1. Suppose that mo votes have already been cast, and that candidate i has received ai votes. Then

mo = ao

+ al + ... + ah-I·

We shall call Vo = a = (ao, al, ... ,ah-I)

the initial ballot vector. There are m remaining voters, each of whom has one vote, and these votes will be cast sequentially. Let Vi,k denote the number of votes that candidate i has received after k additional votes have been cast. We represent the distribution of votes at step k by the ballot vector Vk

= (VO,k,VI,k, ... ,Vh-l,k)'

Then VO,k

for k

+ VI,k + ... + Vh-I,k

= k + mo

= 0,1, ... ,m. Let Vm

= b = (bo, bl, ... , bh-I)

be the final ballot vector. It follows immediately from the definition of the ballot vectors that for k

= 1, ... ,m, and so a

= Yo, VI, ... ,Vm = b

is a path in Zh from a to b. Therefore, the number of distinct sequences of m 'votes that can lead from the initial ballot vector a to the final ballot vector b is the multinomial coefficient

202

Melvyn B. Nathanson

Let v = (Vi, ... , Vh) and w = (Wi' ... ' Wh) be vectors in Rh. The vector v will be called increasing if

and strictly increasing if

Now suppose that the initial ballot vector is a = (0,0,0, ... ,0)

and that the final ballot vector b = (b o, bi> . .. ,bh-i) is nonnegative and increasing. Let m = bo + bi + ... + bh - i . Let B(bo, bi , ... , bh-d denote the number of ways that m votes can be cast so that all of the k-th ballot vectors are nonnegative and increasing. This is the classical h-dimensional ballot number. Observe that

B(O,O, ... ,O)

=1

and B(b o, bi> . .. ,bh-i) >

°

if and only if (b o, bi , ... ,bh-d is a nonnegative, increasing vector. These boundary conditions and the difference equation h-i B(bo, bi , ... , bh- i ) =

L B(bo, ... , b

i - i , bi -

1, bi +1, ... , bh-d

i=O

completely determine the function B(b o, bi> ... ,bh-d. There is an equivalent combinatorial problem. Suppose that the initial ballot vector is a* = (0,1,2, ... ,h - 1), and that the final ballot vector

is nonnegative and strictly increasing. Let h-i m = t;(b i

t; b (h)

h-i -

i) =

i -

2 .

Ballot Numbers, Alternating Products, Erdos-Heilbronn Conjecture

203

Let B(bo , bl , ... , bh-l) denote the number of ways that m votes can be cast so that all of the ballot vectors Vk are nonnegative and strictly increasing. We shall call this the strict h-dimensional ballot number.. A path Yo, Vi> •.. , Vm in Zh will be called strictly increasing if every lattice point Vk on the path is strictly increasing. Then B(bo, bi> ... , bh-l) is the number of strictly increasing paths from a* to b = (b o , ... , bh-t). The strict h-dimensional ballot numbers satisfy the boundary conditions

B(O, 1, . .. ,h - 1)

=1

B(b o, bl ,· .. ,bh-t}

>0

and if and only if (bo, bl , ... , bh-l) is a nonnegative, strictly increasing vector. These boundary conditions and the difference equation h-l

B(bo, bi>"" bh-t} =

L B(bo, ... , bi-i> b

i -

1, bi +1,"" bh-l)

i=O

completely determine B(bo , bi> ... ,bh-l). There is a simple relationship between the h-dimensional ballot numbers B(bo , bi>' .. ,bh-l) and B(b o, bi>' .. , bh- l ). The lattice point v = (vo, Vi> ... , Vh-t) is nonnegative and strictly increasing if and only if the lattice point v'

=v

- (0,1,2, ... , h -1)

=v

- a*

is nonnegative and increasing. It follows that

is a path of strictly increasing vectors from a* to b if and only if 0, Vi

-

a*, V2

-

a*, ... , b - a*

is a path of increasing vectors from 0 to b - a*. Thus, B(b o, bl

, ... ,

bh-l) = B(b o, bl

-

1, b2

-

2, ... , bh-l - (h - 1)).

For 1 ::; i < j ::; h, let Hi,i be the hyperplane in R h consisting of all vectors (Xl, ... ,xn ) such that Xi = Xi' There are (~) such hyperplanes. A path will be called intersecting if there exists at least one vector such that Vk E Hi,i for some hyperplane Hi,j. . The symmetric group Sh acts on Rh as follows: For a (vo, Vi,"" Vh-l) E Rh, let

Vk

E

on the path Sh and v

=

204

Melvyn B. Nathanson

(J'V

=

(Vu(o) , V u (l),""

Vu (h-l»)'

A path is intersecting if and only if there is a transposition T = (i,j) E Sh such that TVk = Vk for some lattice point Vk on the path. Let lea, b) denote the number of intersecting paths from a to b. Let J(a, b) denote the number of paths from a to b that do not intersect any of the hyperplanes Hi,j. Then

pea, b) = lea, b)

+ J(a, b).

Lemma 2.1. Let a be a lattice point in zh, and let b = (b o, . .. ,b h - l ) be a strictly increasing lattice point in Zh. A path from a to b is strictly increasing if and only if it intersects none of the hyperplanes Hi,j, and so B(bo, ... ,bh-d = J(a*, b). Proof. Let a

= Yo, Vi, ... , Vm = b Vk

=

be a path, and let

(VO,k,Vl,k, •.. ,Vh-l,k)

for k = 0,1, ... , m. If the path is strictly increasing, then every vector on the path is strictly increasing, and so the path does not intersect any of the hyperplanes Hi,j. Conversely, if the path is not strictly increasing, then there exists a greatest integer k such that the lattice point Vk-l is not strictly increasing. Then 1 :s; k :s; m, and Vj,k-l

:s; Vj-l,k-l

for some j = 1, ... , h - 1. Since the vector Vj-l,k

Since

Vk-l

and

Vk

:s; Vj,k

Vk

-

is strictly increasing, we have

1.

are successive vectors in a path, we have Vj-l,k-l

:s; Vj-l,k

1

:s; Vj,k-l.

and Vj,k -

Combining these inequalities, we obtain Vj,k-l

:s; Vj-l,k-l :s; Vj-l,k :s; Vj,k

-

1 :s;

Vj,k-l·

This implies that Vj,k-l

=

Vj-l,k-l

and so the vector Vk-l lies on the hyperplane H j - l ,j' Therefore, if b is a strictly increasing vector, then a path from a to b is strictly increasing if and only if it is non-intersecting, and so J(a, b) is equal to the number of strictly increasing paths from a to b. It follows that J(a*, b) is equal to the strict ballot number B(b o, ... ,bh-l). This completes the proof.

Ballot Numbers, Alternating Products, Erdos-Heilbronn Conjecture

205

Lemma 2.2. Let a and b be strictly increasing vectors. Then P(O'a, b)

for every

0'

E Sh, 0'

= [(O'a, b)

=I id.

Proof. If a is strictly increasing and if 0' E Sh, 0' =I id, then O'a is not strictly increasing, and so every path from O'a to b must intersect at least one of the hyperplanes Hi,j' This completes the proof. Lemma 2.3. Let a and b be strictly increasing lattice points. Then

L

e:(O')[(O'a, b)

= O.

UESh

Proof. Since a is strictly increasing, it follows that there are h! distinct lattice points of the form O'a, where 0' E Sh, and none of these lattice points lies on a hyperplane Hi,j' Let {l be the set of all intersecting paths that start at any one of the n! lattice points O'a and end at b. We shall construct an involution from the set {l to itself. Let 0' E Sh, and let O'a = Vo, vI, ... , Vm

=b

be a path that intersects at least one of the hyperplanes. Let k be the least integer such that Vk E Hi,j for some i < j. Then k 2: 1 since a is strictly increasing, and the hyperplane Hi,j is uniquely determined since Vk lies on a path. Consider the transposition T = (i,j) E Sh. Then TVk

= Vk E Hi,j, =I O'a,

TO'a

and

TO'a = TVo, TV1, ... ,TVk = Vk, Vk+I, ... ,Vm = b is an intersecting path in {l from Taa to b. Moreover, k is the least integer such that a lattice point on this new path lies in one of the hyperplanes, and Hi,j is still the unique hyperplane containing Vk. Since T2 is the identity permutation for every transposition T, it follows that if we apply the same mapping to this path from TO'a to b, we recover the original path from O'a to b. Thus, this mapping is an involution on the set {l of intersecting paths from the h! lattice points O'a to b. Moreover, if 0' is an even (resp. odd) permutation, then an intersecting path from O'a is sent to an intersecting path from TO'a, where T is a transposition and so TO' is an odd (resp. even) permutation. It follows that the number of intersecting paths that start at even permutations of a is equal to the number of intersecting paths that start at odd permutations of a. This means that

L aESh «,,)=1

[(O'a,

b)

=

L aESh «,,)=-1

This statement is equivalent to the Lemma.

[(O'a,

b).

206

Melvyn B. Nathanson

Let [X]k denote the polynomial x(x - 1)··· (x - k nonnegative integers, then

+ 1).

bi(bi - l)(b i - 2) ... (b i - u(i)

[bi]O"(i) =

{bi!j(bi - u(i))!

o

If bi, u(i) are

+ 1)

if u(i) ::::; bi if u(i) > bi.

Theorem 2.1. Let h ;::: 2, and let bo, b1, ... , bh- 1 be integers such that

0::::; bo < b1 < ... < bh- 1. Then A

B(bo, b1, ... , bh-l) =

(b o + b1 + ... + bh- 1 - (~))! b 'b , ... b , o· 1· h-l·

II

O~i<j~h-l

(bj - bi).

Proof. Let a* = (O,1,2, ... ,h -1), and let b = (bo,b1, ... ,bh-d E Zh. Applying the previous lemmas, we obtain B(b o, h, ... , bh-d = J(a*,b) P(a*, b) - J(a*, b) P(a*,b)

+

L

c(u)J(ua*,b)

uESh (:T'::pid

P(a*, b)

+

L

c(u)P(ua*, b)

nESh

n=#id

L

c(u)P(ua*, b)

(b o + ... + bh - 1 - (~))! bo!h!'" bh- 1!

(b o + ... + bh- 1 - (~))!

.

L

c(u) [bo]O"(o) [b1]0"(1) ... [bh-1]0"(h-l)

O"ESh

1 1

[boh [b1h

[boh [bd2

1

[bh-1h

[bh-lh

bo!b1!··· bh- 1! (b o + ...

+ bh-l - e))!

II O~i<j~h-l

(b j

-

bi).

[bO]h-l [b1]h-l

Ballot Numbers, Alternating Products, Erdos-Heilbronn Conjecture

207

This completes the proof. We state the following corollary with the notation that is used later in the proof of the Erdos-Heilbronn conjecture. Corollary 2.1. Let h be integers such that

~

2, let P be a prime number, and let io, ii, ... , ih-l

o :::; io < i l < ... < ih-l < P and

.. + + ... .

Zo

Zl

Zh-l

(h)

< 2 + p.

Then B(io, ill' .. , ih-t) ¢. 0

(mod p).

Proof. This follows immediately from the Theorem.

3. A review of linear algebra Let V be a finite-dimensional vector space over a field F, and let T : V -+ V be a linear operator. Let I : V -+ V be the identity operator. For every nonnegative integer i, we define Ti : V -+ V by l(v) = v, T (Ti-l(v))

for all v E V. To every polynomial p(x) = cnx n + Cn_1X n -

l

+ ... + C1X + Co

we associate the linear operator p(T) : V p(T)

-+

E F[x]

V defined by

= CnTn + cn_1Tn - l + ... + CiT + Col.

The set of all polynomials p(x) such that p(T) = 0 forms a nonzero, proper ideal J in the polynomial ring F[x]. Since every ideal in F[x] is principal, there exists a unique monic polynomial PT(X) = PT,v(X) E J such that PT(x) divides every other polynomial in J. This polynomial is called the minimal polynomial of T over the vector space V. A subspace W of V is called invariant with respect to T if T(W) ~ W, that is, if T(w) E W for all wE W. Then T restricted to the subspace W is a linear operator on W with minimal polynomial PT,w(x). Since PT,v(T)(w) = o for all w E W, it follows that PT,W(X) divides PT,v(x), and so deg(PT,w) :::; deg(PT,v) ,

where deg(p) denotes the degree of the polynomial p.

(3.1)

208

Melvyn B. Nathanson

For v E V, the cyclic subspace with respect to T generated by v is the smallest subspace of V that contains v and is invariant under the operator T. We denote this subspace by CT(V). Let Vi = Ti(v) for i = 0,1,2, .... Then CT(V) is the subspace generated by the vectors {v, T(v), T2(V), T 3 (v), ... } = {Yo, v!, V2, V3, ... } and dim(CT(v))

= l,

where l is the smallest integer such the vectors Yo, VI, ... ,VI are linearly dependent. This means that there exist scalars eo, CI, ... ,Cl-I in the field F such that Let

p(x) = xl

+ CI_IX I- 1 + ... + CIX + co.

Then

p(T)(vo)

+ CI_ITI-I(vo) + ... + cIT(vo) + eoI(vo) VI + Ci-IVI-I + ... + CIVI + eovo

TI(VO) 0,

and so

p(T)(Vi) = p(T)(Ti(vO)) = Ti (p(T)(vo)) = Ti(O) = 0

°

for i = 0,1,2, .... Therefore, p(T) = on the cyclic subspace CT(V) so p(x) is divisible by the minimal polynomial PT,c(X) , and m

= deg (PT,C)

::; deg(p)

= C, and

= l.

On the other hand, since

PT,c(T)(v) = 0, it follows that the vectors Yo, v!, ... ,Vm are linearly dependent, and so

l ::; m. This implies that l

= m and so, by inequality (3.1), dim(CT(v))

= deg(PT,c)::; deg(PT,v)

for all v E V. If T(f) = af for some a E F and some nonzero vector f E V, then a is called an eigenvalue of T and f is called an eigenvector of T with eigenvalue a. The spectrum of T, denoted a(T), is the set of all eigenvalues of T. If V has a basis consisting entirely of eigenvectors of T, then T is called a diagonal

operator. The following inequality plays a central role in the proof of the ErdosHeilbronn conjecture.

Ballot Numbers, Alternating Products, Erdos-Heilbronn Conjecture

209

Lemma 3.1. Let T be a diagonal linear operator on a finite-dimensional vector space V, and let aCT) be the spectrum ofT. Then

dim (CT(v» :S la(T)1

(3.2)

for every v E V. Proof. Let a E aCT), and let f be an eigenvector with eigenvalue a. Let W be the one-dimensional subspace generated by f. Then W is invariant with respect to T, and PT, W (x) = x-a. It follows that x - a divides PT, v (x), and so (x - a)

II

aEu(T)

divides PT,V(X). Let dim (V) = k. If T is a diagonal linear operator, then V has a basis {fo, fI, ... , fk-l} of eigenvectors, and

II

(T - a)(fi)

=0

aEu(T)

for i = 0,1, ... , k - 1. It follows that and so PT,V(X) =

a)(v)

TIaEu(T)(T -

II

=0

for all v E V,

(x - a).

aEu(T)

In particular, the degree of PT,v(x) is equal to the number of distinct eigenvalues of T. It follows that, if T is a diagonal operator on a finite-dimensional vector space V, then dim (CT(V» :S deg(PT,v)

=

la(T)1

for every v E V. This completes the proof. Lemma 3.2. Let T : V - t V be a linear operator on the vector space V, and let {fo, f l , ... , fk-r} be eigenvectors ofT with distinct eigenvalues. Let

Vo = fo

+ fl + ... + fk- 1,

and let CT(VO) be the cyclic subspace generated by Yo. Then

dim (CT(VO» = k and

{Yo, T(vo), T 2 (vo), ... , Tk-l(vo)} is a basis for CT(VO). If dim(V)

= k,

then CT(VO)

= v.

210

Melvyn B. Nathanson

Proof. We first show that the vectors f o, f 1 , ... , f k - 1 are linearly independent. If they are linearly dependent, then there is a minimal subset of the vectors fo, ... , f k - 1 that is linearly dependent, say, fo, ... , fl- 1. Moreover, l :2: 2 since fi =I- 0 for i = 0, 1, ... , k - 1. There exist nonzero scalars Co, Cl, ... , CI-1 such that I:~:~ Cifi = O. Let ai E a(T) be the eigenvalue corresponding to the eigenvector f i . Then

Since

1-1

1-1

LCial-1fi = al-1 LCifi = 0, i=O

i=O

it follows that

1-1 L

1-2 Ci(ai - al-1)fi

=L

i=O

Ci(ai - al-1)fi

= 0,

i=O

which contradicts the minimality of l, since Ci(ai - al-1) =I- 0 for < l - 1. Thus, the vectors fo, ... , fk-1 are linearly independent, and span a k-dimensional subspace W of V. Moreover, W is an invariant subspace, since it has a basis of eigenvectors of T. Since

i

Vo = f1

+ ... + fk

E W,

it follows that and so dim (CT(VO)) ::; dim(W)

= k.

The vector Ti(VO) E CT(VO) for every nonnegative integer i. Since Ti(vO)

= abfo + aif1 + ... + aL1fk-1,

the matrix of the set of vectors {Yo, T(vo), T 2(vo), ... , T k - 1 (vo)} with respect to the basis {fo, ... , fk-d is

...

a k-1 k- 1

and its determinant is the Vandermonde determinant

IT O~i<j~h

(aj - ai) =I- O.

Ballot Numbers, Alternating Products, Erdos-Heilbronn Conjecture

211

It follows that {Yo, T(vo), T2(vO), ... , Tk-i(vO)} is a set of linearly independent vectors, and so dim (CT(VO)) ~ k = dim(W). Therefore, dim (CT(VO)) pletes the proof.

=

k. If dim(V)

=

k, then CT(VO)

= V. This com-

4. Alternating products Let !\hV denote the h-th alternating product of the vector space V. Then is a vector space whose elements are linear combinations of expressions of the form !\ h V

Vo !\ Vi !\ ... !\ Vh-i,

where

Yo, Vi, ... , Vh-i E

V. These wedge products have the property that Vo !\ Vi !\ •.. !\ Vh-i

if Vi

= Vj for some i

= 0

i= j, and

V".(O) !\ V".(i) !\ ... !\ V".(h-i)

= c(a)vo!\ Vi !\ ... !\ Vh-i

for all a E Sh. If {eo, ... ,ek-t} is a basis for V, then a basis for !\hV is the set of all wedge products of the form

where

o :::; io < i i < ... < ih-i

and

dim(!\hV) = Every linear operator T : V

--+

:::;

k - 1,

(~).

V induces a linear operator h

h

DT:AV--+AV that acts on wedge products according to the rule

DT(Vio

!\ ... !\ Vih_l)

=

(4.1)

h-i LVio!\···!\ Vij_l !\

T(Vij)!\

j=O

The operator DT is called the derivative of T.

ViHl···!\ Vih_l.

(4.2)

212

Melvyn B. Nathanson

Lemma 4.1. Let T be a diagonal linear operator on V, and let a(T) be the spectrum of T. For h ~ 2, let DT : /\ h V -+ /\ h V be the derivative of T. If T has distinct eigenvalues, that is, if la(T)1 = dim(V), then

a(DT)

=

hl\a(T)

and (4.3) for every

W E

I\hV.

Proof. Let a(T) = {ao,al, ... ,ak-d, and let {fO,fl, .. ·,fk-l} be a basis of eigenvectors of V such that T(fi) = aifi for i = 0,1, ... , k - 1. Then (4.1) implies that DT(fio 1\ .. . 1\ f ih _ 1 ) = (aio

+ ... + aih_J(fio 1\ ... 1\ f ih _

1 ).

It follows that DT is a diagonal linear operator on I\hV, and its spectrum a(DT) consists of all sums of h distinct eigenvalues of T, that is, a(DT)

= hl\a(T).

Applying inequality (3.2) to the vector space I\hV and the operator DT, we obtain Ihl\a(T)1 = la(DT)1 ~ dim (CDT(W)) for every

W E

1\ h V.

This completes the proof.

Theorem 4.1. Let T be a linear operator on the finite-dimensional vector space V. Let h ~ 2, and let DT : I\hV -+ I\hV be the derivative ofT. For Vo E V, define

for i

~

1, and let

Then for every r

~

0

(DT)T(W)

(DTr(vo 1\ VI 1\ ... 1\ Vh-l)

L B(io, il,""

ih-l)Vio 1\ vit 1\ ... 1\ Vih_l'

where the sum is over all integer lattice points (io,il,'" ,ih-l) that o ::; io < il < ... < ih-l ::; r + h - 1 and

.. + + ... + .

20

21

2h-l

=

E Zh

such

(h) + r, 2

and where B(i o, it, ... , ih-l) is the strict h-dimensional ballot number corresponding to the lattice point (io,il, ... ,ih-l).

Ballot Numbers, Alternating Products, Erdos-Heilbronn Conjecture

213

Proof. The proof will be by induction on r. Let r = O. Since

.8(0,1,2, ... ,h - 1) = 1 , we have

(DT)o(w)

w Vo /\ Vi /\ ... /\ Vh-l

.8(0,1,2, ... , h - l)vo /\ Vi /\ ... /\ Vh-l.

o. Then

Suppose the result holds for some integer r ::::

(DTt+l(W) = DT ((DTt(w))

= DT (E .8(io, it, ... ,ih-l)Via

/\ ViI /\ ... /\ Vi h_ l )

= E .8(io, il,···, ih-dDT (Via

/\ ViI /\ ... /\ Vih_l)

h-l

= E .8(io, il,···, ih-d L

(Via /\ ... /\ Vij_l /\ T(Vij) /\ Vij+l /\ ... /\ Vih_l)

j=O

=L

h-l .8(io, il, ... , ih-l)

L

(Via /\ ... /\ Vij_l /\ Vij +1/\ Vij+l /\ ... /\ Vih_l)

j=O

= E C( io, it, ... ,ih-l)Via

/\ ViI /\ ... /\ Vih_l'

where the last sum is over all integer lattice points (io,il, ... ,ih-l) E Zn such that o ::; io < i l < ... < ih-l ::; r + h and io

+ il + ... + ih-l =

G) +

r

+ 1,

and the integer C(io, il, ... , ih-l) satisfies the difference equation

h-l C(io, it, ... , ih-d =

L .8(io, ... , ij-l, ij -

1, ij+l, ... , ih-l).

j=O

This difference equation determines the strict h-dimensional ballot numbers, and so C(io, i l , ... , ih-d = .8(io, i l ,···, ih-l). Therefore, the result holds in the case r

+ 1.

This completes the induction.

214

Melvyn B. Nathanson

5. Erdos-Heilbronn, concluded Theorem 5.1. Let p be a prime number, and let A Let 2 ~ h ~ k. Then Ihl\ AI 2:: min(p, hk - h 2

~

Z/pZ, where IAI = k.

+ 1).

Proof. Let A = {aO,a1, ... ,ak-1}. Let V be a vector space of dimension k over the field Z/pZ, and let {fo, f1, ... , fk-1} be a basis for V. We define the diagonal linear operator T : V ----> V by

for i

= 0,1, ... , k

- 1. The spectrum of Tis

a(T)

= A.

Let

Vo

= fo + f1 + ... + fk-1,

and define Vi+!

= T(Vi) = Ti(vO)

for i 2:: O. By Lemma 3.2, the cyclic subspace generated by Vo is V, and the set of vectors {Yo, Vb ... , vk-d is a basis for V. The alternating product /\ h V is a vector space with a basis consisting of the (~) wedge products of the form where

o ~ io < i1 < ... < ih-1 Let

~

k - 1. h

W = Vo /\ VI /\ ... /\ Vh-I E /\ V. By inequality (4.3), Ihl\ AI = la(DT)1 2:: dimCDT(w). Therefore, it suffices to prove that dimCDT(w)

2:: min(p, hk - h 2 + 1).

This is equivalent to proving that the vectors

are linearly independent in the alternating product /\ h V, where n

= min(p, hk -

h2

+ 1) -

1

= min(p -

1, hk - h 2 ).

Ballot Numbers, Alternating Products, Erdos-Heilbronn Conjecture

215

Let 0 :::; r :::; n. By Theorem 4.1, the vector (DTt(w) is a linear combination of the vectors such that

o :::; io < i 1 < ... < ih-1

and

.. + + ... + .

to

t1

th-1

=

:::;

+h -

r

1

(h) + r.

(5.1)

2

Let I be the interval of integers [0, k - 1]. Since

it follows that there is at least one basis vector expansion of (DTt (w) such that

Vio /\ ViI /\ ... /\ Vih_l

o :::; io < i1 < ... < ih-1 :::; k and io

+ i 1 + ... + ih-1 =

(~) + r :::;

in the

1 < k :::; p

G) +

n

<

(~) + p.

By Theorem 4.1, the coefficient of this basis vector is the strict h-dimensional ballot number B(io, it, •.. , ih-1), and

by Corollary 2.l. Suppose that the vector Vio /\ Vii /\ ... /\ Vih_l satisfies il 2': k for some t. Since every vector VI E V with t 2': k is a linear combination of vo, V1,·.·, Vk-1, it follows that Via /\ Vii /\ ... /\ Vih_l is a linear combination of basis vectors of the form Vjo /\ vit /\ ... /\ Vjh_l' where

o :::; jo < j1 < ... < jh-1 and

:::;

k- 1

.. + + ... + . < (h) +

Jo

J1

2

Jh-1

r.

It follows that (DTt(w) is a linear combination of basis vectors ... /\ Vih_l such that either

or

.. + + ... + .

to

t1

th-1

=

Vio /\ Vii /\

(h) + r, 2

and in the latter case the basis vector appears with a coefficient that is nonzero modulo p. This implies that the vectors w, (DT)(w), ... , (DT)n(w) are linearly independent in the cyclic subspace CDT(W), and the proof of the Erdos-Heilbronn conjecture is complete.

216

Melvyn B. Nathanson

6. Remarks This proof only requires that A be a subset of a field, and does not require that the field be ZjpZ. Let F be an arbitrary field. Let p be the characteristic of F if the characteristic is positive, and let p = 00 if the characteristic is zero. Then we have, in fact, proved that if A ~ F and IAI = k ~ p, then Ih'\ AI ~ min(p, hk - h2 + 1) for all h ~ 1. The Cauchy-Davenport theorem was proved by Cauchy [3] in 1813. Davenport [5] rediscovered the result in 1935. I. Chowla [4] immediately extended the Cauchy-Davenport theorem to composite moduli. Other generalizations have been obtained by Pillai [14], Shatrovskii [20], Pollard [15, 16], Brakemaier [2], and Hamidoune [12]. Davenport [6] discovered in 1947 that Cauchy had proved the Cauchy-Davenport theorem first. The Erdos-Heilbronn conjecture originated in the 1960's. Partial results on the Erdos-Heilbronn conjecture were obtained by Rickert [18], Mansfield [13], ROdseth [19], Pyber [17], and Freiman, Low, and Pitman [11]. Dias da Silva and Hamidoune [8] proved the conjecture by using results from representation theory and linear algebra. This algebraic technique had previously been applied to additive number theory by Dias da Silva and Hamidoune [7] and Spigler [21]. The derivation of the formula for the strict ballot number B(bo, . .. , bn - 1 ) follows a paper of Zeilberger [22]. Using combinatorial ideas from the proof of Dias da Silva and Hamidoune, Alon, Nathanson, and Ruzsa [1] found a different proof of the Erdos-Heilbronn conjecture that uses only the simplest properties of polynomials.

References 1. N. Alon, M. B. Nathanson, and I. Z. Ruzsa. Adding distinct congruence classes modulo a prime. Amer. Math. Monthly, 102, 1995. 2. W. Brakemeier. Eine Anzahlformel von Zahlen modulo n. Monat. Math., 85:277-282, 1978. 3. A. L. Cauchy. Recherches sur les nombres. J. Ecole polytech., 9:99-116, 1813. 4. I. Chowla. A theorem on the addition of residue classes: Application to the number r(k) in Waring's problem. Proc. Indian Acad. Sci., Section A, i:242243, 1935. 5. H. Davenport. On the addition of residue classes. J. London Math. Soc., 10:3032, 1935. 6. H. Davenport. A historical note. J. London Math. Soc., 22:100-101, 1947. 7. J. A. Dias da Silva and Y. O. Hamidoune. A note on the minimal polynomial of the Kronecker sum of two linear operators. Linear Algebra and its Applications, 141:283-287, 1990. 8. J. A. Dias da Silva and Y. O. Hamidoune. Cyclic spaces for Grassmann derivatives and additive theory. Bull. London Math. Soc., 26:140-146, 1994.

Ballot Numbers, Alternating Products, Erdos-Heilbronn Conjecture

217

9. P. Erdos and R. L. Graham. Old and New Problems and Results in Combinatorial Number Theory. L'Enseignement Mathematique, Geneva, 1980. 10. P. Erdos and H. Heilbronn. On the addition of residue classes mod p. Acta Arith., 9:149-159, 1964. 11. G. A. Freiman, L. Low, and J. Pitman. The proof of Paul Erdos' conjecture of the addition of different residue classes modulo prime number. In Structure Theory of Set Addition, 7-11 June 1993, CIRM Marseille, pages 99-108, 1993. 12. Y. O. Hamidoune. A generalization of an addition theorem of Shatrowsky. Europ. J. Combin., 13:249-255, 1992. 13. R. Mansfield. How many slopes in a polygon? Israel J. Math., 39:265-272, 1981. 14. S. S. Pillai. Generalization of a theorem of Davenport on the addition of residue classes. Proc. Indian Acad. Sci. (Series A), 6:179-180, 1938. 15. J. M. Pollard. A generalization of a theorem of Cauchy and Davenport. J. London Math. Soc., 8:460-462, 1974. 16. J. M. Pollard. Additive properties of residue classes. J. London Math. Soc., 11:147-152, 1975. 17. L. Pyber. On the Erdos-Heilbronn conjecture. personal communication. 18. U.-W. Rickert. Uber eine Vermutung in der additiven Zahlentheorie. PhD thesis, Tech. Univ. Braunschweig, 1976. 19. O. ROdseth. Sums of distinct residues mod p. Acta Arith., 65:181-184, 1993. 20. L. Shatrovskii. A new generalization of Davenport's-Pillai's theorem on the addition of residue classes. Doklady Akad. Nauk CCCR, 45:315-317, 1944. 21. R. Spigler. An application of group theory to matrices and to ordinary differential equations. Linear Algebra and its Applications, 44:143-151, 1982. 22. D. Zeilberger. Andre's reflection proof generalized to the many-candidate ballot problem. Discrete Math., 44:325-326, 1983.

Integer Sets Containing no Solution to x+y=3z Fan R. K. Chung! and John L. Goldwasser 2 1 2

University of Pennsylvania, PA 19104 West Virginia University, Morgantown, WV 26506

Summary. We prove that a maximum subset of {1, 2, ... , n} containing no solutions to x + y = 3z has ~ 1 elements if n =I- 4, thus settling a conjecture of Erdos. For n 2: 23 the set of all odd integers less than or equal to n is the unique maximum such subset.

r

1. Introduction Many classical problems in computational number theory focus upon subsets S of positive integers with the property that for all x, y, z in S, we have x+y =I- kz, for a fixed positive integer k. The history can be dated from 1916, when Schur [5], in work related to Fermat's Last Theorem, proved that the set of positive integers cannot be partitioned into finitely many sum-free sets, i.e., sets having no solution to x+y = z. This result is a Ramsey-type theorem which predates Ranlsey's Theorem. In 1927, van der Waerden [9] considered subsets having no solution to x + y = 2z, or in other words, subsets containing no three-term arithmetic progression. His celebrated theorem states that the positive integers cannot be partitioned into finitely many subsets each of which contains no k-term arithmetic progressions. In 1952, Roth proved that a set of positive upper density contains three-term progressions [4]. This was improved by Szemeredi to four-term progressions [7] and later to the general k-term progressions [8]. A problem which appears in several undergraduate combinatorics texts is to show that a maximum subset of {1, ... , n} containing no solutions to x + y = z (x, y, z not necessarily distinct) has size ~ 1- In section 2 of this paper we find all such subsets and prove the following theorem:

r

Theorem 1.1. A maximum subset of {1, ... , n} containing no solution to x + y = z (x, y, z not necessarily distinct) has size ~ 1. If n 2: 3 is odd there are precisely two maximum subsets: the odd integers less than or equal to nand { x E Z I ~ x n}. If n 2: 4 is even there are at least three maximum subsets: { x E Z I ~ x n} and the two maximum subsets for the odd number n - 1. For even n 2: 10 these three are the only ones. For smaller even numbers, {1,4}, {2,5,6}, {1,4,6}, and {2,3, 7,8} are the only additional ones.

r

:s :s :s :s

Let t*(n, 2) denote the maximum size subset of {1, ... ,n} containing no threeterm arithmetic progressions (such subsets contain no solutions to x + y = 2z, but now, for the problem to make sense, x, y, z are distinct). Roth first showed [4] that

t*(n,2)

=0(1

~

og og n

).

The current best bounds are, for appropriate absolute constant

Ci,

Integer Sets Containing no Solution to x

ne-Cl~ < j*(n, 2) <

+y=

3z

219

C2n (log n)C3

where the lower bound was proved by Salem and Spencer [6) (see also Behrend [1)), and the upper bound was proved by Heath-Brown and Szemeredi [3). Erdos conjectured that a maximum subset of {I, ... , n} having no solutions to x + y = 3z (x, y, z not necessarily distinct) has size no more than a small constant more than ~ 1. In section 3 we verify this conjecture by proving the following theorem:

r

Theorem 1.2. Let Tn be a subset of {I, ... ,n} of maximum size such that x+y = 3z has no solutions with x, y, z E Tn (x, y, z not necessarily distinct). If n =f. 4 then I Tn 1= r~l· In section 4 we show that for sufficiently large n there is a unique maximum such subset:

Theorem 1.3. If n ~ 23 and Tn is a subset of maximum size of {I, ... , n} having no solutions to x + y = 3z then Tn is the set of all odd integers less than or equal to n.

r

We use the standard notation 1 and l J for least integer not less than and greatest integer not greater than, respectively. For a and b nonnegative integers we let [a, b) denote the set of all integers x such that a S x S b.

2. Maximum sum-free sets of {I, ... ,n} Proof (of Theorem 1.1). First we show the maximum size is always r~l Let Un be a maximum sum-free subset of {I, ... ,n} and let p be the largest integer in Un. Then at most one integer in each of the pairs (i, p - i), i = 1,2, ... , r~l is in Un, so I Un Is r~l s r~l Clearly, there are subsets which attain this bound, so I Un 1= r~l To characterize the maximum subsets we consider two cases depending on the parity of n.

Case 2.1 (n odd). Let n ~ 5 be the smallest odd integer such that there exists a maximum sum-free subset Un of {I, ... ,n} which is not the odd integers less than or equal to n or [~, n]. Clearly n E Un (or else I Un Is rn;11 < r~l ), so if n - 1 f/. Un then, by the minimality of n, either Un is the set of all odd integers less than or equal to n (which is impossible by assumption) or Un = [n;l, n - 2] U{n} which is impossible since n;l + ~ = n. So we can assume n -1 and n are in Un. Let G be the graph with vertex set

V = {viliE [2,n;3]U[~, n-2]} of size n-4 where {Vi,Vj} is an edge of G if and only if i + j = n or i + j = n - 1. Then G is the path V n -2, V2, V n -3, V3, .•. , v~, Vntl (with an odd number of vertices). Since n - 1 and n are in Un, 1 and n;l are not, so the other n;3 integers in Un must be the indices of an independent set of vertices in G (Le., no two of them adjacent). The only sufficiently large independent set in G is the maximum independent set which has indices [~, n - 2], so Un = [~, n].

220

Fan R. K. Chung and John L. Goldwasser

Case 2.2 (n even). If n 2:: 4 is even and n f/. Un, then certainly Un must be one of the two maximum subsets for the odd integer n - 1. It is easy to check that the statement in the theorem about when n is 4,6, or 8 is correct. Let n 2:: 10 be the smallest even integer such that there exists a maximum sum-free subset Un of {I, ... ,n} which contains n but is not [~ + 1, n]. If n - 1 f/. Un, we let Un -2 = Un n[l, n-2], so that 1 Un-2 1 = n;2. Un-2 cannot be the odd integers less than or equal to n-3 because 3+(n-3) = n. And Un-2 cannot be [n;2, n - 3] or [~, n - 2] because ~ f/. Un. So Un- 2 cannot be any of the three kinds of maximum subsets for even n described in the theorem. So by the minimality of n we would have to have n = 10 and Un -2 = {2, 3, 7, 8}. This cannot be because 2 + 8 = 10. Hence, as with the odd case, n - 1 and n are both in Un. Now let H be the graph with vertex set V = {Vi 1 i E [2, n;2] U [nt2, n - 2]} of size n - 4 where {Vi, Vj} is an edge of H if and only if i + j = n or i + j = n - 1 or {i,j} = {n-2, n;2}. Then H is the cycle Vn-2,V2,Vn-3,V3, ... ,Vnt2,v9. Since n -1 and n are in Un, 1 and ~ are not, so the other n;4 integers in Un must be the indices of an independent set of vertices in H. There are two possibilities: [2, n;2] and [~, n - 2]. If n 2:: 10 the first of these cannot occur because it contains 2 and 4 (If n = 6 the first possibility gives us {2, 5, 6} while if n = 8 it gives {2,3, 7,8}.). So we have Un = [~+ 1, n] which completes the proof.

3. The Size of a set with no solution to x

+y

= 3z

We observe that if Tn is a set containing no solutions to x + y = 3z and if wE Tn, then ~w, ~w, ~w, and 2w cannot be in Tn (because x, y, z need not be distinct).

Proof (of Theorem 1.2). The set of all odd integers less than or equal to n has no solutions to x + y = 3z so 1Tn 12:: r~l It is easy to check that 1Tn 1= r~l for n = 1,2,3,5 (There are three ways to choose Ts: {I, 3, 4}, {I, 3, 5}, or {I, 4, 5}. The first of these shows that 1T4 1= 3.) So it remains to show 1Tn I::; r~l for n 2:: 6. Let n be the smallest integer greater than or equal to 6 such that 1Tn I> r~ 1. We can assume n is even and n E Tn (otherwise n - 1 is a smaller counter-example). Case 3.1. Tn has no integer x such that ~ most

rl¥1

of the integers in [1,

l ~ J]

< x ::;

2;. By the minimality of n at

are in Tn provided

l ~ J =I 4.

So

if n = 0 or 2 (mod 6) if n = 4 (mod 6) . So we are done if n =I 4 (mod 6) and l~ J =I 4. If l~ J = 4 then n = 12 or n = 14 and the respective candidates for a set of size greater than ~ are {I, 3, 4, 9,10,11, 12} and {I, 3, 4, 10, 11, 12, 13, 14}. However, neither is acceptable because 1 + 11 = 3·4. It remains only to consider n = 6k+4 (k = 1,2,3, ... ), in which case the candidate for a counter-example is to choose k + 1 of the integers in [1, 2k + 1] and all the integers in [4k + 3, 6k + 4]. If 2k + 1 f/. Tn then more than half of the first 2k integers are in Tn, so 2k = 4, n = 16, and the candidate is {I, 3, 4,11,12,13,14,15, 16}

Integer Sets Containing no Solution to x

+ y = 3z

221

which fails again because it contains 1,4, and 11. So 2k + 1 E Tn and 6k + 3 is a forbidden sum. Since [4k + 3, 6k + 2] ~ Tn it follows that Tn n [1, 2k] = 0. This is impossible since k + 1 of the first 2k + 1 integers are in Tn.

Case 3.2. Tn has an integer x such that ~

<x S

2;.

2;

x <

In fact x of since n E Tn. Assume x is the largest integer in Tn such ~ < 23n . Then the integers in W = [3x - n, n] can be arranged in pairs as follows:

(3x - n

+ j,

n - j)

j=O,I,2, ... n-

r3;1

Since the sum of the integers in each pair is 3x, at most one integer from each pair can be in Tn. If x is even then I W I is odd and one of the pairs is (3;, 3;). In this case Tn contains at most ~ (I WI-I) integers from Wand, by the minimality of n, at most n-I~I+l integers from [1,3x - n - 1]. So I Tn Is ~. If x is odd, then I W I is even and at most ~ I W I integers from W can be in Tn. So at most ~ (n- I W I) integers from [1, 3x - n - 1] can be in Tn provided 3x - n - 1 of 4. So we are done except for the possibility that 3x - n = 5. In this case one of the pairs of integers in W is e"2- l , 3":}l) = (~, ~). Since x is the largest integer in Tn which is less than and since x = ~ < ~ < ~, we must have ~ > (so that one integer in this pair can be in Tn). Solving this gives n < 18. Since n ~ 6, the only possibilities are n = 10, x = 5 and n = 16, x = 7. The first of these is impossible because n E Tn but Tn cannot contain both 5 and 10. For the second possibility, since 7 E Tn certainly 14 !/. Tn so the only candidate is {I, 3, 4,7,11,12,13,15, 16}. But Tn cannot contain 1, 4, and 11 so the proof is complete.

2;

2;

4. Maximum sets with no solutions to x

+y

= 3z

Choosing lots of smaller integers to go into a set Tn which has no solutions to x + y = 3z clearly eliminates some of the larger integers from inclusion. If the smaller included integers follow a simple pattern it may be possible to get a simple description of the eliminated larger integers. Lemma 4.1. Let w be an odd integer greater than or equal to 3. 1fT is a set which contains no solutions to x + y = 3z and if T contains all odd positive integers less than or equal to w, then T contains no even integer less than 3w.

Proof. The result is easy to verify for w = 3. If w less than 3w, then (precisely) one of the integers v where t is an odd number less than or equal to w.

~

5 and v is any even number 3t

+ 1, v + 3, v + 5 is equal to

In proving Theorem 1.3 we will make frequent use of the maximum size subsets of {I, ... , n} with no solutions to x + y = 3z for n S 22. We have calculated them all and display them for even n between 6 and 22 inclusive. To get all such maximum subsets for n = 2p - 1 for p = 3, 4, ... ,11, just choose the ones for n = 2p which do not include the integer 2p.

Fan R. K. Chung and John L. Goldwasser

222

I

I

n

6 8

10 12 14

16

18 20 22

Tn 134 145 1347 1567 2567 1 458 134710 137910 147910 13471012 1 3 9 10 11 12 13 1 3 9 10 11 12 14 1 3 4 10 12 13 14 1 3 4 7 10 12 13 16 3 4 7 11 12 13 15 16 1 3 4 7 12 13 15 16 1 3 7 11 12 13 15 16 1 3 4 12 13 14 15 16 17 1 3 4 13 14 15 16 17 18 19 1 3 4 13 14 15 16 17 18 20 1 3 4 7 10 12 13 16 19 21 22 1 3 4 15 16 17 18 19 20 21 22

156 256 1568 2568 1678 2678 178910 278910 378910 1391011 12 1 3 10 11 12 13 14 3 4 10 11 12 13 14 1 3 4 12 13 14 15 16 1 3 11 12 13 14 15 16 3 4 11 12 13 14 15 16 1 3 4 13 14 15 16 17 18 1 3 4 14 15 16 17 18 19 20 1 3 5 15 16 17 18 19 20 21 22 1 4 5 15 16 17 18 19 20 21 22

Table 4.1. Maximum subsets of 1, ... , n with no solutions to x + Y 6 ~ n ~ 22 (except the set of all odd integers less than or equal to n).

3z for

Proof (of Theorem 1.3). Suppose the theorem is false and let n ~ 23 be the smallest counter-example with Tn a subset of {I, ... , n} of size r~l which contains an even integer. It is easy to see that 23 cannot be added to any of the maximum subsets of {I, ... , 22} listed in the table without producing a solution to x + Y = 3z, so n ~ 24. By the minimality of the counter-example we can assume n is even and n E Tn. We divide the proof into cases (and subcases) along the lines of the proof of Theorem 1.2.

2;.

Case 4.1. Tn has no integer x such that ~ < x ~ Let y be the largest integer in Tn such that y ~ ~. Then 3y is a forbidden sum and at most one member of each pair (i,3y - i) i = 1,2, ... , y can be in Tn. Since Tn has no integers strictly between y and 2y n 2' = ITnl ~ y + 1[3y,nli = n - 2y + 1. So, y ~

li{n + 2)J

and, since Tn n [Y

~ ~

ITn

n [1,yli

+ 1, l2; J] = 0,

+ril

+ril In;6J+ril·

~ r~l ~

(if y

# 4)

The only even solutions greater than 22 for this inequality are n = 26, 28, 34 with corresponding values y = 7, 7, 9 respectively. If n = 34 and y = 9 then Tn must

Integer Sets Containing no Solution to x

+ y = 3z

223

contain five of the first nine integers, which (see Table) must be {I, 3, 5, 7, 9}, and everything in [23, 34]. Since 24 + 3 = 3·9 this cannot happen. If y = 7 and n = 26 or n = 28, then Tn contains everything in [18, 26] or [19, 28] respectively. But 7 E Tn, so 21 is a forbidden sum, and, since 19 and 20 are in Tn (in both cases), neither 1 nor 2 can be in Tn. Since four of the first seven positive integers must be in Tn this is a contradiction (see Table). If y = 4, then ITn n [1, y]1 could be as much as 3 in the above inequalities, but ~ ~ 3 + r~ 1 has no solutions for n ~ 24. So Case 1 cannot occur.

Case 4.2. Tn has an integer y such that n

2n

-3
(4.1)

Let x be the largest integer in Tn satisfying (4.1). Then 3x is a forbidden sum and the integers in W = [3x - n, n] can be arranged in pairs (l3;' J - i, 3;, 1+ i) i = 0, 1, ... , n - r3;' 1 such that the sum of the integers in each pair is 3x. If x is even then 3;, is paired with itself. All other pairs (for x even or odd) have distinct integers.

r

If x is even then, because of the above pairing,

(4.2) But by Theorem 1.2, (4.3) Since n-I~I+1 + 1WJ-1 = ~, equality must hold in (4.2) and (4.3). So Tn contains precisely one integer out of each pair of distinct integers above. And Tn n [1, 3xn - 1] must be a maximum subset of [1, 3x - n - 1] containing no solutions to x +y = 3z. If x is odd then IWI is even, so Tn must contain precisely one integer out of each pairofW and T n n[l, 3x-n-l] = 3"'-;-1, unless 3x-n-l = 4. If3x-n-l = 4 then it would be possible to have Tn n [1, 4] = {I, 3, 4} and Tn contain precisely one integer from all but one of the pairs and no integer from that one pair.

Subcase 4·21.

r "'t 1 ~ in. 3

1

If x is even then both integers of the pair (3;' - 1, 3;, + 1) are less than or equal to in. Since x is the largest integer in Tn which is less than or equal to in, neither integer in this pair is in Tn which is a contradiction. If x is odd, neither integer in the pair (l 3;, J, 3;, 1) can be in Tn, which again is a contradiction unless 3x - n - 1 = 4. But since n ~ 24

r

3x + 3 2

so neither integer in the pair 2a cannot occur.

(L 32'" J -

= n +8 < 2

1,

r

3;:

~n - 3

1+ 1)

can be in Tn either, so subcase

224

Fan R. K. Chung and John L. Goldwasser

Subcase 4.22. Assume the two following inequalities:

r3X :

11 > ~n

(4.4)

and

3x - n> 23

(4.5)

Since Tn n [1, 3x - n - 1] is a maximum subset of [1, 3x - n - 1] containing no solutions to x + y = 3z and since 23 ~ 3x - n - 1 < n, by the minimality of n as a counter-example, Tn n [1, 3x - n - 1] must be the set of all odd integers less than or equal to 3x - n - 1. By Lemma 1, Tn contains no even integer less than or equal to 68, so n ~ 70. If x is even, then inequality (4.4) becomes

4n-6 x>-9-·

(4.6)

And 3x - n - 1 is odd so, by Lemma 1, Tn contains no even integers less than or equal to 3(3x - n - 1) - 1, which by (4.6) is greater than n - 10. If x is odd then (4.4) becomes 4n-3 (4.7) x>-9and Tn contains no even integers less than or equal to 3(3x - n - 2) - 1 which by (4.7) is also greater than n - 10. So Tn contains at most five even integers, and hence there are at most five odd integers less than n which are not in Tn. Let mi = 2 ~ 1 + 2i - 1 and Pi = 3mi - n, i = 1, 2, ... , 11. It is easy to check that {md and {Pi} are each sets of 11 distinct odd integers less than or equal to n and clearly not both mi and Pi can be in Tn for any i = 1, ... ,11. Hence there are at least six odd integers less than n which are not in Tn, which shows subcase 2b cannot occur.

r

Subcase 4.23. Inequality (4.4) holds but (4.5) does not.

Hence

1 1< n 3x + 2 r12 -n< 3 2- - -+ 2

(4.8)

from which it follows that n ~ 70. So only a finite number of possibilities remain to be checked, and this could be done one by one (by hand or computer). We prefer to avoid this by considering the following possibilities. 4. 23(i}. Assume (4.8) holds and also assume

r?!:l3 + 3 <- x <- ?!:2

(4.9)

If x is even, inequality (4.8) simplifies to

4n - 6 < n+ 22 - 9 - < x - -3-

(4.10)

And if x is even then, as we showed before, ITnn[1, 3x-n-1]1 = 3"';n. By inequality (4.9), 3x - n -1 ~ 9 > 5, so 3x - n -1 E Tn. Since Tn n [x + 1, L2; J] = 0, we must have [3x - L2; J + 1, 2x - 1] ~ Tn, since these integers are each paired with an excluded integer in the pairing of [3x - n, n] we discussed before (3x - L2; J might not be in Tn because it might be equal to 3;). But 3(3x - n - 1) is a forbidden

+y=

Integer Sets Containing no Solution to x

3z

225

2:

sum so Tn n [7x - 3n - 2, 6x - 3n + L J - 4] = 0. Let a = 7x - 3n - 2, b = 6x - 3n + L J - 4, and c === 3x - n - 1. With x satisfying (4.9) and (4.10) it is easy to check that a ~ 0 and c ~ 9. Since Tn n [a, b] = 0 and c E Tn we certainly have a contradiction if a :S c :S b. We also have a contradiction if a :S b < c and b - a + 1 ~ c - b + 2 because then

2:

c+1 -2-

= ITn n [l,c]1 :S

ITn

n [l,a -Ill + (c -

b)

~ +c-b

2 c-1 -2-'

Hence we have a contradiction if the conditions a :S c and 2b satisfied, i.e., if n + 3 < x < 2n + 1.

_l2nJ 3

-

-

~ a

+ c + 1 are both

4

But that is precisely our assumption in (4.9). If x is odd then inequality (4.8) simplifies to 4n-3 n+23 -9-<-3-

(4.11)

2:

and the argument is similar. In this case it turns out that [3x - L J, 2x - 1] ~ Tn and that 9x - 3n - 3 or 9x - 3n - 6 is a forbidden sum, but we still get a contradiction with inequality (4.9).

4.23{ii}. Assume (4.8) holds and x >

%.

If x is even there are eight ordered pairs of values for n ~ 24 and x which satisfy (4.8) when x> %. We list them as triples (n,x,3x - n -1):.

(24, (26, (26, (28,

14, 14, 16, 16,

17) 15) 21) 19)

(30, (32, (34, (38;

16, 18, 18, 20,

17) 21) 19) 21)

Since ITn n [1, 3x - n - 1]1 = 3"';n we see (by the Table) that if 3x - n - 1 is equal to 21 or 15 then Tn must contain all the odd integers less than or equal to 15 and (by Lemma 1) no even integers at all. That eliminates four triples. Since 3x - n - 1 E Tn and X is the largest integer in Tn less than we cannot have That eliminates three more triples, leaving ·only (24, 14, 17). x < 3x - n - 1 :S If 3x - n - 1 = 17, then 15 E Tn (by the Table). But x = 14 < 15 :S ~ ·24, so we get a contradiction here as well. If x is odd there are ten such triples (n, x, 3x - n - 1):

2:,

2:.

(24, (24, (26, (28, (28,

13, 15, 15, 15, 17,

14) 20) 18) 16) 22)

(30, (32, (34, (36, (40,

17, 17, 19, 19, 21,

20) 18) 22) 20) 22)

We will show just the argument for (32, 17, 18) here. Since l 2; J = 21, we must have Tn n [18,21) = 0. Since ITn n [1,18)1 = 9, by the Table (or by Theorem 2) 17 must

226

Fan R. K. Chung and John L. Goldwasser

be in Tn. Also, ITn n [22,32]1 must be 7. Since 51 is a forbidden sum, at most one integer in each of the pairs (22,29), (23,28), (24,27), (25,26) is in Tn. By the Table 15 E Tn, so 30 E Tn, which means ITn n [22,32]1 ::; 6 a contradiction. The other nine triples can be disposed of with similar (and mostly simpler) arguments.

4. 23 {iii}.

Assume (4.8) holds and x

<

r~l

+ 3.

The only possibility here is n = 28 and x = 12. Then 3x-n = 8, so ITnn[l, 7]1 = 4 and Tn contains precisely one member of each pair (18 - i, 18 + i) i = 1,2, ... ,10. Since L J = 18, Tn n [13,18] = 0, so [19, 23] ~ Tn. But 21 is a forbidden sum, so neither 1 nor 2 can be in Tn. This is a contradiction since (by the Table) if ITn n [1,7]1 = 4, either 1 or 2 must be in Tn.

2;

5. Related problems and remarks For k a positive integer not equal to 2, let f(n, k) be the maximum size of a subset S of {I, ... , n} such that there are no solutions to x + y = kz with x, y, z (pot necessarily distinct) integers in S (the problem does not make sense for k = 2). In this paper we determined f(n, 1) and f(n, 3) for all n and found all maximum such subsets. The determination of f(n, k) when k ;::: 4 has a very different flavor, and we have some results in this direction [2]. Let g(t) be the maximum "size" (appropriately defined) of a subset S of the closed interval [0,1] having no solutions to x + y = tx where t is a fixed positive number. Finding g(k) is a continuous analog of finding f(n, k). It turns out there is a strong connection between these problems if k ;::: 4, but not for k = 3. For k = 1 we remark that the maximum set [L ~ J,n] of Theorem 1 does have a continuous analog, while the set of all odd integers less than or equal to n does not. In [2] we show that if k ;::: 3 then the positive integers can be partitioned into finitely many subsets each of which has no solutions to x + y = kz. For k any positive integer, let f*(n, k) be the maximum size of a subset of {I, ... ,n} having no solutions to x + y = kz where x, y, z must be distinct. Clearly, f(n, k) ::; f*(n, k). It is easy to show that f*(n,l) = 1- There are many values of n for which f(n,3) is smaller than f*(n, 3). For example, the set [1,4] U [12,18] shows that f*(n,3) ;::: 11. However, we join Paul Erdos in conjecturing that r(n,3) = f(n,3) = r~l for sufficiently large n. We also suspect there is a unique maximum set for sufficiently large n. One could do some computer work to obtain some information as to the likelihood of this conjecture being correct. To get a proof one could follow the lines of our proofs in this paper. Unfortunately, the minor inconvenience of f( 4,3) being greater than 2 would become the major headache of (n, 3) being greater than ~ 1 for many small values of n. Of course the problem of narrowing the bounds for f*(n, 2) is one of the'most intriguing problems in combinatorics.

rnr

r

r

References 1. F. A. Behrend, On sets of integers which contain no three in arithmetic progression, Proc. Nat. Acad. Sci. 23 (1946), 331-332. 2. F. R. K. Chung and J. L. Goldwasser, Maximum subsets of (0, 1] with no solutions to x + y = kz, preprint.

Integer Sets Containing no Solution to x

+y

= 3z

227

3. D. R. Heath-Brown, Integer sets containing no arithmetic progressions, The Journal of the London Math. Soc. 35 (1987), 385-394. 4. K. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 104-109. 5. I. Schur, Uber die Kongruenz xm + ym = zm (mod p), J. ber. Deutch. Math. Verein. 25 ( 1916), 114-116. 6. R. Salem and D. C. Spencer, On sets of integers which contain no three terms in arithmetical progressions, Proc. Nat. Acad. Sci. USA 28 (1942), 561-563. 7. E. Szemen§di, On sets of integers containing no four elements in arithmetic progression, Acta. Arith. 20 (1969), 89-104. 8. E. Szemeredi, On sets of integers containing no k elements in arithmetic progression, Acta. Arith. 27 (1975), 199-245. 9. B. L. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw Arch. Wisk 15 (1927), 212-216.

On Landau's Function g(n) Jean-Louis Nicolas Mathematiques, Batiment 101, Universite Claude Bernard (LYON 1), F-69622 Villeurbanne cedex

1. Introduction Let Sn be the symmetric group of n letters. Landau considered the function g(n) defined as the maximal order of an element of Sn; Landau observed that

(cf. [5]) g(n)

= max

where the maximum is taken on all the partitions n = of n and proved that, when n tends to infinity logg(n)

(bl)

lcm(m1, ... ,mk)

I'J

In log n.

m1

+ m2 + ... + mk (1.2)

S.M. Shah in 1938 determined two more terms in the above asymptotic expansion (cf. [16]), and I do not know any other paper about g(n) before the sixties. A nice survey paper was written by W. Miller in 1987 (cf. [9]). One may add two more recent references: [7] and [8].1 My very first mathematical paper (cf. [11]) was about Landau's function, and the main result was that g(n), which is obviously non decreasing, is constant on arbitrarily long intervals. First time I met A. Schinzel in Paris in May 1967. He told me that he was interested in my results, but that P. Erdos would be more interested than himself. Then I wrote my first letter to Paul with a copy of my work. I received an answer dated of June 121967 saying"1 sometimes thought about g(n) but my results were very much less complete than yours". Afterwards, I met my advisor, the late Professor Pisot, who, in view of this letter, told me that my work was good for a thesis. The main idea of my work about g(n) was to use the tools introduced by S. Ramanujan to study highly composite numbers (cf. [14]). P. Erdos was very well aware of this paper of Ramanujan (cf. [1], [2] and [3]) as well as of the symmetric group and the order of its elements, (cf. [4]) and I think that he enjoyed the connection between these two areas of mathematics. Anyway, since these first letters, we had many occasions to discuss Landau's function. Let us define n1 = l,n2 = 2,n3 = 3,n4 = 4,n5 = 5,n6 = 7, etc ... , nk, such that lOne may add also the nice paper of J. Grantham. The largest prime dividing the maximal order of an element of Sn, to appear in Mathematics of Computation.

On Landau's Function g(n) g(nk)

> g(nk

229

- 1).

(1.3)

= +00.

(1.4)

The above mentioned result can be read: lim nk+l - nk Here, I shall prove the following result: Theorem 1.1. (1.5) Let Pl = 2, P2 = 3, P3 = 5, ... ,Pk the k-th prime. It is easy to deduce Theorem 1.1 from the twin prime conjecture (Le. lim Pk+l - Pk = 2) or even from the weaker conjecture lim Pk+l - Pk < +00. (cf. § IV below). But I shall prove Theorem 1.1 independently of these deep conjectures. Moreover I shall explain below why it is reasonable to conjecture that the mean value of nk+1 - nk is 2; in other terms one may conjecture that (1.6) and that nk+l - nk = 2 has infinitely many solutions. Due to a parity phenomenon, nk+l -nk seems to be much more often even than odd; nevertheless, I conjecture that: lim nk+1 - nk

= 1.

(1. 7)

The steps of the proof of Theorem 1.1 are first to construct the set G of values of g(n) corresponding to the so called superior highly composite numbers introduced by S. Ramanujan, and then, when g(n) E G, to build the table of g( n + d) when d is small. This will be done in §4 and §5. Such values of g( n + d) will be linked with the number of distinct differences of the form P-Q where P and Q are primes satisfying x-x Q ::; Q ::; x < P ::; x+x Q , where x goes to infinity and 0 < a < 1. Our guess is that these differences P - Q represent almost all even numbers between 0 and 2x Q , but we shall only prove in §3 that the number of these differences is of the order of magnitude of x Q , under certain strong hypothesis on x and a, and for that a result due to Selberg about the primes between x and x + xQ will be needed (cf. §2). To support conjecture (1.6), I think that what has been done here with g(n) E G can also be done for many more values of g(n), but, unfortunately, even assuming strong hypotheses, I do not see for the moment how to manage it. I thank very much E. Fouvry who gave me the proof of Proposition 3.1. Notation 1.1. P will denote a generic prime, Pk the k-th prime; P, Q, Pi, Qj will also denote primes. As usual 7r(x) = Ep~x 1 is the number of primes up to x.

I S I will denote the number of elements of the set S. The sequence nk is defined by (1.3).

230

Jean-Louis Nicolas

2. About the distribution of primes

i

Proposition 2.1. Let us define 7r(x) = 2:p~x 1, and let a be such that < a < 1, and € > O. When e goes to infinity, and e' = e + e/ log e, then for all

x in the interval

[e, e'] but a subset of measure 0(( e' - e) / log3 e) we have: xC< 7r(x) - log x xC< 17r(x) - 7r(x - xC<) - log x

17r(x + xC<) -

x 1

(2.1)

I::; € -

(2.2)

log x xC< log x

.jX

Qk _ Qk-l I Q og

-Iogx

xC<

I::; € -

1

~ - 4 - for all primes

log x

Q, and k ~ 2.

(2.3)

Proof. This proposition is an easy extension of a result of Selberg (cf. [15]) who proved that (2.1) holds for most x in (e, In [13], I gave a first extension of Selberg's result by proving that (2.1) and (2.2) hold simultaneously for all x in (e, e') but for a subset of measure 0(( e' - e) / log3 e). So, it suffices to prove that the measure of the set of values of x in (e, e') for which (2.3) does not hold is O((e' - e)/ log3 e). We first count the number of primes Q such that for one k we have:

n.

e

e'

Qk - Qk-l <--. loge logQ - loge'

--<

(2.4)

If Q satisfies (2.4), then k ::; II~~~' for e' large enough. Further, for k fixed, (2.4) implies that Q ::; (e')l/k, and the total number of solutions of (2.4) is loge' /log 2

::; L

(()l/k

= O( -If) = O( ~).

k=2

With more careful estimations, this upper bound could be divided by log2 e, but this crude result is enough for our purpose. Now, for all values of y = Qk_Qk-l

10gQ

.

.

.

satlsfymg (2.4), we cross out the mterval

We also cross out this interval whenever y =

4

sum of the lengths of the crossed out intervals is 0

(4,

(.If

.If) .

y - ~, y + ~

and y =

~

(10;4 ) ,

lor~/.

The total

which is smaller

than the length of the interval IS~' ), and if lo~ x does not fall into one of these forbidden intervals, (2.3) will certainly hold. Since the derivative of the function