Talk:Collatz conjecture

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, High-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
High Priority
 Field: Number theory
This article has comments.

pls look at it...[edit]

This forum is for discussion of the Wikipedia article.

The appropriate place to discuss this is the Usenet group sci.math and I've transferred it there. You can reach it via Google Groups with subject Collatz Conjecture proof?


This conjecture has an unusual property regarding possible counterexamples. Even if God said "Here's a number which diverges without cycles", this wouldn't really prove anything, because this number couldn't be checked in finite time. Normally, a counterexample instantly (well, at least reasonably quickly) disproves a conjecture, but here it is useless. Are there any other conjectures with this property? Are there any sources that discuss or least mention this? GregorB (talk) 20:29, 20 February 2014 (UTC)

If you ask whether there are any sources that mention this then I suspect you don't actually know whether it is true. Neither do I. Is there any known test which has been proven to determine in finite time whether n is a counter example? I have no idea. If n is a counter example then it obviously wouldn't work to compute the infinite sequence, but it doesn't seem impossible to me that somebody has found or will find a way to prove a sequence with certain testable properties must diverge, without knowing whether such a sequence exists. Many conjectures have the property you ask for, although the meaning of "counter example" may sometimes seem less specific than for the Collatz conjecture. For example, Polignac's conjecture states: "For any positive even number n, there are infinitely many prime gaps of size n". Suppose God claims n=2 is a counter example. Then God would be claiming the twin prime conjecture is false. Oh no, the alleged counter example is a more famous unsolved conjecture than we started with. By the way, last year it was finally proved by Yitang Zhang that there exists n which are not counter examples to Polignac's conjecture, but no specific n has been proven. As an example of how little we sometimes know about small numbers, Friendly number says: "No general method is known for determining whether a number is friendly or solitary. The smallest number whose classification is unknown (as of 2009) is 10". says: "It is believed that 10, 14, 15, 20, 22, 26, 33, 34, 38, 44, 46, 51, 54, 58, 62, 68, 69, 70, 72, 74, 76, 82, 86, 87, 88, 90, 91, 92, 94, 95, 99, 104, 105, 106, and many others are also solitary, although a proof appears to be extremely difficult." PrimeHunter (talk) 02:37, 21 February 2014 (UTC)
You can look at the position of the problem in the arithmetic hierarchy for some indication of the maximum degree of difficulty. The set of all numbers which converge to the 1(-4)-2 cycle here is \Sigma_0^1 (as you can code the entire the entire sequence as an number); so the Collatz conjecture is \Pi_0^2. Similarly, in regard Polignac's conjecture, the question of whether a number occurs infinitely many times as a prime gap is \Pi_0^2, so the conjecture is also \Pi_0^2. There are numerical conjectures at a higher level. — Arthur Rubin (talk) 21:00, 24 February 2014 (UTC)
It also depends on how you define the conjecture - there is an equivalent problem that looks at a map between infinite binary vectors to the 2-adics - depending on what maps to the rationals/integers/naturals determines the conjecture. In that case, you could specify a counterexample by considering the binary vectors also as 2-adics, then giving an irrational 2-adic that maps to a rational 2-adic. I'm not saying it would be easy to check, exactly, but it is a much more direct sort of thing logically speaking.Phoenixia1177 (talk) 04:31, 16 May 2014 (UTC)
Huh? Running the thing backwards, if x is rational, then neither 2x nor (x-1)/3 can be irrational, regardless of whether we're talking about real numbers or 2-adics. —David Eppstein (talk) 04:37, 16 May 2014 (UTC)
The parity of a 2-adic integer's trajectory gives an infinite binary word, that word can be taken as another 2-adic integer. Consider that as mapping 2-adic to 2-adic: if rationals map to rationals, then every rational number is eventually cyclic - on the other hand, if under the inverse map an irrational maps to a rational, then there is a divergent rational trajectory; which, in the case that the image is a natural number, means that the trajectory diverges off to infinity. Essentially, the digits of the image under the mapping encode the trajectory due to the close relation between Collatz trajectories and parity. --The observation is, obviously, fairly trivial - what makes it interesting is how simple it is to work out the form of the mapping.Phoenixia1177 (talk) 05:26, 16 May 2014 (UTC)
The conjecture (as with nearly all mathematics) requires proof. If you claim a number which cycles, you can prove your claim by writing down the sequence. If you show me a number which diverges forever, you obviously can't write the sequence down, so you must use math to show it. Imagine a machine which takes as input a number, and runs the collatz function on it. This function can return True, False, or run forever. The fact that you cannot know (just by running the machine) whether it will return a result (True/False), or if it will run forever, is known as the Halting Problem. It is well known in the field of computer science. — Preceding unsigned comment added by 2601:9:76C0:53:2D87:9BAD:A4D4:62AF (talk) 01:43, 23 October 2014 (UTC)
That's sort of right. There is no reason there can't be a condition equivalent to divergence that can be easily written and checked - for f(x) = x ^ 2, you can't write down the sequence, but |x| > 1 can be checked. There is nothing that has shown that the Collatz Conjecture trajectories reduce to the Halting Problem; if this had been shown, then the conjecture couldn't possibly be true. There is a result that shows that we can't know which functions, from a set of collatz generalizations, converge for all naturals because that would be equiv. the halting problem; but that doesn't really relate to anything being said here.Phoenixia1177 (talk) 08:42, 26 October 2014 (UTC)

Real and complex numbers[edit]

Please could somebody consider adding a derivation for the continuous function which appears to have been "pulled from thin air", or a link to another article where this is discussed.

I see the explanation at e.g. [1] and would do something myself, but I've never done any mathematical editing and really don't want to make a mess of somebody else's article. MarkMLl (talk) 07:55, 26 September 2014 (UTC)



if i wanna add alot of info about the Collatz conjecture that are not on the article what i need to do? do i first need to post in talk and then it will be posted in the article or what?

i have alot of stuff i was working on that are not showen in the article — Preceding unsigned comment added by Isaac.mor (talkcontribs) 10:19, 22 February 2015 (UTC)

If by "stuff I was working on" you mean things you have worked out yourself, then that should not be added to the article: see WP:No original research. Anything you add should be supported by reliable sources. AndrewWTaylor (talk) 18:31, 22 February 2015 (UTC)
Or, to put it more constructively: first get your work published in the usual way in a peer-reviewed mathematics journal, and then come back to this talk page with the publication information; we might or might not add it here but in any case it will be published in the journal for the world to see. —David Eppstein (talk) 19:44, 22 February 2015 (UTC)

What exactly IS "the real extension of the Collatz map optimized by replacing 3n+1 by (3n+1)/2" ?[edit]

Picture caption:

"Cobweb plot of the orbit 10-5-8-4-2-1-2-1-2-1-etc. in the real extension of the Collatz map (optimized by replacing "3n + 1" with "(3n + 1)/2")"

Since there is nothing in the article that refers to a "real extension" of the Collatz map (no less an "optimized" one) — and the caption doesn't go to any trouble to explain what it might be trying to say — can we please remove this picture and its unhelpful caption? (Sorry, but I have zero patience for nonsense posing as editing.)Daqu (talk) 01:41, 12 March 2015 (UTC)

I'm having difficulty understanding, the real extension is right next to the picture in the section "Iterating on real or complex numbers", and it says, right in the caption, what the optimization is (despite being a rather trivial one).Phoenixia1177 (talk) 15:00, 31 March 2015 (UTC)
Ok, but why this particular real function among so many others? Do we have a source for this? Does this offer any actual insight into the Collatz conjecture? As it is, it looks like unsourced original research and as such should be removed. —David Eppstein (talk) 17:31, 31 March 2015 (UTC)
I have no idea why this particulair one, I didn't put it there nor argue that it is the right one. That said, it is an obvious one and I've seen it more than once, but there are others that have been employed, and of equal to greater use - moreover, it is trivial to add terms to the one in the article to get something more general. I don't really see the point in removing it as it is, essentially, a really obvious extension of the parity function, but I would downplay any emphasis that makes it sound like it is the "standard" or "right" real version of the Collatz function (but does serve as a reasonably simple example of an extension, basic enough that I don't think it is OR).Phoenixia1177 (talk) 01:41, 26 May 2015 (UTC)