An elegant proof from Erdős

Here’s an elegant proof from Paul Erdős that there are infinitely many primes. It also does more, giving a lower bound on π(N), the number of primes less than N.

First, note that every integer n can be written as a product n = r s2 where r and s are integers and r is square-free, i.e. not divisible by the square of any integer. To see this, let s2 be the largest square dividing n and set r = n / s2.

Next we over-estimate how many r s2 factorizations there are less than or equal to N.

How many square-free numbers are there less than or equal to N? Every such number corresponds to a product of distinct primes each less than or equal to N. There are π(N) such primes, and so there are at most 2π(N) square-free numbers less than or equal to N. (The number of subsets of a set with m elements is 2m.)

How many squares are there less than N? No more than √N because if s > √N then s2 > N.

So if we factor every number ≤ N into the form r s2 there are at most 2π(N) possibilities for r and at most √N possibilities for s. This means

2π(N)NN

Now divide both sides of this inequality by √N and take logarithms. This shows that

π(N) ≥ log(N) / log 4

The right side is unbounded as N increases, so the left side must be unbounded too, i.e. there are infinitely many primes.

Euclid had a simpler proof that there are infinitely many primes. But unlike Euclid, Erdős gives a lower bound on π(N).

Source: Not Always Buried Deep

Related posts

16 thoughts on “An elegant proof from Erdős

  1. There are π(N) such primes, and so there are 2π(N) square-free numbers less than or equal to N

    Why?

    If primes are less than N, it doesn’t mean that their product is less than N
    There are primes 2,3,5 below 6, but 3*5 is not less than 6.
    There are only five (1,2,3,5,6) squre-free numbers below six, not 2^3 = 8.

    Thanks for great blog records!

  2. There is often a lot less square-free numbers ≤N than 2^π(N). I would emphasize on the fact that the difference between pi(N) and log(N)/2 comes from this over-estimation. (Whereas the √N over-estimation of the number of squares ≤N is pretty accurate.)

    Very nice proof, though.

  3. It’s a very nice proof. I’m just wondering about a detail. I think there are *at most* 2^pi(N) square-free numbers less than or equal to N, because if you multiply primes less than N you do not necessarily get a number less than N. Of course this does not matter for the proof.

  4. Thanks for the comments. Yes, I should have said “at most” regarding the number of square-free numbers <= N. I updated the post with that correction.

  5. “Next we over-estimate how many r s2 factorizations there are less than N.”

    is it “less than or equal to N”? (i.e., “up to N”?)

  6. I’m wondering if this bound can be improved by, say, counting cube-free numbers instead of square-free numbers.

  7. You lost me at the line:

    “So if we factor every number ≤ N into the form r s^2 there are at most 2π(N) possibilities for r and at most √N possibilities for s. This means

    2π(N) √N ≥ N”

    Could you explain this bit in more detail?

  8. Upon further thought, the inequality
    2^π(N) √N ≥ N
    arises from the fact that each integer == N.

  9. Upon further thought, the inequality
    2^π(N) √N ≥ N
    arises from the fact that each integer ≤ N may be written as one of the products r * s^2, when we allow r to be any square-free integer with distinct prime factors each ≤ N, and s to range from 1 to √N. But among these products there may also be integers greater than N. Thus, the set of products includes at least the first N integers, and so 2^π(N) √N ≥ N.

    (HTML caused formatting problems in the last post, sorry.)

  10. The Euclid argument proves that p_k is not greater than 2*3*…*p_{k-1}+1.
    Working on this furmula you prove that p_k leq 2^{2^{k-1}}, or, which is the same, that pi(N) geq log_2(log_2 N). Thus, also Euclid gives a concrete lower bound, but weaker.

  11. > How many squares are there less than N? No more than √N because if s > √N then s<sup2 > N.

    This confused me for a bit until I realized that s was being reused as an integer and not as the original largest square in N. The original definition of s doesn’t have any need to be invoked for that line.

  12. Working with (m-th power)-free numbers, we obtain

    2^(pi(N)) * N^(1/m) \geq N

    or pi(N) \geq (m-1)/m * log_2(N)

    These lower bounds keep increasing, and taking the limit as m–> infinity, we get

    pi(N) \geq log_2(N) which is just twice as much as the bound obtained above.

Leave a Reply

Your email address will not be published.