REVIEW 2 major objections 3 minor 20 references
Free resolutions of function classes via order complexes
T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read For intersection-closed classes of Boolean functions, the paper builds an explicit free resolution from the poset's order complex and reads off Betti numbers from interval homologies.
desk verdict Solid algebraic core with a wrong parity application: the order-complex resolution and Möbius Betti formulas are real contributions, but Corollary 6.8 is false and needs correction or removal. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the order complex $\Delta_P$ of an intersection-closed subposet $P$ of the Boolean lattice: the simplicial complex whose faces are chains $A_0 < A_1 < \cdots < A_i$ in $P$. The paper labels each vertex $A$ by the minimal generator $m(A,A)$ of $I^*_{C(P)}$ and labels each higher face by the least common multiple of its vertex labels, producing a cellular complex of free modules. The crucial local fact is that for intersection-closed $P$, the subcomplex of faces whose labels divide $m(A,B)$ is a cone over $A$ and hence acyclic, so the labeling gives a valid free resolution. The Betti numbers then appear as reduced homologies of truncated order complexes $\Delta_{[A,B]}$, and the Möbius function enters through Philip Hall's theorem once every interval is Cohen-Macaulay. This dictionary—monomial labels to partial functions, intervals to Betti degrees—carries the later applications.
What would settle it
Choose an intersection-closed poset $P$ (for instance a small lattice of flats), compute the multigraded Betti numbers of $I^*_{C(P)}$ from the generators $m(A,A)$ with a Gröbner basis, and compare each $\beta_{i,m(A,B)}$ with $\dim \tilde{H}_{i-2}(\Delta_{[A,B]})$ over the same field. A mismatch in any single degree would refute Theorem 4.4.
Extended reading notes
Core claim
Let $P\subseteq 2^{[n]}$ be closed under intersection, and let $C(P)$ be the class of indicator functions of the sets in $P$. The main theorem states that the cellular complex $F(\Delta_P)$, whose vertices $A\in P$ are labeled by the monomial $m(A,A)=\prod_{i\in A}x_{i,0}\prod_{i\notin A}x_{i,1}$ and whose faces are labeled by lcms of vertex labels, is acyclic and resolves $S/I^*_{C(P)}$. Because $P$ is intersection-closed, the subcomplex of faces whose labels divide $m(A,B)$ is a cone with apex $A$, which gives the acyclicity. It follows that the only possible Betti degrees are $m(A,B)$ for $A\le B$, with $\beta_{i,m(A,B)}=\dim \tilde{H}_{i-2}(\Delta_{[A,B]})$ for $i\ge 1$. When every interval of $P$ is Cohen-Macaulay, these homologies vanish except in the top dimension, so the nonzero Betti numbers are pure and equal $|\mu_P(A,B)|$ when $\operatorname{rank}([A,B])=i$.
Load-bearing premise
The construction assumes the function class is exactly $C(P)$ for a poset $P\subseteq 2^{[n]}$ that is closed under intersections; if $P$ is not intersection-closed, the cone argument that proves acyclicity fails and the interval-homology Betti formula need not hold.
Editorial extensions
If this is right
- For every intersection-closed poset $P$, the homological dimension satisfies $\dim_h C(P) \le \operatorname{rank}(P)$, so the chain length of $P$ bounds the length of any minimal free resolution (Corollary 4.6).
- For interval Cohen-Macaulay $P$, the Betti table is pure: the only nonzero entries occur when $i=\operatorname{rank}([A,B])$, and each equals $|\mu_P(A,B)|$ (Theorem 5.5).
- For the lattice of flats of a matroid $M$, $\dim_{\mathrm{VC}} C(P_M)=\dim_h C(P_M)=\operatorname{rank}(M)$, so homological dimension is a sharp learning-theoretic bound for these classes (Corollary 5.11).
- For the face poset of a polyhedral cell complex $X$, $\dim_h C(P_X)=\dim X+1$, with equality of VC dimension exactly when $X$ contains a full-dimensional simplex and near-equality under simplicial facet or simple vertex hypotheses (Corollary 5.18).
- For $k$-CNF classes in $d$ variables, both VC dimension and homological dimension are $\Theta(d^k)$ with constants depending only on $k$, and for $D$-CSPs homological dimension is at most $|D|$ (Theorems 6.3 and 6.7).
Reading between the lines
- The same order-complex resolution should apply to any function class closed under pointwise conjunction, even when the class is presented by formulas rather than by a poset; the poset is just the collection of 1-sets of the functions.
- The rank bound gives a general strategy for VC upper bounds: any chain bound on a conjunction-closed formula class, as done for k-CNFs and D-CSPs, yields a homological upper bound and hence a sample-complexity bound.
- The matroid equality suggests a broader sufficient condition: if an intersection-closed class shatters a set whose size equals the poset rank, then VC dimension and homological dimension must coincide; other geometric families of lattices could be screened this way.
- Because the resolution is cellular, discrete Morse theory on $\Delta_P$ could collapse it to a minimal resolution for specific classes, potentially giving exact Betti tables where only bounds are currently known.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the Alexander dual ideal I*_{C(P)} attached to a function class C(P) whose 1-sets form a subposet P of the Boolean lattice. For intersection-closed P, it constructs a cellular free resolution supported on the order complex of P (Theorem 4.3), expresses the multigraded Betti numbers of I*_{C(P)} as reduced homology groups of truncated order complexes of intervals of P (Theorem 4.4), and, for interval Cohen-Macaulay posets, identifies the Betti numbers with absolute values of Möbius function values (Theorem 5.5). The paper then applies these results to matroid flat classes, polyhedral cell complexes, k-CNF and CSP classes, and classes of conjunctions of parity functions and of low-degree polynomials over F2.
Significance. The algebraic core is a genuine contribution: the cellular resolution is simple and canonical, the Betti number formulas are explicit and combinatorial, and the matroid and polyhedral specializations yield clean, falsifiable statements (Corollaries 5.10, 5.11, 5.17). The k-CNF and CSP bounds, while proved by an informal chain-counting argument, are plausible and useful. However, the parity-function application is not correct. Corollary 6.8 is false as stated: the class of conjunctions of parity functions is not the flat-indicator class of the matroid on all vectors of F2^d. This is a local but load-bearing error in the applications section.
major comments (2)
- [6.3, Corollary 6.8; also 5.1, Example 5.9] The proof of Corollary 6.8 identifies the class of conjunctions of parity functions with the function class C(P_M) of the matroid on all vectors of F2^d. This identification is invalid. A parity function ell, defined as an F2-linear functional, has 1-set ell^{-1}(1), which is an affine hyperplane not containing 0, whereas every flat of that matroid is a linear subspace and contains 0. Conjunctions of parity functions are therefore intersections of affine hyperplanes, i.e. affine subspaces (in fact, affine subspaces not containing 0, together with the empty set and the whole space), not linear subspaces. The error changes the numerical conclusion: for d=2 the set U={10,01,11} is shattered, witnessed by the empty set via x1∧x2∧(x1+x2), by {10}=x1∧(x1+x2), {01}=x2∧(x1+x2), {11}=x1∧x2, {10,11}=x1, {01,11}=x2, {10,01}=x1+x2, and by the whole space via the empty conjunction. Hence dimVC C is at least 3, contradicting the claimed value 2. For d≥2 the correct value is d+1; for example, an affinely independent (d+1)-set avoiding 0 is shattered by the affine subspaces not containing 0. The proof can be repaired by homogenizing to coordinates (1,x) in F2^{d+1}, whose linear matroid has flats pulling back to affine subspaces, so that Corollary 5.11 gives rank d+1. Example 5.9 should be corrected in the same way, since flats of a matroid over F2 are linear subspaces rather than 1-sets of linear functionals.
- [6.3, Corollaries 6.8 and 6.9] Corollary 6.8 and Corollary 6.9 are in tension with each other. Taking k=1 in Corollary 6.9 gives dimVC=dimh=d+1 for the class of conjunctions of degree at most 1 polynomials, while Corollary 6.8 asserts d for the closely related class of conjunctions of homogeneous parity functions. The concrete counterexample in the previous comment shows that Corollary 6.8 is the one in error: the smaller class already has VC dimension d+1 for d≥2. Corollary 6.9 itself is essentially the correct homogenized statement, but the authors must make the two statements consistent and must update Remark 6.10, which currently claims that adding conjunction does not increase the VC or homological dimension of the parity classes from d to d+1.
minor comments (3)
- [6.2, Theorem 6.3] The expression '2k (d choose k)' appears without a superscript in the statement and proof; it should read '2^k (d choose k)'.
- [3, Definition 3.2] The convention for the truncated order complex of an interval is easy to misread; please clarify which of Delta_{(A,B)} and Delta_{[A,B]} is being defined and how the rank-one case is handled.
- [6.3, Remark 6.10] After correcting Corollary 6.8, Remark 6.10 should be revised: the statement that adding conjunction does not increase complexity is no longer accurate for the parity-based classes, since the VC and homological dimensions increase from d to d+1 for d≥2.
Circularity Check
No significant circularity: the resolution and Betti-number theorems are derived from standard cellular-resolution and poset-topology tools, and the cited [Yan17] inequality is external prior work, not an input disguised as a conclusion.
full rationale
The central derivation chain is self-contained. Theorem 4.3 is proved directly from the cellular-resolution acyclicity criterion [MS05, Proposition 4.5], using intersection-closure only to ensure that the relevant vertex A lies in P and hence that the subcomplex (Δ_P)_{≼m} is a cone. Theorem 4.4 then follows from the standard cellular Betti formula [MS05, Theorem 4.7] together with the suspension observation in Remark 3.3; no quantity is fitted and no target invariant is used as an input. Theorem 5.5 is a straightforward application of Philip Hall's theorem and Reisner's Cohen-Macaulay criterion, and the matroid and polyhedral corollaries follow from shellability of geometric lattices and face posets. The applications to k-CNFs and D-CSPs use the rank bound Corollary 4.6, which is a consequence of the explicit resolution, not a restatement of the desired VC-dimension bound. The only notable reliance on the authors' prior work is Theorem 2.10, quoted from [Yan17], giving dim_VC C ≤ dim_h C; this is an external theorem in a preprint by the third author, it is not the target result of the paper, and the paper's main algebraic theorems do not depend on it for their validity. The parity-function application in Corollary 6.8 appears to contain a separate mathematical error—the 1-set of a parity function is an affine hyperplane, not a linear flat—so the identification of conjunctions of parity functions with C(P_M) is doubtful; but that is a correctness concern, not a circularity of the kind where an input is renamed as a prediction or a cited result is forced by definition. Under the stated rules, no circular step is exhibited.
Assumptions & free parameters
assumptions (6)
- standard math Stanley-Reisner correspondence and Hochster's formula for multigraded Betti numbers
- standard math Cellular resolution acyclicity criterion: a labeled cell complex gives a free resolution if every subcomplex below a monomial is acyclic
- standard math Reisner's criterion and shellability of geometric lattices and polytope face posets
- domain assumption P is an intersection-closed subposet of 2^[n], and the function class C(P) is exactly the indicator functions of elements of P
- domain assumption The classes of k-CNFs, monotone k-CNFs, and D-CSPs are closed under conjunction, so their 1-sets form intersection-closed posets
- ad hoc to paper In Corollary 6.8, the class of conjunctions of parity functions is exactly the function class associated to the matroid of all vectors in F2^d
Cite this review
Pith. "Pith review of Free resolutions of function classes via order complexes." pith.science (2026). https://pith.science/paper/D6ROC224
@misc{pith2026190902159,
author = {Pith},
title = {Pith review of: Free resolutions of function classes via order complexes},
year = {2026},
howpublished = {\url{https://pith.science/paper/D6ROC224}},
note = {Machine review of arXiv:1909.02159}
}
read the original abstract
Function classes are collections of Boolean functions on a finite set, which are fundamental objects of study in theoretical computer science. We study algebraic properties of ideals associated to function classes previously defined by the third author. We consider the broad family of intersection-closed function classes, and describe cellular free resolutions of their ideals by order complexes of the associated posets. For function classes arising from matroids, polyhedral cell complexes, and more generally interval Cohen-Macaulay posets, we show that the multigraded Betti numbers are pure, and are given combinatorially by the M\"obius functions. We then apply our methods to derive bounds on the VC dimension of some important families of function classes in learning theory.
Reference graph
Works this paper leans on
-
[1]
An introduction to cohen-macaulay partially ordered sets
Anders Bj \"o rner, Adriano M Garsia, and Richard P Stanley. An introduction to cohen-macaulay partially ordered sets. In Ordered sets , pages 583--615. Springer, 1982
work page 1982
-
[2]
Shellable and C ohen- M acaulay partially ordered sets
Anders Bj \"o rner. Shellable and C ohen- M acaulay partially ordered sets. Trans. Amer. Math. Soc. , 260(1):159--183, 1980
work page 1980
-
[3]
Shellable decompositions of cells and spheres
Heinz Bruggesser and Peter Mani. Shellable decompositions of cells and spheres. Math. Scand. , 29:197--205 (1972), 1971
work page 1972
-
[4]
Anders Bj\" o rner and Michelle L. Wachs. Shellable nonpure complexes and posets. I . Trans. Amer. Math. Soc. , 348(4):1299--1327, 1996
work page 1996
-
[5]
Harold Scott Macdonald Coxeter. Regular polytopes . Courier Corporation, 1973
work page 1973
-
[6]
The geometry of syzygies , volume 229 of Graduate Texts in Mathematics
David Eisenbud. The geometry of syzygies , volume 229 of Graduate Texts in Mathematics . Springer-Verlag, New York, 2005. A second course in commutative algebra and algebraic geometry
2005
-
[7]
John A. Eagon and Victor Reiner. Resolutions of S tanley- R eisner rings and A lexander duality. J. Pure Appl. Algebra , 130(3):265--275, 1998
work page 1998
-
[8]
Grayson and Michael E
Daniel R. Grayson and Michael E. Stillman. Macaulay2, a software system for research in algebraic geometry. Available at http://www.math.uiuc.edu/Macaulay2/
Show all 20 references
-
[9]
David Helmbold, Robert Sloan, and Manfred K. Warmuth. Learning nested differences of intersection-closed concept classes. In Proceedings of the S econd A nnual W orkshop on C omputational L earning T heory ( S anta C ruz, CA , 1989) , pages 41--56. Morgan Kaufmann, San Mateo, CA, 1989
1989
-
[10]
An Introduction to Computational Learning Theory
Michael Kearns and Umesh Vazirani. An Introduction to Computational Learning Theory . January 1994
1994
-
[11]
Combinatorial commutative algebra , volume 227 of Graduate Texts in Mathematics
Ezra Miller and Bernd Sturmfels. Combinatorial commutative algebra , volume 227 of Graduate Texts in Mathematics . Springer-Verlag, New York, 2005
2005
-
[12]
Matroid theory , volume 21 of Oxford Graduate Texts in Mathematics
James Oxley. Matroid theory , volume 21 of Oxford Graduate Texts in Mathematics . Oxford University Press, Oxford, 2 edition, 2011
2011
-
[13]
Gerald A. Reisner. Cohen- M acaulay quotients of polynomial rings. Advances in Math. , 21(1):30--49, 1976
1976
-
[14]
On the foundations of combinatorial theory
Gian-Carlo Rota. On the foundations of combinatorial theory. I . T heory of M \" o bius functions. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete , 2:340--368 (1964), 1964
1964
-
[15]
Richard P. Stanley. Cohen- M acaulay complexes. pages 51--62. NATO Adv. Study Inst. Ser., Ser. C: Math. and Phys. Sci., 31, 1977
1977
-
[16]
Vapnik and Alexey Y
Vladimir N. Vapnik and Alexey Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications , 16(2):264--280, 1971
1971
-
[17]
Michelle L. Wachs. Poset topology: tools and applications. In Geometric combinatorics , volume 13 of IAS/Park City Math. Ser. , pages 497--615. Amer. Math. Soc., Providence, RI, 2007
2007
-
[18]
A homological theory of functions
Greg Yang. A homological theory of functions. arXiv preprint arXiv:1701.02302 , 2017
2017 arXiv
-
[19]
The M \" o bius function and the characteristic polynomial
Thomas Zaslavsky. The M \" o bius function and the characteristic polynomial. In Combinatorial geometries , volume 29 of Encyclopedia Math. Appl. , pages 114--138. Cambridge Univ. Press, Cambridge, 1987
1987
-
[20]
G\"unter M. Ziegler. Lectures on Polytopes , volume 152 of Graduate Texts in Mathematics . Springer New York, New York, NY, 1995
1995
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.