OctoInformBeta

OpenAI preprint, September 2026 · Introduction · §1

Theorem 1.1: Finite complexes of dimension d≥3d\geq 3 with growing vertex sets and uniform expansion below the top dimension

Bounded-degree coboundary expanders in every dimension.

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

A finite simplicial complex XX on a finite vertex set VV is a family of subsets of VV that contains the empty set and every singleton and is closed under taking subsets.✦ The set X(i)X(i) of ii-dimensional faces of a simplicial complex XX is the set given by (1); an ii-dimensional face of XX is an element of X(i)X(i). X(i)={σ∈X:|σ|=i+1}.X(i)=\{\sigma\in X:|\sigma|=i+1\}.(1)✦

A complex XX is pure of dimension ss if X(s)X(s) is nonempty and every face of XX is contained in a face in X(s)X(s).✦ A complex XX is connected if VV is nonempty and any two vertices can be joined by an edge path in its one-skeleton.✦

The top-dimensional degree deg⁡s(v)\deg_s(v) of a vertex v∈Vv\in V is the number of ss-dimensional faces containing vv, as in (2). deg⁡s(v)=|{τ∈X(s):v∈τ}|.\deg_s(v)=\bigl|\{\tau\in X(s):v\in\tau\}\bigr|.(2)✦

Cochains and Weights

Let 𝔽2\mathbb F_2 denote the field with two elements. An ii-cochain ff on a simplicial complex XX with coefficients in 𝔽2\mathbb F_2 is a function from X(i)X(i) to 𝔽2\mathbb F_2; the cochain space is (3). Ci(X;𝔽2)={f:X(i)→𝔽2}.C^i(X;\mathbb F_2)=\{f:X(i)\longrightarrow\mathbb F_2\}.(3) The simplicial coboundary δi:Ci(X;𝔽2)→Ci+1(X;𝔽2)\delta_i:C^i(X;\mathbb F_2)\to C^{i+1}(X;\mathbb F_2) is the linear map defined by (4). (δif)(τ)=∑σ∈X(i)σ⊆τf(σ),τ∈X(i+1).(\delta_i f)(\tau) =\sum_{\substack{\sigma\in X(i)\\\sigma\subseteq\tau}}f(\sigma), \qquad \tau\in X(i+1).(4)

The space B0(X;𝔽2)B^0(X;\mathbb F_2) consists of the constant functions on X(0)X(0); in positive degree the coboundary space is the image specified in (5). Bi(X;𝔽2)=im⁡δi−1,i≥1.B^i(X;\mathbb F_2)=\operatorname{im}\delta_{i-1},\qquad i\geq 1.(5)✦

For nonnegative integers ss and ii, the normalized weight ws,i(σ)w_{s,i}(\sigma) of an ii-dimensional face σ\sigma is its number of ss-dimensional cofaces divided by the total number of incidences between these two dimensions, as specified in (6). ws,i(σ)={|{τ∈X(s):σ⊆τ}|(s+1i+1)|X(s)|,i≤s and X(s)≠⌀,0,otherwise.w_{s,i}(\sigma)= \begin{cases} \displaystyle \frac{\bigl|\{\tau\in X(s):\sigma\subseteq\tau\}\bigr|} {\binom{s+1}{i+1}|X(s)|}, & i\leq s\text{ and }X(s)\ne\varnothing,\\[6pt] 0,&\text{otherwise}. \end{cases}(6)✦ The weighted support norm ∥f∥s,i\|f\|_{s,i} of an ii-cochain ff is the sum of its nonzero face weights in (7). ∥f∥s,i=∑σ∈X(i)f(σ)≠0ws,i(σ).\|f\|_{s,i}=\sum_{\substack{\sigma\in X(i)\\f(\sigma)\ne 0}} w_{s,i}(\sigma).(7)✦

The weighted distance dist⁡s,i(f,A)\operatorname{dist}_{s,i}(f,A) of an ii-cochain ff on a simplicial complex XX with coefficients in 𝔽2\mathbb F_2 to a set A⊆Ci(X;𝔽2)A\subseteq C^i(X;\mathbb F_2) is the real number given by the infimum in (8) when AA is nonempty, and is zero when AA is empty. dist⁡s,i(f,A)=infa∈A∥f−a∥s,i,A≠⌀.\operatorname{dist}_{s,i}(f,A) =\inf_{a\in A}\|f-a\|_{s,i},\qquad A\ne\varnothing.(8)✦

The Claim

Theorem 1. Fix an integer d≥3d\geq 3. There are an integer D≥0D\geq 0, a real number ε>0\varepsilon>0 and a sequence (Xm)m≥0(X_m)_{m\geq 0} of finite simplicial complexes such that each XmX_m is connected and pure of dimension dd, and the conditions in (9) hold, with all degrees and norms taken in XmX_m. |Xm(0)|→∞as m→∞,deg⁡d(v)≤Dfor every m≥0 and every vertex v of Xm,εdist⁡d,i(f,Bi(Xm;𝔽2))≤∥δif∥d,i+1for every m≥0,0≤i<d,f∈Ci(Xm;𝔽2).\begin{gathered} |X_m(0)|\longrightarrow\infty\quad\text{as }m\longrightarrow\infty,\\ \deg_d(v)\leq D \quad\text{for every }m\geq 0\text{ and every vertex }v\text{ of }X_m,\\ \varepsilon\,\operatorname{dist}_{d,i} \bigl(f,B^i(X_m;\mathbb F_2)\bigr) \leq\|\delta_i f\|_{d,i+1} \quad\text{for every }m\geq 0,\ 0\leq i<d, \ f\in C^i(X_m;\mathbb F_2). \end{gathered}(9)✦

What Is Checked

The claim is stated over finite simplicial complexes with 𝔽2\mathbb F_2 cochains, the normalized face weights of (6) and the coboundary spaces of (5), including the constant functions in degree zero.