Complete scaled-grid enumeration with expected polynomial prefix cost

The ring $O=\mathbb{Z}[\omega ]$ has exactly four residue classes modulo $\sqrt{2}O$, represented by $0,1,\omega ,1+\omega$. Indeed $\sqrt{2}\omega =1+i$ and $\sqrt{2}=\omega -{\omega }^3$ imply $i\equiv 1$, ${\omega }^3\equiv \omega$, and $2\equiv 0$. Conversely the coefficient map $a_0+a_1\omega +a_2{\omega }^2+a_3{\omega }^3\mapsto (a_0+a_2,a_1+a_3)<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>2$ annihilates every multiple of $\sqrt{2}$: multiplying by $\sqrt{2}=\omega -{\omega }^3$ gives even sums in both coordinates. Thus those four residues are distinct and exhaustive. Consequently for $k\ge 1$ the three chosen affine subproblems describe precisely the elements of least exponent $k$. For $k=0$, the algorithm scans all $81$ coefficient tuples in $\{-1,0,1{\}}^4$; [F3] bounds every nonzero grid candidate in this layer by that box, and zero fails the cap because $1-{\epsilon }^2\mathrm{/}2>0$. The two further cosets $\mathbb{Z}[\sqrt{2}]+i\mathbb{Z}[\sqrt{2}]$ and its translate by $\omega$ partition $O$: expand a power-basis element's real and imaginary parts and separate the parity of $a_1+a_3$. Thus all affine subproblems are disjoint. The lattice bijection [F2] and the exact filters preserve every solution, while the emitted set suppresses revisits. The exhaustive background scan makes every finite layer terminate for every sequence of random bits.

The cap is sandwiched between $E$ and its concentric $1\mathrm{/}8$-dilate. In coordinates $u=xw+yiw$, cap points have $1-h\le x\le 1$ and $y^2\le 2h$, so $(x-(1-h\mathrm{/}2){)}^2\mathrm{/}{h}^2+y^2\mathrm{/}(4h)\le 1\mathrm{/}4+1\mathrm{/}2<1$. Conversely the $1\mathrm{/}8$-ellipse lies in $\mathrm{\mid }x-(1-h\mathrm{/}2)\mathrm{\mid }\le h\mathrm{/}8$, $\mathrm{\mid }y\mathrm{\mid }\le \sqrt{h}\mathrm{/}4$, hence $x\ge 1-h$ and $x^2+y^2\le (1-3h\mathrm{/}8{)}^2+h\mathrm{/}16<1$ for $0<h<1\mathrm{/}8$. The normalized outer ellipse eigenvalues are $2\mathrm{/}\sqrt{h}$ and $\sqrt{h}\mathrm{/}2$, within $[H^{-1},H]$ for $H=4\mathrm{/}\epsilon$; the disk matrix is the identity. Therefore [F2] applies with $\log H=O(L)$. For a final normalized ellipse matrix $\left(\begin{array}{cc}a& b\\ b& d\end{array}\right)$ with $b^2\le 15$, its centered bounding box has half-widths $\sqrt{d},\sqrt{a}$. At its box scaled by $1\mathrm{/}8$, the quadratic form is at most $2(ad+\mathrm{\mid }b\mathrm{\mid }\sqrt{ad})\mathrm{/}64\le 1$, since $ad=1+b^2\le 16$. Each transformed cap therefore contains its outer ellipse's bounding box scaled concentrically by $1\mathrm{/}64$, and the same weaker bound holds for the transformed disk. Affine shifts, negative scalar dilations, and coset translations preserve these inclusions.

At $k=0$ the direct coefficient scan has at most $81$ proposals, hence $M=O(N+1)$ for the number $N$ of layer solutions. For $k\ge 1$, consider one of the at most six subproblems. If $P_x,P_y\ge T$, the two inner axis rectangles from step 1.2 supply independent coordinate grid problems with length products $P_x\mathrm{/}{64}^2$ and $P_y\mathrm{/}{64}^2$. Both exceed $4{\lambda }^3$, so [F1] gives at least $c{P}_x$ and $c{P}_y$ solutions, with a fixed $c>0$. Their Cartesian product lies inside both true constraints, giving $N_{\mathrm{s}\mathrm{u}\mathrm{b}}\ge c^2{P}_x{P}_y$. The two outer one-dimensional proposal lengths are $O(P_x+1)$ and $O(P_y+1)$, so their product is $O(N_{\mathrm{s}\mathrm{u}\mathrm{b}})$. If one coordinate product is below $T$, its entire proposal list and filtered coordinate list have bounded length by [F1]. Each remaining exact slice gives $O(N_x+1)$ proposals by the same result, including singleton slices. Summing over the constantly many coordinate solutions gives $O(N_{\mathrm{s}\mathrm{u}\mathrm{b}}+1)$ proposals. Combining the at most six disjoint subproblems proves $M=O(N+1)$. In particular an empty layer has only constantly many proposals; no exponentially large lower-denominator list is generated.

The bound [F2] on $G$ and the affine scalings $2^{k\mathrm{/}2}$ bounds all outer centers and widths above by $\exp (O(k+L))$. A nonzero outer width is bounded below by $\exp (-O(k+L))$, by the ellipse eigenvalue bounds and $\det G=\pm 1$. Thus the integer parts in outer one-dimensional preprocessing cost $O(k+L)$ comparisons each. There are only constantly many exact slice intervals in the small-coordinate branch. A positive slice can have arbitrarily small width, so the algorithm pads it before the [F1] normalization: replace a slice width $\delta$ smaller than $1\mathrm{/}(\mathrm{\Delta }+1)$ by that value, keeping its center and filtering the original slice. Its product is at most one and it creates constantly many proposals. Otherwise $\delta \ge 1\mathrm{/}(\mathrm{\Delta }+1)$, so both positive widths used for normalization are at least $\exp (-O(k+L))$, since $\mathrm{\Delta }$ is bounded by the outer width. The same padding handles singleton slices, and an empty slice is skipped. In either branch the [F1] unit-rescaling exponents are $O(k+L)$, all floor operands have magnitude $\exp (O(k+L))$, and the earlier $O(N_x+1)$ bound is retained. Root and line-intersection calculations use boundedly many source arithmetic operations; sign decisions are charged exact comparisons. Finally $M=O(N+1)$ and [F3] give $\log (M+1)=O(k+1)$, so each random proposal attempt uses $O(k+1)$ random bits and is accepted with probability at least $1\mathrm{/}2$. A balanced comparison tree on exact coefficient tuples handles the emitted set in $O(\log (N+2))=O(k+1)$ comparisons per visit. Thus each proposal visit and all layer preprocessing cost $\mathrm{poly}(k+L)$ in expectation, with polynomial moments.

Every actual solution occupies exactly one proposal index. For $N\ge 1$, after $s<N$ distinct solutions have been drawn, an independent random attempt produces a new solution with probability at least $(N-s)\mathrm{/}(2M)$. Ignoring the background scan can only delay obtaining $j$ solutions. The expected number of random draws to obtain them is at most ${\sum }_{s<j}2M\mathrm{/}(N-s)\le 2C(N+1){\sum }_{s<j}1\mathrm{/}(N-s)\le 4Cj{\sum }_{t=1}^{j}1\mathrm{/}t$, since $N\mathrm{/}(N-s)\le j\mathrm{/}(j-s)$ for $N\ge j$. This is $O(j(1+\log j))$. Moreover each waiting time is dominated by a geometric variable with success probability $1\mathrm{/}(4C(s+1))$, whose $r$th moment is $O_r((s+1{)}^r)$: sum its geometric tail, or bound the sum by the integral of $r{x}^{r-1}\exp (-x\mathrm{/}(4C(s+1)))$. The inequality $({\sum }_{s<j}{x}_s{)}^r\le j^{r-1}{\sum }_{s<j}{x}_s^r$ gives the stated $O_r(j^{2r})$ draw-moment bound. Each random draw adds only one background visit. Independently, after at most $M$ such pairs the deterministic scan ends the layer, bounding complete-layer work by $O((N+1)\mathrm{poly}(k+L))$. Combining these estimates with step 3.1 proves all complexity claims. They control prefixes as well as complete output sizes, so they do not hide a whole-layer precomputation before the first candidate.