May 2015 - mathfun@mailman.xmission.com

[math-fun] Wilson's grid problem
by Warren D Smith 31 May '15

31 May '15

D Wilson: Let G1 = Z^2 be the grid of integer points in the plane R^2. Let G2 be the grid of points in R^2 gotten by rotating G1 by 45 degrees about the origin. What is the smallest c for which there exists bijection f: G1 <--> G2 with |P-f(P)| <= c for all P? WDS: It is superior to consider general Lp norm. Wilson chose the p=infinity norm, but L1, L2, whatever. It also is superior to consider general rotation and translation of G2, not just "translate by (0,0) and rotate by 45 degrees." If we restrict to some finite ball containing N points of G1 and N of G2, then using any Lp norm the optimum solution can be found algorithmically by: Solve a graph min-weight matching problem on the complete bipartite graph with N red and N blue vertices, edge costs are pth powers of distances. This will run in time polynomial in N [in fact O(N^2.5) or less, I believe with Dinic algorithm?]. (Actually p=infinity requires "bottleneck matching" not usual sum-of-weights matching, a slight extra programming hassle -- you make the weights infinite if >threshold, and 1 if <threshold, ask if min-weight matching has finite weight, do outer binary search to find the min allowable threshold. It is possible to combine the binary search with the matching algorithm in such a way no overhead is paid. This is all known.) Re some earlier posters muttering about "fundamental domains," octagons, and so on, I do not understand what they meant. It seems to me, sqrt(2) is irrational. Therefore, there is no domain tiling the plane by translation, that works for both G1 and G2 simultaneously. And there is no octagon that tiles the plane. And there is no 2D crystal group with 8-fold symmetry. Here is a SIMPLER PROBLEM than Wilson's, but I think very rich and of great interest: consider an infinite "slab" (rectangle of width 1, infinite in 1 direction but not bi-infinite). Place it on the grid Z^2 in some generic rotated and translated way. Let F(x) then be the number of grid points lying within distance x of the end of the rectangle. Obviously F(x) is asymptotic to x. The question is what is the error term. If we could prove the additive error is bounded by a constant, that would immediately solve Wilson's problem in the sense of proving his c is finite. (It would not find the minimum c, but would prove it is finite.) It might be that quadratic irrationals (as in Wilson's original problem) behave better than general irrational numbers. F(x) is the counting function for a "1 dimensional quasicrystal." This also is a counting version of classic diophantine approximation problem. So that is 3 reasons why F(x) should be important. A related but harder problem is "Gauss's circle problem" of counting the grid points in the area-A circle centered at (0,0). Obviously this count is asymptotic to A. But what is the error term? k1*A^(1/4) <= |count - A| <= k2*A^(131/416) for positive constants k1 and k2, is the best currently known result; these exponents are 0.25 and 0.314904. Returning to our F(x) problem, The points within the slab can be viewed as the corners of an "infinite stairstep." Whenever the next stairstep would have been outside the slab, you take two steps up, not 1 (or whatever) to correct for that. You never get more than a constant distance outside the slab that you need to correct. There is an infinite sequence of bounded integers (the step-type sequence) that thus arises from any irrational number. For quadratic irrational slopes these sequences have nicer properties than for general irrational slopes. (This also indicates connection to the problem of "pixelized stairstep" approximations to lines, in computer graphics, e.g. see Hanna Uscka-Wehlou: Digital lines with irrational slopes, Theoretical Computer Science 377,1-3 (May 2007) 157-169 http://www.sciencedirect.com/science/article/pii/S0304397507001181 .) For quadratic irrational line slopes these stairstep sequences obey some kind of "approximate self similarity" property. That is, if you hop along a distance corresponding to a best rational approximation to the quadratic approximation, and restart from there, then you are going to get the same sequence back again for quite a while, in fact it should be the same sequence up to some bounded number of edits. And then for quadratic irrationals since they have periodic continued fraction expansion, the best approximants form an exponential sequence roughly (like the fibonacci ratios for golden ratio) which means this "self similarity" works at all scales. Edward T.H. Wang: On Double-Free Sets of Integers, Ars Combinatorica 28 (1989) 97-100 considered one such sequence (I think?) and showed the |error| was bounded by O(logX). See http://mathworld.wolfram.com/Double-FreeSet.html . I may be confused. OEIS and this do not discuss any connection of this to quasicrystals and irrational numbers, and does not seem to explicitly discuss any kind of "stairstep sequence for irrational number" but Wang's sequence clearly is connected to the golden ratio and/or sqrt(2). Anyhow, I think in view of the self similarity thing, log(X) error behavior makes sense and is presumably what one should conjecture is the answer for any quadratic irrational slope in my F(x) error problem. So... I conjecture that whenever the slope is quadratic irrational, |F(X)-X| = O(logX). That conjecture would solve Wilson's original problem but with a logarithmically infinite c, that is, the max distance between a point of G1 and its mate in G2 (within ball of radius R) can be upper bounded by O(logR). I am confident stronger results are true, because Peter W. Shor showed if G2 is random points in an RxR square, then the max distance needed in a matching of G2 to the grid points G1 in same square, is O( (logR)^(3/4) ) with high probability. Wilson's problem must have a better upper bound than this. P W Shor: The average case analysis of some online algorithms for bin packing, Combinatorica 6 (1986) 179-200. T Leighton & P Shor: Tight bounds for minimax grid matching with applications to the average case analysis of algorithms, Combinatorica 9 (1989) 161-187. About "digital lines," if only the pixels corresponding to the points in the slab in my F(x) problem, were colored, then you would draw a line with the correct brightness (i.e. brightness essentially invariant under generic rotations). This is in contrast to every(?) graphics program I ever saw, which always draws lines in a way whose brightness is NOT invariant under rotations. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

8 14

[math-fun] Wilson's grid problem
by Warren D Smith 31 May '15

31 May '15

Wilson's proof of a finite upper bound on c using strips going in a 22.5 degree direction... will also show there is a finite upper bound on c for the problem using ANY rotation angle and ANY translative offset, to define the grid G2 from G1. The strips need to go in the angular direction exactly midway between the x-directions for G1 and for G2. All strips same width. The strip width is chosen so that a G1 gridline parallel to the y axis intersects the strip at a line segment of length=1, open on one end, closed on other. Result, c<=3 in all these problem variants. But wait, there is more. You can also pose Wilson's problem in dimensions 3,4, etc. I claim we can induct on dimension to prove a finite upper bound on c, for any fixed dimension, any and grid G2 defined as G1 with any given translative offset, and any given rotation, where G1 allowed to be any nondegenerate point lattice. To explain this in 3 dimensions where G1=Z^3 simple cubic lattice: Divide the world into slabs using parallel planes. All slabs same width. The planes need to be oriented exactly midway between the xy planes for grid G1, and the xy planes for grid G2, i.e. using the square root of the rotation matrix. The width needs to be chosen so each G1 gridline parallel to z-axis cross slab at a line segment of length=1, closed at one end, open at other. Great. Now WITHIN each slab, we have a 2-dimensional Wilson-esque problem, up to (a) bounded-distance perturbations of each grid point away from its unperturbed grid location, and (b) the two grids G1 and G2 have been distorted by an affine, they are no longer square grids. But they still are geometrically identical lattices, just rotated with respect to one another, and that is all we really needed. QED. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] Wilson's grid problem
by Warren D Smith 30 May '15

30 May '15

> From: Allan Wechsler <acwacw(a)gmail.com> > So the current state of the art is that the minimum possible c is between > 0.707... and 0.92... ? I wonder if a computer search on a reasonably-sized > piece of Z^2 could give any insights. --I'm back to not understanding Veit Elser's solution yielding c<0.92... The problem I have is: although the amazing TILE is 8-way rotationally symmetric, the TILING is not, it has only 4-way rotational symmetry, same symmetry as the grid Z^2=G1. In short the tiling "does not know about" G2. What would have established 0.92 is, each tile contains exactly one point in G1 and exactly one point in G2. I'm only seeing one of those claims. The state of my art is, c is logarithmically infinite or less, almost certainly less. If Elser's result is discarded we currently have no proof c is finitely bounded, but do have nonrigorous arguments, which perhaps can be rigorized, indicating it grows slowly at most, at most like (logN)^(3/4) or logstar(N), and perhaps is finite. Indeed in the Lp norm versions of the problem with p finite, I have given an argument c is finitely bounded, and sketched how to rigorize the argument (but have not carried thru the details, so caveat emptor). The proof of the O(logN) upper bound is rigorous but only works for rotation angles whose tangent is quadratic irrational. I think this is an excellent problem. Great rich depths are hidden inside it.

5 5

[math-fun] mechanical intuition puzzlement
by Bill Gosper 30 May '15

30 May '15

NeilB just 3Dprinted gosper.org/IMG_0348.JPG a more cubical and evil variant of http://www.spacecubes.com/ . The commercial version is known as a dexterity put-together. It isn't it a coordinated motion put-together, like http://gosper.org/IMG_0205.JPG , wherein all six pieces must converge in unison. But puzzle(!): can they *diverge* in unison? If so, what holds it together? Particulalry the slippery commercial one. --rwg Diverge in unison = spin apart, e.g., https://www.youtube.com/watch?v=pvT5ySMnO8U

1 0

Re: [math-fun] Four solid angles
by Henry Baker 30 May '15

30 May '15

BTW, what exactly IS a "solid angle" ? A 2D angle is acos(A.B), where A,B are unit vectors, and A.B is the dot product. What is the analogous quaternion formula for a solid angle ?

4 4

[math-fun] a few tiny comments
by Warren D Smith 30 May '15

30 May '15

To E.S: length ratios are NOT invariant under affine transformations of plane. Area ratios are. To S.W: by Lp norm I meant, not the distance formula in the plane, which is always the usual L2 formula, but rather the closeness of the grid G1 to the grid G2 reckoned in terms of all the N point-to-point distances, via Lp norm of N numbers. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] Elliptic function special values
by Bill Gosper 29 May '15

29 May '15

E.g., EllipticK[1/8 (1 + Sqrt[3])^2] == (3^(3/4) Gamma[1/3]^3)/(4 2^(1/3) π) EllipticTheta[4, 0, E^(-Sqrt[2] \[Pi])] == Sqrt[Gamma[1/8] Gamma[3/8]]/(2^(7/8) \[Pi]^(3/4)) KleinInvariantJ[2 I] == 1331/8 KleinInvariantJ[69^105+2 I] == 1331/8 (Well, whaddya expect from an invariant?) For years I've griped about their absence from Mathematica and from tables (Dlmf, functions.wolfram.com, Mathworld, Wikipedia,...) This is hard to excuse, since such values are nearly all expressible in terms of DedekindEta. E.g., EllipticK[(16 DedekindEta[\[Tau]]^8 DedekindEta[4 \[Tau]]^16)/DedekindEta[2 \[Tau]]^24] == (\[Pi] DedekindEta[2 \[Tau]]^10)/(2 DedekindEta[\[Tau]]^4 DedekindEta[4 \[Tau]]^4) so we'd be well off just mastering DedekindEta[algebraic (north of 0)]. But the biggest collection of values I've ever seen (besides my own) is the *four* in en.wikipedia.org/wiki/Dedekind_eta_function#Special_values . Yet there are papers claiming closed forms for a huge fraction of cases (too many to tabulate). One such is http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.63.5854&rep=rep1&t… which claims to have extended coverage to the likes of DedekindEta[Sqrt[-11]] and DedekindEta[(1 + Sqrt[-11])/3], or at least their Abs's. After several pages of dense hair, they give a formula for a product of these. Then more hair. Then the quotient. In terms of the "Tribonacci constant"! " thus completing our eta evaluation." Which they don't bother to spell out. Lucky for them. Both the product and quotient formulas are WROMG! Digging through my old Macsyma files, DedekindEta[ Sqrt[11]*I] == ((3^(1/8)*(Gamma[1/22])^(1/4)*(Gamma[3/22])^(1/ 4)*(Gamma[5/22])^(1/4)*(Gamma[9/22])^(1/4)*(Gamma[15/22])^(1/ 4))/(2*22^(1/4)*(2^(1/3)*(21*Sqrt[33] + 283)^(1/3) + 2^(1/3)*(283 - 21*Sqrt[33])^(1/3) + 8)^(1/8)*Pi^(7/8))) where the radical simplifies, and is currently choking Corey's denester. But my result is merely empirical. The paper's result is supported by hairy theory. And misprinted, at best. Given the Logs of all its factors, FindIntegerNullVector (PSLQ) finds DedekindEta[ I Sqrt[11]] == ((Gamma[1/11] Gamma[3/11] Gamma[4/11] Gamma[5/11] Gamma[9/11])^(1/5) Root[-1 + 2 #1 - 2 #1^2 + 2 #1^3 &, 1])/ (11^(11/40) (Gamma[2/11] Gamma[6/11] Gamma[7/11] Gamma[8/11] Gamma[10/11])^(3/10)) Modest proposal: We at least have a structure theorem. Or a darn good conjecture. Just evaluate DedekindEta by automated PSLQ|RootApproximant. This could even be made rigorous if there's a theorem stating how close you can get without being exact. Someday, PSLQ will seem a one-button operation, like continued fraction. --rwg MathIsFun for you-know-who.

1 0

Re: [math-fun] Grid problem
by Steve Witham 29 May '15

29 May '15

In the question below, what is the meaning of the brackets in |P-f(P)| ? I thought |P-Q| by default meant the Euclidean distance between the points. From what have I read, that seems to be called l2, not L_\infty. But much of the discussion here seems to be about L_infinity. I am math semi-literate, what am I missing here? It seems to matter below. > Date: Wed, 27 May 2015 23:13:06 -0400 > From: "David Wilson"<davidwwilson(a)comcast.net> > > Let G1 = Z^2 be the grid of integer points in the plane R^2. > > Let G2 be the grid of points in R^2 gotten by rotating G1 by 45? about the > origin. > > What is the smallest c for which there exists bijection f: G1?G2 with > |P-f(P)| ? c for all P? In signal and image processing, the word for bijection is "lossless", and the standard integer-approximation lossless rotation is called the "lifted Givens rotation." The "butterfly" operation within FFTs and DCTs is one application. Expressed as a Python function of x, y, and an angle: def lifted_Givens(x0, y0, theta): x1 = x0 +*round(* y0 * ( cos(theta) - 1 ) / sin(theta)*)* y2 = y0 +*round(* x1 * sin(theta)*)* x2 = x1 +*round(* y2 * ( cos(theta) - 1 ) / sin(theta)*)* return (x2, y2) > Date: Thu, 28 May 2015 18:23:51 +0000 > From: Veit Elser <ve10(a)cornell.edu> > > Take a look at this: > http://arxiv.org/pdf/1305.1798.pdf > > Figure 4 shows such a bijection-generating fundamental domain. The > diameter is given in equation (1), which, after you divide by 2, gives > the bound 0.92 ? on c (for the L_infinity norm). This is actually a > very good bound, considering the fact that 1/sqrt(2) = 0.707 is a > lower bound. > Exercise: Prove that c >= 1/sqrt(2). > Testing the lifted_Givens() function with random numbers, the largest errors I've seen are Euclidian distance: 0.9237+ (l_2?) Max of x error and y error: 0.8534+ (L_infinity?) Since the greatest Euclidean-distance error I get is close to the number from Eq. 1 in the paper, which Veit says is for the L_infinity norm, and the number I get for what I would think is L_infinity, is noticeably less than that, I am confused here. I'm unfamiliar with fundamental domains, although I have generated fractals from orbits of these rotations. (Set the denominator to 8 for 45 degrees, then press Draw.): http://www.tiac.net/~sw/2005/03/Mandala <http://www.tiac.net/%7Esw/2005/03/Mandala> --Steve p.s. Java applets seem to be working again in the latest Chrome.

1 0

[math-fun] Braess' paradox
by Fred Lunnon 28 May '15

28 May '15

See embedded video. New to me, though I had previously heard rumours ... http://theconversation.com/the-maths-of-congestion-springs-strings-and-traf… [no line breaks in above link!] WFL

6 11

[math-fun] Gosper's EllipticK formula. Status and suggested proof.
by Warren D Smith 28 May '15

28 May '15

Bill Gosper: Then I bashed on it so hard that it got unnervingly ungrotesque: (*) EllipticK[1/4 (2 + (-2 + t)/Sqrt[1 - t])] == (1 - t)^(1/4) EllipticK[t] How could anything this simple be new? WDS: Let s=Sqrt[1-t]. Then (*) is rewritten as EllipticK[ 1/2 - (1+s^2)/(4s) ] == EllipticK[ -(1-s)^2/(4s) ] == s^(1/2) EllipticK[1-s^2] Now let s=1-m. Then this is EllipticK[ -m^2/(4(1-m)) ] == (1-m)^(1/2) EllipticK[(2-m)m]. Gosper: WDS formula affliected by "branch bug" Empirically, only works for m west of 1: gosper.org/braunch.pdf WDS: Ok. That demonstrates empirically that my formulas are correct. They work for Re(m)<1, and I claim they also work for Re(m)>1 PROVIDED you choose the correct branch of the EllipticK function [the arbitrary choice made by your software is the "wrong" branch] -- proof: analytic continuation. Gosper: t->1-z is safe and really nice: WDS: Gosper was trying to say this: (**) (1-t)^(-1/4) EllipticK[- ( t^(1/4) - t^(-1/4))^2/4] == EllipticK[t] Now. I think these formulas should be provable, thus demonstrating the correctness of everything, as follows. You note that y=K(x) and y=K(sqrt(1-x^2)) are the basis solutions of the linear differential equation (EQ 1.3.8 in Borwein book "pi & the AGM") (x^3 - x) * y'' + (3*x^3-1) * y' + x*y = 0. Using (**), compute the LHS of the diffl equation using the LHS of (**), and verify it yields 0 if the LHS of the diffl equation yields 0 using the RHS of (**). If so, then we've proven anything obeying the diffl equation must obey the Gosper identity. This proof (if it works) will also prove a "twin" of your identity, for the other solution of the diffl eqn (or, it won't work for the other solution, in which case the initial conditions will be crucial to the proof). By the way, other K() identities in the Borwein book are on pages 10 & 16, probably also many more in there somewhere. It might be yours is equivalent to one Borweins knew about, I have not attempted to decide that.

1 1