Tag: Day080

Although we’ll do a little review, this post assumes some familiarity with the Cantor set as well as working with fractions in bases other than 10.

So what is the Cantor set?

The usual geometrical definition is to begin with a line segment of length one (as shown at the top of the figure).  Next, remove the middle third of that segment, so that two segments of length 1/3 are formed.  Then remove the middle thirds from those segments, and continue recursively.

Even though — after this process is repeated infinitely, of course — you remove segments whose lengths sum to 1, there are still infinitely many points left!  (Actually, uncountably infinitely many, although this observation is not necessary for our discussion.)

There are many ways to describe the remaining points, but one common way is to say that the Cantor set consists of all those numbers between 0 and 1 (inclusive) which, when written in base 3, may be written only with 0’s and 2’s.

Again, we’ll briefly review.  We have .2₃ = 2/3_10, for example — since the places after the ternary point (no “deci”mals here) represent powers of 1/3.

So if we wanted to find 3/4 in base 3, we note that we’d need 2/3 = 0.2₃, but there would be 1/12 left over. This is smaller than 1/9, so we’re at 0.20₃ so far. Next, we need 2/27, giving 0.202₃, with 1/108 left over. And so on. The result is that 3/4 is equal to 0.202020…₃, where the “20” repeats. This can also be shown using infinite geometric series, if desired:

Surprisingly, the idea for a possibly new type of “Cantor set” came from studying binary trees!  I say possibly new, since I couldn’t find any reference to such a set online, but of course that doesn’t mean someone else hasn’t come across it.  And I call it a type of Cantor set since it may also be formed by taking out thirds of segments, but in a slightly different way than described above.

Now I’ve talked a bit about binary trees before, so I won’t go into great detail.  But here is the important idea:  when you make a branch, you’re pointing in some particular direction, and then turn either left or right, but you can’t just keep going in the same direction.

So what if you looked at ternary expansions, and as you added digits, you had the option of adding 1 to the previous digit (like turning left), or subtracting 1 (like turning right), but you couldn’t use the same digit twice consecutively.  So 0.21021201 would be OK (we’ll drop the 3 subscripts since we’ll be working exclusively in base 3 from now on), but 0.12002120 would not be allowed since there are consecutive 0’s.

Note that adding 1 to 2 gives 0 in base 3, and subtracting 1 from 0 gives 2.  So essentially, starting with 0., you build ternary expansions with the property that each digit is different from the previous one.  And, of course, the expansions must be infinite….

What do iterations of this scheme look like?

We start with a segment of length 1.  Recall we begin with 0., so that means the ternary expansions may begin with 0.1 or 0.2.  Expansions beginning with 0.0 are not allowed, so this precludes the first third of the segment.

Now here comes the interesting part!  On the second iteration, (the third line from the top), we remove different thirds from the first two segments.  Since the 0.1 may continued onto 0.10 or 0.12, but not 0.11, we remove the middle third from the 0.1 segment.  Further, 0.2 may be continued as 0.20 or 0.21, but not 0.22, so we remove the last third of the 0.2 segment.  The iteration process is not symmetrical.

We continue on….  Since 0.10 may be continued as 0.101 or 0.102, but not 0.100, we remove the first third of the 0.10 segment.  You get the idea.  Seven iterations of this procedure are shown in the figure above.

Note that since the process for creating the original Cantor set is symmetrical, this imposes a self-similarity on the set itself.  The Cantor set is exactly the union of two duplicate copies of the original, scaled by a factor of 1/3.

In other words, the Cantor set may also be created using an iterated function system with the following two transformations:

What about the self-similarity of the new Cantor set?  To help in seeing this, here’s a slightly more detailed version of the iteration scheme.

Is there any self-similarity here?  Yes, but the fewest number of transformations I’ve found to describe this self-similarity is five.  The curious reader is welcome to find fewer!

It isn’t hard to see the five vertical bands in this figure — the first three look the same (although the second one appears to be reflected), and the last two also look the same, although reflections of each other.

The first band is all ternary expansions in this new set beginning with 0.10.  How do these relate to the whole set?  Well, 1/9 of the set consists of expansions beginning with 0.001… or 0.002…, and then adding digits different from those previous.  Adding 1/3 therefore gives all expansions beginning with 0.101… or 0.102…, and then adding different digits.  This implies that the self-similarity describing the first vertical band is

The second band consists of those expansions in our strings beginning with 0.12.  But if x is an expansion in our set beginning with 0.10, then 1 – x must be an expansion in our set beginning with 0.12, since we may write 1 as .22222…, repeating.  Therefore, the second band is represented by the transformation

We can think of the third band just as we did the first — except that this band consists of number beginning with 0.20 (rather than 0.10).  So this band is represented by the transformation

The last two bands consist of those expansions beginning with 0.21.  Here, we break into the two cases 0.210 and 0.212, and use our previous work.  For example, those beginning with 0.210 can be found by taking those beginning with 0.10, dividing by 3 to get expansions beginning with 0.010, and then adding 2/3 to get expansions beginning with 0.210:

We describe the self-similarity of the last band — those expansions beginning with 0.212 — analogously:

These are five transformations which describe the self-similarity of the new Cantor set.  I haven’t rigorously proved yet that you can’t do it in fewer, but I think this is the case.

Of course this is just the beginning — you can use the same rule in any base.  That is, begin with 0., and either add or subtract one from the previous digit.  In base 4, you get nice self-similarity, but it gets more involved in higher bases.  In bases higher than 3, you can also use the rule that the next digit in the expansion is different than the previous — and this gives yet another class of Cantor sets.  I’ll leave you to investigate, and perhaps I’ll write again about these Cantor sets when I find out more!