T-count guarantees for Clifford+T Rz synthesis

If $\epsilon \ge c_0$, the direct branch from [F2] returns a feasible zero-T Clifford, which is globally optimal by nonnegativity of T-count. Suppose instead $0<\epsilon <c_0$. Then [F1] gives a first solvable candidate in COMPLETE mode. Since the stream is ordered by exponent and the solver is complete, its exponent $k$ is the least exponent of any solvable candidate. By [F3], taking the smaller compiled count returns $f(k)$, the minimum across determinant-one feasible classes, because $f$ is nondecreasing. By [F2] this is the global minimum.

If $c_0\le \epsilon <1\mathrm{/}2$, the direct branch returns $m=0$, so no feasible solution has T-count below $m$ and the expected lower-count is zero; also $\mathbb{E}[m]=0\le \mathbb{E}[m^{\mathrm{\prime }\mathrm{\prime }}]$ whenever $m^{\mathrm{\prime }\mathrm{\prime }}$ is defined. Suppose $0<\epsilon <c_0$. For the bounded-factorization branch let $J$ be the first successful mandatory prime-attempt index, using preassigned fresh bit streams along the candidate sequence. For each enumerator/tie-choice framework, condition first on all its arithmetic data $\mathcal{D}$. By [F11], $\mathrm{Pr}(J>j\mid \mathcal{D})\le {\prod }_{i=1}^j(1-I_i\mathrm{/}2)$. Averaging over the arithmetic model [A1] gives $\mathrm{Pr}(J>j)\le {\prod }_{i=1}^j(1-p_i\mathrm{/}2)\le {\prod }_{i=1}^j(1-c\mathrm{/}(2(k_i+1)))$. This uses independence of the modelled indicators only; actual successful calls may be correlated after averaging over numerical inputs. The procedure succeeds no later than $J$. Apply the joint-failure version of [F7], with $c$ replaced by $c\mathrm{/}2$: $J$ is finite almost surely, $\mathbb{E}[J]=O(L)$, and $\mathbb{E}[{\log }_{2}J]=O(1+\log L)$. All constants are uniform in the iterator tie choices, so these bounds survive averaging over its coins.

By [F3], the returned count satisfies $m\le f(k_J)$. Every feasible class of count below $m$ therefore has exponent strictly below $k_J$, since its class minimum is $f(k)$ and $f$ is nondecreasing. By [F2] these classes cover all feasible solutions. Distinct classes have distinct candidates and occur before index $J$, so their number is at most $J-1$. Taking expectations proves the lower-count solution bound.

The model has infinitely many prime or zero/unit candidates almost surely. Indeed, for each integer $r\ge 1$, the growth bound [F4] implies that for every sufficiently large $m$, ${\sum }_{i=2^m}^{2^{m+1}-1}{p}_i\ge c{2}^m\mathrm{/}(k_2+2m+3)$. These block lower bounds imply ${\sum }_{i=r}^{\mathrm{\infty }}{p}_i=\mathrm{\infty }$. Independence in [A1] gives $\mathrm{Pr}(I_i=0\text{ for every }r\le i\le N)={\prod }_{i=r}^N(1-p_i)\le \exp (-{\sum }_{i=r}^N{p}_i)\to 0$. Thus with probability one good indices occur after every finite $r$, so there are infinitely many. By [F5], each candidate has $\xi ,{\xi }^{\bullet }\ge 0$. If $n=0$, then ${\xi }^{\bullet }\xi =0$ in the field $K$ gives $\xi =0$ or ${\xi }^{\bullet }=0$. The latter also implies $\xi =0$ by [F12], so the solver returns $t=0$. If $n=1$ or $n$ is prime, then $n>0$ makes both embeddings strictly positive; for prime $n$, [F5] gives $n\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}8)$, so [F6] makes the norm equation solvable. Distinct candidates give distinct $u$-classes, so the best and second-best feasible classes exist almost surely. Choose the best and second-best feasible classes, breaking equal-count ties by increasing exponent, and let their exponents be $k^{\mathrm{\prime }}$ and $k^{\mathrm{\prime }\mathrm{\prime }}$. Since their class counts are $f(k)$ and $f$ is nondecreasing, this choice has $k^{\mathrm{\prime }}\le k^{\mathrm{\prime }\mathrm{\prime }}$. The two classes are distinct candidates, so $k_2\le k^{\mathrm{\prime }\mathrm{\prime }}$. By [F3,F4], $m\le 2k_J\le 2k^{\mathrm{\prime }\mathrm{\prime }}+4\lceil {\log }_{2}J\rceil \le m^{\mathrm{\prime }\mathrm{\prime }}+2+4\lceil {\log }_{2}J\rceil \le m^{\mathrm{\prime }\mathrm{\prime }}+6+4{\log }_{2}J$. To check integrability of the benchmark, use the deterministic bound $K=\lceil {\log }_2(512\mathrm{/}{\epsilon }^2)\rceil \ge k_2$ from [F4], and let $H$ be the second index with $I_H=1$. If each of the blocks $1,\dots ,r$ and $r+1,\dots ,2r$ contains a good index, then $H\le 2r$. By [A1,F4] and the same failure-product bound, $\mathrm{Pr}(H>2r)\le 2\exp \text{\hspace{0.17em}⁣}(-\frac{cr}{K+2\lceil {\log }_2(2r)\rceil +1})\mathrm{.}$ The tail comparison in [F7] gives finite moments of $H$. The first two good indices give two feasible classes, so $m^{\mathrm{\prime }\mathrm{\prime }}\le 2k_H$ by [F3], and [F4] makes $m^{\mathrm{\prime }\mathrm{\prime }}$ integrable. Also $m\le 2k_J$ is integrable by step 1.2. Taking expectations of the pathwise inequality and applying step 1.2 now gives $\mathbb{E}[m]\le \mathbb{E}[m^{\mathrm{\prime }\mathrm{\prime }}]+O(1+\log L)$, which is the stated asymptotic bound.

If $c_0\le \epsilon <1\mathrm{/}2$, the direct branch takes constant arithmetic work, including one exact integer-part operation and reducing exponents modulo $8$. Suppose $0<\epsilon <c_0$. Write $C_j$ for the iterator work through its $j$th global candidate, with no norm calls interleaved. The exponent sequence $k_j$ depends only on the number of distinct candidates in each layer, so it is unchanged by the iterator's randomized tie order. By [F4,F8], for some fixed $D$, $\sqrt{\mathbb{E}[C_j^2]}\le C(j+1{)}^2(L+1+\log (j+1){)}^D$. The joint-failure estimate of step 1.2 and [F7] give the stopping tail uniformly for each enumerator/tie-choice framework in [A1], hence also after averaging over the independent iterator coins: $\mathrm{Pr}(J>j)\le \exp (-j\mathrm{/}(a+b\ln j))$, with $a=O(L)$ and fixed $b>0$. Cauchy--Schwarz, applied separately to each event $J=j$, therefore gives $\mathbb{E}[C_J]\le {\sum }_{j\ge 1}\sqrt{\mathbb{E}[C_j^2]}\sqrt{\mathrm{Pr}(J=j)}$. For completeness, the product bound follows by expanding the nonnegative expectation of $(X\mathrm{/}\sqrt{\mathbb{E}[X^2]}-Z\mathrm{/}\sqrt{\mathbb{E}[Z^2]}{)}^2$ with $X=C_j$ and $Z={\mathbf{1}}_{\{J=j\}}$; if either second moment vanishes its term is zero. This sum is polynomial in $L$. Indeed, for $j\ge a$ the tail proof of [F7] bounds its exponential factor by $\exp (-c_1\sqrt{j\mathrm{/}a})$; bound logarithms by powers of $j$ and compare the resulting polynomial-times-exponential sum with its integral, using $y=\sqrt{t\mathrm{/}a}$. The part $j<a$ is also polynomial. Thus no independence between iterator delay and $J$ is assumed.

In capped mode [F11,A2] bound all candidate work through $J$ by $J\mathrm{poly}(1+k_J)$, plus the successful exact compilation. In oracle mode take $J$ to be the first prime/zero/unit model index, which has the same tail and moment bounds and is solvable by [F6]. Then [F9] supplies the same bound in conditional expectation: condition on the preceding history before each call, and sum its uniform polynomial expected bound over the calls that are reached. Integer-factor oracle calls cost one operation; their factorization outputs have polynomial length by [F5]. The stopping bounds [F4,F7] make the expectation of these polynomial expressions finite and polynomial in $L$. By [F3,F10], successful exact compilation also has polynomial cost in $k_J+1$: its entry denominators are at most $k_J$ and squared-entry exponent at most $2k_J$, with only finitely many small cases. Combining this with step 2.3 proves the expected polynomial arithmetic runtime for the actual efficient implementations. It includes charged exact-real arithmetic and comparisons, but supplies no bit-time guarantee for unencoded real parameters.