Big List of Erdős' elementary proofs

Question

Paul Erdős was one of the greatest mathematicians of all time and he was famous for his elegant proofs from The Book. I posted a question about one of his theorem and got a reference, and I have other questions I want to know the answer to too. But, instead of requesting a reference for each theorem he gave with an elementary proof, I've decided to make a thread for a big list of all his elementary proofs.

I'm excited. Let's make an index of the pages of the Book shown to us!

Please feel free to contribute.

To get you guys started, I will make a wish list of his theorems who's references I want to see. I encourage you to add to my wish list if you so desire.

Wish list :

• The product of two or more consecutive positive integers is never a square or any other higher power.
• A connected graph with a minimum degree $d$ and at least $2d+1$ vertices has a path of length at least $2d+1$.
• Let $d(n)$ be the number of divisors of $n$. Then the series $\sum_{n=1}^\infty d(n)/2^n$ converges to an irrational number
• Let $g(n)$ be the minimal number of points in the general position in the plane needed to ensure a subset exists that forms a convex $n$-gon. Then $$2^{n-2} + 1 \leq g(n) \leq \frac{(2n-4)!}{(n-2)!^2} + 1$$
• Erdos-Rado theorem
• Erdős-Mordell inequality

Answer 1

I think this is worth posting here, mostly because I really enjoy the simplicity of this proof but also because I have no idea how well it is known. The result is not deep or important, so the main interest is in the simplicity of the argument. Erdős proved a lower bound on the number of primes before an integer $n$.

Wacław Sierpiński, in his Elementary Theory of Numbers, attributes to Erdős the following elementary proof of the inequality $$\pi(n)\geq\frac{\log{n}}{2\log{2}}\quad\text{for }n=1,2,\ldots.$$

Please note that I have adapted the argument from the text of the book to make things, in my opinion, a bit clearer. Note also that the only tools used in the below proof are some basic combinatorial facts and some results about square-free numbers, which can, for example, be proved with the Fundamental Theorem of Arithmetic.

Let $n\in\mathbb{N}=\{1,2,3,\ldots\}.$ Consider the set $$S(n) = \{(k,l)\in\mathbb{N}^{2}:l\text{ is square-free and }k^{2}l\leq n\}.$$ It is a standard fact that every natural number has a unique representation in the form $k^{2}l,$ where $k$ and $l$ are natural numbers and $l$ is square-free. This gives $\lvert S(n)\rvert = n.$

Now if we have a pair $(k,l)$ with $k^{2}l\leq n,$ then we must have $k^{2}\leq n$ and $l\leq n$, since $k$ and $l$ are positive. Note that this gives $k\leq\sqrt{n}.$ Since $l$ is square-free, $l$ can be expressed as a product of distinct primes, each of which must be not-greater-than $n$ since $l\leq n$. That is, $l$ can be expressed as a product of the primes $p_{1},p_{2},\ldots,p_{\pi(n)}.$ There are $2^{\pi(n)}$ such products.

Therefore, if we know $(k,l)\in S(n)$ then there are at most $\sqrt{n}$ possibilities for what $k$ might be and at most $2^{\pi(n)}$ possibilities for what $l$ might be (independent of $k$, of course). It follows that $\lvert S(n)\rvert \leq 2^{\pi(n)}\sqrt{n},$ so $n\leq2^{\pi(n)}\sqrt{n}.$

Taking $\log$s and rearranging gives the result.

Answer 2

Here is an exposition of the proof that made Erdos famous by David Galvin. An elementary proof of Bertrand's postulate, which states that there is a prime number in between every $n$ and $2n$. The essence of this proof is in noticing that the lower bound of $$\binom{2n}{n} \geq \frac{4^n}{2n + 1}$$ The binomial expression is the middle term (and the largest) of $(1+x)^{2n}$. The lower bound is the average of the sum of all binomial coefficients. This is obtained by putting $x=1$, and then dividing by the number of terms. This gives us the average. Obviously, the largest term should be bigger than the average. If the postulate does not hold, there is an upper bound that is smaller than this lower bound for large $n$. The postulate can easily be verified for the smaller values of $n$.

https://www3.nd.edu/~dgalvin1/pdf/bertrand.pdf

Answer 3

One very simple, and yet one of my favorites is the Erdős-Anning theorem:

Let $ A \subseteq \mathbb C $ be an infinite set of points, such that

$$ \forall x, y\in A \quad |x-y| \in \mathbb N $$

then there exists some $ c,k \in \mathbb C $, such that all $ a \in A $ is of the form $ a = cx + k $ for some $ x \in \mathbb R $.

It was proved in 1945 in the American Mathematical Bulletin. http://www.ams.org/journals/bull/1945-51-08/S0002-9904-1945-08407-9/S0002-9904-1945-08407-9.pdf

---

A more colorful formulation is that an infinite sets of points on the Cartesian plain with mutual integer distances must lie on a straight line.

To prove it, we need an upper bound on the number of non collinear points possible in a set with integral distances. More specifically, if there is a set of non collinear points have integer distances, all at most $d$, then at most $4(d + 1)^2$ points with integer distances can be added to the set.

Answer 4

Erdos' proof of Infinite primes

The following proof is taken from the book - "Proofs from THE BOOK" by Martin Aigner and Gunter Ziegler. This proof is attributed to Erdos.

This proves that there are infinitely many primes and that the series of the sum of prime reciprocal steps diverges. Let us assume that the infinite series $\sum\frac{1}{p}$, where $p$ denotes the prime numbers is a convergent one. Then, there must exist some natural number $k$ such that, $$\sum_{i > k} \frac{1}{p_i} < \frac{1}{2}$$

For an arbitrary natural number $N$, we get the inequality $$\sum_{i > k} \frac{N}{p_i} < \frac{N}{2}$$

Now, we call all the primes $p_1, p_2, \dots , p_k$ the small primes, and all the other primes the big primes.

Let $N_b$ denote the number of positive integers $n \leq N$ that have at least one divisor that is a big prime. And $N_s$ denote the number of positive integers less than $N$ that have only small prime divisors.

We will show that for a suitable $N$, $N_b + N_s < N$, which is a contradiction because their sum should equal $N$.

First, we estimate $N_b$ $$N_b \leq \sum_{i > k}\big\lfloor \frac{N}{p_i} \big\rfloor < \frac{N}{2}$$

Now, we look at $N_s$. We write every $n \leq N$ as $a_nb_n^2$ where $a_n$ is the square free part. $a_n$ is a product of different small primes. There are only $k$ small primes, and each prime may either be chosen or not chosen. So, there are only $2^k$ different values of $a_n$. Furthermore, \begin{align} b_n \leq \sqrt n \leq \sqrt N \\ \text{There are at most $\sqrt N$ different values of $b_n$} \\ \implies N_s \leq 2^k\sqrt N \end{align}

Since, $N_b$ is always less than $N/2$, we just have to find a value of $N$ such that $N_s \leq N/2$. This happens when $N = 2^{2k + 2}$. When $N = 2^{2k + 4}$, $N_s < N/2$. This proves our contradiction that $$N_b + N_s < N$$ which proves that the series diverges and that there are infinitely many primes.

Answer 5

Erdos' favourite questions. The following are not research papers but popular questions Erdos used to ask children.

• If $n+1$ integers are chosen from the first $2n$ integers, there will always be two that are co prime.

There will be two numbers that are consecutive. These two numbers will be relatively prime. To see that this is not true when $n$ integers are chosen, just select all the even numbers.

• If $n+1$ integers are chosen from the first $2n$ integers, there will always be two such that one divides the other.

Every number is expressible as the product of a power of two and an odd number. There are only $n$ odd numbers in the first $2n$ integers. Two of the numbers are multiplied by the same odd number. One of them has a smaller power of two. This number divides the other. To show that it is not necessarily true for $n$ integers, choose $n+1,n+2, \dots 2n$.

• Suppose we have $n$ natural numbers none of which is greater than $2n$ such that the least common multiple of any two is greater than $2n$. Then, all $n$ numbers are greater than $2n/3$.

Answer 6

Erdos answered the following question in the affirmative - Are there infinitely many odd numbers that are not expressible as the sum of a prime number and a power of $2$. The proof is explained in this paper : http://www.maa.org/sites/default/files/3004416309960.pdf.bannered.pdf

The essence of the proof is in showing that for every integral value of $k$, there is a $2^k$ which has a certain residue with certain moduli. By the Chinese remainder theorem, there are infinitely many odd numbers that satisfy those same congruences. Whenever they do, $a - 2^k$ is composite for all integer values of $k$.

Answer 7

Erdos - Mordell Inequality : For a point $O$ inside a given triangle $ABC$, the perpendiculars $OP$, $OQ$ and $OR$ are drawn to the side $$OA + OB + OC \geq 2(OP + OQ + OR)$$

• Here's a proof from Donat K. Kazarinoff http://projecteuclid.org/download/pdf_1/euclid.mmj/1028988998

• A simple visual proof is provided by Claudi Alsina and Roger Nelson in this paper. http://forumgeom.fau.edu/FG2007volume7/FG200711.pdf

Answer 8

The proof of the Littlewood-Offord lemma for sums of real numbers.

Erdos noticed that under the correspondence between sequences of $\pm$ signs and finite sets, Sperner's theorem applies and gives the optimal bound for the Littlewood-Offord lemma in dimension $1$ (on how many signed sums of $n$ given numbers of absolute value at least $1$, can have absolute value at most $1$). This observation is a few lines of very basic algebra and combinatorics.

The rest of the paper is more difficult, and is an extension of Sperner's theorem to handle the case of larger bounds on the sums, once again reading optimal bounds from the combinatorics. This gave evidence that the higher dimensional Littlewood-Offord problem on sums of vectors might also be essentially combinatorial, which was later shown to be true.

Answer 9

The product of consecutive integers is never a power

This was proved by Erdos and Selfridge.

http://www.renyi.hu/~p_erdos/1975-46.pdf

Answer 10

The Erdos-Ko-Rado theorem is a result about intersecting set families.

Suppose $A$ is a set of $r$ subsets on the set $\{1,2,\dots,n\}$ such that any two sets in $A$ have a non empty subset and $n/2\geq r$, the maximal size of $A$ is $\binom{n-1}{r-1}$ i.e., $$|A| \leq \binom{n-1}{r-1}$$with equality holding if and only if all the sets share a common element.

A family of sets may also be called a hypergraph. When every set in $A$ has the same size $r$, it is called a $r$-uniform hypergraph.

Note : The condition of $n/2 \geq r$ is imposed because if $r$ is more than half of $n$, then any two sets have a non empty intersection. The maximal size of the family is then $\binom nr$.