*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 .

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.

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

*is a function from one space to another that*

**isometry***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 on the real number line is an isometry, since if , then . Multiplying 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 , 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** . 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: . Here’s something that’s not a quasi-isometry: . 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 and . This is the question: is the integers generated by quasi-isometric to the integers generated by ? For instance, we know that , so 9 has length 1 in the second set (since is a generator), but , 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 , 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!

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.

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

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.

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?

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!

[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!

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.

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…