Chebyshev’s Trick: Binomial Coefficients and How Many Primes There Are

Chebyshev’s Trick: Διωνυμικοί Συντελεστές και το «Μέτρημα» των Πρώτων

Από τους διωνυμικούς συντελεστές στους πρώτους αριθμούς

Ο Τσεμπίσεφ και το “μέτρημα” των πρώτων

Όλοι ξέρουμε ότι υπάρχουν άπειροι πρώτοι αριθμοί: 2, 3, 5, 7, 11, 13, … Αυτό το είχε ήδη αποδείξει ο Ευκλείδης: αν πολλαπλασιάσεις όλους τους πρώτους μέχρι κάποιον αριθμό και προσθέσεις 1, παίρνεις έναν νέο αριθμό που έχει κάποιον νέο πρώτο διαιρέτη – άρα ποτέ δεν «τελειώνουν» οι πρώτοι.

Οι μαθηματικοί όμως δεν σταμάτησαν εκεί. Δεν τους αρκεί το «άπειροι». Θέλουν να ξέρουν πόσοι περίπου πρώτοι υπάρχουν μέχρι έναν μεγάλο αριθμό x. Αυτή την ποσότητα τη συμβολίζουμε με:

π(x) = αριθμός πρώτων ≤ x.

Παραδείγματα:

• π(10) = 4 (οι πρώτοι είναι 2, 3, 5, 7)
• π(100) = 25
• π(1.000.000.000) είναι πάνω από 50 εκατομμύρια!

Γύρω στον 19ο αιώνα έγινε ξεκάθαρο ότι η σωστή περίπου «φόρμουλα» για αυτό το μέτρημα είναι:

π(x) ≈ x / ln x.

Αυτό είναι το Θεώρημα των Πρώτων Αριθμών. Η πλήρης απόδειξη είναι πολύ δύσκολη. Πριν όμως φτάσουν εκεί, κάποιοι μαθηματικοί – και ανάμεσά τους ο Τσεμπίσεφ (Chebyshev) – κατάφεραν με στοιχειώδη μέσα να δείξουν ότι:

οι πρώτοι μέχρι το x είναι περίπου της τάξης του x / ln x.

Δηλαδή δεν πέσαμε τελείως έξω· το μέγεθος είναι σωστό. Και το κατάφεραν χρησιμοποιώντας κάτι που μοιάζει… άσχετο: έναν διωνυμικό συντελεστή.

Ο “ήρωας” της ιστορίας: ο κεντρικός διωνυμικός συντελεστής

Ο Τσεμπίσεφ κοιτάζει τον αριθμό:

a_n = C(2n, n) = (2n)! / (n!)².

Αυτός ο αριθμός εμφανίζεται παντού: στο τρίγωνο του Pascal, στις πιθανότητες, στη συνδυαστική. Εδώ όμως παίζει έναν άλλο ρόλο: είναι μια «δεξαμενή» μέσα στην οποία κρύβονται όλοι οι πρώτοι μεταξύ n και 2n.

Παρατήρηση:

a_n = (n + 1)(n + 2)⋯(2n) / (1⋅2⋯n).

Άρα, στον αριθμητή βρίσκονται όλοι οι αριθμοί από n + 1 μέχρι 2n.

Αν πάρουμε έναν πρώτο p με n < p ≤ 2n, τότε:

• ο p εμφανίζεται στον αριθμητή,
• δεν εμφανίζεται στον παρονομαστή (όλοι οι αριθμοί εκεί είναι ≤ n),

άρα ο πρώτος p διαιρεί τον a_n.

Συνεπώς, ο κεντρικός διωνυμικός συντελεστής C(2n, n) είναι πολλαπλάσιο του γινομένου όλων των πρώτων μεταξύ n και 2n:

C(2n, n) ≥ ∏_n<p≤2n p.

Αυτή είναι η βασική ιδέα του Τσεμπίσεφ: ένας “συνδυαστικός” αριθμός κουβαλάει πληροφορία για τους πρώτους.

Πώς μπαίνει ο λογάριθμος στο παιχνίδι

Για να μετατρέψουμε το «γινόμενο όλων των πρώτων» σε κάτι πιο διαχειρίσιμο, παίρνουμε λογάριθμους. Θυμόμαστε ότι:

ln(∏ p) = ∑ ln p.

Εδώ εμφανίζεται μια κλασική συνάρτηση της θεωρίας αριθμών:

θ(x) = ∑_p≤x ln p,

δηλαδή το άθροισμα των λογαρίθμων όλων των πρώτων μέχρι το x.

Από την ανισότητα

C(2n, n) ≥ ∏_n<p≤2n p

παίρνουμε λογάριθμο και προκύπτει χοντρικά:

ln C(2n, n) ≥ θ(2n) − θ(n).

Από την άλλη, υπάρχει και μια άνω εκτίμηση για το C(2n, n) (με γνωστές ανισότητες ή με τον τύπο του Stirling), η οποία δίνει μια ανισότητα της μορφής:

θ(2n) − θ(n) ≤ C⋅n

για κάποια σταθερά C.

Επαναλαμβάνοντας τη διαδικασία για 2n, 4n, 8n, … καταλήγουμε τελικά σε μια γραμμική εκτίμηση:

θ(x) ≤ C₂x,

αλλά και σε μια κάτω εκτίμηση:

θ(x) ≥ C₁x,

για κατάλληλες σταθερές C₁, C₂ > 0 και x αρκετά μεγάλο.

Στο άρθρο που συζητούμε προκύπτουν, για x ≥ 854, ανισότητες της μορφής:

(1 / (7 ln 2)) x < θ(x) ≤ 4 (ln 2) x.

Από το θ(x) στο π(x): πώς περνάμε στους «αριθμούς» των πρώτων

Η συνάρτηση θ(x) ασχολείται με λογαρίθμους πρώτων. Εμείς όμως θέλουμε το πλήθος των πρώτων π(x).

Χοντρικά:

• Αν μέχρι το x υπάρχουν π(x) πρώτοι,
• και καθένας έχει ln p ≤ ln x,

τότε:

θ(x) = ∑_p≤x ln p ≤ π(x) ln x.

Άρα:

π(x) ≥ θ(x) / ln x.

Αν βάλουμε την κάτω εκτίμηση για θ(x), παίρνουμε:

π(x) ≳ x / ln x.

Αντίστοιχα, με λίγη περισσότερη δουλειά, παίρνουμε και μια άνω εκτίμηση:

π(x) ≲ C⋅x / ln x

για κάποια σταθερά C. Το τελικό αποτέλεσμα είναι ότι υπάρχουν σταθερές A, B > 0 τέτοιες ώστε, για x μεγάλο:

A⋅x / ln x ≤ π(x) ≤ B⋅x / ln x.

Δηλαδή, ναι, το σωστό «μέγεθος» του π(x) είναι x / ln x.

Τι κερδίσαμε;

Με καθαρά στοιχειώδη εργαλεία:

• διωνυμικούς συντελεστές C(2n, n),
• βασικές ιδιότητες της παραγοντικής n!,
• λίγη λογαριθμική άλγεβρα,

ο Τσεμπίσεφ έδειξε ότι:

• οι πρώτοι δεν είναι τόσο αραιοί όσο φοβόμαστε,
• ούτε όμως και «υπερβολικά πολλοί»,
• αλλά ακολουθούν (σε μέγεθος) το μοτίβο x / ln x.

Αυτό άνοιξε τον δρόμο για το Θεώρημα των Πρώτων Αριθμών και για τη μεγάλη επανάσταση του Riemann και της μιγαδικής ανάλυσης στη θεωρία αριθμών.

Chebyshev’s Trick: Binomial Coefficients and How Many Primes There Are

From Binomial Coefficients to Prime Numbers

Chebyshev and the “Counting” of Primes

We all know that there are infinitely many prime numbers: 2, 3, 5, 7, 11, 13, … Euclid had already proved this: if you multiply all primes up to some number and add 1, you obtain a new number that must have a new prime divisor — so the primes can never “run out.”

But mathematicians did not stop there. “Infinite” is not enough. They wanted to know approximately how many primes there are up to a large number x. This quantity is denoted by:

π(x) = number of primes ≤ x.

Examples:

• π(10) = 4 (the primes are 2, 3, 5, 7)
• π(100) = 25
• π(1,000,000,000) is more than 50 million!

By the 19th century it became clear that the correct approximate “formula” for this counting function is:

π(x) ≈ x / ln x.

This is the Prime Number Theorem. Its full proof is extremely difficult. Long before that, however, some mathematicians — among them Chebyshev — managed, using only elementary tools, to show that:

π(x) is roughly of order x / ln x.

In other words, they proved that the size of π(x) is correct, even without the exact asymptotic formula. And they did this using something that looks completely unrelated: a binomial coefficient.

The Hero of the Story: The Central Binomial Coefficient

Chebyshev focused on the number

a_n = C(2n, n) = (2n)! / (n!)².

This number appears everywhere: in Pascal’s triangle, in probability theory, in combinatorics. But here it plays a different role: it becomes a “container” in which all the primes between n and 2n are hidden.

Observation:

a_n = (n + 1)(n + 2)⋯(2n) / (1⋅2⋯n).

So the numerator contains all integers from n + 1 up to 2n.

If p is a prime with n < p ≤ 2n, then:

• p appears in the numerator,
• p does not appear in the denominator (every number there is ≤ n),

hence the prime p divides a_n.

Therefore, the central binomial coefficient C(2n, n) is a multiple of the product of all primes between n and 2n:

C(2n, n) ≥ ∏_n<p≤2n p.

This is Chebyshev’s key idea: a “combinatorial” number carries information about primes.

How the Logarithm Enters the Game

To turn the “product of all these primes” into something more manageable, we take logarithms. We recall that:

ln(∏ p) = ∑ ln p.

Here we meet a classical function of number theory:

θ(x) = ∑_p≤x ln p,

the sum of the logarithms of all primes up to x.

From the inequality

C(2n, n) ≥ ∏_n<p≤2n p

we take logarithms and obtain, roughly:

ln C(2n, n) ≥ θ(2n) − θ(n).

On the other hand, there is an upper bound for C(2n, n) (via known inequalities or Stirling’s formula), which yields an inequality of the form:

θ(2n) − θ(n) ≤ C⋅n

for some constant C.

Repeating the argument for 2n, 4n, 8n, … we eventually get a linear estimate:

θ(x) ≤ C₂x,

and also a lower estimate:

θ(x) ≥ C₁x,

for suitable constants C₁, C₂ > 0 and sufficiently large x.

In the article you referred to, one obtains, for x ≥ 854, inequalities of the form:

(1 / (7 ln 2)) x < θ(x) ≤ 4 (ln 2) x.

From θ(x) to π(x): Getting the Prime Count

The function θ(x) deals with logarithms of primes. What we really want, however, is the number of primes π(x).

Roughly:

• Suppose there are π(x) primes up to x,
• each of them satisfies ln p ≤ ln x.

Then:

θ(x) = ∑_p≤x ln p ≤ π(x) ln x.

Thus:

π(x) ≥ θ(x) / ln x.

Using the lower bound for θ(x), we obtain:

π(x) ≳ x / ln x.

Similarly, with a bit more work, we can also deduce an upper bound:

π(x) ≲ C⋅x / ln x

for some constant C. The final outcome is that there exist constants A, B > 0 such that, for sufficiently large x:

A⋅x / ln x ≤ π(x) ≤ B⋅x / ln x.

In other words, the correct **order of growth** of π(x) is x / ln x.

What Have We Gained?

Using purely elementary tools:

• binomial coefficients C(2n, n),
• basic properties of factorials n!,
• a bit of logarithmic algebra,

Chebyshev showed that:

• primes are not as sparse as one might fear,
• nor are they “too many”,
• instead, they follow the growth pattern x / ln x.

This work opened the way toward the Prime Number Theorem and the later revolution brought by Riemann and complex analysis in number theory.

Short technical recap

Chebyshev studied the central binomial coefficient

C(2n, n) = (2n)! / (n!)²

and observed that every prime p with n < p ≤ 2n must divide this number. Thus

C(2n, n) ≥ ∏_n<p≤2n p.

Taking logarithms links the size of C(2n, n) to

θ(x) = ∑_p≤x ln p.

By bounding θ(x) from above and below using only elementary methods, Chebyshev proved that for large x

c₁x ≤ θ(x) ≤ c₂x

for suitable constants c₁, c₂ > 0. Since θ(x) ≤ π(x) ln x, this implies bounds of the form

A⋅x / ln x ≤ π(x) ≤ B⋅x / ln x.

Long before the full Prime Number Theorem was proved, Chebyshev had thus shown that the correct order of growth for the number of primes up to x is x / ln x.