Skip to main content

2013 | Buch

The Mathematics of Paul Erdős I

herausgegeben von: Ronald L. Graham, Jaroslav Nešetřil, Steve Butler

Verlag: Springer New York

insite
SUCHEN

Über dieses Buch

This is the most comprehensive survey of the mathematical life of the legendary Paul Erdős (1913-1996), one of the most versatile and prolific mathematicians of our time. For the first time, all the main areas of Erdős' research are covered in a single project. Because of overwhelming response from the mathematical community, the project now occupies over 1000 pages, arranged into two volumes. These volumes contain both high level research articles as well as key articles that survey some of the cornerstones of Erdős' work, each written by a leading world specialist in the field. A special chapter "Early Days", rare photographs, and art related to Erdős complement this striking collection. A unique contribution is the bibliography on Erdős' publications: the most comprehensive ever published. This new edition, dedicated to the 100th anniversary of Paul Erdős' birth, contains updates on many of the articles from the two volumes of the first edition, several new articles from prominent mathematicians, a new introduction, more biographical information about Paul Erdős, and an updated list of publications.

The first volume contains the unique chapter "Early Days", which features personal memories of Paul Erdős by a number of his colleagues. The other three chapters cover number theory, random methods, and geometry. All of these chapters are essentially updated, most notably the geometry chapter that covers the recent solution of the problem on the number of distinct distances in finite planar sets, which was the most popular of Erdős' favorite geometry problems.

Inhaltsverzeichnis

Frontmatter
Paul Erdős: Life and Work

Dipping into the mathematical papers of Paul Erdős is like wandering into

Aladdin’s Cave

. The beauty, the variety and the sheer wealth of all that one finds is quite overwhelming. There are fundamental papers on number theory, probability theory, real analysis, approximation theory, geometry, set theory and, especially, combinatorics. These great contributions to mathematics span over six decades; Erdős and his collaborators have left an indelible mark on the mathematics of the twentieth-century. The areas of probabilistic number theory, partition calculus for infinite cardinals, extremal combinatorics, and the theory of random graphs have all practically been created by Erdős, and no-one has done more to develop and promote the use of probabilistic methods throughout mathematics.

Béla Bollobás
Erdős Magic

Paul Erdős was a giant of twentieth century mathematics. Born in 1913 he was a child prodigy whose talents were well cultivated in his native Budapest. Dubbed

Der Zauberer von Budapest

he moved onto the world stage in his early 20s. And there he stayed, extraordinarily active right until his death in 1996.

Joel Spencer

I. Early Days

Frontmatter
Some of My Favorite Problems and Results

Problems have always been an essential part of my mathematical life. A well chosen problem can isolate an essential difficulty in a particular area, serving as a benchmark against which progress in this area can be measured. An innocent looking problem often gives no hint as to its true nature. It might be like a “marshmallow,” serving as a tasty tidbit supplying a few moments of fleeting enjoyment. Or it might be like an “acorn,” requiring deep and subtle new insights from which a mighty oak can develop.

Paul Erdős
Integers Uniquely Represented by Certain Ternary Forms

This paper has no connection with the two papers jointly authored by Paul Erdős and myself; nor does it overlap any of the many conversations we had. But I feel it is appropriate to dedicate the paper to him. It has the flavor of the mathematics we both particularly enjoyed: very explicit problems challenging us to answer “yes” or “no”.

Irving Kaplansky
Did Erdős Save Western Civilization?

If you stand on the famous Chain bridge in Budapest, you will see below you the broad sweep of the Danube. But this broad river arose from the confluence of many small streams. Indeed, there is a point near St. Moritz, where if a rain drop happens to fall a few centimeters to the north, it will make its way into the Rhine, and so to the North Sea. If it falls a little to the west, it will join the Adda and the Po, and end up in the Adriatic, whereas to the east it would run into the Inn, the Danube, and the Black Sea. An apparently negligible movement at the start can make a difference of hundreds of kilometers later on.

Cedric A. B. Smith
Encounters with Paul Erdős

My first encounter with Paul Erdős was curiously indirect. As a pre-undergraduate at Cambridge (England) in 1934, I learned from one of the Trinity College tutors that a mathematician named Erdős, passing through Cambridge, had mentioned an intriguing conjecture (attributed to Lusin, I believe), implying that a square could not be dissected into a finite number of unequal smaller square pieces. I passed this problem on to three fellow students, and we eventually found methods that produced counterexamples [1]. Of recent years the advent of high-speed computing has given rise to a considerable industry listing large numbers of dissections of squares into unequal squares ([2] and [6] for example), an industry that could continue indefinitely as there are infinitely many different dissections of this kind.

Arthur H. Stone
On Cubic Graphs of Girth at Least Five

It is an honor to be asked to contribute a paper to so historically important a collection. Yet it can be embarrassing too. In my case I ask distractedly “What can I write about? The researches I have completed have been published already, or at least have been submitted to Journals. The work I am engaged upon is incomplete, may be anticipated, perhaps even fallacious. And what else can there be?”

William T. Tutte

II. Number Theory

Frontmatter
Cross-Disjoint Pairs of Clouds in the Interval Lattice

Let

$$\mathcal{I}_{n}$$

be the lattice of intervals in the Boolean lattice

$$\mathcal{L}_{n}$$

. For

$$\mathcal{A},\mathcal{B}\,\subset \,\mathcal{I}_{n}$$

the pair of clouds

$$(\mathcal{A},\mathcal{B})$$

is cross-disjoint, if

$$I \cap J = \emptyset $$

for

$$I \in \mathcal{A},\ J \in \mathcal{B}$$

. We prove that for such pairs

$$\vert \mathcal{A}\vert \vert \mathcal{B}\vert \leq {3}^{2n-2}$$

and that this bound is best possible.

Optimal pairs are up to obvious isomorphisms unique. The proof is based on a new bound on cross intersecting families in

$$\mathcal{L}_{n}$$

with a weight distribution. It implies also an Intersection Theorem for multisets of Erdős P, Schőnheim J (1969) On the set of non pairwise coprime division of a number. In: Proc. of the Colloquium on Comb. Math. Dalaton Füred, pp 369–376.

Rudolf Ahlswede, Ning Cai
Classical Results on Primitive and Recent Results on Cross-Primitive Sequences

When the kind invitation of Ron Graham and Jaroslav Nešetřil, to write in honour of Paul Erdős about aspects of his work, reached us, our first reaction was to follow it with great pleasure. Our second reaction was not as clear: Which one among the many subjects in mathematics, to which he has made fundamental contributions, should we choose?

Finally we just followed the most natural idea to write about an area which just had started to fascinate us: Density Theory for Integer Sequences.

More specifically we add here to the classical theory of primitive sequences and their sets of multiples results for cross-primitive sequences, a concept, which we introduce. We consider both, density properties for finite and infinite sequences. In the course of these investigations we naturally come across the main theorems in the classical theory and the predominance of results due to Paul Erdős becomes apparent. Several times he had exactly proved the theorems we wanted to prove! Many of them belong to his earliest contribution to mathematics in his early twenties.

Quite luckily our random approach led us to the perhaps most formidable period in Erdős’ work. It reminds us about a statement, which K. Reidemeister [18, ch. 8] made about Carl Friedrich Gauss: “…Aber das Epochale ist doch die geniale Entdeckung des Jünglings: die Zahlentheorie.”

Rudolf Ahlswede, Levan H. Khachatrian
Dense Difference Sets and Their Combinatorial Structure

We show that if a set

B

of positive integers has positive upper density, then its difference set

D

(

B

) has extremely rich combinatorial structure, both additively and multiplicatively. If on the other hand only the density of

D

(

B

) rather than

B

is assumed to be positive, one is not guaranteed any multiplicative structure at all and is guaranteed only a modest amount of additive structure.

Vitaly Bergelson, Paul Erdős, Neil Hindman, Tomasz Łuczak
Integer Sets Containing No Solution to $$x + y = 3z$$

We prove that a maximum subset of

$$\{1,2,\ldots,n\}$$

containing no solutions to

$$x + y = 3z$$

has

$$\lceil \frac{n} {2} \rceil$$

elements if

n

≠4, thus settling a conjecture of Erdős. For

n

≥23 the set of all odd integers less than or equal to

n

is the unique maximum such subset.

Fan R. K. Chung, John L. Goldwasser
On Primes Recognizable in Deterministic Polynomial Time

We discuss some simple deterministic algorithms that establish primality for a robust set of primes in polynomial time. The first 6 sections comprise the intact original article published in the first edition of this volume in 1997. The last 2 sections discuss developments in this fast-moving field to early 2013, and refer to the prior sections in the past tense. The bibliography for the original article and the new update have been combined.

Sergei Konyagin, Carl Pomerance
Ballot Numbers, Alternating Products, and the Erdős-Heilbronn Conjecture

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

a

1

+⋯+

a

h

, where

a

1

,

,

a

h

A

and

a

i

a

j

for

i

j

.

Melvyn B. Nathanson
On Landau’s Function g(n)

Let

S

n

be the symmetric group of

n

letters. Landau considered the function

g

(

n

) defined as the maximal order of an element of

S

n

; Landau observed that (cf. [9])

1

$$\displaystyle{ g(n) =\max \mathrm{lcm}(m_{1},\ldots,m_{k}) }$$

where the maximum is taken on all the partitions

$$n = m_{1} + m_{2} + \cdots + m_{k}$$

of

n

and proved that, when

n

tends to infinity

2

$$\displaystyle{ \log g(n) \sim \sqrt{n\log n}. }$$

More precise asymptotic estimates have been given in [11, 22, 25].

Jean-Louis Nicolas
On Divisibility Properties of Sequences of Integers

Our first joint paper with Erdős appeared in 1966. It was a triple paper with Szemerédi written on divisibility properties of sequences of integers which is one of Erdős’ favorite subjects. Nine further triple papers written on the same subject followed it, and since 1966, we have written altogether 52 joint papers with Erdős. On this special occasion I would like to return to the subject of our very first paper. In Sect. 2, I will give a survey of the related results, while in Sect. 3, I will study a further related problem.

András Sárközy
On Additive Representative Functions

In this paper we give a short survey of additive representation functions, in particular, on their regularity properties and value distribution. We prove a couple of new results and present many related unsolved problems.

András Sárközy, Vera T. Sós
Arithmetical Properties of Polynomials

The present article describes Erdős’s work contained in the following papers.

[E1]

On the coefficients of the cyclotomic polynomials, Bull. Amer. Math. Soc. 52 (1946), 179–183.

[E2]

On the coefficients of the cyclotomic polynomial, Portug. Math. 8 (1949), 63–71.

[E3]

On the number of terms of the square of a polynomial, Nieuw Archief voor Wiskunde (1949), 63–65.

[E4]

On the greatest prime factor of

$$\mathop{\prod }\limits _{k=1}^{x}f(k)$$

, J. London Math. Soc. 27 (1952), 379–384.

[E5]

On the sum

$$\sum \limits _{k=1}^{x}d(f(k))$$

, ibid. 7–15.

[E6]

Arithmetical properties of polynomials, ibid. 28 (1953), 436–425.

[E7]

Über arithmetische Eigenschaften der Substitutionswerte eines Polynoms für ganzzahlige Werte des Arguments, Revue Math. Pures et Appl. 1 (1956) No. 3, 189–194.

[E8]

On the growth of the cyclotomic polynomial in the interval (0,1), Proc. Glasgow Math. Assoc. 3 (1957), 102–104.

[E9]

On the product

$$\mathop{\prod }\limits _{k=1}^{n}(1 {-\zeta }^{a_{i}})$$

, Publ. Inst. Math. Beograd 13 (1959), 29–34 (with G. Szekeres).

[E10]

Bounds for the

r

-th coefficients of cyclotomic polynomials, J. London Math. Soc. (2) 8 (1974), 393–400 (with R. C. Vaughan).

[E11]

Prime polynomial sequences, ibid. (2) 14 (1976), 559–562 (with S. D. Cohen, M. B. Nathanson).

[E12]

On the greatest prime factor of

$$\mathop{\prod }\limits _{k=1}^{x}f(k)$$

, Acta Arith. 55 (1990), 191–200 (with A. Schinzel).

Andrzej Schinzel
Some Methods of Erdős Applied to Finite Arithmetic Progressions

Since 1934 Erdős has introduced various methods to derive arithmetic properties of blocks of consecutive integers. This research culminated in 1975 when Erdős and Selfridge (Ill J Math 19:292–301, 1975) established the old conjecture that the product of two or more consecutive positive integers is never a perfect power. It is very likely that the product of the terms of a finite arithmetic progression of length at least four is never a perfect power. In the present paper it is shown how Erdős’ methods have been extended to obtain results for arithmetic progressions.

T. N. Shorey, Robert Tijdeman
Sur la non-dérivabilité de fonctions périodiques associées à certaines formules sommatoires

Les fonctions arithmétiques associées aux systèmes de représentations d’entiers, comme le développement dans une base donnée, satisfont généralement des relations de récurrence qui facilitent considérablement l’étude de leur valeur moyenne.

Gérald Tenenbaum
1105: First Steps in a Mysterious Quest

During the summer of 1975, I spent a few days with my mother and sister who were on holidays near La Baule. I had just left

École Polytechnique

, and needed some rest after the military service.

Gérald Tenenbaum

III. Randomness and Applications

Frontmatter
Games, Randomness and Algorithms

The object of this 50 % survey and 50 % “theorem-proof” paper is to demonstrate recent developments of some of the ideas initiated by Erdős [17, 18], Erdős and Selfridge [201], Erdős and Lovász [19] and Erdős and Chvátal [15].

József Beck
On Some Hypergraph Problems of Paul Erdős and the Asymptotics of Matchings, Covers and Colorings

This article summarizes progress on several old hypergraph problems of Paul Erdős and a few questions to which they led. Quite unexpectedly, there turned out to be substantial connections between the problems under discussion, surely some indication (if any were needed) that Erdős’ questions were the “right” ones. Here’s a quick synopsis.

Jeff Kahn
The Origins of the Theory of Random Graphs

The origins of the theory of random graphs are easy to pin down. Undoubtedly one should look at a sequence of eight papers co-authored by two great mathematicians: Paul Erdős and Alfred Rényi, published between 1959 and 1968:

Michał Karoński, Andrzej Ruciński
An Upper Bound for a Communication Game Related to Time-Space Tradeoffs

We prove an unexpected upper bound on a communication game proposed by Jeff Edmonds and Russell Impagliazzo [

2

,

3

] as an approach for proving lower bounds for time-space tradeoffs for branching programs. Our result is based on a generalization of a construction of Erdős, Frankl and Rödl [

5

] of a large 3-hypergraph with no 3 distinct edges whose union has at most 6 vertices.

Pavel Pudlák, Jiří Sgall
How Abelian is a Finite Group?

The first paper with the above title was written by Erdős and Straus. Here we solve one of the problems considered there by proving that every group of order

n

contains an abelian subgroup of order at least

$${2}^{\varepsilon \sqrt{\log n}}$$

for some

$$\varepsilon > 0$$

. This result is essentially best possible.We also give a quick survey of recent developments in related areas of group theory which were greatly stimulated by questions of Erdős.

Lásló Pyber
On Small Size Approximation Models

In this paper we continue the study of the method of approximations in Boolean complexity. We introduce a framework which naturally generalizes previously known ones. The main result says that in this framework there exist approximation models providing in principle exponential lower bounds for almost all Boolean functions, and such that the number of testing functionals

is only singly exponential in the number of variables

.

Alexander A. Razborov
The Erdős Existence Argument

The Probabilistic Method is now a standard tool in the combinatorial toolbox but such was not always the case. The development of this methodology was for many years nearly entirely due to one man: Paul Erdős. Here we reexamine some of his critical early papers. We begin, as all with knowledge of the field would expect, with the 1947 paper Erdős P (1947) Some remarks on the theory of graphs. Bull Amer Math Soc 53:292–294 giving a lower bound on the Ramsey function

R

(

k

,

k

). There is then a curious gap (certainly

not

reflected in Erdős’s overall mathematical publications) and our remaining papers all were published in a single ten year span from 1955 to 1965.

Joel Spencer

IV. Geometry

Frontmatter
Extension of Functional Equations

Extension theorems are common in various areas of mathematics. In topology continuous extensions of continuous functions are studied. In functional analysis one is interested mainly in linear extensions of linear operators preserving continuity or some other properties like bounds or norm. In algebra extensions of homomorphisms and isomorphisms are investigated. The latter can be considered as extensions of functional equations.

János Aczél, László Losonczi
Remarks on Penrose Tilings

This paper will cover some details on Penrose tilings presented in lectures over the years but never published in print before. The main topics are: (i) the characterizability of Penrose tilings by means of a local rule that does not refer to arrows on the edges of the tiles, and (ii) the fact that the Ammann quasigrid of the inflation of a Penrose tiling is topologically equivalent to the pentagrid that generates the original tiling.

N. G. de Bruijn
Distances in Convex Polygons

One of Paul Erdős’s many continuing interests is distances between points in finite sets. We focus here on conjectures and results on intervertex distances in convex polygons in the Euclidean plane. Two conjectures are highlighted. Let

t

(

x

) be the number of different distances from vertex

x

to the other vertices of a convex polygon

C

, let

$$T(C) = \Sigma t(x)$$

, and take

$$T_{n} =\min \{ T(C) : C\mbox{ has $n$ vertices}\}$$

. The first conjecture is

$$T_{n} = \left ({ n \atop 2} \right )$$

. The second says that if

$$T(C) = \left ({ n \atop 2} \right )$$

for a convex

n

-gon, then the

n

-gon is regular if

n

is odd, and is what we refer to as bi-regular if

n

is even. The conjectures are confirmed for small

n

.

Peter Fishburn
Unexpected Applications of Polynomials in Combinatorics

In the last 6 years, several combinatorics problems have been solved in an unexpected way using high degree polynomials. The most well-known of these problems is the distinct distance problem in the plane.

Larry Guth
The Number of Homothetic Subsets

We investigate the maximal number

S

(

P

,

n

) of subsets of a set of

n

elements homothetic to a fixed set

P

. Elekes and Erdős proved that

S

(

P

,

n

) >

cn

2

if |

P

| = 3 or the elements of

P

are algebraic. For |

P

| ≥ 4 we show that

S

(

P

,

n

) >

cn

2

if and only if every quadruple in

P

has an algebraic cross ratio. Moreover, there is a sequence

S

n

of numbers such that

$$S(P,n) \asymp S_{n}$$

whenever |

P

| = 4 and the cross ratio of

P

is transcendental.

Miklós Laczkovich, Imre Z. Ruzsa
On Lipschitz Mappings Onto a Square

The following problem was posed by Laczkovich [5]: Let

$$E \subseteq \mathbb{R}{\mathbb{R}}^{d}$$

(

d

≥ 2) be a set with positive Lebesgue measure

λ

d

(

E

) > 0. Does there exist a Lipschitz mapping

$$f : {\mathbb{R}}^{d} \rightarrow Q = {[0,1]}^{d}$$

, such that

f

(

E

) =

Q

? Preiss [6] answered this question affirmatively for

d

= 2:

Jiří Matoušek
A Remark on Transversal Numbers

In his classical monograph published in 1935, Dénes König [23] included one of Paul Erdős’s first remarkable results: an infinite version of the Menger theorem. This result (as well as the König-Hall theorem for bipartite graphs, and many related results covered in the book) can be reformulated as a statement about transversals of certain hypergraphs.

János Pach
In Praise of the Gram Matrix

We use the Gram matrix to prove that the largest number of points in

R

d

such that the distance between all pairs is an odd integer (the square root of an odd integer) is ≤

d

+ 2 and we characterize all dimensions

d

for which the upper bound is attained. We also use the Gram matrix to obtain an upper bound for the smallest angle determined by sets of

n

lines through the origin in

R

d

.

Moshe Rosenfeld
On Mutually Avoiding Sets

Two finite sets of points in the plane are called mutually avoiding if any straight line passing through two points of any one of these two sets does not intersect the convex hull of the other set. For any integer

n

, we construct a set of

n

points in general position in the plane which contains no pair of mutually avoiding sets of size more than

$$\mathcal{O}(\sqrt{n})$$

each. The given bound is tight up to a constant factor, since Aronov et al. [1] showed a polynomial-time algorithm for finding two mutually avoiding sets of size

$$\Omega (\sqrt{n})$$

each in any set of

n

points in general position in the plane.

Pavel Valtr
Metadaten
Titel
The Mathematics of Paul Erdős I
herausgegeben von
Ronald L. Graham
Jaroslav Nešetřil
Steve Butler
Copyright-Jahr
2013
Verlag
Springer New York
Electronic ISBN
978-1-4614-7258-2
Print ISBN
978-1-4614-7257-5
DOI
https://doi.org/10.1007/978-1-4614-7258-2