A New Cantor Set?

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 .23 = 2/310, 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.23, but there would be 1/12 left over. This is smaller than 1/9, so we’re at 0.203 so far. Next, we need 2/27, giving 0.2023, with 1/108 left over. And so on. The result is that 3/4 is equal to 0.202020…3, where the “20” repeats. This can also be shown using infinite geometric series, if desired:

$\dfrac34=\dfrac{2/3}{1-1/9}.$

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:

$y=\dfrac13x,\qquad y=\dfrac13x+\dfrac23.$

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

$y=\dfrac 19x+\dfrac13.$

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

$y=1-\left(\dfrac 19x+\dfrac13\right)=\dfrac23-\dfrac19x.$

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

$y=\dfrac 19x+\dfrac23.$

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:

$y=\dfrac13\left(\dfrac 19x+\dfrac13\right)+\dfrac23=\dfrac1{27}x+\dfrac79.$

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

$y=\dfrac13\left(\dfrac23-\dfrac 19x\right)+\dfrac23=\dfrac89-\dfrac1{27}x.$

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!

Imagifractalous! 3: Fractal binary trees

I’ve taken a break from Koch-like curves and p-adic sequences for an arboreal interlude….  Yes, there’s a story about why — I needed to work with Nick on a paper he was writing for Bridges — but that story isn’t quite finished yet.  When it is, I’ll tell it.  But for now, I thought I’d share some of the fascinating images we created along the way.

Let’s start with a few examples of simple binary trees.  If you want to see more, just do a quick online search — there are lots of fractal trees out there on the web!  The construction is pretty straightforward.  Start by drawing a vertical trunk of length 1.  Then, move left and right some specified angle, and draw a branch of some length r < 1.  Recursively repeat from where you left off, always adding two more smaller branches at the tip of each branch you’ve already drawn.

If you look at these two examples for a moment, you’ll get the idea.  Here, the angle used is 40 degrees, and the ratio is 5/8.  On the left, there are 5 iterations of the recursive drawing, and there are 6 iterations on the right.

Here’s another example with a lot more interaction among the branches.

This type of fractal binary tree has been studied quite a bit.  There is a well-known paper by Mandelbrot and Frame which discusses these trees, but it’s not available without paying for it.  So here is a paper by Pons which addresses the same issues, but is available online.  It’s an interesting read, but be forewarned that there’s a lot of mathematics in it!

In trying to understand various properties of these fractal trees, it’s natural to write code which creates them.  But here’s the interesting thing about writing programs like that — once they’re written, you can input anything you like!  Who says that r has to be less than 1?  The tree above is a nice example of a fractal tree with r = 1.  All the branches are of the same length, and there is a lot of overlap.  This helps create an interesting texture.

But here’s the catch.  The more iterations you go, the bigger the tree gets.  In a mathematical sense, the iterations are said to be unbounded.  But when Mathematica outputs a graphic, it is automatically scaled to fit your viewing window.  So in practice, you don’t really care how large the tree gets, since it will automatically be scaled down so the entire tree is visible.

It is important to note that when r < 1, the trees are bounded, so they are easier to study mathematically.  The paper Nick and I are working on scales unbounded trees so they are more accessible, but as I said, I’ll talk more about this in a later post.

Here are a few examples with r > 1.  Notice that as there are more and more iterations, the branches keep getting larger.  This creates a very different type of binary tree, and again, a tree which keeps getting bigger (and unbounded) as the number of iterations increases.  But as mentioned earlier, Mathematica will automatically scale an image, so these trees are easy to generate and look at.

Nick created the following image using copies of binary trees with r approximately equal to 1.04.  The ever-expanding branches allow for the creation of interesting textures you really can’t achieve when r < 1.

Another of my favorites is the following tree, created with r = 1.  The angle used, though, is 90.9 degrees.  Making the angle just slightly larger than a right angle creates an interesting visual effect.

But the exploration didn’t stop with just varying r so it could take on values 1 or greater.  I started thinking about other ways to alter the parameters used to create fractal binary trees.

For example, why does r have to stay the same at each iteration?  Well, it doesn’t!  The following image was created using values of r which alternate between iterations.

And the values of r can vary in other ways from iteration to iteration.  There is a lot more to investigate, such as generating a binary tree from any sequence of r values.  But studying these mathematically may be somewhat more difficult….

Now in a typical binary tree, the angle you branch to the left is the same as the angle you branch to the right.  Of course these two angles don’t have to be the same.  What happens if the branching angle to the left is different from the branching angle to the right?  Below is one possibility.

And for another possibility?  What if you choose two different angles, but have the computer randomly decide which is used to branch left/right at each iteration?  What then?

Here is one example, where the branching angles are 45 and 90 degrees, but which is left or right is chosen randomly (with equal probability) at each iteration.  Gives the fractal tree a funky feel….

You might have noticed that none of these images are in color.  One very practial reason is that for writing Bridges papers, you need to make sure your images look OK printed in black-and-white, since the book of conference papers is not printed in color.

But there’s another reason I didn’t include color images in this post.  Yes, I’ve got plenty…and I will share them with you later.  What I want to communicate is the amazing variety of textures available by using a simple algorithm to create binary trees.  Nick and I never imagined there would be such a fantastic range of images we could create.  But there are.  You’ve just seen them.

Once the Bridges paper is submitted, accepted (hopefully!), and revised, I’ll continue the story of our arboreal adventure.  There is a lot more to share, and it will certainly be worth the wait!