Mapping Zr into Zs with Maximal Contraction

Given any bijection f: Z ^r →f: Z ^s with s≥ r , easy volume comparisons show that there must be a universal constant K>0 (depending only on r and s ) and infinitely many pairs of points x,y∈ Z ^r such that || f(x)-f(y)|| > K|| x-y|| ^r/s . This puts a bound on how much contraction can be achieved for any such bijection. We show that, conversely, for any s≥ r there is a bijection f: Z ^r →Z ^s and a constant C>0 such that for all x,y∈ Z ^r we have || f(x)-f(y)|| <C|| x-y|| ^r/s . Phrased differently there is a bijection f: Z ^r →Z ^s which shrinks the distance between the images of any two points as much as possible, up to a constant factor. This generalizes a construction in fractal image processing and answers in the affirmative a question of Michael Freedman. Received May 15, 1996.