[math-fun] Wilson's grid problem
From: Allan Wechsler <acwacw@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.
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. On Fri, May 29, 2015 at 8:49 AM, Warren D Smith <warren.wds@gmail.com> wrote:
From: Allan Wechsler <acwacw@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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [Golly link suppressed; ask me why] --
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.
On Fri, May 29, 2015 at 8:49 AM, Warren D Smith <warren.wds@gmail.com> wrote:
From: Allan Wechsler <acwacw@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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [Golly link suppressed; ask me why] --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Not a worry. I can supply an upper bound. Run vertical lines through the points of G1. Points of G1 with the same x coordinate lie on each vertical line, separated by 1 unit. Call this figure L1. Now rotate L1 by pi/4, giving parallel lines through the points of G2, call this figure L2. Now consider a third set of parallel lines at angle pi/8 to the x-axis, each line of L3 passing through an integer point (0, k). Adjoin each line of L3 to the region strictly between it and the next line above it, you get a set S3 of disjoint half-open strips that cover the plane. Note that each line of L1 intersects each strip of S3 in a half-open segment of length 1, which must include exactly one point of G1. Likewise, each line of L2 intersects each strip of S3 in a half-open segment of length 1, which include exactly one point of G2. Let the intersection of L1 with S be the set of segments A1. Let the intersection of L2 with S be the set of segments A2. Pair each segment of A1 with the segment of A2 by closest midpoint. This induces a bijection between A1 and A2. With a little analytic geometry, we can bound the distance between the midpoints of A1 and A2, and hence the distance between any point P1 on A1 and any point P2 on A2, that is, |P1-P2| <= D for some finite D (definitely D < 2). Each segment of A1 includes a unique point P1 of G1, each segment of A2 includes a unique point P2 of G2. The map f_S(P1) = P2 is a bijection between all points of G1 in S and all points of G2 in S, with |P-f_S(P)| <= D. The union f of f_S for all S is a bijection between all points of G1 and G2 with |P-f(P)| <= D. D is therefore the sought-after upper bound. Could anybody follow this?
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Allan Wechsler Sent: Friday, May 29, 2015 3:13 PM To: math-fun Subject: Re: [math-fun] Wilson's grid problem
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.
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.
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
participants (5)
-
Allan Wechsler -
David Wilson -
Tom Rokicki -
Veit Elser -
Warren D Smith