pith. sign in

arxiv: 2604.18290 · v1 · submitted 2026-04-20 · 🧮 math.CO · math.LO

Finite combinatorics and computability theory

Damir D. Dzhafarov , Jun le Goh This is my paper

Pith reviewed 2026-05-10 04:25 UTC · model grok-4.3

classification 🧮 math.CO math.LO
keywords finite combinatoricscomputability theorypigeonhole principlealgorithmic reductionsaffine planesLatin squaresblock designs
0
0 comments X

The pith

The existence of finite combinatorial objects such as affine planes equals the existence of algorithmic reductions between pigeonhole principle problems.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that statements about the existence of certain finite designs can be translated exactly into statements about whether one computational problem reduces algorithmically to another. The designs in question include affine planes, mutually orthogonal Latin squares, and resolvable balanced incomplete block designs, each tied to a specific reduction between variants of the pigeonhole principle. Once recast this way, the authors apply counting arguments and techniques from computability theory to obtain information about when the designs exist. A reader would care because the translation opens a route for computational methods to address longstanding existence questions in combinatorics that have traditionally been handled only by direct combinatorial arguments.

Core claim

We prove that the existence of finite combinatorial objects such as affine planes, mutually orthogonal Latin squares, and resolvable balanced incomplete block designs can be reformulated as the existence of certain algorithmic reductions between problems related to the pigeonhole principle. We then study the latter using counting arguments and computability theory. In particular, we demonstrate that computability theoretic techniques can be used to refine and prove new results in finite combinatorics.

What carries the argument

Algorithmic reductions between pigeonhole-principle problems, which serve as the exact reformulation of the combinatorial existence statements.

If this is right

  • Counting arguments applied to the reductions yield new bounds or non-existence results for the designs.
  • Computability-theoretic invariants of the reductions classify which designs can exist.
  • New existence theorems for the designs follow from known reduction relations between pigeonhole problems.
  • Refinements of classical combinatorial theorems become available once the reductions are analyzed in detail.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same reduction-based translation might apply to other existence questions in extremal combinatorics that can be phrased in terms of choice functions or colorings.
  • If the reductions turn out to be computably enumerable or arithmetic, this could link combinatorial existence to the arithmetic hierarchy in a uniform way.
  • The approach suggests checking whether known non-existence results for designs already correspond to failures of computable reductions.

Load-bearing premise

The combinatorial existence statements can be faithfully recast as algorithmic reductions between pigeonhole-related problems without introducing extraneous assumptions that change the original meaning or scope.

What would settle it

A concrete pair consisting of a specific combinatorial design whose existence is known and a pair of pigeonhole problems for which no corresponding algorithmic reduction exists, or the converse.

Figures

Figures reproduced from arXiv: 2604.18290 by Damir D. Dzhafarov, Jun le Goh.

Figure 1
Figure 1. Figure 1: We do not have a conjecture for a complete answer. As we discuss in the [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 1
Figure 1. Figure 1: For n ≤ 5 and selected m ≤ n 2 , we draw (m′ , n′ ) → (m, n) if (m ̸,→ n) ≤ (m′ ̸,→ n ′ ); these follow from Propositions 1.4, 1.6, 2.2, 2.18, 2.21 and 5.1. A node (m, n) lies above (or along) the dotted line passing through idk if and only if idk ≤ (m ̸,→ n); the nonreductions here follow from Lemma 2.8. Proposition 2.2. For each n ≥ 2, we have (n + 1 ̸,→ n) ≡ id( n+1 2 ) . Proof. To prove (n + 1 ̸,→ n) ≤… view at source ↗
Figure 2
Figure 2. Figure 2: We describe the strength of (m ̸,→ n) ′ for m between n 2 and n 5 . A node m lies above the dotted line passing through ACCk/AUCk/etc. if and only if the latter is Weihrauch reducible to (m ̸,→ n) ′ , according to Theorems 2.11, 3.4, Proposition 3.7, Corollary 3.9, Propositions 3.13 and 3.14. considering their jumps. This is not possible by results of [7, 28], as we explain below. To this end we consider t… view at source ↗
Figure 3
Figure 3. Figure 3: id6 ≤ (9 ̸,→ 4). View edges of the same color as defining a function from 9 to 4. The proof that (m0 ̸,→ n0) ≤ (m1 ̸,→ n1) if and only if (m0 ̸,→ n0) ′ ≤W (m1 ̸,→ n1) ′ is analogous. □ 5. Additional results This section establishes several ad hoc reductions and nonreductions. When constructing reductions, we shall express a function from m to n by listing its fibers in order. For example, (02)(13) represen… view at source ↗
read the original abstract

We prove that the existence of finite combinatorial objects such as affine planes, mutually orthogonal Latin squares, and resolvable balanced incomplete block designs can be reformulated as the existence of certain algorithmic reductions between problems related to the pigeonhole principle. We then study the latter using counting arguments and computability theory. In particular, we demonstrate that computability theoretic techniques can be used to refine and prove new results in finite combinatorics.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript claims that the existence of finite combinatorial objects such as affine planes, mutually orthogonal Latin squares, and resolvable balanced incomplete block designs can be reformulated as the existence of certain algorithmic reductions between problems related to the pigeonhole principle. It then applies counting arguments and computability-theoretic techniques to analyze these reformulated problems, with the goal of refining and proving new results in finite combinatorics.

Significance. If the central reformulations are faithful and the computability methods produce genuinely new combinatorial theorems, the work would establish a potentially useful bridge between finite combinatorics and computability theory. This could allow algorithmic and counting techniques to address existence questions for designs that have traditionally been studied via direct combinatorial arguments or algebraic constructions.

major comments (1)
  1. The abstract asserts that specific combinatorial existence statements are equivalent to algorithmic reductions between PHP-related problems, but the manuscript provides no explicit definitions of the reduction notions, no formal statement of the equivalence for any of the three example objects (affine planes, MOLS, resolvable BIBDs), and no proof sketches. Without these, the central claim cannot be verified and the subsequent counting/computability arguments rest on an unexamined foundation.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thoughtful review and for recognizing the potential bridge between finite combinatorics and computability theory. We address the single major comment below and will revise the manuscript to strengthen the presentation of our central claims.

read point-by-point responses

  1. Referee: The abstract asserts that specific combinatorial existence statements are equivalent to algorithmic reductions between PHP-related problems, but the manuscript provides no explicit definitions of the reduction notions, no formal statement of the equivalence for any of the three example objects (affine planes, MOLS, resolvable BIBDs), and no proof sketches. Without these, the central claim cannot be verified and the subsequent counting/computability arguments rest on an unexamined foundation.

    Authors: We agree that the current manuscript would benefit from greater explicitness at the outset. While the body develops the reformulations via counting and computability arguments, we acknowledge that the reduction notions (e.g., the specific form of algorithmic reductions between PHP instances) and the precise equivalences for affine planes, MOLS, and resolvable BIBDs are not stated with sufficient formality or accompanied by proof outlines in a single accessible location. In the revised version we will insert a new preliminary section that (i) defines the relevant reduction concepts in the context of PHP problems, (ii) states the three equivalences formally as theorems, and (iii) provides concise proof sketches. This change will make the foundation of the subsequent results immediately verifiable without altering the technical content. revision: yes

Circularity Check

0 steps flagged

Reformulation and subsequent analysis are independent; no circularity

full rationale

The paper's core step is a direct reformulation of standard combinatorial existence statements (affine planes, MOLS, resolvable BIBDs) as algorithmic reductions between PHP-related problems. This equivalence is derived from the definitions of the objects and the notion of reduction, without any self-referential fitting, ansatz smuggling, or load-bearing self-citation. The subsequent counting arguments and computability-theoretic techniques are applied to the reformulated problems to obtain new combinatorial results; these methods are external to the reformulation and do not feed back to justify it. No equation or claim reduces to its own input by construction, and the derivation remains self-contained against external benchmarks in combinatorics and computability.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based solely on the abstract, the paper relies on standard mathematical background in combinatorics and computability without introducing free parameters, new axioms beyond domain assumptions, or invented entities.

pith-pipeline@v0.9.0 · 5351 in / 1101 out tokens · 29035 ms · 2026-05-10T04:25:18.482109+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages

  1. [1]

    David Belanger, C. T. Chong, Wei Wang, Tin Lok Wong, and Yue Yang. Where pigeonhole principles meet K¨ onig lemmas.Trans. Amer. Math. Soc., 374(11):8275–8303, 2021

    work page 2021

  2. [2]

    Heidi Benham. Ph.D. thesis – University of Connecticut, to appear

    work page

  3. [3]

    Dzhafarov, Reed Solomon, and Java Darleen Villano

    Heidi Benham, Andrew DeLapo, Damir D. Dzhafarov, Reed Solomon, and Java Darleen Villano. The Ginsburg–Sands theorem and computability theory.Adv. Math., 444:109618, 2024

    work page 2024

  4. [4]

    Bibliography on Weihrauch complexity, website: http://cca-net.de/publications/weibib.php, 2019

    Vasco Brattka. Bibliography on Weihrauch complexity, website: http://cca-net.de/publications/weibib.php, 2019

    work page 2019

  5. [5]

    Stashing and parallelization pentagons.Log

    Vasco Brattka. Stashing and parallelization pentagons.Log. Methods Comput. Sci., 17(4):Pa- per No. 20, 29, 2021

    work page 2021

  6. [6]

    Springer International Publishing, Cham, 2017

    Vasco Brattka, Guido Gherardi, Rupert H¨ olzl, and Arno Pauly.The Vitali Covering Theorem in the Weihrauch Lattice, pages 188–200. Springer International Publishing, Cham, 2017

    work page 2017

  7. [7]

    The Bolzano-Weierstrass theorem is the jump of weak K¨ onig’s lemma.Ann

    Vasco Brattka, Guido Gherardi, and Alberto Marcone. The Bolzano-Weierstrass theorem is the jump of weak K¨ onig’s lemma.Ann. Pure Appl. Logic, 163(6):623–655, 2012

    work page 2012

  8. [8]

    Weihrauch complexity in computable anal- ysis

    Vasco Brattka, Guido Gherardi, and Arno Pauly. Weihrauch complexity in computable anal- ysis. InHandbook of computability and complexity in analysis, Theory Appl. Comput., pages 367–417. Springer, Cham, [2021]©2021

    work page 2021

  9. [9]

    Vasco Brattka, Matthew Hendtlass, and Alexander P. Kreuzer. On the uniform computational content of computability theory.Theory Comput. Syst., 61(4):1376–1426, 2017. 22 DZHAF AROV AND GOH

    work page 2017

  10. [10]

    Vasco Brattka, Matthew Hendtlass, and Alexander P. Kreuzer. On the Uniform Compu- tational Content of the Baire Category Theorem.Notre Dame Journal of Formal Logic, 59(4):605 – 636, 2018

    work page 2018

  11. [11]

    Monte Carlo computability

    Vasco Brattka, Rupert H¨ olzl, and Rutger Kuyper. Monte Carlo computability. In34th Sym- posium on Theoretical Aspects of Computer Science, volume 66 ofLIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 17, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017

    work page 2017

  12. [12]

    Miller, and Arno Pauly

    Vasco Brattka, St´ ephane Le Roux, Joseph S. Miller, and Arno Pauly. Connected choice and the Brouwer Fixed Point Theorem.Journal of Mathematical Logic, 19(01):1950004, 2019

    work page 2019

  13. [13]

    On the uniform computational content of Ramsey’s theorem.The Journal of Symbolic Logic, 82(4):1278–1316, 2017

    Vasco Brattka and Tahina Rakotoniaina. On the uniform computational content of Ramsey’s theorem.The Journal of Symbolic Logic, 82(4):1278–1316, 2017

    work page 2017

  14. [14]

    Colbourn and Jeffrey H

    Charles J. Colbourn and Jeffrey H. Dinitz, editors.Handbook of combinatorial designs. Dis- crete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, second edition, 2007

    work page 2007

  15. [15]

    Dorais, Damir D

    Fran¸ cois G. Dorais, Damir D. Dzhafarov, Jeffry L. Hirst, Joseph R. Mileti, and Paul Shafer. On uniform relationships between combinatorial problems.Trans. Amer. Math. Soc., 368(2):1321–1359, 2016

    work page 2016

  16. [16]

    Downey and Denis R

    Rodney G. Downey and Denis R. Hirschfeldt.Algorithmic randomness and complexity. The- ory and Applications of Computability. Springer, New York, 2010

    work page 2010

  17. [17]

    Dzhafarov, Jun Le Goh, Denis R

    Damir D. Dzhafarov, Jun Le Goh, Denis R. Hirschfeldt, Ludovic Patey, and Arno Pauly. Ramsey’s theorem and products in the Weihrauch degrees.Computability, 9(2):85–110, 2020

    work page 2020

  18. [18]

    Dzhafarov and Carl Mummert.Reverse Mathematics: Problems, Reductions, and Proofs

    Damir D. Dzhafarov and Carl Mummert.Reverse Mathematics: Problems, Reductions, and Proofs. Theory and Applications of Computability. Springer Nature, 2022

    work page 2022

  19. [19]

    Dzhafarov, Ludovic Patey, Reed Solomon, and Linda Brown Westrick

    Damir D. Dzhafarov, Ludovic Patey, Reed Solomon, and Linda Brown Westrick. Ram- sey’s theorem for singletons and strong computable reducibility.Proc. Amer. Math. Soc., 145(3):1343–1355, 2017

    work page 2017

  20. [20]

    Genovesi

    Giorgio G. Genovesi. Reverse mathematics of regular countable second countable spaces. To appear

    work page

  21. [21]

    Guido Gherardi and Alberto Marcone. How incomputable is the separable Hahn-Banach theo- rem? InProceedings of the Fifth International Conference on Computability and Complexity in Analysis (CCA 2008), volume 221 ofElectron. Notes Theor. Comput. Sci., pages 85–102. Elsevier Sci. B. V., Amsterdam, 2008

    work page 2008

  22. [22]

    Compositions of multivalued functions.Computability, 9(3-4):231–247, 2020

    Jun Le Goh. Compositions of multivalued functions.Computability, 9(3-4):231–247, 2020

    work page 2020

  23. [23]

    Hirschfeldt.Slicing the Truth: On the Computable and Reverse Mathematics of Combinatorial Principles

    Denis R. Hirschfeldt.Slicing the Truth: On the Computable and Reverse Mathematics of Combinatorial Principles. Lecture notes series / Institute for Mathematical Sciences, National University of Singapore. World Scientific Publishing Company Incorporated, 2014

    work page 2014

  24. [24]

    Hirschfeldt and Carl G

    Denis R. Hirschfeldt and Carl G. Jockusch, Jr. On notions of computability-theoretic reduc- tion between Π 1 2 principles.J. Math. Log., 16(1):1650002, 59, 2016

    work page 2016

  25. [25]

    Hirst.Combinatorics in Subsystems of Second Order Arithmetic

    Jeffry L. Hirst.Combinatorics in Subsystems of Second Order Arithmetic. PhD thesis, The Pennsylvania State University, 1987

    work page 1987

  26. [26]

    Hirst and Carl Mummert

    Jeffry L. Hirst and Carl Mummert. Banach’s theorem in higher-order reverse mathematics. Computability, 12(3):203–225, 2023

    work page 2023

  27. [27]

    Computability of the Radon– Nikodym derivative.Computability, 1(1):3–13, 2012

    Mathieu Hoyrup, Crist´ obal Rojas, and Klaus Weihrauch. Computability of the Radon– Nikodym derivative.Computability, 1(1):3–13, 2012

    work page 2012

  28. [28]

    Finite choice, convex choice and finding roots.Log

    St´ ephane Le Roux and Arno Pauly. Finite choice, convex choice and finding roots.Log. Methods Comput. Sci., 11(4):4:6, 30, 2015

    work page 2015

  29. [29]

    J. B. Paris and L. A. S. Kirby. Σ n-collection schemas in arithmetic. InLogic Colloquium ’77 (Proc. Conf., Wroc law, 1977), volume 96 ofStud. Logic Foundations Math., pages 199–209. North-Holland, Amsterdam-New York, 1978

    work page 1977

  30. [30]

    Theses, Universit´ e Paris Diderot (Paris 7) Sorbonne Paris Cit´ e, February 2016

    Ludovic Patey.The reverse mathematics of Ramsey-type theorems. Theses, Universit´ e Paris Diderot (Paris 7) Sorbonne Paris Cit´ e, February 2016. PhD thesis, 268 pages

    work page 2016

  31. [31]

    Richard A. Shore. Reverse mathematics: the playground of logic.Bull. Symbolic Logic, 16(3):378–402, 2010

    work page 2010

  32. [32]

    Simpson.Subsystems of second order arithmetic

    Stephen G. Simpson.Subsystems of second order arithmetic. Perspectives in Logic. Cam- bridge University Press, Cambridge, second edition, 2009

    work page 2009

  33. [33]

    Soare.Recursively enumerable sets and degrees

    Robert I. Soare.Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. FINITE COMBINATORICS AND COMPUTABILITY THEORY 23

    work page 1987

  34. [34]

    Soare.Turing Computability: Theory and Applications

    Robert I. Soare.Turing Computability: Theory and Applications. Springer Publishing Com- pany, Incorporated, 1st edition, 2016

    work page 2016

  35. [35]

    D. R. Stinson. Combinatorial techniques for universal hashing.J. Comput. System Sci., 48(2):337–346, 1994

    work page 1994

  36. [36]

    P. Tur´ an. On the theory of graphs.Colloq. Math., 3:19–30, 1954. Department of Mathematics, University of Connecticut, Storrs CT, USA 06107 Email address:damir@math.uconn.edu Department of Mathematics, National University of Singapore, Singapore 119076 Email address:gohjunle@nus.edu.sg

    work page 1954