In a reassuring move for people with faith in the scientific community as a whole, professor admits error, and works to correct it:
http://www.wtop.com/index.php?nid=104&sid=73297
http://www.wtop.com/index.php?nid=104&sid=73297
Twin Prime conjecture still not proven...
- Thread starter Andonyx
- Start date
-
- Tags
- conjecture prime proven twin
I love these abstract math problems. I am facinated when a mainstream science show such as Nova focuses on Fermat or any one of the classic previously/currently unsolved theorems. I could watch it all day.
That said, I have no real understanding of the math involved, and I don't comprehend the significance of the solutions to either the field of mathematics or the man in the street.
But I'm rooting for these guys! Hope they find their holy grail.
That said, I have no real understanding of the math involved, and I don't comprehend the significance of the solutions to either the field of mathematics or the man in the street.
But I'm rooting for these guys! Hope they find their holy grail.
The only thing I understand about this is its significance to prime numbers.
I guess there are a lot of great unsolved questions about primes, including, how to find them, how many of each type there are, etc... etc...
One immediate application for this information is encryption. Many forms of encryption rely on prime numbers and a way of factoring for primes. Solving some of these problems may render some forms of encryption useless, I suppose.
I guess there are a lot of great unsolved questions about primes, including, how to find them, how many of each type there are, etc... etc...
One immediate application for this information is encryption. Many forms of encryption rely on prime numbers and a way of factoring for primes. Solving some of these problems may render some forms of encryption useless, I suppose.
aggle_rithm
Unregistered
A
swellman said:
Have you read "Fermat's Enigma" by Simon Singh and John Lynch? I highly recommend it.
One of the interesting things in the book is how natural selection uses prime numbers. The seventeen-year locust, for instance, evolved a long life-cycle so that its emergence from the cocoon would not co-incide with the life-cycles of enemy organisms (such as fungus). However, if the enemy organism's life cycle were a factor of the insects longer life cycle, nothing is gained. If the insect's life cycle were sixteen years and the enemy's is two, then the same problem exists. Hence, natural selection (eventually) chose a relatively large prime number, 17.
I will have to check out the book. Sounds interesting.
A high school teacher once told me that Fibonacci series can be used to model the growth of some plants, but I don't have a formal reference on it.
There are some (to my mind) crazy applications of certain abstract mathematical constructs to the stock market, but I prefer to consult my Magic 8-ball when formulating a stock picking strategy.
A high school teacher once told me that Fibonacci series can be used to model the growth of some plants, but I don't have a formal reference on it.
There are some (to my mind) crazy applications of certain abstract mathematical constructs to the stock market, but I prefer to consult my Magic 8-ball when formulating a stock picking strategy.
One of the so-called "millenium problems" -- the 7 biggest math problems in the world today (check out some interesting stuff at http://www.claymath.org/Millennium_Prize_Problems/ ) -- is the Riemann Hypthesis, which I can't really describe, but involves an equation whose solutions are prime numbers.
One of the cool things about all of these problems is that the proof itself is not really that important, but it is assumed that the methods used to find the solutions will yield huge mathematical breakthroughs.
One of the cool things about all of these problems is that the proof itself is not really that important, but it is assumed that the methods used to find the solutions will yield huge mathematical breakthroughs.
JesFine said:
I remember when Fermat was proven, some mathematicians were disappointed that a solution had been found because it would stop potentially fruitful research along those lines. I don't think anyone doubted the validity of the theorem itself.
I work with some researchers who run numerical solutions to Navier-Stokes, which is also discussed on the Millenium problem page you cite. Answers to many cases have been achieved. As computers advance, the need for a theoretical "solution" to N-S probably won't be necessary to the engineering side, but who knows what breakthroughs may come about during the search?
Facinating stuff, these classic unsolved problems.
Tez
Graduate Poster
- Joined
- Nov 29, 2001
- Messages
- 1,104
cryptology is based on the difficulty of factorization (and more generally on finding solutions to various elliptic functions over finite fields - solutions to Pells equation and the like.)
If knowing the answer yes/no as to whether there was an infinite number of twin primes had any bearing on the issue, we'd just guess, and with probability 1/2 be right! Much like one can look for factorisation algorithms under the hypothesis that the Riemann conjecture is true - still doesnt get you very far.
More seriously, you might think that the techniques used to prove the twin prime conjecture could possibly help with factorisation or similar. ALthough both are number theory problems, and so there is, I guess, a small chance - its very unlikely given the techniques which are normally brought to bear. THink of the proof of the infinitude of primes - doesnt help one whit in factorisation.
In the reverse direction - we know of quantum algorithms for all the number theory problems (inclusing factorisation) that are used for cryptology, and the existsence of these algorithms has no bearing on the twin prime conjecture.
Basically, the problems are very disparate. In cryptology its known that the numbers have factors, the question is one of efficiency of an algorithm. In the twin prime conjecture the question of existence is what needs to be proven (and will almost certainly not be proven by explicit construction of an infinite set of the little beggars!).
Hope that helps
If knowing the answer yes/no as to whether there was an infinite number of twin primes had any bearing on the issue, we'd just guess, and with probability 1/2 be right! Much like one can look for factorisation algorithms under the hypothesis that the Riemann conjecture is true - still doesnt get you very far.
More seriously, you might think that the techniques used to prove the twin prime conjecture could possibly help with factorisation or similar. ALthough both are number theory problems, and so there is, I guess, a small chance - its very unlikely given the techniques which are normally brought to bear. THink of the proof of the infinitude of primes - doesnt help one whit in factorisation.
In the reverse direction - we know of quantum algorithms for all the number theory problems (inclusing factorisation) that are used for cryptology, and the existsence of these algorithms has no bearing on the twin prime conjecture.
Basically, the problems are very disparate. In cryptology its known that the numbers have factors, the question is one of efficiency of an algorithm. In the twin prime conjecture the question of existence is what needs to be proven (and will almost certainly not be proven by explicit construction of an infinite set of the little beggars!).
Hope that helps
Andonyx said:
I don't see any way how knowing that there are an infinite number of twin primes could affect cryptography in any way. I'm not saying that it is impossible, though, but someone has to give a detailed explanation for me to believe otherwise.
For example, consider the RSA algorithm. A RSA public-private key pair is generated from two large random primes. Those primes are generated by randomly choosing large integers until two are found that pass the primality tests. (If you have a really bad luck you might hit on a number that only looks like it is prime, but chances for this are miniscule). If one of them is actually a twin prime, then what could it matter?
Tez said:
Yes! Thank you.
I think it was my misunderstanding of the original question....
Earlier I mentioned that many of the larger math problems currently being worked on involve primes, and that finding information about primes, such as the number of factors, could be key to many encryption issues.
Then the poster above me asked about this specific problem and encryption. I supposed that when you replied, "Nope." I interpreted that as primes being irrelevant to encrytpion, and so overstated the scope of your answer. But your answer was great, and clears up a lot about how these topics are related.....
Tez
Graduate Poster
- Joined
- Nov 29, 2001
- Messages
- 1,104
LW said:
Actually a recent (and very exciting) development was the discovery of a deterministic, polynomial time algorithm for checking primality.
Some guy here (Bell Labs) has now improved this algorithm to its theoretical optimum, but I'm not sure if anyone has actually written any code that runs it yet (my feeling is that the probabilistic algorithms are so efficient people may still continue to use them anyway...)
ZeeGerman
Graduate Poster
Tez said:
Err, maybe I'm getting it wrong here, but checking primality of a number should be at most be linear in complexity? All I have to do (in the simplest way) is to check all odd numbers up to sqrt
as a possible divisor for a given number n. That is tedious for large numbers but still even sublinear in complexity, since if I double the size of the problem, e.g. check for primality of a number about twice as big as n, the number of divisions to check only increases by the factor sqrt(2), i.e. 1.4.Factorization of numbers on otoh is known to be NP-complete, so if someone found a deterministic polynomial solution for that one ALL NP-complete problems would be solved and in fact it would be proven that P=NP.
Zee
The algorithm you describe is not linear, because the complexity of algorithms is generally given in terms of the length of the input, i.e., the number of bits needed to represent the input. To represent n requires only log<sub>2</sub> n bits. An algorithm that's linear in n is exponential in log n.ZeeGerman said:Err, maybe I'm getting it wrong here, but checking primality of a number should be at most be linear in complexity? All I have to do (in the simplest way) is to check all odd numbers up to sqrt
ZeeGerman said:
69dodge already commented on the linearity part, so I'll answer only this.
Factorization is not known to be NP-complete, and in fact, it would be really surprising if it turned out so. For starters, speaking of NP in connection with factorization is a little fuzzy since technically only decision problems (that have a YES/NO answer) are in NP, and if you want to compute something you move into FNP ("function problem NP"). However, it is possible to construct a decision problem that is essentially equivalent to factoring so we don'treally have to worry about it. (The same thing holds also for the Traveling Salesman Problem that is usually formulated in such a way that it is not a decision problem).
The decision problem formulation of factoring is in both NP and co-NP (the set of problems whose complements are in NP). If factoring was NP-complete, then it would happen that NP = co-NP. While this result is more probable than P=NP, it still is a rather unlikely case as it would collapse the polynomial hierarchy. I'm not going to delve into details of polynomial hierarchy here, but among other things it would mean that finding a minimal model of a logical formula would be as difficult as finding any model, so you would get optimization "for free".
ZeeGerman
Graduate Poster
LW said:
What can I say, I stand corrected
After checking my Hopcraft&Ulman I had to admit to myself that I've forgotten more about complexity theorie than I've actually bothered to learn back in my university times
Zee