{"id":"57b63532-a243-442d-9171-aa6cf159dcd8","arxiv_id":"1909.02159","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For intersection-closed Boolean function classes, the paper builds cellular free resolutions from order complexes and gives pure Betti numbers from Möbius functions for interval Cohen-Macaulay posets.","lead":"This paper constructs algebraic objects called free resolutions for collections of Boolean functions that are closed under intersections, and shows how to read off their structure from the shape of an associated family of sets. It connects commutative algebra to learning theory by using these resolutions to bound the VC dimension of several well-known function classes.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 6.8 is false: the 1-set of a conjunction of parity functions is an affine subspace, not a flat of the all-vectors matroid; for d=2 the class shatters {10,01,11}, giving dimVC=3.","rationale":"I find no flaw in the proof of Theorem 4.3 itself: for intersection-closed P, the subcomplex (Delta_P)_{⪯m(A,B)} is a cone over the point A, hence acyclic, and Theorem 4.4 then follows from the cellular-resolution Betti formula together with the suspension observation in Remark 3.3. The k-CNF and CSP applications are also defensible, since those classes are conjunction-closed and hence their 1-sets form an intersection-closed poset. The concrete failure is in Section 6.3: the parity class is conflated with the flat-indicator class of the matroid on all vectors of F2^d. The 1-set of a homogeneous parity function is an affine hyperplane, not a linear subspace, and conjunctions of such functions give affine subspaces. For d=2 this class contains enough sets to shatter a 3-element set, so Corollary 6.8 is false as stated. This is a genuine correctness issue in an advertised application, but it does not undermine the main resolution theorem; the correct response is a conditional acceptance requiring the parity application to be fixed or removed. The reader's weakest_assumption focused on the intersection-closed hypothesis and the unstated conjunction-closure of the application classes, which is related but not identical to the concrete false statement I identify here.","tokens_in":18497,"tokens_out":15363,"duration_ms":159695,"concrete_test":"Enumerate C for d=2: all conjunctions of the three nonzero linear functionals x1, x2, and x1+x2 on F2^2, together with the empty conjunction (constant 1). For U={10,01,11}, list the restrictions of the following functions: constant 0, the three singletons {10},{01},{11}, the three 2-point affine lines {10,11},{01,11},{01,10}, and constant 1; they are respectively 000, 100, 010, 001, 101, 011, 110, 111. If all eight occur, dimVC C≥3, so Corollary 6.8's value d=2 is wrong. Then recompute dimh C for d=2, for example with Macaulay2 using the suboplex ideal of this 12-function class, to determine whether a corrected equality is dimVC=dimh=3 or some other rank of the affine-subspace poset.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central resolution theorem appears sound: the cone argument in Theorem 4.3 uses intersection-closure only to ensure A is in P, and Theorem 4.4 follows from the standard cellular-resolution Betti formula. The load-bearing problem is the advertised parity application. Corollary 6.8 identifies the class C of conjunctions of parity functions on F2^d with C(P_M), where P_M is the lattice of flats of the matroid on all vectors of F2^d. This identification is wrong: a homogeneous parity function ℓ has 1-set ℓ^{-1}(1), an affine hyperplane, not the linear hyperplane ℓ^{-1}(0); the flat lattice consists of linear subspaces. For example, the conjunction x1∧x2 on F2^2 has 1-set {11}, which is not a subspace. The class C is the family of intersections of affine hyperplanes, i.e. affine subspaces (plus the empty set and, with the empty conjunction, all of F2^d), not the subspace-indicator class C(P_M). Consequently Corollary 6.8 is false as stated: for d=2, C contains the empty set, the three singletons {10},{01},{11}, the three affine lines {10,11},{01,11},{01,10}, and the whole space (empty conjunction), so U={10,01,11} is shattered and dimVC C≥3, contradicting the claimed value d=2. The matroid theorem Corollary 5.11 remains correct for flat-indicator classes; the defect is in the translation to parity functions. The paper must either correct the parity/affine identification, updating the dimension to the appropriate rank of the affine-subspace poset, or remove Corollaries 6.8 and 6.9.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":18882,"tokens_out":56557,"duration_ms":532966,"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":[{"comment":"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.","section":"6.3, Corollary 6.8; also 5.1, Example 5.9"},{"comment":"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.","section":"6.3, Corollaries 6.8 and 6.9"}],"minor_comments":[{"comment":"The expression '2k (d choose k)' appears without a superscript in the statement and proof; it should read '2^k (d choose k)'.","section":"6.2, Theorem 6.3"},{"comment":"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.","section":"3, Definition 3.2"},{"comment":"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.","section":"6.3, Remark 6.10"}],"recommendation":"major_revision","confidential_remarks":"The core commutative algebra (Theorems 4.3, 4.4, and 5.5) appears sound, and the paper contains several attractive examples and applications. The problem is confined to the parity-function application, but it is a genuine false statement in a headline application. The fix is straightforward: replace the all-vectors matroid by the homogenized affine matroid and change the dimension from d to d+1, then reconcile Corollaries 6.8 and 6.9. I recommend major revision rather than rejection, because the central algebraic claims are defensible and the error is repairable within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things. First, the algebraic engine is real: the paper constructs an explicit cellular free resolution of I*_C(P) from the order complex of an intersection-closed poset P, and for interval Cohen-Macaulay posets it gets pure Betti numbers as Möbius numbers. The proofs are sound; the cone argument in Theorem 4.3 uses intersection-closure exactly where needed, and Theorem 4.4 follows from the standard cellular-resolution Betti formula. This is a genuine advance over Yan's earlier homological dimension, which did not give resolutions or Betti numbers. The matroid and polyhedral corollaries are clean and correctly derived.\n\nSecond, the advertised VC-dimension application to parity functions is broken. Example 5.9 and Corollary 6.8 identify the flat lattice of the all-vectors matroid over F2 with conjunctions of parity functions. That identification confuses 1-sets with 0-sets: a homogeneous linear functional has 1-set an affine hyperplane {ℓ=1}, not a linear hyperplane {ℓ=0}. Conjunctions of parity functions therefore cut out affine subspaces, not linear subspaces. For d=2, the class shatters {10,01,11}, so dimVC C = 3, not 2. Corollary 6.8 is false as stated. This is a real flaw, but it is contained in the application section; it does not touch Theorems 4.3, 4.4, or 5.5. Corollary 6.9, on the other hand, survives: the Veronese embedding includes the constant coordinate y_∅ = 1, so the flats correspond to affine algebraic sets, and the class of conjunctions of degree-≤k polynomials really is the flat-indicator class. The stress-test note is right about 6.8 but overreaches by bundling 6.9.\n\nThe k-CNF/CSP bounds are looser; they rely on an unstated semilattice observation, but they look workable. The core paper is worth a serious referee; the author should fix the parity translation, either by replacing the matroid with the affine-subspace poset and updating the dimensions, or by removing that application.","headline":"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.","tokens_in":61,"tokens_out":18760,"would_cite":true,"duration_ms":780728,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["13D02","13F55","05E45"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["function classes","free resolutions","order complexes","intersection-closed posets","multigraded Betti numbers","Möbius functions","VC dimension","matroids"],"falsifier":"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.","tokens_in":18273,"feed_emoji":"🧮","tokens_out":12913,"duration_ms":121026,"temperature":0.7,"pith_summary":"Boolean function classes are families of 0/1-valued functions on a finite set, and their VC dimension controls how much data a learner needs. This paper shows that for classes arising from intersection-closed posets, the algebraic ideal encoding the class has a free resolution shaped by the poset's order complex. Consequently the multigraded Betti numbers of that ideal are computed by reduced homologies of interval order complexes, and for interval Cohen-Macaulay posets they become Möbius numbers. The same machine feeds the known inequality $\\dim_{\\mathrm{VC}} C \\le \\dim_h C$, yielding sharp or near-sharp VC bounds for k-CNFs, matroids, and polyhedral complexes.","feed_headline":"An order complex resolves every intersection-closed function class","feed_subtitle":"The same complex turns Betti numbers into bounds on how much data a learner needs.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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)."],"supporting_citations":[{"why":"Introduces the suboplex ideal $I_C$, its Alexander dual $I^*_C$, and the inequality $\\dim_{\\mathrm{VC}} C \\le \\dim_h C$ that motivates the resolution.","marker":"[Yan17]"},{"why":"Supplies the lcm-labeled cellular resolution construction, the acyclicity criterion for such complexes, and the theorem expressing Betti numbers as reduced homology of subcomplexes.","marker":"[MS05]"},{"why":"Provides the link criterion for Cohen-Macaulay simplicial complexes used to detect interval Cohen-Macaulay posets.","marker":"[Rei76]"},{"why":"Gives Philip Hall's theorem equating the reduced Euler characteristic of a truncated order complex with the Möbius function.","marker":"[Rot64]"},{"why":"Surveys the shellability facts (subintervals of shellable posets are shellable, shellability implies Cohen-Macaulay) applied to matroids and polyhedral complexes.","marker":"[Wac07]"},{"why":"Supplies the VC-dimension lower bound for k-CNFs that the paper's homological upper bound matches.","marker":"[KV94]"}],"fun_headline_variants":["One order complex resolves every intersection-closed class","Pure Betti numbers from order complexes","Order complexes turn Betti numbers into VC bounds","A cellular resolution for all intersection-closed classes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["One order complex resolves every intersection-closed class","Pure Betti numbers from order complexes","Order complexes turn Betti numbers into VC bounds","A cellular resolution for all intersection-closed classes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000643,"raw_usage":{"total_tokens":2938,"prompt_tokens":909,"completion_tokens":2029,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":525,"completion_tokens_details":{"reasoning_tokens":1972}},"tokens_in":525,"tokens_out":2029,"duration_ms":17784,"temperature":1.0,"reasoning_tokens":1972,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:05:41.553911+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}