So it's headed for sqrt(3)/2 (lol).
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Veit Elser Sent: Friday, May 29, 2015 10:29 PM To: math-fun Subject: Re: [math-fun] Wilson's grid problem
I side-stepped the problem of finding optimal perfect matchings of infinite point sets by taking the limit of two lattices with an ever larger common period.
Let G1 be generated by [q, p] and [-p, q] and G2 by [q, -p] and [p, q] where
(q,p) = (1,0), (2,1), (5,2), (12,5), …
i.e. the “silver mean” recursion:
q’ = 2q+p p’ = q
G1 and G2 are both square lattices and in the limit of the recursion have relative rotation 45 degrees. This embedding of G1 and G2 into Z^2 always has the same symmetry as Z^2. The four lattice generators and their negatives approximate the vertices of the octagon in an alternating fashion, much like the ratio q/p alternates being greater/smaller than 1+sqrt(2). This may seem like an innocent point, but it has a big effect because it turns out the optimal matching has what’s called “symmetry breaking”.
The lattice (m Z)^2, where m = q^2 + p^2, is a common subgroup of G1 and G2 of index m. You can therefore work with the m cosets of G1 and G2 and compute distances in the m x m flat torus. I did that for various (q, p) and choices of norm.
Before I get to the results, I should clear up the confusion about norms. Let P be a coset of G1 and f(P) the G2-coset in the bijection, and |P - f(P)| the Euclidean distance in the flat torus (ordinary Euclidean distance taking into account the torus periodicity) between P and f(P). The z-norm we want to minimize is
( (1/m) sum_i |Pi - f(Pi)|^z )^(1/z)
In the limit z -> infinity this just gives the maximum separation.
Now for the results. I found the minimum z-norm bijection using the Hungarian algorithm for minimum-weight bipartite matching. For z >= 2 the bijection converges to a "fractal-greek-cross" in the following sense. Take the set of integer coordinates Pi - f(Pi), translated if necessary into the range (- m/2, +m/2), and center on them unit squares. The union of all the squares is a connected set. If I then rescale this union of squares by the scale of my square lattices, sqrt(q^2 + p^2), I get convergence to a fractal set roughly resembling a greek cross.
Now to the question of symmetry-breaking. As you know, the greek cross has 4-fold symmetry whereas the original optimization problem is invariant with respect to 8-fold rotations. Our approximations of the original problem, i.e. (q, p), break 8-fold symmetry, albeit by diminishing amounts. The optimal bijection *could* have converged to an 8-fold pattern, with the deviations diminishing with the order of the recursion. Instead, I find that all the even- order recursion lattice pairs converge to one greek cross while the odd-order recursion lattice pairs converge to another greek cross — related to the first by a 45 degree rotation.
This is something I knew a couple of years ago, when I was interested in the 2-norm case. (It comes up in the study of quasicrystals.) When David Wilson asked about the infinity-norm case I redid those calculations and found that apparently you get the same bijection for z-norms with z >= 2. I don’t have any ideas why this should be the case, and also why the the optimal bijection changes for z < 2 (the union of unit squares becomes disconnected).
Here are the furthest separated pairs, and corresponding infinity norms:
(q, p) P - f(P) infinity-norm
(2, 1) [1, 0] 0.447214 (5, 2) [3, 2] 0.669534 (12, 5) [10, 2] 0.784465 (29, 12) [22, 14] 0.830876 (70, 29) [63, 14] 0.851753 (169, 70) [133, 84] 0.859952 (408, 169) [372, 84] 0.863568 (985, 408) [780, 492] 0.864982
(I computed the optimal matchings for the first four, and then inferred the rest from the pattern I observed.)
This is converging to a value well below the norm for the 8-fold symmetric bijection in Frettloeh’s paper, which I previously reported as an upper bound. And of course it’s consistent with David Wilson’s lower bound.
-Veit
On May 29, 2015, at 12:12 PM, Allan Wechsler <acwacw@gmail.com> wrote:
The thing that is so challenging about the problem with Z^2(exp(pi/4)) is that the pair of superposed grids is not periodic, so no periodic matching can work. The creeping fear is that no matter how clever your matching procedure is, it will eventually maze itself and leave a point with no available partner closer than (per my earlier joke) 17,000.
On Fri, May 29, 2015 at 2:42 PM, Tom Rokicki <rokicki@gmail.com> wrote:
If I had time I'd start investigating this looking at the Pythagorean triples to get some bounds and insight.
These will give periodic grids. We can assume the matching is *also* periodic and see what happens (the periodicity of the matching may or may not match the periodicity of the tiling).
Both with and without a coinciding point would be useful. There are effective matching algorithms that will probably work up to a pretty large number of points, especially with a reasonably tight bound on the allowed distance.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun