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 on line 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)