OctoInformBeta

OpenAI preprint, September 2026 · §6. Two matroids on a double ray (proof of Theorem 1.1) · §6

The double ray, the copies Q_n and the sums M_0, M_1: The sums M0M_0, M1M_1 of copies of QQ at even and odd vertices: independence and bases tested copy by copy, self-dual when QQ is

Summing copies of a matroid along a double ray.

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

Two matroids M0M_0 and M1M_1, one for each parity of vertex, live on a double ray. Its vertices are the integers, and between the vertices kk and k+1k+1 runs the bundle ek={k}×De_k = \{k\} \times D, a copy of the countable set DD of pairs (m,f)(m, f) with f:{0,1}m→{0,1}f \colon \{0,1\}^m \to \{0,1\}. So the vertex nn meets the bundles en−1e_{n-1} and ene_n, and the ground set E=ℤ×DE = \mathbb{Z} \times D is the disjoint union of all bundles. The bundle e−1e_{-1}, between −1-1 and 00, is the central one: at each vertex, the inward bundle is the one nearer to e−1e_{-1}, and the outward bundle is the other. A matroid QQ on E0=D×{L,R}E_0 = D \times \{L, R\}, whose two sides are LL and RR, is copied onto the two bundles at every vertex, with LL on the inward bundle and RR on the outward one, and the copies at the vertices of one parity are summed into a matroid on EE.

The library makes this construction for any set α\alpha in place of DD, on the ground set ℤ×α\mathbb{Z} \times \alpha with bundles ek={k}×αe_k = \{k\} \times \alpha, and for any matroid QQ on α×{L,R}\alpha \times \{L, R\}.

Vertices and Components

Fix a set α\alpha. A parity pp is 00 or 11. The set VpV_p of vertices of parity pp is the set of integers nn with n≡p(mod⁡2)n \equiv p \pmod 2.✦

At a vertex n∈ℤn \in \mathbb{Z}, the bundle position is the map s↦β(n,s)s \mapsto \beta(n, s) from the sides {L,R}\{L, R\} to ℤ\mathbb{Z} that sends LL to the index of the inward bundle at nn and RR to the index of the outward one: β(n,L)={n,n<0,n−1,n≥0,β(n,R)={n−1,n<0,n,n≥0.\beta(n, L) = \begin{cases} n, & n < 0,\\ n - 1, & n \ge 0, \end{cases} \qquad \beta(n, R) = \begin{cases} n - 1, & n < 0,\\ n, & n \ge 0. \end{cases}(1)✦

For a vertex v∈Vpv \in V_p, the component map at vv is the map κv:α×{L,R}→ℤ×α\kappa_v \colon \alpha \times \{L, R\} \to \mathbb{Z} \times \alpha given by κv(a,s)=(β(v,s),a)\kappa_v(a, s) = (\beta(v, s), a).✦ The trace of a set X⊆ℤ×αX \subseteq \mathbb{Z} \times \alpha on the copy at vv is its preimage κv−1(X)\kappa_v^{-1}(X), a subset of α×{L,R}\alpha \times \{L, R\}.

The component bijection Φp\Phi_p of parity pp is the map from Vp×(α×{L,R})V_p \times (\alpha \times \{L, R\}) to ℤ×α\mathbb{Z} \times \alpha that sends a pair (v,x)(v, x), with v∈Vpv \in V_p and x∈α×{L,R}x \in \alpha \times \{L, R\}, to κv(x)\kappa_v(x): Φp:Vp×(α×{L,R})→ℤ×α,Φp(v,x)=κv(x).\Phi_p \colon V_p \times (\alpha \times \{L, R\}) \to \mathbb{Z} \times \alpha, \qquad \Phi_p(v, x) = \kappa_v(x).(2)✦

For a matroid MM, E(M)E(M) is its ground set, ℐ(M)\mathcal{I}(M) the family of its independent sets and ℬ(M)\mathcal{B}(M) the family of its bases.

The Claim

Definition 1. Let QQ be a matroid on α×{L,R}\alpha \times \{L, R\} and pp a parity. The ray matroid MpM_p is the matroid on ℤ×α\mathbb{Z} \times \alpha that is the image under Φp\Phi_p of the direct sum of copies of QQ, one for each vertex of parity pp: Mp=Φp(⨁v∈VpQ).M_p = \Phi_p\Bigl(\bigoplus_{v \in V_p} Q\Bigr).(3)✦ If QQ has the whole of α×{L,R}\alpha \times \{L, R\} as ground set, then E(Mp)=ℤ×α.E(M_p) = \mathbb{Z} \times \alpha.(4)✦ For every set I⊆ℤ×αI \subseteq \mathbb{Z} \times \alpha, I∈ℐ(Mp)⇔κv−1(I)∈ℐ(Q) for every v∈Vp,I \in \mathcal{I}(M_p) \iff \kappa_v^{-1}(I) \in \mathcal{I}(Q) \text{ for every } v \in V_p,(5)✦ and for every set B⊆ℤ×αB \subseteq \mathbb{Z} \times \alpha, B∈ℬ(Mp)⇔κv−1(B)∈ℬ(Q) for every v∈Vp.B \in \mathcal{B}(M_p) \iff \kappa_v^{-1}(B) \in \mathcal{B}(Q) \text{ for every } v \in V_p.(6)✦ If QQ has the whole of α×{L,R}\alpha \times \{L, R\} as ground set and Q*=QQ^* = Q, then Mp*=Mp.M_p^* = M_p.(7)✦

In the paper, the result reads: with bundles en={n}×De_n = \{n\} \times D and E=ℤ×DE = \mathbb{Z} \times D, QnQ_n is a copy of QQ on en−1∪ene_{n-1} \cup e_n whose side LL is the inward bundle, ene_n for n≤−1n \le -1 and en−1e_{n-1} for n≥0n \ge 0, and whose side RR is the outward one, and M0=⨁n evenQnM_0 = \bigoplus_{n \text{ even}} Q_n and M1=⨁n oddQnM_1 = \bigoplus_{n \text{ odd}} Q_n are self-dual on the same labels; there α=D\alpha = D, and QnQ_n is the copy of QQ at the vertex nn.

What Is Checked

The claim is stated over a set α\alpha, a matroid QQ on α×{L,R}\alpha \times \{L, R\} and a parity pp, through the vertices VpV_p, the bundle positions (1), the component maps κv\kappa_v, the component bijection (2) and the ray matroid (3); the ground set (4) assumes that QQ has the whole of α×{L,R}\alpha \times \{L, R\} as ground set, and the self-duality (7) assumes this and Q*=QQ^* = Q.

The library proves that Φp\Phi_p is one-to-one and onto ℤ×α\mathbb{Z} \times \alpha.