The counting ability of weak formalisms (e.g. determining the number of 1’s in a string of length N) is of interest as a measure of their expressive power, and also resorts to complexity theoretic motivations : the more we can count the closer we get to real computing power. The question was investigated in several papers in complexity theory and in weak arithmetic a long time ago. In each case, the considered formalism (constant-depth circuits, MSO with addition or first-order bounded arithmetic) was shown to be able to count up to a polylogarithmic number. An essential part of the proofs is the construction of a 1–1 mapping from a small subset of {0,...,N - 1} into a small initial segment. In each case the expressibility of this mapping depends on some strong and non-constructive argument (group theoretic device or prime number theorem).

In this talk we will evocate these different methods and present a completely elementary (and constructive) approach to reprove uniformly all these results (based on an old paper with M. More and C. Lautemann). We will also review why some of these results cannot be extended.