December 2011 - mathfun@mailman.xmission.com

[math-fun] spherical pendulums?
by Bill Gosper 05 Dec '11

05 Dec '11

Are they chaotic or just hairy? The Wolfram demonstration seems quasiperiodic.? Gene once disabused me of the folly of trying to resolve the motion into x and y. But suppose we hung the string from the inside of an upward cusp of a cycloid of revolution. Would the pendulum simply describe an ellipse? --rwg

2 1

Re: [math-fun] Request for example elementary non-constructive proofs with "witnesses"
by Bill Gosper 05 Dec '11

05 Dec '11

rcs> I think the original counting argument was Moore's, and it easily applied directly to Life. However, there's an easy example of a GOE from the counting argument: The argument shows that there's some GOE pattern, of size < a computable number N. To make the argument constructive, just make up a supersize pattern, with all possible patterns of size N. Wrt showing Louiville numbers are transcendental: Use the example L = sum 10 ^ (- N!). In this special case, it's not too hard to check that L defeats any prospective polynomial. Rich --- Quoting Allan Wechsler <acwacw(a)gmail.com <http://gosper.org/webmail/src/compose.php?send_to=acwacw%40gmail.com>>: > This is the one I've been trying to remember. Thank you, Alon.>> This also reminds me of the proof that the Game of Life has a finite Garden> of Eden pattern. (Since the original proof, many explicit predecessorless> patterns have been found.) It depends on counting possible predecessors> and shows that for a certain class of patterns, the number of candidate> predecessors is smaller than the number of patterns, so one of that class> must lack a predecessor. The class is astronomically large, though, and> the counting argument gives no hints about how to find an example. <...> http://www.tweedledum.com/rwg/goe.htm --rwg

4 5

[math-fun] Request for example elementary non-constructive proofs with "witnesses"
by Marc LeBrun 04 Dec '11

04 Dec '11

Could anyone supply me with elementary examples that illustrate the idea of a non-constructive proof, for those with a "Martin Gardner reader" level of mathematical sophistication that also has a not-too-trivial but reasonably easily-verified case? For example a non-constructive proof that some set of numbers is non-empty, along with an example of such a number that can be fairly easily checked? Thanks!

8 12

[math-fun] New Algorithms for Integer Factoring and Integer Factorials (draft #1)
by Warren Smith 03 Dec '11

03 Dec '11

> I have only read the first paragraph, and the following glitch may not > matter, but suppose N=11. The integer square root of this is 3, so I set > R=3 and peel off 3 chunks of three. I'm left with the final chunk being 4, > which is *not* smaller than R as claimed. I have no clue yet whether this > cooks the algorithm; I'm reading on. --Actually 11=3+3+3+2 not 3+3+3+4, but use 14=3+3+3+5 and you're right. Sorry for that bug. No, it does not cook the algorithm since the leftover chunk is never more than about twice as large as the other chunks, which is good enough. (Also, even if it were way larger that still would not matter if the leftover chunk were handled recursively.) Another minor bug is, my final time bound should have had another log factor in it -- log^3 not log^2 --, due to the binary search.

2 1

[math-fun] New Algorithms for Integer Factoring and Integer Factorials (draft #1)
by Warren Smith 03 Dec '11

03 Dec '11

New Algorithms for Integer Factoring and Integer Factorials ====Warren D. Smith Dec 2011===PRELIMINARY FIRST DRAFT============== In this note I explain new algorithms for factoring integer N. I also explain new algorithms for computing N!, the factorial of N. These algorithms both appaear to be world records, although the senses in which that is true are not necessarily very impressive. *****I. Factorial. To compute N!, the naive method is 1*2*3*...*(N-1)*N. We want faster methods. Mentally divide the sequence 1,2,3,...,N into R=floor(squareroot(N)) chunks each R long, plus a leftover smaller chunk if N is not a perfect square. Consider the degree-M polynomial (x)(x-1)(x-2)...(x+1-M) which we can abbreviate as x^_M ["falling factorial"]. We have N! = N^_R * (N-R)^_R * (N-2R)^_R *... * (N-[R-1]R)^_R * (N-RR)!. The final chunk (N-RR)! can be evaluated recursively or just naively using <R operations. All the other chunk values are different values of the same polynomial x^_R, it is just that this polynomial is evaluated at R different values of its argument x, where the different arguments form an arithmetic sequence. Finally multiply all the R+1 terms together going up a binary tree. There are known fast algorithms for simultaneously-evaluating a polynomial of degree M at M different argument values (forming an arithmetic sequence) in a number of arithmetic operations O(pm(M)*logM) where pm(M) denotes the number of arithmetic operations required to multiply to degree-M polynomials symbolically. See, e.g. A.Bostan & E.Schost: Polynomial evaluation and interpolation on special sets of points, Journal of Complexity 21,4 (2005) 420-446. http://algo.inria.fr/bostan/publications/BoSc05.pdf [I also have a different algorithm than theirs which matches their time bound, though probably with a worse constant factor.] By using FFT convolution theorem to multiply polynomials symbolically, pm(M)=O(M*logM). Note, this FFT approach takes us outside the integers into the real and complex numbers, but at the end of the process you get integers back (and the reals did not need to have much higher precision than the integers had to keep the erorrs below +-0.1). If this bothers you you can use Toom multiplication with pm(M)=O(M^(1+epsilon)) instead. This keeps everything rational with bounded denominators. Also, the polynomial x^_M can be computed in symbolic form if desired by polynomial multiplication on a binary tree, in O(pm(M)*logM) arithmetic steps. CONCLUSIONS: 1. N! can be computed in O(squareroot(N)*(logN)^2) arithmetic operations. 2. The total time usage is more interesting to most people than the arithmetic operation count. If we compute over the ring of integers, then the time should be of the same order as performing logN multiplications on numbers of the same length as N!. If we compute over some small ring (such as "the integers mod 1009") then the arithmetic-op count really does govern the time since all operations are on bounded-length numbers. 3. The memory usage is large: need to store order squareroot(N) numbers. *****II. Even faster "primorial"-like things such as LCM(1,2,3,...,N). It is possible to speed up the above algorithm somewhat further by cleverness about primes. I have not thought carefully about how far that can be pushed. But just to make it clear that speedup is possible... suppose instead of computing N! we were satisfied to compute some multiple of primorial(N). Then we do not need to multiply 1*2*3*...*(N-1)*N. It suffices to multiply (product of primes<L) * (product of numbers from L to N which are relatively prime to all primes<L) where L is chosen so that primorial(L)=squareroot(N) roughly, i.e. L has order logN/loglogN roughly. In this case each of my "falling factorial" polynomials can be replaced by a polynomial whose terms have been "sieved" to remove ones that would have been multiples of the primes<L. The degree of this polynomial would no longer be longer R, but rather about R/loglogN. Actually you need to adjust the parameters a bit... and if you want factorials not primorials you need to keep track of the stuff you sacrificed and put it back in... but anyhow SLIGHT IMPROVEMENT: N! can be computed in O(squareroot(N/loglogN)*(logN)^2) arithmetic operations and comparable-factor savings should be possible re time savings and memory usage too. Quite possibly one can do better than these since my prime-using methods were very straightforward with no attempt to be clever. Peter Luschny and Arnold Sch:onhage each invented clever prime-using methods that compute N! in the same time as doing a constant number of multiplications of the numbers of the same length as N! [i.e. O(NlogN) bits long] but their methods, though better than me by a log factor about TIME, are far far worse than me about ARITHMETIC-OP COUNT... so we have to wonder if it is possible to get the best of both worlds. *****III. Factoring the integer N. Assume we know N is composite (fast primality tests are known) and it is not divisible by (say) the primes<100. Define the function F(x)=gcd(x!, N). This is a monotonically increasing function of x with 1<x<=N, and F(1)=1 and F(N)=N. We can evaluate it fast by computing (x! mod N) using the fast algorithm above in the ring of integers mod N, then fast gcd algorithm. (The "improved" algorithm II will also work.) To factor N, one approach is to do a binary search on x with 100<x<squareroot(N) to find an x such that F(x)>F(x-1) and then gcd(x,N) will be a nontrivial factor of N. This will run in time = O( (squareroot(N)/loglogN)^(1/2) * (logN)^2) arithmetic operations on numbers each O(logN) bits long [same length as const*N^2] memory = O( (squareroot(N)/loglogN)^(1/2) ) numbers each O(logN) bits long. That is: Total time = O( N^(1/4) * (logN)^2 * (loglogN)^(1/2) ) * (logloglogN or lower) bit-ops. Total memory = O( N^(1/4) * logN * (loglogN)^(1/2) ) bits. As far as I know, this is a new world record time bound for integer factoring provided we only allow algorithms that are (i) deterministic and (ii) have rigorous worst-case time bound. Further, as I said it might be possible to improve this further by some kind of log factor with cleverer prime-using tricks. *****IV. Factoring the integer N using less memory but more time. Our proposal so far can be viewed as a way to speed up "trial division." As R.S.Lehman pointed out, it is possible to speed up factoring by doing a combination of "trial division to find factors < L" with "Fermat's difference of squares method to find factors > L". Lehman chose the breakpoint L to be of order N^(1/3) thus achieving a rigorous factoring algorithm running in O(N^(1/3)) arithmetic operations. R. Sherman Lehman: Factoring Large Integers, Mathematics of Computation 28, 126 (April 1974) 637-646 We now propose to do the same thing as Lehman but now using "sped-up trial division." I haven't checked this as carefully as I should, but I believe what happens is this. Choose the breakpoint L=N^P for 1/4<=P<=1/2. Besides P, there will also be another tunable parameter Q, with 0<Q<=P/2. The runtime will then be time = O( N^(P-Q) * (loglogN)^(-1/2) * (logN)^2 + N^([1-P]/2) ) arithmetic operations and memory = O( (N^Q / loglogN)^(1/2) ) numbers. If P=1/2 and Q=1/4 then we get our fast (but memory-hog) algorithm without using Fermat. If 1/4<=P<1/2 we slow down, but can enjoy using less memory. For example, choose P=0.4 and Q=0.1 to get a factoring algorithm running in time O(N^0.3) ignoring log terms, and with memory usage O(N^).1) ignoring log terms. This compromise strikes me as actually pretty attractive -- more attractive than either plain Lehman, plain Fermat, or plain trial division. However, it will still be heavily outperformed by Pollard-rho method, ECM, Quadratic Sieve, and NF-Sieve factorers, if you are willing to accept the fact they are nondeterministic and/or have nonrigorous time bounds. *****V. History -- is this just a rediscovery?. It now seems likely that V.Strassen 1976 in a paper I have not seen, invented something similar to my algorithms here -- but I suspect his log terms must have been slightly worse than mine? Volker Strassen: Einige Resultate u:ber Berechnungskomplexitat, Jahresber. Deutsch. Math.-Verein 78,1 (1976/7) 1-8. --end.

2 1