Relative approximate counting success guarantee

The rough loop starts at $L=2$ and doubles each round. By [F26] choose a natural $q>4N$. Induction gives $2^j\ge j+1$ for every natural $j$: it is equality at $j=0$, and $2^{j+1}=2^j+2^j\ge (j+1)+(j+1)\ge j+2$. Thus after at most $q$ rounds the scale $L=2^q>4N$ has been reached, so $L^2\ge 4N$; the other stopping condition can only make the loop stop earlier. By [F21]–[F22], $y\mathrm{\ne }0$ is exactly a nonzero raw estimate test.

Suppose $t>0$ and put $\theta =\arcsin \sqrt{t\mathrm{/}N}$. Let $m$ be the largest nonnegative index such that $2^j\theta \le 1\mathrm{/}5$ for every $1\le j\le m$; the condition is vacuous for $m=0$. This index is finite because $\theta >0$ and the powers of two are unbounded by [F26]. For each rough scale $L=2^j$ with $1\le j\le m$, one has $L\theta \le 1\mathrm{/}5$ and $L^2\le 1\mathrm{/}(25{\theta }^2)\le N\mathrm{/}25<4N$, because $\theta \ge \sin \theta =\sqrt{t\mathrm{/}N}\ge 1\mathrm{/}\sqrt{N}$. Thus cutoff cannot occur during these $m$ rounds.

The threshold $T=[20(22\mathrm{/}7{)}^2\mathrm{/}ϵ]L$ is a positive rational. By [F26] and the induction argument in step 1.1, some power of two exceeds $T$, so the doubling loop terminates; its first value $M\ge T$ is the least such power and satisfies $M<2T$. Since $L\ge 2$ and $ϵ\le 1$, $T>2$, so $M$ is even and at least $2$, as required by Count and the rounding lemma. Since $22\mathrm{/}7>\pi$, $M\ge 20{\pi }^{2}L\mathrm{/}ϵ$ and $M<40(22\mathrm{/}7{)}^{2}L\mathrm{/}ϵ$. The rounding step [F24] terminates and makes the integer output explicit; its bit work is covered by [F25].

For $0\le x\le 2\mathrm{/}5$, define $H(x)=\sin x-x\cos x$. By [F7], $H(0)=0$ and $H^{\mathrm{\prime }}(x)=x\sin x\ge 0$, so the mean value theorem gives $\sin x\ge x\cos x$. At each rough scale $L\theta \le 1\mathrm{/}5$, this and $\sin \theta \le \theta$ yield $P_0(L)\ge {\cos }^2(L\theta )$ by [F2]. Fresh runs make their zero events independent. If $m\ge 1$, then $\theta \le 1\mathrm{/}10$ and [F8] gives ${\prod }_{j=1}^m{\cos }^2(2^j\theta )=[\sin (2^{m+1}\theta )\mathrm{/}(2^{m+1}\sin \theta \cos \theta ){]}^2\ge {\cos }^2(2\mathrm{/}5)$, using $\sin x\ge x\cos x$, $\sin \theta \cos \theta \le \theta$, $2^{m+1}\theta \le 2\mathrm{/}5$, and the decrease of nonnegative cosine from [F7]. If $m=0$, the empty product is $1\ge {\cos }^2(2\mathrm{/}5)$.

On the event that the first $m$ rough labels are zero, the loop cannot terminate before rough scale $2^{m+1}$: none of scales $2^j$, $1\le j\le m$, triggers the cutoff by step 1.2, and the first $m$ labels are zero. By maximality of $m$, $2^{m+1}\theta >1\mathrm{/}5$, so $2^{m+1}>1\mathrm{/}(5\theta )$. The loop therefore terminates at some scale $L\ge 2^{m+1}>1\mathrm{/}(5\theta )$, whether by a nonzero label or by the cutoff. Thus [F1] gives $M\ge 20(22\mathrm{/}7{)}^{2}L\mathrm{/}ϵ>4{\pi }^2\mathrm{/}(ϵ\theta )$, in particular $M\ge 4$. Applying [F3], using $\sqrt{t(N-t)}=N\sin \theta \cos \theta$ and $\theta \le (\pi \mathrm{/}2)\sin \theta$, gives $\mathrm{\mid }\tilde{t}-t\mathrm{\mid }\le ϵt\mathrm{/}4+{ϵ}^{2}t\mathrm{/}64$. The trigonometric inequality follows from [F4] with $u=\theta \mathrm{/}\pi$.

Each Count call uses a fresh preparation; the algorithm uses only the supplied access capabilities in [F21]. It is a finite procedure with exact finite stopping tests and certified final output, but no success or query-cost bound follows from this definition alone.

Since $\cos (2\mathrm{/}5)\ge 1-(2\mathrm{/}5{)}^2\mathrm{/}2=23\mathrm{/}25$ by the alternating cosine series [F6], [F5] gives ${\cos }^2(2\mathrm{/}5)8\mathrm{/}{\pi }^2>(23\mathrm{/}25{)}^2(8\cdot 49\mathrm{/}484)>2\mathrm{/}3$, where the last comparison is $622104>605000$ after cross multiplication. The final Count is a fresh run, so conditionally on the rough outcomes it succeeds with probability at least $8\mathrm{/}{\pi }^2$; multiplying by the rough-event probability proves joint probability greater than $2\mathrm{/}3$.

The output integer differs from $\tilde{t}$ by at most $2\mathrm{/}3$ by [F1]. If $ϵt<1$, raw error plus rounding is at most $(ϵ\mathrm{/}4+{ϵ}^2\mathrm{/}64)t+2\mathrm{/}3<17\mathrm{/}64+2\mathrm{/}3<1$, so the integer equals $t$. If $ϵt\ge 1$, then $2\mathrm{/}3\le 2ϵt\mathrm{/}3$ and ${ϵ}^{2}t\le ϵt$, so total error is at most $(1\mathrm{/}4+1\mathrm{/}64+2\mathrm{/}3)ϵt=179ϵt\mathrm{/}192<ϵt$.

If $t=0$, every Count phase is exactly zero by [F2], so rough labels are zero and cutoff $L^2\ge 4N$ eventually terminates. The final Count is also exactly zero, and certified rounding returns zero. This proves the zero-count branch and completes the success guarantee.