Mathematics and Digital Art: Final Update

It’s hard to believe yet another academic year is over!  I do think this second semester of Mathematics and Digital Art went a little more smoothly than the first.  This shouldn’t be too surprising, though — the first time implementing any new course is a little bumpy.  Though I must admit, there were surprisingly few bumps the first time around….

Like last semester, I had students create a movie in Processing.  The main tool I had them use was linear interpolation to create animation effects.  As before, I encouraged them to use linear interpolation with any numerical parameter in their movie — how much red there is in the background color, the position of objects on the screen, or the width of points and lines, just to name a few possibilities.

Colette created some interesting visual effects.  Some students (like her) took advantage of the fact that if you don’t set the background color in the draw function in Processing, successive calls to the draw function overlap the previous ones, giving a sense of movement.

 

Peyton was inspired when her friends invited her to go to the beach.  Here is a screen shot of her movie, where the moon reflects off the rippling waves of the sea at Ocean Beach in San Francisco.

PeytonMovie

Next, I’d like to share a few pieces from students’ Final Projects.  Recall that Final Projects are an important part of the course — during the second half of the semester, we spend one or two days a week working on them.  This is the opportunity for students to explore any aspect of the course in more detail.

While Lainey focused on making images which reminded her of her dreams, she began with this collage including  several motifs from our coursework throughout the semester.  She was one of the few to incorporate L-systems into her Final Project.

FinalPresentation-ElaineTousignant

 

Karina, as many students did, experimented with image processing.  She wanted to overlay multiple images at various transparencies to create a kaleidoscopic effect.  Rotating the images required that she brush up on her trigonometry….

Karina

 

Karla was interested in experimenting with color.  She was interested in morphing images of the Buddha.  Karla used the RGB values of the pixels in an original image, like the one shown below on the left, to determine the RGB values of the pointillistic image shown on the right.

KarlaFinal

Also like last semester, I asked students to write a final response paper about their experience with the digital course.  The responses were similar to those of last semester, so I’ll only include a few excerpts here.

I think differently about mathematics in how it relates to art. I always thought that the two would be separate entities, but this class has proved that’s not always the case.

After having taken this course this semester I really have gained an interest in art and programming that I certainly didn’t have before, even after having taken some courses in programming. I think that actually being able to see the endless things that are able to be created using programming and math is really cool….

One student made a particularly interesting remark:

I wish that I had more knowledge on how to type my own code. There were points in the semester where the art I was creating felt a bit like a coloring page where we were given a page that was already drawn and told to fill it in and try to make it our own.

Of course this is what I want to read!  I do want to inspire students to investigate programming further — but students taking this course receive a mathematics credit.  There is certainly no doubt in your mind about how passionate I am about having students learn to write code, but I do need to emphasize the mathematics of digital art.  Maybe next semester I’ll have Nick run some extra sessions on coding for those who are interested in learning more.

I also wanted to share some work from the other course I taught this semester, Linear Algebra and Probability.  I have students work with affine transformations and iterated function systems in this course as well.  Their first project is a still image using Sage, and their second project is a fractal animation using Processing.  Here is Jay’s submission.

 

And finally, I want to remind you that Mathematics and Digital Art is becoming a university-wide course next year.  I am working with the Fine Arts department here at USF to encourage incoming fine arts majors to earn their mathematics credit by creating digital art!  I expect the course to be quite a bit larger this Fall, and will be connecting with the Fine Arts faculty to make sure the content meets their needs as well.

In addition, I will be giving a talk at Bridges this summer (in Waterloo, (the Canadian one, that is)) about my digital art course.  I’m expecting that I’ll receive a wide range of comments and suggestions, so the course may be a little different in the fall.  That’s one nice feature of this course — it’s not a prerequisite for any other course, so there is some flexibility as far as content is concerned.

Like this semester, I’ll provide monthly updates to let you know what changes I’ve implemented, and also to showcase student work.  So stay tuned!

On Cheese: Reprise

I haven’t repeated a post yet — but as I’m getting ready for Final Exams, I thought it appropriate.  I posted this satire over a year ago, but of course it is still relevant.  The traditional system of assigning grades as a measure of, well, anything, is woefully inadequate.  Continue reading at your own peril….

On Cheese

A new semester is about to start! Finally, those students we have worked so hard to prepare are ready to learn The Calculus!  (Note: We do not teach The Calculus, but rather facilitate its learning.)

With class Roster in hand, we make for the Cheesemonger. (Mr. Hadley has been here for decades.) “Mr. Hadley, twenty-one, if you please,” I say, handing him my Roster. That is all there is to it. The next morning, twenty-one perfectly crafted cubes of Preferred Cheese (each having a mass of precisely 100g) are in my class Cupboard — one for each student, clearly labelled. We are ready!

Of course the students’ initial enthusiasm is high, until the inevitable First Exam. Surely much of the material is review — so we use the Petite grater to shave off a small bit of cheese from a student’s Block when they make the inevitable First Mistake. (There is always the exception, naturally — the Micro is used for sign errors, as well as trivial arithmetic errors.) This is done to accurately track students’ progress.

As the semester progresses, the situation becomes more dire. More egregious errors require the use of a Usual grater, while blocks of students who neglect to turn in entire assignments surely warrant being shaved by an Ultra. After years of experience, we are able to gauge precisely how much cheese must be shaved for each particular type of error. (Truly, it is all in the wrist.)

The end draws near — and although well-acquainted with the system, students still worry about the mass of their Block. They must realize that what is done is done — and No!, it is not possible to replenish the cheese! Is there no justice? They have been warned aplenty, but it is not our fault they do not heed our omens.

We are particularly meticulous with the shaving of the Final Exam — as it is an important assessment. Certain errors now warrant more grievous penalties — the Micro is no longer relevant. Beware the sign error!

But the wonders of being Complete! As a result of our experience (and training, naturally — Mr. Hadley is quite the Cheesemonger), the mass of each student’s Block represents their understanding of The Calculus entirely! Moreover, this mass may be converted to any number of convenient units — a percentage, perhaps, or one of various letters meant to convey a State of Understanding. But the work of the Facilitator is done! We rest well, and enjoy our cuppa. (Yes, some decry the fairness of such a system. No matter. Surely it is the best possible.)

On Coding IX: Computer Graphics I

It has been some time since an On Coding installment, and I thought it finally time to discuss computer graphics.  Of course I’ve done that a lot already, as far as several applications go.  For this post, I asked myself something different:  what do I use computer graphics for?

2017-05-04BinaryTreeLambdais01.png

I had never really taken a step back to look at the larger picture, but that’s one of the purposes of this thread.  I came up with seven major uses, in roughly chronological order from when I started using graphics in each way:

  1. Creating fractals.
  2. Graphic design.
  3. Rendering polyhedra in three dimensions.
  4. Mathematical illustration.
  5. Web design.
  6. Mathematical art.
  7. Research.

Today, I’ll give a brief overview, and follow up in future posts with more details about the various platforms I’ve used.

I don’t need to say a lot about the first two uses, since I’ve discussed them in some detail in my posts on Postscript and iterated function systems.  My interest in fractals has of course continued, especially given my passion for Koch curves and binary trees.  I work less with graphic design now — I used to design stationery and business cards for myself and friends, but now that communication is so largely electronic, there is less of a need.  But I do still occasionally design business cards using my art logo, print them onto cardstock, and cut them myself when I need to.

Day092c2016Vienna

I also spend quite a bit of time designing title and separator slides for presentations.  (I frankly admit to never having created a PowerPoint presentation in my entire life.  Yuck.)  I now exclusively use TikZ in LaTeX since you have complete control over the graphics environment.

Day092a

I haven’t mentioned polyhedra extensively on my blog so far, but my interest in three-dimensional geometry goes back to my undergraduate days.  When I started teaching college for the first time, I designed (and eventually wrote a textbook for) a course on polyhedra based on spherical trigonometry.

The main tool I used early on was Mathematica, and when I redid all my graphics for my textbook about five years ago, I used Mathematica.  The image you see above was rendered using POV-Ray, a ray-tracing package which allows the user to specify a wide range of parameters to create realistic effects.  You can see shadows and a reflection as if the polyhedron were sitting on a shiny, black surface.  And while the images generated by POV-Ray are quite a bit nicer than those created with Mathematica, they take more time and effort to create.

Mathematical illustration covers a wide range of uses.  Drawing figures for a mathematical paper perhaps first comes to mind.  I used a package called PSTricks for quite a while (since the “PS” stands for Postscript), but once I learned about TikZ, I changed over fairly quickly.  This means I needed to re-render many older graphics (especially in my textbook) — but since for both packages you need precise coordinates, I already had all the mathematics worked out for the PSTricks function calls.  So converting to TikZ wasn’t all that problematic.  I will be talking in more detail about TikZ in a future post.

Day092b

Of course there are also geometrical puzzles and problems, as I’ve discussed before on my blog.  Nicely formatted graphics go a long way in making a puzzle appealing to the reader.

Web design is especially important, since I rely so much on my website for everything.  I have a web page for my artwork, for my publications, talks, and anything I do professionally.  I strive for functionality and aesthetics.  I’m also a minimalist as far as design goes — “less is more.”

Also important is ease of use for me.  It’s not hard to add something to my homepage.  I don’t have the time (or interest) in redesigning my homepage every I want to add a new link.  I’m not a fan of hiding everything in dropdown menus — I want the user to glance at my site, and immediately click on the relevant link without having to pore through menus.

Mathematical art has actually been a fairly recent use of computer graphics for me — I only really started getting into it about four years ago.  I don’t feel I have to say a lot about it right here, since it is a common thread throughout so many of my posts.  You can visit my art website, or look at my Twitter, where I try to update daily (as much as I can) with new and interesting pieces of mathematical art.

Finally, I’d like to say a word about the last use of computer graphics:  research.   I think this is extremely important, especially with the exploding world of data visualization.  Really, this has been perhaps Nick’s and my most important tool when it comes to studying binary trees.

2017-02-10tree1

Without going into too much detail about this image, is consists of six scaled and rotated copies of one tree (the ones in color) and a related dual tree (in white).  Now count the number of leaves (ends of paths) in common with the colorful trees — and you’ll count 1, 5, 10, 10, 5, and 1.  These are, of course, binomial coefficients:  row 5 of Pascal’s triangle.

Why is this the case?  And is there some general result to be proved?  The point I’m making is that when Nick and I create routines to display different trees or combinations of trees, we look at lots of examples, and seek recurring themes.

We learn a lot by doing this, and the direction of our research is heavily influenced by what we observe.  This might not be so surprising, since after all, fractal trees are such geometrical objects.  I can honestly say the pace of our progress in making conjectures is directly linked to our ability to produce large numbers of trees and knowing what to look for.

So that’s what I use computer graphics for!  In future posts, I’ll discuss the various software packages I use, and try to give some idea of the advantages and disadvantages of each.  I’ll give special emphasis to those that are open-source — there is so much out there that is free to download, anyone interesting in computer graphics will have no difficulty finding something interesting to experiment with!

What is…Inversive Geometry?

It’s been a while since we’ve looked at a new type of geometry, so today I’d like to introduce inversive geometry.  Let’s look at a few pictures first for some motivation.

Day091a

We would like to consider the operation of inverting points, as illustrated above.  Suppose the red circle is a unit circle, the white dot is the origin, and consider the blue point P.  Now define P′ (the orange dot) to be the inverse point of P as follows:  draw a ray from the origin through P, and let P′ be that point on the ray such that

[OP]\cdot[OP']=1,

where [AB] denotes the distance from A to B. That is, when you multiply the distances from the origin of a point and its inverse point, you get 1.

Now why would you want to do this?  It turns out this operation is actually very interesting, and has many unexpected consequences.  Consider the circles in the figure below.

Day091b

Start with the blue circle.  Now for every point P on the blue circle, find its inverse point P′, and plot it in orange.  The result is actually another circle!  Yes, it works out exactly, although we won’t prove that here.  Note that since every point on the blue circle is outside the unit circle (that is, greater than a distance of 1 from the origin), every inverse point on the orange circle must be inside the unit circle (that is, less than a distance of 1 from the origin).

This is just one geometrical property of inversion, and there are many others.  I just want to suggest that the operation of inversion has many interesting properties.

If you pause a moment to think about this operation, you’ll notice there’s a little snag.  Not every point has an inverse point.  There’s just one point which is problematic here:  the origin.  According to the definition,

[OO]\cdot[OO']=1.

But the distance from the origin to itself is just 0, and it is not possible to multiply 0 by another number and get 1, since 0 times any real number is still 0.

Unless…could we somehow make the distance from O to O′ infinite?  It should be clear that O′ cannot be a point in the plane different from the origin, since any point in the plane has a finite distance to the origin (just use the Pythagorean theorem).

So how do we solve this problem?  We add another point to the usual Euclidean plane, called the point at infinity, which is usually denoted by the Greek letter ω.

You might be thinking, “Hey, wait a minute!  You can’t just add a point because you need one.  Where would you put it?  The plane already extends out to infinity as it is!”

In a sense, that’s correct.  But remember the idea of this thread — we’re exploring what geometry is.  When we looked at taxicab geometry, we just changed the distance, not the points.  And with spherical geometry, we looked at a very familiar geometrical object:  the surface of a sphere.  We can also change the points in our geometrical space.

How can we do this?  Though perhaps a simplification, we must do this consistently as long as it is interesting.

What does this mean?  In some sense, I can mathematically define lots of things.  Let’s suppose I want to define a new operation on numbers, like this:

a\otimes b=a^2+37b.

Wow, we’ve just created something likely no one has thought of before!  And yes, we probably have — and for good reason.  This operation is not very interesting at all — no nice properties like commutativity or associativity, no applications that I can think of (what are you going to do with the 37?).  But it is a perfectly legitimate arithmetical operation, defined for all real numbers a and b.

As I tried to suggest earlier, the operation of inversion is actually quite interesting.  So it would be very nice to have a definition which allowed every point to have an inverse point.

But if we want to add ω, we must do so consistently.  That is, the properties of ω cannot result in any contradictory statements or results.

It turns out that this is in fact possible — thought we do have to be careful.  Although we can’t go into all the details of adding the point at infinity to the plane, here are some important properties that ω has:

  1. The distance from ω to any other point in the plane is infinite;
  2. ω lies on any unbounded curve (like a line or a parabola, but not a circle, for example);
  3. The inverse point of ω is the origin; that is, O′ = ω and ω′ = O.

So we can create an entirely consistent system of geometry which contains all the points in the Euclidean plane plus a point at infinity which is infinitely far away from every other point.  We usually call the Euclidean plane with ω added the extended plane.

With the new point, we can now say that every point in the extended plane has a unique inverse point.

This idea of adding a point at infinity is also important is other areas of mathematics.  In considering the complex plane — that is, the set of points of the form abi, where i is a solution of the equation x^2+1=0 — it is often useful to add the number ∞, so that division by 0 is now possible.  This results in the extended complex plane, and is very important in the study of complex analysis.

The point at infinity is also important in defining stereographic projection.  Here, a sphere is placed on the plane, so that the South pole is the origin of the plane.  The sphere is then projected onto the plane as follows:  for any point on the sphere, draw a ray from the North pole through that point, and see where it intersects the plane.

 

Stereographic_projection_in_3D
Courtesy the Wikipedia Commons.

Where does the North pole get mapped to under this projection?  Take one guess:  the point at infinity!

So here is another new geometry!  As we get introduced to more and more various geometrical systems, I hope you will continue to deepen your intuition about the question, What is a geometry?

Mathematics and Digital Art: Update 3

It’s hard to believe it’s been a month since my last update!  This semester has been unusually busy.

At the end of my last update, I said I’d talk more about using L-systems in class.  I decided to focus on the symmetrical Koch-like images I had been working on for the past few years.  There are two reasons for this.  First, it’s fresh — and demonstrates that creating new fractal images is an active research topic; not everything is known.  Second, you need to know some elementary number theory in order to create symmetrical images.  Since none of the mathematics we studied so far was closely related to number theory, this was a great opportunity to see yet another application of a different branch of mathematics.

Day007koch-45-175

I started with introducing the basics of modular arithmetic.  This was new to most students, but the motivation was easy:  the direction you’re pointing after any given move is relevant to deciding if your sequence of segments closes up.  And any time you turn counterclockwise, you increment the direction by the angle you turn, but subtract 360° when you go over 360° since a turn of 360° doesn’t alter your direction.  This is just using a modulus of 360 for the direction you’re pointing.

Then, I reminded them how to find the prime factorization of numbers in order to create a 2-adic valuation.  Recall that the 2-adic valuation of a number is the exponent of the highest power of 2 which divides that number.  This is significant since the 2-adic valuation (mod 2) indicates how to turn when drawing a Koch-like curve:  a 0 represents one angle (60° for the Koch curve), and a 1 represents the other (240° for the Koch curve).  So we created charts like this:

Day0902adic

Then finally, I showed students how to find angle pairs which created symmetrical images using a theorem in a paper I’m working on for the College Mathematics Journal.  As the proof involves significantly more mathematics at a level beyond what we could reasonably discuss in the course, I just showed them the result.  I won’t go into details here, but I’d be glad to share a draft of the paper if you’re interested and adventurous….

For their project work, they had to create images using the results of the theorem in Processing.  Karla created this image, which I find interesting since it exhibits six-fold symmetry, but the exterior elements have seven points on them.  So rarely do you encounter 6 and 7 together in geometry.

Day090karla

Peyton created this image, which is suggestive of a complete image, but which doesn’t include all the line segments.  But the overall symmetry of the image is clear; you can complete it in your mind’s eye.

Day090Peyton

I also asked students to create an image which did not close up, to experiment with parameters which generated a more chaotic image.  Colette created this image, which reminded her of the top of a pine tree.

Day090Colette

Some students did have difficulty using the theorem correctly to generate images with symmetry, so next semester I’ll spend a little extra time making sure everyone’s on track.

We also had another guest speaker visit the class since the last update.  I met Gwen Fisher at the Art Exhibition in Santa Clara at the Regional MAA meeting last month, and thought she would be a great fit for our class.  What I liked about her art is that she works with beads in very mathematical ways — and her work is very different from anything we had been doing in the class.

She brought in several of examples of her beadwork to pass around.  You can see many beautiful pieces on her website, including this Wisdom Mandala piece she designed.

Day090Gwen
Wisdom Mandala, by Gwen Fisher.

What was wonderful about her presentation was that Gwen discussed both the design and the execution of her pieces.  My students were very engaged, and asked lots of questions along the way.

It turns out, though, that I had seen a talk she gave two or three years ago at another conference!  Of course you can’t remember every speaker you see at every conference you attend, especially out of context.  But after seeing her talk, I realized some of the slides looked strangely familiar, and that is because I had actually seen them before….

One more bit of news.  You might remember that Mathematics and Digital Art has been offered as a First-Year Seminar course this year, meaning that only first-year students may enroll, and the maximum number of students in the course is set at 16.

Being a faculty member at the University of San Francisco, I am also working on a project with colleagues in creating a Mathematics for Educators minor — a series of courses aimed at prospective middle-school teachers to broaden their knowledge of mathematics especially suited to middle-school students.  And of course a digital art course would fit nicely into this framework.

But what if a student decides to opt for the minor after their first year?  Well, they couldn’t take digital art.  So now, the course is a regular offering in the Mathematics and Statistics Department, open to any student at USF.  I’m very excited about this, and really hope to spread the word about the Imagifractalous world of mathematics and digital art!

I’ll keep you updated in the Fall, as I have more changes in store for the course.  I plan to move completely to Processing, since now everything I used Sage for has been rewritten for Processing.  And next semester, I’ll include a short unit on binary trees as well.  Stay tuned….

Imagifractalous! 6: Imagifractalous!

No, the title of today’s post is not a typo….

About a month ago, a colleague who takes care of the departmental bulletin boards in the hallway approached me and asked if I’d like to create a bulletin board about mathematical art.  There was no need to think it over — of course I would!

Well, of course we would, since I immediately recruited Nick to help out.  We talked it over, and decided that I would describe Koch-like fractal images on the left third of the board, Nick would discuss fractal trees on the right third, and the middle of the bulletin board would highlight other mathematical art we had created.

I’ll talk more about the specifics in a future post — especially since we’re still working on it!  But this weekend I worked on designing a banner for the bulletin board, which is what I want to share with you today.

BBoardBanner

I really had a lot of fun making this!  I decided to create fractals for as many letters of Imagifractalous! as I could, and use isolated letters when I couldn’t.  Although I did opt not to use a third fractal “A,” since I already had ideas for four fractal letters in the second line.

The “I”‘s came first.  You can see that they’re just relatively ordinary binary trees with small left and right branching angles.  I had already incorporated the ability to have the branches in a tree decrease in thickness by a common ratio with each successive level, so it was not difficult to get started.

I did use Mathematica to help me out, though, with the spread of the branches.  Instead of doing a lot of tweaking with the branching angles, I just adjusted the aspect ratio (the ratio of the height to the width of the image) of the displayed tree.  For example, if the first “I” is displayed with an aspect ratio of 1, here is what it would look like:

2017-04-16Tree1

I used an aspect ratio of 6 to get the “I” to look just like I wanted.

Next were the “A”‘s.  The form of an “A” suggested an iterated function system to me, a type of transformed Sierpinski triangle.  Being very familiar with the Sierpinski triangle, it wasn’t too difficult to modify the self-similarity ratios to produce something resembling an “A.”  I also like how the first “A” is reminiscent of the Eiffel Tower, which is why I left it black.

I have to admit that discovering the “R” was serendipitous.  I was reading a paper about trees with multiple branchings at each node, and decided to try a few random examples to make sure my code worked — it had been some time since I tried to make a tree with more than two branches at each node.

fR

When I saw this, I immediately thought, “R”!  I used this image in an earlier draft, but decided I needed to change the color scheme.  Unfortunately, I had somehow overwritten the Mathematica notebook with an earlier version and lost the code for the original “R,” but luckily it wasn’t hard to reproduce since I had the original image.  I knew I had created the branches only using simple scales and rotations, and could visually estimate the original parameters.

The “C” was a no-brainer — the fractal C-curve!  This was fairly straightforward since I had already written the Mathematica code for basic L-systems when I was working with Thomas last year.  This fractal is well-known, so it was an easy task to ask the internet for the appropriate recursive routine to generate the C-curve:

+45  F  -90  F  +45

For the coloring, I used simple linear interpolation from the RGB values of the starting color to the RGB values of the ending color.  Of course there are many ways to use color here, but I didn’t want to spend a lot of time playing around.  I was pleased enough with the result of something fairly uncomplicated.

For the “T,” it seemed pretty obvious to use a binary tree with branching angles of 90° to the left and right.  Notice that the ends of the branches aren’t rounded, like the “I”‘s; you can specify these differences in Mathematica.  Here, the branches are emphasized, not the leaves — although I did decide to use small, bright red circles for the leaves for contrast.

The “L” is my favorite letter in the entire banner!  Here’s an enlarged version:

fL

This probably took the longest to generate, since I had never made anything quite like it before.  My inspiration was the self-similarity of the L-tromino, which may be made up of four smaller copies of itself.

2017-04-16Ltromino

The problem was that this “L” looked too square — I wanted something with a larger aspect ratio, but keeping the same self-similarity as much as possible.  Of course exact self-similarity isn’t possible in general, so it took a bit of work to approximate is as closely as I could.  I admit the color scheme isn’t too creative, but I liked how the bold, primary colors emphasized the geometry of the fractal.

The “O” was the easiest of the letters — I recalled a Koch-like fractal image I created earlier which looked like a wheel with spokes and which had a lot of empty space in the interior.  All I needed to do was change the color scheme from white-on-gray  to black-on-white.

Finally, the “S.”  This is the fractal S-curve, also known as Heighway’s dragon.  It does help to have a working fractal vocabulary — I knew the S-curve existed, so I just asked the internet again….  There are many ways to generate it, but the easiest for me was to recursively producing a string of 0’s and 1’s which told me which way to turn at each step.  Easy from there.

So there it is!  Took a lot of work, but it was worth it.  I’ll take a photo when it’s actually displayed — and update you when the entire bulletin board is finally completed.  We’ve only got until the end of the semester, so it won’t be too long….

Imagifractalous! 5: Binary Trees III

Last week I talked about working with binary trees whose branching ratio is 1 or greater.  The difficulty with having a branching ratio larger than one is that the tree keeps growing, getting larger and larger with each iteration.

But when you work with software like Mathematica, for example, and you create such a tree, you can specify the size of the displayed image in screen size.

So the trees above both have branching ratio 2 and branching angle of 70°.  The left image is drawn to a depth of 7, and the right image is drawn to a depth of 12.  I specified that both images be drawn the same size in Mathematica.

But even though they are visually the same size, if you start with a trunk 1 unit in length, the left image is about 200 units wide, while the second is 6000 units wide!

So this prompted us to look at scaling back trees with large branching ratios.  In other words, as trees kept getting larger, scale them back even more.  You saw why this was important last week:  if the scale isn’t right, when you overlap trees with r less than one on top of the reciprocal tree with branching ratio 1/r, the leaves of the trees won’t overlap.  The scale has to be just right.

2017-04-08ris2d.png

So what should these scale factors be?  This is such an interesting story about collaboration and creativity — and how new ideas are generated — that I want to share it with you.

For your usual binary tree with branching ratio less than one, you don’t have to scale at all.  The tree remains bounded, which is easy to prove using convergent geometric series.
2017-01-20ris1

What about the case when r is exactly 1, as shown in the above figure?  At depth n, if you start with a trunk of length 1, the path from the base of the trunk to the leaf is a path of exactly n + 1 segments of length 1, and so can’t be any longer than n + 1 in length.  As the branching angle gets closer to 0°, you do approach this bound of n + 1.  So we thought that scaling back by a factor of n + 1 would keep the tree bounded in the case when r is 1.

What about the case when r > 1?  Let’s consider the case when r = 2 as an example.  The segments in any path are of length 1, 2, 4, 8, 16, etc., getting longer each time by a power of 2.  Going to a depth of n, the total length is proportional to 2^n in this case.  In general, the total length is about 2\cdot r^n for arbitrary r, so scaling back by a factor of r^n would keep the trees bounded as well.

So we knew how to keep the trees bounded, and started including these scaling factors when drawing our images.  But there were two issues.  First, we still had to do some fudging when drawing trees together with their reciprocal trees.  We could still create very appealing images, but we couldn’t use the scale factor on its own.

And second — and perhaps more importantly — Nick had been doing extensive exploration on his computer generating binary trees.  Right now, we had three different cases for scaling factors, depending on whether r < 1, r = 1, or r > 1.  But in Nick’s experience, when he moved continuously through values of r less than 1 to values of r greater than one, the transition looked very smooth to him.  There didn’t seem to be any “jump” when passing through r = 1, as happened with the scale factors we had at the moment.

I wasn’t too bothered by it, though.  There are lots of instances in mathematics where 1 is some sort of boundary point.  Take geometric series, for example.  Or perhaps there is another boundary point which separates three fundamentally different types of solutions.  For example, consider the quadratic equation

x^2+c=0.

The three fundamentally different solution sets correspond to  c < 0, c = 0, and c > 0.  There is a common example from differential equations, too, though I won’t go into that here.  Suffice it to say, this type of trichotomy occurs rather frequently.

I tried explaining this to Nick, but he just wouldn’t budge.  He had looked at so many binary trees, his intuition led him to firmly believe there just had to be a way to unify these scale factors.

I can still remember the afternoon — the moment — when I saw it.  It was truly beautiful, and I’ll share it in just a moment.  But my point is this:  I was so used to seeing trichotomies in mathematics, I was just willing to live with these three scale factors.  But Nick wasn’t.  He was tenacious, and just insisted that there was further digging to do.

Don’t ask me to explain how I came up with it.  It was like that feeling when you just were holding on to some small thing, and now you couldn’t find it.  But you never left the room, so it just had to be there.  So you just kept looking, not giving up until you found it.

And there is was:  if the branching ratio was and you were iterating to a depth of n, you scaled back by a factor of

\displaystyle\sum_{k=0}^n r^k.

This took care of all three cases at once!  When r < 1, this sum is bounded (think geometric series), so the boundedness of the tree isn’t affected.  When r = 1, you just get n + 1 — the same scaling factor we looked at before!  And when r > 1, this sum is large enough to scale back your tree so it’s bounded.

Not only that, this scale factor made proving the Dual Tree Theorem so nice.  The scaling factors for a tree with r < 1 and its reciprocal tree with branching ratio 1/r matched perfectly.  No need to fudge!

This isn’t the place to go into all the mathematics, but I’d be happy to share a copy of our paper if you’re interested.  We go into a lot more detail than I ever could in a blog post.

This is how mathematics happens, incidentally.  It isn’t just a matter of finding a right answer, or just solving an equation.  It’s a give-and-take, an exploration, a discovery here and there, tenacity, persistence.  A living, breathing endeavor.

But the saga isn’t over yet….  There is a lot more to say about binary trees.  I’ll do just that in my next installment of Imagifractalous!