Hacker News Reader

Comment by troymc | Hacker News Reader

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.

View on HN

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.

> 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.

I've edited the comment and clarified the ambiguity.

> 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".

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.

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...

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.

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.

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.)

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...

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

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 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.

Reply on news.ycombinator.com