The Riemann Hypothesis Says 5040 Is the Last | Hacker News Reader

The Riemann Hypothesis Says 5040 Is the Last

golem.ph.utexas.edu

219 pointsColinWright56 comments

This provides random Joe a way to show that the Riemann Hypothesis is false: try a bunch of big numbers (bigger than 5040) in σ(n)/(n ln(ln (n))) and check if the result is greater than or equal to e^γ (1.7810724179901979852365041031071…).

If it is, then the Riemann Hypothesis is false. That would be a fun day.

5040 is 7! might be a good idea to try a bunch of factorials first ....

Or primorials, which generally have lots of divisors compared to their size. Primorials go 123251723111... Basically just include the 'new' prime factors in your factorial. But even these aren't necessarily "the best" for getting lots of divisors for their size since, well, for example you multiple by 11 maybe you should multiply by a another 2 instead - does the reduced size more than compensate from the reduced divisors?

https://en.wikipedia.org/wiki/Primorial

The HN markdown is interpreting your asterisks a signals to start/stop italics. You need to escape them with a \ first.

HN most assuredly does nothing like markdown for comment rendering.

It doesn't use Markdown(TM)* , but I have often seen "markdown" used as an informal term for the stripped down text formatting available in comments on websites. It's probably technically incorrect, but I'm not aware of a more accurate but similarly short name for it.

* I'm not actually sure Markdown is trademarked

Also, it turns out that you can't even escape asterisks with a \, you need to leave whitespace after them. So my original comment was doubly wrong.

> But even these aren't necessarily "the best" for getting lots of divisors for their size since, well, for example you multiple by 11 maybe you should multiply by a another 2 instead

The concept you may be reaching for here is Highly Composite Numbers. https://en.wikipedia.org/wiki/Highly_composite_number

While highly composite numbers relate to the number of divisors, an even closer fit to the Robin inequality are the somewhat similar superabundant and colossally abundant numbers, which relate to the sum of divisors instead.

https://en.wikipedia.org/wiki/Superabundant_number

In fact if counterexamples to the inequality exist, the smallest such counterexample must be a superabundant number.

This is a nice, accessible paper about searching for counterexamples to the inequality by generating superabundant and colossally abundant numbers: https://projecteuclid.org/euclid.em/1175789744

It might be not-super-difficult to prove that primorials larger than 5040 always do satisfy the inequality, due to the fairly simple structure of primorials. I was never great at analysis, so I don't see how to do it offhand, but I suspect it is significantly easier than the full RH.

I'd love to live in the world where a random Joe would know what ln(ln (n)) is. Or e^y.

You'll never be sure if you got all the numbers though. You could try 1 trillion numbers and mathmaticians wouldn't be satisfied. Because 1 trillion and 1 could be it.

You'll only know for sure if you prove it false.

I seem to be missing something here. The comment is that this provides a way to show that the Riemann Hypothesis is false. And that statement is true - finding a single number n such that n>5040 and σ(n)/(n ln(ln (n))) is enough to show that the Riemann Hypothesis is false.

Checking this for a bunch of numbers and not finding one does not, of course, show that the RH is true, but that's not what this comment is stating.

The only way I can understand your comment is that you think the grandparent comment, the one to which you are replying, is asserting that we can use this result to prove the RH by computer search. The GP comment is not saying that.

So I don't understand what you're saying.

Let me summarise:

* If we can find n such that n>5040 and σ(n)/(n ln(ln (n))) then the RH is false;

* This gives a method by which Joe Random could, in theory, prove the RH false - that is, simply find and publish such a number;

* This does not give a way for Joe Random to prove that the RH is true, since searching for such a number and failing does not prove anything.

So, what are you saying?

> You'll only know for sure if you prove it false.

Yes.

Interestingly, there are disproved hypotheses, of which, before they got disproved formally, previous massive computations failed to find a single counterexample despite the search reached a huge upper bound. But from time to time, someone could get lucky enough and actually find one to disprove something entirely through computation...

The CDC 6600, R and a Conjecture by Euler

* https://criticathink.wordpress.com/2018/09/30/the-cdc-6600-r...

Where they disproven of massive computation failing to find a counter example or was the search space entirely exhausted? Or by actually finding the counter example? Those are different things. You can disprove by computing every possible input but you can only reasonably disprove but not actually disprove if you didn't test every input.

And if you don't find ANY counter example you can't definitely disprove.

> And if you don't find ANY counter example you can't definitely disprove.

This is... not even close to being true.

How is it untrue?

Any nonconstructive proof would fail to meet your criterion (which pretty much defines constructive mathematics). Consider the standard proof that the square root of 2 is irrational -- it takes the logical form

1. IF sqrt(2) is rational...

2. THEN it has a representation a/b where a and b are coprime integers.

3. THEN (after some algebra) a is a multiple of 2.

4. THEN (after some more algebra) b is a multiple of 2.

5. Points (3) and (4) contradict point (2), which says that a and b are coprime.

6. THEREFORE, we have disproven the idea that sqrt(2) is rational.

This is a correct proof, but not a constructive proof. It's difficult to have a constructive disproof of the claim that a particular number is rational. What would you construct?

But you can easily have a nonconstructive disproof of any given claim. Sticking to proof by contradiction, imagine the sequence "if this conjecture were true, there would be a unique largest prime number -> there is no largest prime number -> this conjecture is false".

this is actually a constructive proof, you are proving that sqrt(2) = a/b implies false and "irrational" is defined as "not rational".

A better easy non constructive proof is to show that there are two irrational numbers c and d such that c^d is rational. and either c1=d1=sqrt(2) or c2=(sqrt(2)^sqrt(2)) and d2=sqrt(2) as c2^d2 == 2 and if c2 is irrational you are done and if c2 is rational then c1^d1 is rational and you are done.

The non constructivity is in that you do not know two irrational numbers c and d such that c^d is rational.

In general proving "not P" by "P is absurd" is constructive and proving "P" by "not P cannot happen" is not.

”It's difficult to have a constructive disproof of the claim that a particular number is rational. What would you construct?”

Nitpick: an irrational number that is equal to the number that you want to prove not being a rational.

Because the irrational aren’t closed under the ‘normal’ operations, that’s often problematic, but, as a trivial example, proving that 1/37+3√2 is not rational can easily be done that way: √2 is irrational, and the sum of a rational and an irrational is irrational, so 1/37+3√2 is irrational.

Here's a constructive proof that does not rely on the law of excluded middle: https://en.m.wikipedia.org/wiki/Square_root_of_2#Constructiv...

I'm aware that nonconstrutive disproof/proof exists but my comments were about constructive/example-driven proofs/disproofs, so I don't see the point really.

Not all proofs are constructive. For example, Euclid’s classic proof that any finite set of primes is incomplete doesn’t actually tell you what the next one is.

Is that proof not constructive? While you aren’t constructing the sequence of all primes, you are constructing some infinite set of primes to prove that there are infinite primes.

I doesn’t construct only primes. If p1, p2, ..., pn are prime, then p1p2...pn + 1 is not divisible by any of them, but it may not be prime itself.

Then you haven't proved a additional prime; you still need the (trivial[0]) step of breaking down 1+Πp into its one or more prime factors. And then you've constructed a (or several) prime not in the original set.

0: Trivial in the logical sense (try every number up to √(1+Πp)), but computationally impractical, thus left as a exercise for the reader.

You don't need that; you can proceed purely through generalities.

1. 1+Πp is congruent to 1 (mod p) for every prime p.

2. This conflicts with the definition of "prime number"; all composite numbers must be congruent to 0 (mod p) for some prime p. Only the empty product can be congruent to 1 (mod p) for every p.

This is already sufficient to prove that the number of primes is not finite -- we derived a contradiction from that premise without demonstrating any additional primes.

(Note that -- within the proof, where we've assumed a finite list of primes -- it's easy to show that 1+Πp is itself prime (since it has no prime divisors less than itself). You can then declare a contradiction with the premise, as it isn't in the original list. However, you can only show that it's prime by using the earlier contradiction, so while this step makes the proof more intuitive, it isn't actually necessary.)

Yes that is correct but that's not what I was talking about in earlier comments, which were exclusively about example-based proof/disproof.

If you're not talking about proof/disproof, you might want to look for a different word.

I was unware there is only one type of proof or that it is not allowed to talk only about specific types of proof.

You said:

> Yes that is correct but that's not what I was talking about in earlier comments, which were exclusively about example-based proof/disproof.[0]

In reply, thaumasiotes said:

> If you're not talking about proof/disproof, you might want to look for a different word.[1]

Now you say:

> I was unaware there is only one type of proof or that it is not allowed to talk only about specific types of proof.[2]

Based on your comment [0] above, your comments were apparently about a specific type of proof, and yet the words you used did not make that qualification clear. In particular, statement [0] says you were restricting the type of proof you were considering.

Reply [1] above is suggesting that if you are only talking about a restricted type of proof then you might want to use a word other that "proof", because you are not talking about proofs in general.

Your comment [2] seems to have missed the point. You yourself in [0] said you were restricting your type of proof. You're allowed to talk about anything you like, but if you use the word "proof" without qualifying it, but you intend only to be talking about a specific type of proof, don't then be surprised if people misunderstand you.

There are cases of all of the following:

(a) A conjecture claims that X doesn't exist, and a proof has been found to show that X does not exist;

(b) A conjecture claims that X doesn't exist, and an exhaustive search has failed to find X;

(d) A conjecture claims that X does exist, and a proof has been given that such an X does exist but without ever demonstrating a specific example.

This collection of cases seems to show that your statements are mistaken.

I think they're saying that case d specifically is not a legitimate proof, or equivalently that instances of case that are legitimate proof can be made constructive through a trivial addition (eg https://news.ycombinator.com/item?id=20395476).

I suspect they are mistaken, depending on how one defines "demonstrate" and "specific", but you haven't actually shown that.

It would be interesting to see how they react to this proof:

https://en.wikipedia.org/wiki/Probabilistic_method#First_exa...

I've edited the comment and clarified the ambiguity.

There was also a computational search for counterexamples of Fermat's last theorem (with nothing found - April 1st jokes regardless)

You are missing the point. The logic goes as follows:

Logically constructed unproven argument:

Statement x is true for all numbers with y property

Now how do you go about proving or disproving the argument:

One way is to provide a general proof that it is true for all numbers.

A way to disprove it is to find a single number that doesn't work. This is basically why people have been running huge computations trying to find a number that disproves the Riemann hypothesis.

What this article essentially says is that we can transform the hypothesis in such a way that the space within which we have to search for that magical number that disproves it has a certain property.

Numberphile has a nice video on 5040 https://www.youtube.com/watch?v=2JM2oImb9Qg

This cites a 2013 paper by Jeffry Lagarias. Lagarias also has a 2001 paper [1] with another elementary equivalent to the Riemann Hypothesis.

Let s(n) be the sum of the positive integers that divide n. For example, s(6) = 1 + 2 + 3 + 6 = 12.

Let H(n) = 1/1 + 1/2 + 1/3 + ... + 1/n.

The Riemann Hypothesis is true if and only if s(n) < H(n) + exp(H(n)) log(H(n)) for all n > 1.

[1] https://arxiv.org/abs/math/0008177

If (efficiently) searching for a disproof requires fast (prime) factorization, are there connections to other open problems?

In this case efficiently searching for an example n does not require fast factorization. We are search for a number n such that σ(n)/(n ln(ln (n))) is large. That mean we want σ(n) large, and that means n will have to have lots and lots of small factors.

So your comment is relevant, but in this case, it doesn't provide new insight.

I just checked how one could implement the search, finding all the divisors for σ(n) can be done with a prime factoring algorithm and then calculating the number of their combinations. But that's just one way.

You can make that more efficient by noting that you need σ(n) to be large, so if you know that, for example, the smallest factor of n is more than ln(n)^4 then you already know this won't be a counter-example. So general purpose factoring doesn't really help in this search, even though, as you say, it's one (naive and simple) approach.

It will work for small n, but it will quickly become infeasible.

I see it now, thanks!

Oh yes. The Riemann Hypothesis is connected to just about everything; lots of statements have been shown to either follow from it or be equivalent to it.

I think you could just generate candidate counter-examples by multiplying factors, rather than the other way around.

Yes! I was just in the middle of doing this in a sage notebook!

Good thinking :)

I have to think some mathematician had already done this for like every pattern they could think of but ya never know. Never hurts to try... As long as you don't delude yourself that is.

update: Okay so the tricky thing here is that in order to naively generate the divisors (and sum over them), you'd have to consider butt-tons of combinations of prime factors, including many, many, many repeated ones.

So finding divisors given a list of factors scales very rapidly.

It's really fun to take shots at these hard problems. It's like any way you attack them they're hard, even when you don't intuitively expect it.

Yes. In fact, if we ever manage to build a quantum computer with a non-trivial amount of qubits, we can expect exponential improvement in the performance of any prime number-related numerical research.

5040 == 7!

coincidence?

Not a coincidence.

sigma(n) is largest when n has lots of large factors. Since d is a factor if n/d is, it's easiest to guarantee this by making sure that n has lots of small factors.

Factorials, by construction, are good examples of numbers with many small factors.

Interesting. So would one way to approach a proof be to define the upper bounds of sigma(n)? If so, have people attempted this?

It seems like something that could be done, since you know sigma(n) cannot contain factors larger than n/2 and the number of factors is finite.

Is that fact that 7 is prime relevant?

Somewhat: you want the number to be as unsmooth (having few small factors) as possible. Since the factorial is the product of all numbers up to a given number, that happens when the top number is a prime, since the next number is necessarily divisible by 2 (and therefore more likely to be smooth).

Yes. For example, 7! is already divisible by 8.

The smallest integer that 8! is divisible by, and that 7! isn't, is 32 -- much less small.

Possibly that all the odd factors of 5040 are prime and they are all the primes less than pr equal to the largest prime divisor of 5040. Only happens for 7!

> all the odd factors of 5040 are prime

No, they aren't. 15, 21, 35 are all factors of 5040.

In fact, any number with more than two factors will necessarily have at least one non-prime odd factor.

Sorry, my bad. Silly comment.

Reply on news.ycombinator.com