Prev: HEAP SORT
Next: Greedy Algorithm
From: tchow on 24 Mar 2006 18:07
In article <1143235307.145842.278090(a)e56g2000cwe.googlegroups.com>,
Craig Feinstein <cafeinst(a)msn.com> wrote:
>Tim, I thought you were more thoughtful than this. Read my response to
>the earlier post.

What part of that response are you referring to? The appeal to your
paper http://arxiv.org/abs/math/0312309 ? The argument in that paper
also generalizes.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: tchow on 24 Mar 2006 18:43
In article <44247bb8$0$579$b45e6eb0(a)senator-bedfellow.mit.edu>, I wrote:
>What part of that response are you referring to? The appeal to your
>paper http://arxiv.org/abs/math/0312309 ? The argument in that paper
>also generalizes.

Let me spell this out in case it isn't obvious.

Define the function T(n) = floor(n/2).

Theorem 1. For any vector x in {0,1}^m, there exists n in N so that
x = (n, T(n), ..., T^(m-1)(n)) mod 2.

Proof. Simply let n be the reversal of x, interpreted as a binary number.
For example, if x = (1,0,1,1), let n = 1101 in binary, i.e., n is thirteen.
Then in base ten, n = 13, T(n) = 6, T(T(n)) = 3, T(T(T(n))) = 1, and
(13, 6, 3, 1) = (1, 0, 1, 1) mod 2.

Theorem 2. If m, n are in N and T^(m)(n) = 1, then to prove T^(m)(n) = 1,
it is necessary to describe the values of (n, T(n), ..., T^(m-1)(n)) mod 2.

Proof. T^(m)(n) can be reduced to the formula

(1/2^m) * (n - sum_{i=0}^{m-1} a_i * 2^i)

where a_i = T^(i)(n) mod 2 (by convention we let T^(0)(n) = n). Hence,
in order to prove that T^(m)(n) = 0, it is necessary to describe the values
of (n, T(n), ..., T^(m-1)(n)) mod 2, since the formula for T^(m)(n) is
determined by the values of of (n, T(n), ..., T^(m-1)(n)) mod 2.

Theorem 3. It is impossible to prove that for all n, there exists m such
that T^(m)(n) = 0.

Proof. Exercise for the careful reader of http://arxiv.org/math/0312309.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: Craig Feinstein on 26 Mar 2006 20:16

tchow(a)lsa.umich.edu wrote:
> In article <44247bb8$0$579$b45e6eb0(a)senator-bedfellow.mit.edu>, I wrote:
> >What part of that response are you referring to? The appeal to your
> >paper http://arxiv.org/abs/math/0312309 ? The argument in that paper
> >also generalizes.
>
> Let me spell this out in case it isn't obvious.
>
> Define the function T(n) = floor(n/2).
>
> Theorem 1. For any vector x in {0,1}^m, there exists n in N so that
> x = (n, T(n), ..., T^(m-1)(n)) mod 2.
>
> Proof. Simply let n be the reversal of x, interpreted as a binary number.
> For example, if x = (1,0,1,1), let n = 1101 in binary, i.e., n is thirteen.
> Then in base ten, n = 13, T(n) = 6, T(T(n)) = 3, T(T(T(n))) = 1, and
> (13, 6, 3, 1) = (1, 0, 1, 1) mod 2.

I agree.

>
> Theorem 2. If m, n are in N and T^(m)(n) = 1, then to prove T^(m)(n) = 1,
> it is necessary to describe the values of (n, T(n), ..., T^(m-1)(n)) mod 2.
>
> Proof. T^(m)(n) can be reduced to the formula
>
> (1/2^m) * (n - sum_{i=0}^{m-1} a_i * 2^i)
>
> where a_i = T^(i)(n) mod 2 (by convention we let T^(0)(n) = n). Hence,
> in order to prove that T^(m)(n) = 0, it is necessary to describe the values
> of (n, T(n), ..., T^(m-1)(n)) mod 2, since the formula for T^(m)(n) is
> determined by the values of of (n, T(n), ..., T^(m-1)(n)) mod 2.

I don't agree. Yes, it is true that your T^(m)(n) can be reduced to the
formula,
(1/2^m) * (n - sum_{i=0}^{m-1} a_i * 2^i).

But then your T^(m)(n) could be reduced algebraically to zero when m is
sufficiently large, so your conclusion that your formula for T^m(n) is
determined by the values of (n, T(n), ..., T^(m-1)(n)) mod 2 is false,
for sufficiently large m.

The formula in my paper for T^(m)(n) cannot be reduced algebraically
any further than what I had in my paper and therefore since this
formula is determined by the values of (n, T(n), ..., T^(m-1)(n)) mod
2, the conclusion of Theorem 2 in my paper still stands.

Craig

>
> Theorem 3. It is impossible to prove that for all n, there exists m such
> that T^(m)(n) = 0.
>
> Proof. Exercise for the careful reader of http://arxiv.org/math/0312309.
> --
> Tim Chow tchow-at-alum-dot-mit-dot-edu
> The range of our projectiles---even ... the artillery---however great, will
> never exceed four of those miles of which as many thousand separate us from
> the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences

From: tchow on 26 Mar 2006 21:16
In article <1143422199.045467.117280(a)v46g2000cwv.googlegroups.com>,
Craig Feinstein <cafeinst(a)msn.com> wrote:
>I don't agree. Yes, it is true that your T^(m)(n) can be reduced to the
>formula,
>(1/2^m) * (n - sum_{i=0}^{m-1} a_i * 2^i).
>
>But then your T^(m)(n) could be reduced algebraically to zero when m is
>sufficiently large, so your conclusion that your formula for T^m(n) is
>determined by the values of (n, T(n), ..., T^(m-1)(n)) mod 2 is false,
>for sufficiently large m.

That it can be reduced to zero does not mean that the conclusion is false;
T^(m)(n) is still determined by the values of (n, T(n), ..., T^(m-1)(n))
mod 2. "X determines Y" means that if the value of X is given, then the
value of Y is determined. It does not mean, as you appear to think, that
*unless* the value of X is given, then the value of Y *cannot* be
determined.

>The formula in my paper for T^(m)(n) cannot be reduced algebraically
>any further than what I had in my paper and therefore since this
>formula is determined by the values of (n, T(n), ..., T^(m-1)(n)) mod
>2, the conclusion of Theorem 2 in my paper still stands.

First of all, you haven't proved that the formula cannot be reduced
algebraically (whatever "algebraically" means---this isn't clear).
Secondly, even if you could prove this, it wouldn't prove what it
seems you want to prove, namely that T^(m)(n) cannot be determined
from any proper subset of the values of (n, T(n), ..., T^(m-1)(n)) mod 2.
Thirdly, and most importantly, even if this could be proved, it would
not prove that these values must *appear explicitly in any proof of
the Collatz conjecture*. Proofs can use symbols like "m," "n," and
so forth, and can derive general facts about sequences of high complexity
without ever giving a single such sequence explicitly. Your own "proof"
is an example: How is it that you manage to prove something about these
arbitrarily complex sequences without ever describing them explicitly?
Couldn't one prove that

It is impossible to prove that "It is impossible to prove the Collatz
conjecture, if it is true," if it is true

by arguing that any such impossibility proof would have to refer to
arbitrarily complex binary sequences?
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: Craig Feinstein on 26 Mar 2006 21:50
Tim, I appreciate that you have read my paper and have given your
feedback. I don't agree with your criticisms, but I don't really have
the time to argue with you either, so let's just agree to disagree.

Craig

First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6 7 8 9
Prev: HEAP SORT
Next: Greedy Algorithm