Prime Gap Grows After Decades-Long Lull | Hacker News Reader

Prime Gap Grows After Decades-Long Lull

quantamagazine.org

83 pointsdigital5523 comments

I laughed out loud when I saw that formula--y = loglogloglog x is a nonsense function. For those of you who haven't thought about logs for a while, that function is increasing (bigger x give bigger y), but it grows so slowly that y won't be larger than 1 until x is larger than 2.33 x 10^1656520.

A lot of approximate conjecture equations are only really true for very large numbers.

Is loglogloglog...log the only beast that can conquer Knuth's arrow notation? (x ↑↑↑↑...↑ n)

Every time I watch videos about arrow notation or, more famously, Graham's number, my head explodes :) https://www.youtube.com/watch?v=GuigptwlVHo

Big big numbers are really, really cool!

log*(x) = how many times you have to take a log before you get to 1, grows more slowly than any constant length sequence of logs, and also appears naturally in many theoretical algorithms (e.g., union-find). I suspect even that is not enough to tame Knuth's arrow notation though.

Union-find's big-Oh is the inverse of the Ackermann function, which isn't quite the same as iterated logs...

Depends on how you derive it. I've seen derivations that end up with a log* term. Of course, inverse Ackermann is a tighter bound.

log* doesn't beat Knuth arrows. See that

    log*(e ↑↑ n) = (n-1) log*(e)
                 = n

So log* is just the inverse of e ↑↑ n.

That makes sense. Logarithm is the inverse of exponentiation. log* is iterated logartithm-ing, and (↑↑) is iterated exponentiation (aka tetration). (↑↑) builds up a stack of powers, and log* tells you how tall that stack is.

Here's another nice big number link:

http://www.scottaaronson.com/writings/bignumbers.html

If the inverse of the Ackerman function grows more slowly than loglogloglog...log, and the inverse of BB(N) grows more slowly still, maybe that would be enough to conquer Knuth's arrow notation?

BB(N) must grow faster than any computable function. BB isn't computable because computing it would involve solving the halting problem. Any function which could grow larger than BB would imply solving the halting problem, and therefore can't be computable. Basically, inverse BB would eat Knuth's arrow notation for breakfast, and start asking about second breakfast and elevenses.

See my other comment: log* only conquers the second level of Knuth arrows, e ↑↑ n. But you can easily generalize log* , in a way that mirrors the way Knuth arrows are constructed, and inverts them at any level.

Say

    log*[1](n) = log(n)

    log*[k](n) = 0                            if n <= 1
               = 1 + log*[k](log*[k-1](n))    if n > 1

Then the k-th level is the inverse of the k-th level Knuth arrows, e ↑^k n -- that is, e ↑↑..↑ n, with k arrows.

"log log log x goes to infinity with great dignity." -- Dan Shanks

> This is the first Erdös prize problem Tao has been able to solve, he said. “So that’s kind of cool.”

There are only fifteen, right? Possibly even fewer open ones. It'd be pretty impressive if he/they manage to solve multiple Erdös prize problems.

You might be thinking of something else. Erdős was constantly remarking that he would offer some amount for some problem. I would guess there are hundreds of open problems with Erdős prizes attached -- some large, some small.

I can't find a list. Odd.

http://mathoverflow.net/questions/27716/does-there-exist-a-c...

Fifteen? No list I am aware of has 15 -- Erdos' definitely had lots more, of the Millennium Prize problems there are six open (and there was seven), most of Hilbert's are down there are 3 or 10 open depending how you look, but definitely not 15 (and there were 23 or so).

I was looking at http://mathoverflow.net/a/66219

But, yeah, apparently that's not a comprehensive list by any means.

Yeah, but if anyone in the world was going to have solved multiple Erdös problems, it would be Terry Tao. And he's still quite young, so he may well solve more.

What is the significance of studying this problem? I mean, say they prove the twin primes conjecture. What does that mean? Do we benefit like we would if the travelling salesman problem was solved?

This is a different but related problem: instead of trying to prove that there are arbitrarily large twin primes, they are trying to see how the maximum gap between primes grows with their size. I know that doesn't answer the applicability question, but I think the answer to that is "who knows?" Pure mathematicians tend to study these things for their own sake and then someone may or may not figure out something useful to do with it.

Conjecture: Given enough time for science to make progress, eventually all mathematical theorems and conjectures will gain applicability in practice.

The weaker claim that at least some findings will gain applicability in practice should be well enough to justify all of our efforts.

Significance of a problem shouldn't be considered from the same point of view as pricing an asset, by face value.

Open problems concerning prime numbers can be considered as large floodgates, waiting to be opened. Their applicability is likely to be infinite. Pick up any subject, try to quantify some behavior, sooner or later, primes will make an appearance. In fact, you should really do this; read the first few chapters of an elementary number theory book, then try to represent your area of expertise in a way that involves primes.

Perhaps in a few decades, or centuries, by tracing a certain technological improvement back in time, we'll be able to place a $-value this work. You can already do this now, for other (probably all, if you can be bothered) areas of (previously abstruse) mathematics, for example Group Theory -> Spectroscopy -> Biomedical Spectroscopy, or Algebraic Topology -> Improvements in semiconductors.

Think of it more like fundamental research. Maybe nobody could make immediate productive use of the discovery of (for example) radioactivity in the late 1800s, but it has a wide variety of uses today from energy production to medical imaging.

It's unlikely that proof of the twin prime conjecture would prove that fundamental, but the results are hard to predict in advance.

Reply on news.ycombinator.com