AXIOM MATH / SEPTEMBER 2026
Matroid log-concavity
in Lean.
An explanatory companion to the strongest Mason inequality and the Heron–Rota–Welsh theorem.
About this writeup
This is a mathematical companion to two accepted Lean formalizations: the strongest Mason inequality for independent sets, and the Heron–Rota–Welsh theorem for characteristic polynomials. It explains the statements and gives a guided route through the arguments used by the accepted code. The hyperlinks point to named declarations in immutable source snapshots.
The exposition was prepared after the formal proofs were accepted. It is a guide to those artifacts, rather than the blueprint from which they were originally produced. The original mathematical theorems are credited below; no claim of a new theorem is made.
Independence and log-concavity
A matroid consists of a ground set and a collection of subsets called independent sets. The empty set is independent; every subset of an independent set is independent; and if and are independent with , some element of can be added to while preserving independence. The last property is the exchange axiom.
Linear independence is an example. So is acyclicity: take the edges of a graph as the ground set, and its forests as independent sets. A matroid’s rank function records the largest size of an independent subset of .
A nonnegative sequence is log-concave if
Where the entries are positive, this means the ratios do not increase with . It is a constraint on how the sequence grows and falls. It does not mean that the entries themselves decrease.
The two theorems concern different sequences attached to the same finite matroid. Mason counts independent sets. Heron–Rota–Welsh studies coefficients of a polynomial formed from the rank function. Both conclusions are log-concavity, but Mason’s binomial normalization makes its assertion stronger than ordinary log-concavity of the counts.
A small example
The uniform matroid has five elements, with precisely the sets of size at most three declared independent. The independent-set counts in sizes are
Dividing each count by the number of all subsets of that size gives
This is the sequence in the strongest Mason inequality. Its entries are the probabilities that uniformly chosen subsets of each size are independent.
The same matroid has characteristic polynomial
Its unsigned coefficients in ascending degree are . The two nontrivial Heron–Rota–Welsh inequalities read and . These are a different sequence and a different theorem.
Two proof routes
The accepted Mason formalization uses a combinatorial atlas: a family of quadratic forms constructed from counts of ordered independent extensions. A local-to-global argument transports a reverse Cauchy–Schwarz inequality through the family. Evaluating the root form gives the normalized counting inequality.
The accepted Heron–Rota–Welsh formalization first rewrites coefficients as sums of Möbius weights on flats. It constructs an explicit quadratic form from incidences between adjacent ranks and proves the required Hodge-index inequality using localization and a weighted graph Laplacian. A coloop reduction transfers the result from the reduced characteristic polynomial to the original one.
The common linear-algebra theme is a symmetric bilinear form with at most one positive direction. For a vector with , nonpositivity on the hyperplane gives
Indeed, apply nonpositivity to and expand. The difficult work is constructing the right form, proving its sign property, and identifying these three pairings with consecutive terms of the desired sequence.
Sources and scope
Brändén and Huh’s Lorentzian polynomials contains the strongest Mason inequality as Theorem 4.14. Anari, Liu, Oveis Gharan, and Vinzant proved it independently in Log-Concave Polynomials III. The accepted code here uses the kind of combinatorial atlas method described by Chan and Pak in Introduction to the combinatorial atlas.
Adiprasito, Huh, and Katz established the Heron–Rota–Welsh theorem for arbitrary matroids in Hodge theory for combinatorial geometries. These results form part of the broader geometric approach to combinatorial log-concavity highlighted in June Huh’s 2022 Fields Medal citation.
The artifacts establish the two specified matroid inequalities. They do not constitute formalizations of all tropical geometry, all Lorentzian polynomial theory, or the entire Hodge–Riemann theory for matroid Chow rings.
Both submissions passed the official and wide comparator lanes in Axiom Proofs. The verification page records the accepted versions and their provenance. Source repositories are private to AxiomMath, so the Lean and workflow links require repository access; this explanatory site and PDF are publicly readable.
Strong Mason
The theorem
Let be a matroid on a finite ground set of cardinality . Write
The strongest form of Mason’s conjecture, now a theorem, says that the sequence , for , is log-concave. Thus, whenever ,
The normalization matters: is the probability that a uniformly chosen -element subset is independent. The theorem controls the shape of these probabilities, giving a stronger conclusion than ordinary log-concavity of the counts .
The accepted Lean statement clears the binomial denominators:
This formulation remains meaningful beyond the interior of the sequence. No representability, simplicity, looplessness, or connectedness assumption is imposed. The matroid may have loops, parallel elements, or rank zero. The exported result is branden_huh_strongest_mason.
Brändén and Huh prove this result as Theorem 4.14 of Lorentzian polynomials; Anari, Liu, Oveis Gharan, and Vinzant independently proved the strongest inequality. The formal development presented here takes a combinatorial-atlas route, closely related to the method explained by Chan and Pak. Its central objects are finite matrices of extension counts and a reverse Cauchy–Schwarz inequality.
The counting convention
The benchmark represents by a finite type and explicitly assumes that the matroid’s ground set is the entire type. Consequently, counts actual ground elements. Its independent-set count filters the finite collection of all -element subsets by the predicate of matroid independence.
The atlas development uses a second, set-based cardinality expression. independentSetCount_eq_challenge proves exact equality between these definitions. This is a substantive interface check: the final theorem counts the subsets specified by the benchmark, with the same cardinality and independence predicate.
For the main argument, fix . If , the desired inequality is immediate. Otherwise, a positive count supplies an independent set of cardinality . This witness will justify the positivity assumptions needed by the matrix induction. See strong_mason_finite.
1. Replace subsets by ordered continuations
For a finite prefix , let count ordered strings of distinct new elements whose union with is independent. The recursion is
Repetition is excluded at each insertion. Let be the collection of independent supersets of with cardinality . Double counting a distinguished newly added element proves
The factorial records the possible orders of the new elements. The recursive definition makes choosing the first letter an exact identity, which later becomes an identity between matrix entries. These facts are formalized in continuation and continuation_eq_factorial_mul_card_extensionLevel.
Matroid augmentation also proves that whenever is independent and . Here need not contain : augmentation supplies a sufficiently large independent extension of .
2. Put the strongest normalization into the weights
Define a coefficient depending on the final cardinality:
The denominator is positive because . Adding the first element increases the prefix size by one and decreases the remaining length by one. Their sum stays fixed, so the weighted counts satisfy the same first-letter recursion.
At the empty prefix, the three relevant values are
This single exceptional weight supplies the extra ground-set factor in the strongest Mason inequality. See masonCoeff and weightedContinuation.
3. Arrange the counts into an atlas of matrices
Introduce an extra letter which leaves a prefix unchanged. A ground letter inserts , unless it is already present. For depth , form a matrix indexed by : its entry is if reading from validly produces , and zero otherwise. Dependent extensions also give zero through the continuation count.
The matrices are symmetric and entrywise nonnegative. Reading one additional letter gives a child matrix. Commutativity of insertion and cyclic symmetry of three-letter insertion produce the inheritance identities used below. The construction is atlasMatrix.
For any such matrix, write and . The formal predicate Hyperbolic means
This reverse Cauchy–Schwarz property is the target of the matrix induction. It is defined explicitly and proved for the atlas matrices.
4. Establish hyperbolicity at depth one
Suppose is independent and . Its feasible one-element extensions split into parallel classes: two distinct feasible elements belong to the same class when adjoining both makes the prefix dependent. Matroid augmentation proves transitivity of this relation.
The depth-one matrix has star–star entry , star–feasible entries , zero entries within a parallel class, and a common coefficient between different classes. Here unless , when . Infeasible rows vanish.
For a vector , let be the sum of its coordinates in parallel class , and set . Expanding gives
On the hyperplane , ordinary Cauchy–Schwarz gives , where is the number of classes. If , nonpositivity follows immediately. In the exceptional case,
which again proves on that hyperplane. A quadratic-form lemma converts this into hyperbolicity. Dependent prefixes and empty feasible sets are handled separately. See atlasMatrix_one_hyperbolic.
5. Pass from children to parents
The linear-algebra engine considers a symmetric nonnegative parent , a positive vector , and hyperbolic children satisfying
Child reverse Cauchy–Schwarz yields
Positive diagonal normalization turns this into for a symmetric nonnegative matrix having a positive fixed vector . A maximum-ratio argument bounds its eigenvalues by ; the energy inequality gives . Thus every positive eigenvalue is . A strictly positive hub column forces that eigenspace to be one-dimensional. The spectral theorem then makes nonpositive on , establishing hyperbolicity and transferring it back to .
This argument is hyperbolic_of_local_quadratic_data.
For the atlas, apply it to
with ground-letter weights and star weight . Remove infeasible coordinates, whose rows and columns are identically zero. The independent witness ensures positivity of the needed continuations, including the star hub. The insertion identities provide inheritance and the weighted quadratic identity exactly.
Finally, hyperbolicity passes to the endpoint as . Induction from depth one reaches . See hyperbolic_right_endpoint and atlasMatrix_hyperbolic_iter.
6. Evaluate the root and clear the factors
Let be one on ground coordinates and zero at the star, and let select the star. At the root , expanding finite sums gives
All these counts are nonnegative, so root hyperbolicity yields
Canceling positive factorial and denominator factors gives
The evaluation is normalized_inequality_of_root_hyperbolic. Binomial recurrences convert this into the benchmark’s exact statement. If , both and vanish, so both sides are zero. The final adapter proves this boundary case explicitly: branden_huh_strongest_mason.
Scope and provenance
The accepted development formalizes this matroid inequality through combinatorial atlas matrices. It does not formalize the full theory of Lorentzian polynomials or tropical geometry. Mathlib supplies general infrastructure, including matroids, finite cardinalities, real symmetric spectral theory, and limits; the submitted modules assemble the missing argument.
Submission issue #15 passed both Axiom Proofs comparator lanes on September 1, 2026. The frozen submission is commit f0629e6b9c80a8aedef6a923892150735f56570a; its archived proof comprises 13 Lean source files and uses Lean 4.33.0. The verification record reports only the standard foundational dependencies propext, Classical.choice, and Quot.sound.
The recorded final worker used Codexiom with openai/gpt-5.6-sol-pro. It received a preloaded, audited AxiomMath atlas development, checked the dependency chain and counting conventions, completed the exact benchmark adapter, and removed warnings. Its recorded runtime and model cost therefore describe that final run, not the entire preceding development. Human involvement is recorded as theorem selection, orchestration, review requirements, and acceptance criteria. The accepted metadata and frozen proof blueprint preserve this distinction.
References
- Petter Brändén and June Huh, Lorentzian polynomials, Annals of Mathematics 192 (2020), 821–891. Theorem 4.14 gives the strongest Mason inequality.
- Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant, Log-Concave Polynomials III: Mason’s Ultra-Log-Concavity Conjecture for Independent Sets of Matroids (2018), an independent proof through complete log-concavity.
- Swee Hong Chan and Igor Pak, Introduction to the combinatorial atlas (2022), especially the local-to-global framework and its application to Mason’s inequality.
- AxiomMath, frozen proof blueprint and audit record, and acceptance workflow.
Heron–Rota–Welsh
The theorem
Let be a matroid on a finite ground set , with rank function . Its characteristic polynomial is
Write . The Heron–Rota–Welsh theorem says that these unsigned coefficients are log-concave:
The Lean statement uses coefficients in ascending degree. This reverses the indexing often used in the literature, without changing the inequality. It quantifies over every finite matroid whose ground set is the whole ambient finite type; there is no representability assumption. Loops are allowed, and coefficients beyond the polynomial’s degree are zero. Formal entry point.
Adiprasito, Huh, and Katz proved the theorem using the Hodge–Riemann relations for matroid Chow rings. Their 2018 paper treats arbitrary matroids; the earlier Huh–Katz paper establishes the result for realizable matroids through intersection theory.
The accepted formal proof follows an explicit route through weighted bilinear forms on the lattice of flats. It proves the Hodge-index inequality needed for the coefficient sequence. It does not formalize the complete Chow-ring construction, hard Lefschetz theorem, or full Hodge–Riemann package of the original paper.
1. Replace subsets by flats
A flat is a subset closed under matroid closure. Every subset has a unique closure, so the defining sum for can be grouped by flats. For a flat , define
For a loopless matroid, the proof identifies with , the Möbius function of the flat lattice. Its cumulative sums are at the bottom flat and elsewhere, which characterizes this Möbius function. Consequently,
The next ingredient is the sign rule . Thus the nonnegative weight can replace signed Möbius weights whenever the rank is fixed. The proof establishes this sign rule using cancellation after adjoining a distinguished element to a flat, followed by induction on rank.
Sources: closure-fiber weights, Möbius identification, alternating signs.
2. Identify the reduced coefficients
For a nonempty loopless matroid of rank , set and
Set for . This extension makes the consecutive-coefficient formulas below meaningful at every ; it also agrees with the avoiding-flat sum, since the top flat contains and no flat has rank greater than .
Fix an element . The proof obtains two descriptions of the same number:
The first formula comes from the relation between the characteristic and reduced characteristic polynomials. The second uses closure with : a flat avoiding is sent to , increasing its rank by one. The relevant Möbius cancellation identity gives the equality of the weighted sums. This is a weighted identity, not an assertion that the two collections of flats have equal cardinality.
These formulas are the bridge from polynomial coefficients to the explicit bilinear form below. Reduced polynomial coefficient identity, avoiding-flat formula, containing-flat formula.
3. Build a form on adjacent ranks
Let be a flat, and let . On real-valued functions on the flats, define
Here means that covers : no flat lies strictly between them. The last term is a weighted graph energy along cover relations. All ingredients are finite sums, ranks, containment, and the weights already defined.
Take , and let indicate that , while indicates that . The coefficient identities give
For example, an avoiding flat has exactly one cover containing , namely its closure after adjoining . Its contribution to the graph energy therefore cancels its contribution on the lower diagonal. This gives the last pairing identity. The mixed identity also uses the Möbius-weighted cancellation from the preceding step.
Sources: definition of the form, containing-vector pairing, avoiding-vector self-pairing.
4. Establish the Hodge-index inequality
The central theorem asserts that, whenever ,
This reverse Cauchy–Schwarz inequality expresses that the form has at most one positive direction. It is proved for every rank and every ceiling flat containing a chosen element. All-ranks theorem.
At rank one, call the rank-one flats points and the rank-two flats lines. Each pair of distinct points lies on a unique line, and a line’s weight is its number of points minus one. Expanding the form produces a square of the total point sum minus a sum of squares indexed by lines. On the hyperplane where the point sum is zero, the form is therefore nonpositive. Elementary bilinear algebra gives reverse Cauchy–Schwarz. Atomic nonpositivity.
The inductive step studies the deformation
with reference vector when and otherwise. Only flats of ranks contribute. For each flat in this three-rank window, the proof constructs a local form. At the lower rank the required inequality reduces to an atomic interval calculation; at the middle rank it is an explicit two-functional calculation; at the upper rank it follows from the induction hypothesis applied below that flat. Local forms.
5. Assemble the local inequalities
The passage from those local calculations to is the main assembly argument. The local forms obey exchange identities and decompose the global form. They also have positive norms at .
From these norms, the proof constructs a positive diagonal form such that is a weighted graph Laplacian after rescaling coordinates by . Its quadratic form is a sum of nonnegative edge energies. The cover graph on the three-rank window is connected, so its Laplacian equation is solvable for every forcing term of total mass zero. Connectivity, Laplacian solvability.
If , the resulting forcing term has zero total mass. A solution supplies a vector with . Summing the local reverse Cauchy–Schwarz inequalities gives
Together with , this implies . Applying to then yields
Thus is nonpositive on its primitive hyperplane. The proof derives reverse Cauchy–Schwarz for and then sends to zero. In Lean, the last passage is an explicit small-parameter argument bounding the error terms of a quadratic polynomial, rather than an appeal to a spectral continuity theorem. This completes the rank induction for .
6. Recover log-concavity
Apply the all-ranks inequality to the containing and avoiding indicators from Step 3. When , it gives immediately
If , the same inequality follows from nonnegativity. The formal implementation packages the form, the two vectors, the pairing identities, and primitive nonpositivity as a finite Hodge witness, then applies a general coefficient reduction. Incidence witness, reduced log-concavity.
To return to , adjoin one coloop: let . Direct-sum multiplicativity gives
Reduced log-concavity for is therefore exactly the desired coefficient inequality for , after reversing indices. The proof also handles the boundary cases: beyond rank the upper-degree coefficient vanishes; if has a loop, subsets cancel in pairs and the entire characteristic polynomial is zero. This coloop argument includes the empty ground set. Coloop identity, final reduction.
Formalization and provenance
The accepted overlay contains 14 Lean files, totaling 26,918 lines. That is the size of the preserved submission, including supporting developments and alternative constructions; it is not a measurement of a minimized dependency closure.
The acceptance record dates to September 5, 2026. Both the official and wide Comparator lanes passed submission #23. The recorded environment uses Lean 4.33.0 and mathlib commit 6f1ef4e5dd604a435bddba4747b13970cd65d2a1.
The submitted provenance describes a supervised Codexiom run lineage involving several models. It credits GPT-6 Astra at maximum reasoning effort with the decisive incidence construction and final proof, building on earlier coefficient reductions and exploration. It records human involvement in theorem selection, orchestration, recovery, model switching, and acceptance criteria, with no manually constructed Lean proof text. These are provenance claims in the submission record; the mathematical acceptance evidence is the checked theorem and the successful Comparator runs.
For historical background and the original Chow-ring proof, see Adiprasito–Huh–Katz, Hodge theory for combinatorial geometries, Annals of Mathematics 188 (2018), 381–452. The explanation above follows the accepted Lean declarations and makes no claim that this particular presentation is a new mathematical proof.