Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.48.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
HTML articles powered by AMS MathViewer

by Samuel R. Buss, Leszek Aleksander Kołodziejczyk and Konrad Zdanowski PDF
Trans. Amer. Math. Soc. 367 (2015), 7517-7563 Request permission


Jeřábek introduced fragments of bounded arithmetic which are axiomatized with weak surjective pigeonhole principles and support a robust notion of approximate counting. We extend these fragments to accommodate modular counting quantifiers. These theories can formalize and prove the relativized versions of Toda’s theorem on the collapse of the polynomial hierarchy with modular counting. We introduce a version of the Paris-Wilkie translation for converting formulas and proofs of bounded arithmetic with modular counting quantifiers into constant depth propositional logic with modular counting gates. We also define Paris-Wilkie translations to Nullstellensatz and polynomial calculus refutations. As an application, we prove that constant depth propositional proofs that use connectives AND, OR, and mod p gates, for $p$ a prime, can be translated, with quasipolynomial increase in size, into propositional proofs containing only propositional formulas of depth three in which the top level is Boolean, the middle level consists of mod p gates, and the bottom level subformulas are small conjunctions. These results are improved to depth two by using refutations from the weak surjective pigeonhole principles.
Similar Articles
Additional Information
  • Samuel R. Buss
  • Affiliation: Department of Mathematics, University of California, San Diego, La Jolla, California 92093-0112
  • Email:
  • Leszek Aleksander Kołodziejczyk
  • Affiliation: Institute of Mathematics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland
  • Email:
  • Konrad Zdanowski
  • Affiliation: Faculty of Mathematics and Natural Sciences, Cardinal Stefan Wyszyński University, Wóycickiego 1/3, 01-938 Warszawa, Poland
  • Email:
  • Received by editor(s): September 1, 2012
  • Received by editor(s) in revised form: June 21, 2013
  • Published electronically: February 26, 2015
  • Additional Notes: The first author was supported in part by NSF grants DMS-1101228 and CCR-1213151. In the preliminary stages of this work, the second and third authors were supported by grant no. N N201 382234 of the Polish Ministry of Science and Higher Education. Most of this work was carried out while the second author was visiting the University of California, San Diego, supported by the Polish Ministry of Science and Higher Education programme “Mobilność Plus” with additional support from a grant from the Simons Foundation (#208717 to Sam Buss).
  • © Copyright 2015 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: Trans. Amer. Math. Soc. 367 (2015), 7517-7563
  • MSC (2010): Primary 03F20, 03F30, 03B05, 68Q15
  • DOI:
  • MathSciNet review: 3391892