Studies in Pure Mathematics To the Memory of Paul Turan Editorial Board Editor-in-Chief: Paul Erdos Associate Editors: Laszl4 Alpar, Gabor Halasz and Andras Sarkozy Springer Basel AG Library of Congress Cataloging in Publication Data Main entry under title : Studies in pure mathematics. Includes index. 1. Mathematics—Addresses, essays, lectures. 2. Turân, P. (Paul) 1910—1976. I. Turân, P. (Paul), 1910—1976. IL Erdös, Paul, 1913- QA7.S845 510 81-17016 AACR2 CI P Kurztitelaufnahme der Deutschen Bibliothek Studies in pure Mathematics: to the memory of Paul Turân/Paul Erdös, ed. ... — Basel ; Boston; Stuttgart: Birkhäuser, 1983. NE: Erdös, Paul [Hrsg.] All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, without the prior permission of the copyright owner. © Springer Basel AG 1983 Originally published by Akadémiai Kiadô, Budapest in 1983 Softcover reprint of the hardcover 1st edition 1983 ISBN 978-3-7643-1288-6 ISBN 978-3-0348-5438-2 (eBook) DOI 10.1007/978-3-0348-5438-2 Contents Editors' Preface. . . . . . . . . . . . . . . . . . . 9 Preface, Personal reminiscences by P. ERD6s (Budapest) II G. HALAsz (Budapest), Letter to Professor Paul Tunin. 13 ABBOT, H. L. and MEIR, A. (Edmonton), An extremal problem in combinatorial number theory. . . . . . . . . . . . . . . . . . . 17 AJTAI, M., HAvAs, I. and KOMWS, J. (Budapest), Every group admits a bad topology. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 ALPAR, L. (Budapest), Sur certains changements de variable des series de puissances. . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 ANDERSON, 1. M. and CLUNlE, 1. (London), The spherical derivative of meromorphic functions with relatively few poles . . . . . . . . . . 43 ASKEY, R. and ISMAIL, MOURAD E.-H. (Madison), A generalization of ultraspherical polynomials . . . . . . . . . . . . . . . . . . . . 55 BELNA, C. (State Univ. Pennsylvania) and PIRANlAN, G. (Ann Arbor), A Blaschke product with a level-set of infinite length . . . . . . . . . 79 BOLLOBAS, B. (Cambridge), CHUNG, F. R. K. (Murray Hi\I) and GRAHAM, R. L. (Murray Hill), On complete bipartite subgraphs con- tained in spanning tree complements. . . . . . . . . . . . . .. 83 BROWN, W. G. (Montreal), On an open problem of Paul Tunin concerning 3-graphs.. . . . . . . . . . . . . . . . . . . . . 91 CARLESON, L. see Appendix to the paper of J.-P. KAHANE and Y. KATZNELSON ....................... . CHUNG, F. R. K. (Murray Hi\I), ER06s, P. (Budapest) and SPENCER, J. (Stony Brook), On the decomposition of graphs into complete bipartite subgraphs. '.' . . . . . . . . . . 95 CHUNG, F. R. K. see also BOLLOBAS, B. ............. . CLUNIE, 1. see ANDERSON, J. M. . . . . . . . . . . . . . . . . . CsASZAR, A. (Budapest), Syntopogenous spaces and zero-set spaces. 103 DENES, 1. (Budapest), KIM, K. H. and ROUSH, F. W.(Montgomery), Automata on one symbol. . . . . . . . . . . . . . . . . . . .. 127 DoBROWOLSKI, E. (WrocIaw), LAWTON, W. (Pasadena) and SCffiNZEL, A. (Warszava), On a problem of Lehmer. . . . 135 ELBERT, A. (Budapest), On extremal polynomials . . . . . . . . . .. 145 6 Contents ELUOTT, P. D. T. A. (Boulder), Subsequences of primes in residue classes to prime moduli . . . . . . . . . . . . . . . . . . . . . . . . .. 157 ERD6s, P. and SARKOZY, A. (Budapest), Some asymptotic formulas on generalized divisor functions I. . . . . . . . . . . . . . . . . .. 165 ERD6s, P. and T. S6s, V. (Budapest), On a generalization of Tunin's graph- theorem. . . . . . . . . . . . . . . . . . . . . . . . . . . .. 181 ERD6s, P. and SZALAY, M. (Budapest), On some problems of J. DENES and P. TuRAN . . . . . . . . . . . . . . . . . . . . . . . . . . .. 187 ERD6s, P. and SZEMEREDI, E. (Budapest), On sums and products of integers 213 ERD6s, P. see also CHUNG, F. R. K ................. . FUCHS, W. H. J. (Cornell Univ.), On the growth of meromo rphic functions on rays ......................... '. . .. 219 GAIER, D. (Giessen) and KJELLBERG, B. (Stockholm), Entire functions and their derivative on an asymptotic arc. . . . . . . . . 231 GANEUUS, T. (GOteborg), Orthogonal polynomials and rational approximation of holomorphic functions. . . . . . . 237 GRAHAM, R. L. see BOLLOBAS, B.. . . . . . . . . . . . Gyl)RY, K. (Debrecen) and PAPP, Z. Z. (Budapest), Norm form equations and explicit lower bounds for linear forms with algebraic coefficients. 245 HALASZ, G. (Budapest), On the first and second main theorem in Turim's theory of power sums. . . . . . . . . . . . . . . . . . . . . .. 259 HARARY, F. and MILLER, Z. (Ann Arbor), Generalized Ramsey theory VIII. The size ramsey number of small graphs . . . . . . . . . . . .. 271 HARRIS, B. (Madison), The asymptotic distribution of the order of elements in alternating semigroups and in partial transformation semigroups. 285 HAVAS, I. see AlTAI, M. . . . . . . . . . . . . . . . . . . . . . . . HAYMAN, W. K. (London) and KJELLBERG, B. (Stockholm), On the mini- mum of a subharmonic function on a connected set . . . . . . .. 291 HEPPNER, E. und ScHWARZ, W. (Frankfurt am Main), Benachbarte multiplikative Funktionen. . . . . . . . . . . . . . . . . . . . 323 HLAWKA, E. (Wien), Eine Bemerkung zur Theorie der Gleichverteilung 337 IuEV, L. (Sofia), Laguerre entire functions and Turim inequalities.' . 347 INDLEKOFER, K.-H. (Paderborn), On Turan's equivalent power series 357 ISMALL, MOURAD, E.-H. see ASKEY, R .............. . JAGER, H. (Amsterdam), The average order of Gaussian sums. . . . 381 JUTlLA, M. (Turku and Djursholm), Zeros of the zeta-function near the critical line . . . . . . . . . . . . . . . . . . . . . . . . . .. 385 KAHANE, I-P. (paris) et KATZNELSON, Y. (Jerusalem), series de Fourier des fonctions bornees . . . . . . . . . . . . . . . . . . . . . . .. 395 CARLESON, L. (Djursholm), Appendix to the paper of I-P. KAHANE and Y. KATZ NELSON . . . . . . . . . . . . . 411 KATAI, I. (Budapest), Characterization of log n . . . . . . . . . . . 415 KATZNELSON, Y. see KAHANE, I-P. ................. . KIM, K. H. and ROUSH, F. W. (Montgomery), On a problem of Turim 423 KIM, K. H. see also DENES, J. . . . . . . . . . . . . . KIELLBERG, B. see GAIER, D. and HAYMAN, W. K. . . . . . . . . . Contents 7 KOLESNIK, G. (Austin) and STRAUS, E. G. (Los Angeles), On the sum of powers of complex numbers. . . 427 KOMWS, J. see AlTAI, M. ....... . LAWTON, W. see DoBROWOLSKI,.E.. . .. ........ . LoRCH, L. (Downsview) and NEWMAN, D. J. (Philadelphia), On a monotonicity property of some Hausdorff transforms of certain Fourier series. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 443 LoRENTZ, G. G. (Austin), Theorem of Budan-Fourier and BirkhofT interpolation. . . . . . . . . . . . . . . . . . . . . .' . . . .. 455 LovAsz, L. and SIMONOVlTS, M. (Budapest), On the number of complete subgraphs of a graph II. 459 MEIR, A. see ABBOT, H. L.. . . . . . . . . . . . . . . . . . . . . . MILLER, Z. see HARARV, F. . . . . . . . . . . . . . . . . . . . . . MONTGOMER'Y, H. L. (Ann Arbor), Zeros of approximations to the zeta function . . . . . . . . . . . . . . . . . . . . . . . . . .. 497 MOTOHASHI, Y. (Tokyo), Large sieve extensions of the Brun-Titchmarsch theorem. . . . . . . . . . . . . . . . . . . . . . . . . . . .. 507 NARKlEWlCZ, W. (Wroclaw), On a question of Alladi and Erdos on sums of squares . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 517 NEWMAN, D. J. see LORCH, L. . . . . . . . . . . . . . . . . . . . . NIEDERREITER, H. (Wien), A quasi-Monte Carlo method for the approximate computation of the extreme values of a function . . . . . . . . .. 523 PALFV, P. P. and SZALAY, M. (Budapest), On a problem of P. TuRAN concerning Sylow subgroups ............. '. . . . .. 531 PAPP, Z. Z. see GvlBtv, K.. . . . . . . . . . . . . . . . . . . . . . PIERRE, R. (Sherbrooke) and RAHMAN, Q. I. (Montreal), On polynomials with curved majorants . . . . . . . . . . . . . . . . . . . . .. 543 PlNTz, J. (Budapest), Oscillatory properties of the remainder term of the prime number formula. . . . . . . . . . . . . . . . . . . . .. 551 PIRANlAN, G. see BELNA, CH.. . . . . . . . . . . . . . . . . . . . . POMMERENKE, CH. (Herlin-Minneapolis) and PuRzITSKV, N. (Toronto- Berlin), <1n some universal bounds for Fuchsian groups. 561 PURZITSKV, N. see POMMERENKE, CH. . . . . RAHMAN, Q. I. see PIERRE,"R. ............. . ROUSH, F. W. see DENES, J. and KIM, K. H.. . . . . . . . RUZSA, I. Z. (Budapest), On the variance of additive functions 577 SACHS, H. and STIEBITZ, M. (Ilmenau), Automorphism group and spectrum of a graph. . . . . . . '. . . . 587 SARKOZV, A. see ERD&, P. ..................... . SeHlNZEL, A. see DoBROWOLSKI, E.. . . . . . . . . . . . . . . . . . SCHMIDT, W. M. (Boulder-Tokyo), The joint distribution of the digits of certain integer s-tulpes . . . . . . . . . . . . . . . . . . . . .. 605 ScHOENBERG, I. J. (West Point), On Jacobi-Bertrand's proof of a theorem of Poncelet. . . . . . . . . . . . . . . . . . . . . . . . . . . .. 623 ScHWARZ, W. see HEPPNER, E.. . . . . . . . . . . . . . . . . . . . SHAH, S. M. (Lexington), Entire functions of bounded value distribution and gap power series. . . . . . . . . . . . . . . . . . . . . . . .. 629 8 Contents SmDLOVSKY, A. B. (Moscow), Estimates for the moduli of polynomials with algebraic coefficients at the value of E-functions . . . . . . . . .. 635 SIEBERT, H. (Mannheim), Sieve methods and Siegel's zeros. . . . . .. 659 SIMONOVITS, M. (Budapest), Extremal graph problems and graph products 669 SIMONOVITS, M. see also LovAsz, L. ................. . SOMORJAI, G. t (Budapest), On the coefficients of rational functions. .. 681 T. S6s, V. (Budapest), On stroung irregularities of the distribution of {nIX} sequences . . . . . . . . . . . . . . . . 685 T. S6s, V. see also Ean(}s, P.. . . . . . . . . . . . . . . . . . . . . SPENCER, J. see CHUNG, F. R. K ................... . STEW ART, C. L. (Waterloo) and TIJDEMAN, R. (Leiden), On density-difference sets of sets of integers . . . . . . . . . . . 70 I STIEBITZ, M. see SACHS, M. . . . . . . . . . . . . . . . . . . . . . STRAUS, E. G. see KOLESNIK, G ................... . SURANYI, J. (Budapest), Some notes on the power sums of complex numbers o. . . . . . . . . . . . . . . . . . . . . . . . .. whose sum is 711 SWINNERTON-DYER, H. P. F. (Cambridge), The field of definition of the Neron-Severi group. . . . . . . . . . . . . . . 719 SZALAY, M. see ERD6s, P. and PALFI, P. P ...... . SZEMEREDI, E. see ERD6s, P. . . . . . . . . . . . . . Sziisz, P. (Stony Brook), On Hadamard's gap theorem. 733 TIJDEMAN, R. see STEWART,C. L. .......... . VAUGHAN, R. C. (London), A remark on Freud's tauberian theorem 737 VERTESI, P. (Budapest), Two problems of P. TURAN . . . . . . . . 743 WALDSCHMIDT, M. (Paris), Un lemme de Schwarz pour des intersections d'hyperplans. . . . . . . . . . . . . . . . . . . . . . . . . 751 WIERTELAK, K. (poman), On the density of some sets of primes III . .. 761 Editors' Preface This volume, written by his friends, collaborators and students, is offered to the memory of Paul Tunin. Most of the papers they contributed discuss subjects related to his own fields of research. The wide range of topics reflects the versatility of his mathematical activity. His work has inspired many mathematicians in analytic number theory, theory of functions of a complex variable, interpolation and approximation theory, numerical algebra, differential equations, statistical group theory and theory of graphs. Beyond the influence of his deep and important results he had the exceptional ability to communicate to others his enthusiasm for mathematics. One of the strengths of Turan was to ask unusual questions that became starting points of many further results, sometimes opening up new fields of research. We hope that this volume will illustrate this aspect of his work adequately. Born in Budapest, on August 28, 1910, Paul Turan obtained his Ph. D. under L. Fejer in 1935. His love for mathematies enabled him to work even under inhuman circumstances during the darkest years of the Second World War. One of his major achievements, his power sum method originated in this period. After the war he was visiting professor in Denmark and in Princeton. In 1949 he became professor at the Eotvos Lorand University of Budapest, a member of the Hungarian Academy of Sciences and a leading figure of the Hungarian mathematical community. His untimely death on September 26, 1976 prevented him from working out a great many of the ideas he had so abundantly. Even the relatively large extent of this volume did not permit to invite and include all desirable contributions. We express our gratitude to the Akademiai Kiad6 for having made it possible for the many friends of Paul Turan to pay their tribute to a great mathematician. The Editors Studies in Pure Mathematics To the Memory of Paul Turim Preface Personal reminiscences I met Paul Turan first in September 1930 at the University of Budapest though we knew of each others existence since we both worked for the mathematical journal for high school students and our first joint paper appeared there, i.e. a solution of a problem which we obtained independently. At our first meeting I asked him if the sum of the reciprocals of the primes diverges or converges. He informed me that it diverges and he told me about the prime number theorem. (Seven or eight years earlier I learned from my father that the number of primes is infinite.) We met and discussed mathematics nearly every day until I went to Manchester in October 1934, after that date until early September 1938 I spent half my time in England half in Hungary but when I was in England we corresponded a great deal. Our first joint paper dealt with elementary number theory, in which we deal with a problem ofG. Griinwald and D. Lazar: Let f(n) be the largest integer so that if 1 ~ al < ... < an n are any set of n integers then (ai + aj) has at least f(n) distinct prime factors. We proved I~i;::;j;:;;;n n (1) cllog n<f(n)<c2- logn and we conjectured that f(n)flog n-+oo, which is still open. Very soon we started our collaboration on interpolation which produced many more "serious" results. From England I returned to Hungary for Christmas, Easter and summer vacations. In the spring of 1938 Hitler succeeded in disturbing my plans, but I could return to Hungary precariously in the summer of 1938. On September 3, 1938, I did not like the news and in the evening I was on my way to England and three and one-half weeks later to the USA. We corresponded until 1941, then there was an enforced gap offour years. As soon as possible we started our first postwar joint paper on the difference of consecutive primes which we wrote in correspondence. In this paper we stated a few problems which I find very interesting: Put d,,=Pk+1 -p", Is it true that