The second-step complexity conjecture for multivariable Chebyshev subdivision

Let $n$ be the dimension and $d$ the degree. Consider a system of $n$ degree-$d$ Chebyshev polynomials in $n$ variables, and suppose that $d$ is sufficiently large. Second-step complexity conjecture. The cost of subdivision is greatest on the second step, whose complexity is $\sqrt{2}^{n-1}$ times that of the first step. The complexity then decreases at an increasing rate, becoming $50\%$ cheaper at each step in the limit; consequently, the arithmetic complexity of the entire algorithm is

$$O(nd^{n+1}\sqrt{2}^{n-1}).$$

This conjecture is motivated by the predicted degree decrease and is supported by the numerical complexity data in the paper. It describes the expected dominant cost in the subdivision algorithm for sufficiently large degrees.