Growth rates [in substitution systems]

The total number of elements of each color that occur at each step in a neighbor-independent substitution system can be found by forming the matrix m where m〚i, j〛 gives the number of elements of color j + 1 that appear in the block that replaces an element of color i + 1. For case (c) above, m = {{1, 1}, {1, 0}}. A list that gives the number of elements of each color at step t can then be found from init . MatrixPower[m, t], where init gives the initial number of elements of each color—{1, 0} for case (c) above. For large t, the total number of elements typically grows like λ^t, where λ is the largest eigenvalue of m; the relative numbers of elements of each color are given by the corresponding eigenvector. For case (c), λ is GoldenRatio, or (1 + √5)/2. There are exceptional cases where λ  1, so that the growth is not exponential. For the rule {0  {0, 1}, 1  {1}}, m = {{1, 1}, {0, 1}}, and the number of elements at step t starting with {0} is just t. For {0  {0, 1}, 1 {1, 2}, 2  {2}}, m = {{1, 1, 0}, {0, 1, 1}, {0, 0, 1}}, and the number of elements starting with {0} is (t² - t + 2)/2. For neighbor-independent rules, the growth for large t must follow an exponential or an integer power less than the number of possible colors. For neighbor-dependent rules, any form of growth can in principle be obtained.