March 2016 - mathfun@mailman.xmission.com

[math-fun] The upside of ignorance
by Bill Gosper 24 Mar '16

24 Mar '16

Mathematica won't intersect a line with a plane if any coordinate is non-numeric. So I tricked it into confessing the general case by replacing the twelve symbolic coordinates with Zeta 3, ... , Zeta 25, and then back-substituting. Safe, as long as nobody knows how to simplify the Zetaberg. A burlesque of Bell's inequality? --rwg ppPlane[InfiniteLine[{a_, b_, c_}, {d_, e_, f_}], Hyperplane[{v1_, v2_, v3_}, {p1_, p2_, p3_}]] := Point[{ (a (e v2 + f v3) + d (p1 v1 - b v2 + p2 v2 - c v3 + p3 v3))/(d v1 + e v2 + f v3), (b (d v1 + f v3) + e (-a v1 + p1 v1 + p2 v2 - c v3 + p3 v3))/(d v1 + e v2 + f v3), (c (d v1 + e v2) + f (-a v1 + p1 v1 - b v2 + p2 v2 + p3 v3))/(d v1 + e v2 + f v3)}]

2 2

[math-fun] Grabbing Cubes
by Mike Beeler 22 Mar '16

22 Mar '16

I think this game is now pretty much cooked. The Conclusion in my write-up is: Boxes are classified according to their dimensions into "tall" and "short". Tall boxes have game length equal to the product of their two smaller dimensions, which is also an upper bound on game length of all boxes. Most short boxes have several possible game lengths, but there are a few exceptions. The comparison n1 + n2 - 2 : n3 distinguishes tall (<) from short (>=) boxes. Monte Carlo analysis was used to investigate the game, and to derive and support the above test. It is possible, though unlikely, that further exception cases exist among short boxes larger than those explored. A variant called Getting Cubes has behavior similar to Grabbing Cubes, but differs in the details of exception cases and shape of the game length distributions for short boxes. The box in the original "Problem 327" published in Playground is 5 x 13 x 31. This is a tall box. Therefore, the magazine's claim that the game always lasts 65 moves, is correct. However, some discussion of why that box is not one with varying length games, might improve the published proof. http://www.mikebeeler.com/grabcube-v5.txt <http://www.mikebeeler.com/grabcube-v5.txt> Thanks everyone, — Mike

1 0

[math-fun] Biased coin parity puzzle
by James Propp 22 Mar '16

22 Mar '16

Show that, for any bias p < 1/2, and any positive integer n, if you take a biased coin that shows heads with probability p and toss it n times, the number of times the coin shows heads is likelier to be even than odd. I know one proof (by way of an exact formula for the probability in question) but I'll bet some of you will find other ways to prove this. Jim Propp

4 8

[math-fun] Pizza hut / Conway problems, with alleged solutions (or partially)
by Warren D Smith 21 Mar '16

21 Mar '16

For problem B (at least in the list=set version I did) we can indeed prove uniqueness for the solution "19": As mentioned before, 20 is not a solution; now add "n" to every sum=20 and multiply every product by n, to see that 20+n also is not a solution. This rules out every integer >19, except that there are a few cases where n was already used in the proof 20 was not a solution, hence adding n is forbidden since "set," not "multiset," of numbers summing to 20. But, all those cases, as it happens, were already ruled out anyhow by the computation I originally did. QED. Somebody might also want to work out the list=multiset version of Pizzahut problem B... the answer(s) if any, must be either 0,1,2,... or 19. I'd also be interested to know what Dan Asimov concluded about problem C, his post was rather mysterious. My own investigation of C was likely flawed and/or incomplete in some manner; I think I had some valid thoughts, but they probably were more "a good start" than "the full answer."

1 2

Re: [math-fun] Characterizing polys which permute GF(p)
by Hilarie Orman 21 Mar '16

21 Mar '16

Applied Algebra and Number Theory edited by Gerhard Larcher, Friedrich Pillichshammer, Arne Winterhof, Chaoping Xing Cambridge University Press, 2014 contains a paper "Index Bounds for Value Sets of Polynomials Over Finite Fields" by Gary L. Mullen, Daqing Wan, and Quiang Wang with an extensive bibliography of references, many of them about permutation polynomials. With a reasonably clever search, Google Books will display enough of the paper to allow you to view the bilbiography for that paper. Hilarie

2 4

[math-fun] permutation polynomials
by Warren D Smith 21 Mar '16

21 Mar '16

1. I want to argue that permutation polynomials of GF(q) with polynomial degree <= q*(1-1/ln(q)) are likely to be rare. So prize them when you find them. All functions mapping GF(q) into itself are polynomials of degree<q. There are q^q such functions. Assume nonrigorously that the q! ones which happen to be permutations (bijective maps) are randomly distributed within all functions. Since q! = q^q * exp(-q) = q^(q-q/lnq) approximately (crude Stirling formula) we see that the number of perm-polys living within the polys of degree<q-q/lnq, is expected to be <1. Of course, this probability model is largely bunk, e.g. A*x+B is a permutation-polynomial if A is nonzero, with degree=1. And Dickson found a parameterized family of degree-5 ones when q=+-2 (mod 5): x * (x^4 + B*x^2 + B^2/5) (and compose with linears ad libitum). Also x^k (for k odd) is a perm-poly if q-1 is not divisible by k. But still, presumably there must be some shred of validity to this, in which case there are not terribly many low-degree permutation polynomials in the sense that almost all of them have degrees>q*(1-1/lnq), which is nearly as high as degrees can get. ======== 2. I want to argue, again nonrigorously, that it is likely that Dickson's degree-5 guys (if & when they exist) and linears, suffice to generate all, or anyhow at least half, of all perm-polys via composition. Because: John D. Dixon: The probability of generating the symmetric group, Math. Zeitschrift 110,3 (1969) 199-205 http://link.springer.com/article/10.1007%2FBF01110210 John D. Dixon: The probability of generating the symmetric group, Electronic J. Combinatorics 12 (2005), #R56, pp. 1-5. showed (and the 2nd paper finds the asymptotic expansion of the probability; the first gave merely a quite weak lower bound) that 2 random elements of S[n] will generate the entire group, or its half-size subgroup (the even perms only) with probability-->1 when n-->infinity. So if we regard the Dickson degree-5 polynomials as "random enough" then the Dixon theorem would indicate they should generate everything. Then you'd get examples of most odd degrees easily for large q, but even (and unusual odd) degrees not so easily. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] Correction: Simpler provably random PRNG, and general conjecture about provably random PRNGs
by Warren D Smith 21 Mar '16

21 Mar '16

On 3/21/16, rcs(a)xmission.com <rcs(a)xmission.com> wrote: > I'm not seeing this CRT reconstruction property. > Can you fill in a detail or two? > I know that the sum of the two reconstruction coeffs > must be pq+1, since (1,1) must reconstruct to 1. > But I don't see how the general case turns into the > XOR property: It seems to depend on the quotient > of the raw reconstructed number Kp+Lq, divided by pq. > Awaiting enlightenment, > > Rich --WDS: sorry folks, it appears my claim about Blum-Blum-Shub getting simpler, does not work. Post mortem below: We want to reconstruct x from y=x mod p and z=x mod q. Remember p and q are both primes with p mod 4=q mod 4=3. An answer is x=A*y+B*z, where A is a multiple of q with A mod p=1, and B is a multiple of p with B mod q=1. Then necessarily A and B both are odd, so that LeastSignifBit(x)=LeastSignifBit(y) XOR LeastSignifBit(z). Why? Well, if one or more were even, then LeastSigBit(x) would simply be constant, or would simply equal (say) LeastSignifBit(y). If so, then the bit sequence LeastSignifBit(x) would not be a hard Blum-Blum-Shub sequence, it would be an easy sequence. Just to be sure that this obvious, here's somebody recapitulating Blum-Blum-Shub: http://diamond.boisestate.edu/~liljanab/ISAS/course_materials/BBSpresentati… Well, that all sounded like a great argument. But: Counterexample, p=7, q=11. Then A=22 and B=56. Well, humbug. We can overcome any such counterexample by adding or subtracting M=p*q (which is odd, indeed is 1 mod 4) to either A or B if it were even, to make it become odd. Then A=-55 and B=-21. So x = -55*(x mod 7)-21*(x mod 11)+(some multiple of 77). So, provided the "multiple of 77" is held fixed, my claim is valid in this case. But we can't hold it fixed. Crap. So, OK, my claim is refuted. The reason for failure is: when you chinese remainderize to construct x=A*y+B*z from y=x mod p and z=x mod q, this does NOT really yield x. It really yields "x plus a highly varying multiple of M=p*q, which needs to be removed." ============================== Meanwhile, I nevertheless remain interested in the CONJECTURE: Given K circular sequences of N random bits, and also given a further N-bit "message" which is the XOR of the first K sequences after secret cyclic shifts are applied to each... there is no algorithm that will detect the nonrandomness of the message (e.g. by determining the K private shift values) in expected time less than N^(K/2) operations. REMARK: Here (to make a little progress) the exponent K/2 appears to be tight. We can achieve N^(K/2) * 2*log(N)*K expected running time as follows. Build a McCreight suffix tree indexing all possible log(N)*K-long bit strings arising inside all possible shifted XORs of the first K/2 sequences. But if K is odd, then only index substrings beginning at locations that are multiples of sqrt(N). Now consider all XORs of the message plus the last K/2 sequences shifted all possible ways. Look up their initial 2*log(N)*K bits in the suffix tree, or if K is odd do this not for the "initial" bits but rather try every startpoint from 1 up to sqrt(N). Whenever a lookup succeeds that tells you that you probably won, plus tells you the shifts you need. THE USE OF IT: Seems to me this conjecture is plausible and fundamentally useful for devising psu-random generators immune to statistical tests, crypto, and for devising alleged lower bounds on computational complexity probably all over the place, with your favorite polynomial degree.

1 0

Re: [math-fun] how to test whether a coin is fair
by Guy Haworth 21 Mar '16

21 Mar '16

Gene has it exactly right: a) you need to decide what you mean by 'fair' ... Expectation of a Head = 0.5 +- epsilon ... but what's epsilon? b) Bayesian inference totally takes care of this just decide what your prior belief in the coin is .... e.g., it's Probability of throwing a Head is 'x' ... for all x ... i.e. you know nothing to start with Of course, if it's not fair, you'll be tossing it a long time and getting increasingly incredulous. [ Greece will tell you that if it's a Euro, you don't need to toss it - it's not fair :-) ] Guy

13 19

Re: [math-fun] true random generators
by Warren D Smith 20 Mar '16

20 Mar '16

Salamin's idea with 2 photodetectors requires adjustment to make them balanced, otherwise you'll get, say 70% "1" bits and 30% "0" bits. E.g. an adjustable iris. Also, it is annoying to have to use funny components like light bulbs, which seem non-miniaturizable. More generally, I do not like any design idea involving explicit enormous amplification factors, such as 1 photon amplified all the way up to a logic signal, or tiny noise amplified all the way up to logic signal. The Intel idea -- using a bistable static RAM bit-cell, turn it on, it assumes randomly either an 0 or 1 state -- also requires careful balancing at manufacturing time, otherwise you may get cells which turn on 99.99% of the time to "1." Also it might behave differently at different temperatures. My idea -- iterating F(x) where F is an appropriate function computed by analog circuit -- seems immune to temperature issues. Maybe in theory it is immune to balancing issues but in practice it will not be. But even without balancing it still should be reasonably balanced. Although ultimately all its randomness comes from thermal and quantum noise, it only involves low amplification gains, like factor 2, which should enable higher speed operation. The Intel idea is the simplest and the fastest. Perhaps the Intel idea can be "actively tuned," i.e. if it produces too many 1s, some controller circuit turns a knob to cure that. That however removes a goodly amount of its simplicity advantage.

7 8

[math-fun] Characterizing polys which permute GF(p)
by Warren D Smith 20 Mar '16

20 Mar '16

DA: The original question plus (ax+b)/(cx+d)brings up the question: Which rational functions over GF(n) (n = prime power) are permutations of GF(n) ? WDS: One of my quibbles with RCS probably due to miscommunication. My point is, the cycle in the multiplicative group of GF(p^e) is generated by x := g*x where g is a plain element of GF(p^e). Re DA's question about rational functions: It seems more natural to me if we ask, not about permuting GF(q), but rather about permuting GF(Q) U {infinity}, which has q+1 elements. That is a different question, which DA may or may not prefer. My question has a nice partial answer which is that A/(x+B) with A nonzero causes a permutation. Not so nice in DA's version. And plainly composing those and RCS's two polynomial generators in all possible ways yields all permutations of GF(Q) U {infinity}. The point of RCS's proof was, every permutation of GF(q) is realizable by a polynomial of degree<q. Further, that polynomial is unique, since we can do lagrange interpolation to find it. Can every perm of GF(q) U {infinity} can be realized by poly1(x)/poly2(x) with degree1+degree2<=q because of rational interpolation? For DA's original problem without infinity, The denominator cannot be linear(x) since it will have a zero. It perhaps could be quadratic though, e.g: denominator = x^2 - A where A is nonsquare in GF(q). -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0