ζ(s)=pprime(1ps)1\zeta(s) = \displaystyle\prod_{p \: prime}^\infty (1-p^{-s})^{-1}

In the 18th century, Euler found a powerful connection between number theory, primarily the study of primes, and analysis, the study of Taylor series and infinite expansions. This link between two previously unrelated subjects created the basis for modern analytic number theory, and it appears in the title. At a first glance this is relating the Riemann Zeta function, ζ(s)\zeta(s), to an infinite product involving primes. This is a strong hint that this function is closely connected to prime numbers.

As it turns out, it really is! A relatively simple consequence is finding the infinite harmonic sum of prime numbers, or 1/p \sum 1/p , which diverges thanks to Euler's product formula. A more significant implication is the prime number theorem, whose proof eventually relies on the zeta function having no zeroes on a certain strip. Finally, there's an exact formula relating the number of primes below a given number xx involving the zeroes of ζ(s)\zeta(s), suggested (but not proved!) by Riemann.

π(x)=n=1μ(n)n0x1/ndtln(t)+ρn=1μ(n)n0xρ/ndtln(t)1ln(x)+π1tan1(π/ln(x)) \pi(x) = \displaystyle\sum_{n=1}^\infty \frac{\mu(n)}{n} \displaystyle\int_{0}^{x^{1/n}} \frac{dt}{ln(t)} + \displaystyle\sum_{\rho} \displaystyle\sum_{n=1}^\infty \frac{\mu(n)}{n} \displaystyle\int_{0}^{x^{\rho/n}} \frac{dt}{ln(t)} - \frac{1}{ln(x)} + \pi^{-1}tan^{-1}(\pi/ln(x))

Where π(x)\pi(x) represents the prime counting function, μ(n)\mu(n) is the Möbius function and ρ\rho are all non-trivial zeroes of ζ(s)\zeta(s). This creates a far more explicit connection between zeroes of ζ(s)\zeta(s) and primes, though it is way more complicated and very hard to prove.

Returning back to our main topic, the examples above all start from a common point: the identity known as the Euler product formula.

ζ(s)=n=11ns=pprime11ps\zeta(s) = \displaystyle\sum_{n=1}^\infty \frac{1}{n^s}= \displaystyle\prod_{p \: prime}^\infty \frac{1}{1-p^{-s}}

To really understand what's going on, we should isolate the righthand side and set s=1s=1. Doing that won't change the results at all, it will just be easier to write everything out.

ζ(1)=1+12+13+14+=pprime11p1 \zeta(1) = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots =\displaystyle\prod_{p \: prime}^\infty \frac{1}{1-p^{-1}}

We can expand out each term by using the Taylor expansion 11x=1+x+x2+\frac{1}{1-x} = 1 + x + x^2 + \cdots to give us

pprime(1+1p+1p2+) \displaystyle\prod_{p \: prime}^\infty \left( 1 + \frac{1}{p} + \frac{1}{p^{2}} + \cdots \right) =(1+12+14+)(1+13+19+)(1+15+125+) = \left( 1 + \frac{1}{2} + \frac{1}{4} + \cdots \right) \left( 1 + \frac{1}{3} + \frac{1}{9} + \cdots \right) \left( 1 + \frac{1}{5} + \frac{1}{25} + \cdots \right) \cdots

This looks like a wildly complicated expression, but bear with me here. We know that every integer nn can be written as the unique product of its prime factors, n=p1ap2bp3cn = p_1^a p_2^b p_3^c \cdots , and likewise that every possible combination of prime factors leads to a unique integer. This fact is the fundamental theorem of arithmetic. How can we write every possible combination of prime factors in this case?

An easy way is to make the observation that (a+b)(c+d)=ac+ad+bc+bd (a + b )(c + d ) = ac + ad + bc + bd essentially tries every possible combination of terms from both parentheses. This can be generalized to an arbitrary number of terms so that every term on the right side is a unique multiplicative combination of one term each. Since an integer nn is a unique multiplicative combination of primes and their powers, this suggests that we can "construct" all possible integers by using

(1+21+22+)(1+31+32+)(1+51+52+)=1+2+3+4+5+6+7++n+ (1 + 2^1 + 2^2 + \cdots)(1 + 3^1 + 3^2 + \cdots)(1 + 5^1 + 5^2 + \cdots) \cdots = 1 + 2 + 3 + 4 + 5 + 6 + 7 + \cdots + n + \cdots

Where every term on the righthand side can be written as a unique combination of one term from each parenthesized sum. For example, a number such as 20=22520=2^2 \cdot 5 can be constructed by choosing 222^2 from the first term, 11 from the second term, 515^1 from the third, and 11 from all other terms. This holds for reciprocals as well, where any number 1/n1/n can be expressed as a unique combination of terms from

(1+12+122+)(1+13+132+)(1+15+152+) \left( 1 + \frac{1}{2} + \frac{1}{2^2} + \cdots \right) \left( 1 + \frac{1}{3} + \frac{1}{3^2} + \cdots \right) \left( 1 + \frac{1}{5} + \frac{1}{5^2} + \cdots \right) \cdots

Generalizing this to arbitrary powers leads us back to the product formula

1+12s+13s+14s+15s+=pprime11ps 1 + \frac{1}{2^s} + \frac{1}{3^s} + \frac{1}{4^s} + \frac{1}{5^s} + \cdots =\displaystyle\prod_{p \: prime}^\infty \frac{1}{1-p^{-s}}

Which we now know relies on the fundamental theorem of arithmetic. I'll say more about this at the end of the note.

We can also prove this equality starting from the lefthand side. This is how Euler originally proved this formula.

ζ(s)=1+12s+13s+14s+15s+ \zeta(s) = 1 + \frac{1}{2^s} + \frac{1}{3^s} + \frac{1}{4^s} + \frac{1}{5^s} + \cdots

Dividing by a prime psp^s will "pick out" the terms with psp^s as a prime factor. Here's an example of what this leads to

ζ(s)ps=1ps+1(2p)s+1(3p)s+1(4p)s+ \frac{\zeta(s)}{p^s} = \frac{1}{p^s} + \frac{1}{(2p)^s} + \frac{1}{(3p)^s} + \frac{1}{(4p)^s} + \cdots ζ(s)2s=12s+14s+16s+18s+ \frac{\zeta(s)}{2^s} = \frac{1}{2^s} + \frac{1}{4^s} + \frac{1}{6^s} + \frac{1}{8^s} + \cdots

It's generally not advised to add or subtract infinite sums, but we end up being justified doing so here. We can now use this to "remove" all multiples of a given prime from the series expansion of ζ(s) \zeta(s) .

(112s)ζ(s)=1+13s+15s+17s+19s+ \left(1 - \frac{1}{2^s}\right)\zeta(s) = 1 + \frac{1}{3^s} + \frac{1}{5^s} + \frac{1}{7^s} + \frac{1}{9^s} + \cdots

We can repeat this again for 33

(113s)(112s)ζ(s)=1+15s+17s+111s+113s+ \left(1 - \frac{1}{3^s}\right) \left(1 - \frac{1}{2^s}\right)\zeta(s) = 1 + \frac{1}{5^s} + \frac{1}{7^s} + \frac{1}{11^s} + \frac{1}{13^s} + \cdots

This is essentially the Sieve of Eratosthenes. We can sieve up to a prime pnp_n to get the right-hand side to the form pn+1p_{n+1}

ζ(s)p=2p=pn(1ps)=1+1pn+1s+=1+ϵ \zeta(s) \displaystyle\prod_{p=2}^{p=p_n} (1-p^{-s}) = 1 + \frac{1}{p_{n+1}^s} + \cdots = 1 + \epsilon

As 1/ϵ0 1/\epsilon \to 0 as pp \to \infty, we get the equality

ζ(s)p=2p=(1ps)=1 \zeta(s) \displaystyle\prod_{p=2}^{p=\infty} (1-p^{-s}) = 1

Which returns us back to the Euler product formula. Believe it or not, this argument also requires the fundamental theorem of arithmetic, but in a less explicit way related to the Sieve of Eratosthenes. In some sense, given the ubiquity of this formula in number theory and the study of zeta functions, maybe it could be argued that this is "the" main consequence of the fundamental theorem of arithmetic. It has some competition.

If you're familiar with logic, you may be able to know that logical sentences can be encoded in an unambiguous way into the natural numbers. For example, take the sentence ϕ\phi, xy(x2=y) \forall x \exists y(x^2=y) . We can break it up into each symbol

[,x,,y,(,x,x,=,y,)] [\forall, x, \exists, y,(,x,x,=,y,)]

And assign values to each symbol such as #()1,#()2,#(()3,#())5,#(x)7,#(y)11,#(=)13 \#(\forall) \to 1, \#(\exists) \to 2, \#(() \to 3, \#()) \to 5, \#(x) \to 7,\#(y) \to 11, \#(=) \to 13 . Creating a number

#(ϕ)=21375271111313717719132311295 \#(\phi) = 2^1 3^7 5^2 7^{11} 11^3 13^7 17^7 19^{13} 23^{11} 29^5

Which, while very large, 'encodes' that particular sentence in logic into a number - known as its Gödel code - where it is now in the realm of arithmetic. This might not seem very useful, but thanks to the fundamental theorem of arithmetic we can go in the opposite direction to find what logical sentence any arbitrary number represents via its unique prime factorization. This eventually leads to defining arithmetic functions which can extract meta-information about a given logical sentence. With a far more careful coding scheme than the one I showed here, Gödel managed to fully encode logic into arithmetic. This had severe consequences though: he managed to define provability as an arithmetical function and, using a fixed-point lemma, found the existence of a sentence that is true if and only if it isn't provable in arithmetic. This was his first incompleteness theorem - the result that in any mathematical system in which the fundamental theorem of arithmetic holds, that system must have theorems which are unprovable within it.

Note by Levi Adam Walker
3 weeks, 4 days ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Wow ! Thank you for sharing this incredible formula for π(x)\pi(x)! That is the first time I see it, I always wondered if there was more than the Euler product linking prime number and ζ\zeta (I knew the answer is yes but I did not know what).

Bay the way, just a little typo in the title, it misses the s-s.

Théo Leblanc - 3 weeks, 4 days ago

Log in to reply

You're right, thanks for catching that :)

Levi Adam Walker - 3 weeks, 4 days ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...