= Two-sample exact period recovery
{title2=$\widehat r=N/\gcd(N,c_1,c_2)$}
Suppose a function has least period $r\mid N$ and distinct values on distinct period cosets. Two independent <Fourier samples> have the form $c_j=s_jN/r$ with uniform $s_j\in\mathbb Z_r$. The displayed candidate is $r/\gcd(r,s_1,s_2)$, so exact recovery occurs when no prime divisor of $r$ divides both residues. The <Chinese remainder theorem> gives probability $\prod_{\ell\mid r}(1-\ell^{-2})\ge1/\zeta(2)=6/\pi^2$, using the <Euler product>. Unlike a single-sample coprimality probability, this bound is uniformly greater than one half. A candidate-period test makes successful recovery heralded when such a test is available.
Back to article page
