Wikipedia:Reference desk/Archives/Mathematics/2012 April 7
Mathematics desk | ||
---|---|---|
< April 6 | << Mar | April | May >> | April 8 > |
Welcome to the Wikipedia Mathematics Reference Desk Archives |
---|
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
April 7
editwhat is open subgroup in Group theory?
editwhat is open subgroup in Group theory? — Preceding unsigned comment added by Cjsh716 (talk • contribs) 07:03, 7 April 2012 (UTC)
- A subgroup of a topological group that is an open set. Sławomir Biały (talk) 13:48, 7 April 2012 (UTC)
Expert opinion on methods required for proof of Goldbach's Conjecture
editI don't know if anybody here would necessarily be 'tuned in' enough to give a good answer, but I am wondering if those mathematicians knowledgeable about related work believe that proof of Goldbach's conjecture (probably the paramount example of an unproven but 'known' to be true mathematical fact) will require essentially new methods or could theoretically just be an extraordinarily difficult problem in applying methods already in use. If the former, I would also be interested in knowing if opinions are out there as to how much of a departure from what is in use--degree of difficulty of imagination, let's say--may be required, just marginal tweaking or phenomenal ingenuity. If the latter, I wonder if simple but very strong versatility in computer programming--along with full knowledge of prior mathematical work--might be expected to crack the problem (and might be needed to do so because of number and difficulty of requisite computations).173.15.152.77 (talk) 11:07, 7 April 2012 (UTC)
- I am guessing, but I would think the answer is somewhere between "essentially new methods" and "an extraordinarily difficult problem in applying methods already in use". If current methods could be used, it would have already been done; but my guess is that some insightful advance on existing methods might do the trick. My (uninformed) guess would be that this is how Wiles proved Fermat's Last Theorem -- insightful advances on existing methods, bordering on new methods. Anyone have a different perspective on that?
- Incidentally, I would disagree with the characterization of the Goldbach Conjecture as " 'known' to be true" in the sense that everyone thinks the probability of its truth is extremely close to 100%. You never know about these things -- sometimes the first counterexamples to number theory assertions of the non-existence of anything with a certain property turn out to be very very large counterexamples. For example, from Pythagorean triple#Elementary properties of primitive Pythagorean triples:
- There exist infinitely many Pythagorean triples with square numbers for both the hypotenuse c and the sum of the legs a+b. The smallest such triple[10] has a = 4,565,486,027,761; b = 1,061,652,293,520; and c = 4,687,298,610,289. Here a+b = 2,372,15922 and c = 2,165,01722. This is generated by Euclid's formula with parameter values m = 2,150,905 and n = 246,792.
- Similarly, the smallest known counterexample to the previously conjectured impossibility of w4 + x4 + y4 = z4 is (95800, 217519, 414560; 422481). So sure, we've checked a very large number of numbers looking for counterexamples to Goldbach's Conjecture; but that still represents essentially 0% of all possible numbers -- the smallest 0%! Duoduoduo (talk) 16:36, 7 April 2012 (UTC)
- Also you ask if simple but very strong versatility in computer programming--along with full knowledge of prior mathematical work--might be expected to crack the problem (and might be needed to do so because of number and difficulty of requisite computations). If the conjecture is false, it strikes me that would be at least as likely to be proven with a computer-found counterexample as with a non-computer-based proof by contradiction. On the other hand, if the conjecture is true, it's hard to see how this could be proven with a computer program. But maybe a proof could go something like this: Someone shows that every even number is in exactly one of N categories, defined in such a way that which category a number is in could be established via computer in polynomial time, and they show that either all or none of the numbers in any category are Goldbach counterexamples. Then we could use clever programming to find one example of a number in each category, and check to see if it's a counterexample. This strikes me as similar to how the four color theorem was proven -- it was proven that there are only a certain finite number of types of know to check, and then a computer was used to check them all. Duoduoduo (talk) 20:46, 7 April 2012 (UTC)
- There is a link in the article about verifying the Goldbach conjecture up to 4*10^18 with a brute-force computer search. It keeps getting more and more convincing as you go (every single even integer up to 4*10^18 can be represented as a prime pair with one of the primes <10,000). Basically, if we have good heuristics that says that the probability for any given number N to be a counterexample is X(N), and the sum of X(N) from a certain N_0 to infinity is much less than 1, that's a strong indication that the hypothesis is true.--Itinerant1 (talk) 21:01, 7 April 2012 (UTC)
- But then the question is "What are good heuristics?" Heuristics are really just extrapolations from what we already know. If the conjecture is true, the heuristics may well make sense. But if the conjecture is false, the heuristics are meaningless because they fail to take account of whatever makes the conjecture self-contradictory. Duoduoduo (talk) 21:22, 7 April 2012 (UTC)
- On the other hand, the Goldbach conjecture article contains this diagram.
Number of ways to write an even number n as the sum of two primes (4 ≤ n ≤ 1,000,000)
- On the other hand, the Goldbach conjecture article contains this diagram.
- I am actually the OP on this question (on a sub-standard browser). I do have to disagree with you, Duoduoduo. Of course it is true that proof is always required for anything to be established as irrefutably true in mathematics, but much much less believable things are routinely assumed true for heuristic purposes, contingently of course, but genuinely assumed true. And I don't mean in the way that the Riemann hypothesis is assumed true, and new results are contingently caveated to be dependent on a likely but not fairly certain fact. The reason that I asked the question was because the problem is HARD, but the thing is that I suspect myself that answering it specifically is not so much of a 'holy grail' problem with other results depending upon it or a massive enough financial motivation behind it that somebody would necessarily have built the right tools and mixture of different areas of expertise as a specialist, even if it would be close to routine--but massively time consuming--to complete a proof using pretty much just older methods. I would imagine that if it were a matter of primarily needing to have a computer do something extraordinarily lengthy, as with the Four color theorem, that it would be considerably more difficult also to program, graph theory being essentially an already in-between subject area to computer science. Now, the Goldbach conjecture itself, I really think is quite clearly known to be true, as much as anything unproven is ever in mathematics, and the real mathematical questions are "What on Earth will it take to prove it?!" and, then, "How can the asymptotic range for number of representations be narrowed further than >0?" You may disagree, but find me then at least one person very knowledgable about both the Goldbach conjecture and another unproven (non-axiomatic, of course) but pretty much assumed to be true mathematical statement if I am really to have any reason to withdraw my opinion. If all that you are saying is that proof is always required, well, yeah, I get that.Julzes (talk) 02:44, 8 April 2012 (UTC)
- Well, there's a good reason that a proof is always required: because without a proof, it might not be true. There only has to be one counterexample for Goldbach's conjecture to fail to be true (I'm assuming there isn't any theoretical reason why there has to be more than one counterexample; feel free to correct me if I'm wrong here), and while that may seem very unlikely according to the heuristics and the evidence from the first few numbers tried, it hasn't actually been proved impossible. --COVIZAPIBETEFOKY (talk) 03:51, 8 April 2012 (UTC)
- Sure, but there's plenty of evidence. The evidence that GC is true would be more than sufficient to establish, say, a physical theory, to the point that no one would openly doubt it except as an intellectual exercise.
- I think the reason that people demand a higher standard of proof in mathematics than in physics is mainly that it's just not available in physics. But that's not really a very good reason. The natural conclusion really is that GC is true; we just don't know how to prove it. --Trovatore (talk) 05:03, 8 April 2012 (UTC)
- Yes, but what is the evidence for GC? Perhaps more the partial results, heuristic arguments, the simplicity of the statement, and the way it fits in with other conjectures, combining to create a gut feeling it is true, and perhaps less the numerical evidence. You might have to go up to 40 digit numbers to find a counterexample for Mertens conjecture, but that one exists is proven. IIRC, that one was thought to be too much to be true even before 1985, so gut feeling was proved right. But number theory is tricky.John Z (talk) 10:51, 8 April 2012 (UTC)
- Nothing to do with size of first counterexample per se. It's the probabilistic argument that I find extremely convincing. --Trovatore (talk) 17:42, 8 April 2012 (UTC)
- Yes, but what is the evidence for GC? Perhaps more the partial results, heuristic arguments, the simplicity of the statement, and the way it fits in with other conjectures, combining to create a gut feeling it is true, and perhaps less the numerical evidence. You might have to go up to 40 digit numbers to find a counterexample for Mertens conjecture, but that one exists is proven. IIRC, that one was thought to be too much to be true even before 1985, so gut feeling was proved right. But number theory is tricky.John Z (talk) 10:51, 8 April 2012 (UTC)
- Well, there's a good reason that a proof is always required: because without a proof, it might not be true. There only has to be one counterexample for Goldbach's conjecture to fail to be true (I'm assuming there isn't any theoretical reason why there has to be more than one counterexample; feel free to correct me if I'm wrong here), and while that may seem very unlikely according to the heuristics and the evidence from the first few numbers tried, it hasn't actually been proved impossible. --COVIZAPIBETEFOKY (talk) 03:51, 8 April 2012 (UTC)
- Julzes here again (same problem, common for me these days on weekends). While this discussion on the need for a proof specifically as applied to the Goldbach conjecture might have some value beyond that there is always such a need (If people feel so, then by all means continue, and perhaps I will chime in) in determining which of two opposing mathematical propositions is true, it does not approach the question I was trying to ask (and now realize I muddied by soft-lining the need for proof--or refutation). Let me briefly re-pose that question, and then if nobody here can respond I may report a reasonable answer myself sometime (a long time,most likely) after this has been archived. What I was essentially asking bears upon the question of groupthink among mathematicians in a way, a different way than that of which I perceive myself perhaps being accurately accused. As it would certainly garner some substantial attention and other benefits within the society of mathematicians to completely solve the problem, I was wondering if it still might not be the case that the problem is already on the verge of being proved (not something I at all have ideas of doing myself; I just think I might be able to gather what is the expert opinion I want without Herculean efforts). The question would be, then, if those who have looked at the proof of Chen's theorem and related material and said A) "The work and computations needed to go that last step along these paths would be absolutely mind-boggling and could never realistically be done by human beings for such an obviously worthless fact's proof just for its own sake by one or a few sane people seeing all the related and more interesting stuff there is right now to be done in related areas of mathematics" or B) "We really will have to wait for new 'stuff' for this one to be cracked if it ever will be." If it is A, though, perhaps C is now more accurate, that being C) "A good programmer knowing this sort of subject matter exquisitely well could have the programming done in half a year, a result in half a day, and a write-up, then, in another half month." Now, I suspect it may be hard to find anybody who can give a great reliable answer to this, but I asked because I am not sure. No offense to those holding the hard-line on proof and digressing from my question because of my own failing in wording things initially to avoid the debate, but answering me--not necessary, of course--requires answering the question differently than so far has been done. I am capable of taking the hard line on the need for proof myself, and disagreement here on which is right does not appear terribly expert (Expert, specialized, opinion being my question really--It is a problem that has certainly had a lot of people weigh in over the centuries, and some even recently; so, I had hopes somebody might be conversant in this).173.15.152.77 (talk) 13:51, 8 April 2012 (UTC)
- I for one was not responding to your question, to which I really have no informed comment to give, but to the intervening discussion. --Trovatore (talk) 19:32, 8 April 2012 (UTC)
- I am actually the OP on this question (on a sub-standard browser). I do have to disagree with you, Duoduoduo. Of course it is true that proof is always required for anything to be established as irrefutably true in mathematics, but much much less believable things are routinely assumed true for heuristic purposes, contingently of course, but genuinely assumed true. And I don't mean in the way that the Riemann hypothesis is assumed true, and new results are contingently caveated to be dependent on a likely but not fairly certain fact. The reason that I asked the question was because the problem is HARD, but the thing is that I suspect myself that answering it specifically is not so much of a 'holy grail' problem with other results depending upon it or a massive enough financial motivation behind it that somebody would necessarily have built the right tools and mixture of different areas of expertise as a specialist, even if it would be close to routine--but massively time consuming--to complete a proof using pretty much just older methods. I would imagine that if it were a matter of primarily needing to have a computer do something extraordinarily lengthy, as with the Four color theorem, that it would be considerably more difficult also to program, graph theory being essentially an already in-between subject area to computer science. Now, the Goldbach conjecture itself, I really think is quite clearly known to be true, as much as anything unproven is ever in mathematics, and the real mathematical questions are "What on Earth will it take to prove it?!" and, then, "How can the asymptotic range for number of representations be narrowed further than >0?" You may disagree, but find me then at least one person very knowledgable about both the Goldbach conjecture and another unproven (non-axiomatic, of course) but pretty much assumed to be true mathematical statement if I am really to have any reason to withdraw my opinion. If all that you are saying is that proof is always required, well, yeah, I get that.Julzes (talk) 02:44, 8 April 2012 (UTC)
Perimeter that is tangent to a circle
editThis is not homework problem. Imagine there are 5 points in two-dimensional space. They are, and their coordinates are as follows:
- A=(0, -u)
- B=(-s, 0)
- C=(0, t)
- D=(DX, DY)
- O=(0,0)
and:
- u is the distance between O and A
- s is the distance between O and B
- t is the distance between O and C
- RA is equal to u+t and is the radius of an arc from D to C
- RB is the radius of a circle with B as iits center
- D is a point that lies on the perimeter of the aformentioned circle
- DX=-s-RB*u/(s*sqrt(u2/s2+1))
- DY=RB*u/(s*sqrt(u2/s2+1))
- θ=arctan(s/u) and is the angle formed by D, A, and C
Given s, t, RB, how do I find DX, DY, u, RA, and θ? --Melab±1 ☎ 19:44, 7 April 2012 (UTC)
- You must specify u (or θ, or something else). In other words, your problem is underconstrained, and its answer depends on the value of u or equivalently where Point A is; or some other specified parameter.
- You have five unknowns. You specified three. You provided one constraint (that the distance from Point D to the center of the circle at (0, t-u) is fixed). You have one remaining free parameter. Nimur (talk) 20:07, 7 April 2012 (UTC)
- I want to determine the size of an arc that is tangent to the circle formed by B. The arc starts at C and is drawn counter-clockwise to where it will just touch the circle formed by B. The distance from B to O is fixed as well. --Melab±1 ☎ 20:38, 7 April 2012 (UTC)
Decidability and Goldbach's Conjecture
editOne time I saw this line of reasoning on an article's talk page, but I can't find it now. It went like this:
The Goldbach conjecture cannot be undecidable, because if it's false it's decidable by showing a counterexample, and so if it's undecidable then it's true and hence decidable.
It seems to me that this is wrong for the following reason -- if someone could sort this out for me it would help me understand undecidability better. It seems to me that undecidability means undecidability within the confines of a particular axiomatic system (the number system in this case?); so the Goldbach conjecture might be undecidable within that framework but might still be decidably true in a wider logical framework. Does this make sense? Is it conceptually possible for the Goldbach conjecture to be undecidable? Duoduoduo (talk)
- The thing you have to keep in mind is that undecidability is not a truth value. Undecidability is always relative to some particular formal theory. Truth, on the other hand, is just truth.
- If GC is undecidable in, say, Peano arithmetic, or even Robinson arithmetic (basically, any formal theory capable of proving all true quantifier-free sentences of arithmetic), then GC is really genuinely true. However, that doesn't mean that it's necessarily provably true in any particular named formal theory (other than, e.g., ones that take GC as an axiom). --Trovatore (talk) 23:33, 7 April 2012 (UTC)
- To clarify, that quote is wrong, although I've seen trained mathematicians fooled by the same reasoning in the past. I've also seen them try to argue that therefore if it's undecidable, it cannot be proven undecidable. This is also wrong.
- Another way of looking at it would be that there are two notions of truth: true in every model; and true in the standard model. That comment is confusing the two. Undecidable means (by Godel) true in some models and false in others. If it's false in the standard model, then it's decidable by showing a counterexample. But it might be true in the standard model and false in others.--121.74.125.218 (talk) 22:15, 8 April 2012 (UTC)
- I think the phrase "true in the standard model" is an excessively wordy way of saying "true". In a language that has a clear intended interpretation (such as the language of arithmetic), true is just true; it doesn't need to be relativized to anything. Provability and decidability, on the other hand, are always relative to some particular theory. Your truth in "other" models is also relative to some particular theory (otherwise, "model" of what, exactly?) --Trovatore (talk) 22:54, 8 April 2012 (UTC)
- Whereas I think "true" is a short way of saying "true in every model". And of course this is all relative to a theory.--121.74.125.218 (talk) 23:32, 8 April 2012 (UTC)
- No, "true" does not mean "true in every model". "True in every model" is the same as "provable", which is definitely not the same as "true". --Trovatore (talk) 00:58, 9 April 2012 (UTC)
- Clearly I think true and provable are the same (not definitionally; they're equivalent by Godel). I'm not prepared to commit to the existence of a standard model, whatever that means, so using "true" to mean "true in the standard model" is discomforting. Of course, I can still reason about a standard model in certain cases, for example analyzing the standard model of PA when my metatheory is ZFC.--121.74.125.218 (talk) 13:46, 9 April 2012 (UTC)
- Well, you're just using the word wrong. True does not mean provable. True means true. The sentence "2+2=4" is true just in case 2 plus 2 really is 4; it has nothing to do with whether you can prove it.
- If the natural numbers do not really exist, then sentences of arithmetic are simply meaningless rather than true or false. They can still be provable or refutable, but this does not suddenly license you to start calling that true or false. --Trovatore (talk) 17:30, 9 April 2012 (UTC)
- There can be reasonable cases where the longer 'True in the standard model' is clarifying, but it is ultimately a redundancy except where one is comparing truth in one model non-standard and one standard. If the question is well-posed, it is either true or false aside from such a case (which nevertheless may arise).Julzes (talk) 17:49, 9 April 2012 (UTC)Specific, literally labeled models ('standard' and 'non-standard'), that is.Julzes (talk) 17:53, 9 April 2012 (UTC)
- I don't disagree with that. Most of the time, though, I think it's a bad idea to add "in the standard model", especially in contexts like exposition of the Goedel incompleteness theorems. It is important to emphasize, for example, the fact that the Goedel sentence of a consistent theory is just simply true, and saying it this definitely is no more problematic than saying that the theory is consistent. --Trovatore (talk) 19:19, 9 April 2012 (UTC)
- There can be reasonable cases where the longer 'True in the standard model' is clarifying, but it is ultimately a redundancy except where one is comparing truth in one model non-standard and one standard. If the question is well-posed, it is either true or false aside from such a case (which nevertheless may arise).Julzes (talk) 17:49, 9 April 2012 (UTC)Specific, literally labeled models ('standard' and 'non-standard'), that is.Julzes (talk) 17:53, 9 April 2012 (UTC)
- Clearly I think true and provable are the same (not definitionally; they're equivalent by Godel). I'm not prepared to commit to the existence of a standard model, whatever that means, so using "true" to mean "true in the standard model" is discomforting. Of course, I can still reason about a standard model in certain cases, for example analyzing the standard model of PA when my metatheory is ZFC.--121.74.125.218 (talk) 13:46, 9 April 2012 (UTC)
- No, "true" does not mean "true in every model". "True in every model" is the same as "provable", which is definitely not the same as "true". --Trovatore (talk) 00:58, 9 April 2012 (UTC)
- Whereas I think "true" is a short way of saying "true in every model". And of course this is all relative to a theory.--121.74.125.218 (talk) 23:32, 8 April 2012 (UTC)
- I think the phrase "true in the standard model" is an excessively wordy way of saying "true". In a language that has a clear intended interpretation (such as the language of arithmetic), true is just true; it doesn't need to be relativized to anything. Provability and decidability, on the other hand, are always relative to some particular theory. Your truth in "other" models is also relative to some particular theory (otherwise, "model" of what, exactly?) --Trovatore (talk) 22:54, 8 April 2012 (UTC)