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