59
$\begingroup$

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
$\endgroup$
  • 1
    $\begingroup$ You need to define what you mean by "elementary". I think the list of elementary proofs will be very big, e.g. it will contain all his results in set theory, all his results on finite and infinite graphs. $\endgroup$ – bof Jul 6 '16 at 9:31
  • $\begingroup$ @bof Hi bof. It will be big but I don't think all of them will be posted here. For starters, I'm looking for the questions in the wish list. Please post if you have any results $\endgroup$ – user230452 Jul 6 '16 at 9:35
  • 5
    $\begingroup$ Is it fair that 4 people get to close a thread when 50 people have upvoted it ? Please open the thread for further posts $\endgroup$ – user230452 Jul 7 '16 at 10:59
  • $\begingroup$ I voted to reopen. $\endgroup$ – Spenser Jul 7 '16 at 13:00
  • $\begingroup$ @Spenser Thanks, Spencer. I appreciate it. I have collected another theorem of Erdos' to post. $\endgroup$ – user230452 Jul 7 '16 at 13:24

10 Answers 10

23
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ How can you say a lower bound on the Prime Number Theorem is not important ! $\endgroup$ – user230452 Jul 6 '16 at 6:05
  • $\begingroup$ I find this answer about referencing original work on Academia.se worth linking to, cf. your comment :) $\endgroup$ – Therkel Jul 6 '16 at 11:24
  • 1
    $\begingroup$ @user230452: Better bounds are known through elementary arguments (I think the most famous is by Chebyshev, and has the advantage of providing an upper bound of the same order of growth). So this result is not so important since a little more work can give much better results, with still only elementary ideas. $\endgroup$ – Will R Jul 6 '16 at 17:23
  • $\begingroup$ @Therkel: I think I understand, but, in this situation, I felt it best to make clear a) how I knew this argument was from Erdos and b) that chasing up the source would lead readers to a superficially different-sounding argument. $\endgroup$ – Will R Jul 6 '16 at 17:27
  • 3
    $\begingroup$ This is brilliant! $\endgroup$ – Vinícius Novelli Jul 20 '16 at 1:41
15
$\begingroup$

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

$\endgroup$
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I have a doubt. Can you help me ? The theorem says that for any $n$, it is possible to have $n$ points on a plane, not all collinear such that they have integral distances but not infinitely many points. As I understand it, infinity is not a number, but a concept. To say that infinitely many points are possible it means that for any $ n \geq l$, it is possible, where $l$ is an arbitrarily large natural number. It seems to me the first part of the theorem is stating it, and the second is contradicting it. $\endgroup$ – user230452 Jul 6 '16 at 3:45
  • $\begingroup$ @user230452 No, to say that there is an infinite set with integral distances is not the same as saying for any $n\ge l$ there is a set with $n$ points and integral distances. Compare: For any $n\ge l$ there is a bounded subset of $\Bbb R$ with integral distances, but there is no bounded infinite subset of $\Bbb R$ with integral distances. $\Bbb N$ is an unbounded infinite subset of $\Bbb R$ with integral distances. $\endgroup$ – Mario Carneiro Jul 6 '16 at 8:05
  • $\begingroup$ @bof There was a typo; the constraint $ 0 \in A $ was lacking. It is equivalent to adding some constant, s.t. $ a = cx + k $. $\endgroup$ – AnonymousC Jul 6 '16 at 16:23
10
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ Regarding the first one, you can easily see that "all the even numbers" is actually the only solution -- we can't select 1, because it's coprime to everything; and we can't have any consecutive numbers. If we take $n-1$ numbers, a bit of thinking/excluding a few small cases shows that for $n>3$, the only solutions are "all even numbers but one". For $n=3$, we have $\{3,6\}$. In general, any set of $n-k$ must be all even unless $n-k \ge 2n/3$, because we have an odd number at least $3$, which immediately narrows us to $1/3$ of the numbers. I wonder how # of solutions grows with $n$ and $k$? $\endgroup$ – Alex Meiburg Jul 7 '16 at 23:21
  • 1
    $\begingroup$ @Alex, your final conclusion is false. In fact, for all $\epsilon > 0$ there exists an $n$ and a set $S \subset \{1,2,\ldots, 2n\}$ with $|S| > (1 - \epsilon)n$ such that $S$ contains an odd integer and for all $x,y \in S$ we have $\gcd(x,y) > 1$. For example, choose $n$ to be the product of the first $m$ odd primes and define $S = \{2k | k < n \text{ and } \gcd(k, n) > 1 \} \cup \{n\}$. You will see that $|S| = n - \varphi(n) + 1 > n(1 - \frac{c}{\log \log(n)})$ for some absolute constant $c$. For $m \ge 8$ we have $|S| > \frac{2n}{3}$. $\endgroup$ – Woett Oct 11 '18 at 12:00
  • $\begingroup$ @Woett, right, how silly of me. I figured that if $k$ is odd then the density of numbers sharing a factor with $k$ is at most $1/3$ -- totally neglecting the possibility of multiple factors. :) Taking $n=105=3\cdot 5\cdot 7$ gives a density of $0.54$, of course. $\endgroup$ – Alex Meiburg Oct 12 '18 at 2:46
6
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Surely this is clear because the set of all numbers $p+2^k$ is density zero? Although perhaps that is not elementary. $\endgroup$ – Mario Carneiro Jul 7 '16 at 1:20
  • $\begingroup$ The density should be positive, not zero. There are n/log(2) choices of (prime, power of 2) both less than n. If most, or a positive fraction, of those are unique representations then a positive density subset of integers less than 2n have such a representation. $\endgroup$ – zyx Jul 7 '16 at 2:08
  • $\begingroup$ @zyx Oh, indeed if $|A\cap[n]|\sim f(n)$, and $B=\{a+2^k:a\in A,k\in\Bbb N\}$, then $|B\cap[n]|\le\sum_k f(n-2^k)\le f(n)\log_2n$, which is not strong enough to conclude density zero with $A=\Bbb P$, $f(n)=n/\log n$. A simulation of the quantity $\sum_{p\le n}\log_2(n-p)$ appears to converge to about $1.468n$, which is obviously useless as an upper bound on $|B\cap[n]|$ since it's larger than the trivial bound. $\endgroup$ – Mario Carneiro Jul 7 '16 at 4:59
  • $\begingroup$ That is close to n/log(2) = 1.443 n . $\endgroup$ – zyx Jul 7 '16 at 5:08
  • $\begingroup$ Does the simulation appear to converge to 1/log(2) when using integer logarithms, $\lfloor \log_2 ( \dots ) \rfloor$? @MarioCarneiro $\endgroup$ – zyx Jul 7 '16 at 19:10
2
$\begingroup$

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)$$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.