One-dimensional quadratic grid enumeration and counting

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.