March 2016 - mathfun@mailman.xmission.com

[math-fun] A problem about finite sets
by Victor Miller 10 Sep '16

10 Sep '16

Say that a finite set of integers, A, has *property P* is there are two non-empty disjoint subsets S and T of A, such that sum(S) = sum(T) (where sum(X) is the sum of the elements of X). 1) Show that every 10 element subset of {1,...,100} has property P (this is fairly easy). 2) Is it true that every 9 element subset of {1,...,100} has property P? Victor

8 9

Re: [math-fun] Raghavendra's algorithm for solving linear systems over finite fields
by Henry Baker 06 Jun '16

06 Jun '16

I can see applications in distributed/parallel implementations. You can do most of the checking & probably a lot of the randomization in parallel. At 09:02 AM 8/15/2012, Warren Smith wrote: >>Preliminary draft: >> http://www.eecs.berkeley.edu/~prasad/linsystems.pdf > >--I don't understand why anybody would want to use this algorithm >for any purpose. It's slower than everything else I can think of and also >randomized i.e. can fail. > >However... perhaps it might be useful if changed to be about finite >RINGS not fields. In rings, you cannot divide, hence gaussian elimination is >not usable. Hence this algorithm then has less competition. >(Even then I'm dubious, but then it'd have at least a hope.)

8 9

[math-fun] 473-gene "artificial bactierium"
by Warren D Smith 12 May '16

12 May '16

Venter et al made their long-awaited "artificial bacterium" (actually synthetic DNA that they managed to get inside a bacterium to "boot up" a wholy artificial design for living being, which of course was based on 473 known natural genes). They think or hope that 473 is near minimum possible. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

6 9

[math-fun] 5 and 7 outcome fair dice
by Bill Gosper 06 May '16

06 May '16

Odd barrel dice have the problem that two faces are always uppermost, so how do you label them? Alternative to face-transitivity, there are fair dice which cannot rest on any face, and yet have one face uppermost. Spoiler: gosper.org/5&7dice.png --rwg I assume these are old ideas. Check out Wikipedia if you haven't seen spherical, 6 outcome dice.

4 3

[math-fun] The Dime and Penny Switcheroo
by James Propp 24 Apr '16

24 Apr '16

Now that my daughter and I have both solved "The Dime and Penny Switcheroo" (see page 21 of Martin Gardner's "Perplexing Puzzles and Tantalizing Teasers, or google "dime and penny switcheroo"), I'm wondering what the general story is. What if we start with n pennies and n dimes on a strip of length 2n+1? How many moves does it take to switch the pennies and the dimes? More generally, given two arbitrary configurations on the strip of length 2n+1, is there an easy way to determine the minimum number of moves required to turn one into the other? Surely this has been studied. (Is it explained in Winning Ways? I don't have my copy handy.) Jim Propp

6 13

Re: [math-fun] Quickies
by Keith F. Lynch 05 Apr '16

05 Apr '16

Victor Miller <victorsmiller(a)gmail.com> wrote: > Gareth McCaughan <gareth.mccaughan(a)pobox.com> wrote: >> William R. Somsky wrote: >>> If done w/ sufficient resolution, and barring a measure-zero set >>> of coincidences, your procedure w/ N dead presidents should result >>> in N(N-1)/2 different orderings. And nice question -- I solved it >>> while driving in the car to get dinner. :-) >> I think you have an off-by-one error. .... >> (You get one *change* in ordering per "line joining two >> of the points", not one *ordering*.) Correct. > Very cute puzzle. Thanks. Coming up with interesting puzzles is often even more difficult than solving them. > Believe it or not, this is related to the clever algorithm of Nimrod > Megiddo for linear programming in 2 dimensions. The idea is that if > you have N linear inequalities in 2 dimensions (which is what this > problem had) the vertices of the polytope given by their intersection > come from intersections of of pairs of the lines (there might be > some degeneracy) which are N(N-1)/2. > Megiddo's idea for minimizing a linear form over the polytope was a > divide and conquer, which done cleverly, only took time *linear* in N. Interesting. I'm not a visual thinker, so I didn't solve the dead presidents puzzle visually. I did notice that it's the same solution as the number of orderings of distances to N random points on a line. I have no idea whether this is a coincidence, or whether in some sense these are the same puzzle. In other words, if you have N random points on a line, and you measure their distances from a point, there are always (except, again, in the case of measure-zero coincidences) exactly N(N-1)/2 + 1 possible different sort orders. Which sort order you get depends on where the point you measure the distance from is. That point doesn't have to be on the line. Also, if you have N random points in M-dimensional space, there are once again N(N-1)/2 + 1 possible different sort orders, *if* the points you measure the distances from are all constrained to a line. But now I'm wondering about the more general case. For instance the number of sort orders of distances to N random points in a plane, as measured from any point in the plane. I think it would not be a constant. Maybe I should write a simulation. For definiteness, I'll say the N points are distributed, with equal probability density per unit area, within a circle. The point the distances are measured from need not be within the circle. Would I get a different answer if, instead of a region of a plane, the distribution was over the whole of a sphere, a torus, or a Klein bottle? (Distances of course to be measured along the surface in each case.) What about instead of a Euclidian metric (sqrt(x^2+y^2)), using a Minkowski metric (sqrt(x^2-y^2))? But then how would I sort the imaginary distances?

7 9

Re: [math-fun] Quickies
by Henry Baker 02 Apr '16

02 Apr '16

If you're on a Linux system, cat file.txt | tr 'A-Za-z' 'N-ZA-Mn-za-m' should do the trick, where the text you want to translate is in file.txt. At 04:47 AM 3/31/2016, Tom Rokicki wrote: >It's rot13. The name should tell you everything. Most good mail readers >let you ungarble it with a single keystroke. > >On Thu, Mar 31, 2016 at 7:35 AM, Simon Plouffe <simon.plouffe(a)gmail.com> wrote: > >> Hello, >> what language is this : V jnf unccl jvgu guvf fbyhgvba, hagvy V abgvprq >> gung jura A vf guerr, >> guvf tvirf frira qvssrerag beqrevatf, naq gurer ner bayl fvk gbgny >> beqrevatf bs guerr guvatf! ???? >> >> Google translate cannot even recognize what it is, >> >> Ok, I see, you have something big in your mouth and this is english, but >> unable to pronounce it correctly ?? >> >> Have a nice day. >> >> Simon Plouffe >> >> 2016-03-31 13:17 GMT+02:00 Andy Latto <andy.latto(a)pobox.com>: >> >> > On Wed, Mar 30, 2016 at 11:35 PM, Keith F. Lynch <kfl(a)keithlynch.net> wrote: >> > >> > > But now I'm wondering about the more general case. For instance the >> > > number of sort orders of distances to N random points in a plane, >> > > as measured from any point in the plane. I think it would not be a >> > > constant. >> > >> > Here's a fallacious proof I came up with for the wrong answer. I had >> > fun figuring out the fallacy, so maybe some other funsters will too. >> > There's a hint as to what's wrong in rot13 at the bottom; I'll post >> > the fallacy, together with the correct answer, in a day or two. >> > >> > For any two of the points, A, B, draw the perpendicular bisector of >> > AB. If we measure from a point on one side of this bisector, A will >> > come before B in the ordering, while if we measure from a point on the >> > other side, B will come before A. So with N points, we have N(N-1)/2 >> > bisectors dividing up the plane into regions, and we'll get a >> > different ordering for each region. If we have K lines in the plane in >> > general position, they divide the plane into K(K + 1)/2 + 1 regions; >> > this is easily seen by induction; when we add the K'th line, it >> > intersects the existing K-1 lines in K points, dividing it into K >> > pieces (K-2 segments and 2 rays); each piece divides one planar region >> > in 2, so we have added K regions, so K lines give us the 1 region we >> > start with plus 1 + 2 + 3 + .... + K more. >> > >> > So with N points, we have N(N-1)/2 perpendicular bisectors, so they >> > divide the plane into >> > >> > 1 + (N(N-1)/2)((N(N-1)/2) + 1) / 2 = (N^4 - 2 N^3 + 3 N^2 - 2N + >> > 8)/8 possible orderings. >> > >> > V jnf unccl jvgu guvf fbyhgvba, hagvy V abgvprq gung jura A vf guerr, >> > guvf tvirf frira qvssrerag beqrevatf, naq gurer ner bayl fvk gbgny >> > beqrevatf bs guerr guvatf! >> > >> > Andy >-- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --

4 4

[math-fun] provable pseudo-randomness viewed as about information loss
by Warren D Smith 31 Mar '16

31 Mar '16

The Blum Blum Shub "provably unpredictable" psu-random number generator is just repeated squaring modulo (p*q) where p and q are each large primes that each are 3 mod 4. Output just one bit per iteration, and the bits are provably hard to predict in the backwards-time direction, in the sense that any algorithm that could predict them would also be able to factor p*q. Well, seems to me, abstracting what is going on and regarding the prime factoring stuff as a red herring... that what we have here, is information loss. That is, squaring (mod p*q) is a many-to-one map. It loses information. If you try to go backward in time, there are several "correct answers"... except only one of them is itself a square (i.e. could have been the result of a forward iteration) and hence the "really correct" answer. So. Let us contrast iterating a function x:=F(x) in two cases: where F is random bijection, and where F is a random function, both having both domain and range that is a universe of cardinality U. Random bijections F: After iterating F a total of T times in a U-element universe from a random starting point, the chance the last step creates a cycle is 1/(U+1-T). So the chance that we evade creating a cycle during steps 1,2,3,...,T is (U-1)/U * (U-2)/(U-1) * ... * (U-T)/(U+1-T) = (U-T)/U so the chance that we are in a giant cycle missing <=M elements of the universe is M/U. In other words, in the best 1% of such experiments, our cycle will miss <=1% of the universe. Random functions F: After iterating F a total of T times in a U-element universe from a random starting point, the chance the last step creates a cycle by returning to a previous, is T/U. So the chance that we evade creating a cycle during steps 1,2,3,...,T is (U-1)/U * (U-2)/U * (U-3)/U * ... * (U-T)/U which is <= (1-(T+1)/(2*U))^T by Jensen's inequality, and >= (1-T/U)^T by monotonicity of the terms. Hence if U is large, the period length is more than 63% likely to be below sqrt(2*U), but also more than 50% likely to be above sqrt(U)*ln2=0.69*sqrt(U). The chance the period exceeds K*sqrt(2*U) is less than exp(-K). So the best 1% of experiments should have periods exceeding about ln(100)*sqrt(U) which is about 4.6*sqrt(U). but the worst among the best 1% should not exceed ln(100)*sqrt(2*U) which is about 6.5*sqrt(U). Point I want to make is: iterating a random function F which is NOT bijective loses information, in fact about 1 bit of information per iteration. One might therefore expect that if we output 1 bit from each iterate, then essentially ANY such iteration ought to be "hard to predict" in the backwards time direction, by any algorithm which doesn't work hard enough to know about which elements of the universe are cycle-members and which aren't. In the Blum-Blum-Shub case, the "cycle members" were the "squares" and recognizing a cycle member with 51% accuracy was equivalent to recognizing squares, which was computationally polynomial-time-equivalent to factoring p*q. But I think that in general, where F is implemented using a boolean circuit, say, distinguishing cycle members from not is going to be a hell of a lot harder than integer factoring. Integer factoring is soluble in polynomial time if you own a quantum computer. But cycle-member recognition should be beyond quantum assistance; since information-loss is generally speaking a quantum-computer killer. Essentially the only way I know to test cycle-membership for X is just to iterate F until it cycles, then ask whether X was on that cycle. That takes exponential expected time for random functions F, and also empirically takes exponential expected time for plenty of actual F. Now let me note that the "boolean circuit cycle recognition problem" is COMPLETE. PROBLEM STATEMENT: Given a boolean circuit F that inputs N bits and outputs N bits; and given an N-bit string X; question is: "is X a cycle member?" Fairly obviously, any oracle capable of answering that with >=51% accuracy (for both false-positive and false-negative error rates below 49%), would also be capable of solving cycle membership for any function F computable in polynomial time, and I think also ought to be capable of 99.9999% accuracy for "most" F. So regard this as a new (?) computational complexity class. Can we now prove interesting/useful subclasses of it, remain complete? (Such as, as a first step, restricted classes of circuits?) -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

3 3

[math-fun] Ray Tomlinson memorial celebration Sunday 4/3 at MIT
by Mike Beeler 31 Mar '16

31 Mar '16

> > http://rst41.weebly.com/a-celebration-of-rays-life.html >

1 0

Re: [math-fun] HB's reasoning about repeated roots
by Henry Baker 30 Mar '16

30 Mar '16

Actually, I still haven't been able to prove that the product of 2 perm polys can be another perm poly. The best I have so far: a quadratic *can't* be a perm poly -- or even a factor of a perm poly -- unless it has a repeated root in the field. Proof: a perm poly p(x) must have a root r in the field (p(r)=0), because some element must map to zero, but then its other factor must also be a zero in the field, which can be computed from the linear poly quotient(p(x),(x-r))=a*(x-s)*(x-r). But a perm poly can't have 2 distinct roots r,s, so r=s and p(x)=a*(x-r)^2, where a/=0. I was hoping to extend this theorem to even polynomials -- e.g., no quartic can be a perm poly, but we aren't in the reals anymore, so a quartic might still factor into a linear (which is a perm poly) and an irreducible cubic. Since the cubic is irreducible, and not a perm poly, it's ok that it has no linear factors. At 11:42 AM 3/30/2016, Warren D Smith wrote: >> From: Henry Baker <hbaker1(a)pipeline.com> >> Permutation polynomials aren't so easy to factor -- at least not into 2 >> factors that are both permutations. >> >> Suppose that a permutation poly p(x) factors into q(x)*r(x), where q(x) & >> r(x) are also perm polys. But p(x) must have exactly 1 root, else two >> distinct roots map into zero. But since q(x) and r(x) are also perm polys, >> they must each have a single root. If they are different, then p(x) would >> have two distinct roots, a contradiction. If q(x) and r(x) share the same >> root, then p(x) has a repeated root. > >> But if p(x) has a repeated root, then >> by the pigeonhole principle, there is some field element without a preimage >> via p(x), so p(x) can't be a permutation poly -- once again a contradiction. >--that is where you went wrong. >> Scratch that reasoning! >> x^3 is a perm poly mod 5, & has a repeated root! > >> So a permutation poly can't possibly factor into two permutation polys. > >--so what you really proved was, a permpoly cannot factor into two permpolys, >unless all three have the same root. >Without loss of generality we can demand that root be 0 (via a translation).

1 0