Lemma 13 — Lift the next simplex boundary
OpenTwoReLULayers.DepthCollapse.Supplement.simplex_boundary_liftmachine-learningp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1polytope-geometryrelu-networks
Let , with arbitrary edge orientations in ambient dimensions and . Suppose that some satisfies
There is a chain such that
The input face direction condition is on the boundary of . In the output the degree remains , but the ambient dimension and the cardinality of a witnessing simplex facet increase by one. This is the boundary-lifting statement used in the simplex construction.
Differences from the source:
- encoding: Rational polytopes in oriented subspaces, with Minkowski differences modulo translations and lower-dimensional terms → Finite rational vertex and ordered-frame presentation of the same geometric quotient; reason: The presentation imposes exactly those geometric relations; facet boundaries are evaluated on a chosen representative, with no extra hypothesis
- encoding: Group algebra tensored with the exterior power of the formally labeled simplex edges → Finite rational support on lattice points and increasing edge-label subsets; reason: This is its canonical basis presentation; dependent geometric edge vectors are not identified
- encoding: n ≥ 2 → n = m+2, m : ℕ; reason: Equivalent enumeration of every permitted natural dimension or degree; avoids dependent transports from natural subtraction
- encoding: Simplex vertices labeled 1,…,n+1 → Simplex vertices labeled 0,…,n; reason: Only labels change; actual vertices, edges and facet cardinalities are the same
Preamble
import Definitions.Def_TwoReLULayers_DepthCollapse_Supplement_Realization
Formal statement
namespace TwoReLULayers.DepthCollapse.Supplement
/-- Lemma 13, p.18. Ambient n+2 ranges over every n of the source with n≥2.
The input condition is imposed on d(x), not on x. -/
theorem simplex_boundary_lift (n : ℕ)
(o : EdgeOrientations (n + 2)) (o' : EdgeOrientations (n + 3))
(h : ∃ x : C (n + 2) (n + 1), rho o x = simplexClass (n + 2) ∧
FaceDirection o (dC o x)) :
∃ y : C (n + 3) (n + 1), IsCycle o' y ∧ FaceDirection o' y ∧
rho o' y = dP (n + 3) (n + 3) (simplexClass (n + 3)) := by sorry
end TwoReLULayers.DepthCollapse.Supplement
Source
Kilian Rueß, Florestan Brunck, Christoph Hertrich, Jack Stade, Amir Yehudayoff, Two ReLU layers is all you need, STOC 2027 submission #980 (October 2026). Use this pinned PDF and its own labels; no arXiv version is asserted. p. 18, Lemma 13.