Hacker News Reader

Comment by oneepic | Hacker News Reader

Neat. I mean, I don't understand the mathspeak since I stopped taking math after calculus in college, but it's neat to see fun approaches turn into viable tactics for finding a solution.

By coincidence I toyed with the problem a bit this past week. Pretty difficult to tackle with a "basic" math toolbox (calc, trig, algebra, and some discrete math/number theory that's taught in many CS undergrad curricula). Much like Fermat's Last Theorem, it seems like this might require much higher-level math to solve what seems like a simple problem.

View on HN

Man HR is harsh as hell. While yes, if a proof of RH is found it will probably use advanced tools, ever finding a proof with elementary tools is not totally out of the question. Regarding the Prime Number Theorem, which can be seen as a baby version of RH, experts in the field such as Hardy have been quoted as saying elementary proofs would not exist. Then 50 years after Hadamard and Poussin found the original proofs, Selberg and Erdos published proofs based on elementary methods. No one can say that it's worthless for someone to try the same for RH.

Notice also the decidability of primality in polynomial time, which was proved by some Computer Science graduates (Neeraj Kayal, and Nitin Saxena) in 2011, and led Bombieri (one of the leading experts on Number Theory) to say that Number Theory may have gone astray in theoretical complexity in some fields.

That's very interesting, do you know offhand where Bombieri said that?

I've taken math up to calculus and linear algebra and enjoy watching 3B1B proofs. Is that enough to follow the elementary Prime Number Theorem proof? I've been interested in understanding that for a while. Any good links?

Check out the book “Prime Obsession”

It was easy for me to follow along.

You can probably slog through it with that level of knowledge, if you’v got a good grasp of summation notation.

Here’s one version of the proof: https://www.math.lsu.edu/~mahlburg/teaching/handouts/2014-72...

And, a related, very simple and elementary proof of Chebyschev’s theorem that there is always a prime number between n and 2n: https://en.wikipedia.org/wiki/Proof_of_Bertrand%27s_postulat...

You will need to learn some complex analysis which is very beautiful. Ash has a very good chapter on the Prime Number Theorem as a reward for learning complex variables: https://faculty.math.illinois.edu/~r-ash/CV.html You don't need to learn the whole book just some knowledge of contour integral and analytic continuation is sufficient to understand the proof. So you could just start with the last chapter and fill the gaps as you go. (If you go linearly through the book you will encounter things like the normal family not required for your stated goal. Even though the normal family stuff are even more beautifully amazing IMHO the presentation here may be too abstract to grok and could discourage one to soldier on.)

Visual Complex Analysis by Tristan Needham is an incredibly approachable textbook on the subject.

I agree, I'm not saying a simple proof is ever out of the question either. But my failed attempt makes me wonder how much of a creative burst a typical person would have to have in order to come up with a simple solution in this case.

Don’t conflate “elementary” in the GP post with “simple.” Elementary in this context just means that the proof does not use tools from complex analysis (i.e. it only uses theorems from real analysis, which is basically freshman calculus on steroids). The elementary proof of the prime number theorem is not easy by any means.

I didn't mean you were the one implying an elementary proof is unobtainable, that was directed at some of the other replies to your comment like "oh really?". I agree that it's enlightening to give these things a try.

Oh really? :-D

Well, parent tried to understand the problem, used the tools at his hand to solve it without preconceptions, and realized it was more complex that it seemed.

The world would be a better place if more people had the same approach to problem-solving, IMHO.

Not saying that there is anything wrong with it. It is still funny though :-) It is like somebody saying they tried to go to the moon, but after walking for an hour they discovered it was harder to get there than they initially thought.

Yes! I had a lot of ideas but didn't get anywhere, including:

- reframe the real part of a complex input s as 1/2 + k for -1/2 < k < 1/2, since we're only looking at the critical strip 0 < Re(s) < 1. Then show k has to be zero for the math to work out, so that the real AND complex parts of the value of the function at s are both zero. Eventually failed because I can only show that Re(s) = 1/2 would work out relatively "nicely" so you could more easily pick Imag(s) to find zeroes, but can't prove that a different real value would still let the math work out so you could find a zero in the first place.

- come up with a formula to sum the series. I don't have much math know-how in this regard, except for some tricks I learned in discrete math/algos class so I quickly ran out of ideas. Pairing sum terms together (like you can do to prove the sum of telescoping series, or of natural no's from 0 to N) doesn't seem to work.

- The original sum formula looks like sum(n=1, infinity, ((-1)^(n+1))/(n^s)) where s is the complex input. I tried to turn it into a continuous function by using -cos(pi*n) for the numerator and then use a definite integral, but the result is nasty before you even plug in the integral bounds. There's an imaginary term as the second argument for the gamma function, which I don't understand how to handle.

- show two different real values, r1 and r2, of zeroes at r1 + ci and r2 + di for some imaginary parts c and d. Then show the ratio r1/r2 = 1, and since we know r1 = 1/2 works, we know 1/2 is the only possible real part that works. Much like the summing stuff above, I couldn't figure out how to simplify things enough to even get an equation in terms of either r1 or r2.

- show that two zeroes on either side of the line s = 1/2 + iy cannot exist, or at least something like if one exists then the other must not exist, which contradicts the notion that we'd have two zeroes on either side of the line, where one has a real part between 0 and 1/2 (exclusive) and the other is in (1/2, 1). I don't have a good way of actually attacking this idea though.

There are some other ideas I tried, but the main problem is I can't simplify the sum. The sum itself plus the fact there's exponents in every denominator makes it especially hard to simplify algebraically, or at least I don't know how to do it.

Reply on news.ycombinator.com