  Population protocols are a model of distributed computation in which
finite-state agents interact randomly in pairs. A protocol decides for any
initial configuration whether it satisfies a fixed property, specified as a
predicate on the set of configurations. The state complexity of a predicate is
smallest number of states of any protocol deciding that predicate. For
threshold predicates of the form $x\ge k$, with $k$ constant, prior work has
shown that they have state complexity $\Theta(\log\log k)$ if the protocol is
extended with leaders. For ordinary protocols it is only known to be in
$\Omega(\log\log k)\cap \mathcal{O}(\log k)$. We close this remaining gap by
showing that it is $\Theta(\log\log k)$ as well, i.e. we construct protocols
with $\mathcal{O}(n)$ states deciding $x\ge k$ with $k\ge2^{2^n}$.
