Clifford+T Exact and Approximate Synthesis

Reduce $a$ modulo $p$. If $p=2$, return its residue; if $a=0$, return zero. Otherwise [F1] rejects exactly the nonsquares by testing $a^{(p-1)\mathrm{/}2}=-1$. In the remaining case write $p-1=2^{s}q$ with $q$ odd and $s\ge 1$. Repeatedly sample $z$ uniformly from $1,\dots ,p-1$ until $z^{(p-1)\mathrm{/}2}=-1$. Uniform sampling is implemented by drawing $\lceil {\log }_{2}p\rceil$ bits and rejecting zero and integers at least $p$. Each draw is accepted with probability at least $1\mathrm{/}4$, and each accepted $z$ is a nonsquare with probability $1\mathrm{/}2$ by [F2]; thus this search has bounded expected trials and terminates almost surely.

Set $x=a^{(q+1)\mathrm{/}2}$, $t=a^q$, $c=z^q$ and $M=s$, all modulo $p$. Then $x^2=at$, $c$ has exact multiplicative order $2^M$, and $t^{2^{M-1}}=1$ by the tests in step 1.1. While $t\mathrm{\ne }1$, find the least $m\ge 1$ with $t^{2^m}=1$ by successive squaring; it satisfies $m<M$. Put $b=c^{2^{M-m-1}}$ and replace $(x,t,c,M)$ by $(xb,t{b}^2,b^2,m)$. The identity $x^2=at$ is preserved. The old $t$ has order exactly $2^m$, so $t^{2^{m-1}}=-1$: in a field, the only roots of $X^2-1$ are $1,-1$ by factorization. Likewise $b^2$ has order $2^m$ and its $2^{m-1}$-st power is $-1$. Therefore the new $t$ has order dividing $2^{m-1}$, while the new $c$ has order $2^m$. The invariants are maintained and $M$ strictly decreases. After at most $s$ iterations, $t=1$ and $x^2=a$. Return $x$.

Put $B=1+\lceil {\log }_{2}p\rceil$. Every modular integer has $O(B)$ bits. Schoolbook multiplication and division use $O(B^2)$ bit operations; binary repeated squaring computes a power with $O(B)$-bit exponent in $O(B)$ modular multiplications. These bounds follow directly by forming at most $B$ shifted rows for multiplication and eliminating at most $B$ quotient digits for division. Step 1.1 uses an expected bounded number of such powers. Each of the at most $B$ iterations in step 2.1 uses at most $O(B)$ modular multiplications to find $m$ and compute $b$. Its total cost is $O(B^4)$. Initial reduction has cost polynomial in the original length of $a$ and $p$. Thus the algorithm has the asserted expected bit bound; only the nonsquare search is randomized, and its outcome never changes the correctness of the final answer.

For $z\in D$, its definition gives $z=a\mathrm{/}{2}^r$ for some $a\in O$ and integer $r\ge 0$. Expand $a$ in the integral basis [F1]. Among all such exponents choose the least $r$; if $r>0$ and all four coefficients of $a$ were even, replacing $(a,r)$ by $(a\mathrm{/}2,r-1)$ would contradict minimality. This gives an encoding of the required form.

Suppose $a\mathrm{/}{2}^r=b\mathrm{/}{2}^s$ are two canonical encodings. If $r<s$, then $b=2^{s-r}a$, so every coefficient of $b$ is even, contrary to its canonical condition because $s>0$. If $s<r$, the same argument makes every coefficient of $a$ even. Hence $r=s$, and then $a=b$; uniqueness of the four coefficients follows from the basis property [F1]. The zero element is represented only by the all-zero numerator, and minimality forces its exponent to be $0$.

Multiplying $(\omega -{\omega }^3)(a+b\omega +c{\omega }^2+d{\omega }^3)$ and reducing every power ${\omega }^j$ with ${\omega }^4=-1$ gives $(b-d)+(a+c)\omega +(b+d){\omega }^2+(c-a){\omega }^3$. By [F1], this product is in $2O$ exactly when all four displayed coefficients are even, which is equivalent to $a+c$ and $b+d$ even, or $a\equiv c$ and $b\equiv d(\mathrm{m}\mathrm{o}\mathrm{d}2)$. This proves the first criterion.

Expanding $x\bar{x}$ with $\bar{\omega }=-{\omega }^3$ and reducing powers gives the stated $P+\sqrt{2}Q$. Write $A=a+c$ and $B=b+d$ modulo $2$. Then $P\equiv A+B$ and $Q\equiv AB(\mathrm{m}\mathrm{o}\mathrm{d}2)$. The pair $(A+B,AB)$ is $(0,0)$ exactly for $(A,B)=(0,0)$: the other three pairs give $(0,1)$, $(1,0)$, or $(1,0)$. Since $P+\sqrt{2}Q$ is in $2O$ exactly when its unique power-basis coefficients are all even, equivalently when $P,Q$ are both even, the norm is in $2O$ exactly when $A=B=0$, which by step 1.1 is exactly when $\sqrt{2}$ divides $x$.

Since $(\sqrt{2}{)}^{2r}=2^r$, multiplying $z$ by $(\sqrt{2}{)}^{2r}$ gives its canonical numerator in $O$. Hence the exponent set is nonempty.

Suppose $k=-m<0$ belongs to that set, so $z=(\sqrt{2}{)}^{m}y$ for some $y\in O$. Then the numerator $a=2^{r}z=(\sqrt{2}{)}^{m+2r}y=2^q(\sqrt{2}{)}^{ϵ}y$, where $q=\lfloor (m+2r)\mathrm{/}2\rfloor$ and $ϵ\in \{0,1\}$. Multiplication by $\sqrt{2}$ has integer coefficients in the power basis, so all coefficients of $a$ are divisible by $2^q$. Choose a nonzero coefficient $a_j$; its finite $2$-adic valuation bounds $q$ above, and therefore bounds $m$ above. Thus the negative exponents in the set are bounded below; nonnegative exponents already are.

A nonempty subset of $\mathbb{Z}$ bounded below has a least element. Hence the set of clearing exponents has a least integer; this does not assume that the least exponent is nonnegative.

Write $z=a\mathrm{/}{2}^r$ using [F1]. Since $2^r$ is real, $z^{†}z=(a^{†}a)\mathrm{/}{2}^{2r}$.

Substituting the exact norm formula from [F2] gives $z^{†}z=(P+\sqrt{2}Q)\mathrm{/}{2}^{2r}$. Both coefficients are dyadic rationals, so this element lies in $D_{+}=\mathbb{Z}[\sqrt{2},1\mathrm{/}2]$ and has the claimed form.

For nonzero $z$, write its canonical form $z=a\mathrm{/}{2}^r$ using [F1]. If $r>0$, then $a\bar{a}=2^{2r}$, so $2\mid a\bar{a}$ in $O$ and [F2] gives $a=\sqrt{2}{a}_1$ for some $a_1\in O$. Whenever $a_j\in O$ has $a_j{\bar{a}}_j=2^m$ with $m>0$, the same argument gives $a_j=\sqrt{2}{a}_{j+1}$ and $a_{j+1}{\bar{a}}_{j+1}=2^{m-1}$. Applying this for $m=2r,2r-1,\dots ,1$ yields $a=(\sqrt{2}{)}^{2r}{a}_{2r}=2^r{a}_{2r}$. All canonical coefficients of $a$ are then even, contradicting the minimality of $r$. Thus $r=0$ and $z\in O$.

Write $z=a+b\omega +c{\omega }^2+d{\omega }^3$ with integer coefficients. Direct multiplication gives $z\bar{z}=P+\sqrt{2}Q=1$, where $P=a^2+b^2+c^2+d^2$ and $Q=a(b-d)+c(b+d)$ by [F2]. The numbers $1$ and $\sqrt{2}$ are linearly independent over $\mathbb{Q}$: if $\sqrt{2}=m\mathrm{/}n$ in lowest terms, then $m^2=2n^2$ forces $m$ even and then $n$ even, a contradiction. Thus $P=1$ and $Q=0$. Four integer squares sum to $1$ only when exactly one coefficient is $1$ or $-1$ and the others are zero. Hence $z\in \{\pm 1,\pm \omega ,\pm {\omega }^2,\pm {\omega }^3\}=\{{\omega }^j:0\le j<8\}$.

For $x=a+b\sqrt{2}\in \mathbb{Q}(\sqrt{2})$ put $N_R(x)=\mathrm{\mid }{a}^2-2b^2\mathrm{\mid }$. For $z=A+B\omega$ with $A,B\in \mathbb{Q}(i)$ put $N_O(z)=\mathrm{\mid }{A}^2-i{B}^2{\mathrm{\mid }}^2=\mathrm{\mid }z{\mathrm{\mid }}^2\mathrm{\mid }{z}^{\bullet }{\mathrm{\mid }}^2$. These functions are multiplicative, positive on nonzero elements, and take positive integer values on nonzero elements of their respective rings: $A,B\in \mathbb{Z}[i]$ for $z\in O$, and $z{z}^{\bullet }=A^2-i{B}^2\in \mathbb{Z}[i]$. Integer norm one is equivalent to being a unit: the converse follows by multiplicativity, and the forward implication follows by taking the product of the other conjugates divided by the norm (with a sign in $R$). All coordinates of that inverse remain in the ring.

The real elements of $O$ are exactly $R$. Indeed, for $z=a_0+a_1\omega +a_{2}i+a_3{\omega }^3$, its imaginary part is $a_2+(a_1+a_3)\mathrm{/}\sqrt{2}$; irrationality of $\sqrt{2}$ makes this zero exactly when $a_2=0$ and $a_3=-a_1$. The real part is then $a_0+a_1\sqrt{2}$. A real unit of $O$ consequently is a unit of $R$, since its inverse is real too. Also ${\lambda }^{-1}=\sqrt{2}-1\in R$ and ${\lambda }^{\bullet }=-{\lambda }^{-1}$.

To divide in $R$, round the rational coefficients of a quotient to nearest integers. Its error $e=a+b\sqrt{2}$ has $\mathrm{\mid }a\mathrm{\mid },\mathrm{\mid }b\mathrm{\mid }\le 1\mathrm{/}2$, so $N_R(e)=\mathrm{\mid }{a}^2-2b^2\mathrm{\mid }\le 1\mathrm{/}2<1$. To divide in $O$, express a quotient as $A+B\omega$ and round $A,B$ to Gaussian integers. For the errors $C,D$, $\mathrm{\mid }C{\mathrm{\mid }}^2,\mathrm{\mid }D{\mathrm{\mid }}^2\le 1\mathrm{/}2$, whence $N_O(C+D\omega )=\mathrm{\mid }{C}^2-i{D}^2{\mathrm{\mid }}^2\le (\mathrm{\mid }C{\mathrm{\mid }}^2+\mathrm{\mid }D{\mathrm{\mid }}^2{)}^2\le 1$. If the last upper bound equals one, all four real coordinates of $C,D$ are $\pm 1\mathrm{/}2$. Then $C^2,D^2$ are purely imaginary of magnitude $1\mathrm{/}2$, so $C^2$ and $-i{D}^2$ are perpendicular and the actual norm is $1\mathrm{/}2$. Otherwise the displayed bound is already strict. Multiplicativity therefore gives a remainder of norm strictly below that of the divisor in both rings. This proves the Euclidean assertions, including ties in rounding.

If $u\in R$ is a unit, choose a sign and an integer power of $\lambda$ to make $v=\pm {\lambda }^{j}u$ lie in $[1,\lambda )$. Such a power exists because $\lambda >1$. Write $v=a+b\sqrt{2}$. Its signed field norm is $\pm 1$, so $v^{\bullet }=\pm 1\mathrm{/}v$. For norm $+1$, $a=(v+1\mathrm{/}v)\mathrm{/}2\in [1,\sqrt{2})$, hence $a=1$; the equation $a^2-2b^2=1$ forces $b=0$ and $v=1$. For norm $-1$, $a=(v-1\mathrm{/}v)\mathrm{/}2\in [0,1)$, hence $a=0$, incompatible with $-2b^2=-1$. This proves $u=\pm {\lambda }^m$. Its two embeddings are positive exactly when the sign is positive and $m$ is even. In this case ${\lambda }^{m\mathrm{/}2}$ is the required real unit square root. Enumerating integer powers until the exact coefficients agree recovers $m$ in finite time. Signs and comparisons of $a+b\sqrt{2}$ are decided by signs of the rational coefficients and, when necessary, comparing $a^2$ and $2b^2$.

Repeated division terminates because nonzero remainder norms strictly decrease through positive integers. Back substitution expresses the gcd as a linear combination. If an irreducible $p$ does not divide $a$, the gcd of $p,a$ is a unit, so multiplying a Bezout identity by $b$ shows that $p\mid ab$ implies $p\mid b$. Thus irreducibles are prime. A nonunit has a factorization into irreducibles by induction on its norm: a proper factorization has two factors of norm at least two, each of smaller norm. The prime-divisor property and cancellation give uniqueness up to ordering and units. Divisibility is decidable by computing the quotient in the field and checking its integral coordinates; two elements are associates exactly when their quotient has integral coordinates and norm one.

Here is an explicit finite factor search, which makes the existence proof algorithmic without a primality oracle for $O$. For a nonunit $\alpha \in O$ put $M=N_O(\alpha )\ge 2$ and enumerate all power-basis integer tuples with coefficients between $-(M+3)$ and $M+3$. Test whether such an element $d$ divides $\alpha$ and $1<N_O(d)<M$; any successful $d$ splits $\alpha$ into smaller-norm factors. If $\alpha$ is reducible, choose a nonunit proper divisor and multiply it by a power of the unit $\lambda$ so $1\le \mathrm{\mid }d\mathrm{\mid }<\lambda$. Its norm is unchanged and less than $M$, and $\mathrm{\mid }{d}^{\bullet }\mathrm{\mid }=\sqrt{N_O(d)}\mathrm{/}\mathrm{\mid }d\mathrm{\mid }\le \sqrt{M}$. Recovering power-basis coefficients from the two complex embeddings gives $\mathrm{\mid }{a}_0\mathrm{\mid },\mathrm{\mid }{a}_2\mathrm{\mid }\le (\mathrm{\mid }d\mathrm{\mid }+\mathrm{\mid }{d}^{\bullet }\mathrm{\mid })\mathrm{/}2$ and $\mathrm{\mid }{a}_1\mathrm{\mid },\mathrm{\mid }{a}_3\mathrm{\mid }\le (\mathrm{\mid }d\mathrm{\mid }+\mathrm{\mid }{d}^{\bullet }\mathrm{\mid })\mathrm{/}\sqrt{2}$. They are all below $\lambda +\sqrt{M}<M+3$, so the list contains this normalized proper divisor. Failure of the finite search therefore certifies irreducibility. Recursing on successful factors terminates by strict norm descent, and the residual norm-one elements supply the unit.

First suppose $I=[x_0,x_1]$, $J=[y_0,y_1]$ have positive lengths $\delta ,\mathrm{\Delta }$. Multiplication by the unit ${\lambda }^r$ on the first embedding and by $(-{\lambda }^{-1}{)}^r$ on the second is a bijection of the grid solutions. Choose the integer $r$ so the new first length lies in $[{\lambda }^{-1},1)$, reversing the second interval's endpoints when necessary. This is done by taking an integer part of a logarithm and checking the endpoint inequalities; $P$ is unchanged. Work henceforth with the rescaled intervals. Every solution $a+b\sqrt{2}$ satisfies $(x_0-y_1)\mathrm{/}(2\sqrt{2})\le b\le (x_1-y_0)\mathrm{/}(2\sqrt{2})$. Enumerate the integers in this interval. For each $b$, the interval $[x_0-b\sqrt{2},x_1-b\sqrt{2}]$ has length less than one, so its least integer is the only possible $a$; retain it only if both grid inequalities hold. No solution is duplicated or missed. The number of $b$ proposals is at most $1+(\delta +\mathrm{\Delta })\mathrm{/}(2\sqrt{2})=O(1+P)$ because ${\lambda }^{-1}\le \delta <1$ and $\mathrm{\Delta }=P\mathrm{/}\delta$. The integer endpoints and the affine formula for $b$ give random access to proposals.

Any pair of intervals whose length product is at least ${\lambda }^3$ contains a solution. Indeed, rescale as above, this time putting the first length in $[\lambda ,{\lambda }^2)$; the second length is then greater than or equal to $\lambda$. For the two interval centers $x,y$, round $(x+y)\mathrm{/}2$ and $(x-y)\mathrm{/}(2\sqrt{2})$ to their nearest integers $a,b$. Both errors $\mathrm{\mid }a+b\sqrt{2}-x\mathrm{\mid }$ and $\mathrm{\mid }a-b\sqrt{2}-y\mathrm{\mid }$ are at most $(1+\sqrt{2})\mathrm{/}2=\lambda \mathrm{/}2$, so the rounded point satisfies both constraints. If $P\ge 4{\lambda }^3$, put $q=\lfloor P\mathrm{/}(2{\lambda }^3)\rfloor$. Divide $I$ into $q$ equal cells and use the concentric closed half of each cell. Each resulting interval paired with $J$ has length product $P\mathrm{/}(2q)\ge {\lambda }^3$. Their disjointness gives $q$ distinct solutions, and $q\ge P\mathrm{/}(4{\lambda }^3)$. Consequently the proposal bound in step 1.1 is $O(N+1)$, including the case $P<4{\lambda }^3$.

If $I$ is a singleton and $J$ has length $\mathrm{\Delta }$, replace $I$ temporarily by the concentric interval of length $1\mathrm{/}(\mathrm{\Delta }+1)$ and test the original equality when filtering proposals. The product is at most one, so step 1.1 gives only constantly many proposals and contains all original solutions. Treat a singleton $J$ symmetrically; if both are singletons, enlarge both to length $1\mathrm{/}2$. Empty intervals need no work. For all cases, restore the inverse unit scaling on retained points. Thus the asserted finite list and counting estimates hold without an unbounded search for a witness or a free floor oracle.

Put $\lambda =1+\sqrt{2}$ and define $R=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& -1\\ 1& 1\end{array}\right)$, $A=\left(\begin{array}{cc}1& -2\\ 0& 1\end{array}\right)$, $B=\left(\begin{array}{cc}1& \sqrt{2}\\ 0& 1\end{array}\right)$, $K=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}-{\lambda }^{-1}& -1\\ \lambda & 1\end{array}\right)$, $X=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$, $Z=\mathrm{diag}(1,-1)$, and $L=\mathrm{diag}(\lambda ,{\lambda }^{-1})$. Express a determinant-one positive matrix as $D=\left(\begin{array}{cc}e{\lambda }^{-z}& b\\ b& e{\lambda }^z\end{array}\right)$, $e=\sqrt{1+b^2}$; use $\beta ,f,\zeta$ for $\mathrm{\Delta }$. Define skew $S=b^2+{\beta }^2$ and bias $\zeta -z$. For a matrix $T$, act on the pair by $(T^{\mathsf{T}}DT,(T^{\bullet }{)}^{\mathsf{T}}\mathrm{\Delta }{T}^{\bullet })$. In real/imaginary coordinates, with $s=1\mathrm{/}\sqrt{2}$, the additive group $O=\mathbb{Z}[\omega ]$ is $\{(a+sb,c+sd):a,b,c,d\in \mathbb{Z},b\equiv d(\mathrm{m}\mathrm{o}\mathrm{d}2)\}$. For integer matrices $P,Q$, the real matrix $M=P+sQ$ maps $O$ into $O$ exactly when the sum of the four entries of $P$ is even and all four entries of $Q$ have the same parity; applying $M$ to $(1,0),(0,1),(s,s),(-s,s)$ gives these conditions. In the order (sum parity of $P$, common parity of $Q$, determinant), each of $R,R^{-1}$ has (even, odd, $1$); each of $A,A^{-1}$ has (even, even, $1$); each of $B,B^{-1}$ has (even, even, $1$); each of $K,K^{-1}$ has (even, odd, $1$); $X$ has (even, even, $-1$); $Z$ has (even, even, $-1$); and each of $L,L^{-1}$ has (even, even, $1$). Thus these matrices preserve $O$ and have the stated determinants. Their entries lie in $\mathbb{Q}(\sqrt{2})$, so [F1] gives the conjugation identity.

The extra maps in the shifted-map factorization also preserve the lattice, including their inverses. With the criterion of step 1.1, $U=\mathrm{diag}(\lambda ,1)$, $U^{-1}$, $\lambda I$, and ${\lambda }^{-1}I$ each have even total integer part and even entries in their $s$-coefficient matrix; hence all four map $O$ into itself. Applying the same criterion to each inverse gives equality with $O$.

A skew-preserving temporary shift replaces $(z,\zeta ,b,\beta )$ by $(z-q,\zeta +q,b,(-1{)}^q\beta )$, where $q=\lfloor (1-(\zeta -z))\mathrm{/}2\rfloor$. It puts the bias in $[-1,1]$. This is conjugation by ${\sigma }^q=\mathrm{diag}({\lambda }^{q\mathrm{/}2},{\lambda }^{-q\mathrm{/}2})$ on $D$ and by ${\tau }^q=\mathrm{diag}({\lambda }^{-q\mathrm{/}2},(-1{)}^q{\lambda }^{q\mathrm{/}2})$ on $\mathrm{\Delta }$. If a lattice map $T$ reduces the shifted pair, then $T^{\mathrm{\prime }}={\sigma }^{q}T{\sigma }^q$ reduces the original skew by the same factor: shifting again preserves skew and gives precisely the action of $T^{\mathrm{\prime }}$, whose bullet is $(-\tau {)}^q{T}^{\bullet }{\tau }^q$. This $T^{\mathrm{\prime }}$ is still a lattice map. For $q=1$, its entries are $\left(\begin{array}{cc}\lambda t_{11}& t_{12}\\ t_{21}& {\lambda }^{-1}{t}_{22}\end{array}\right)$, the product ${\lambda }^{-1}I\mathrm{diag}(\lambda ,1)T\mathrm{diag}(\lambda ,1)$ of lattice maps; the same argument applies to inverse shifts. Finally apply $Z$ if necessary to make $\beta \ge 0$, and $X$ if necessary to make $z+\zeta \ge 0$. These preserve skew and the bias strip.

Assume $S\ge 15$ and the normalization of step 3.1. In the central region $\mathrm{\mid }z\mathrm{\mid },\mathrm{\mid }\zeta \mathrm{\mid }\le 4\mathrm{/}5$, use $R$. Its new off-diagonals are $e{\sinh }_{\lambda }z,f{\sinh }_{\lambda }\zeta$, where ${\sinh }_{\lambda }x=({\lambda }^x-{\lambda }^{-x})\mathrm{/}2$. Thus $S^{\mathrm{\prime }}\le S(17\mathrm{/}15){\sinh }_{\lambda }^2(4\mathrm{/}5)<(9\mathrm{/}10)S$. For an explicit strict bound, ${\lambda }^{4\mathrm{/}5}<21\mathrm{/}10$ follows from $\lambda <5\mathrm{/}2$ and $(5\mathrm{/}2{)}^4<(21\mathrm{/}10{)}^5$, so ${\sinh }_{\lambda }(4\mathrm{/}5)<341\mathrm{/}420$ and $(17\mathrm{/}15)(341\mathrm{/}420{)}^2<9\mathrm{/}10$.

If $b\ge 0$, $z\le 3\mathrm{/}10$, and $\zeta \ge 4\mathrm{/}5$, use $K$. Its off-diagonal squares sum to $(\sqrt{2}b-e{\cosh }_{\lambda }(z+1){)}^2+(\sqrt{2}\beta -f{\cosh }_{\lambda }(\zeta -1){)}^2$. Both arguments belong to $[-1\mathrm{/}5,13\mathrm{/}10]$. For $c={\cosh }_{\lambda }x=({\lambda }^x+{\lambda }^{-x})\mathrm{/}2$, the inequality $be\ge b^2$ gives $(\sqrt{2}b-ec{)}^2\le b^2(\sqrt{2}-c{)}^2+c^2$, and likewise for $\beta$. On this interval $1\le c<109\mathrm{/}60<2\sqrt{2}-1$, so $(\sqrt{2}-c{)}^2\le (\sqrt{2}-1{)}^2$. Here the rational bound follows from $\lambda <17\mathrm{/}7$, ${\lambda }^{1\mathrm{/}5}<6\mathrm{/}5$, ${\lambda }^{1\mathrm{/}10}<11\mathrm{/}10$, and ${\lambda }^{13\mathrm{/}10}>12\mathrm{/}5$: hence $c<((17\mathrm{/}7)(6\mathrm{/}5)(11\mathrm{/}10)+5\mathrm{/}12)\mathrm{/}2<109\mathrm{/}60$. All fractional-power comparisons follow by raising positive sides to powers five or ten. Therefore $S^{\mathrm{\prime }}\mathrm{/}S\le (\sqrt{2}-1{)}^2+(2\mathrm{/}15)(109\mathrm{/}60{)}^2<9\mathrm{/}10$. For $z\ge 4\mathrm{/}5$, $\zeta \le 3\mathrm{/}10$, use $K^{\bullet }$ and exchange the two matrices.

If $b\ge 0$ and $z,\zeta \ge 3\mathrm{/}10$, put $c=\min (z,\zeta )$, $n=\max (1,\lfloor {\lambda }^c\mathrm{/}2\rfloor )$ and use $A^n$. The new off-diagonals are $b-2ne{\lambda }^{-z}$ and $\beta -2nf{\lambda }^{-\zeta }$. Expanding their squares and using $be\ge b^2$, $\beta f\ge {\beta }^2$ gives $S^{\mathrm{\prime }}\mathrm{/}S\le {\max }_{x\in \{z,\zeta \}}(1-2n{\lambda }^{-x}{)}^2+(8\mathrm{/}15)n^2{\lambda }^{-2c}$. If $\lfloor {\lambda }^c\mathrm{/}2\rfloor \ge 1$, then ${\lambda }^c\mathrm{/}4\le n\le {\lambda }^c\mathrm{/}2$ and $c\le z,\zeta \le c+1$; the displayed bound is at most $(1-1\mathrm{/}(2\lambda ){)}^2+2\mathrm{/}15<9\mathrm{/}10$. Otherwise $n=1$, ${\lambda }^c<2$, and the two arguments ${\lambda }^{-x}$ lie in $[1\mathrm{/}(2\lambda ),{\lambda }^{-3\mathrm{/}10}]$. The quadratic's maximum is at the left endpoint: ${\lambda }^{3\mathrm{/}10}>13\mathrm{/}10$ and $\lambda >12\mathrm{/}5$ verify the endpoint comparison. The bound is then at most $(1-1\mathrm{/}\lambda {)}^2+(8\mathrm{/}15){\lambda }^{-3\mathrm{/}5}<(3\mathrm{/}5{)}^2+8\mathrm{/}15<9\mathrm{/}10$.