From: Chas F Brown Subject: Re: Isometries in the integer lattice. Date: Mon, 28 Aug 2000 20:02:29 -0700 Newsgroups: sci.math Summary: [missing] Pierre Bornsztein wrote: > > > So, my questions are : > a) for what values of d it is necessary that a bijective function > T:S ->S which preserves the distance d is an isometrie of S? > Let S be the 2-D integer lattice ZxZ, D(p,q) be the euclidean distance function. (Much of the following argument could probably be adapted for QxQ, the lattice of points with rational coordinates. Hmmm...). Define Isom(S, d) be the set of all functions T:S->S such that for all p, q in S, D(p,q) = d -> D(T(p),T(q)) = d. So T in Isom(S,d) is "T preserves distance d". Define Isom(S) to be the set of all functions T such that for all d, T in Isom(S,d), i.e., "T is an isometry". (T in Isom(S) implies T is bijective). For your questions (bijective T or not) we only need consider those T with T((0,0)) = (0,0), since if T' in Isom(S,d), let T(p) = T'(p) - T'((0,0)). Then T in Isom(S, d), and T' in Isom(S) iff T in Isom(S). Given some d, let G = {g_i | g_i in S and D(g_i,(0,0)) = d}. (If G is empty, then every function trivially preserves distance d; so assume G not empty.) Let S' = { p | p = sum(g_i in G, n_i*g_i), n_i some integer for each g_i}. S is an Abelian group under addition of points. S' is a subgroup (the smallest subgroup containing G), hence a normal subgroup, of S; therefore S is the disjoint union of cosets of S'. Let K be some coset of S', so K = p0 + S'. If p in K, q in S, then D(p,q) = d implies q in K. In particular, p0 = (0,0) implies that p in S', q in S, and D(p,q)=d implies q in S'. From this, we can get: if T in Isom(S,d) and T((0,0)) = (0,0), then T(S') is a subset of S'; if in addition, T is bijective, then T(S') = S'. This gives us our first criteria: [1] If S' != S, then exists some bijective T in Isom(S, d) and T not in Isom(S). Proof: Let V((a,b)) = (b,a). V in Isom(S) -> V in Isom(S,d). Let T(p) be defined: for p in S', T(p) = V(p); if p not in S', T(p) = p. Then T in Isom(S, d), but not T in Isom(S). Next step: we can show that for bijective T with T((0,0)) = 0 and T in Isom(S, d), then T is a group automorphism of S'; i.e., T(S')=S', and p,q in S' -> T(p+q) = T(p) + T(q). The proof follows (roughly) from first assuming g, h in G, and noting that (g+h) and (0,0) are the only two points that are distance d from both g and h, thus the same must follow for T(g+h), T(0,0), with respect to T(g) and T(h). Given T(0,0), T(g), and T(h), only one point satifies this criteria, point T(g)+T(h); so T(g+h) = T(g) + T(h). Then use similar logic and induction to show that if g in G, p in S', then T(p + g) = T(p) + T(g); and finally show that p,q in S' -> T(p+q) = T(p) + T(q). (a,b) in S' -> (-a,b) in S' and (b,a) in S', so we can see that S' = S iff (1,0) in S'. If T is a group automorphism of S', and (1,0) in S', then every point (a,b) in S has T(a,b) = a*T(1,0) + b*T(0,1). It's fairly easy to show that if also T in Isom(S,d) and T(1,0) = (x,y), then x^2 + y^2 = 1. This then implies that T in Isom(S). This gives our next criteria: [2] If S' = S, then for all bijective T in Isom(S,d), T in Isom(S). This with [1] gives: [3] (for all bijective T, T in Isom(s,d) -> T in Isom(S)) iff ((1,0) in S'). Which d satisfy (1,0) in S'? Some off-the-cuff observations. Trivially, if not exists integers a,b with a^2 + b^2 = d^2, then G = S' = {}, so not (1,0) in S'. Similarly, d = 0 has not (1,0) in S'. Also, let G = {(a,b), (-a,b), (b,a), (b,-a)} with a*b !=0 and a != b; and S' = (generated by G). Let q = gcd(a,b). Certainly we can form (2*a,0) and (2*b,0), which implies we can form (2*gcd(a,b), 0) = (2*q,0). At least one of a/q, b/q is odd. If both are odd, we can form (q,q); but we need one of a/q, b/q to be even to form (q,0). Thus, we need (d^2) an odd integer; since d^2 even -> every pair (a,b) with a^2 + b^2 would either both be even -> gcd(a,b) even, or both be odd -> we can't get (gcd(a,b),0), instead we get (2*gcd(a,b),0). Thus, d = sqrt(34) = sqrt(3^2 + 5^2) doesn't meet our needs, for example. On the other hand, if (d^2) is odd and square-free and exists at least one pair (a,b) with a^2 + b^2 = d^2, then this implies that any pair (a',b') with a'^2 + b'^2 = d^2 has gcd(a',b') = 1, since if p|a' and p|b', then p^2 | (d^2); then we can form (1,0). So d = sqrt(13) = sqrt(2^2 + 3^2) meets our needs, for example. This latter doesn't cover all cases - (5^2) is odd and not square free, but because 5^2 = 3^2 + 4^2, and gcd(3,4) = 1, we can form (1,0). Perhaps you have some futher ideas about d's satsifying (1,0) in S'? > b) For these values, may the condition "bijective" be omitted? > If T is not assumed to be a bijection, then (1,0) in S' is still neccessary (by [1]) but not sufficient in [3]; for example if T in Isom(S, 1), then we can use T((a,b)) = (a+b, 0), which is clearly not an isometry. > c) for what values of d and d' it is necessary that a bijective function > T:S ->S which preserves the distances d and d' is an isometrie of S? > I'm not sure; if there is some set U = {d_1, d_2, .. d_n} of distances, then let G = { p | D(p, (0,0)) in U }; [1] follows as above; for [2], i *think* it could be proven that (bijective) T is still an automorphism, in which case [3] would still hold. T is still an automorphism of the subgroups of S that are generated *solely* by distance d_i; but when considering g in G_d1 and h in G_d2, you've got 2 unknown points that could be T(g+h). Have to think about it.... > Thanks in advance for your answers or references. > > Pierre. Cheers - Chas --------------------------------------------------- C Brown Systems Designs Multimedia Environments for Museums and Theme Parks ---------------------------------------------------