Hacker News Reader

Comment by nomilk | Hacker News Reader

Also curious about the potential significance of a proof. The article is vague:

> (primes) are important for securing encrypted transmissions sent over the internet. And importantly, a multitude of mathematical papers take the Riemann hypothesis as a given. If this foundational assumption were proved correct, “many results that are believed to be true will be known to be true,” says mathematician Ken Ono of Emory University in Atlanta. “It’s a kind of mathematical oracle.”

Are there some obvious, known applications where a RH proof would have immediate practical effects? (beyond satisfaction and 'slightly better encryption').

View on HN

Mathematics is sort of strange in this regard in that there's lots of work already done that assumes RH, so many of the consequences of the theorem itself are already worked out. And RH seems to be true on extensive numerical searches(no counterexamples found). So the theorem being true wouldn't be earth-shattering in and of itself.

It's more about the method used to prove the theorem, which might involve novel mathematics. And probably will in this case considering how long it's taking to prove RH. Since this method hasn't been found yet, it's hard to say what the consequences of it might be.

At least that's my layman's understand of it.

If we knew that the extended Riemann hypothesis was true, we could use the Miller test for deterministic primality testing in log(n)^4; the AKS test, which doesn't depend on RH, is lg(n)^6.

Do we care? Not for most applications -- doing a bunch of randomized Miller-Rabin tests is fine for most practical purposes. But it would be really nice to have a faster deterministic algorithm around. AKS isn't practical for anything; miller... Miiiiiggghtt be.

Then why not just assume it's true and if something breaks, hey, you might just have disproved it?

What if an airliner or a spacecraft or a self- driving car or a surgical robot breaks?

They already do. Was this supposed to be an enlightening question?

The randomized algorithm doesn't need to be perfect, it just needs to present a failure probability << the failure rate from other causes. And it can easily do that, since the failure probability goes down exponentially with the number of iterations of the test.

Because for practical things we have a faster solution that might also be wrong occasionally (randomized testing). There's no benefit to using any of the known deterministic tests if they're not truly deterministic. The speed gap vs randomized is huge.

Then it seems it wouldn't be better to use the deterministic test ever. Just use the randomised test and accept the failure rate.

To put some numbers on it, assume a civilization of 1 trillion people, with each person using 1 000 things that needs a large prime, and those 1 000 things need to generate a new prime 1 000 times a second.

The most conservative bound on the chance that a random single Miller-Rabin test will say that a composite number is prime is 1/4.

Using that bound, if that civilization used Miller-Rabin with 48 random Miller-Rabin tests to find primes they would get a composite falsely identified as a prime about once every 60 000 years.

If they used 64 tests they would have one false positive about ever 258 trillion years. That's past the point when all stars in the universe have run out of fuel.

Now assume that every star in the universe has a similar civilization. If everyone uses 96 Miller-Rabin tests there will be a false positive about once per 24 billion years.

As I said that is using a false positive rate of 1/4, which is very conservative. There's a paper [1], "Average Case Error Estimates For the Strong Prime Test" by Damgard, Landrock, and Pomerance that gives several bounds.

Their bounds are in terms of k, the number of bits of the odd number being tests, and t, the number of random Miller-Rabin tests. They give 4 bounds, for various ranges of k and t:

  (* Valid for k >= 2 *)
  k^2 4^(2-Sqrt[k])

  (* Valid if t = 2, k >= 88 or if 3 <= t <= k/9, k >= 21 *)
  k^(3/2) 2^t t^(-1/2)  4^(2-Sqrt[t k])

  (* Valid for t >= k/9, k >= 21 *)
  7/20 k 2^(-5t) + 1/7 k^(15/4) 2^(-k/2-2t) + 12 k 2^(-k/4-3t)

  (* Valid for t >= k/4, k >= 21 *)
  1/7 k^(15/4) 2^(-k/2-2t)

It is the second one that is most relevant in most situations where you want a large prime and want to do as few tests as possible to get your false positive chances below your acceptable threshold.

Using the hypothetical trillion being civilization with each being needing a million primes a second, here's the expected number of years between that civilization seeing a false positive using the second bound above, for k = 64 and t 2 through 5:

  2 3.6 x 10^26
  3 7.6 x 10^27
  4 8.5 x 10^28
  5 6.5 x 10^29

The bound gets lower as k increases. If they needed 1024 bit primes that table becomes:

  2 1.5 x 10^45
  3 1.3 x 10^51
  4 1.1 x 10^56
  5 2.1 x 10^60

[1] https://math.dartmouth.edu/~carlp/PDF/paper88.pdf

Oh, no disagreement. "Practical" really means "practical for math things where you want to guarantee correctness, not just have extremely high confidence". I can't think of any normal use of primes that needs something past what you can do with a bunch of M-R tests.

But we _do_ use a lot of computational power to verify finding particularly interesting primes, etc., so I maintain that it'd be a nice thing to have in our pocket. You never know when you'll find yourself on a deserted island with a powerful computer and need to deterministically prove the primality of a large number. ;)

Of course, if you end up with an incorrect result due to assuming the Riemann hypothesis, you'll get a fields medal anyway...

Note: the first section, using the conservative estimate, is correct. The second using the tighter bounds is not. I multiplied where I should have divided, leading to an error of a factor or around 10^48 in both tables. E.g., for generating 1024 bit primes with 5 tests the trillion people civilization generating a million primes a second per person would see one error around every 10^12 years, not one ever 10^60 years.

For 64 bit primes they would need to do around 48 tests per prime to get down to a similar error rate.

For

as nomilk said above, for any practical real-world application you could likely just assume the reimann hypothesis was true and proceed accordingly

In the realm of applications, most engineers would say that our confidence in the RH (or more realistically, downstream consequences thereof) is high enough to treat it as true. The proof is, for applications, a formality (albeit a wide-ranging, consequential one!).

More likely, a proof of the Riemann Hypothesis would require new ideas, techniques, and math. It is probable that those devices would have broader reach.

The applications of expansions in math often work that way: as we forge through the jungle, the tools we develop to make our way through are more useful than the destination.

Reply on news.ycombinator.com