Quantum weak-separation query bound

If the supplied boundary width is smaller than half its positive admissible upper bound, regard the same oracle as having that larger width. Its two assertions remain valid because outer bands enlarge and inward erosions shrink; the same is true for an exact zero-width oracle. Write $\epsilon >0$ for this working allowance, which still satisfies the displayed input bound. First query membership at $x$. IN implies $x\in B(K,\epsilon )\subseteq B(K,\eta )$, which is a permitted output. OUT implies $x\mathrm{\notin }B(K,-\epsilon )$, hence $x\mathrm{\notin }B(K,-\eta )$ since inward erosions decrease with their radius. For $n=1$, $K$ is an interval containing $[-r,r]$ and $\epsilon <r\mathrm{/}2$. A positive OUT point must be at or beyond the positive endpoint minus $\epsilon$; a negative one has the analogous property. Its outward signed normal therefore satisfies the separation contract with slack at most $\epsilon$. The point zero necessarily has an IN answer. This proves the scalar case with a single query.

Suppose $n\ge 2$ and OUT occurs. Rotate $x$ to $-\mathrm{\parallel }x\mathrm{\parallel }{e}_n$ and use the height function of [F1]. Set $L=2R\mathrm{/}r$, ${\rho }_0=99\rho \mathrm{/}100$, $r_1=r\eta \mathrm{/}(12\sqrt{n}R)$ and $\delta =\frac{\eta {\rho }_0{n}^{-9\mathrm{/}2}}{96\cdot {23}^4}{\left(\frac{r\eta }{R^2}\right)}^2\mathrm{.}$ Then $[-2r_1,2r_1{]}^{n-1}\subseteq B(0,r\mathrm{/}2)$ since $2\sqrt{n}{r}_1\le r\mathrm{/}6$. Moreover $\delta \le n{r}_{1}L\mathrm{/}{\rho }_0$, by substituting $r_1,L$, $r\le R$, $\eta \le R$ and ${\rho }_0\le 1\mathrm{/}3$. Thus the height and grid lemma hypotheses hold.

Substitution of the input bound shows $\epsilon <0.97r\delta \mathrm{/}(3R)$: squaring verifies ${58}^9>(300\cdot {23}^4{)}^2$, while the remaining factor is at most $288\mathrm{/}(300\cdot 0.99)<0.97$. The deterministic address perturbation in [F4] is at most $\epsilon \mathrm{/}1000$ and its height displacement at most $\delta \mathrm{/}1000$. Thus effective membership uncertainty is less than $0.98r\delta \mathrm{/}(3R)$. The lower height error is less than $0.98\delta$, and the upper one is at most $2(0.98)\delta \mathrm{/}3+\delta \mathrm{/}3<0.987\delta$ before the additional $\delta \mathrm{/}1000$ value rounding. Hence the implemented clean height-value oracle has uniform error below $\delta$. Binary search and its inverse use $O(1+\log (R\mathrm{/}\delta ))$ membership/inverse calls by [F1]. This explicit slack also permits the certified rotation/address rounding in [F4]; those are bit costs, not uncounted queries.

Apply [F2] to the transverse dimension $d=n-1$, using its finite shift and $M\ge 32$ grid. With failure probability at most $\rho$, it returns $g$ satisfying $h(y)\ge h(0)+⟨g,y⟩-(23n{)}^2\sqrt{\delta L\mathrm{/}({\rho }_0{r}_1)}\mathrm{\parallel }y\mathrm{\parallel }-2L\sqrt{n}{r}_1\mathrm{.}$ The parameter substitutions are exact: $2L\sqrt{n}{r}_1=\eta \mathrm{/}3$ and $(23n{)}^2\sqrt{\delta L\mathrm{/}({\rho }_0{r}_1)}=\eta \mathrm{/}(2R)$. No differentiability of $h$ or exact membership at boundary points is used.

The finite shift uses no membership query. There are $O(\log (n\mathrm{/}\rho ))$ phase/median runs by [F2], each using a height query and its inverse; step 2.1 supplies their logarithmic membership cost. Since $R\mathrm{/}\delta$ is a fixed constant times a product of powers of $n$, $1\mathrm{/}\rho$, $R\mathrm{/}r$ and $R\mathrm{/}\eta$, its logarithm is $O(\log ((n\mathrm{/}\rho )(R\mathrm{/}\eta )(R\mathrm{/}r)))$. Initial queries and the scalar branch are absorbed because the displayed logarithms are bounded below by positive constants. This proves the first bound, counting forward and inverse calls separately and then adding them.

The separator conversion [F1] therefore gives, on this event, a unit inward normal $s$ with $⟨s,z⟩\ge ⟨s,x⟩-5\eta \mathrm{/}6-2R\epsilon \mathrm{/}r$ on all of $K$. The input precision implies $2R\epsilon \mathrm{/}r<\eta \mathrm{/}100$, so the additional encoded direction/rotation slack $\eta \mathrm{/}100$ in [F4] still leaves error below $\eta$. Emit $G=-s$ in the original coordinates. This gives $⟨G,z⟩\le ⟨G,x⟩+\eta$ on $K$, in particular on its inward $\eta$-erosion, with the OUT assertion already justified in step 1.1. Together with the IN branch this is exactly [F3]. The rational-direction encoding in [F4] specifies an exact unit normal by normalization; its output approximation was charged in the displayed slack.

For optimization, [F5] makes at most $BT$ adaptive weak-separation calls at precision ${\eta }_{\ast }$ and per-call failure ${\rho }_{\ast }$. Each is implemented by the first part with the stated ${\epsilon }_{\ast }$; the conditional oracle guarantee is uniform over its input point and completed membership oracle, so the classical adaptive reduction applies. Its failure accounting and output guarantee are exactly those proved in [F5]. Now $BT=O(n\log (nR\mathrm{/}s)(1+\log (R\mathrm{/}\zeta )))$ and $s=r\zeta \mathrm{/}(128R)$, while $1\mathrm{/}{\eta }_{\ast }$ and $1\mathrm{/}{\rho }_{\ast }$ have only polynomial dependence on these radius/precision ratios, $n$, and $1\mathrm{/}\nu$. Multiplying by step 3.2 therefore gives the claimed $\tilde{O}(n)$ membership queries. This multiplication charges every call; it imports neither the stronger arithmetic bound from a cited cutting-plane paper nor a free centroid operation.