PAUL ERDOS (1913-1996) A Memorial Tribute PhOlo: courtesy of Krishnaswami Alladi Paul Erdos (1913-1996), giving a lecture in Madras, India in January 1984, when he was Ramanujan Visiting Professor. 1998 Springer-Science+Business Media, B.V. THE RAMANUJAN JOURNAL EDITOR-IN-CHIEF Professor Krishnaswami Alladi Department of Mathematics University of Florida Gainesville, FL 32611, USA COORDINATING EDITORS Professor Bruce Berndt Professor Frank Garvan Department of Mathematics Department of Mathematics University of lllinois University of Florida Urbana,IL 61801, USA Gainesville, FL 32611, USA EDITORIAL BOARD Professor George Andrews Professor Paul Erdiis Professor Lisa Lorentzen Department of Mathematics Mathematics Institute Division of Mathematical Sciences The Pennsylvania State University Hungarian Academy of Sciences The Norwegian Institute of University Park, PA 16802, USA Budapest, Hungary Technology Professor Richard Askey Professor George Gasper N-7034 Trondheim-NTH, Norway Department of Mathematics Department of Mathematics Professor Jean-Louis Nicolas University of Wisconsin Northwestern University Department of Mathematics Madison, WI 53706, USA Evanston, 1L 60208, USA Universite Claude Bernard Professor Frits Beukers Professor Dorian Goldfeld Lyon I, 69622 Villeurbanne Cedex, Mathematics Institute Department of Mathematics France Rijksuniversiteit te Utrecht Columbia University, Professor Alfred van der Poorten 3508 TA Utrecht New York, NY 10027, USA School of MPCE The Netherlands Professor Basil Gordon Macquarie University Professor Jonathan Borwein Department of Mathematics NSW 2109, Australia Simon Fraser Centre for Experimental University of California and Constructive Mathematics Los Angeles, CA 90024, USA Professor Robert Rnnkin Department of Mathematics Department of Mathematics and Professor Andrew Granville University of Glasgow Statistics Department of Mathematics Glasgow, Gl2 SQW, Scotland Simon Fraser University University of Georgia Burnaby, B.C., V5A 156, Canada Athens, OA 30602, USA Professor Gerald Tenenbanm Professor Peter Borwein Professor Adnlf Hildebrand lnstitut Elie Cartan Simon Fraser Centre for Experimental Department of Mathematics Universite Heori Poincare Nancy 1 and Constructive Mathematics University of lllinois BP 239, F-54506 Vandoeuvre Cedex, Department of Mathematics and Urbana, lL 61801, USA France Statistics Professor Mourad Ismail Professor Michel Waldschmidt Simon Fraser University Department of Mathematics Universite P et M Corle (Paris VI) Burnaby, B.C., V5A 156, Canada University of South Florida Mathematiques UFR 920 Professor David Bressoud Tampa, FL 33620, USA F-75252 Paris Cedex, France Department of Mathematics and Professor Marvin Knopp Professor Don Zagier Computer Science Department of Mathematics Max Planck InstitUt Macalester College Temple University ftir Mathematik St. Paul, MN 55105, USA Philadelphia, PA 19122, USA 5300 Bonn 1, Germany Professor Peter Elliott Professor James Lepowsky Professor Doron ZeUberger Department of Mathematics Department of Mathematics Department of Mathematics University of Colorado Rutgers University Temple University Boulder, CO 80309, USA New Brunswick, NJ 08903, USA Philadelphia, PA 19122, USA ISSN: 1382-4090 @ 1998 Springer Science+B usiness Media Dordrecht Originally published by Kluwer Academic Publishers in 1998. Softcover reprint of the hardcover I st edition 1998 No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without written permission permission from the copyright owner. THE RAMANUJAN JOURNAL Volume 2, Nos. 112, 1998 Editorial ................................................... Krishnaswami Alladi 5 Euler's Function in Residue Classes........ Thomas Dence and Carl Pomerance 7 Partition Identities Involving Gaps and Weights, Il ......... Krishnaswami Alladi 21 The Voronoi Identity via the Laplace Transform ................. Aleksandar /vic 39 The Residue of p(N) Modulo Small Primes ........................... Ken Ono 47 A Small Maximal Sidon Set ...................................... Imre Z Ruzsa 55 Sums and Products from a Finite Set of Real Numbers ............... Kevin Ford 59 The Distribution of Totients .......................................... Kevin Ford 67 A Mean-Value Theorem for Multiplicative Functions on the Set of Shifted Primes ................................. Karl-Heinz Indlekofer and Nikolai M. Timofeev 153 Entiers Lexicographiques .................... Andre Stef and Gerald Tenenbaum 167 The Berry-Esseen Bound in the Theory of Random Permutations ............... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E. Manstavicius 185 Products of Shifted Primes. Multiplicative Analogues of Goldbach's Problems, Il .................................................................. P.D. T.A. Elliott 201 On Products of Shifted Primes ............... P. Berrizbeitia and P.D.T.A. Elliott 219 On Large Values of the Divisor Function ....................................... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Paul Erdos, Jean-Louis Nicolas and Andras Sarkozy 225 Some New Old-Fashioned Modular Identities .................................. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Paul T. Bateman and Marvin I. Knopp 247 Linear Forms in Finite Sets of Integers ......................................... . . . . . . . . . . . . . . . . . . . . . . . Shu-Ping Han, Christoph Kirfel and Melvyn B. Nathanson 271 A Binary Additive Problem of Erdos and the Order of 2 mod p2 ......•...•.•..• . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Andrew Granville and K. Soundararajan 283 ISBN 978-1-4419-5058-1 ISBN 978-1-4757-4507-8 (eBook) DOI 10.1007/978-1-4757-4507-8 Library of Congress Cataloging-i•Publication Data A C.I.P. Catalogue record for this book is available from the Library of Congress. Copyright ID 1998 by Springer Science+Business Media Dordrecht Originally published by Kluwer Academic Publishers in 1998. Softcover reprint of the hardcover I st edition 1998 All rights reseJVed. No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher, Kluwe1 Academic Publishers, 101 Philip Drive, Assinippi Park, Norwell, Massachusetts 02061 Printed on acid-free paper. i., THE RAMANUJAN JOURNAL 2, 5-6 (1998) ill © 1998 Kluwer Academic Publishers. Manufactured in The Netherlands. Editorial In September 1996, Professor Paul Erdos, one of the mathematical legends of this century, died while attending a conference in Warsaw, Poland. His death at the age of 83 marked the end of a great era, for Erdos was not only an outstanding mathematician but a very kind and generous human being, who encouraged hundreds of mathematicians over the decades, especially young aspirants to the subject. Many, including me, owe their careers to him. He was without doubt the most prolific mathematician of this century, having written more than 1000 papers, a significant proportion of them being joint papers. Even in a mathematical world, which is used to geniuses and their idiosyncracies, Erdos was considered an unusual phenomenon and was viewed with awe and adoration, just as Ramanujan evoked surprise and admiration. And like Ramanujan's mathematics, the contributions of Erdos will continue to inspire and influence research in the decades ahead. Paul Erdos was unique in many ways. Born in Hungary in April1913, he was a member of the Hungarian Academy of Sciences. But he did not have a job or any regular position. He was constantly on the move, criss-crossing the globe several times during a year, visiting one university after the other giving lectures. Somehow in his word wide travels, like migrating birds, he managed to hover around the isotherm 70°F. So he visited Calgary in the summers, California in the winters and Florida in February/March. He seldom stayed at one place for more than two weeks except, perhaps, in his native Hungary where he returned periodically between his travels. And he did this every year for the past half a century or more! To be in constant demand at universities throughout the world, one should not only be an unending source of new ideas but should also have the ability to interact with persons of varying tastes and abilities. Erdos was superbly suited to this task. This is what kept his furious productivity going till the very end. In a long and distinguished career starting in 1931, Erdos made fundamental contributions to many branches of mathematics, most notably, Number Theory, Combinatorics, Graph Theory, Analysis, Set Theory and Geometry. He was the champion of the "elementary method", often taming difficult questions by ingenious elementary arguments. Erdos began his illustrious career as a mathematician with a paper in 1932 on prime numbers. Interestingly, it was through this paper that he first became aware ofRamanujan's work. Ramanujan was a strong influence and inspiration for him from then on as he himself said in an article written for the Ramanujan centennial. Two of Erdos's greatest accomplishments were the elementary proof of the prime number theorem, proved simultaneously and independently by Atle Selberg, and the Erdos-Kac theorem which gave birth to Probabilistic Number Theory. The Erdos-Kac theorem itself was an outcome of the famous Hardy-Ramanujan paper of 1917 on the number of prime factors of an integer. For these contributions, Erdos was awarded the Cole Prize of the American Mathematical Society in 1952. In 1983 he was awarded the Wolf Prize for his lifelong contributions to mathematics and he joined the ranks of other illustrious winners 6 EDITORIAL of this prize like Kolmogorov and Andre Weil. He was elected member of the National Academy of Sciences of USA and also elected Foreign Member of The Royal Society. He is also the recipient of numerous honorary doctorates from universities around the world. What did Erdos do with his income and prize money? Erdos, who was a bachelor all his life, was wedded to mathematics which he pursued with a passion. Erdos had no desire for any material possessions and was saintly in his attitude towards life. He often used to say that property was a nuisance. During his visits to universities and institutes of higher learning, he was paid honoraria for his lectures. After keeping what was necessary to pay for his travel and living expenses, he would give away the remaining amount either in the form of donations to educational organizations or as prizes for solutions to mathematical problems he posed. I should emphasize that Erdos was without doubt the greatest problem proposer in history. During his lectures worldwide, he posed several problems and offered prize money ranging from $50 to $1000, depending on the difficulty of the problem. This was one way in which he spotted and encouraged budding mathematicians. It has often been mentioned about Ramanujan that his greatness was not only due to the remarkable results he proved, but also due to the many important questions that arose from his work. Similarly, Erdos will not only be remembered for the multitude of theorems he proved, but also for the numerous problems he raised. When the idea to start the Ramanujan Journal was put forth, Erdos was very supportive. When he was invited to serve on the Editorial Board, he agreed very graciously. Had he been alive, he would have been delighted to see the first issue of the journal appear in January 1997. But before he died, he contributed a paper to the journal written jointly with Carl Pomerance and Andras Sarkozy which appeared in volume 1, issue 3, in July 1997. Erdos will be sorely missed by the entire mathematical community, especially by those who got to know him closely. The Ramanujan Journal is proud to dedicate the first two issues of volume 2 to his memory. Based on the success of the Ramanujan Journal, Kluwer Academic Publishers decided to launch the new book series Developments in Mathematics this year. This book series will publish research monographs, conference proceedings and contributed volumes in areas similar to those of The Ramanujan Journal. It was felt that it would be worthwhile to offer the Erdos special issues also in book (hard cover) form for those who may wish to purchase them separately. We are pleased that this book is the opening volume of Developments in Mathematics. Thus the new book series is off to a fine start with a volume of such high quality. In preparing the Erdos memorial issues (volume), I had the help of Peter Elliott, Andrew Granville and Gerald Tenenbaum of The Ramanujan Journal editorial board. My thanks to them in particular, and more generally to the other members of the editorial board for their support. Finally we are grateful to the various authors for their contributions. By publishing the Erdos memorial issues in The Ramanujan Journal and in Developments in Mathematics, we are paying a fitting tribute to Erdos and Ramanujan both of whom are legends of twentieth century mathematics. Krishnaswami Alladi Editor-in-Chief llo..., THE RAMANUJAN JOURNAL 2, 7-20 (1998) ' © 1998 Kluwer Academic Publishers. Manufactured in The Netherlands. Euler's Function in Residue Classes THOMAS DENCE tdence@ ashland.edu Department ofM athematics, Ashland University, Ashland, OH 44805 CARL POMERANCE, carl@ ada.math.uga.edu Department ofM athematics, University of Georgia, Athens, GA 30602 Dedicated to the memory of Paul Erdoo Received June 28, 1996; Accepted October 16, 1996 Abstract. We discuss the distribution of integers n with rp(n) in a particular residue class, showing that if a residue class contains a multiple of 4, then it must contain infinitely many numbers rp(n). We get asymptotic formulae for the distribution of rp(n) in the various residue classes modulo 12. Keywords: 1991 Mathematics Subject Classification: 1. Introduction Let q; denote Euler's arithmetic function, which counts the number of positive integers up ton that are coprime ton. Given a residue class r mod m must there be infinitely values of q;(n) in this residue class? Let N(x, m, r) denote the number of integers n S x with q;(n) = r mod m. If there are infinitely many Euler values in the residue class r mod m, can we find an asymptotic formula for N (x, m, r) as x -+ oo? It is to these questions that we address this paper. Since q;(n) is even for each integer n > 2, we immediately see that if the residue class r mod m does not contain any even numbers, then it cannot contain infinitely many values of q;(n). Is this the only situation where we cannot find infinitely many Euler values? We conjecture that this is the case. Conjecture. If the residue class r mod m contains an even number then it contains in finitely many numbers q;(n). This conjecture is a consequence of Dirichlet's theorem on primes in arithmetic progres sions and the following elementary assertion: If the residue class r mod m contains an even number, then there are integers a, k with k 2:: 0 and (a, m) = 1 such that ak(a - 1) = r mod m. We have not been able to prove or disprove this assertion, though we conjecture it is true. We can prove the following result. 8 DENCEANDPOMERANCE Theorem 1.1. If the residue class r mod m contains a multiple of 4 then it contains infinitely many numbers qJ(n). The proof is an elementary application of Dirichlet's theorem on primes in an arithmetic progression, and is inspired by an argument in a paper of Narkiewicz [6]. One relevant result from [6] is that if m is coprime to 6 and r is coprime tom, then there are infinitely many Euler values in the residue class r mod m. In particular, it is shown that = asymptotically 1/qJ(m) of the integers n with qJ(n) coprime tom have qJ(n) r mod m. From this it is a short step to get an asymptotic formula for N (x, m, r) for such pairs m, r. In fact, for any specific pair m, r it seems possible to decide if N(x, m, r) is unbounded and to obtain an asymptotic formula in case it is. We shall illustrate the kinds of methods one might use for such a project in the specific case m = 12. We only have to consider the even residue classes mod 12. By Dirichlet's theorem we immediately see that the residue classes 0, 4, 6, 10 mod 12 each contain infinitely many qJ-values, since there are infinitely many primes in each of the residue classes 1, 5, 7, 11 mod 12. This leaves r = 2 and 8. If pis an odd prime= 2 mod 3, then qJ(4p) = 8 mod 12, so 8 mod 12 contains infinitely many qJ-values. As noticed in [3], the residue class 2 mod 12 is tougher for qJ to occupy. But if p = 11 mod 12 and p is prime, then qJ(p2) = 2 mod 12, so occupied it is. Now we tum to estimating N(x, 12, r) for r even. We begin with examining the nu merical data in Table 1. Perhaps the most striking feature of Table 1 is the paucity of integers n with qJ(n) = 2 mod 12. This behavior was already noticed in [3], and it was shown there that the set of such integers has asymptotic density 0. Another observation that one might make is that the numbers for the 0 residue class keep growing as a per centage of the whole, from 30% at 100 to over 73% at 107• Though their contribution decreases as a percentage of the whole, the columns for 4 and 8 grow briskly, and seem to keep in approximately the same ratio. And the columns for 6 and 10 seem to be about equal. Can anything be proved concerning these observations? We prove the following theorem. Theorem 1.2. We have, as x ~ oo, N(x, 12, 0) "'x, (1.1) Table 1. The number of n ::5 x with <p(n) in a particular residue class modulo 12. X 0 2 4 6 8 10 lol 30 3 21 17 18 9 UP 511 6 185 84 145 67 ur 6114 13 1651 511 1233 476 tOS 66646 32 15125 3761 10743 3691 106 703339 81 140155 30190 96165 30068 107 7300815 208 1313834 253628 878141 253372 EULER'S FUNCTION 9 N(x, 12, 2)"" (~ + -1-) ~, (1.2) 2 2-J2 logx X N(x, 12, 4) ""c1 ~· (1.3) v log x 3 X N(x, 12, 6) "" Slogx, (1.4) X N(x, 12, 8) ""c2 ~· (1.5) v log x 3 X N(x, 12, 10)"" 81ogx, (1.6) where c1:::::: .6109136202 is given by (1.7) with n ( C3 = 1 + 2 ~ 1 ). (1.8) p pnme P p=2(3) = and c2 .3284176245 is given by the same expression as for c1, except that 2c3 + c4 is replaced by 2c3 - c4. The case of 0 mod 12 follows from a more general result of Erdos. Theorem (Erdos). For any positive integer m, N(x, m, 0) ""x as x -+ oo. We have not been able to find the first place this result appears but the proof follows = from the fact that the sum of the reciprocals of the primes p 1 mod m is infinite, so that almost all integers n are divisible by such a prime. But if such a prime p divides n, then = q;(n) 0 mod m. There is a fairly wide literature on the distribution in residue classes of values of multi plicative functions, in fact there is a monograph on the subject by Narkiewicz [7). However, but for Narkiewicz's result above, and a result of Delange [2) (which can be used to give an asymptotic formula for the number of n up to x for which q;(n) is not divisible by a fixed integer m ), the problems considered here appear to be new. We begin now with the proof of Theorem 1.2, giving the proof of Theorem 1.1 at the end of the paper. In the sequel, the letter p shall always denote a prime. 2. The residue classes 2, 6 and 10 mod 12 = Let Sm,r denote the set of integers n with q;(n) r mod m. So N(x, m, r) counts how many members Sm,r has up to x.