  Population protocols are a model of computation in which an arbitrary number
of indistinguishable finite-state agents interact in pairs. The goal of the
agents is to decide by stable consensus whether their initial global
configuration satisfies a given property, specified as a predicate on the set
of configurations. The state complexity of a predicate is the number of states
of a smallest protocol that computes it. Previous work by Blondin \textit{et
al.} has shown that the counting predicates $x \geq \eta$ have state complexity
$\mathcal{O}(\log \eta)$ for leaderless protocols and $\mathcal{O}(\log \log
\eta)$ for protocols with leaders. We obtain the first non-trivial lower
bounds: the state complexity of $x \geq \eta$ is $\Omega(\log\log \eta)$ for
leaderless protocols, and the inverse of a non-elementary function for
protocols with leaders.
