Beyond the Static Barrier for Ordinary Dynamic Approximate Membership

Abstract

We prove a strict space separation between static and ordinary dynamic approximate membership at every fixed error rate. For each fixed $\epsilon \in (0,1)$, a capacity-$n$ ordinary dynamic filter over a universe of size $u$, with zero false negatives, pointwise false-positive probability at most $\epsilon$, arbitrary history dependence, a free public random tape, and at most $H$ bits of persistent state, satisfies \[ H\ge \bigl(\log_2(1/\varepsilon)+a_\varepsilon^{\rm c}\bigr)n-o(n), \] under only $u/n\to \infty$. The constant $a_{\epsilon }^{\mathrm{c}}$ is an explicit variational threshold obtained by preserving the dependence between the parent accepted mass and the successor reservoir. The structural step is a common-continuation transport lemma. A joint posterior KL bound gives a branch-specific survivor support; the same legal delete--insert word transports that support to one successor state, forcing an accepted reservoir. We then keep the parent outside mass $1-X$ in the conditional-entropy argument instead of replacing it by $1-\epsilon$. This yields a two-variable analytic envelope, with no selected thresholds, dyadic witnesses, or numerical assumptions.