December 2008 - mathfun@mailman.xmission.com

[math-fun] Fast factoring ??
by Tom Knight 12 Dec '08

12 Dec '08

The Shor algorithm for quantum computing the factors of a composite number N relies on a physical trick to calculate r, the period of x^a mod N for 0<a<N-1, while doing the exponentiation mod N on a superposition of the possible a's. This step, and the fourier transform of the result are done on the superposition, leading to a fast algorithm for finding the period r, following a magic "collapse." I attended a talk on Tuesday from Adi Akavia (former student of Shafi Goldwasser) in which she discussed the problem of finding (whp) large fourier coefficients of a function g(a) over a domain of size N while examining only polylog(N) of the values, pointing to her paper (FOCS 03) "Proving Hard-Core Predicates using List Decoding," Akavia, Goldwasser, Safra. In that paper they show a very clever algorithm for finding the set of large fourier coefficients efficiently. Question of the day: Can these two ideas be put together to find a polynomial factoring algorithm? Almost certainly I'm overlooking or misunderstanding some very fundamental thing, but I don't see what.

2 1

Re: [math-fun] Twubbling Turtle Trajectories (HAKMEM 45)
by Dan Asimov 11 Dec '08

11 Dec '08

Good point, Rich. I was thinking of the partial sums Sum{k=1...n} exp(n i c) as an analogy, but this is a bad analogy. --Dan << 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(a)mailman.xmission.com [math-fun-bounces(a)mailman.xmission.com] On Behalf Of Dan Asimov [dasimov(a)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].) >> _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

[math-fun] Twubbling Turtle Trajectories (HAKMEM 45)
by Marc LeBrun 10 Dec '08

10 Dec '08

Just was wondering if this group might have anything to add about this 1972 puzzle? Can you cite other elegant questions, with such startling special-case answers? ======== 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 ). But a denominator of 171 = 9 * 19 never loops, probably because 9 divides phi(19). Similarly for 9009 and 2525. Can someone construct an irrational multiple of pi with a bounded locus? Do such angles form a set of measure zero in the reals, even though the "measure" in the rationals is about .155? About .155 = the fraction of rationals with denominators containing odd primes squared = 1 - product over odd primes of 1 - 1/P(P + 1). This product = .84533064 +- a smidgen, and is not, alas, sqrt(pi/2) ARCERF(1/4) = .84534756. This errs by 16 times the correction factor one expects for 1093 and 3511, and is not even salvaged by the hypothesis that all primes > a million satisfy the congruence. It might, however, be salvaged by quantities like 171.

1 0

[math-fun] 4x4 Game of Life devices
by Steve Witham 08 Dec '08

08 Dec '08

Tileable 4x4 Game of Life devices: http://www.thinkgeek.com/gadgets/electronic/ae39/ --Steve

1 0

[math-fun] Puzzle (rerun?)
by Dan Asimov 06 Dec '08

06 Dec '08

I was recently reminded of this old puzzle of mine, but cannot recall if I ever posted it to math-fun. (Apologies if this is a rerun.) PUZZLE: What surface is obtained from the square [0,1]^2 by identifying each edge with the opposite edge after translating it halfway (mod 1)? (I.e., for all t in [0,1), (t,0) ~ (t + 1/2 (mod 1), 1) and (0,t) ~ (1, t + 1/2 (mod 1)). ) --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

2 1

[math-fun] Oliver Selfridge
by rcs＠xmission.com 04 Dec '08

04 Dec '08

Oliver Selfridge died Wednesday. An obit from the New York Times is available at http://news.cnet.com/Oliver-Selfridge,-early-innovator-in-AI,-dies-at-82/21… Rich

1 0