Re: [math-fun] Twubbling Turtle Trajectories (HAKMEM 45)
Marc asks what if anything new is now known re this Hakmem question. Special cases such as those discussed below will probably present the most difficulty. But I would also guess that for almost all c in [0,1], the set of values P(c) = {2^n c mod 1 | n = 1,2,3,...} is uniformly distributed in [0,1] -- and that (hence?) the set of partial sums { Sum{k=1...n} exp(2^k c 2pi i) | n = 1,2,3,...} is a bounded set for almost all c (i.e., with probability 1). ---------------------------------------------------- (On the other hand, the last I heard is that the set {(3/2)^n mod 1 | n = 1,2,3,...} is not even known to be dense (!) in [0,1].) (Cf. Math Review MR1322557.) --Dan << PROBLEM 45 (Gosper): Take a unit step at some heading (angle). Double the angle, step again. Redouble, step, etc. For what initial heading angles is your locus bounded? PARTIAL ANSWER (Schroeppel, Gosper): When the initial angle is a rational multiple of pi, it seems that your locus is bounded (in fact, eventually periodic) iff the denominator contains as a factor the square of an odd prime other than 1093 and 3511, which must occur at least cubed. (This is related to the fact that 1093 and 3511 are the only known primes satisfying P 2 2 = 2 mod P ). . . .
_____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele
Since almost all C are normal numbers, I'd imagine that the partial sums resemble a random walk. And that the walk gradually wanders away from the origin, at distance O(sqrt(step#)). Rich ________________________________________ From: math-fun-bounces@mailman.xmission.com [math-fun-bounces@mailman.xmission.com] On Behalf Of Dan Asimov [dasimov@earthlink.net] Sent: Wednesday, December 10, 2008 11:06 AM To: math-fun Subject: Re: [math-fun] Twubbling Turtle Trajectories (HAKMEM 45) Marc asks what if anything new is now known re this Hakmem question. Special cases such as those discussed below will probably present the most difficulty. But I would also guess that for almost all c in [0,1], the set of values P(c) = {2^n c mod 1 | n = 1,2,3,...} is uniformly distributed in [0,1] -- and that (hence?) the set of partial sums { Sum{k=1...n} exp(2^k c 2pi i) | n = 1,2,3,...} is a bounded set for almost all c (i.e., with probability 1). ---------------------------------------------------- (On the other hand, the last I heard is that the set {(3/2)^n mod 1 | n = 1,2,3,...} is not even known to be dense (!) in [0,1].) (Cf. Math Review MR1322557.) --Dan << PROBLEM 45 (Gosper): Take a unit step at some heading (angle). Double the angle, step again. Redouble, step, etc. For what initial heading angles is your locus bounded? PARTIAL ANSWER (Schroeppel, Gosper): When the initial angle is a rational multiple of pi, it seems that your locus is bounded (in fact, eventually periodic) iff the denominator contains as a factor the square of an odd prime other than 1093 and 3511, which must occur at least cubed. (This is related to the fact that 1093 and 3511 are the only known primes satisfying P 2 2 = 2 mod P ). . . .
_____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I mentioned this problem to Don Coppersmith and he (not surprisingly) jumped all over it. Below are his arguments that 1) There are uncountably many starting angles, theta, for which the locus remains bounded. 2) The set of theta in [0,1] for which the locus remains bounded has measure 0. We use the standard notation: e(x) := exp(2 pi i x) for x real. The idea for (1) is the following: Note that e(0) = 1, and e(1/7) + e(2/7) + e(4/7) = alpha = -1/2 + i sqrt(7)/2, e(3/7) + e(6/7) + e(5/7) = alpha' = -1/2 - i sqrt(7)/2. Note that the angle subtended by the three points 1,alpha,alpha' is less than 180 degrees. We build up a desired theta inductively: if we have T terms S = sum_{n=0}^{T-1} e(2^n theta), and |S| > 2, we can fix up S by subtracting off the closest of -1,-alpha, -alpha', by changing theta to theta + epsilon, where 2^T (theta + epsilon) = 1,1/7,3/7 (appropriately). The epsilon that we need to add is bounded by 2^-T. Thus the sum of all the fix-up terms is bounded by 1. We can get uncountably many theta, by alternating the above construction with flipping a coin to determine the next bit of theta. The idea for (2) is a counting argument: suppose that for a given M there is a T such that 1/2^T #{ 0 <= k < 2^T : there exists epsilon in [0,1) such that |sum_{n=0}^{T-1} e(2^-n k)| < M } < 1 On Wed, Dec 10, 2008 at 3:56 PM, Schroeppel, Richard <rschroe@sandia.gov> wrote:
Since almost all C are normal numbers, I'd imagine that the partial sums resemble a random walk. And that the walk gradually wanders away from the origin, at distance O(sqrt(step#)).
Rich ________________________________________ From: math-fun-bounces@mailman.xmission.com [math-fun-bounces@mailman.xmission.com] On Behalf Of Dan Asimov [dasimov@earthlink.net] Sent: Wednesday, December 10, 2008 11:06 AM To: math-fun Subject: Re: [math-fun] Twubbling Turtle Trajectories (HAKMEM 45)
Marc asks what if anything new is now known re this Hakmem question.
Special cases such as those discussed below will probably present the most difficulty.
But I would also guess that for almost all c in [0,1], the set of values
P(c) = {2^n c mod 1 | n = 1,2,3,...}
is uniformly distributed in [0,1] -- and that (hence?) the set of partial sums
{ Sum{k=1...n} exp(2^k c 2pi i) | n = 1,2,3,...}
is a bounded set for almost all c (i.e., with probability 1).
---------------------------------------------------- (On the other hand, the last I heard is that the set
{(3/2)^n mod 1 | n = 1,2,3,...}
is not even known to be dense (!) in [0,1].)
(Cf. Math Review MR1322557.)
--Dan
<< PROBLEM 45 (Gosper):
Take a unit step at some heading (angle). Double the angle, step again. Redouble, step, etc. For what initial heading angles is your locus bounded?
PARTIAL ANSWER (Schroeppel, Gosper): When the initial angle is a rational multiple of pi, it seems that your locus is bounded (in fact, eventually periodic) iff the denominator contains as a factor the square of an odd prime other than 1093 and 3511, which must occur at least cubed. (This is related to the fact that 1093 and 3511 are the only known primes satisfying P 2 2 = 2 mod P ). . . .
_____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Dan Asimov -
Schroeppel, Richard -
victor miller