Element-distinctness O(N^{2/3}) query bound

The total number of $r$-subsets is $\left(\genfrac{}{}{0px}{}{N}{r}\right)$. The number containing a fixed pair $\{a,b\}$ is $\left(\genfrac{}{}{0px}{}{N-2}{r-2}\right)$, so its uniform probability is $\frac{\left(\genfrac{}{}{0px}{}{N-2}{r-2}\right)}{\left(\genfrac{}{}{0px}{}{N}{r}\right)}=\frac{r(r-1)}{N(N-1)}\mathrm{.}$ Every subset containing this colliding pair is marked, so the marked stationary mass is at least this value.

Apply [F1] to the lazy walk in [F2]. Its stationary law is uniform and its absolute gap is the displayed $\delta$; the nonnegative spectrum rules out a negative-eigenvalue obstruction to the absolute gap. For any positive rational $q\le 1$, let $\mathrm{dyad}(q)=2^{-j}$ for the least integer $j\ge 0$ with $2^{-j}\le q$; exact rational comparisons compute it and give $q\mathrm{/}2\le \mathrm{dyad}(q)\le q$. Supply the dyadic lower gap bound ${\delta }_0=\mathrm{dyad}(\delta )$. The initial stored list requires one query for each of its $r$ values. Replacing one selected index by one unselected index erases the old stored value with one inverse value query and loads the new value with one forward value query. The marked check compares the already stored values, so it costs no additional value query. Explicitly, the basis permutation $\mathrm{\mid }S,d,b⟩\mapsto \mathrm{\mid }S,d,b\oplus c(d)⟩$, where $c(d)$ is the collision bit of the stored list, is a clean coherent check: it preserves the list, needs no value-oracle call, and is its own inverse. Tensoring identity on every other existing register gives exactly the check interface in [F3]; its fresh-flag Lüders readout and inverse therefore add zero value queries as well, with gates and readout resources separate. These are stored-vertex setup and elementary replacement costs. The coherent row construction [F4] separately supplies the stronger access inputs required by [F3], with stationary edge setup $S_0\le r+2$, common controlled-walk/inverse/row-reflection bound $U_0=8$, and $C=0$.

Put ${\epsilon }_{\ast }=r(r-1)\mathrm{/}[N(N-1)]$ and supply the dyadic lower marked-mass bound ${\epsilon }_0=\mathrm{dyad}({\epsilon }_{\ast })$. For $r\ge 2$ and $N\ge 4$, $r-1\ge r\mathrm{/}2$ and $N(N-1)\le N^2$, hence ${\epsilon }_{\ast }\ge r^2\mathrm{/}(2N^2)$ and ${\epsilon }_0\ge {\epsilon }_{\ast }\mathrm{/}2\ge r^2\mathrm{/}(4N^2)$. Also $r\le N\mathrm{/}2$ gives $\delta =N\mathrm{/}[2r(N-r)]\ge 1\mathrm{/}(2r)$, so ${\delta }_0\ge \delta \mathrm{/}2\ge 1\mathrm{/}(4r)$ by step 2.1. Since $r\le N\mathrm{/}2$, ${\epsilon }_{\ast }\le (N-2)\mathrm{/}(4(N-1))<1\mathrm{/}2$, so [F3] applies even if the actual marked mass is larger. Run the wrapper with the dyadic failure target $\rho =31\mathrm{/}32$. Since $19\mathrm{/}20\le 31\mathrm{/}32$, its cap is exactly $n_{\mathrm{o}\mathrm{u}\mathrm{t}}=1$, and [F3] gives success probability at least $1\mathrm{/}20$. Its two fresh stationary preparations use at most $2(r+2)$ value queries by [F4], while the recursive search uses $O\text{\hspace{0.17em}⁣}\left(\frac{1}{\sqrt{{\epsilon }_0}}\frac{8}{\sqrt{{\delta }_0}}\right)$. The total is therefore $2r+4+O\text{\hspace{0.17em}⁣}\left(\frac{N}{r}\sqrt{r}\right)=2r+O(N\mathrm{/}\sqrt{r})$, with the additive $4$ absorbed since $N\mathrm{/}\sqrt{r}\ge 1$. The measured set is marked; by [F2] it contains two indices with equal stored values, and scanning those $r$ stored values identifies such a pair without a new value-oracle query.

For $N\ge 8$, $N^{2\mathrm{/}3}\le N\mathrm{/}2$; for $4\le N\le 7$, the displayed clamp selects an admissible integer in $[2,\lfloor N\mathrm{/}2\rfloor ]$. The clamp differs from $N^{2\mathrm{/}3}$ by only fixed factors over this finite range and is $\mathrm{\Theta }(N^{2\mathrm{/}3})$ for all $N\ge 4$. Therefore both $r$ and $N\mathrm{/}\sqrt{r}$ are $O(N^{2\mathrm{/}3})$. If $N\le 3$, the definition specifies direct pairwise value comparison instead of a Johnson walk; querying each value once uses at most $N$ value queries.