Lemma 12 — Cycle replacement with zero augmentation
OpenTwoReLULayers.DepthCollapse.Supplement.zero_augmentation_replacementmachine-learningp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1polytope-geometryrelu-networks
Let , choose arbitrary orientations of the simplex edges, and let be a cycle with . There is a chain satisfying all of
Here denotes the face direction condition, with a separate facet direction witness for each nonzero basis term. The preservation condition concerns the same chosen and is conditional; it imposes no face direction assumption on the input. This permits the zero-augmentation requirement to be met while retaining the geometric realization.
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: k ≥ 2 → k = 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 12, p.18; the same witness preserves face directions conditionally. -/
theorem zero_augmentation_replacement (n k : ℕ) (o : EdgeOrientations n)
(x : C n (k + 2)) (hx : IsCycle o x) :
∃ x' : C n (k + 2), IsCycle o x' ∧ epsilon x' = 0 ∧ rho o x' = rho o x ∧
(FaceDirection o x → FaceDirection o x') := 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 12.