December 2008 - mathfun@mailman.xmission.com

Re: [math-fun] Fast factoring ??
by Fred W. Helenius 18 Dec '08

18 Dec '08

At 01:27 PM 12/17/2008, Fred lunnon wrote: >On 12/17/08, rwg(a)sdf.lonestar.org <rwg(a)sdf.lonestar.org> wrote: >> ... >> Thereby reenacting one of my favorite denestings: >> >> 1/5 3/5 3/5 2/5 1/5 2/5 >> 3/5 1/5 1/3 - 2 3 + 2 3 + 3 + 2 >> (3 - 2 ) = ------------------------------------- , >> 2/3 >> 5 >> >> a major simplification that looks anything but. > >Indeed! > >u := 3^(1/5); v := 2^(1/5); w := 5^(1/3); >l := (u^3 - v)^1/3; Presumably you meant to write l := (u^3 - v)^(1/3); which would account for the difference. >r := (u + v^2 - v*u^3 + v^3*u^2)/w^2; >evalf(l - r); # -.6607822845 ?! -- Fred W. Helenius fredh(a)ix.netcom.com

2 1

Re: [math-fun] Fast factoring ??
by Dan Asimov 18 Dec '08

18 Dec '08

Fred wrote: << On 12/17/08, rwg(a)sdf.lonestar.org <rwg(a)sdf.lonestar.org> wrote: > ... > Thereby reenacting one of my favorite denestings: > > 1/5 3/5 3/5 2/5 1/5 2/5 > 3/5 1/5 1/3 - 2 3 + 2 3 + 3 + 2 > (3 - 2 ) = ------------------------------------- , > 2/3 > 5 > > a major simplification that looks anything but. Indeed! u := 3^(1/5); v := 2^(1/5); w := 5^(1/3); l := (u^3 - v)^1/3; r := (u + v^2 - v*u^3 + v^3*u^2)/w^2; evalf(l - r); # -.6607822845 ?! >> Mathematica gives a different result: <<n[1]:= u = 2^(1/5) 1/5 Out[1]= 2 In[2]:= v = 3^(1/5) 1/5 Out[2]= 3 In[3]:= w = 5^(1/3) 1/3 Out[3]= 5 In[4]:= x = (v^3 - u)^(1/3) 1/5 3/5 1/3 Out[4]= (-2 + 3 ) In[5]:= y = (-u v^3 + u^3 v^2 + v + u^2)/w^2 2/5 1/5 3/5 2/5 1/5 3/5 2 + 3 + 2 3 - 2 3 Out[5]= ----------------------------------- 2/3 5 In[6]:= N[x-y] -16 Out[6]= -2.22045 10 >> --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

5 5

Re: [math-fun] Fast factoring ??
by Michael Reid 17 Dec '08

17 Dec '08

> lost a Mathematica 7.0 that had gone 2.5 days on > > Factor[x^3-3^(3/5)+2^(1/5), Extension -> {5^(1/3),2^(1/5),3^(1/5)}] its linear factor should be x - (3^(1/5) + 4^(1/5) - 54^(1/5) + 72^(1/5))/5^(2/3) and of course the quadratic cofactor is irreducible. mike

3 2

Re: [math-fun] segue
by Michael Reid 16 Dec '08

16 Dec '08

> Rich, note that throwing in a factor of 25 reduces many days to > Timing[Factor[x^3-(25*3^(3/5)-25*2^(1/5)),Extension->{2,3}^(1/5)]] > > {0.297, (2^(2/5) + 3^(1/5) + 2^(3/5) 3^(2/5) - 2^(1/5) 3^(3/5) - > x) (5 2^(4/5) - 5 2^(2/5) 3^(1/5) - > 5 3^(2/5) + (-2^(2/5) - 3^(1/5) - 2^(3/5) 3^(2/5) + > 2^(1/5) 3^(3/5)) x - x^2)} > > < 1/3 sec. ! ? that's what i did (after mistakenly futzing around with 5 * (3^(3/5) - 2^(1/5)) for a spell). with Pari/gp ( http://pari.math.u-bordeaux.fr/ ) i needed to initialize the number field "nfinit" (0.305 secs) and then the factorization took 0.224 secs. so time is comparible. i am currently running "nfinit" on the degree 75 field Q(2^(1/5), 3^(1/5), 5^(1/3)) and it has been going for over 24 hours. if it finishes, i'll try the factorization without the catalyzing factor of 25 . mike p.s. i should have realized the easy way to do it is to use the cheat sheet at http://www.tweedledum.com/rwg/identsi2.gif !

1 0

Re: [math-fun] Twubbling Turtle Trajectories (HAKMEM 45)
by victor miller 16 Dec '08

16 Dec '08

Yes, That's what happened. I'm still trying to work out the last details. Even though Don didn't phrase it this way, I think that it's an application of the Borel-Cantelli lemma: If E[n] are a series of events in a probability space and sum_n Prob(E[n]) < infinity, then the probability that infinitely many of these events occur is 0. To apply it to our problem, fix a bound M, and let E[n] be the event that |sum_{j=0}^{n-1} e(2^j theta) | < M and |sum_{j=0}^n e(2^j theta) | < M. I think that possibly you can let M depend on n. There is some sort of counting argument you can give, after noticing that the probability of E[n], depends on only the first n+1 bits of the binary expansion of theta, up to a small fudge. Victor On Tue, Dec 16, 2008 at 1:19 PM, Andy Latto <andy.latto(a)pobox.com> wrote: > On Mon, Dec 15, 2008 at 3:58 PM, victor miller <victorsmiller(a)gmail.com> wrote: > >> 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 > > Did this get posted before you finished? It doesn't seem like a sketch > of a proof, just a single definition. > > -- > Andy.Latto(a)pobox.com >

1 0

[math-fun] segue
by Schroeppel, Richard 16 Dec '08

16 Dec '08

Only rich nerds. They are fun to ride, but I can't understand the $5K+ price. I assumed Kamen was keeping the price high to make luxury-style profit, but a recent magazine profile presents him as a visionary out to change the world. Can it really cost $2K to make the gadget? Wrt quantum factoring 15, no further progress. I keep hoping to see 21. The problem with 15 is that it's too easy. It's a Mersenne form, 2^4-1, which makes the modular reduction trivial. There are a lot of other simplifications for this case, including phi(15) = 4, and multiplication by 2 or 4 is accomplished by rotating the bits. I regarded the original Nature paper as a cheat, since the N=15 case avoids most of the problems that come up in factoring "random" numbers. A more charitable interpretation is that they picked an easy example to start with. It must have taken a lot of work to get their 7-qubit molecule working. Subsequent progress has been lateral: The demo has been repeated with several other underlying quantum systems different from the original NMR approach. But I haven't seen anyone doing complex boolean functions like Majority(X,Y,Z), needed to compute carry bits in any non-trival arithmetic. Any logic system needs a way to carry results through several levels of gates, without the logic levels decaying to indistinguishability. The quantum systems haven't shown this capability yet. It doesn't seem impossible from the theory. Maybe next year. I couldn't get through the Akavia-Goldwasser-Safra paper. (Have you ever started skiing down a Green slope, and found it gradually transitioning to Black?) But AGS use RSA and discrete logs as examples of (apparently) hard problems, and I doubt they would overlook any applicability of their results to classical factoring. <speculation> Maybe some undiscovered physical principle limits our ability to exploit quantum parallelism for computation. My wild guess is that each independent entangled state requires its own kT of energy in the system. This would let us build toy quantum computers to validate the physics, with up to ~2^80 states (a mole), but prevent us from going after the goal problems with 2^1000 states. <end speculation> RWG: For your cube root: Pick a large prime P, maybe 500 or 1000 digits, congruent to -1 (mod 15). This guarantees that cubing and ^5 are 1-1 maps, so cube/fifth roots exist and are unique. Working mod P, compute x as cbrt(stuff), and use the number recognizer to see if x is a rational function of 5^(1/3),2^(1/5),3^(1/5). That's about 150 terms; will NumRec handle that? You need terms for 5^a/3 * 2^b/5 * 3^c/5 and (same)*x. If NumRec balks, you might try using 150 different primes, and directly solving the matrix. Rich ________________________________________ From: math-fun-bounces(a)mailman.xmission.com [math-fun-bounces(a)mailman.xmission.com] On Behalf Of rwg(a)sdf.lonestar.org [rwg(a)sdf.lonestar.org] Sent: Friday, December 12, 2008 1:27 AM To: math-fun Cc: Tom Knight Subject: Re: [math-fun] Fast factoring ?? > 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. I was about to say that thanks to Berlekamp et seq., polynomial factoring is ridiculously easy compared to integer factoring. (With Kronecker's old algorithm, it used to be pretty much equivalent.) But factoring over algebraic coefficient fields seems another story. I just lost a Mathematica 7.0 that had gone 2.5 days on Factor[x^3-3^(3/5)+2^(1/5), Extension -> {5^(1/3),2^(1/5),3^(1/5)}] Has anybody quantum factored anything > 3*5 yet? rcs>And the codicil [to http://www.tweedledum.com/rwg/pizza.htm] provides a >wonderful segue like nerds play polo on? > into series acceleration, and your mysterious irregular >convergence of the pi = 4 arctan 1 series. Good point. I added a warning and the AIM 304 url, http://dspace.mit.edu/handle/1721.1/6088?show=full --rwg Codicil = "little codex". _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

3 3

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

15 Dec '08

Victor wrote: << 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 ... >> This is totally fascinating. Message to Don: Please consider joining math-fun! (We can even offer you a free membership!) --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

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

15 Dec '08

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

3 2

Re: [math-fun] polyhedra with all faces congruent
by Dan Asimov 13 Dec '08

13 Dec '08

Here's the Math Reviews review of a paper by Branko Grunbaum that answers the "Odd?" question in the negative. << Branko Grunbaum On polyhedra in E^3 having all faces congruent. Bull. Res. Council Israel Sect. F 8F 1960 215–218 (1960) The polyhedra having all faces congruent include the reciprocals (duals) of all the “uniform” polyhedra, namely, the five Platonic solids, the dipyramids, the reciprocals of the thirteen Archimedian solids, and the reciprocals of the antiprisms. These last have, for any n, 2n kite-shaped faces. (It is unfortunate that the author uses, instead of “kite”, the name “deltoid”, which belongs more properly to a curve, the three-cusped hypocycloid.) The author proves that, if all the faces of a convex polyhedron are congruent, their number is even. Since the faces cannot all have more than five sides, and the result is obvious when the faces are triangular or pentagonal, the problem is quickly reduced to the case of quadrangular faces, and then to kites or parallelograms. The kites are dealt with by an ingenious combination of metrical and topological arguments. Finally, if the faces are parallelograms, their number is equal to the product of two consecutive integers [Coxeter, Regular polytopes, Methuen, London, 1948, p. 27; MR0027148 (10,261e)]. > _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

7 14

Re: [math-fun] segue
by Henry Baker 12 Dec '08

12 Dec '08

At 10:35 AM 12/12/2008, Schroeppel, Richard wrote: >Only rich nerds. >They are fun to ride, but I can't understand the $5K+ price. >I assumed Kamen was keeping the price high to make luxury-style >profit, but a recent magazine profile presents him as a visionary out >to change the world. Can it really cost $2K to make the gadget? I know more about this than I'm allowed to say here, but the single word answer is "batteries". To a first approximation, the cost of the Segway--or any electric vehicle, for that matter--is primarily in the batteries/energy storage system. This is why the MIT spinoff A123 Systems of Watertown, MA, filed for its IPO in August, 2008, but which is in doubt due to current market conditions. There was speculation that the GM "Volt" was to use their batteries. (Perhaps the "Volt" should be renamed the "Ohm" ?)

1 0