What is known about the area of the symmetric Pythagorean tree?

Question

$\begingroup$

What is known about the area of the symmetric Pythagorean tree? (Closed unit square as base, area of enclosed triangles not included.) The problem in calculating the area is that squares start to overlap from the sixth iteration onwards.

Without much effort it can be computed that height is 4 and breadth is 6, so an upper bound for the area is 24. Wikipedia reports that lower and upper bounds can with some effort be tightened to 5 and 18, respectively. The accompanying Wikipedia talk page reports on numerical approximations (pixel counts) that end somewhere near 14. Other than that, no trace of a hint of an exact answer in the literature.

Seems like a simple high-school problem. On closer inspection I believe it is not, due to the problem of overlapping squares.

asked May 3, 2013 at 20:52

$\endgroup$

16

Answer 1

The area is the rational number 12823413011547414368862997525616691741041579688920794331363953564934456759066858494476606822552437442098640979 / 877512406035620068631903180662851572553488753575243048137500508983979170248733422547196905684808937723408093 (approximately equal to 14.6134).

Details of the calculation are here: https://penteract.github.io/pythagTree.html.

The idea is that the shape can be divided into 28 squares, the corners of each of which are overlapping scaled and rotated copies of other squares from among the 28. This means that a non-deterministic finite state automaton can, given an infinite sequence of corners describing a point within one of these squares, determine whether that point is in the Pythagoras tree (ignoring the measure zero set of points which have multiple describing sequences). This NFA can be converted into a DFA using the usual powerset construction. Since the area of the Pythagoras tree within a square is the sum of the area within each of the 4 corners of the square, this gives rise to system of linear equations (of the form $A_N=A_{N_{tl}}/4+A_{N_{tr}}/4+A_{N_{bl}}/4+A_{N_{br}}/4$ ) which make it possible to calculate the area of each square, hence the area of the whole tree. Few enough of the nodes in the DFA are reachable from starting points (corresponding to singleton sets) that this calculation is tractable.

You must log in to answer this question.