OctoInformBeta

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

The descending ranks (6.2): M0M_0 and M1M_1 put copies of QQ at the even and at the odd vertices of a double ray

The ray matroids of QQ admit no independent cover.

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

Let DD be a set, for the counterexample the countable set of pairs (m,f)(m, f) with f:{0,1}m→{0,1}f \colon \{0,1\}^m \to \{0,1\}, and let QQ be a matroid on E0=L⊔R=D×{L,R}E_0 = L \sqcup R = D \times \{L, R\}, where LL and RR are the left and the right copy of DD. The ground set E=ℤ×DE = \mathbb{Z} \times D is spread over a double ray whose vertices are the integers and whose edges are the bundles en={n}×De_n = \{n\} \times D, the bundle ene_n joining nn to n+1n+1; the central bundle is e−1e_{-1}, between −1-1 and 00. For p∈{0,1}p \in \{0, 1\}, the vertices of class pp are the integers congruent to pp modulo 22, and VpV_p is their set.✦

At a vertex nn the inward bundle, toward e−1e_{-1}, is ein(n)e_{\mathrm{in}(n)}, and the outward bundle is eout(n)e_{\mathrm{out}(n)}, where in(n)={n,n<0,n−1,n≥0,out(n)={n−1,n<0,n,n≥0.\mathrm{in}(n) = \begin{cases} n, & n < 0,\\ n - 1, & n \ge 0, \end{cases} \qquad \mathrm{out}(n) = \begin{cases} n - 1, & n < 0,\\ n, & n \ge 0. \end{cases}(1)✦ The placement of E0E_0 at nn is the map πn:E0→E\pi_n \colon E_0 \to E that puts LL on the inward and RR on the outward bundle at nn: πn(d,L)=(in(n),d),πn(d,R)=(out(n),d).\pi_n(d, L) = (\mathrm{in}(n), d), \qquad \pi_n(d, R) = (\mathrm{out}(n), d).(2)✦

For each class pp, the map φp:Vp×E0→E\varphi_p \colon V_p \times E_0 \to E given by φp(v,x)=πv(x)\varphi_p(v, x) = \pi_v(x) is a bijection.✦ The ray matroid MpM_p of QQ is the matroid on EE that is the image under φp\varphi_p of the direct sum of copies QvQ_v of QQ, one for each vertex vv of class pp: Mp=φp(⨁v∈VpQv).M_p = \varphi_p\Bigl(\bigoplus_{v \in V_p} Q_v\Bigr).(3)✦

The question is whether EE has an independent cover by M0M_0 and M1M_1: a set I∈ℐ(M0)I \in \mathcal{I}(M_0) and a set J∈ℐ(M1)J \in \mathcal{I}(M_1) with I∪J=EI \cup J = E, where ℐ(M)\mathcal{I}(M) is the family of independent sets of a matroid MM.

Let 𝒰\mathcal{U} be an ultrafilter on DD and ρ\rho a rank assigning to each subset of DD an ordinal below 𝔠\mathfrak{c}, the continuum taken as its initial ordinal. A subset of DD is large when it belongs to 𝒰\mathcal{U}.

Slices and the Rank Step

The left slice XLX_L and the right slice XRX_R of a set X⊆E0X \subseteq E_0 are the subsets of DD given by XL={d∈D:(d,L)∈X},XR={d∈D:(d,R)∈X}.X_L = \{d \in D : (d, L) \in X\}, \qquad X_R = \{d \in D : (d, R) \in X\}.(4)

The independent sets of QQ satisfy a rank step: if a set X⊆E0X \subseteq E_0 is independent in QQ and its left slice XLX_L is large, then D\XR∈𝒰andρ(D\XR)<ρ(XL).D \setminus X_R \in \mathcal{U} \qquad\text{and}\qquad \rho(D \setminus X_R) < \rho(X_L).(5)✦

The Parts at the Vertices

The part An(I)A_n(I) of a set I⊆EI \subseteq E at a vertex nn is the subset of E0E_0 that πn\pi_n places in II when nn is even and outside II when nn is odd: An(I)=πn−1(I)(n even),An(I)=πn−1(E\I)(n odd).A_n(I) = \pi_n^{-1}(I) \quad (n \text{ even}), \qquad A_n(I) = \pi_n^{-1}(E \setminus I) \quad (n \text{ odd}).(6)✦ The slices of II at nn are the slices An(I)LA_n(I)_L and An(I)RA_n(I)_R of this part.✦

The double ray has a right ray, with the vertices 0,1,2,…0, 1, 2, \dots, and a left ray, with the vertices −1,−2,…-1, -2, \dots; on each ray the kkth vertex vkv_k, for k≥0k \ge 0, is kk on the right ray and −k−1-k-1 on the left ray, so that each ray is numbered outward from the central bundle.✦

The Claim

Theorem 1. Let QQ, 𝒰\mathcal{U} and ρ\rho be as above, and let M0M_0 and M1M_1 be the ray matroids of QQ. If a set I⊆EI \subseteq E is independent in M0M_0, then E\I∉ℐ(M1).E \setminus I \notin \mathcal{I}(M_1).(7)✦ If a set II is independent in M0M_0 and a set JJ is independent in M1M_1, then I∪J≠E.I \cup J \neq E.(8)✦

In the paper, the result reads: an independent covering by M0M_0 and M1M_1 gives an independent partition, at each vertex nn the assigned elements are independent in the copy QnQ_n, and, starting from the large side of the central bundle and moving outward, ρ(xk)≥ρ(uk)>ρ(yk)≥ρ(xk+1)\rho(x_k) \ge \rho(u_k) > \rho(y_k) \ge \rho(x_{k+1}), an infinite descending sequence of ordinals, with xkx_k, uku_k and yky_k the paper’s sets along the ray.

What Is Checked

The claim is stated over an arbitrary set DD, a matroid QQ on D×{L,R}D \times \{L, R\} with an ultrafilter 𝒰\mathcal{U} on DD and a rank ρ\rho, and the ray matroids (3) of QQ, built through the placements (2) and the bijections φp\varphi_p.

About the parts at the vertices: if I⊆EI \subseteq E is independent in M0M_0 and E\IE \setminus I is independent in M1M_1, then An(I)∈ℐ(Q)for every n∈ℤ.A_n(I) \in \mathcal{I}(Q) \quad \text{for every } n \in \mathbb{Z}.(9)✦

For every set I⊆EI \subseteq E, the slices at the two ends of the central bundle satisfy A−1(I)L=D\A0(I)L,A_{-1}(I)_L = D \setminus A_0(I)_L,(10)✦ and those at the two ends of the bundle between vkv_k and vk+1v_{k+1}, on either ray and for every k≥0k \ge 0, satisfy Avk+1(I)L=D\Avk(I)R.A_{v_{k+1}}(I)_L = D \setminus A_{v_k}(I)_R.(11)✦