Joshua Trees and Toothpicks

After the Joint Mathematics Meetings in San Diego last month, I took a day off for some botanical and mathematical tourism. I drove up to Joshua Tree National Park, in the high desert beyond the San Bernardino Mountains.

The park’s namesake is the cheerfully odd Yucca brevifolia. According to a park brochure and web site, the Joshua tree used to be a lily, but now it’s an agave. The same brochure explains a little about the growth and development of the plant. Initially, a single stalk grows straight upward and eventually produces a flower at the apex. If that flower is fertilized, the fruiting process destroys the meristem—the actively growing tissue at the tip of the stem. The stalk then bifurcates, producing two limbs of roughly equal size, each with a new apical meristem. The branches grow in unpredictable directions. When the two new growth tips ultimately flower and fruit, they too bifurcate, creating four apices.

Joshua trees with 2⁰, 2¹, 2² and 2³ terminal tufts of green, bristly leaves.

What could be geekier than that? It’s a symmetrical binary tree, straight out of a computer science textbook. (Except that the textbook would turn the tree upside down.) Abstracting away all the shaggy biological details, a topological model of an idealized Joshua tree would look like this:

The same motif adorns the windows of a building at Duke University.

In this diagram I have taken the liberty of filling in the unseen, underground portions of the plant by assuming symmetry: I give the root system the same branching structure as the above-ground parts. When this figure is turned 90 degrees, it is known as the H curve; in this orientation I guess it must be the I curve.

Before going any further with this story, I have to admit that the graph-theoretical structure of Yucca brevifolia is not quite as precise and regular as I first thought it might be. Not all the trees are strictly binary. As the sun came up in the park I soon spotted some trifurcations. Later in the day I found even odder branching patterns.

So once again nature tries to implement an algorithm, and before long her mind begins to wander, producing doodles that are nowhere to be found in the specification. But that’s all right. My mind was wandering, too. As I trekked through the groves of Joshua trees, I kept reverting to thoughts of “toothpick trees.” These are structures I had learned about the day before from Neil J. A. Sloane, the sequencemeister of the Online Encyclopedia of Integer Sequences. I had run into Neil on the exhibit floor at the San Diego meeting, where the OEIS Foundation had a booth.

I sensed a connection between Joshua trees and toothpick trees. In the idealized H curve shown above, the branches added in each generation are a little smaller than their parents. The shrinkage factor is \(1/\sqrt{2}\), which I applied to both the length and the thickness of the branches. What happens if the branches don’t shrink? They begin colliding with one another after just three generations. That’s the situation in a toothpick tree. It is formed on essentially the same pattern as the H curve, but without the shrinkage factor; instead we adopt a rule that whenever a branch touches another branch, the colliding tip is “sterilized” and no new branches grow there.

Here is a more precise description from the paper by David Applegate, Omar E. Pol and Sloane that introduced the idea of toothpick trees:

We start with an infinite sheet of graph paper and an infinite supply of line segments of length 1, called “toothpicks.” At stage 1, we place a toothpick on the y-axis and centered at the origin. Each toothpick we place has two ends, and an end is said to be “exposed” if this point on the plane is neither the end nor the midpoint of any other toothpick.

At each subsequent stage, for every exposed toothpick end, we place a toothpick centered at that end and perpendicular to that toothpick. The toothpicks placed at odd-numbered stages are therefore all parallel to the y-axis, while those placed at even-numbered stages are parallel to the x-axis.

I have cobbled together a JavaScript-and-SVG program for assembling and disassembling toothpick trees up to stage n = 128. At this stage the number of toothpicks is 10,923, which is a lot of toothpicks if you buy them in boxes of 250. On the other hand, it’s a whole lot smaller than the 2¹²⁸–1 branches of the full binary tree.

The successive toothpick totals form sequence A139250 in Sloane’s OEIS. The notes accompanying that listing point out lots of interesting facts about the pattern and the process that generates it. If you run the animation, you can’t help noticing the distinctive behavior as n approaches each integer power of 2, or the repeating pattern in which a square block has a smaller square “ear” at each corner. And no toothpick after the initial one three crosses either the x or the y axis. (When the x or y coordinate is a power of 2, toothpicks from opposite sides meet at points along the axis, but they do not cross it.)

The notes also mention a conjecture, which I assume remains open:

Conjecture: Consider the rectangles in the sieve (including the squares). The area of each rectangle (A=b*c) and the edges (b and c) are powers of 2, but at least one of the edges (b or c) is <= 2.

The rectangles at issue in this conjecture are “open” rectangles, with no toothpicks or parts of toothpicks inside of them. I’ve become curious about more general squares and rectangles, defined as any axis-aligned quadrilateral whose perimeter is traced by an unbroken chain of toothpicks or half-toothpicks, regardless of what’s in the interior. Here are a few squares discovered in a small sample of the toothpick pattern:

The unit of distance in this compilation is half of a toothpick, since that’s the smallest square that can possibly appear. I have highlighted squares with side lengths of 1, 2, 3, 4, 6, 7 and 8 units. Is there a square of side length 5? How about 9 and 17? Looking for rectangles more generally rather than just squares, I enlisted the help of Ros. The black dots in the matrix at right represent all the rectangles we were able to find by hand and eye. (I have not yet written a program to search more systematically.) The red circles at 5-by-5 and 9-by-9 are vacancies that seem particularly intriguing. Do those squares exist anywhere in the toothpick tree? If not, is there some simple argument to explain why?

Joshua trees and toothpick trees, natural trees and mathematical trees: They are very different, but I’m fond of them both.

A day spent in the desert sun admiring the idiosyncrasies of Yucca brevifolia feels quite unlike a day spent coding H curves or toothpick trees in JavaScript, or poring over printouts searching for 5-by-5 squares. But I wouldn’t want to have to choose between those activities. And I’m particularly pleased when I can make a connection between them, however tenuous and fanciful.