June 2014 - mathfun@mailman.xmission.com

[math-fun] prime tests
by Warren D Smith 01 Jun '14

01 Jun '14

If what you are seeking is never-fail primality tests, the following is the fastest I have that never fails for 32-bit unsigned integers: uint SmithIsPrime32(uint32 p){ //TRUE iff p is a prime and <=32 bits long. uint hash; if((p&1)==0){ return(p==2); } if( !StrongPsp232(p) ){ return(FALSE); } //base 2 strong psuprime test if(p<2047){ return(TRUE); } if( !StrongPsp32(p, 63778) ){ return(FALSE); } //base 63778 ditto hash = (p*2869299540U)>>25; assert(hash < 128); return(hash63778tab[hash]!=p); //perfect hash table of exceptions } where you need this array const uint hash63778tab[128] = { //these 50 numbers are the only nonprime odd spsp{2,63778} below 2^32: 979363153, 0, 0, 643552909, 0, 8725753, 0, 0, 0, 0, 329153653, 48191653, 0, 8036033, 0, 3116107, 0, 0, 839280691, 0, 450866021, 0, 0, 0, 0, 0, 0, 2269093, 0, 0, 0, 0, 0, 2693739751, 0, 2717428033, 1464568381, 0, 0, 0, 0, 1714322377, 1140573601, 0, 0, 63318169, 0, 0, 4157008813, 0, 0, 220729, 0, 0, 0, 0, 0, 3207297773, 0, 0, 0, 385319089, 1930534453, 0, 0, 0, 1054999441, 787085857, 0, 0, 2017509601, 0, 0, 967287751, 1272866167, 0, 3548378341, 3274264033, 0, 0, 0, 2206095589, 2766006253, 453366029, 176030977, 126132553, 0, 0, 0, 0, 3242533897, 0, 1121176981, 0, 2181961, 0, 0, 17208601, 0, 0, 0, 0, 48316969, 741751, 724969087, 0, 0, 0, 43661257, 0, 0, 0, 0, 0, 0, 1153164097, 1104194521, 0, 3323829169, 0, 765378241, 22591301, 1894909141, 3900327241, 60547831, 0, 1328256247, 0 }; and you also need to code up the strong PSP test (which I did). For 64-bit unsigned integers I also have a never-fail test which on average over all odd numbers takes only about 10% more time. It is somewhat harder to describe though, it involves both a strongPSP (base 2) test and a "Lehmer-Smith test." I can supply C code file. The first pseudoprimes for my 64-bit never-fail tests are not known and probably exceed 10^100 (if they exist, which they probably do).

1 0

Re: [math-fun] algebraic geometry query
by Dan Asimov 01 Jun '14

01 Jun '14

Fred wrote: ----- I take off my hat to a model of clarity and concision, making everything look easier than it is (as earlier discovered to my cost). However, I do not understand the necessity for C^2 --- why would not C^1 suffice? . . . ----- Andy had written: ----- nnnI think this is really a theorem of differential geometry, not of algebraic geometry; the only place Warren's proof uses the fact that f is polynomial is when he needs it to be sufficiently smooth. Since we can replace R by any smaller simply connected region that doesn't touch C, we may as well choose R to be diffeomorphic to a disc, and the theorem then becomes: For any sufficiently smooth (C2?) function f on the unit disc, if f is nonzero on the unit circle, but has zeroes inside the disc, then it has a critical point inside the disc. Proof: if f is negative on the unit circle, its maximum is a critical point; if f is positive on the circle, its minimum is a critical point. ----- Hmm, Why wouldn't C^0 (just continuous) work. In R^n, let W be a compact connected (n-1)-dimensional submanifold with connected boundary M = bd(W). Claim: ------ If a continuous function f: W -> R^1 (= the reals) for which 0 lies in f(W) but not in f(M), then f must have an absolute extremum in int(W) = W - M. Proof à la Latto: ----------------- Since f is continuous on the compact set W, it must have both an absolute minimum and an absolute maximum on W. Since f is nonzero on the connected set M, f must take M into either (0,oo) or (-oo,0). If the former, f must have a local minimum in int(W); if the latter f must have a local maximum in int(W). [ ] Corollary: ---------- If f is also differentiable on int(W), then it has a critical point there (since any local extremum x of a function differentiable in a neighborhood of x must have a critical point at x). --Dan Daniel Asimov Visiting Scholar Department of Mathematics University of California Berkeley, California

1 0

[math-fun] Data compressing the primes < 104000
by Bill Gosper 01 Jun '14

01 Jun '14

with CarmichaelQ (fairly simple), and three special cases, Block[{a = 15485857, b = 29462131}, Reap[Do[If[! PrimeQ[k] && ! CarmichaelQ[k] && Divisible[ PowerMod[a + b, k, k] - PowerMod[a, k, k] - PowerMod[b, k, k], k], Sow[k]], {k, 2, 117568}]]] {Null, {{56033, 73633, 93961, 104653}}} There may well be superior and smaller a and b. And almost certainly superior larger ones. But I don't have a good way to look for them. --rwg

1 2

[math-fun] algebraic geometry query
by Fred Lunnon 01 Jun '14

01 Jun '14

Given a plane curve C defined by f = 0 with f(x, y) polynomial, and a region R of the plane (possibly extending to infinity), I assert that C avoids R provided C avoids the boundary of R ; and C has no critical points within R . There must be a well-known theorem to this effect (unless, of course, it's actually false --- a situation by no means previously unknown). But I don't know a reference (or a counter-example) --- anybody? A straightforward way to locate the critical points seems to be to compute the discriminant g of f with respect to (say) x , then find the roots of g(y) = 0 . Is there a more respectable alternative? WFL

5 21

[math-fun] Latto's proof of critical point theorem
by Warren D Smith 31 May '14

31 May '14

>Andy Latto: >> Aha. Right, this is now trivial. > > I'm a little confused. My statement is false, *and* you have a > counterexample, *and* it's trivial? --sorry, to be more clear: I think you had it right, and not only that, have reduced it to a triviality, while my old proof is now seen to have been highly overcomplicated.

1 0

[math-fun] critical points curves regions
by Warren D Smith 31 May '14

31 May '14

Andy Latto: I think this is really a theorem of differential geometry, not of algebraic geometry; the only place Warren's proof uses the fact that f is polynomial is when he needs it to be sufficiently smooth. --WDS: not so. I also used the fact the zero set of a polynomial, restricted to a compact region, has finite measure, e.g. cannot be an infinite spiral. One can easily construct an INFINITELY differentiable (i.e way smooth) function f(x,y) such that f(x,y)=0 is a spiral curve that within some annulus -- or disc -- makes an infinite number of winds. The function f will be 0 on the spiral, and in between windings will have a ridge or valley, but the ridge always has a slight slope, approaching but never quite becoming horizontal. As a result there are no critical points of f within the annulus. > Since we can replace R by any smaller simply connected region that > doesn't touch C, we may as well choose R to be diffeomorphic to a > disc, and the theorem then becomes: > > For any sufficiently smooth (C2?) function f on the unit disc, if f is > nonzero on the unit circle, but has zeroes inside the disc, then it > has a critical point inside the disc. > > Proof: if f is negative on the unit circle, its maximum is a critical > point; if f is positive on the circle, its minimum is a critical > point. --a counterexample to that "theorem" and "proof" is the function f(x,y)=x? Oh, by "nonzero" you meant "never zero." Aha. Right, this is now trivial. > This works in any dimension, and we don't really need the > Perelman-Thurston classification theorem, the Jordan Curve theorem, or > the classification of surfaces. Latto: All we need is the fact that the boundary of a compact simply connected set is connected; the theorem doesn't really require that R is simply connected, merely that it has connected boundary. WDS: my infinite spiral counterexample seems to indicate that is false (within a 3D solid torus)? Well, I think the final last winding of the spiral, which never comes, is a circular ring of critical points, which lie on the boundary of the region, but not inside it, and thus technically yield a counterexample, at least to some wordings of the theorem.

2 1