TripleGrid Refinement

$ \def \half {\frac{1}{2}} \def \hieruit {\quad \Longrightarrow \quad} \def \slechts {\quad \Longleftrightarrow \quad} $ The end result of the preceding paragraph is: $$ y_{k+1} (y_{k+1} - 3)^2 = y_k \slechts \cos(3\phi_{k+1}) = \cos(\phi_k) $$ This gives us a very simple algorithm, which is entirely in terms of angles: $$ 3\phi_{k+1} = \left\{\;\phi_k\;,\;2\pi-\phi_k\;,\;2\pi+\phi_k\;\right\} $$ $$ \phi_{k+1} = \left\{\; \frac{\phi_k}{3} \;,\; \frac{2\pi-\phi_k}{3} \;,\; \frac{2\pi+\phi_k}{3} \;\right\} $$ Now we will start with the value that is certainly dangerous, namely $y_0 = 3$. Because that value will give rise to a division by zero during the Gaussian elimination process. Then we have: $$ \cos(\phi_0) = \half y_0 - 1 = \half \hieruit \phi_0 = \frac{\pi}{3} $$ The next step is: $$ \phi_1 = \left\{ \; \frac{\pi}{9} \; , \; \frac{2\pi}{3} - \frac{\pi}{9} \; , \; \frac{2\pi}{3} + \frac{\pi}{9} \; \right\} = \pi \left\{\; \frac{1}{9} \;,\; \frac{5}{9} \;,\; \frac{7}{9} \;\right\} $$ Add to this the initial value $\pi/3$ , then we have in total for the dangerous values so far: $$ \phi_0 \cup \phi_1 = \pi\left\{\; \frac{1}{9} \;,\; \frac{3}{9} \;,\; \frac{5}{9} \;,\; \frac{7}{9} \;\right\} $$ Each of the $\pi(1/9,5/9,7/9)$ may serve as an input for another sequence of solutions of our cubic. In order to bring order in the chaos, an article was posted in 'sci.math'. And Mike Guy offered a complete solution: It's easier to see when you deal in integers $x$. $$ \phi_k = \frac{\pi\,x_{k+1}}{3^{k+1}} \quad \mbox{where:} \quad x_{k+1} = \left\{\; x_k \;,\; 2.3^k-x_k \;,\; 2.3^k+x_k \;\right\} $$ Start with $x_1 = 1$, then we find for the first iterations (sorted computer output):

 1
 1 5 7
 1 5 7 11 13 17 19 23 25
 1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79

Quoted from his article. There are $3^k$ elements of the array; they are all distinct, odd and non multiples of 3, and are all $< 3^{k+1}$. But if we add the previous iterates to the set, each multiplied with a proper factor $3^k$, then we have:

 1
 1 3 5 7
 1 3 5 7 9 11 13 15 17 19 21 23 25

And their number is: $$ 3^0 + 3^1 + 3^2 + ... + 3^k = \frac{3^{k+1}-1}{3-1} $$ Which is precisely the number of odd integers between $0$ and $3^{k+1}$. Thus, indeed, the cumulative distribution of dangerous angles is given by: $$ \bigcup_{i=0}^{k} \phi_i = \frac{\pi\,x_{k+1}}{3^{k+1}} \quad \mbox{where:} \quad x_{k+1} = \left\{ \mbox{all odd numbers between 0 and } 3^{k+1} \right\} $$ The different iterates can still be distinguished, though: determine the maximum power $k$ in $3^k$ by which an odd number is divisible. For example, in the set $\{1,3,5,7,9,11,13,15,17,19,21,23,25\}$, the subset $\{1,5,7,11,13,17,19,23,25\}$ belongs to iteration 3, the subset $\{3,15,21\}$ belongs to iteration 2, the subset $\{9\}$ belongs to iteration 1. In general, with the $n$-th iteration, numbers which are divisble by $3^{n-k}$ belong to the $k$-th iteration.
A slightly different setup is to start with the dangerous value $y_0 = 0$ and the corresponding angle: $$ \cos(\phi_0)=\half y_0-1 = -1 \hieruit \phi_0=\pi $$ Herewith the first iteration becomes: $$ \phi_1 = \left\{ \; \frac{\pi}{3} \; , \; \frac{2\pi}{3} - \frac{\pi}{3} \; , \; \frac{2\pi}{3} + \frac{\pi}{3} \; \right\} = \pi \left\{\; \frac{1}{3} \;,\; \frac{3}{3} \;\right\} $$ Instead of the zero'th. And the second iteration becomes: $$ \phi_2 = \left\{ \; \frac{\pi}{9} \; , \; \frac{2\pi}{3} - \frac{\pi}{9} \; , \; \frac{2\pi}{3} + \frac{\pi}{9} \; , \; \frac{\pi}{3} \; , \; \pi \; \right\} = \pi \left\{\; \frac{1}{9} \;,\; \frac{3}{9} \;,\; \frac{5}{9} \; , \; \frac{7}{9} \;,\; \frac{9}{9} \;\right\} $$ Instead of the first. And so on and so forth. Herewith we find all odd fractions in one sweep, up and including a last one, which is equal to $3^n/3^n = 1$ .
So far so good for the Dangerous domain with {\em TripleGrid Refinement}. Let the iterand $y_k$ be in the Safe domain, meaning that $y_k > 4$. Then it is obvious that, with TripleGrid Coarsening, the iterand $y_{k+1} = y_k(y_k-3)^2$ will again be greater than 4 and hence in the Safe domain. But is the reverse also true? Let $y_k > 4$ and solve for $y_{k+1}$ in: $$ y_{k+1}(y_{k+1} - 3)^2 = y_k $$ Can we be certain then that $y_{k+1} > 4$ as well? Yes we can. The discriminant of this cubic, as we have seen already, is: $D = 27.y_k(4-y_k)$ . It is negative for $y_k > 4$, meaning that the corresponding cubic has two complex conjugate and one real solution. In our case, the real solution is the one that really counts. It is found by solving for the corresponding hyperbolic angle $3p_{k+1} = p_k$ and then find $\; y_{k+1} = 2 + 2 \cosh(p_{k+1})$ , which is definitely greater than $4$.