April 2016 - mathfun@mailman.xmission.com

Re: [math-fun] perm polys and continued fractions -- not.
by Henry Baker 10 Apr '16

10 Apr '16

Note that everything is mod x^p-x, which is NOT irreducible; in fact x^p-x = x(x+1)(x+2)...(x+p-1), so lots of zero-divisors. Result is *not* a field, and lots of intuitions are wrong. For example, "x" itself has no inverse. We know for sure that x->x+1 and x->2/x do generate ALL (and just) the perm polys (proved by someone else & verified by my Maxima code), so all I'm doing is examining the consequences of this. At 06:12 PM 4/9/2016, Warren D Smith wrote: >H.Baker: >(I may be the last person on Earth to know this, but...) >All "even" perm polys over a prime p can be written in the form: >... >a+1/(b+1/(c+1/(d+1/(e+1/(f+x)))) >...a *continued fraction* !! > >--WDS: >Seems like a great observation! >And I think this CF rational form is more useful than the polynomial form >where x^(p-2) is written instead of 1/x. > >By "all even" you meant what? That every even permutation >can be written this way?? > >If so, then every odd perm is representable as a single odd perm, composed >with a general even perm. And the most convenient odd perm is: x --> >g*x mod p >if p is an odd prime and g is a generator modulo that prime. > >Which would mean that EVERY perm -- both odd and even -- modulo p=prime, >is representable as a continued fraction in this way, it is just that >at the end we optionally >multiply it by g. > >Seems very elegant to me. > >=== > >There's just one problem: you're wrong. > >Specifically, a+1/(b+1/(c+1/(d+1/(e+1/(f+x)))), >no matter how high you stack it, is just a fractional linear >of the form > (A+Bx) / (C+Dx). > >So this all was rather absurd. Plainly, this is not enough, in general, >to generate all perms, or all even perms, or even anyplace close. >There are p! perms and p!/2 even perms but fractional linears >cannot generate more than p^4 of them, indeed (slightly >more carefully counting) at most (p+1)*p*(p-1)/6 are possible. > >-- >Warren D. Smith >http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

Re: [math-fun] perm polys and continued fractions -- not.
by Warren D Smith 10 Apr '16

10 Apr '16

H.Baker: (I may be the last person on Earth to know this, but...) All "even" perm polys over a prime p can be written in the form: ... a+1/(b+1/(c+1/(d+1/(e+1/(f+x)))) ...a *continued fraction* !! --WDS: Seems like a great observation! And I think this CF rational form is more useful than the polynomial form where x^(p-2) is written instead of 1/x. By "all even" you meant what? That every even permutation can be written this way?? If so, then every odd perm is representable as a single odd perm, composed with a general even perm. And the most convenient odd perm is: x --> g*x mod p if p is an odd prime and g is a generator modulo that prime. Which would mean that EVERY perm -- both odd and even -- modulo p=prime, is representable as a continued fraction in this way, it is just that at the end we optionally multiply it by g. Seems very elegant to me. === There's just one problem: you're wrong. Specifically, a+1/(b+1/(c+1/(d+1/(e+1/(f+x)))), no matter how high you stack it, is just a fractional linear of the form (A+Bx) / (C+Dx). So this all was rather absurd. Plainly, this is not enough, in general, to generate all perms, or all even perms, or even anyplace close. There are p! perms and p!/2 even perms but fractional linears cannot generate more than p^4 of them, indeed (slightly more carefully counting) at most (p+1)*p*(p-1)/6 are possible. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] perm polys and continued fractions
by Henry Baker 08 Apr '16

08 Apr '16

(I may be the last person on Earth to know this, but...) All "even" perm polys over a prime p can be written in the form: p(x) = (a + (b + c + ... + (z+x)^(p-2))...)^(p-2)) e.g., p1(x) = a+x p2(x) = a+(b+x)^(p-2) p3(x) = a+(b+(c+x)^(p-2))^(p-2) p4(x) = a+(b+(c+(d+x)^(p-2))^(p-2))^(p-2) etc. So, for p=7, we have p1(x) = a+x p2(x) = a+(b+x)^5 p3(x) = a+(b+(c+x)^5))^5 p4(x) = a+(b+(c+(d+x)^5)^5)^5 p5(x) = a+(b+(c+(d+(e+x)^5)^5)^5)^5 p6(x) = a+(b+(c+(d+(e+(f+x)^5)^5)^5)^5 This form may not look familiar, but we can rewrite y^5 as 1/y, and we now recognize this form as a *continued fraction* !! Thus, for p6(x), a,b,c,d,e,f forms a continued fraction for the permutation polynomial !! Note that this cf representation is not unique, but it may be possible to produce a canonic form. We can get *odd* permutations by premultiplying the entire permutation polynomial by a constant from the other coset.

1 0

Re: [math-fun] cubes passing thru holes in cubes
by Warren D Smith 08 Apr '16

08 Apr '16

> There's a neglected part of this puzzle: Proving there's a path > for the inner hypercube, through the outer hypercube. Confirming that > the left over piece of the OH is connected, and that there's an > actual tunnel through it. Perhaps showing that the IH can pass > through the tunnel -- if it's not straight, maybe there are twists > and turns? > > We can check the 3D case with a model. But the higher dimensional > margins are pretty skimpy, suggesting it might not be a cakewalk. > > Rich --if there ever were a problem that could be described as a "cakewalk" this must be it! But yes, based on the literature Gosper mentioned (I had no idea but this cubes-thru-cubes problem goes back to 1693!) it seemed like nobody had considered the possibility of a twisting/turning tunnel? It seems "obvious" that best is a straight tunnel, but it seemed like nobody had proved that, and thus perhaps by twisting/turning one could optimize the cube size ratio a little more than one could with a straight tunnel? No... I think not. See http://mathworld.wolfram.com/CubeSquareInscribing.html especially picture, which seems to show, that the size ratio is determined by a single moment in the history of the cube-passing-thru-tunnel. Therefore, the twisting and turningness of the tunnel is irrelevant to improving the size-ratio. Also the connectedness of the cube after drilling the tunnel, is "obvious" in all dimensions>=3. If so, the problem is equivalent to the question of what is the largest (n-1)-hypercube you can inscribe in an n-hypercube. If it is believed (which happens to be true when n=1,2,3) that the answer involves the two hypercubes having the same center, then the answer arises from an nXn rotation matrix, times a scaling factor. This has n*(n-1)/2+1 degrees of freedom. [The other n*(n+1)/2 degrees of freedom are not free, they are determined by simultaneous quadratic equations saying the rows of matrix are orthonormal.] You optimize those degrees of freedom subject to the demands that all vertices of the rotated cube, lie inside or on the boundary of the unrotated cube, which is a set of linear inequalities. (If we did not believe the "same centers" hypothesis, then an additional n degrees of freedom would be needed.) So, whatever the optimum is, is determined by n*(n+1)/2 quadratic equations plus some linear equations, involving n^2+1 real variables. We can eliminate all variables but 1 by the method of "Macaulay multipolynomial resultants" which appears to be not very well understood even over 100 years after F.S.Macaulay invented them. He wrote a book "The algebraic theory of modular systems" (Cambridge University Press, 1916) available online here https://archive.org/details/algebraictheoryo00macauoft More pedestrianly, we can eliminate one variable at a time by computing pairwise resultants with respect to that variable, for pairs of polynomials, using one of several standard determinant formulas (one is by Sylvester) for the polynomial-pair resultant. That means if we start with P polynomials (in P variables) of degree <=d then after we eliminate a variable we get (P-1)*P/2 polynomials (in P-1 variables) of degree <=d*d (I think; perhaps a somewhat greater degree bound is necessary) and I presume we may discard all but P-1 of those polynomials then continue on. This repeated degree-squaring explains the tremendous degree growth in the algebraic numbers. After eliminating all but 1 variable, P-1 eliminated in all, the degree is squared P-1 times, resulting in final degree<=d^(2^(P-1)) for the final univariate polynomial. In our cubes-thru-cubes problem in n dimensions this would predict the algebraic number answer would be of algebraic degree about 2^(2^(n*(n-1)/2)), note the DOUBLE exponential. Now by the use of Macaulay rather than pedestrian resultant techniques, and being actually careful (I've been non-careful), one can probably improve the degree bounds versus what I just said. Further, there could be miracles where, e.g, the polynomials magically factor, or decompose ala Kozen-Landau, so you have less degree than naively thought. But it should be clear the algebraic degrees probably are going to be pretty damn enormous pretty damn soon, and I very much doubt enough miracles can occur to save you from that. Hence I also think, above some moderate dimension (say 10), it is going to be utterly hopeless to express the optimum answer to the cube-thru-cube problem in any kind of closed form that fits in the observable universe. Which returns me to the question I posed as "more interesting" and certainly more hopeful: what is the asymptotic behavior of the cube-thru-cube answer in large dimension n? And wikipedia claims one can pass a regular simplex thru a hole in another, and a regular octahedron -- both those problems again can be generalized to n dimensions. John Wallis in the first ever solution (which was suboptimal) in 1693 of the cube-thru-cube problem, assumed the direction of motion was the long diagonal. Because a cube viewed that way projects to a regular hexagon, Wallis found largest square inscribable in reghex, and voila. Can we use Wallis's idea to derive a lower bound for the n-dimensional problem? Well. It seems to me if you were to drill a conventional circular (cross section is hyperspherical) hole thru the hypercube [-1/2,1/2]^n in the (1,1,1,...,1) direction, then the largest radius R you could use would obey: R is the length of the vector from 0 to the mean of (n-1) hypercube vertices. So I think 2R = squareroot( n - log2(n) ) approximately. That is not quite large enough, we would need sqrt(n-1) for the most naive lower bound from the circular hole idea, to get traction. So, the most naive Wallis-like attack failed.

1 0

Re: [math-fun] cubes passing thru holes in cubes, try 3D printing
by Bill Gosper 08 Apr '16

08 Apr '16

On 2016-04-07 16:51, rcs(a)xmission.com wrote: > I've seen this, maybe at a past G4G. Gosper? Well, there's https://en.wikipedia.org/wiki/Prince_Rupert%27s_cube http://momath.org/home/math-monday-passing-a-cube-through-another-cube/ They've been called Ronayne's Cubes. http://www.gabrielnivasch.org/fun/hole-in-a-cube https://books.google.com/books?id=Aq5JAQAAMAAJ&pg=PA185&lpg=PA185&dq=cube+c… https://books.google.com/books?id=ZZ9ZAAAAYAAJ&pg=PA185&lpg=PA185&dq=cube+c… James Lee (shown with Jeannine Mosely, gosper.org/IMG_2161.JPG) who has been 3D printing since age 6, and I have been looking at this. The punctured cube is little more than a flimsy triangle. Passing one through another is not very impressive, so modelers usually leave one cube unpunctured. --rwg > > There's a neglected part of this puzzle: Proving there's a path > for the inner hypercube, through the outer hypercube. Confirming that > the left over piece of the OH is connected, and that there's an > actual tunnel through it. Perhaps showing that the IH can pass > through the tunnel -- if it's not straight, maybe there are twists > and turns? > > We can check the 3D case with a model. But the higher dimensional > margins are pretty skimpy, suggesting it might not be a cakewalk. > > Rich > > ---------- > Quoting Warren D Smith <warren.wds(a)gmail.com>: > >> actually, the 3D printers among us might want to construct the 3D >> case of this problem. >> >> >> >> -- >> Warren D. Smith >> http://RangeVoting.org <-- add your endorsement (by clicking >> "endorse" as 1st step) >> >> _______________________________________________

2 1

[math-fun] Database of math problems
by Keith F. Lynch 08 Apr '16

08 Apr '16

Suppose I had a math problem, and wanted the solution. For instance the following: How large a subset of the N^2 points on an N-by-N square grid can there be with none of the distances between the points in the subset being equal? I could try to solve it, or I could ask others, perhaps on this list, if they know the answer. Thanks to Sloane, there's also a way to look it up: I could "solve" it, by brute force, for the first few N, then look up the resulting sequence in OEIS. If anyone has a general solution, that will point me at it. Also, if a problem gives rise to a large integer or an unusual real number ("large" and "unusual" meaning it likely never occurs in any other context), I could do a Google search on the integer or a search on one of the several databases of real numbers for the real number. For instance when I discovered that 8022581057533823761829436662099 was a palindrome in both binary and ternary, a Google search assured me that (probably) nobody had ever noticed this fact before. Unfortunately, many problems don't lead themselves to any such searches. For instance: What odd numbers, if any, are equal to the sum of their proper divisors? If I didn't know that that's called a "perfect number," I'd be unlikely to be able to find a link to the enormous research that's been done on it. (It's very likely the oldest unsolved problem.) But what's really needed is not just a database of sequences, large integers, or unusual real numbers, but a database of problems. The difficulty, of course, is that there are many different ways of phrasing the same problem, no canonical logical language in which there is a unique way of phrasing a problem (and I'm not sure whether such a language is even possible (Lojban certainly doesn't qualify)) and no known way of automatically translating the former into the latter. But if these difficulties could somehow be solved, it would be a wonderful resource. Each problem would be listed, along with its full or partial solution, whatever is known. If you type in an ambiguous description of the problem, the search program would point out the ambiguity to you. What do professional mathematicians do when they wonder if a "new" problem has a known solution? I suspect that the division of math into numerous subject areas is of limited utility, given that the same problem may fit in different subject areas, depending on how it's phrased, or (equivalently (?)) may be isomorphic to what sounds like a very different problem. For instance would anyone have ever noticed the link between the Riemann zeta function and prime numbers if every mathematician knew either number theory or analysis, but never both? I think it was Euler who first noticed the link; he lived early enough that he may have known the whole of then-known math. But that's obviously no longer possible.

6 6

Re: [math-fun] cubes passing thru holes in cubes, try 3D printing
by Warren D Smith 07 Apr '16

07 Apr '16

actually, the 3D printers among us might want to construct the 3D case of this problem. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] cubes passing thru holes in cubes
by Warren D Smith 07 Apr '16

07 Apr '16

[To RWG: My naive look would have yielded a degree estimate a good deal greater than 8, but the degree reductions are probably sort of low-dimensional miracles that eventually in high dimensions will not have much effect?] Suppose we begin with two unit hypercubes, one is [-1/2,1/2]^D, other is same but translated 10 along the x-axis. Now, rotate the first hypercube in the (x,x1) plane by angle 1/9 radian, in the (x,x2) plane by angle 1/9^2, in the (x,x3) plane by angle 1/9^3, etc. Here x1,x2,x3,... all are axes orthogonal to each other and to the x-axis. Now claim the second hypercube will, by moving it back down the x-axis, pass thru the first hypercube, because those rotations "widened" it in all directions orthogonal to x-axis. If that argument is valid, then it shows the first D-dimensional hypercube can actually be made slightly smaller than unit by about 1 part in 9^(D-1), and a unit hypercube still will pass thru it. Better would be to figure out what the max-allowed rotation angles are, which would not necessarily be optimum, but would provide a sort of greedy-like crude guess at the optimum, and which would be a valid lower bound. As an upper bound, the scaling factor must be less than squareroot(D/(D-1)) by considering diameters of the D-hypercube and (D-1)-hypercube. So there is a pretty large gap between this upper bound, and the putative lower bound (which I have not actually worked out, I merely sketched roughly a way one might try to do it) -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] Embedding and curvature
by Mike Stay 07 Apr '16

07 Apr '16

A sphere can be embedded into Euclidean 3-space. Can a lower-curvature space always be embedded in a space with higher curvature and more dimensions? I.e. could a hyperbolic surface with constant curvature 1 be embedded in a three-dimensional hyperbolic space with constant curvature 2? -- Mike Stay - metaweta(a)gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com

2 4

Re: [math-fun] math-fun Digest, Vol 158, Issue 26
by Warren D Smith 07 Apr '16

07 Apr '16

> From: Mike Stay <metaweta(a)gmail.com> > Subject: [math-fun] Embedding and curvature > A sphere can be embedded into Euclidean 3-space. Can a > lower-curvature space always be embedded in a space with higher > curvature and more dimensions? I.e. could a hyperbolic surface with > constant curvature 1 be embedded in a three-dimensional hyperbolic > space with constant curvature 2? > -- > Mike Stay - metaweta(a)gmail.com > http://www.cs.auckland.ac.nz/~mike > http://reperiendi.wordpress.com --you are confused: hyperbolic spaces would have curvature -2 and -1, note the minus signs. But anyhow: The "sphere at infinity" in hyperbolic space is Euclidean (curvature=0) and smaller spheres have every positive curvature. The "equidistant surfaces" from a hyperplane in hyperbolic space have got every constant negative curvature you could want (above the curvature of the mother space). So I think the answer to your intended question is yes. > > > > ------------------------------ > > Message: 5 > Date: Thu, 7 Apr 2016 18:56:05 +0200 > From: Simon Plouffe <simon.plouffe(a)gmail.com> > To: math-fun(a)mailman.xmission.com > Subject: Re: [math-fun] cubes passing thru holes in cubes > Message-ID: <57069125.1010804(a)gmail.com> > Content-Type: text/plain; charset=windows-1252; format=flowed > > > > Hello, > > I passed the number into the grinding machine : nothing found. > 1.00083944685934978860193... = unknown to me. > > I used the 'smart' lookup and even the super smart lookup, > generalized expansion, LLL test: Nothing. > > Best regards, > Simon plouffe > > > > > ------------------------------ > > Subject: Digest Footer > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > ------------------------------ > > End of math-fun Digest, Vol 158, Issue 26 > ***************************************** > -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0