5 ms·

Prime Gap Grows After Decades-Long Lull

83 points by digital55 12y ago

lkbm 12y ago
> 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.
- ggchappell 12y ago
  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.
  - chx 12y ago
    http://mathoverflow.net/questions/27716/does-there-exist-a-comprehensive-compilation-of-erdoss-open-problems http://mathoverflow.net/questions/27716/does-there-exist-a-c...
- chx 12y ago
  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).
  - lkbm 12y ago
    I was looking at http://mathoverflow.net/a/66219 http://mathoverflow.net/a/66219 But, yeah, apparently that's not a comprehensive list by any means.
- StefanKarpinski 12y ago
  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.
typomatic 12y ago
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.
- rtkwe 12y ago
  A lot of approximate conjecture equations are only really true for very large numbers.
- prezjordan 12y ago
  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 https://www.youtube.com/watch?v=GuigptwlVHo Big big numbers are really, really cool!
  - anonetal 12y ago
    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.
    - jordigh 12y ago
      Union-find's big-Oh is the inverse of the Ackermann function, which isn't quite the same as iterated logs...
      - charrison 12y ago
        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.
    - 12y ago
deleted 12y ago
[deleted]
darkstar999 12y ago
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?
- StefanKarpinski 12y ago
  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.
  - Florin_Andrei 12y ago
    Conjecture: Given enough time for science to make progress, eventually all mathematical theorems and conjectures will gain applicability in practice.
    - WhitneyLand 12y ago
      The weaker claim that at least some findings will gain applicability in practice should be well enough to justify all of our efforts.
- patrickmclaren 12y ago
  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.

83 points by digital55 12y ago

lkbm 12y ago

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

ggchappell 12y ago
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.
- chx 12y ago
  http://mathoverflow.net/questions/27716/does-there-exist-a-comprehensive-compilation-of-erdoss-open-problems http://mathoverflow.net/questions/27716/does-there-exist-a-c...
chx 12y ago
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).
- lkbm 12y ago
  I was looking at http://mathoverflow.net/a/66219 http://mathoverflow.net/a/66219 But, yeah, apparently that's not a comprehensive list by any means.
StefanKarpinski 12y ago
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.

typomatic 12y ago

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.

rtkwe 12y ago
A lot of approximate conjecture equations are only really true for very large numbers.
prezjordan 12y ago
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 https://www.youtube.com/watch?v=GuigptwlVHo Big big numbers are really, really cool!
- anonetal 12y ago
  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.
  - jordigh 12y ago
    Union-find's big-Oh is the inverse of the Ackermann function, which isn't quite the same as iterated logs...
    - charrison 12y ago
      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.
  - 12y ago

deleted 12y ago

[deleted]

darkstar999 12y ago

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?

StefanKarpinski 12y ago
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.
- Florin_Andrei 12y ago
  Conjecture: Given enough time for science to make progress, eventually all mathematical theorems and conjectures will gain applicability in practice.
  - WhitneyLand 12y ago
    The weaker claim that at least some findings will gain applicability in practice should be well enough to justify all of our efforts.
patrickmclaren 12y ago
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.