OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

Theorem 1.1: Two self-dual matroids M0,M1M_0, M_1 on a countably infinite set EE with I0∪I1≠EI_0 \cup I_1 \neq E whenever IiI_i is independent in MiM_i

A counterexample to the infinite matroid packing/covering conjecture.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Matroids are the infinite matroids of Bruhn, Diestel, Kriesell, Pendavingh and Wollan, given by their bases with the maximality axiom. For a matroid MM, M*M^* is its dual and M↾XM \upharpoonright X its restriction to a set XX; a matroid MM with ground set SS is self-dual when M*=MM^* = M. The contraction M.CM.C of a matroid MM onto a set CC is the matroid M.C=(M*↾C)*.M.C = (M^* \upharpoonright C)^*.(1)✦

A packing/covering partition of two matroids M0M_0 and M1M_1 with a common ground set SS is a partition of SS into sets PP and CC such that M0↾PM_0 \upharpoonright P and M1↾PM_1 \upharpoonright P have disjoint spanning sets P0P_0 and P1P_1, and M0.CM_0.C and M1.CM_1.C have independent sets C0C_0 and C1C_1 whose union is CC: S=P⊔C,P0∩P1=∅,C0∪C1=C.S = P \sqcup C, \qquad P_0 \cap P_1 = \emptyset, \qquad C_0 \cup C_1 = C.(2)✦ The infinite matroid packing/covering conjecture asserts that every pair of matroids with a common ground set has a packing/covering partition.

The Double Ray

Let DD be the set of all Boolean functions, each paired with its number of variables✦, and let EE be the product of the integers with DD: D={(m,f):m≥0,f:{0,1}m→{0,1}},E=ℤ×D.D = \{(m, f) : m \ge 0,\ f \colon \{0,1\}^m \to \{0,1\}\}, \qquad E = \mathbb{Z} \times D.(3)✦

Over a set AA, the set ℤ×A\mathbb{Z} \times A is a double ray: its vertices are the integers, and its edges are the bundles en={n}×Ae_n = \{n\} \times A, the bundle ene_n joining the vertices nn and n+1n + 1. The set EE is the double ray over DD.✦ For p∈{0,1}p \in \{0, 1\}, the vertices of parity pp are the integers v≡p(mod⁡2)v \equiv p \pmod 2.✦

Let QQ be a matroid on A×{L,R}A \times \{L, R\}, two copies of AA labelled LL and RR. At a vertex vv, the map ϕv\phi_v from A×{L,R}A \times \{L, R\} to ℤ×A\mathbb{Z} \times A lays the two copies on the bundles ev−1e_{v-1} and eve_v that meet at vv: for a∈Aa \in A, ϕv(a,L)={(v−1,a)if v≥0,(v,a)if v<0,ϕv(a,R)={(v,a)if v≥0,(v−1,a)if v<0.\phi_v(a, L) = \begin{cases} (v - 1, a) & \text{if } v \ge 0,\\ (v, a) & \text{if } v < 0, \end{cases} \qquad \phi_v(a, R) = \begin{cases} (v, a) & \text{if } v \ge 0,\\ (v - 1, a) & \text{if } v < 0. \end{cases}(4)✦ The ray matroid Rayp(Q)\mathrm{Ray}_p(Q) of parity pp is the matroid on ℤ×A\mathbb{Z} \times A obtained from the direct sum of copies of QQ, one at each vertex vv of parity pp, by carrying the copy at vv through ϕv\phi_v: Rayp(Q)=ϕ(⨁v≡pQ),ϕ(v,x)=ϕv(x).\mathrm{Ray}_p(Q) = \phi\Bigl(\bigoplus_{v \equiv p} Q\Bigr), \qquad \phi(v, x) = \phi_v(x).(5)✦

The Claim

Theorem 1.

  1. The set EE is countably infinite, and there are self-dual matroids M0M_0 and M1M_1, each with ground set EE, such that every independent set I0I_0 of M0M_0 and every independent set I1I_1 of M1M_1 satisfy I0∪I1≠E,I_0 \cup I_1 \neq E,(6)✦ and the pair M0,M1M_0, M_1 has no packing/covering partition.

  2. Let AA be a set and QQ a matroid on A×{L,R}A \times \{L, R\}. If II is independent in Ray0(Q)\mathrm{Ray}_0(Q) and JJ is independent in Ray1(Q)\mathrm{Ray}_1(Q), then I∪J≠ℤ×A.I \cup J \neq \mathbb{Z} \times A.(7)✦

  3. Let M0M_0 and M1M_1 be self-dual matroids, each with ground set SS, and suppose the pair has a packing/covering partition. Then there are an independent set J0J_0 of M0M_0 and an independent set J1J_1 of M1M_1 with J0∪J1=S.J_0 \cup J_1 = S.(8)✦

In the paper, the result reads: in Zermelo-Fraenkel set theory with the axiom of choice (ZFC) there are a countably infinite set EE and two infinite matroids M0M_0, M1M_1 on EE with Mi*=MiM_i^* = M_i on the same labelled ground set, such that I0∪I1≠EI_0 \cup I_1 \neq E for every independent set I0I_0 of M0M_0 and I1I_1 of M1M_1; the pair has no packing/covering partition, and consequently the infinite matroid packing/covering conjecture is false.

What Is Checked

The claim is stated over infinite matroids given by bases with the maximality axiom, with their duals, restrictions and self-duality, the contraction (1), the packing/covering partition (2), the set DD and the double ray EE of (3), and the ray matroids Rayp(Q)\mathrm{Ray}_p(Q) of (5), laid out by the maps ϕv\phi_v of (4). The library proves that for each parity pp the map ϕ\phi is a bijection from the disjoint union of copies of A×{L,R}A \times \{L, R\}, one at each vertex of parity pp, onto ℤ×A\mathbb{Z} \times A.✦