April 2016 - mathfun@mailman.xmission.com

Re: [math-fun] Prof.Dr. Landau's polynomial decomposition
by Henry Baker 03 Apr '16

03 Apr '16

The Landau algorithm can handle the cases in GF(p) s.t. p doesn't divide deg(G). I didn't mention this, because I wasn't interested in deg(G)>p, as I'm only interested in permutation polys over GF(p), which have deg(F)<p. The other cases (called "non-tame") are handled by a companion paper to the one I referenced by Prof./Dr. von zur Gathen. I've been using Maxima (an open source version of Macsyma); I don't believe that its polydecomp routine uses the Landau algorithm -- at least I haven't been able to get it to properly handle finite field cases. I have submitted a bug report; we'll see what comes back. I'm pretty sure Maple implements some of the best poly decomp algorithms, as von zur Gathen is Canadian, as is Maple. Mathematica might implement a good one, perhaps. I implemented a version of the Landau algorithm for my own use in Maxima. My version is quick & very dirty; I merely wanted to see what it was doing & whether it worked. At 06:26 PM 4/3/2016, Warren D Smith wrote: >I suppose you could call a poly "prime" if it has no >such decomposition. (And I use the term literally: >"de-composition.") New kind of primeness notion. > >Seems to me Macsyma et al ought to offer finding this >decomposition as yet another capability. Could be useful. >If Landau does it over finite fields then doing it over integers >(and perhaps rationals?) could be done via some kind of chinese >remaindering of finite field results. > >In a finite field, there is a problem however. >Some polynomial decomposition F(x)=G(H(x)) >could happen, even though H and/or G actually have greater >degree than F. Right? > >Can Landau detect those? Doubt it. > >-- >Warren D. Smith >http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

Re: [math-fun] very cool perm poly decomposition over GF(p)
by Henry Baker 03 Apr '16

03 Apr '16

Hi Jim: Sorry, I don't know her personally (although I've seen her on many YouTube talks), so tell Dr. Landau that I'm sorry for using an inappropriate name. Dr. Henry Baker At 01:03 PM 4/3/2016, James Propp wrote: >On Sunday, April 3, 2016, Henry Baker <hbaker1(a)pipeline.com> wrote: > >> I just found a really cool polynomial decomposition algorithm >> which works beautifully for polys over GF(p) whose degree is <p, >> i.e., particularly those which are permutation polynomials. >> I believe this algorithm is due to Ms. Susan Landau (now @ WPI), >> although I can't be 100% sure about this w/o asking her. > >I know Susan Landau, and I am 99% sure she would rather be called "Dr. >Landau" or "Prof. Landau" than "Ms. Landau". (Though there are worse things >you could call her, I guess, like "Mrs. Neil Immerman".) > >Jim Propp

3 4

Re: [math-fun] lotteries
by Henry Baker 03 Apr '16

03 Apr '16

Someone recently described to me a scheme to make a 50-state legal one-armed bandit. Basically, whenever you pull the lever, the machine will make a small bet on an option listed on the Chicago options exchange, and then quickly close out the bet for whatever the winnings (or losings) on this bet produce. So long as you are a "sophisticated investor" who has a properly signed options agreement, you should be able to legally play to your heart's content. If nothing else, this system will test economist Malkiel's thesis. At 09:53 AM 4/3/2016, Warren D Smith wrote: >Those one-arm bandit machines in Vegas I believe have psu-random >generators by Marsaglia inside them, but may achieve true randomness >by just perpetually running the psu-random generator, then outputting >when some human hits a button. Unless the human can time it to a >fraction of a microsecond the result has a lot of true randomness. >Vegas's needs are very low, in terms of bit rate. E.g. a few bits per >second would be good enough for them. >-- >Warren D. Smith >http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

Re: [math-fun] lotteries
by Warren D Smith 03 Apr '16

03 Apr '16

Those one-arm bandit machines in Vegas I believe have psu-random generators by Marsaglia inside them, but may achieve true randomness by just perpetually running the psu-random generator, then outputting when some human hits a button. Unless the human can time it to a fraction of a microsecond the result has a lot of true randomness. Vegas's needs are very low, in terms of bit rate. E.g. a few bits per second would be good enough for them. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] random number generator circuit diagram
by Warren D Smith 03 Apr '16

03 Apr '16

I actually drew a circuit diagram, based on my old idea: https://dl.dropboxusercontent.com/u/3507527/OpAmpChaos2.png -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

4 7

[math-fun] palindromes
by Warren D Smith 02 Apr '16

02 Apr '16

https://www.youtube.com/watch?v=JUQDzj6R3p4 And here's a professor who made students write a computer program to discover palindromes: http://www.cs.columbia.edu/~evs/papers/palindrome.ps He claims it will find "several thousand" palindromes per day, of which about 1% actually make any sort of grammatical sense, which is determined by a human reading about 1000 of them and finding 10 that are allegedly grammatical. This seems a rather slow generation rate(?), and one has to wonder whether some sort of piping of the output into an English-parser program to eliminate things that seem unparsable, could greatly reduce the human part of the labor. Their finest discovery was "Twenties acne? Encase it, Newt."

1 0

[math-fun] Why no actual Victorian computers?
by Henry Baker 02 Apr '16

02 Apr '16

This is a serious question, and not just a steampunk (Google it) fantasy. Perhaps the rest of you have had the same experience of being incredibly impressed by the willingness of Victorian mathematicians to do prodigious calculations by hand. I'm not talking about merely algebraic manipulations, although some of those are legendary, but also numerical calculations. Babbage & Lovelace had already shown how to make a computer in the 1840's, and modern reconstructions showed that it worked just as they had predicted. Babbage was intimately involved in code-breaking, so he would have had precisely the same rationale for building a computer as did Turing & the Bletchley-ites. Now the manufacture of machinery wasn't in the greatest of shapes in 1840, although the manufacture of arms and bullets pushed things along dramatically in the Civil War and the European wars in the latter part of the 19th C. The auto industry dramatically improved the precision and scale of manufacturing, but we still didn't see computers in 1910. Boole & Frege made substantial improvements in mathematical logic, and Hilbert basically laid out the program in 1900. But still no computers. My conclusion: The inventor of the first true computer died in WWI. No one knows his/her name, but WWI put such a huge notch in the demographics of England and Germany, the two most likely places for the first computer to have been developed, that the engineering talent to develop a computer was wiped out, and took another generation to develop. The homelands of both England and Germany were more-or-less unscathed by WWI, but like Passover or a neutron bomb, the structures remained but the people were gone. Yes, a mechanical computer would not have been terribly reliable, but neither were the first electronic computers. However, once even an unreliable mechanical computer had been developed, the race would have been on to develop faster & more reliable computers, which would have forced an electronic revolution -- probably 20 years earlier. What would the 20th C. have looked like had Moore's Law started 20 years earlier? BTW, a similar question can be addressed to the clockmakers of several hundred years earlier. How come they didn't develop a programmable computer? Ditto with the Greeks and their Antikythera Mechanism. Ditto with the Romans and their extensive water works. The Romans could have developed *fluidic logic* with water on some of the mountain streams, and used it to do some basic calculations. Nature figured this out a long time ago: We now know that minimal universal calculating machines can be extremely simple; the number of gates in the simplest CPU is very small. The question is: why did it take mankind so long to discover this idea? Evolution apparently discovered self-replication pretty early on -- perhaps only a few hundred million years after the Earth was formed -- i.e., on about the same time scale as it took the Moon's orbit to settle down. RNA self replication wasn't terribly reliable, but then evolution came up with DNA, which is a more-or-less "pure" digital storage mechanism. I don't know the exact dates for DNA, but they may go back further than 1.5 billion years ago. Once a reliable storage (i.e., *tape*) mechanism was available, life was off to the races. References: https://en.wikipedia.org/wiki/Mechanical_calculator https://en.wikipedia.org/wiki/Mathematical_logic

5 5

Re: [math-fun] Sort orders according to distances
by Keith F. Lynch 02 Apr '16

02 Apr '16

Dan Asimov <dasimov(a)earthlink.net> wrote: > 1) Are the points labeled? Yes, if only by their coordinates. I didn't mention this, since the solution obviously doesn't depend on what they're labeled or in what order they're labeled. I thought it went without saying that they're not to be renamed in the middle of the solution, just as I didn't mention in my dead president's puzzle that it's not okay to get additional sort orders by renaming Wilson "Jefferson" and vice versa. > 2) Are you taking N labeled points, (selected in advance from > whatever space and then asking what are their different orders > from a variable additional point? Yes. > 3) How are they selected? Randomly, with uniform probability distribution within some range, and no points outside it. As I mentioned, in the 2D infinite plane case, that range is the interior of a circle, but I'm not sure that makes any difference. In the 2D sphere, torus, and Klein bottle cases, that range is the whole 2D surface. The location of the variable additional point is not constrained, except that it's within the space. And, to avoid zero-measure pathologies, it can't be equidistant from three of the labeled points. (Other zero-measure pathologies to be avoided are equidistant labeled points, three labeled points on the same line (except in the 1D case), four labeled points in the same plane (except in the 2D case), etc., two of the labeled points being in the same place, and two of the lines connecting pairs of labeled points being parallel (except in the 1D case). There may be others.) > The first 2 paragraphs seem to assume that in at least 1D, however > they be selected there is going to be one answer, just a function > of N. Yes, which is why I didn't bother to give a distribution for them. It doesn't matter how they're distributed, so long as no two are in the same place and no two of their N-choose-2 pairwise distances are equal. As I mentioned, the solution is the same as for the dead presidents problem, which makes me wonder if they're the same problem in disguise. > But then in paragraphs 3 and 4, you are considering some probability > distribution and mentioning a simulation, indicating that you agree > that (in general) the answer is not necessarily just a function of N. I don't have any intuition as to whether there's a unique solution for 2D, or whether it depends on the arrangement. I have determined that if the "variable additional point" is constrained to be very distant from the circle containing all the labeled points, that the first point in the sort order will always be one of the labeled points in the convex hull of the labeled points, and that the number of the points in the convex hull, if N>2, can be anything from 3 to N. But that's very weak evidence about the more general case. > Keith, can you please express the problem rigorously so that the > answers to my 3 questions above are included either explicitly or > implicitly? I hope I have done so now. It's not easy being totally unambiguous. Especially when dealing with something random. It's even worse than the problem of proofreading my own text. *I* know what I meant, so it's easy to read what I meant rather than what I wrote. (And I have worked as a professional proofreader.)

1 0

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

01 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

Re: [math-fun] MXOR
by Henry Baker 01 Apr '16

01 Apr '16

The tried & true way to get your own instruction is to get that functionality incorporated into a standard benchmark. Also, convince Microsoft, Apple or Oracle to put this functionality into one of their inner loops. That's how the graphics people got their stuff in. That's how the linear algebra people got their stuff in. That's how the crypto people got their stuff in. That's why the Lisp stuff never made it in (aside from the fact that they could never decide exactly what instruction they wanted). Thanks to GCM crypto, Intel now has carryfree multiplications, so GF(2^n) ops are now fast. https://en.wikipedia.org/wiki/CLMUL_instruction_set http://www.samiam.org/galois.html At 05:23 PM 4/1/2016, Adam P. Goucher wrote: >Just out of interest, *why* isn't MXOR in the Intel instruction >set? It doesn't seem too complicated to implement, and it's useful >both in cryptography and data analysis (see 'persistent homology').

1 0