{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:19:08Z","timestamp":1772119148978,"version":"3.50.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,7,22]],"date-time":"2024-07-22T00:00:00Z","timestamp":1721606400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,22]],"date-time":"2024-07-22T00:00:00Z","timestamp":1721606400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004721","name":"The University of Tokyo","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004721","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Arch. Math. Logic"],"published-print":{"date-parts":[[2025,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We formalize various counting principles and compare their strengths over\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$V^{0}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:msup>\n                            <mml:mi>V<\/mml:mi>\n                            <mml:mn>0<\/mml:mn>\n                          <\/mml:msup>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . In particular, we conjecture the following mutual independence between:\n                    <jats:list list-type=\"bullet\">\n                      <jats:list-item>\n                        <jats:p>a uniform version of modular counting principles and the pigeonhole principle for injections,<\/jats:p>\n                      <\/jats:list-item>\n                      <jats:list-item>\n                        <jats:p>\n                          a version of the oddtown theorem and modular counting principles of modulus\n                          <jats:italic>p<\/jats:italic>\n                          , where\n                          <jats:italic>p<\/jats:italic>\n                          is any natural number which is not a power of 2,\n                        <\/jats:p>\n                      <\/jats:list-item>\n                      <jats:list-item>\n                        <jats:p>and a version of Fisher\u2019s inequality and modular counting principles.<\/jats:p>\n                      <\/jats:list-item>\n                    <\/jats:list>\n                    Then, we give sufficient conditions to prove them. We give a variation of the notion of\n                    <jats:italic>PHP<\/jats:italic>\n                    -tree and\n                    <jats:italic>k<\/jats:italic>\n                    -evaluation to show that any Frege proof of the pigeonhole principle for injections admitting the uniform counting principle as an axiom scheme cannot have\n                    <jats:italic>o<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    )-evaluations. As for the remaining two, we utilize well-known notions of\n                    <jats:italic>p<\/jats:italic>\n                    -tree and\n                    <jats:italic>k<\/jats:italic>\n                    -evaluation and reduce the problems to the existence of certain families of polynomials witnessing violations of the corresponding combinatorial principles with low-degree Nullstellensatz proofs from the violation of the modular counting principle in concern.\n                  <\/jats:p>","DOI":"10.1007\/s00153-024-00938-1","type":"journal-article","created":{"date-parts":[[2024,7,22]],"date-time":"2024-07-22T14:02:12Z","timestamp":1721656932000},"page":"117-158","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On some $$\\Sigma ^{B}_{0}$$-formulae generalizing counting principles over $$V^{0}$$"],"prefix":"10.1007","volume":"64","author":[{"given":"Eitetsu","family":"Ken","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,7,22]]},"reference":[{"issue":"1\u20132","key":"938_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00153-014-0398-3","volume":"54","author":"A Atserias","year":"2015","unstructured":"Atserias, A., M\u00fcller, M.: Partially definable forcing and bounded arithmetic. Arch. Math. Logic 54(1\u20132), 1\u201333 (2015). https:\/\/doi.org\/10.1007\/s00153-014-0398-3","journal-title":"Arch. Math. Logic"},{"key":"938_CR2","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/BF01302964","volume":"14","author":"M Ajtai","year":"1994","unstructured":"Ajtai, M.: The complexity of the Pigeonhole principle. Combinatorica 14, 417\u2013433 (1994). https:\/\/doi.org\/10.1007\/BF01302964","journal-title":"Combinatorica"},{"key":"938_CR3","doi-asserted-by":"publisher","unstructured":"Beame, P., Impagliazzo, R., Kraj\u00ed\u010dek, J., Pitassi, T., Pudlak, P.: Lower bounds on Hilbert\u2019s Nullstellensatz and propositional proofs. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 794\u2013806 (1994). https:\/\/doi.org\/10.1109\/SFCS.1994.365714","DOI":"10.1109\/SFCS.1994.365714"},{"key":"938_CR4","doi-asserted-by":"publisher","unstructured":"Beame, P., Riis, S.: More on the relative strength of counting principles. In: Beame, P., Buss, S. (eds.) Proof Complexity and Feasible Arithmetics. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 39, pp. 13\u201335. American Mathematical Society, Providence (1998). https:\/\/doi.org\/10.1090\/dimacs\/039\/02","DOI":"10.1090\/dimacs\/039\/02"},{"issue":"3","key":"938_CR5","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0020-0190(84)90018-8","volume":"18","author":"SJ Berkowitz","year":"1984","unstructured":"Berkowitz, S.J.: On computing the determinant in small parallel time using a small number of processors. Inf. Process. Lett. 18(3), 147\u2013150 (1984). https:\/\/doi.org\/10.1016\/0020-0190(84)90018-8","journal-title":"Inf. Process. Lett."},{"key":"938_CR6","doi-asserted-by":"publisher","unstructured":"Bonet, M., Buss, S., Pitassi, T.: Are there hard examples for Frege systems? In: Clote, P., Remmel, J.B. (eds.) Feasible Mathematics II, Progress in Computer Science and Applied Logic, vol. 13, pp. 30\u201356. Birkh\u00e4user Boston (1995). https:\/\/doi.org\/10.1007\/978-1-4612-2566-9_3","DOI":"10.1007\/978-1-4612-2566-9_3"},{"key":"938_CR7","doi-asserted-by":"publisher","unstructured":"Buss, S.: Lower bounds on Nullstellensatz proofs via designs. In: Beame, P., Buss, S. (eds.) Proof Complexity and Feasible Arithmetics. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 39, pp. 59\u201371. American Mathematical Society, Providence (1998). https:\/\/doi.org\/10.1090\/dimacs\/039\/04","DOI":"10.1090\/dimacs\/039\/04"},{"key":"938_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511676277","volume-title":"Logical Foundations of Proof Complexity, Perspectives in Logic","author":"S Cook","year":"2010","unstructured":"Cook, S., Nguyen, P.: Logical Foundations of Proof Complexity, Perspectives in Logic. Cambridge University Press, New York (2010). https:\/\/doi.org\/10.1017\/CBO9780511676277"},{"key":"938_CR9","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1111\/j.1469-1809.1940.tb02237.x","volume":"10","author":"RA Fisher","year":"1940","unstructured":"Fisher, R.A.: An examination of the different possible solutions of a problem in incomplete blocks. Ann. Eugen. 10, 52\u201375 (1940)","journal-title":"Ann. Eugen."},{"issue":"2","key":"938_CR10","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1137\/130917788","volume":"44","author":"P Hrube\u0161","year":"2015","unstructured":"Hrube\u0161, P., Tzameret, I.: Short proofs for the determinant identities. SIAM J. Comput. 44(2), 340\u2013383 (2015). https:\/\/doi.org\/10.1137\/130917788","journal-title":"SIAM J. Comput."},{"issue":"5\u20136","key":"938_CR11","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1007\/s00153-021-00810-6","volume":"61","author":"E Je\u0159\u00e1bek","year":"2022","unstructured":"Je\u0159\u00e1bek, E.: Iterated multiplication in $$ {VTC}^0$$. Arch. Math. Logic 61(5\u20136), 705\u2013767 (2022). https:\/\/doi.org\/10.1007\/s00153-021-00810-6","journal-title":"Arch. Math. Logic"},{"key":"938_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511529948","volume-title":"Bounded Arithmetic, Propositional Logic, and Complexity Theory, Encyclopedia of Mathematics and Its Applications","author":"J Kraj\u00ed\u010dek","year":"1995","unstructured":"Kraj\u00ed\u010dek, J.: Bounded Arithmetic, Propositional Logic, and Complexity Theory, Encyclopedia of Mathematics and Its Applications, vol. 60. Cambridge University Press, Cambridge (1995). https:\/\/doi.org\/10.1017\/CBO9780511529948"},{"key":"938_CR13","doi-asserted-by":"publisher","DOI":"10.1017\/9781108242066","volume-title":"Proof Complexity, Encyclopedia of Mathematics and Its Applications","author":"J Kraj\u00ed\u010dek","year":"2019","unstructured":"Kraj\u00ed\u010dek, J.: Proof Complexity, Encyclopedia of Mathematics and Its Applications, vol. 170. Cambridge University Press, Cambridge (2019). https:\/\/doi.org\/10.1017\/9781108242066"},{"issue":"1","key":"938_CR14","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1002\/rsa.3240070103","volume":"7","author":"J Kraj\u00ed\u010dek","year":"1995","unstructured":"Kraj\u00ed\u010dek, J., Pudl\u00e1k, P., Woods, A.: An exponential lower bound to the size of bounded depth Frege proofs of the pigeonhole principle. Random Struct. Algorithms 7(1), 15\u201339 (1995). https:\/\/doi.org\/10.1002\/rsa.3240070103","journal-title":"Random Struct. Algorithms"},{"key":"938_CR15","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1214\/aoms\/1177728978","volume":"24","author":"KN Majumdar","year":"1953","unstructured":"Majumdar, K.N.: On some theorems in combinatorics relating to incomplete block designs. Ann. Math. Stat. 24, 377\u2013389 (1953). https:\/\/doi.org\/10.1214\/aoms\/1177728978","journal-title":"Ann. Math. Stat."},{"issue":"2","key":"938_CR16","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01200117","volume":"3","author":"T Pitassi","year":"1993","unstructured":"Pitassi, T., Beame, P., Impagliazzo, R.: Exponential lower bounds for the pigeonhole principle. Comput. Complex. 3(2), 97\u2013140 (1993). https:\/\/doi.org\/10.1007\/BF01200117","journal-title":"Comput. Complex."},{"issue":"4","key":"938_CR17","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/s000370050013","volume":"7","author":"AA Razborov","year":"1998","unstructured":"Razborov, A.A.: Lower bounds for the polynomial calculus. Comput. Complex. 7(4), 291\u2013324 (1998). https:\/\/doi.org\/10.1007\/s000370050013","journal-title":"Comput. Complex."},{"key":"938_CR18","unstructured":"Soltys, M.: The complexity of derivations of matrix identities, Thesis (Ph.D.), University of Toronto, Canada (2001)"},{"issue":"1\u20133","key":"938_CR19","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/j.apal.2003.10.018","volume":"130","author":"M Soltys","year":"2004","unstructured":"Soltys, M., Cook, S.: The proof complexity of linear algebra. Ann. Pure Appl. Logic 130(1\u20133), 277\u2013323 (2004). https:\/\/doi.org\/10.1016\/j.apal.2003.10.018","journal-title":"Ann. Pure Appl. Logic"},{"issue":"2","key":"938_CR20","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1145\/3431922","volume":"68","author":"I Tzameret","year":"2021","unstructured":"Tzameret, I., Cook, S.: Uniform, integral, and feasible proofs for the determinant identities. J. ACM 68(2), 80 (2021). https:\/\/doi.org\/10.1145\/3431922","journal-title":"J. ACM"},{"issue":"1","key":"938_CR21","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1006\/jcta.1996.2729","volume":"77","author":"DR Woodall","year":"1997","unstructured":"Woodall, D.R.: A note on Fisher\u2019s inequality. J. Combin. Theory Ser. A 77(1), 171\u2013176 (1997). https:\/\/doi.org\/10.1006\/jcta.1996.2729","journal-title":"J. Combin. Theory Ser. A"}],"container-title":["Archive for Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-024-00938-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00153-024-00938-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-024-00938-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T00:40:31Z","timestamp":1739320831000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00153-024-00938-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,22]]},"references-count":21,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["938"],"URL":"https:\/\/doi.org\/10.1007\/s00153-024-00938-1","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-2855463\/v1","asserted-by":"object"}]},"ISSN":["0933-5846","1432-0665"],"issn-type":[{"value":"0933-5846","type":"print"},{"value":"1432-0665","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,22]]},"assertion":[{"value":"24 April 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 July 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}