arXiv:2609.17650v3 Announce Type: replace-cross Abstract: The Binary Tree Mechanism is a standard algorithm for differentially private continual counting, but its complete asymptotic optimality under differential privacy has remained unresolved since its introduction. We resolve this question. For $0 \leq \varepsilon \leq 1$, we prove asymptotically tight lower bounds for $\ell_\infty$, mean squared, and maximum per-coordinate expected squared error simultaneously under all regimes of $0 \leq \delta \leq 1/4$. These bounds hold for arbitrary mechanisms, even when the entire stream is available in advance. Our lower bounds match the (blocked) Binary Tree Mechanism instantiated with the best of Laplace or Gaussian noise, establishing its asymptotic optimality. Our proof uses a single hard distribution where elements are ``tagged'' as potentially being the target flipped element via a score evaluated down a tree. A simple modification of the score allows the same framework to establish tight lower bounds for all three error measures.