Tag Archives: quasi-isometry

Open problem in geometric group theory

16 Nov

Update: Per Jeremy’s comments, I’ve updated the end of this post to be more clear and less inaccurate/blatantly untrue.  Thanks Jkun!

The other day in my topics in geometric group theory course, my professor described an open problem which I thought was pretty cool and relatively easy to explain.

First, if you haven’t (which you probably haven’t), check out the “groups” section in my post about Cayley graphs, which was really just about groups.  I just need you to know what the group of integers is \mathbb{Z}.

Now we’re going to talk about generators.  Again, mathematicians do a pretty good job of using reasonable words to name mathematical terms: generators of a group are elements of the group that “generate” that group- just like our parents created our generation (aww yeah), the integers “1” generates all of the integers.  So 2 = 1+1, 17 = 1+ 1+ … +1, -23 = (-1)+ (-1)+ … + (-1).  There’s a bit of terminology that I slipped in there without pointing it out: I used -1 as well as +1 to build all the integers, but I only said that 1 generated everything.  Technically it’s that 1 and -1 generate all the integers, but since -1 is “negative one,” or the inverse of 1, I’ll just say that 1 generates the integers, leaving it implicit that we also include the inverse.

I could also choose more generators.  So, for instance, “1” and “2”.  Why would I do this when I can already write everything in terms of 1?  Because it’s faster sometimes to write things in terms of 2.  For instance, 6 = 1+ 1+ 1+ 1+ 1+ 1, but 6= 2+2+2.  I only need three generators to express 6 if I use 2 as a generator, but I need six if I only have 1.  One thing that geometers care about is distance.  So if I just use “1” as my generators, the distance from 0 to 6 is 6.  But I use “2” as a generator, the distance from 0 to 6 is 3, because I only needed to use three generators to get to 6.

Six blue arrows, only three red arrows

Six blue arrows, only three red arrows

OK so that’s generators, and why we care about them (distances, a.k.a. metrics).  We’re going to switch gears for a minute and then I’ll describe the open problem (it hinges on using different generators for the integers).

Next topic, much scarier sounding word that isn’t actually that scary: quasi-isometry.  Let’s deal with “isometry” first, and “quasi” later.  An isometry is a function from one space to another that preserves distances.  So if x and y are distance 3 apart in the first space, then f(x) and f(y) are still distance 3 apart in the second space.  A few examples: translating x\mapsto x+1 on the real number line is an isometry, since if x-y = d, then f(x) - f(y) = (x+1)-(y+1) = x-y = d.  Multiplying x\mapsto 3x isn’t an isometry: for instance, 1 and 4 are distance 3 apart on the real line, but 3*1 =3 and 3*4=12 are distance 12-3=9 apart.  So this map didn’t preserve distance, and so it isn’t an isometry.  In symbols, the equation for an isometry is d(x,y) = d(f(x),f(y)), and we want this to be true for all possible choices of x and y.

Isometries are great, but sometimes life is a little bit fuzzier than perfectly preserving distances.  We wanted a word to describe functions that were almost isometries, and in math land, that would be quasi-isometry.  Using an equation, we have that f is a quasi-isometry if there are constant numbers k and C so that \frac{1}{k}d(f(x),f(y))-C \leq d(x,y) \leq k d(f(x),f(y))+C.  So it’s an isometry up to some multiplicative and additive constants.  Examples and non examples: all isometries are quasi-isometries, we just let k=1 and C=0.  That multiplication map from earlier is a quasi-isometry with k=3 and C=0: d(f(x),f(y)) = d(3x,3y) = |3x-3y| = 3|x-y| = 3d(x,y).  Here’s something that’s not a quasi-isometry: x\mapsto e^x.  The exponential map grows faster than the multiplicative constant can hold it down.

And now that you know what the integers, generators, and quasi-isometries are, I can describe this open problem.

Remember that 2^0 =1, 2^1=2, 2^2= 4, 2^3 = 8,\ldots and 3^0 =1, 3^1=3, 3^2=9, 3^3=27,\ldots.  This is the question: is the integers generated by \{2^n\} quasi-isometric to the integers generated by \{3^n\}?  For instance, we know that 9=3^2, so 9 has length 1 in the second set (since 3^2 is a generator), but 9=2^3 + 2^0, so 9 has length 2 in the first set.  You can play around with any integer and write it as a sum of powers of 2 and of 3, and try to see if there’s a relationship between the lengths (i.e. the length of 45 is 23 in the 2-set, and is only 15 in the 3-set).  To reiterate, the length of a number in the first set is the minimum number of powers of two you need to add up to it- so although 9 = 2 ^1 + 2^2 + 2^0+2^1, the length of 9 in the first set isn’t 4, but just 2, which is the minimum number.  Similarly, in the second set its the minimum number of powers of three you need.

Fact: If we only look at a finite set of generators, the sets are quasi-isometric.  The tricky part is when we have infinitely many generators, as they get farther and farther apart.

Now you understand something that no one knows the answer to yet!  Isn’t that cool??? This is math!

%d bloggers like this: