From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Collatz "proof" (was Re: Collatz ("3n+1") Problem: discoveries and questions) Date: 7 Feb 1998 08:44:35 GMT Geoffrey E. Caveney wrote: >I gave up trying to solve the 3n+1 Collatz problem and thought of how to >generalize it from 3n+1 and n/2 to an+1 and n/b for coprime a,b. I might generalize it a little more. This dresses up the problem so that it looks primed for an easy victory. Of course it's not, but I can talk fast -- to make it look convincing -- and then duck and run. For p prime you can analyze the problem like this: recall that the p-adic norm |x| of a rational number x = y/z is p^(s-r), where p^r and p^s are respectively the greatest powers of p dividing y and z. Then the rational number x*|x| has no powers of p in numerator or denominator. It's also integral if x is, and positive if x is. Observe that the standard Collatz conjecture simply asks about the behaviour of the function f(x) = (3x+1) * |3x+1| (where p=2) on the positive integers: do the iterates of each x eventually become 1 ? So you could easily generalize to this: given some linear map L(x) = mx+b (with m and b integral) and a prime p, do the iterates of f(x) = L(x) * |L(x)| stabilize, whenever starting with a positive integer x? If there is more than one limit point, which initial x lead to which limit? The real reason this formulation is suggestive, I think, is that it allows us to change the domain of x's while keeping the question; we can see how the answers might differ. These functions f can be extended to any ring containing the integers as long as the norm functions are defined; in particular, they may be extended to the rationals, or to the p-adics or p-adic integers. Here f is a continous function defined on one of these rings and mapping into that ring's intersection with the p-adic unit ball. So the iterates form a sequence inside this compact set, which if infinite has a convergent subsequence; whatever x the subsequence converges to is then a point for which some f^k(x) = x. But it's very easy to itemize such points x for k = 1, 2, 3, ... It follows that every initial x eventually falls into the same cycle as one of these x's. To solve the Collatz-like conjectures, we have only to identify the x's to which such a sequence can converge _when starting with a natural number_. Consider the ordinary Collatz conjecture, L(x)=3x+1 and p=2. Of course x=1 is a fixed point of f. Are there other fixed points? The answer is ... YES! If |3x+1| = 2^(-r), then x is a fixed point iff x = 1/(2^r-3); this does indeed give the right norm to 3x+1 iff r > 0. So you see, the ordinary Collatz conjecture has already overlooked the obvious other cycles containing x = -1, (1,) 1/5, 1/13, ... But 1 is the only positive integer among these. We next consider the possibility that the sequence of iterates of f has a subsequence converging to an x with f(f(x))=x. Well, if |3x+1| = 2^(-r) and |3 f(x) + 1 | = 2^(-s) then x = (3 (3x+1)*2^(-r) + 1 ) * 2^(-s) means x = (2^r + 3)/(2^(r+s) - 9), with r, s > 0; this adds a host of new periodic points for f: -5, -7, 5/7, 1/29, 11/7, ... Of course, none can be another positive integer as 2^(r+s) - 9 > 2^r + 3 unless r+s < 4; those cases are easily checked. We can go on in this way, finding many more interesting cycles (of increasing length) than with the standard Collatz conjecture, yet never another cycle involving positive integers. So if we start with a positive integer to form the sequence of iterates, the x we converge to cannot be a positive integer except x=1. So is the Collatz conjecture solved? Well, no: not only have I lied about four times, but something peculiar happens when we pass to the p-adics. Recall that all sequences of iterates contain a convergent subsequence. What if by luck we found a sequence of iterates which equalled X+1, X+5, X+21, X+85, ..., X+(1+4+4^2+...4^N), ... for some X. Where's the convergent subsequence? The answer is: the _whole sequence_ converges, to X - 1/3 ! So unfortunately, the observations that none of our periodic points are positive integers are irrelevant; even though f(x) is a positive integer if x is, convergent sequences of positive integers need not converge to positive integers. dave (He ducks...) PS: To make this analysis rigorous, begin by noting that f isn't actually continuous! (...and runs) ============================================================================== Date: Sun, 8 Feb 1998 15:42:19 -0800 (PST) From: james dolan To: rusin@vesuvius.math.niu.edu Subject: Re: Collatz "proof" (was Re: Collatz ("3n+1") Problem: discoveries and questions) Newsgroups: sci.math In article <6bh6tj$4o9$1@gannett.math.niu.edu> you write: >(He ducks...) > >PS: To make this analysis rigorous, begin by noting that f isn't actually >continuous! > >(...and runs) hi. i have an idle obvious stupid question about this problem that strangely i don't recall seeing anyone else ever discuss, so i figured i'd inflict it on you. does anything interesting happen if you extend the collatz dynamical system to an entire complex-analytic dynamical system in a hopefully obvious way?? ============================================================================== Date: Mon, 9 Feb 1998 00:33:45 -0600 (CST) From: Dave Rusin To: jdolan@math.ucr.edu Subject: Re: Collatz "proof" (was Re: Collatz ("3n+1") Problem: discoveries and questions) I don't know what extension exists to the complex domain. In some sense extending it to the p-adic sphere is almost the same thing, I suppose, although it's a pretty frustrating extension -- lots of periodic points, all of them repelling. I'm not sure how "quasiperiodic" is formally defined, but every point has the propoerty that it has arbitrarily long strings of iterates which are within epsilon of a periodic cycle of iterates; On the other hand the map itself is clearly not periodic. You end up looking at a dynamical system on Q_p which eventually stabilizes to a particular point ( = 1 ) iff the initial point was an ordinary positive integer. I don't know much about dynamical systems, but that doesn't sound to me like the kind of set you expect to hear mention of as the "right" set of starting values. (Doesn't nearly fractal enough!) I guess I don't expect this perspective to help prove collatz, but it does make me feel the conjecture is a little less arbitrary; it "fits" somewhere. dave ============================================================================== Date: Sun, 8 Feb 1998 23:31:50 -0800 (PST) From: james dolan To: rusin@math.niu.edu Subject: Re: Collatz "proof" (was Re: Collatz ("3n+1") Problem: discoveries and questions) well, the extension i had in mind was i thought the obvious entire complex-analytic extension: form a linear combination of "3z+1" and "z/2" with appropriate "trigonometric" coefficients, if you know what i mean. i remember i actually played around with this on a computer once, but i don't remember whehter anything interesting happened. ============================================================================== Date: Wed, 11 Feb 1998 13:19:52 -0800 (PST) From: james dolan To: rusin@math.niu.edu Subject: Re: Collatz "proof" (was Re: Collatz ("3n+1") Problem: discoveries and questions) to be more explicit: z |-> sine(pi*z/2)^2 * (3*z + 1) + cosine(pi*z/2)^2 * (z/2) so what do you think? totally uninteresting?? ============================================================================== Date: Wed, 11 Feb 1998 15:47:35 -0600 (CST) From: Dave Rusin To: jdolan@math.ucr.edu Subject: Re: Collatz "proof" (was Re: Collatz ("3n+1") Problem: discoveries and questions) Cc: rusin Oh. (For some reason I didn't quite understand what generalization you intended) Well, to start with, you have a lot more fixed points!, roughly near each large solution of tan(pi*z/2)=1/2. Of course these are wildly repelling. Perhaps, with an eye towards families of maps such as the traditional z |-> z^2+c, one should view your smooth generalization in this way: ask about pairs of linear functions L1, L2 for which the maps z|-> sin(z)^2 * L1(z) + cos(z)^2 * L2(z) stabilize. You propose a conjugate to L1(z)=3z+(pi/2), L2=(1/2)z; while there are number-theoretic angles to pursue in this case, I would think that in the analytic setting this one example would cease to hold as much interest as the behaviour of the general family. It's not even obvious what to say about simple pairs such as when L1(z) = L2(z) + constant. What do you suppose are the right questions to ask? dave ============================================================================== Date: Wed, 11 Feb 1998 17:50:40 -0800 (PST) From: james dolan To: rusin@math.niu.edu Subject: Re: Collatz "proof" (was Re: Collatz ("3n+1") Problem: discoveries and questions) Well, to start with, you have a lot more fixed points!, roughly near each large solution of tan(pi*z/2)=1/2. Of course these are wildly repelling. Perhaps, with an eye towards families of maps such as the traditional z |-> z^2+c, one should view your smooth generalization in this way: ask about pairs of linear functions L1, L2 for which the maps z|-> sin(z)^2 * L1(z) + cos(z)^2 * L2(z) stabilize. You propose a conjugate to L1(z)=3z+(pi/2), L2=(1/2)z; while there are number-theoretic angles to pursue in this case, I would think that in the analytic setting this one example would cease to hold as much interest as the behaviour of the general family. It's not even obvious what to say about simple pairs such as when L1(z) = L2(z) + constant. interesting comments. What do you suppose are the right questions to ask? not sure yet. let me think about it a bit. feel free to write again if you get any ideas. ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Collatz "proof" (was Re: Collatz ("3n+1") Problem: discoveries and questions) Date: 16 Feb 1998 15:08:59 GMT Onno Garms wrote: >On 7 Feb 1998 08:44:35 GMT, rusin@vesuvius.math.niu.edu (Dave Rusin) >wrote: ... >>Observe that the standard Collatz conjecture simply asks about the >>behaviour of the function >> f(x) = (3x+1) * |3x+1| (where p=2) >>on the positive integers: do the iterates of each x eventually become 1 ? ... >Great "proof"! But as long as you do not define |0| and hence f(-1/3) >(you did not do so) the function |.| is even locally constant and >hence f continious, am I right? Right; the usual definition is |0|=0, but while |x| is continuous on the set of nonzero p-adics, it admits no continuous extension to 0. >How did you find your ideas? Is this piece of mathematical rhetorics >some garbage you got when attempting to find a real proof? Or did you >even at the beginning intend to find a "theory" for the Collatz >conjecture which is good to fool the readers? Fool the readers? Me? I'm just here to help :-) Actually it's more accurate to say that I was trying to put the Collatz conjecture into some context which makes it seem less arbitrary. Certainly the idea of looking for cycles in dynamical systems of nearly-linear maps is quite common; indeed, at first blush, the map f(x) = L(x)*|L(x)| looks quadratic, just like the common choices for f on the complex plane. But having placed the problem into the "right" context does not mean we are any closer to a solution (compare e.g. the Langlands conjectures). dave