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!


14 Responses to “Open problem in geometric group theory”

  1. j2kun November 16, 2013 at 10:16 pm #

    I’m confused. Is the metric on integers generated by powers of two different from the metric on integers generated by powers of three? Surely it must be, or else the identity map would be a quasi-isometry.

    • j2kun November 16, 2013 at 10:17 pm #

      (also, I think 7 has length 3 as well: 7 = 111 in binary)

      • yenergy November 17, 2013 at 11:52 am #

        Ha thanks Jeremy! I switched it to 9. I know binary…

        This is the word metric, so in the powers of two, the powers of two are our alphabet. If you stop and say generated by 1, 2, 4 vs. 1, 3, 9, you’ll get a quasi-isometry, but the open problem is if you use all the powers- unclear if there’s a universal (k,C). Kevin mentioned this off-hand during class and I thought it’d be a cool little post.

  2. Stephen Bigelow (@stephenpi) December 8, 2013 at 5:20 pm #

    For fixed N, the powers of 3 modulo 2^N can be anything that is 1 or 3 modulo 8 (which I found in the Wikipedia artical on Multiplicative group of integers modulo n). Thus powers of 3 can be arbitrarily large in the powers-of-2 metric. Why doesn’t that answer the question?

    • yenergy December 9, 2013 at 7:07 pm #

      It might be this ridiculous cold but it’s probably just me- I don’t quite understand what you’re saying in your first sentence, Stephen. Can you explain further? Also, thanks for stopping by and commenting!

      • Stephen Bigelow (@stephenpi) December 16, 2013 at 12:21 pm #

        [Oops. I thought I typed a reply but it looks like it hasn’t shown up. Let me try again…]

        If you write the powers of three in binary (1, 11, 1001, 11011, …) then you will eventually see any given sequence of 1s and 0s as a substring – at least, if I understand Wikipedia correctly. So there’s a power of three that goes blahblah1010101010101blahblah. Surely that could be made arbitrarily large in the powers-of-two metric, although it is length one in the powers-of-three metric.

        I think that proves the identity map is not a quasiisomorphism between the two metrics, but I guess that leaves open the question of whether they are quasiisomorphic by some contrived function from Z to Z.

        I trust your cold is better!

      • yenergy December 19, 2013 at 9:45 am #

        Fantastic; I love it when people answer their own questions. But now I have questions for you. I’m not seeing the connection between the integers mod 3 being generated by 2 (I’m guessing that’s what you’re referring to, based on the wikipedia entry?) and this writing powers of three in binary=getting any sequence of 1s and 0s as a substring. Can you clarify more?

        It’s possibly whooping cough! I’ve got antibiotics and an inhaler and I feel much less bad about neglecting my blog.

  3. Stephen Bigelow (@stephenpi) January 6, 2014 at 12:01 pm #

    Whooping cough?! My mother had that as a young child, and has a very early memory of someone saying to her mother “Well, you can’t expect to keep them all.” Perhaps not the best anecdote to tell you – I’m sure you’ll be fine.

    Now, about the powers of 3, let’s just do it modulo 128 instead of 2^N.

    Let U be the group of units modulo 128. It’s just the odd numbers, so it has order 64.

    Let G be the numbers in U that are 1 or 3 modulo 8. It’s easy to check that G is a subgroup of U with order 32.

    It turns out G is cyclic, generated by 3. Thus, for any bits a,b,c,d, the numbers abcd001 and abcd011 are both powers of 3 modulo 128. That is, there are powers of 3 that are [junk]abcd001 and [junk]abcd011.

    The same goes for “arbitrarily large values of 128”. So there are powers of 3 that are [junk][anything-you-want]001 and [junk][anything-you-want]011 in binary.

    The fact that G is cyclic and generated by 3 is apparently due to Guass. I couldn’t find a proof online, though there’s lots of interesting stuff about powers of 3 in binary. It shouldn’t be too hard: you need to show 3^16 is not 1 modulo 128 (for arbitrary values of 128).

    Anyway, thanks for the food for thought, and get well soon. Sorry I’m slow because I get no sort of notification when you reply to a comment…


  1. HAPPY BIRTHDAY BLOG! | Baking and Math - November 27, 2013

    […] Quasi-isometries and an open problem in geometric group theory […]

  2. What is geometric group theory? | Baking and Math - March 2, 2015

    […] and topology- “group theory” is the study of groups, which we’ve seen a few times before, and “geometric” means that we’ll be looking at shapes.  Geometric group […]

  3. Introduction to random groups | Baking and Math - April 26, 2015

    […] describe our groups- every element will be written as a word in the alphabet of generators.  So we’ll use letters like a,b,c… to represent generators, and we’ll put them […]

  4. The fundamental theorem of geometric group theory (part I), topology | Baking and Math - September 24, 2015

    […] background on geometric group theory: you’ll want to know what a group action is and what a quasi-isometry is.  (Refresher: a group G acts on a space X if each group element g gives a homomorphism of the […]

  5. What is a covering space? | Baking and Math - November 14, 2015

    […] I’m obviously referring to a space, and then I mean the Cayley graph of that group (which changes depending on generating set, but if it’s a finite generating set then all Cayley graphs are […]

  6. Happy 3rd birthday, blog! | Baking and Math - November 26, 2015

    […] also like the open problems series: geometric group theory, combinatorics, and group […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: