Effective simultaneous grid uprighting of paired ellipses

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$.

If $b\le 0$ and $z,\zeta \ge -1\mathrm{/}5$, put $c=\min (z,\zeta )$, $n=\max (1,\lfloor {\lambda }^c\mathrm{/}\sqrt{2}\rfloor )$ and use $B^n$. Its off-diagonals are $b+\sqrt{2}ne{\lambda }^{-z}$ and $\beta -\sqrt{2}nf{\lambda }^{-\zeta }$. Since $be\le -b^2$ and $\beta f\ge {\beta }^2$, expansion gives $S^{\mathrm{\prime }}\mathrm{/}S\le {\max }_{x\in \{z,\zeta \}}(1-\sqrt{2}n{\lambda }^{-x}{)}^2+(4\mathrm{/}15)n^2{\lambda }^{-2c}$. When the floor is positive, ${\lambda }^c\mathrm{/}(2\sqrt{2})\le n\le {\lambda }^c\mathrm{/}\sqrt{2}$, giving at most $(1-1\mathrm{/}(2\lambda ){)}^2+2\mathrm{/}15<9\mathrm{/}10$. Otherwise $n=1$ and ${\lambda }^{-x}\in [1\mathrm{/}(\sqrt{2}\lambda ),{\lambda }^{1\mathrm{/}5}]$. The absolute value at both endpoints is less than $5\mathrm{/}7$: use $1-1\mathrm{/}\lambda <3\mathrm{/}5$, $\sqrt{2}<10\mathrm{/}7$, and ${\lambda }^{1\mathrm{/}5}<6\mathrm{/}5$. The remaining term is below $(4\mathrm{/}15)(6\mathrm{/}5{)}^2=48\mathrm{/}125$, so $S^{\mathrm{\prime }}\mathrm{/}S<25\mathrm{/}49+48\mathrm{/}125<9\mathrm{/}10$.

These cases cover the normalized strip. If the central region fails, one coordinate exceeds $4\mathrm{/}5$: a coordinate below $-4\mathrm{/}5$ would, by $z+\zeta \ge 0$, force bias magnitude greater than one. When $b\ge 0$, either both coordinates are at least $3\mathrm{/}10$, or the smaller is at most $3\mathrm{/}10$ and a $K$ case applies. When $b\le 0$, a coordinate below $-1\mathrm{/}5$ forces the other below $4\mathrm{/}5$ by the bias strip, putting both in the central region. Undo the temporary shift as in step 3.1 and repeat. Each iteration reduces $S$ by $9\mathrm{/}10$, so after $O(\log H)$ iterations $S<15$, since initially $S\le 2H^2$. For a determinant-one ellipse, its area-to-box ratio is $\pi \mathrm{/}(4\sqrt{1+b^2})$: its area is $\pi$ and box half-widths are $\sqrt{d},\sqrt{a}$ when the matrix is $\left(\begin{array}{cc}a& b\\ b& d\end{array}\right)$. Thus the final ratios exceed $\pi \mathrm{/}16>1\mathrm{/}6$. The inverse cumulative map is the desired $G$, including translated centers.

To control integer parts, after every contraction balance the top-left coefficients $a,\alpha$ using a right action $L^r$ with ${\lambda }^{-2}\le (a\mathrm{/}\alpha ){\lambda }^{4r}\le {\lambda }^2$; this preserves skew. Let $T$ be the cumulative lattice map. Each column $v$ has some nonzero coordinate in $2^{-1\mathrm{/}2}\mathbb{Z}[\sqrt{2}]$, so $\mathrm{\parallel }v{\mathrm{\parallel }}^2\mathrm{\parallel }{v}^{\bullet }{\mathrm{\parallel }}^2\ge 1\mathrm{/}4$ by its nonzero rational norm, whose absolute value is at least $1\mathrm{/}2$. Hence $a\alpha \ge H^{-2}\mathrm{/}4$, and likewise $d\delta \ge H^{-2}\mathrm{/}4$. Since $(ad)(\alpha \delta )=(1+b^2)(1+{\beta }^2)\le (1+2H^2{)}^2$, both products are also at most $4H^2(1+2H^2{)}^2$. Balancing makes $a,\alpha$ individually $H^{O(1)}$ and bounded below by $H^{-O(1)}$; $d=(1+b^2)\mathrm{/}a$ and $\delta =(1+{\beta }^2)\mathrm{/}\alpha$ have the same bounds. The quadratic forms then bound the entries of $T,T^{\bullet }$ by $H^{O(1)}$. At each iteration the temporary shifts and powers in step 3.1 and step 4.1 and step 4.2 and step 4.3 and step 4.4 have exponents $O(\log H)$ and values $H^{O(1)}$ as well. Integer parts are therefore computable by binary search within integer bounds $H^{O(1)}$ in $O(\log H)$ comparisons each. Balancing does not alter any skew estimate or termination bound, proving the quantitative claims without a free floor oracle.