  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 all initial configurations. The state complexity of a predicate is the
number of states of a smallest protocol that computes it. Previous work by
Blondin et al. has shown that the counting predicates $x \ge \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\log \eta)$ for leaderless protocols, and the inverse of a
non-elementary function for protocols with leaders.
