__Preprint:__

**
Samuel R. Buss,
Leszek Aleksander Kołodziejczyk, and Neil Thapen
"Fragments of Approximate Counting"
Journal of Symbolic Logic 49 (2014) 496-525.
**

**
Download manuscript: PDF.
**

**Abstract:**
We study the long-standing open problem of giving
$\forall \Sigma^b_1$ separations for
fragments of bounded arithmetic in the relativized setting.
Rather than considering the usual fragments defined
by the amount of induction they allow,
we study Jerabek's theories for approximate counting
and their subtheories.
We show that the $\forall \Sigma^b_1$ Herbrandized
ordering principle is unprovable in a fragment
of bounded arithmetic that includes the injective weak
pigeonhole principle for polynomial time functions,
and also in a fragment that includes the surjective weak pigeonhole principle
for $FP^{NP}$ functions.
We further give new propositional translations,
in terms of random resolution refutations,
for the consequences of $T^1_2$ augmented with
the surjective weak pigeonhole principle
for polynomial time functions.