Introduction
The ubiquity and success of neural networks as a model of computation motivates studying the capabilities of their architectures. This study raises familiar complexity-theoretic questions, like what is the class of functions they can compute, at what depth, with how many gates, etc.?
This work investigates the role of depth in neural networks. On the one hand, deep learning is one of the major successes of modern computer science. On the other hand, classical approximation theorems dating back to the late 1980s show that, for many activation functions including ReLU, a single hidden layer suffices to approximate any continuous function arbitrarily well on a compact domain [10 , 19 , 24 ] . Although various explanations for the power of compositions have been proposed [5 , 26 ] , a quantitative understanding of the role of depth remains incomplete [20 , 17 ] .
The role of depth has been studied from several perspectives. One line of work investigates depth-width tradeoffs in expressivity: can additional layers reduce the resources needed to represent or approximate a function [2 , 12 , 32 ] ? Another asks whether depth can provide advantages for training [29 ] . Perhaps the most fundamental question, however, is whether deeper networks can represent functions that shallower networks cannot. Until now, this question has remained open.
We focus on neural networks that use the ReLU(x x x ) = = = max { 0 , x } \max\{0, x\} max { 0 , x } activation function, which are among the most widely used ones in practice [13 , 20 ] . A ReLU network with k k k hidden layers (and depth k + 1 k + 1 k + 1 ) is traditionally defined as the alternating composition
T ( k ) ∘ ReLU ∘ T ( k − 1 ) ∘ ⋯ ∘ ReLU ∘ T ( 1 ) ∘ ReLU ∘ T ( 0 ) T^{(k)} \circ\operatorname{ReLU} \circ T^{(k-1)} \circ\cdots\circ\operatorname{ReLU} \circ T^{(1)} \circ\operatorname{ReLU} \circ T^{(0)} T ( k ) ∘ ReLU ∘ T ( k − 1 ) ∘ ⋯ ∘ ReLU ∘ T ( 1 ) ∘ ReLU ∘ T ( 0 )
where T ( i ) T^{(i)} T ( i ) is an affine map between two Euclidean spaces and ReLU stands for entry-wise application.
ReLU networks compute continuous and piecewise linear (CPWL) functions. These are continuous functions that are affine on each cell of a finite polyhedral partition of the input Euclidean space. Conversely, every CPWL function can be computed by a ReLU network (see e.g. [2 ] ). Their ability to capture nonlinear behavior while retaining a simple local affine structure makes CPWL functions useful beyond neural networks. For example, they are central to finite element methods [16 ] , and their structure enables exact verification of stability conditions in robotic control [11 ] .
For a ring R ⊆ R R \subseteq\mathbb{R} R ⊆ R , denote by C P W L n ( R ) \mathrm{CPWL}_n(R) CPWL n ( R ) the space of CPWL functions whose affine pieces have coefficients in R R R . Denote by R e L U n , k ( R ) \mathrm{ReLU}_{n,k}(R) ReLU n , k ( R ) the subset of C P W L n ( R ) \mathrm{CPWL}_n(R) CPWL n ( R ) representable by ReLU networks with k k k hidden layers, and weights and biases in R R R . The obvious inclusions are
R e L U n , 0 ( R ) ⊆ R e L U n , 1 ( R ) ⊆ R e L U n , 2 ( R ) ⊆ ⋯ ⊆ C P W L n ( R ) . (1) \mathrm{ReLU}_{n,0}(R) \subseteq\mathrm{ReLU}_{n,1}(R) \subseteq\mathrm{ReLU}_{n,2}(R) \subseteq\cdots\subseteq\mathrm{CPWL}_n(R). \tag*{(1)} ReLU n , 0 ( R ) ⊆ ReLU n , 1 ( R ) ⊆ ReLU n , 2 ( R ) ⊆ ⋯ ⊆ CPWL n ( R ) . (1)
Our main results work when R R R is any field containing Q \mathbb{Q} Q . We often write C P W L n \mathrm{CPWL}_n CPWL n and R e L U n , k \mathrm{ReLU}_{n,k} ReLU n , k for C P W L n ( Q ) \mathrm{CPWL}_n(\mathbb{Q}) CPWL n ( Q ) and R e L U n , k ( Q ) \mathrm{ReLU}_{n,k}(\mathbb{Q}) ReLU n , k ( Q ) respectively.
The main goal of this work is understanding the inclusions in the chain (1) . Wang and Sun [34 ] identified a key structural result; see also [17 , 4 ] for alternative, more geometric proofs. They showed that
MAX n ( x 1 , … , x n ) : = max { x 1 , … , x n } \operatorname{MAX}_n(x_1,\ldots,x_n) := \max\{x_1,\ldots,x_n\} MAX n ( x 1 , … , x n ) := max { x 1 , … , x n }
is complete for C P W L n − 1 ( R ) \mathrm{CPWL}_{n-1}(\mathbb{R}) CPWL n − 1 ( R ) with respect to depth. That is, every function f ∈ C P W L n ( R ) f \in\mathrm{CPWL}_n(\mathbb{R}) f ∈ CPWL n ( R ) can be expressed as a finite sum
f ( x ) = ∑ i σ i MAX n + 1 ( A i ( x ) ) (2) f(x) = \sum_i \sigma_i \operatorname{MAX}_{n+1}(A_i(x)) \tag*{(2)} f ( x ) = i ∑ σ i MAX n + 1 ( A i ( x )) (2)
where A i : R n → R n + 1 A_i:\mathbb{R}^n \to\mathbb{R}^{n+1} A i : R n → R n + 1 is an affine map and σ i ∈ { ± 1 } \sigma_i \in\{\pm1\} σ i ∈ { ± 1 } . The geometric proof by [4 ] for the universality of MAX n + 1 \operatorname{MAX}_{n+1} MAX n + 1 relies on the fact that MAX n + 1 \operatorname{MAX}_{n+1} MAX n + 1 is the support function of a simplex, and every polytope can be triangulated into simplices.
The first inclusion in (1) is trivially strict because R e L U n , 0 ( R ) \mathrm{ReLU}_{n,0}(\mathbb{R}) ReLU n , 0 ( R ) is precisely the set of affine functions. Mukherjee and Basu [27 ] showed that the second inclusion is strict for n ≥ 3 n \geq3 n ≥ 3 because MAX 3 ∈ R e L U 3 , 2 ( R ) \operatorname{MAX}_3 \in\mathrm{ReLU}_{3,2}(\mathbb{R}) MAX 3 ∈ ReLU 3 , 2 ( R ) but MAX 3 ∉ R e L U 3 , 1 ( R ) \operatorname{MAX}_3 \notin\mathrm{ReLU}_{3,1}(\mathbb{R}) MAX 3 ∈ / ReLU 3 , 1 ( R ) . In the other direction, Arora, Basu, Mianjy, and Mukherjee [2 ] observed that (2) implies that the length of the chain is at most logarithmic:
C P W L n = R e L U n , k for k ≥ ⌈ log 2 ( n + 1 ) ⌉ . \mathrm{CPWL}_n = \mathrm{ReLU}_{n,k} \quad\text{for } k \geq\left\lceil\log_2(n+1) \right\rceil. CPWL n = ReLU n , k for k ≥ ⌈ log 2 ( n + 1 ) ⌉ .
The reason is that a divide-and-conquer network of depth ⌈ log 2 ( n + 1 ) ⌉ \left\lceil\log_2(n+1) \right\rceil ⌈ log 2 ( n + 1 ) ⌉ computes MAX n + 1 \operatorname{MAX}_{n+1} MAX n + 1 . Subsequently, Hertrich, Basu, Di Summa, and Skutella [17 ] conjectured that the length of the chain is exactly ⌈ log 2 ( n + 1 ) ⌉ \left\lceil\log_2(n+1) \right\rceil ⌈ log 2 ( n + 1 ) ⌉ . In other words, they conjectured that MAX n \operatorname{MAX}_n MAX n can not be computed by less than ⌈ log 2 ( n ) ⌉ \left\lceil\log_2(n) \right\rceil ⌈ log 2 ( n ) ⌉ hidden layers.
A series of works validated this conjecture in a variety of special cases. Haase, Hertrich, and Loho [15 ] proved the conjecture over the integers:
k < ⌈ log 2 ( n ) ⌉ ⇒ MAX n ∉ R e L U n , k ( Z ) . k < \left\lceil\log_2(n) \right\rceil\quad\Rightarrow\quad\operatorname{MAX}_n \notin\mathrm{ReLU}_{n,k}(\mathbb{Z}). k < ⌈ log 2 ( n ) ⌉ ⇒ MAX n ∈ / ReLU n , k ( Z ) .
Averkov, Hojny, and Merkert [3 ] extended the logarithmic lower bounds to rings of the form Z [ 1 / N ] \mathbb{Z}[1/N] Z [ 1/ N ] for an integer N > 0 N > 0 N > 0 . They showed that if a prime p p p does not divide N N N then
k < ⌈ log p ( n ) ⌉ ⇒ MAX n ∉ R e L U n , k ( Z [ 1 / N ] ) . k < \left\lceil\log_p(n) \right\rceil\quad\Rightarrow\quad\operatorname{MAX}_n \notin\mathrm{ReLU}_{n,k}(\mathbb{Z}[1/N]). k < ⌈ log p ( n ) ⌉ ⇒ MAX n ∈ / ReLU n , k ( Z [ 1/ N ]) .
There are more lower bounds for special classes of networks. Valerdi [33 ] proved the conjecture for input convex neural networks (ICNN), which was defined by Amos, Xu and Kolter [1 ] and studied in subsequent works (e.g. [7 , 8 , 9 , 6 , 18 ] ). Grillo, Hertrich, and Loho [14 ] proved an Ω ( log log n ) \Omega(\log\log n) Ω ( log log n ) lower bound for ReLU networks that “respect the singularities of MAX n \operatorname{MAX}_n MAX n ”.
The conjecture was, however, recently disproved by Bakaev, Brunck, Hertrich, Stade, and Yehudayoff [4 ] . They proved that
MAX 5 ∈ R e L U 5 , 2 \operatorname{MAX}_5 \in\mathrm{ReLU}_{5,2} MAX 5 ∈ ReLU 5 , 2
and concluded the asymptotic improvement
M A X n ∈ R e L U n , k for k = ⌈ log 3 ( n − 2 ) ⌉ + 1. \mathrm{MAX}_n \in\mathrm{ReLU}_{n,k} \qquad\text{for } k = \lceil\log_{3}(n-2) \rceil+ 1. MAX n ∈ ReLU n , k for k = ⌈ log 3 ( n − 2 )⌉ + 1.
Shortly after, computer-assisted constructions [28 ] showed that
M A X 12 ∈ R e L U 12 , 2 . \mathrm{MAX}_{12} \in\mathrm{ReLU}_{12,2}. MAX 12 ∈ ReLU 12 , 2 .
Again, this finite case can be converted into an improvement of the asymptotic bound from [4 ] , yielding
M A X n ∈ R e L U n , k for k = ⌈ log 6 ( n / 2 ) ⌉ + 1. \mathrm{MAX}_n \in\mathrm{ReLU}_{n,k} \qquad\text{for } k = \lceil\log_{6}(n/2) \rceil+ 1. MAX n ∈ ReLU n , k for k = ⌈ log 6 ( n /2 )⌉ + 1.
Our main result is that the entire depth hierarchy collapses to the second level, which is optimal by [27 ] . See Figure 1 for an illustration.
Figure 1. The depth hierarchy of ReLU networks collapses to its first 3 levels.
Theorem 1. For all n ≥ 1 n \ge1 n ≥ 1 and any field R ⊆ R R \subseteq\mathbb{R} R ⊆ R containing Q \mathbb{Q} Q ,
C P W L n ( R ) = R e L U n , 2 ( R ) . \mathrm{CPWL}_n(R) = \mathrm{ReLU}_{n,2}(R). CPWL n ( R ) = ReLU n , 2 ( R ) .
To prove our main result, it suffices to prove the inclusion
M A X n ∈ R e L U n , 2 ( Q ) \mathrm{MAX}_n \in\mathrm{ReLU}_{n,2}(\mathbb{Q}) MAX n ∈ ReLU n , 2 ( Q )
We provide two proofs of the inclusion. The first is abstract and uses the language of homological algebra. The second is concrete and is based on exact combinatorial cancellations.
We, in fact, show that there is a ReLU network with two hidden layers for M A X n \mathrm{MAX}_n MAX n over the rationals where the precision required is poly ( n ) \operatorname{poly}(n) poly ( n ) many bits. The lower bound from [3 ] says that such a network must divide by the product of all primes up to ≈ n \approx\sqrt{n} ≈ n , which requires precision of ≈ n \approx\sqrt{n} ≈ n many bits. The combinatorial proof requires division by n ! n! n ! , which is consistent with this barrier. As written, the homological algebra proof also uses division by n ! n! n ! , but this is not strictly necessary. What the homological proof actually uses is division by 2 k − 1 2^k-1 2 k − 1 for k = 1 , … , n k=1,\ldots,n k = 1 , … , n , which is consistent with the barrier by Fermat’s little theorem.
Building the Simplex
Because M A X n \mathrm{MAX}_n MAX n is positively homogeneous, we can assume that all biases in the network expressing it are zero, see [17 ] . Because M A X 2 ( x 1 , x 2 ) = x 1 + ReLU ( x 2 − x 1 ) \mathrm{MAX}_2(x_1,x_2)=x_1+\operatorname{ReLU}(x_2-x_1) MAX 2 ( x 1 , x 2 ) = x 1 + ReLU ( x 2 − x 1 ) , we can and will work with networks that use M A X 2 \mathrm{MAX}_2 MAX 2 gates instead of ReLU gates, also known as maxout networks.
There is a duality between computing functions with M A X 2 \mathrm{MAX}_2 MAX 2 networks and building formal Minkowski differences of polytopes using the two operations: Minkowski sums and convex hulls of a union (see e.g. [17 , 4 ] and references therein). This duality says that computing M A X n + 1 \mathrm{MAX}_{n+1} MAX n + 1 is equivalent to building the n n n -dimensional simplex Δ n \Delta_n Δ n . (There are n + 1 n+1 n + 1 vertices and the dimension is n n n .)
Computations with one hidden layer exactly correspond to differences of zonotopes , i.e. Minkowski sums of segments. Every zonotope can be decomposed into parallelepipeds ([31 Theorem (54)] ) so one hidden layer is actually captured by parallelepipeds ∑ i [ a i , b i ] \sum_i [a_i,b_i] ∑ i [ a i , b i ] . A general two-layer computation corresponds to the convex hull of two zonotopes.
Both of the constructions we describe use a particular class of two-layer components we call paramids . A paramid is the convex hull of an apex γ ∈ R n \gamma\in\mathbb{R}^n γ ∈ R n and a parallelepiped ∑ i [ a i , b i ] \sum_i [a_i,b_i] ∑ i [ a i , b i ] . For an example see Figure 2 . The support function of a paramid is thus of the form
Figure 2. A pyramid given as the pyramid over a two-dimensional parallelepiped B B B with apex q q q .
M A X 2 ( ⟨ γ , x ⟩ , ∑ i M A X 2 ( ⟨ a i , x ⟩ , ⟨ b i , x ⟩ ) ) \mathrm{MAX}_2\left(\langle\gamma,x\rangle,\sum_i \mathrm{MAX}_2(\langle a_i,x\rangle,\langle b_i,x\rangle)\right) MAX 2 ( ⟨ γ , x ⟩ , i ∑ MAX 2 (⟨ a i , x ⟩ , ⟨ b i , x ⟩) )
Paramids are the simplest two-layer polytopes and are thus a natural starting point to understand two-layer computations. Our results imply that R e L U n , 2 \mathrm{ReLU}_{n,2} ReLU n , 2 is spanned by support functions of paramids. Actually, there is a more direct way to see this (see § 5.1 ). Informally, every convex hull of two zonotopes can be expressed algebraically in terms of paramids.
Another natural idea is to work modulo lower-dimensional pieces. A CPWL function f : R n → R f:\mathbb{R}^n \to\mathbb{R} f : R n → R is said to be lower-dimensional if there is a non-zero direction v v v such that f ( x + t v ) = f ( x ) f(x+tv)=f(x) f ( x + t v ) = f ( x ) for all x ∈ R n x \in\mathbb{R}^n x ∈ R n and t ∈ R t \in\mathbb{R} t ∈ R . So if, for each n n n , we can write M A X n + 1 \mathrm{MAX}_{n+1} MAX n + 1 as a
M A X n + 1 = ∑ i c i h P i + R \mathrm{MAX}_{n+1}=\sum_i c_i h_{P_i}+R MAX n + 1 = i ∑ c i h P i + R
where each P i P_i P i is a paramid and the remainder R R R is a sum of lower-dimensional functions, then we are done by induction. The reason is that every lower-dimensional function is reducible to M A X n \mathrm{MAX}_n MAX n , which we already know how to compute.
Subdivisions give us a powerful tool in these arguments. If we can subdivide Δ \Delta Δ into pieces that can be computed in k k k hidden layers, then Δ \Delta Δ can be computed by k k k hidden layers. So subdivisions are “free” in the sense that they do not cost us anything in terms of depth. This follows from the following well-known inclusion-exclusion-like formula also known as valuation (see e.g. Lemma 6.1.1 in [30 ] or 5.20 in [25 ] ):
Lemma 2 (Valuation property). Suppose that a polytope X X X can be written as a union of polytopes X = A 1 ∪ ⋯ ∪ A k X = A_1 \cup\cdots\cup A_k X = A 1 ∪ ⋯ ∪ A k . Then,
X + ∑ ∅ ≠ S ⊆ { 1 , … , k } ∣ S ∣ e v e n ⋂ i ∈ S A i = ∑ S ⊆ { 1 , … , k } ∣ S ∣ o d d ⋂ i ∈ S A i , X + \sum_{\substack{\varnothing\ne S \subseteq\{1,\ldots,k\} \\ |S|\ \mathrm{even}}} \bigcap_{i\in S} A_i = \sum_{\substack{S\subseteq\{1,\ldots,k\} \\ |S|\ \mathrm{odd}}} \bigcap_{i\in S} A_i, X + ∅ = S ⊆ { 1 , … , k } ∣ S ∣ even ∑ i ∈ S ⋂ A i = S ⊆ { 1 , … , k } ∣ S ∣ odd ∑ i ∈ S ⋂ A i , where an empty polytope is interpreted as zero.
Our new goal is thus to build the simplex using paramids modulo sums of lower dimensional pieces. We present two such constructions. One construction proceeds by induction and uses the language of chain complexes and homological algebra. The second construction is based on a direct inclusion-exclusion formula.
Overview of the Homological Algebra Implementation
Let us start with some intuition. Imagine we already found a two-layer representation of Δ n \Delta_n Δ n . By restricting the representation to a facet, we get a two-layer representation of Δ n − 1 \Delta_{n-1} Δ n − 1 . Each facet has its own representation and the n + 1 n+1 n + 1 representations are somehow glued together coherently. What extra conditions does the boundary representation need to satisfy in order for it to extend to the n n n -simplex?
This type of “boundary filling” question naturally suggests using the framework of chain complexes and homology. A chain complex C ∙ C_\bullet C ∙ is a sequence of vector spaces C 0 , C 1 , C 2 , … C_0, C_1, C_2, \ldots C 0 , C 1 , C 2 , … equipped with linear boundary maps d : C k → C k − 1 d : C_k \to C_{k-1} d : C k → C k − 1 . The boundary map satisfies d 2 = 0 d^2 = 0 d 2 = 0 , which implies that the image of d : C k + 1 → C k d : C_{k+1} \to C_k d : C k + 1 → C k is a subspace of the kernel of d : C k → C k − 1 d : C_k \to C_{k-1} d : C k → C k − 1 . This leads to homology :
H k ( C ∙ ) = ker ( d : C k → C k − 1 ) / img ( d : C k + 1 → C k ) . H_k(C_\bullet) = \ker(d : C_k \to C_{k-1})/\operatorname{img}(d : C_{k+1} \to C_k). H k ( C ∙ ) = ker ( d : C k → C k − 1 ) / img ( d : C k + 1 → C k ) .
An element x x x satisfying d ( x ) = 0 d(x) = 0 d ( x ) = 0 is called a cycle (we use lowercase x x x to distinguish a formal element x x x of a chain complex from a polytope, which we would represent with a capital X X X ). An element x x x that is equal to d ( y ) d(y) d ( y ) for some y y y is called a boundary . The condition that d 2 = 0 d^2 = 0 d 2 = 0 says that every boundary is a cycle. The homology groups record which cycles are boundaries.
In § 4.1 , we define the chain complex P ∙ P_\bullet P ∙ of formal Minkowski differences of polytopes modulo lower dimensional polytopes. This is the main chain complex we care about, because it corresponds to ReLU networks by the duality discussed above. A central property for performing induction is that a top-dimensional class in P ∙ P_\bullet P ∙ is determined by its boundary. Namely, for chains of polytopes in R n \mathbb{R}^n R n , the map d : P n → P n − 1 d : P_n \to P_{n-1} d : P n → P n − 1 is injective. This is a consequence of known results (see Theorem 3). So if we can find some x ∈ P n x \in P_n x ∈ P n such that d ( x ) = d ( Δ n ) d(x) = d(\Delta_n) d ( x ) = d ( Δ n ) then we actually obtained Δ n \Delta_n Δ n .
We let Λ ∙ \Lambda_\bullet Λ ∙ be the subcomplex of P ∙ P_\bullet P ∙ generated by paramids. This chain complex corresponds to the subclass of two-layer ReLU networks we focus on. The homology of Λ ∙ \Lambda_\bullet Λ ∙ tells us a lot about the functions that can be represented in terms of paramids. If we can represent the n n n -simplex by paramids, then the boundary of the ( n + 1 ) (n+1) ( n + 1 ) -simplex is a cycle in Λ n \Lambda_n Λ n . By injectivity, the question of whether we can represent the ( n + 1 ) (n+1) ( n + 1 ) -simplex by paramids exactly asks whether this cycle is a boundary in Λ ∙ \Lambda_\bullet Λ ∙ .
The Minkowski sum relations in Λ ∙ \Lambda_\bullet Λ ∙ are complicated, and it is difficult to perform calculations in this complex directly. So we try to approximate Λ ∙ \Lambda_\bullet Λ ∙ with a chain complex that is easier to understand. We define a chain complex C ∙ C_\bullet C ∙ of parallelepipeds. There is a coning map ρ : C k → P k + 1 \rho: C_k \to P_{k+1} ρ : C k → P k + 1 that sends a parallelepiped X X X to the paramid with base X X X and apex at the origin. The image of ρ \rho ρ lies in the subcomplex Λ ∙ \Lambda_\bullet Λ ∙ of P ∙ P_\bullet P ∙ . A parallelepiped is a sum of intervals so it is zero in P k P_k P k for k ≥ 2 k \ge2 k ≥ 2 . The parallelepiped facet of a k k k -dimensional paramid is zero in P k − 1 P_{k-1} P k − 1 for k ≥ 3 k \ge3 k ≥ 3 . Because the base does not survive in Λ ∙ \Lambda_\bullet Λ ∙ , this means that ρ \rho ρ commutes with the boundary maps of C ∙ C_\bullet C ∙ and P ∙ P_\bullet P ∙ for k ≥ 2 k \ge2 k ≥ 2 .
Let us try to implement the inductive construction. We start with a chain of parallelepipeds x ∈ C n − 1 x \in C_{n-1} x ∈ C n − 1 such that ρ ( x ) \rho(x) ρ ( x ) is the n n n -simplex. We then create copies of x x x for each facet of the ( n + 1 ) (n+1) ( n + 1 ) -simplex to get a cycle x ′ ∈ C n − 1 x' \in C_{n-1} x ′ ∈ C n − 1 such that ρ ( x ′ ) \rho(x') ρ ( x ′ ) is the boundary of the n + 1 n+1 n + 1 simplex. If we can find some y ∈ C n y \in C_n y ∈ C n such that d ( y ) = x ′ d(y)=x' d ( y ) = x ′ , then ρ ( y ) \rho(y) ρ ( y ) satisfies
d ( ρ ( y ) ) = ρ ( d ( y ) ) = ρ ( x ′ ) = d ( Δ n + 1 ) . d(\rho(y))=\rho(d(y))=\rho(x')=d(\Delta_{n+1}). d ( ρ ( y )) = ρ ( d ( y )) = ρ ( x ′ ) = d ( Δ n + 1 ) .
Injectivity tells us that ρ ( y ) \rho(y) ρ ( y ) is the needed ( n + 1 ) (n+1) ( n + 1 ) -simplex.
This still does not explain how we find y ∈ C n y \in C_n y ∈ C n with d ( y ) = x ′ d(y)=x' d ( y ) = x ′ . We notice that not all cycles in C ∙ C_\bullet C ∙ are boundaries. Every boundary x x x in C ∙ C_\bullet C ∙ satisfies the augmentation condition , which says that x x x becomes 0 0 0 if we work modulo translations, because pairs of opposite faces of a parallelepiped give sign-reversed translates of each other after taking the boundary. But there are cycles in C ∙ C_\bullet C ∙ that do not have this property, see for example Figure 3 .
Figure 3. This triangle cannot be a boundary because it does not have the augmentation property.
We show that this is the only obstruction to filling boundaries in C ∙ C_\bullet C ∙ : any cycle with the augmentation condition is a boundary. The idea is that non-trivial homology in C ∙ C_\bullet C ∙ comes from relations among edge directions (see § 4.2.1 , or § 5.1.1 for a different perspective). For example, the triangle illustrated in Figure 3 is a cycle in C 1 C_1 C 1 that is not a boundary due to the relation t 1 + t 2 + t 3 = 0 t_1+t_2+t_3=0 t 1 + t 2 + t 3 = 0 , where t 1 t_1 t 1 , t 2 t_2 t 2 and t 3 t_3 t 3 are the edge vectors of the triangle.
We first illustrate our solution with the example of a regular hexagon, as shown in Figure 4 . Of the three edge directions t 1 t_1 t 1 , t 2 t_2 t 2 and t 3 t_3 t 3 , we choose the free generating set t 1 t_1 t 1 and t 2 t_2 t 2 . The two edges with direction t 3 t_3 t 3 can be connected by parallelepipeds, as shown in the right part of the figure. After subtracting the boundary of these parallelepipeds, the remaining boundary (bottom part of the figure) has only t 1 t_1 t 1 and t 2 t_2 t 2 as edge directions. Since t 1 t_1 t 1 and t 2 t_2 t 2 are independent, this remaining boundary can be filled.
Figure 4. The hexagon has the augmentation property, so it can be filled.
More generally, choose a set E E E of edge directions that have no relations among them. Let x ∈ C k x \in C_k x ∈ C k be a cycle with the augmentation property. Write X = x 0 + ⋯ + x k X=x_0+\cdots+x_k X = x 0 + ⋯ + x k , where x i x_i x i is a parallelepiped with i i i edge directions in E E E and k − i k-i k − i edge directions not in E E E . Letting x j x_j x j be the first non-zero term, we can find a boundary y = y j + ⋯ + y k y=y_j+\cdots+y_k y = y j + ⋯ + y k where y i y_i y i has i i i directions in E E E such that y j = x j y_j=x_j y j = x j . The j = 0 j=0 j = 0 case requires the augmentation condition. By subtracting y y y from x x x , we reduce the number of non-zero terms. Inductively, this implies that x x x is a boundary.
We are still not done. By induction, we constructed x x x such that ρ ( x ) \rho(x) ρ ( x ) is Δ n \Delta_n Δ n . To perform the induction step, we take x ′ x' x ′ to be copies of x x x for the facets of Δ n + 1 \Delta_{n+1} Δ n + 1 so that ρ ( x ′ ) = d ( Δ n + 1 ) \rho(x') = d(\Delta_{n+1}) ρ ( x ′ ) = d ( Δ n + 1 ) . We now want to fill x ′ x' x ′ , but in general it is not true that x ′ x' x ′ satisfies the augmentation condition.
The last ingredient is the doubling map S : C ∙ → C ∙ S : \mathbf{C}_{\bullet} \to\mathbf{C}_{\bullet} S : C ∙ → C ∙ . It takes a k k k -dimensional parallelepiped, scales it by a factor of 2, and then subdivides the scaled parallelepiped into 2 k 2^k 2 k copies of the original one. This is illustrated in Figure 5 . The element x ′ ′ = 2 k x ′ − S x ′ x'' = 2^k x' - Sx' x ′′ = 2 k x ′ − S x ′ is a cycle and it satisfies the augmentation property, so it can be filled. Geometrically, S S S is just a dilation by a factor of two:
Figure 5. The doubling map S S S scales a parallelogram in C k C_k C k by a factor of 2 2 2 , then subdivides the parallelepiped face into 2 k 2^k 2 k pieces, which are each a translated copy of the original parallelepiped face. In P ∙ P_\bullet P ∙ , this corresponds to scaling a paramid by 2 2 2 and then subdividing into 2 k 2^k 2 k pieces. But subdivision does not change a class in P ∙ P_\bullet P ∙ , so ρ ∘ S \rho\circ S ρ ∘ S is equal to 2 ρ 2\rho 2 ρ .
ρ ( S ( x ′ ) ) = 2 ρ ( x ′ ) . \rho(S(x')) = 2\rho(x'). ρ ( S ( x ′ )) = 2 ρ ( x ′ ) .
So, for n − 1 ≥ 2 n - 1 \ge2 n − 1 ≥ 2 ,
ρ ( x ′ ′ 2 n − 1 − 2 ) = ρ ( x ′ ) = d ( Δ n + 1 ) . \rho\left(\frac{x''}{2^{n-1}-2}\right) = \rho(x') = d(\Delta_{n+1}). ρ ( 2 n − 1 − 2 x ′′ ) = ρ ( x ′ ) = d ( Δ n + 1 ) .
Because x ′ ′ x'' x ′′ can be filled, there is y y y such that
d ( y ) = x ′ ′ 2 n − 1 − 2 . d(y) = \frac{x''}{2^{n-1}-2}. d ( y ) = 2 n − 1 − 2 x ′′ .
Finally, by injectivity, the induction is complete
ρ ( y ) = Δ n + 1 . \rho(y) = \Delta_{n+1}. ρ ( y ) = Δ n + 1 .
Overview of the Direct Implementation
The second proof we present is based on directly constructing a family of paramids, whose indicator functions exhibit a combinatorial cancellation when being summed up. Here the goal is to build the regular ( n − 1 ) (n - 1) ( n − 1 ) -simplex Δ = conv { e i : i ∈ [ n ] } \Delta= \operatorname{conv}\{e_i : i \in[n]\} Δ = conv { e i : i ∈ [ n ]} that sits inside the space { x ∈ R n : ∑ i x i = 1 } \{x \in\mathbb{R}^n : \sum_i x_i = 1\} { x ∈ R n : ∑ i x i = 1 } . There are two main ingredients to the construction. The first step is a comparably simple subdivision step, and the second step is where the non-trivial cancellation happens. By the valuation property (Theorem 20), it suffices to establish suitable identities up to lower-dimensional terms.
The first step is a geometric identity obtained by subdividing the simplex. Fix a nonempty subset R ⊊ [ n ] R \subsetneq[n] R ⊊ [ n ] . For v ∉ R v \notin R v ∈ / R , consider the simplex
Q v , R : = ( n − ∣ R ∣ ) Δ − v − ∑ i ∉ R ∪ { v } e i . Q_{v,R} := (n-|R|)\Delta_{-v}-\sum_{i\notin R\cup\{v\}} e_i. Q v , R := ( n − ∣ R ∣ ) Δ − v − i ∈ / R ∪ { v } ∑ e i .
where Δ − v = conv { e i : i ≠ v } \Delta_{-v}=\operatorname{conv}\{e_i:i\ne v\} Δ − v = conv { e i : i = v } is the facet opposite to e v e_v e v . The simplex Q v , R Q_{v,R} Q v , R is a dilation and translation of the facet Δ − v \Delta_{-v} Δ − v . Cone it with e v e_v e v to get the simplex
pyr e v ( Q v , R ) : = conv ( { e v } ∪ Q v , R ) . \operatorname{pyr}_{e_v}(Q_{v,R}) := \operatorname{conv}(\{e_v\}\cup Q_{v,R}). pyr e v ( Q v , R ) := conv ({ e v } ∪ Q v , R ) .
See Figure 6 for an illustration. The simplices pyr e v ( Q v , R ) \operatorname{pyr}_{e_v}(Q_{v,R}) pyr e v ( Q v , R ) for v ∉ R v\notin R v ∈ / R partition the simplex Δ \Delta Δ up to dilation and a translation, so the valuation property of support functions implies
Figure 6. On left, a partition of the simplex Δ \Delta Δ to simplices with R = { 3 } R = \{3\} R = { 3 } . On middle and right, the two pyramids pyr e v ( Q v , R ) \operatorname{pyr}_{e_v}(Q_{v,R}) pyr e v ( Q v , R ) for v = 1 v = 1 v = 1 and v = 2 v = 2 v = 2 .
MAX n = h Δ ≡ 1 n − ∣ R ∣ ∑ v ∉ R h pyr e v ( Q v , R ) . \operatorname{MAX}_n=h_\Delta\equiv\frac{1}{n-|R|}\sum_{v\notin R}h_{\operatorname{pyr}_{e_v}(Q_{v,R})}. MAX n = h Δ ≡ n − ∣ R ∣ 1 v ∈ / R ∑ h pyr e v ( Q v , R ) .
where ≡ \equiv ≡ means up to support functions of lower-dimensional pieces.
This gives a family of identities expressing the support function of the original simplex in terms of other simplices. These identities alone do not yield the two-layer representations because the pyramids pyr e v ( Q v , R ) \operatorname{pyr}_{e_v}(Q_{v,R}) pyr e v ( Q v , R ) are simplices rather than paramids.
The second weightier step replaces the simplices Q v , R Q_{v,R} Q v , R by parallelepipeds, which we cone with the apex e v e_v e v to pyramids. For each vertex v v v , we construct a family of parallelepipeds B v , π , M B_{v,\pi,M} B v , π , M indexed by permutations π \pi π and sets of positions M M M . Their signed indicator sum can be evaluated by viewing the input-coordinates as steps of a walk from 0 to 1. Inclusion–exclusion cancels all walks except the thermostat walks which rise below level 1 and fall above level 1. Their signed count turns out to be exactly ( − 1 ) s − 1 s ! ( n − 1 − s ) ! (-1)^{s-1}s!(n-1-s)! ( − 1 ) s − 1 s ! ( n − 1 − s )! , where s s s is the number of positive coordinates of the (generic) input. Binomial inversion expresses this count as a linear combination of the indicator sums of the auxiliary simplices Q v , R Q_{v,R} Q v , R :
∑ π ∑ M ( − 1 ) ∣ M ∣ 1 B v , π , M ≡ ( n − 1 ) ! ∑ R ( − 1 ) ∣ R ∣ − 1 ∣ R ∣ n − ∣ R ∣ 1 Q v , R . \sum_{\pi}\sum_{M}(-1)^{|M|}\mathbf{1}_{B_{v,\pi,M}}\equiv(n-1)!\sum_{R}\frac{(-1)^{|R|-1}|R|}{n-|R|}\mathbf{1}_{Q_{v,R}}. π ∑ M ∑ ( − 1 ) ∣ M ∣ 1 B v , π , M ≡ ( n − 1 )! R ∑ n − ∣ R ∣ ( − 1 ) ∣ R ∣ − 1 ∣ R ∣ 1 Q v , R .
This identity replaces the simplices Q v , R Q_{v,R} Q v , R by parallelepipeds B v , π , M B_{v,\pi,M} B v , π , M . See Figure 7 for illustrations.
Figure 7. At the top, the parallelepipeds B v , π , M B_{v,\pi,M} B v , π , M and the simplices Q v , R Q_{v,R} Q v , R together with their respective coefficients. At the bottom, the total sum is the same for the parallelepipeds and for the simplices.
But this identity by itself is not useful, because parallelepipeds are not enough. We need to cone the identity. Coning by e v e_v e v brings the needed pyramids to the left-hand side.
Summing over all vertices v v v and applying the geometric identities from the first step gives h Δ h_\Delta h Δ up to a lower-dimensional remainder term R n − 1 R_{n-1} R n − 1 :
M A X n = h Δ = ( − 1 ) n n ! ∑ v ∑ π ∑ M ( − 1 ) ∣ M ∣ h pyrev e v ( B v , π , M ) + R n − 1 . \mathrm{MAX}_n = h_\Delta= \frac{(-1)^n}{n!} \sum_v \sum_\pi\sum_M (-1)^{\lvert M\rvert} h_{\operatorname{pyrev}_{e_v}(B_{v,\pi,M})} + R_{n-1}. MAX n = h Δ = n ! ( − 1 ) n v ∑ π ∑ M ∑ ( − 1 ) ∣ M ∣ h pyrev e v ( B v , π , M ) + R n − 1 .
This gives a two-layer representation of M A X n \mathrm{MAX}_n MAX n , because all pyramids have support functions representable in two layers and the lower dimensional correction R n − 1 R_{n-1} R n − 1 is handled by induction.
Statement of AI Use
The authors verified the correctness and originality of all content, including references.
Homological Algebra Approach
The proof contains significant technical contributions from both AI models and the authors. We used ChatGPT Sol 5.6 and ChatGPT Astra 6.
The major contribution of the human authors is the overall proof strategy. The constructions of the chain complexes P ∙ P_\bullet P ∙ and Λ ∙ \Lambda_\bullet Λ ∙ , the idea to represent elements of Λ ∙ \Lambda_\bullet Λ ∙ as images of a coning map ρ : C ∙ → P ∙ \rho: C_\bullet\to P_\bullet ρ : C ∙ → P ∙ , and the injectivity of the top boundary (Theorem 3) are all authors’ ideas. AI was used throughout the process to check proofs and look for simplifications.
The largest contributions from AI are the proofs of Theorem 10 and the doubling map used to prove Theorem 11. The proof of Theorem 4 that appears in this paper is also due largely to AI, but another proof was previously known to the authors (see § 5.1.4 ).
Direct Combinatorial Approach
We used Claude Opus 5.5 extensively in developing the mathematical content of the combinatorial proof.
The outline of the proof was conceptualized by the authors. Our idea was to generalize the approach of subdividing into pyramids over zonotopes used in [4 ] to prove M A X 5 ∈ R e L U 5 , 2 \mathrm{MAX}_5 \in\mathrm{ReLU}_{5,2} MAX 5 ∈ ReLU 5 , 2 , handling lower-dimensional intersections by induction. We proposed combining this approach with ideas from the computational proof that M A X 12 ∈ R e L U 12 , 2 \mathrm{MAX}_{12} \in\mathrm{ReLU}_{12,2} MAX 12 ∈ ReLU 12 , 2 in [28 ] . Working interactively with the authors, the model implemented and carried out calculations in small dimensions, identified patterns in the resulting solutions and proposed the concrete constructions underlying Theorems 22 and 23 .
LLMs, primarily ChatGPT Sol 6.1, were also used to produce some of the TikZ figures.
Acknowledgments
The authors thank the members of the Neural Polytopes Zulip community. F.B. and A.Y. are supported by the DNRF Chair grant 20231101-28697. J.S. is supported by Starting Grant 1054-00032B from the Independent Research Fund Denmark under the Sapere Aude research career programme, and by the Carlsberg Foundation, grant CF24-1929.
Part 1. A Homological Algebra Proof
The Chain Complex of Polytopes
We start by defining a chain complex P ∙ n P^n_\bullet P ∙ n . Here P k n P^n_k P k n should represent “k k k -dimensional polytopes in Q n \mathbb{Q}^n Q n under Minkowski sum, modulo polytopes of dimension < k <k < k .”
For a finite-dimensional real vector space S S S , let V S V_S V S be the vector space of formal Minkowski-linear combinations of polytopes. Formally, V S V_S V S is the Q \mathbb{Q} Q -vector space spanned by pairs ( X , Y ) (X,Y) ( X , Y ) of polytopes, modulo the relation ( X , X ) = 0 (X,X)=0 ( X , X ) = 0 . Addition in V S V_S V S is given by Minkowski sum ( X 1 , Y 1 ) + ( X 2 , Y 2 ) = ( X 1 + X 2 , Y 1 + Y 2 ) (X_1,Y_1)+(X_2,Y_2)=(X_1+X_2,Y_1+Y_2) ( X 1 , Y 1 ) + ( X 2 , Y 2 ) = ( X 1 + X 2 , Y 1 + Y 2 ) . Multiplication by a constant is given by λ ( X , Y ) = ( λ X , λ Y ) \lambda(X,Y)=(\lambda X,\lambda Y) λ ( X , Y ) = ( λ X , λY ) when λ \lambda λ is positive, and λ ( X , Y ) = ( ∣ λ ∣ Y , ∣ λ ∣ X ) \lambda(X,Y)=(|\lambda|Y,|\lambda|X) λ ( X , Y ) = ( ∣ λ ∣ Y , ∣ λ ∣ X ) when λ \lambda λ is negative.
If S ′ S' S ′ is a subspace of S S S , then there is a natural inclusion V S ′ → V S V_{S'}\to V_S V S ′ → V S . We define V ~ S \widetilde V_S V S to be the quotient of V S V_S V S by the sum over all proper subspaces S ′ S' S ′ of S S S of V S ′ V_{S'} V S ′ .
Formally, for k ≥ 1 k\geq1 k ≥ 1 , we define P k n P^n_k P k n to be the direct sum of V ~ S \widetilde V_S V S over each oriented k k k -dimensional subspace S S S of Q n \mathbb{Q}^n Q n , with relations that reversing the orientation of a subspace corresponds to reversing sign in V S V_S V S .
P 0 n P^n_0 P 0 n will be mostly irrelevant for our calculations, but we define it here for completeness. For k = 0 k=0 k = 0 , P 0 n P^n_0 P 0 n is defined as a direct sum over Q n \mathbb{Q}^n Q n -indexed copies of Q \mathbb{Q} Q , modulo global translations. Note a translation induces a permutation of the summands. Here we are adding relations x − t ( x ) = 0 x-t(x)=0 x − t ( x ) = 0 , where x ∈ ⨁ Q n Q x\in\bigoplus_{\mathbb{Q}^n}\mathbb{Q} x ∈ ⨁ Q n Q and t t t is the linear map induced by the translation t t t permuting the factors.
We want to define the boundary d : P k + 1 n → P k n d:P^n_{k+1}\to P^n_k d : P k + 1 n → P k n . We start with k ≥ 1 k\geq1 k ≥ 1 . Now P k + 1 n P^n_{k+1} P k + 1 n is generated (as a Q \mathbb{Q} Q -vector space) by classes of form ( X , 0 ) (X,0) ( X , 0 ) with X X X a polytope in a k + 1 k+1 k + 1 -dimensional oriented subspace S ⊆ Q n S\subseteq\mathbb{Q}^n S ⊆ Q n . The boundary of ( X , 0 ) (X,0) ( X , 0 ) is defined as the sum over all unit vectors v ∈ S v\in S v ∈ S of the face of X X X in direction v v v , translated so that it lies in the subspace U U U orthogonal to v v v . The orientation A A A of U U U is chosen so that v ∧ A v\wedge A v ∧ A represents the orientation of S S S . Note that this term is zero in P k n P^n_k P k n unless v v v is orthogonal to a k k k -dimensional face of X X X , so only finitely many terms are non-zero.
When k = 1 k=1 k = 1 , P 1 n P^n_1 P 1 n is generated by classes of form ( X , 0 ) (X,0) ( X , 0 ) , with X X X a line segment in a 1 1 1 -dimensional space S S S . Let a a a and b b b be the endpoints of X X X , chosen so that the vector a − b a-b a − b induces the orientation on S S S . We set d ( ( X , 0 ) ) d((X,0)) d (( X , 0 )) to be the class of e a − e b e_a-e_b e a − e b , where e a e_a e a is the standard basis vector corresponding the a a a -component of ⨁ Q n Q \bigoplus_{\mathbb{Q}^n}\mathbb{Q} ⨁ Q n Q , and e b e_b e b is the one of the b b b component.
We need to check that d d d is well-defined and linear. Linearity is straightforward: if X X X and Y Y Y are polytopes, then the face of X + Y X+Y X + Y in direction v v v is the Minkowski sum of the faces of X X X and Y Y Y in direction v v v .
It is clear that d ( ( X , X ) ) = 0 d((X,X))=0 d (( X , X )) = 0 . If X X X is ≤ k \leq k ≤ k -dimensional and S S S is a k + 1 k+1 k + 1 -dimensional subspace containing X X X , then ( X , 0 ) (X,0) ( X , 0 ) is 0 0 0 in V ~ S \widetilde V_S V S , so we also need to check that d ( ( X , 0 ) ) = 0 d((X,0))=0 d (( X , 0 )) = 0 . If X X X is < k <k < k dimensional, then it has no k k k -dimensional faces, so d ( ( X , 0 ) ) d((X,0)) d (( X , 0 )) is 0 0 0 in P k n P^n_k P k n . If X X X is exactly k k k dimensional, then it has two identical k k k -dimensional faces in the two directions orthogonal to X X X . These induce opposite orientations of the same class in P k n P^n_k P k n , so they cancel, and again d ( X ) = 0 d(X)=0 d ( X ) = 0 . This shows that d d d is well-defined.
We need to check that d 2 = 0 d^2=0 d 2 = 0 . Let X X X be an n n n -dimensional polytope. Every n − 2 n-2 n − 2 -dimensional face F F F of X X X is a face of two n − 1 n-1 n − 1 dimensional faces Y 1 Y_1 Y 1 and Y 2 Y_2 Y 2 of X X X . When we take d 2 ( x ) d^2(x) d 2 ( x ) , a class corresponding to F F F appears twice, but with opposite orientations. So d 2 ( ( X , 0 ) ) = 0 d^2((X,0))=0 d 2 (( X , 0 )) = 0 , and d 2 = 0 d^2=0 d 2 = 0 by linearity.
We define Λ ∙ n \Lambda_\bullet^n Λ ∙ n to be the subcomplex of P ∙ n P_\bullet^n P ∙ n where Λ ∙ n \Lambda_\bullet^n Λ ∙ n is generated by classes of paramids of dimension k k k . For k ≤ 2 k \le2 k ≤ 2 , a paramid is a simplex, so Λ ∙ n = P ∙ n \Lambda_\bullet^n=P_\bullet^n Λ ∙ n = P ∙ n . For k ≥ 3 k \ge3 k ≥ 3 , the parallelepiped face of a paramid is 0 0 0 in P k − 1 n P_{k-1}^n P k − 1 n , and all the other faces of a paramid are paramids of one dimension lower. So Λ ∙ n \Lambda_\bullet^n Λ ∙ n is closed under the boundary.
Paramids can be represented in depth 2. If the n − 1 n-1 n − 1 -simplex can be represented in depth 2, then anything of dimension < n <n < n can be represented in depth 2, so everything in Λ ∙ n \Lambda_\bullet^n Λ ∙ n can be represented in depth 2. Our goal is to show that the class of the n n n -simplex is in Λ ∙ n \Lambda_\bullet^n Λ ∙ n for each n n n . By induction, this will show that the n n n -simplex is in depth 2 for all n n n .
The key property of P ∙ n P_\bullet^n P ∙ n is the following lemma, which says that a polytope is uniquely defined by its boundary, even modulo lower-dimensional terms:
Lemma 3. The top differential d : P n n → P n − 1 n d:P_n^n \to P_{n-1}^n d : P n n → P n − 1 n is injective.
In order to prove Theorem 3, we need to understand the space V ~ \widetilde V V better. Our goal is to prove the following characterization of V ~ S \widetilde V_S V S :
Lemma 4. Let X X X and Y Y Y be polytopes in Q n \mathbb{Q}^n Q n , with n ≥ 2 n \ge2 n ≥ 2 . Then ( X , Y ) = 0 (X,Y)=0 ( X , Y ) = 0 in V ~ Q n \widetilde V_{\mathbb{Q}^n} V Q n if and only if, for each non-zero direction v v v , the following property holds: let F 1 F_1 F 1 and F 2 F_2 F 2 be the faces of X X X in directions v v v and − v -v − v respectively, and let G 1 G_1 G 1 and G 2 G_2 G 2 be the faces of Y Y Y in directions v v v and − v -v − v respectively. Then ( F 1 + G 2 , F 2 + G 1 ) = 0 (F_1+G_2,F_2+G_1)=0 ( F 1 + G 2 , F 2 + G 1 ) = 0 in V ~ S \widetilde V_S V S , where S S S is the subspace of Q n \mathbb{Q}^n Q n orthogonal to v v v , and we translate F 1 , F 2 , G 1 F_1,F_2,G_1 F 1 , F 2 , G 1 and G 2 G_2 G 2 so that they lie in S S S .
The “only if” direction appears in [22 ] . We reproduce the proof below:
Proof of the “only if” direction. The condition ( X , Y ) = 0 (X,Y)=0 ( X , Y ) = 0 in V ~ Q n \widetilde V_{\mathbb{Q}^n} V Q n is equivalent to saying that there exist polytopes A 1 , … , A k A_1,\ldots,A_k A 1 , … , A k and B 1 , … , B j B_1,\ldots,B_j B 1 , … , B j , each of dimension < n <n < n , such that X + A 1 + ⋯ + A k = Y + B 1 + ⋯ + B j X+A_1+\cdots+A_k=Y+B_1+\cdots+B_j X + A 1 + ⋯ + A k = Y + B 1 + ⋯ + B j .
First, suppose that such A i A_i A i and B i B_i B i exist. Fix a non-zero direction v v v . For each i i i , let A i ′ A'_i A i ′ be the face of A i A_i A i in direction v v v , and let A i ′ ′ A''_i A i ′′ be the face of A i A_i A i in direction − v -v − v , and define B i ′ B'_i B i ′ and B i ′ ′ B''_i B i ′′ similarly. Let F 1 F_1 F 1 and F 2 F_2 F 2 be the faces of X X X in directions v v v and − v -v − v respectively, and G 1 G_1 G 1 and G 2 G_2 G 2 similarly for Y Y Y . Now F 1 + A 1 ′ + ⋯ + A k ′ = G 1 + B 1 ′ + ⋯ + B j ′ F_1+A'_1+\cdots+A'_k=G_1+B'_1+\cdots+B'_j F 1 + A 1 ′ + ⋯ + A k ′ = G 1 + B 1 ′ + ⋯ + B j ′ and F 2 + A 1 ′ ′ + ⋯ + A k ′ ′ = G 2 + B 1 ′ ′ + ⋯ + B j ′ ′ F_2+A''_1+\cdots+A''_k=G_2+B''_1+\cdots+B''_j F 2 + A 1 ′′ + ⋯ + A k ′′ = G 2 + B 1 ′′ + ⋯ + B j ′′ , so:
F 1 + G 2 + A 1 ′ + ⋯ + A k ′ + B 1 ′ ′ + ⋯ + B j ′ ′ = F 2 + G 1 + A 1 ′ ′ + ⋯ + A k ′ ′ + B 1 ′ + ⋯ + B j ′ F_1+G_2+A'_1+\cdots+A'_k+B''_1+\cdots+B''_j=F_2+G_1+A''_1+\cdots+A''_k+B'_1+\cdots+B'_j F 1 + G 2 + A 1 ′ + ⋯ + A k ′ + B 1 ′′ + ⋯ + B j ′′ = F 2 + G 1 + A 1 ′′ + ⋯ + A k ′′ + B 1 ′ + ⋯ + B j ′
For each A i A_i A i , we have two cases: either v v v is not orthogonal to A i A_i A i , in which case A i ′ A'_i A i ′ and A i ′ ′ A''_i A i ′′ have dimension < n − 1 <n-1 < n − 1 , or v v v is orthogonal to A i A_i A i , in which case A i ′ = A i ′ ′ A'_i=A''_i A i ′ = A i ′′ . In the latter case, we can cancel A i ′ A'_i A i ′ and A i ′ ′ A''_i A i ′′ from both sides of the equation. A similar claim holds for B i ′ B'_i B i ′ and B i ′ ′ B''_i B i ′′ . After canceling equivalent terms, we see that ( F 1 + G 2 , F 2 + G 1 ) = 0 (F_1+G_2,F_2+G_1)=0 ( F 1 + G 2 , F 2 + G 1 ) = 0 in V ~ S \widetilde V_S V S , where S S S is the subspace orthogonal to v v v . The assumption that n ≥ 2 n \ge2 n ≥ 2 means that we can translate F 1 + G 2 F_1+G_2 F 1 + G 2 and F 2 + G 1 F_2+G_1 F 2 + G 1 so that they lie in S S S . □ \square □
The other direction of the lemma could be deduced from the results in [23 ] (see § 5.1.4 ). Instead, we will use a result of Jessen and Thorup [21 ] . They studied an algebra of polytopes modulo translations and a subdivision relation. Their results are stated for polytopes with vertices in an arbitrary subfield of R \mathbb{R} R . We specialize to the case of vertices in Q \mathbb{Q} Q .
For a finite-dimensional rational vector space S S S , we define B S B_S B S to the abelian group freely generated by generators corresponding to full-dimensional polytopes in S S S . There is a homomorphism Vol S : B S → Q \operatorname{Vol}_S : B_S \to\mathbb{Q} Vol S : B S → Q that sends a polytope to its volume.
We define Π S \Pi_S Π S to be B S B_S B S modulo translations and subdivision relations that say that X 1 + X 2 = Z X_1 + X_2 = Z X 1 + X 2 = Z if X 1 , X 2 X_1, X_2 X 1 , X 2 and Z Z Z are polytopes where X 1 X_1 X 1 and X 2 X_2 X 2 are interior-disjoint and X 1 ∪ X 2 = Z X_1 \cup X_2 = Z X 1 ∪ X 2 = Z . It is straightforward to see that Vol S \operatorname{Vol}_S Vol S descends to a map Π S → Q \Pi_S \to\mathbb{Q} Π S → Q .
Let Q Q Q be a codimension 1 subspace of S S S and let v v v be a vector not in Q Q Q . Then we define a map h Q , v : B S → B Q h_{Q,v} : B_S \to B_Q h Q , v : B S → B Q as follows: for a polytope X X X in S S S , let F 1 F_1 F 1 and F 2 F_2 F 2 be the faces of X X X in the directions orthogonal to Q Q Q , with the normal to F 1 F_1 F 1 being in the + v +v + v direction and the normal of F 2 F_2 F 2 being in the − v -v − v direction, and translate F 1 F_1 F 1 and F 2 F_2 F 2 by multiples of v v v so that they are in Q Q Q . We view F 1 F_1 F 1 or F 2 F_2 F 2 as 0 if it is not full-dimensional.
Similar to the proof of the “only if” direction of Theorem 4, it is not too hard to see that, if x ∈ B S x \in B_S x ∈ B S is 0 in Π S \Pi_S Π S , then h Q , v ( x ) = 0 h_{Q,v}(x) = 0 h Q , v ( x ) = 0 in Π Q \Pi_Q Π Q . Jessen and Thorup prove the following:
Theorem 5. ([21 ] , Theorem 1) An element x ∈ B S x \in B_S x ∈ B S is 0 in Π S \Pi_S Π S if and only if Vol S ( x ) = 0 \operatorname{Vol}_S(x) = 0 Vol S ( x ) = 0 and, for every codimension 1 subspace Q ⊆ S Q \subseteq S Q ⊆ S and v ∉ Q v \notin Q v ∈ / Q , h Q , v ( x ) h_{Q,v}(x) h Q , v ( x ) is 0 in Π Q \Pi_Q Π Q .
We define a map ξ : B S → V S \xi: B_S \to V_S ξ : B S → V S that sends a polytope X X X to the class of ( X , 0 ) (X, 0) ( X , 0 ) . Clearly, ξ \xi ξ is surjective. When n ≥ 1 n \ge1 n ≥ 1 , Theorem 2 says that ξ \xi ξ descends to a map Π S → V ~ S \Pi_S \to\widetilde{V}_S Π S → V S . In order to use Theorem 5 , we need to understand ξ \xi ξ better.
For k ∈ N + k \in\mathbb{N}_+ k ∈ N + , the dilation λ k : Π S → Π S \lambda_k : \Pi_S \to\Pi_S λ k : Π S → Π S is the map that sends a polytope X X X to k X kX k X . An element x ∈ Π S x \in\Pi_S x ∈ Π S is said to have degree i i i if λ k ( x ) = k i x \lambda_k(x) = k^i x λ k ( x ) = k i x for each k k k . We let Π S i \Pi_S^i Π S i be the subgroup of elements of degree i i i . Jessen and Thorup show the following:
Theorem 6. ([21 ] , Section 5) The group Π S \Pi_S Π S is the direct sum of Π S 1 , … , Π S dim ( S ) \Pi_S^1, \ldots, \Pi_S^{\dim(S)} Π S 1 , … , Π S d i m ( S ) .
An example with S = Q 2 S = \mathbb{Q}^2 S = Q 2 is illustrated in Figure 8 . In this case, Π Q 2 2 \Pi_{\mathbb{Q}^2}^2 Π Q 2 2 is spanned by parallelograms, while Π Q 2 1 \Pi_{\mathbb{Q}^2}^1 Π Q 2 1 is spanned by terms that are the difference of a triangle and a parallelogram with the same area.
Figure 8. Top: the dilation of a parallelogram by 2 can be subdivided into 4 copies of the original parallelogram. Middle: the dilation of a triangle by 2 can be subdivided into two copies of the original triangle and one parallelogram. So the difference of a triangle and a rectangle of the same area is in Π Q 2 1 \Pi^{1}_{\mathbb{Q}^{2}} Π Q 2 1 (bottom).
Our next step is to show that ξ \xi ξ gives an isomorphism Π S 1 → V ~ S \Pi_S^1 \to\widetilde{V}_S Π S 1 → V S . Note that an element of Π S i \Pi_S^i Π S i for i < dim ( S ) i < \dim(S) i < dim ( S ) has volume 0. Indeed, Vol S ( λ k ( x ) ) = k dim ( S ) Vol S ( x ) \operatorname{Vol}_S(\lambda_k(x)) = k^{\dim(S)}\operatorname{Vol}_S(x) Vol S ( λ k ( x )) = k d i m ( S ) Vol S ( x ) . We also note that every h Q , v h_{Q,v} h Q , v map commutes with every λ k \lambda_k λ k , so h Q , v h_{Q,v} h Q , v preserves the decomposition into Π S i \Pi_S^i Π S i .
If S S S has dimension ≥ 2 \ge2 ≥ 2 and Q ⊆ S Q \subseteq S Q ⊆ S , then we can define a unique map h Q , v : V S → V Q h_{Q,v} : V_S \to V_Q h Q , v : V S → V Q similarly to h Q , v h_{Q,v} h Q , v on B S B_S B S . Note that h Q , v ∘ ξ = ξ ∘ h Q , v h_{Q,v} \circ\xi= \xi\circ h_{Q,v} h Q , v ∘ ξ = ξ ∘ h Q , v . We can now determine the kernel of ξ \xi ξ :
Lemma 7. The kernel of ξ : Π S → V ~ S \xi: \Pi_S \to\widetilde{V}_S ξ : Π S → V S is the sum of Π S i \Pi_S^i Π S i for i > 1 i > 1 i > 1 .
Proof. First, we notice that every degree > 1 > 1 > 1 component of Π S \Pi_S Π S is in the kernel of ξ \xi ξ . This is because the dilation λ k \lambda_k λ k commutes with multiplication by k k k in V ~ S \widetilde{V}_S V S . That is, ξ ( λ k ( x ) ) = k ξ ( x ) \xi(\lambda_k(x)) = k\xi(x) ξ ( λ k ( x )) = k ξ ( x ) .
So it remains to show that this is the entire kernel, i.e. that ξ \xi ξ is injective on Π S 1 \Pi_S^1 Π S 1 . This is by induction on dim ( S ) \dim(S) dim ( S ) . The base case is dim ( S ) = 1 \dim(S) = 1 dim ( S ) = 1 . In this case, Π S = Π S 1 \Pi_S = \Pi_S^1 Π S = Π S 1 and it is easy to see that ξ : Π S → V ~ S \xi: \Pi_S \to\widetilde{V}_S ξ : Π S → V S is an isomorphism.
Now let dim ( S ) ≥ 2 \dim(S) \ge2 dim ( S ) ≥ 2 . Let x ∈ Π S 1 x \in\Pi_S^1 x ∈ Π S 1 with ξ ( x ) = 0 \xi(x) = 0 ξ ( x ) = 0 . Represent x x x as a sum of polytopes A 1 + ⋯ + A k − B 1 − ⋯ − B j A_1 + \cdots+ A_k - B_1 - \cdots- B_j A 1 + ⋯ + A k − B 1 − ⋯ − B j . So ξ ( x ) = ( A 1 + ⋯ + A k , B 1 + ⋯ + B k ) = 0 \xi(x) = (A_1 + \cdots+ A_k, B_1 + \cdots+ B_k) = 0 ξ ( x ) = ( A 1 + ⋯ + A k , B 1 + ⋯ + B k ) = 0 in V ~ S \widetilde{V}_S V S .
The “only if” part of Theorem 4 exactly says that h Q , v ( ( A 1 + ⋯ + A k , B 1 + ⋯ + B k ) ) = 0 h_{Q,v}((A_{1}+\cdots+A_{k},B_{1}+\cdots+B_{k}))=0 h Q , v (( A 1 + ⋯ + A k , B 1 + ⋯ + B k )) = 0 for all Q , v Q,v Q , v . So ξ ( h Q , v ( x ) ) = h Q , v ( ξ ( x ) ) = 0 \xi(h_{Q,v}(x))=h_{Q,v}(\xi(x))=0 ξ ( h Q , v ( x )) = h Q , v ( ξ ( x )) = 0 for all Q , v Q,v Q , v .
Now h Q , v ( x ) h_{Q,v}(x) h Q , v ( x ) is in Π Q 1 \Pi^{1}_{Q} Π Q 1 for all Q , v Q,v Q , v , so by inductive assumption, ξ ( h Q , v ( x ) ) = 0 \xi(h_{Q,v}(x))=0 ξ ( h Q , v ( x )) = 0 implies h Q , v ( x ) = 0 h_{Q,v}(x)=0 h Q , v ( x ) = 0 . We also know that Vol S ( x ) = 0 \operatorname{Vol}_{S}(x)=0 Vol S ( x ) = 0 . So by Theorem 5 , x = 0 x=0 x = 0 in Π S \Pi_{S} Π S . By induction, this proves the claim. □
We know that ξ \xi ξ is surjective, so Theorem 7 shows that ξ : Π S 1 → V ~ S \xi:\Pi^{1}_{S}\to\widetilde{V}_{S} ξ : Π S 1 → V S is an isomorphism.
We can now complete the proof of Theorem 4:
Proof of the “if” part of Theorem 4. The conditions of the lemma say exactly that h Q , v ( ( X , Y ) ) = 0 h_{Q,v}((X,Y))=0 h Q , v (( X , Y )) = 0 for every codimension 1 subspace Q ⊆ Q n Q\subseteq\mathbb{Q}^{n} Q ⊆ Q n and v ∉ Q v\notin Q v ∈ / Q . Since ξ \xi ξ is an isomorphism Π S 1 → V ~ S \Pi^{1}_{S}\to\widetilde{V}_{S} Π S 1 → V S , there is some x ∈ Π S 1 x\in\Pi^{1}_{S} x ∈ Π S 1 such that ξ ( x ) = ( X , Y ) \xi(x)=(X,Y) ξ ( x ) = ( X , Y ) . For every Q , v Q,v Q , v , we have ξ ( h Q , v ( x ) ) = h Q , v ( ξ ( x ) ) = h Q , v ( ( X , Y ) ) = 0 \xi(h_{Q,v}(x))=h_{Q,v}(\xi(x))=h_{Q,v}((X,Y))=0 ξ ( h Q , v ( x )) = h Q , v ( ξ ( x )) = h Q , v (( X , Y )) = 0 . Since h Q , v ( x ) ∈ Π S 1 h_{Q,v}(x)\in\Pi^{1}_{S} h Q , v ( x ) ∈ Π S 1 , we have h Q , v ( x ) = 0 h_{Q,v}(x)=0 h Q , v ( x ) = 0 by Theorem 7. Since n ≥ 2 n\geq2 n ≥ 2 , Vol Q n ( x ) = 0 \operatorname{Vol}_{\mathbb{Q}^{n}}(x)=0 Vol Q n ( x ) = 0 , so x = 0 x=0 x = 0 in Π S \Pi_{S} Π S . So ( X , Y ) = ξ ( 0 ) = 0 (X,Y)=\xi(0)=0 ( X , Y ) = ξ ( 0 ) = 0 in V ~ S \widetilde{V}_{S} V S . □
Theorem 3 follows immediately from Theorem 4.
The Chain Complex of Parallelepipeds
Let T = { t 1 , … , t r } T = \{t_1,\ldots,t_r\} T = { t 1 , … , t r } be the set of edge directions of the n n n simplex (with an arbitrary direction chosen for each). So r = ( n + 1 2 ) r = \binom{n+1}{2} r = ( 2 n + 1 ) . Let Γ = Span Z { t 1 , … , t r } \Gamma= \operatorname{Span}_{\mathbb{Z}}\{t_1,\ldots,t_r\} Γ = Span Z { t 1 , … , t r } be the lattice in Q n \mathbb{Q}^n Q n generated by the t i t_i t i .
The ring Q [ Γ ] \mathbb{Q}[\Gamma] Q [ Γ ] consists of formal Q \mathbb{Q} Q -linear combinations of elements of Γ \Gamma Γ , where multiplication is given by the group law on Γ \Gamma Γ . We write g 1 , … , g r g_1,\ldots,g_r g 1 , … , g r for the generators of Q [ Γ ] \mathbb{Q}[\Gamma] Q [ Γ ] corresponding to t 1 , … , t r t_1,\ldots,t_r t 1 , … , t r . So, for example, g i g j g_i g_j g i g j is the element of Q [ Γ ] \mathbb{Q}[\Gamma] Q [ Γ ] corresponding to t i + t j t_i+t_j t i + t j . The element g i + g j g_i+g_j g i + g j is viewed formally as a superposition of t i t_i t i and t j t_j t j .
We define a chain complex C ∙ n C_\bullet^n C ∙ n , which consists of formal oriented parallelepipeds with edge directions in T T T and vertices in Γ \Gamma Γ , with the differential defined in the standard way.
Let E = Q r E=\mathbb{Q}^r E = Q r with basis e 1 , … , e r e_1,\ldots,e_r e 1 , … , e r . We can view C k n C_k^n C k n as the Q \mathbb{Q} Q -module Q [ Γ ] ⊗ Q ⋀ k E \mathbb{Q}[\Gamma]\otimes_{\mathbb{Q}}\bigwedge^k E Q [ Γ ] ⊗ Q ⋀ k E . This is generated by elements of the form γ ⊗ e i 1 ∧ ⋯ ∧ e i k \gamma\otimes e_{i_1}\wedge\cdots\wedge e_{i_k} γ ⊗ e i 1 ∧ ⋯ ∧ e i k (γ ∈ Γ \gamma\in\Gamma γ ∈ Γ ), which we view as corresponding to the parallelepiped:
γ + [ 0 , t i 1 ] + ⋯ + [ 0 , t i k ] \gamma+[0,t_{i_1}]+\cdots+[0,t_{i_k}] γ + [ 0 , t i 1 ] + ⋯ + [ 0 , t i k ]
The boundary map on C k n C_k^n C k n is then defined as the standard cubical boundary. We have d ( e i ) = g i − 1 d(e_i)=g_i-1 d ( e i ) = g i − 1 , this extends to higher orders using the graded Leibniz rule:
d ( γ ⊗ e i 1 ∧ ⋯ ∧ e i k ) = ∑ j = 1 k ( − 1 ) j − 1 γ ( g i j − 1 ) ⊗ e i 1 ∧ ⋯ ∧ e i j ^ ∧ ⋯ ∧ e i k d(\gamma\otimes e_{i_1}\wedge\cdots\wedge e_{i_k})=\sum_{j=1}^{k}(-1)^{j-1}\gamma(g_{i_j}-1)\otimes e_{i_1}\wedge\cdots\wedge\widehat{e_{i_j}}\wedge\cdots\wedge e_{i_k} d ( γ ⊗ e i 1 ∧ ⋯ ∧ e i k ) = j = 1 ∑ k ( − 1 ) j − 1 γ ( g i j − 1 ) ⊗ e i 1 ∧ ⋯ ∧ e i j ∧ ⋯ ∧ e i k
The ρ : C k n → P k + 1 n \rho:C_k^n\to P_{k+1}^n ρ : C k n → P k + 1 n is defined as follows: let x = γ ⊗ e i 1 ∧ ⋯ ∧ e i k x=\gamma\otimes e_{i_1}\wedge\cdots\wedge e_{i_k} x = γ ⊗ e i 1 ∧ ⋯ ∧ e i k be a parallelepiped in C k n C_k^n C k n . Let X X X be the convex hull of 0 0 0 and the vertices of x x x , which is a polytope in S = span ( γ , t i 1 , … , t i k ) S=\operatorname{span}(\gamma,t_{i_1},\ldots,t_{i_k}) S = span ( γ , t i 1 , … , t i k ) . If γ , t i 1 , … , t i k \gamma,t_{i_1},\ldots,t_{i_k} γ , t i 1 , … , t i k are linearly independent, then the cone is non-degenerate and ρ ( x ) \rho(x) ρ ( x ) is the class corresponding to X X X in S S S , with the orientation of S S S given by t i 1 ∧ ⋯ ∧ t i k ∧ γ t_{i_1}\wedge\cdots\wedge t_{i_k}\wedge\gamma t i 1 ∧ ⋯ ∧ t i k ∧ γ . Otherwise, the cone is degenerate and ρ ( x ) = 0 \rho(x)=0 ρ ( x ) = 0 .
Lemma 8. The map ρ \rho ρ is well-defined.
Proof. The only thing to check is that ρ \rho ρ respects the relation:
γ ⊗ e i 1 ∧ ⋯ ∧ e i j ∧ ⋯ ∧ e i ℓ ∧ ⋯ ∧ e i k = − γ ⊗ e i 1 ∧ ⋯ ∧ e i ℓ ∧ ⋯ ∧ e i j ∧ ⋯ ∧ e i k \gamma\otimes e_{i_1}\wedge\cdots\wedge e_{i_j}\wedge\cdots\wedge e_{i_\ell}\wedge\cdots\wedge e_{i_k}
=
-\gamma\otimes e_{i_1}\wedge\cdots\wedge e_{i_\ell}\wedge\cdots\wedge e_{i_j}\wedge\cdots\wedge e_{i_k} γ ⊗ e i 1 ∧ ⋯ ∧ e i j ∧ ⋯ ∧ e i ℓ ∧ ⋯ ∧ e i k = − γ ⊗ e i 1 ∧ ⋯ ∧ e i ℓ ∧ ⋯ ∧ e i j ∧ ⋯ ∧ e i k
in C k n C_k^n C k n . This is straightforward. □
We now claim that ρ \rho ρ commutes with the differentials on C ∙ n C_\bullet^n C ∙ n and P ∙ n P_\bullet^n P ∙ n in degrees at least 2:
Lemma 9. If x ∈ C k n x\in C_k^n x ∈ C k n for k ≥ 2 k\geq2 k ≥ 2 , then d ( ρ ( x ) ) = ρ ( d ( x ) ) d(\rho(x))=\rho(d(x)) d ( ρ ( x )) = ρ ( d ( x )) .
Proof. It is sufficient to check the claim for x = γ ⊗ x i 1 ∧ ⋯ ∧ x i k x=\gamma\otimes x_{i_1}\wedge\cdots\wedge x_{i_k} x = γ ⊗ x i 1 ∧ ⋯ ∧ x i k a parallelepiped. In this case, we have:
d ( x ) = ∑ j = 1 k ( − 1 ) j − 1 γ ( g i j − 1 ) ⊗ x i 1 ∧ ⋯ ∧ x ^ i j ∧ ⋯ ∧ x k d(x)=\sum_{j=1}^{k}(-1)^{j-1}\gamma(g_{i_j}-1)\otimes x_{i_1}\wedge\cdots\wedge\widehat{x}_{i_j}\wedge\cdots\wedge x_k d ( x ) = j = 1 ∑ k ( − 1 ) j − 1 γ ( g i j − 1 ) ⊗ x i 1 ∧ ⋯ ∧ x i j ∧ ⋯ ∧ x k
There are two cases to check, depending on whether x x x is degenerate. First, we consider the case that x x x is not degenerate. In this case, ρ ( x ) \rho(x) ρ ( x ) is the class in P k + 1 n P^{n}_{k+1} P k + 1 n of the polytope X X X , which is the convex hull of 0 and γ + [ 0 , t i 1 ] + ⋯ + [ 0 , t i k ] \gamma+ [0,t_{i_1}] + \cdots+ [0,t_{i_k}] γ + [ 0 , t i 1 ] + ⋯ + [ 0 , t i k ] . The orientation is given by t i 1 ∧ ⋯ ∧ t i k ∧ γ t_{i_1} \wedge\cdots\wedge t_{i_k} \wedge\gamma t i 1 ∧ ⋯ ∧ t i k ∧ γ .
X X X has 2 k + 1 2k+1 2 k + 1 facets. The face not containing 0 is γ + [ 0 , t i 1 ] + ⋯ + [ 0 , t i k ] \gamma+ [0,t_{i_1}] + \cdots+ [0,t_{i_k}] γ + [ 0 , t i 1 ] + ⋯ + [ 0 , t i k ] . This is a Minkowski sum of intervals, which have dimension 1 < k 1 < k 1 < k . So the contribution of this face to d ( ρ ( x ) ) d(\rho(x)) d ( ρ ( x )) is 0.
For each j ∈ { 1 , … , k } j \in\{1,\ldots,k\} j ∈ { 1 , … , k } , we have two faces F j F_j F j and G j G_j G j of X X X . F j F_j F j the convex hull of 0 and γ + ∑ ℓ ≠ j [ 0 , t i ℓ ] \gamma+ \sum_{\ell\ne j}[0,t_{i_\ell}] γ + ∑ ℓ = j [ 0 , t i ℓ ] and G j G_j G j is the convex hull of 0 and γ + t i j + ∑ ℓ ≠ j [ 0 , t i ℓ ] \gamma+ t_{i_j} + \sum_{\ell\ne j}[0,t_{i_\ell}] γ + t i j + ∑ ℓ = j [ 0 , t i ℓ ] .
Now t i j t_{i_j} t i j points out from G j G_j G j and − t i j -t_{i_j} − t i j points out from F j F_j F j . So the orientation A A A of F j F_j F j is chosen so that ( − t i j ) ∧ A (-t_{i_j}) \wedge A ( − t i j ) ∧ A is the same as the orientation of t i 1 ∧ ⋯ ∧ t i k ∧ γ t_{i_1} \wedge\cdots\wedge t_{i_k} \wedge\gamma t i 1 ∧ ⋯ ∧ t i k ∧ γ of X X X . So ( − 1 ) j t i 1 ∧ ⋯ ∧ t i j − 1 ∧ t i j + 1 ∧ ⋯ ∧ t i k ∧ γ (-1)^j t_{i_1} \wedge\cdots\wedge t_{i_{j-1}} \wedge t_{i_{j+1}} \wedge\cdots\wedge t_{i_k} \wedge\gamma ( − 1 ) j t i 1 ∧ ⋯ ∧ t i j − 1 ∧ t i j + 1 ∧ ⋯ ∧ t i k ∧ γ is a representation of the orientation of F j F_j F j . Similarly, the orientation of G j G_j G j is represented by ( − 1 ) j + 1 t i 1 ∧ ⋯ ∧ t i j − 1 ∧ t i j + 1 ∧ ⋯ ∧ t i k ∧ γ (-1)^{j+1}t_{i_1} \wedge\cdots\wedge t_{i_{j-1}} \wedge t_{i_{j+1}} \wedge\cdots\wedge t_{i_k} \wedge\gamma ( − 1 ) j + 1 t i 1 ∧ ⋯ ∧ t i j − 1 ∧ t i j + 1 ∧ ⋯ ∧ t i k ∧ γ , which is equal to ( − 1 ) j + 1 t i 1 ∧ ⋯ ∧ t i j − 1 ∧ t i j + 1 ∧ ⋯ ∧ t i k ∧ ( γ + t i j ) (-1)^{j+1}t_{i_1} \wedge\cdots\wedge t_{i_{j-1}} \wedge t_{i_{j+1}} \wedge\cdots\wedge t_{i_k} \wedge(\gamma+ t_{i_j}) ( − 1 ) j + 1 t i 1 ∧ ⋯ ∧ t i j − 1 ∧ t i j + 1 ∧ ⋯ ∧ t i k ∧ ( γ + t i j ) . This shows that contributions of F j F_j F j and G j G_j G j to d ( ρ ( x ) ) d(\rho(x)) d ( ρ ( x )) are exactly:
ρ ( ( − 1 ) j − 1 γ ( g i j − 1 ) ⊗ x i 1 ∧ ⋯ ∧ x i j − 1 ∧ x i j + 1 ∧ ⋯ ∧ x k ) \rho\left((-1)^{j-1}\gamma(g_{ij}-1)\otimes x_{i_1}\wedge\cdots\wedge x_{i_{j-1}}\wedge x_{i_{j+1}}\wedge\cdots\wedge x_k\right) ρ ( ( − 1 ) j − 1 γ ( g ij − 1 ) ⊗ x i 1 ∧ ⋯ ∧ x i j − 1 ∧ x i j + 1 ∧ ⋯ ∧ x k )
So d ( ρ ( x ) ) = ρ ( d ( x ) ) d(\rho(x)) = \rho(d(x)) d ( ρ ( x )) = ρ ( d ( x )) when the cone of x x x is non-degenerate. We now move on to the degenerate case. Similarly to before, let X X X be the convex hull of 0 and γ + ∑ j [ 0 , t i j ] \gamma+ \sum_j[0,t_{i_j}] γ + ∑ j [ 0 , t i j ] . Since the cone is degenerate, X X X is at most k k k dimensional. If X X X is ≤ k − 1 \le k-1 ≤ k − 1 dimensional, then every face in d ( x ) d(x) d ( x ) is degenerate, so ρ ( d ( x ) ) = 0 \rho(d(x)) = 0 ρ ( d ( x )) = 0 . The remaining case is when X X X is exactly k k k dimensional. Let S S S be the k k k -dimensional subspace containing X X X , and choose an arbitrary orientation of S S S .
In this case, define F j F_j F j and G j G_j G j as oriented polytopes in the same way as before. We also define a parallelepiped face Z = γ + ∑ j [ 0 , t i j ] Z = \gamma+ \sum_j[0,t_{i_j}] Z = γ + ∑ j [ 0 , t i j ] . Since Z Z Z is zero in P k n P^n_k P k n , it is clear that ρ ( d ( x ) ) \rho(d(x)) ρ ( d ( x )) is the sum of classes corresponding to the F j F_j F j , G j G_j G j and Z Z Z .
Now each of the F j F_j F j , G j G_j G j or Z Z Z is either degenerate, has positive orientation (with respect to the orientation chosen for S S S ), or has negative orientation. We claim that the positive-orientation faces give a subdivision of X X X , and similarly the negative orientation faces also give a subdivision of X X X . This is straightforward.
So by Theorem 2 , the contributions from the positively-oriented pieces cancel with the contributions from the negatively-oriented pieces, so ρ ( d ( x ) ) = 0 \rho(d(x)) = 0 ρ ( d ( x )) = 0 , as required. □
The image of ρ \rho ρ in P ∙ n P^n_\bullet P ∙ n lies in the subcomplex Λ ∙ n \Lambda^n_\bullet Λ ∙ n generated by paramids. Note that parallelepipeds in C ∙ n C^n_\bullet C ∙ n are restricted to having edge directions in T T T , so being in the image of ρ \rho ρ is more restrictive than just being in Λ ∙ n \Lambda^n_\bullet Λ ∙ n .
The Homology of C ∙ n C^n_\bullet C ∙ n
We can actually give a nice characterization of the homology of C ∙ n C^n_\bullet C ∙ n . Let Γ ^ = Z r \widehat{\Gamma} = \mathbb{Z}^r Γ = Z r , generated by t ^ 1 , … , t ^ r \widehat{t}_1,\ldots,\widehat{t}_r t 1 , … , t r , and let π \pi π be the projection Γ ^ → Γ \widehat{\Gamma} \to\Gamma Γ → Γ given by t ^ i ↦ t i \widehat{t}_i \mapsto t_i t i ↦ t i .
Let C ^ ∙ n \widehat{C}^n_\bullet C ∙ n be the chain complex of parallelepipeds (in R r \mathbb{R}^r R r ) with vertices in Γ ^ \widehat{\Gamma} Γ and edge direction in { t ^ 1 , … , t ^ r } \{\widehat{t}_1,\ldots,\widehat{t}_r\} { t 1 , … , t r } . Now C ^ ∙ n \widehat{C}^n_\bullet C ∙ n is a cubicalization of R r \mathbb{R}^r R r , and C ∙ n C^n_\bullet C ∙ n is obtained from C ^ ∙ n \widehat{C}^n_\bullet C ∙ n by identifying parallelepipeds that differ by a translation in ker ( π ) \ker(\pi) ker ( π ) . Now ker ( π ) \ker(\pi) ker ( π ) is a subgroup of Z r \mathbb{Z}^r Z r , so by the structure theorem for finitely generated abelian groups, it is freely generated by elements a 1 , … , a r − n a_1,\ldots,a_{r-n} a 1 , … , a r − n of Z r \mathbb{Z}^r Z r . The t i t_i t i are edge vectors of the simplex, and it is not too hard to find such a set of generators explicitly.
So C ∙ n C_\bullet^n C ∙ n is a cubicalization of a topological space which is the quotient of R r \mathbb{R}^r R r by the action of the group generated by a 1 , … , a r − n a_1,\ldots,a_{r-n} a 1 , … , a r − n . This space is homeomorphic to a product of R n \mathbb{R}^n R n and r − n r-n r − n circles. So H k ( C ∙ n ) H_k(C_\bullet^n) H k ( C ∙ n ) is a direct sum of ( r − n k ) \binom{r-n}{k} ( k r − n ) copies of Q \mathbb{Q} Q .
We didn’t need to use anything special about t 1 , … , t r t_1,\ldots,t_r t 1 , … , t r here. In general, let T = { t 1 , … , t r } T=\{t_1,\ldots,t_r\} T = { t 1 , … , t r } be a set of directions generating an abelian group Γ \Gamma Γ , and let C ∙ T C_\bullet^T C ∙ T be the chain complex of parallelepipeds with edges directions in T T T and vertices in Γ \Gamma Γ . Then the argument above shows that C ∙ T C_\bullet^T C ∙ T is a cubicalization of a topological space which is the quotient of R r \mathbb{R}^r R r by the set of relations among the t i t_i t i . In particular, if the t i t_i t i freely generate Γ \Gamma Γ , then C ∙ T C_\bullet^T C ∙ T has the homology of a point. This observation will be useful for filling cycles in C ∙ n C_\bullet^n C ∙ n .
This last observation is also a consequence of a more general idea about the Koszul resolution of a regular sequence, see § 5.1.1 .
Filling Boundaries in Cn
Let D ∙ n D_\bullet^n D ∙ n be C ∙ n C_\bullet^n C ∙ n modulo translations. Formally, we can think of D k n D_k^n D k n as being equal to ⋀ Q k E \bigwedge^k_{\mathbb{Q}} E ⋀ Q k E (recall E = Q r E=\mathbb{Q}^r E = Q r , generated by e 1 , … , e r e_1,\ldots,e_r e 1 , … , e r ). Let ε \varepsilon ε be the map C ∙ n → D ∙ n C_\bullet^n\to D_\bullet^n C ∙ n → D ∙ n that forgets translation in C ∙ n C_\bullet^n C ∙ n . Using C k n = Q [ Γ ] ⊗ Q ⋀ Q k E C_k^n=\mathbb{Q}[\Gamma]\otimes_{\mathbb{Q}}\bigwedge^k_{\mathbb{Q}} E C k n = Q [ Γ ] ⊗ Q ⋀ Q k E , ε \varepsilon ε can be defined using the map Q [ Γ ] → Q \mathbb{Q}[\Gamma]\to\mathbb{Q} Q [ Γ ] → Q that sends each γ ∈ Γ \gamma\in\Gamma γ ∈ Γ to 1 1 1 .
We note that every boundary x x x in C k n C_k^n C k n has ε ( x ) = 0 \varepsilon(x)=0 ε ( x ) = 0 . Indeed, opposite pairs of faces of a parallelepiped cancel after taking ε \varepsilon ε . So this gives a necessary condition for a cycle x x x to be a boundary. We claim that it is sufficient:
Lemma 10. A cycle x ∈ C k n x\in C_k^n x ∈ C k n is a boundary if and only if $\varepsilon(x)=0
Proof. The “only if” direction is clear. So suppose that x x x is a cycle with ε ( x ) = 0 \varepsilon(x)=0 ε ( x ) = 0 . We need to show that x x x is a boundary.
Without loss of generality, suppose that t 1 , … , t n t_1,\ldots,t_n t 1 , … , t n freely generate the rank-n n n free abelian group Γ \Gamma Γ . For example, we can take t 1 , … , t n t_1,\ldots,t_n t 1 , … , t n to be the set of edges of the simplex containing one distinguished vertex. Write A = { t 1 , … , t n } A=\{t_1,\ldots,t_n\} A = { t 1 , … , t n } and B = { t n + 1 , … , t r } B=\{t_{n+1},\ldots,t_r\} B = { t n + 1 , … , t r } . Let K ∙ K_\bullet K ∙ be the chain complex of parallelepipeds with edge directions in A A A and vertices in Γ \Gamma Γ , and similarly let T ∙ T_\bullet T ∙ be the chain complex of parallelepipeds with edge direction in B B B and vertices in Γ \Gamma Γ . Write δ \delta δ for the differential on K ∙ K_\bullet K ∙ and ∂ \partial ∂ for the differential on T ∙ T_\bullet T ∙ .
We claim that C ∙ n ≅ K ∙ ⊗ T ∙ C_\bullet^n\cong K_\bullet\otimes T_\bullet C ∙ n ≅ K ∙ ⊗ T ∙ . Formally, this says:
C k n ≅ ⨁ p + q = k K p ⊗ Q [ Γ ] T q C_k^n\cong\bigoplus_{p+q=k}K_p\otimes_{\mathbb{Q}[\Gamma]}T_q C k n ≅ p + q = k ⨁ K p ⊗ Q [ Γ ] T q
In other words, every parallelepiped in C k n C_k^n C k n can be written as a formal product of one in K ∙ K_\bullet K ∙ and one in T ∙ T_\bullet T ∙ . The claim is clear from K p = Q [ Γ ] ⊗ ⋀ Q p ⟨ e 1 , … , e n ⟩ K_p=\mathbb{Q}[\Gamma]\otimes\bigwedge_{\mathbb{Q}}^p\langle e_1,\ldots,e_n\rangle K p = Q [ Γ ] ⊗ ⋀ Q p ⟨ e 1 , … , e n ⟩ and T q = Q [ Γ ] ⊗ ⋀ Q q ⟨ e n + 1 , … , e r ⟩ T_q=\mathbb{Q}[\Gamma]\otimes\bigwedge_{\mathbb{Q}}^q\langle e_{n+1},\ldots,e_r\rangle T q = Q [ Γ ] ⊗ ⋀ Q q ⟨ e n + 1 , … , e r ⟩ . We can think of K p ⊗ T q K_p\otimes T_q K p ⊗ T q as consisting of parallelepipeds with p p p edge directions in A A A and q q q edge directions in B B B .
We extend δ \delta δ and ∂ \partial ∂ to maps δ : K p + 1 ⊗ T q → K p ⊗ T q \delta:K_{p+1}\otimes T_q\to K_p\otimes T_q δ : K p + 1 ⊗ T q → K p ⊗ T q and ∂ : K p ⊗ T q + 1 → K p ⊗ T q \partial:K_p\otimes T_{q+1}\to K_p\otimes T_q ∂ : K p ⊗ T q + 1 → K p ⊗ T q . In order for these to be compatible with the differential on C ∙ n C_\bullet^n C ∙ n , the map ∂ : K p ⊗ T q + 1 → K p ⊗ T q \partial:K_p\otimes T_{q+1}\to K_p\otimes T_q ∂ : K p ⊗ T q + 1 → K p ⊗ T q has a ( − 1 ) p (-1)^p ( − 1 ) p factor compared to ∂ : T q + 1 → T q \partial:T_{q+1}\to T_q ∂ : T q + 1 → T q . Note that δ ∂ + ∂ δ = 0 \delta\partial+\partial\delta=0 δ ∂ + ∂ δ = 0 , and the differential d d d on C ∙ n C_\bullet^n C ∙ n is identified with δ + ∂ \delta+\partial δ + ∂ . Now x x x is a cycle in C k n C_k^n C k n . For i = 0 , … , k i = 0, \ldots, k i = 0 , … , k , let x i x_i x i be the component of x x x in K i ⊗ T k − i K_i \otimes T_{k-i} K i ⊗ T k − i . The strategy will be to inductively add boundaries that zero x i x_i x i , starting with x 0 x_0 x 0 . Note that ε \varepsilon ε identifies sets of parallelepipeds with the same set of edge directions, so ε ( x ) = 0 \varepsilon(x) = 0 ε ( x ) = 0 implies that ε ( x i ) = 0 \varepsilon(x_i) = 0 ε ( x i ) = 0 for each x i x_i x i .
So x 0 x_0 x 0 is a class in K 0 ⊗ T k K_0 \otimes T_k K 0 ⊗ T k with ε ( x 0 ) = 0 \varepsilon(x_0) = 0 ε ( x 0 ) = 0 . Note that K 0 = Q [ Γ ] K_0 = \mathbb{Q}[\Gamma] K 0 = Q [ Γ ] . The image of δ : K 1 → K 0 \delta: K_1 \to K_0 δ : K 1 → K 0 is the ideal I I I in Q [ Γ ] \mathbb{Q}[\Gamma] Q [ Γ ] generated by g 1 − 1 , … , g n − 1 g_1 - 1, \ldots, g_n - 1 g 1 − 1 , … , g n − 1 . We claim that x 0 ∈ I ⊗ T k x_0 \in I \otimes T_k x 0 ∈ I ⊗ T k . Indeed, the parallelepipeds in x 0 x_0 x 0 can be grouped in pairs that are orientation-reversed translates of each other, and each pair is an element of I ⊗ T k I \otimes T_k I ⊗ T k . This says that x 0 x_0 x 0 is a δ \delta δ -boundary. Let y 1 ∈ K 1 ⊗ T k y_1 \in K_1 \otimes T_k y 1 ∈ K 1 ⊗ T k with δ ( y 1 ) = x 0 \delta(y_1) = x_0 δ ( y 1 ) = x 0 . We can subtract d ( y 1 ) = δ ( y 1 ) + ∂ ( y 1 ) d(y_1) = \delta(y_1) + \partial(y_1) d ( y 1 ) = δ ( y 1 ) + ∂ ( y 1 ) from x x x to get a new cycle with no component in K 0 ⊗ T k K_0 \otimes T_k K 0 ⊗ T k . Note that d ( y 1 ) d(y_1) d ( y 1 ) is a cycle (since d 2 = 0 d^2 = 0 d 2 = 0 ), so x − d ( y 1 ) x - d(y_1) x − d ( y 1 ) is a cycle.
Now proceed by induction: suppose that x i = 0 x_i = 0 x i = 0 for i = 0 , … , j − 1 i = 0, \ldots, j - 1 i = 0 , … , j − 1 for some j ≥ 1 j \ge1 j ≥ 1 . We want to add a boundary to x x x that zeros x j x_j x j . Now x j ∈ K j ⊗ T k − j x_j \in K_j \otimes T_{k-j} x j ∈ K j ⊗ T k − j , and δ ( x j ) = d ( x j ) \delta(x_j) = d(x_j) δ ( x j ) = d ( x j ) since no other non-zero x i x_i x i has any boundary in K j − 1 ⊗ T k − j K_{j-1} \otimes T_{k-j} K j − 1 ⊗ T k − j . Since x j x_j x j is a cycle, δ ( x j ) = 0 \delta(x_j) = 0 δ ( x j ) = 0 . By exactness of K ∙ K_\bullet K ∙ , there is some y j + 1 ∈ K j + 1 ⊗ T k − j y_{j+1} \in K_{j+1} \otimes T_{k-j} y j + 1 ∈ K j + 1 ⊗ T k − j with δ ( y j + 1 ) = x j \delta(y_{j+1}) = x_j δ ( y j + 1 ) = x j . Subtracting d ( y j + 1 ) = δ ( y j + 1 ) + ∂ ( y j + 1 ) d(y_{j+1}) = \delta(y_{j+1}) + \partial(y_{j+1}) d ( y j + 1 ) = δ ( y j + 1 ) + ∂ ( y j + 1 ) gives a new cycle with no K j ⊗ T k − j K_j \otimes T_{k-j} K j ⊗ T k − j component.
By induction, we can eventually zero all the terms in x x x . Since we have only subtracted boundaries from x x x , this proves that x x x is a boundary, as required. □
Remark. In § 5.1.3 , we give a shorter, but less concrete proof of Theorem 10. We are also aware of a more explicit proof. We have decided not to include this since the combinatorial construction is explicit.
Filling Simplices
In order to show that the n n n -simplex is in Λ n \Lambda_n Λ n , we want to find a cycle x x x in C n − 2 n C_{n-2}^n C n − 2 n with ε ( x ) = 0 \varepsilon(x) = 0 ε ( x ) = 0 such that ρ ( x ) = d ( Δ n ) \rho(x) = d(\Delta^n) ρ ( x ) = d ( Δ n ) is the boundary of the n n n -simplex. By Theorem 10, x x x is then the boundary of some y ∈ C n − 1 n y \in C_{n-1}^n y ∈ C n − 1 n , and by Theorem 9, d ( ρ ( y ) ) = ρ ( d ( y ) ) = d ( Δ n ) d(\rho(y)) = \rho(d(y)) = d(\Delta^n) d ( ρ ( y )) = ρ ( d ( y )) = d ( Δ n ) . By Theorem 3, ρ ( y ) \rho(y) ρ ( y ) is the class of Δ n \Delta^n Δ n in P n P_n P n . Since the image of ρ \rho ρ is in Λ n ∘ \Lambda_n^\circ Λ n ∘ , this will show that Δ n \Delta^n Δ n is in Λ n ∘ \Lambda_n^\circ Λ n ∘ .
For a subset S ⊆ { 1 , … , n + 1 } S \subseteq\{1, \ldots, n + 1\} S ⊆ { 1 , … , n + 1 } of size n n n , let F S F_S F S be the n − 1 n - 1 n − 1 -dimensional subspace of Q n \mathbb{Q}^n Q n spanned by edge directions contained in the face of Δ n \Delta^n Δ n that is the convex hull of vertices in S S S . We say that an element x x x of C k n C_k^n C k n satisfies the face direction condition if, for every parallelepiped p p p with non-zero coefficient in x x x , all the vertices of p p p are contained in F S F_S F S for some S S S .
First, we show how to realize condition ε = 0 \varepsilon= 0 ε = 0 :
Lemma 11. Let x x x be a cycle in C k n C_k^n C k n with k ≥ 2 k \ge2 k ≥ 2 . Then there is a cycle x ′ ∈ C k n x' \in C_k^n x ′ ∈ C k n with ε ( x ′ ) = 0 \varepsilon(x') = 0 ε ( x ′ ) = 0 and ρ ( x ′ ) = ρ ( x ) \rho(x') = \rho(x) ρ ( x ′ ) = ρ ( x ) . Furthermore, if x x x satisfies the face direction condition , then x ′ x' x ′ does as well.
Proof. Let S : C k n → C k n S : C_k^n \to C_k^n S : C k n → C k n be the map that takes a parallelepiped in C k n C_k^n C k n , multiplies by 2, then subdivides it into 2 k 2^k 2 k translated copies of the original parallelepiped (see Figure 5 ). Formally,
S ( γ ⊗ e i 1 ∧ ⋯ ∧ e i k ) = ∑ ( u 1 , … , u k ) ∈ { 0 , 1 } k ( γ 2 ⋅ g i 1 u 1 ⋯ g i k u k ) ⊗ e i 1 ∧ ⋯ ∧ e i k S(\gamma\otimes e_{i_1} \wedge\cdots\wedge e_{i_k}) =
\sum_{(u_1,\ldots,u_k)\in\{0,1\}^k}
(\gamma^2 \cdot g_{i_1}^{u_1} \cdots g_{i_k}^{u_k}) \otimes e_{i_1} \wedge\cdots\wedge e_{i_k} S ( γ ⊗ e i 1 ∧ ⋯ ∧ e i k ) = ( u 1 , … , u k ) ∈ { 0 , 1 } k ∑ ( γ 2 ⋅ g i 1 u 1 ⋯ g i k u k ) ⊗ e i 1 ∧ ⋯ ∧ e i k
Clearly, ε ( S ( x ) ) = 2 k ε ( x ) \varepsilon(S(x)) = 2^k\varepsilon(x) ε ( S ( x )) = 2 k ε ( x ) for x ∈ C k n x \in C^n_k x ∈ C k n . We claim that ρ ( S ( x ) ) = 2 ρ ( x ) \rho(S(x)) = 2\rho(x) ρ ( S ( x )) = 2 ρ ( x ) . To see this, let x = γ ⊗ e i 1 ∧ ⋯ ∧ e i k x = \gamma\otimes e_{i_1} \wedge\cdots\wedge e_{i_k} x = γ ⊗ e i 1 ∧ ⋯ ∧ e i k be a parallelepiped in C k n C^n_k C k n . Recall that ρ ( x ) \rho(x) ρ ( x ) is the (class of the) paramid X X X with apex at the origin and base γ + [ 0 , t i 1 ] + ⋯ + [ 0 , t i k ] \gamma+ [0,t_{i_1}] + \cdots+ [0,t_{i_k}] γ + [ 0 , t i 1 ] + ⋯ + [ 0 , t i k ] . So 2 X 2X 2 X is the paramid with apex at the origin and base 2 γ + [ 0 , 2 t i 1 ] + ⋯ + [ 0 , 2 t i k ] 2\gamma+ [0,2t_{i_1}] + \cdots+ [0,2t_{i_k}] 2 γ + [ 0 , 2 t i 1 ] + ⋯ + [ 0 , 2 t i k ] , which can be subdivided into 2 k 2^k 2 k pieces, corresponding to the components of S ( x ) S(x) S ( x ) (see Figure 5 ).
So set x ′ = 1 2 k − 2 ( 2 k x − S ( x ) ) x' = \frac{1}{2^k-2}(2^k x - S(x)) x ′ = 2 k − 2 1 ( 2 k x − S ( x )) . Since k ≥ 2 k \ge2 k ≥ 2 , the denominator is non-zero. Now ε ( x ′ ) = 0 \varepsilon(x') = 0 ε ( x ′ ) = 0 , and ρ ( x ′ ) = ρ ( x ) \rho(x') = \rho(x) ρ ( x ′ ) = ρ ( x ) . It is straightforward to check that x ′ x' x ′ is a cycle. □
Now, we prove the inductive step that constructs a boundary of Δ n + 1 \Delta^{n+1} Δ n + 1 given a Δ n \Delta^n Δ n .
Lemma 12. Let n ≥ 2 n \ge2 n ≥ 2 . Suppose there is an x ∈ C n − 1 n x \in C^{n}_{n-1} x ∈ C n − 1 n such that ρ ( x ) = [ Δ n ] \rho(x) = [\Delta^n] ρ ( x ) = [ Δ n ] , where d ( x ) d(x) d ( x ) satisfies the face direction condition. Then there is a cycle y ∈ C n − 1 n + 1 y \in C^{n+1}_{n-1} y ∈ C n − 1 n + 1 such that ρ ( y ) = d ( [ Δ n + 1 ] ) \rho(y) = d([\Delta^{n+1}]) ρ ( y ) = d ([ Δ n + 1 ]) , where y y y satisfies the face direction condition.
Proof. The cycle y y y will be constructed from one copy of x x x for each injective map μ : { 1 , … , n + 1 } → { 1 , … , n + 2 } \mu: \{1,\ldots,n+1\} \to\{1,\ldots,n+2\} μ : { 1 , … , n + 1 } → { 1 , … , n + 2 } . We can view μ \mu μ as a map that realizes Δ n \Delta^n Δ n as a face of Δ n + 1 \Delta^{n+1} Δ n + 1 . So each facet of the n n n -simplex is represented by ( n + 1 ) ! (n+1)! ( n + 1 )! symmetrized copies of x x x .
Let Γ \Gamma Γ be the lattice generated by simplex edge directions in R n \mathbb{R}^n R n , and let Γ ′ \Gamma' Γ ′ be the lattice generated by simplex edge directions in R n + 1 \mathbb{R}^{n+1} R n + 1 . A map μ : { 1 , … , n + 1 } → { 1 , … , n + 2 } \mu: \{1,\ldots,n+1\} \to\{1,\ldots,n+2\} μ : { 1 , … , n + 1 } → { 1 , … , n + 2 } induces a homomorphism Γ → Γ ′ \Gamma\to\Gamma' Γ → Γ ′ . This defines a map \psi_\mu: C^n_\mathord{\bullet} \to C^{n+1}_\mathord{\bullet} .
Each injective map μ : { 1 , … , n + 1 } → { 1 , … , n + 2 } \mu: \{1,\ldots,n+1\} \to\{1,\ldots,n+2\} μ : { 1 , … , n + 1 } → { 1 , … , n + 2 } extends uniquely to a permutation μ ′ : { 1 , … , n + 2 } → { 1 , … , n + 2 } \mu' : \{1,\ldots,n+2\} \to\{1,\ldots,n+2\} μ ′ : { 1 , … , n + 2 } → { 1 , … , n + 2 } . We define:
y = 1 ( n + 1 ) ! ∑ μ sign ( μ ′ ) ψ μ ( x ) y = \frac{1}{(n+1)!}\sum_{\mu}\operatorname{sign}(\mu')\psi_\mu(x) y = ( n + 1 )! 1 μ ∑ sign ( μ ′ ) ψ μ ( x )
where the sum is over injective μ : { 1 , … , n + 1 } → { 1 , … , n + 2 } \mu: \{1,\ldots,n+1\} \to\{1,\ldots,n+2\} μ : { 1 , … , n + 1 } → { 1 , … , n + 2 } .
We claim that ρ ( y ) ∈ P n n + 1 \rho(y) \in P^{n+1}_n ρ ( y ) ∈ P n n + 1 is the boundary of Δ n + 1 \Delta^{n+1} Δ n + 1 . For each S ⊂ { 1 , … , n + 2 } S \subset\{1,\ldots,n+2\} S ⊂ { 1 , … , n + 2 } of size n + 1 n+1 n + 1 , there are ( n + 1 ) ! (n+1)! ( n + 1 )! maps μ : { 1 , … , n + 1 } → { 1 , … , n + 2 } \mu: \{1,\ldots,n+1\} \to\{1,\ldots,n+2\} μ : { 1 , … , n + 1 } → { 1 , … , n + 2 } with image S S S . For each of these μ \mu μ , ρ ( ψ μ ( x ) ) \rho(\psi_\mu(x)) ρ ( ψ μ ( x )) is the Δ n \Delta^n Δ n face of Δ n + 1 \Delta^{n+1} Δ n + 1 in F S F_S F S , with sign determined by sign ( μ ′ ) \operatorname{sign}(\mu') sign ( μ ′ ) (note that the orientation on F S F_S F S induced by μ \mu μ is determined by sign ( μ ′ ) \operatorname{sign}(\mu') sign ( μ ′ ) ). So ρ ( y ) \rho(y) ρ ( y ) is exactly the boundary of Δ n + 1 \Delta^{n+1} Δ n + 1 .
Next, we claim that y y y is a cycle in C n − 1 n + 1 C^{n+1}_{n-1} C n − 1 n + 1 . Clearly, ψ μ \psi_\mu ψ μ commutes with the boundary d d d on C n − 1 n + 1 C^{n+1}_{n-1} C n − 1 n + 1 . For each parallelepiped z z z with non-zero coefficient in d ( x ) d(x) d ( x ) , we choose some S ⊂ { 1 , … , n + 1 } S \subset\{1,\ldots,n+1\} S ⊂ { 1 , … , n + 1 } such that z z z is in F S F_S F S . This is possible by the face direction condition for d ( x ) d(x) d ( x ) .
Let z z z be a parallelepiped in d ( x ) d(x) d ( x ) , which by assumption is in F S F_S F S for some S S S . Let μ : { 1 , … , n + 1 } → { 1 , … , n + 2 } \mu: \{1,\ldots,n+1\} \to\{1,\ldots,n+2\} μ : { 1 , … , n + 1 } → { 1 , … , n + 2 } be injective, and let κ \kappa κ be the unique map that agrees with μ \mu μ on S S S but is not equal to μ \mu μ . Note that sign ( μ ′ ) = − sign ( κ ′ ) \operatorname{sign}(\mu') = -\operatorname{sign}(\kappa') sign ( μ ′ ) = − sign ( κ ′ ) , since μ ′ \mu' μ ′ and κ ′ \kappa' κ ′ differ by a transposition. Now ψ μ ( z ) = ψ κ ( z ) \psi_\mu(z) = \psi_\kappa(z) ψ μ ( z ) = ψ κ ( z ) , so these terms cancel in d ( y ) d(y) d ( y ) . This shows that d ( y ) = 0 d(y) = 0 d ( y ) = 0 .
Note that every parallelepiped in the image of ψ μ \psi_\mu ψ μ is contained in the subspace F img ( μ ) F_{\operatorname{img}(\mu)} F img ( μ ) , so y y y satisfies the face direction condition. □
Theorem 13. For each n n n , [ Δ n ] ∈ Λ n n [\Delta^n] \in\Lambda^n_n [ Δ n ] ∈ Λ n n .
Proof. We will show by induction on n n n that there is an x ∈ C n − 1 n x \in C^{n}_{n-1} x ∈ C n − 1 n such that ρ ( x ) = Δ n \rho(x) = \Delta^{n} ρ ( x ) = Δ n , and d ( x ) d(x) d ( x ) satisfies the face direction condition. The claim will follow since img ( ρ ) ⊆ Λ n \operatorname{img}(\rho) \subseteq\Lambda^{n} img ( ρ ) ⊆ Λ n .
The base case is n = 3 n = 3 n = 3 . We notice that the 3 simplex Δ 3 \Delta^{3} Δ 3 is equivalent in V ~ R n \widetilde{V}_{\mathbb{R}^{n}} V R n to the negation of a paramid X X X that satisfies the face direction conditions. This is illustrated in Figure 9 . The two polytopes give a subdivision of a polytope which is the sum of a triangle and a line segment. Since the triangle and line segment are less than 3 dimensional, this shows that Δ 3 + X = 0 \Delta^{3} + X = 0 Δ 3 + X = 0 in V ~ R n \widetilde{V}_{\mathbb{R}^{n}} V R n . It is straightforward to check the face direction conditions for X X X . So the class of the base of X X X (with appropriately chosen orientation) gives an x ∈ C 2 3 x \in C^{3}_{2} x ∈ C 2 3 such that ρ ( x ) = Δ 3 \rho(x) = \Delta^{3} ρ ( x ) = Δ 3 .
Figure 9. Top: Using inclusion-exclusion, we can write the union P P P of the standard 3-simplex Δ 3 \Delta_{3} Δ 3 – with vertices at ( 0 , 0 , 0 ) (0,0,0) ( 0 , 0 , 0 ) , ( 1 , 0 , 0 ) (1,0,0) ( 1 , 0 , 0 ) , ( 0 , 1 , 0 ) (0,1,0) ( 0 , 1 , 0 ) and ( 0 , 0 , 1 ) (0,0,1) ( 0 , 0 , 1 ) – and the paramid Π \Pi Π – with vertices ( 0 , 0 , 0 ) (0,0,0) ( 0 , 0 , 0 ) , ( 0 , 1 , 0 ) (0,1,0) ( 0 , 1 , 0 ) , ( − 1 , 1 , 0 ) (-1,1,0) ( − 1 , 1 , 0 ) , ( − 1 , 0 , 1 ) (-1,0,1) ( − 1 , 0 , 1 ) and ( 0 , 0 , 1 ) (0,0,1) ( 0 , 0 , 1 ) – as the sum of the simplex and the paramid minus their intersection – the triangular face F F F with vertices ( 0 , 0 , 0 ) (0,0,0) ( 0 , 0 , 0 ) , ( 0 , 1 , 0 ) (0,1,0) ( 0 , 1 , 0 ) and ( 0 , 0 , 1 ) (0,0,1) ( 0 , 0 , 1 ) . Bottom: P P P is also the Minkowski sum of the triangular face T T T with vertices at ( 0 , 0 , 0 ) (0,0,0) ( 0 , 0 , 0 ) , ( − 1 , 1 , 0 ) (-1,1,0) ( − 1 , 1 , 0 ) and ( − 1 , 0 , 1 ) (-1,0,1) ( − 1 , 0 , 1 ) and the segment E E E with vertices at ( 0 , 0 , 0 ) (0,0,0) ( 0 , 0 , 0 ) and ( 1 , 0 , 0 ) (1,0,0) ( 1 , 0 , 0 ) .
For the inductive step, suppose the claim is true for some n ≥ 3 n \ge3 n ≥ 3 . By Theorem 12, there is a cycle y ∈ C n − 1 n + 1 y \in C^{n+1}_{n-1} y ∈ C n − 1 n + 1 such that ρ ( y ) = d ( Δ n + 1 ) \rho(y) = d(\Delta^{n+1}) ρ ( y ) = d ( Δ n + 1 ) . By Theorem 11, there is some y ′ y' y ′ with ρ ( y ′ ) = ρ ( y ) = d ( Δ n + 1 ) \rho(y') = \rho(y) = d(\Delta^{n+1}) ρ ( y ′ ) = ρ ( y ) = d ( Δ n + 1 ) , with ε ( y ′ ) = 0 \varepsilon(y') = 0 ε ( y ′ ) = 0 . So by Theorem 10, there is some z ∈ C n n + 1 z \in C^{n+1}_{n} z ∈ C n n + 1 with d ( z ) = y ′ d(z) = y' d ( z ) = y ′ (so d ( z ) d(z) d ( z ) satisfies the face direction condition).
By Theorem 9, we have d ( ρ ( z ) ) = ρ ( d ( z ) ) = ρ ( y ′ ) = d ( Δ n + 1 ) d(\rho(z))=\rho(d(z))=\rho(y^{\prime})=d(\Delta^{n+1}) d ( ρ ( z )) = ρ ( d ( z )) = ρ ( y ′ ) = d ( Δ n + 1 ) . By Theorem 3, this means that ρ ( z ) = Δ n + 1 \rho(z)=\Delta^{n+1} ρ ( z ) = Δ n + 1 . By induction, this completes the proof. □
Additional Ideas
This section contains some results and alternate proofs that did not fit into the main body of this part of the paper. We believe that these ideas can be valuable intuition for understanding our result.
The Universality of Paramids
Haase, Hertrich, and Loho show that ReLU n , 2 \operatorname{ReLU}_{n,2} ReLU n , 2 is generated by support functions of polytopes that are each the convex hull of two zonotopes (see Theorem 8 in [15 ] ). By Propositions 9 and 10 in [15 ] and Theorem 2, such a polytope can be written in terms of polytopes of form conv ( A ∪ B ) \operatorname{conv}(A\cup B) conv ( A ∪ B ) , where conv ( A ∪ B ) \operatorname{conv}(A\cup B) conv ( A ∪ B ) is a join of A A A and B B B (i.e. A A A and B B B have disjoint affine hulls and their tangent spaces are transverse). Working modulo lower-dimensional pieces, we can ignore pieces except those with dim ( A ) + dim ( B ) = n − 1 \dim(A)+\dim(B)=n-1 dim ( A ) + dim ( B ) = n − 1 .
When A A A or B B B is a point, the piece we get is a paramid. The purpose of this section is to show that, modulo lower-dimensional terms, every such piece is equivalent to a paramid. This somewhat justifies the choice to focus on paramids with our proof.
We write α : R n → R n \alpha:\mathbb{R}^{n}\to\mathbb{R}^{n} α : R n → R n for the antipodal map. The key result is the following:
Lemma 14. Let A A A and B B B be polytopes in R n \mathbb{R}^{n} R n (n ≥ 1 n\ge1 n ≥ 1 ) with disjoint affine hulls. Suppose A A A can be written A 1 + A 2 A_{1}+A_{2} A 1 + A 2 , where A 1 A_{1} A 1 and A 2 A_{2} A 2 have transverse tangent spaces. Then in V ~ R n \widetilde{V}_{\mathbb{R}^{n}} V R n , the class of conv ( A ∪ B ) \operatorname{conv}(A\cup B) conv ( A ∪ B ) is equal to ( − 1 ) dim ( A 2 ) (-1)^{\dim(A_{2})} ( − 1 ) d i m ( A 2 ) times the class of conv ( A 1 ∪ ( B + α ( A 2 ) ) ) \operatorname{conv}(A_{1}\cup(B+\alpha(A_{2}))) conv ( A 1 ∪ ( B + α ( A 2 ))) .
Proof. In this proof, we use the convention that a zero-dimensional point has one − 1 -1 − 1 -dimensional facet, which is the empty set. The Minkowski sum of any polytope with the empty set is empty. The way we use the induction hypothesis, we will sometimes need a version of the claim where A 1 A_{1} A 1 or B B B empty. We will check this case first.
If both A 1 A_{1} A 1 and B B B are empty, then both conv ( A ∪ B ) \operatorname{conv}(A\cup B) conv ( A ∪ B ) and conv ( A 1 ∪ ( B + α ( A 2 ) ) ) \operatorname{conv}(A_{1}\cup(B+\alpha(A_{2}))) conv ( A 1 ∪ ( B + α ( A 2 ))) are empty, so the claim is trivial. If A 1 A_{1} A 1 is empty and B B B is not, then conv ( A ∪ B ) = B \operatorname{conv}(A\cup B)=B conv ( A ∪ B ) = B and conv ( A 1 ∪ ( B + A 2 ) ) = B + A 2 \operatorname{conv}(A_{1}\cup(B+A_{2}))=B+A_{2} conv ( A 1 ∪ ( B + A 2 )) = B + A 2 . Since A 2 A_{2} A 2 and B B B have dimension < n <n < n , these both represent 0 0 0 in V ~ R n \widetilde{V}_{\mathbb{R}^{n}} V R n .
We also handle the case dim ( A 2 ) = 0 \dim(A_{2})=0 dim ( A 2 ) = 0 separately. In this case, A 2 A_{2} A 2 is a point, and it is clear that conv ( A 1 ∪ ( B + α ( A 2 ) ) ) \operatorname{conv}(A_{1}\cup(B+\alpha(A_{2}))) conv ( A 1 ∪ ( B + α ( A 2 ))) is just conv ( A ∪ B ) \operatorname{conv}(A\cup B) conv ( A ∪ B ) translated by − A 2 -A_{2} − A 2 .
Now suppose that A A A and B B B are non-empty and A 2 A_{2} A 2 has dimension at least 1. The proof is by induction on n n n . When n = 1 n=1 n = 1 , the conditions of the lemma are impossible to satisfy, and so the result is true trivially.
We want to use Theorem 4. Since A A A and B B B have disjoint affine hulls, the facets of conv ( A ∪ B ) \operatorname{conv}(A\cup B) conv ( A ∪ B ) are of form conv ( F ∪ B ) \operatorname{conv}(F\cup B) conv ( F ∪ B ) or conv ( A ∪ G ) \operatorname{conv}(A\cup G) conv ( A ∪ G ) , where F F F is a facet of A A A or G G G is a facet of B B B .
Since A 1 A_{1} A 1 and A 2 A_{2} A 2 have transverse tangent spaces, the facets of A = A 1 + A 2 A=A_{1}+A_{2} A = A 1 + A 2 are of form F 1 + A 2 F_{1}+A_{2} F 1 + A 2 or A 1 + F 2 A_{1}+F_{2} A 1 + F 2 , where F 1 F_{1} F 1 is a facet of A 1 A_{1} A 1 or F 2 F_{2} F 2 is a facet of A 2 A_{2} A 2 . So the facets of conv ( A ∪ B ) \operatorname{conv}(A\cup B) conv ( A ∪ B ) are:
for each facet G G G of B B B , conv ( A ∪ G ) \operatorname{conv}(A\cup G) conv ( A ∪ G ) ,
for each facet F 1 F_{1} F 1 of A 1 A_{1} A 1 , conv ( ( F 1 + A 2 ) ∪ B ) \operatorname{conv}((F_{1}+A_{2})\cup B) conv (( F 1 + A 2 ) ∪ B ) , and
Since A A A and B B B have transverse tangent spaces, B B B and A 2 A_2 A 2 do as well. So by a similar argument to the above, the facets of conv ( A 1 ∪ ( B + α ( A 2 ) ) ) \operatorname{conv}(A_1\cup(B+\alpha(A_2))) conv ( A 1 ∪ ( B + α ( A 2 ))) are:
for each facet F 1 F_1 F 1 of A 1 A_1 A 1 , conv ( F 1 ∪ ( B + α ( A 2 ) ) ) \operatorname{conv}(F_1\cup(B+\alpha(A_2))) conv ( F 1 ∪ ( B + α ( A 2 ))) ,
for each facet G G G of B B B , conv ( A 1 ∪ ( G + α ( A 2 ) ) ) \operatorname{conv}(A_1\cup(G+\alpha(A_2))) conv ( A 1 ∪ ( G + α ( A 2 )))
for each facet F 2 F_2 F 2 of A 2 A_2 A 2 , conv ( A 1 ∪ ( B + α ( F 2 ) ) ) \operatorname{conv}(A_1\cup(B+\alpha(F_2))) conv ( A 1 ∪ ( B + α ( F 2 )))
By the inductive hypothesis, the class (in V ~ S \widetilde{V}_S V S , where S S S contains A 1 A_1 A 1 , G G G and A 2 A_2 A 2 ) of conv ( A 1 ∪ ( G + α ( A 2 ) ) ) \operatorname{conv}(A_1\cup(G+\alpha(A_2))) conv ( A 1 ∪ ( G + α ( A 2 ))) is equal to ( − 1 ) dim ( A 2 ) (-1)^{\dim(A_2)} ( − 1 ) d i m ( A 2 ) times the class conv ( A ∪ G ) \operatorname{conv}(A\cup G) conv ( A ∪ G ) . Similarly, the class of conv ( F 1 ∪ ( B + α ( A 2 ) ) ) \operatorname{conv}(F_1\cup(B+\alpha(A_2))) conv ( F 1 ∪ ( B + α ( A 2 ))) is equivalent to ( − 1 ) dim ( A 2 ) (-1)^{\dim(A_2)} ( − 1 ) d i m ( A 2 ) times the class of conv ( ( F 1 + A 2 ) ∪ B ) \operatorname{conv}((F_1+A_2)\cup B) conv (( F 1 + A 2 ) ∪ B ) . The dimension of F 2 F_2 F 2 is one less than the dimension of A 2 A_2 A 2 , so the class of conv ( A 1 ∪ ( B + α ( F 2 ) ) ) \operatorname{conv}(A_1\cup(B+\alpha(F_2))) conv ( A 1 ∪ ( B + α ( F 2 ))) is − ( − 1 ) dim ( A 2 ) -(-1)^{\dim(A_2)} − ( − 1 ) d i m ( A 2 ) times the class of conv ( ( A 1 + F 2 ) ∪ B ) \operatorname{conv}((A_1+F_2)\cup B) conv (( A 1 + F 2 ) ∪ B ) .
We notice that the outward facing normal vector of conv ( A 1 ∪ ( G + α ( A 2 ) ) ) \operatorname{conv}(A_1\cup(G+\alpha(A_2))) conv ( A 1 ∪ ( G + α ( A 2 ))) is the same as the one for conv ( A ∪ G ) \operatorname{conv}(A\cup G) conv ( A ∪ G ) , and similarly for conv ( F 1 ∪ ( B + α ( A 2 ) ) ) \operatorname{conv}(F_1\cup(B+\alpha(A_2))) conv ( F 1 ∪ ( B + α ( A 2 ))) and conv ( ( F 1 + A 2 ) ∪ B ) \operatorname{conv}((F_1+A_2)\cup B) conv (( F 1 + A 2 ) ∪ B ) , while conv ( A 1 ∪ ( B + α ( F 2 ) ) ) \operatorname{conv}(A_1\cup(B+\alpha(F_2))) conv ( A 1 ∪ ( B + α ( F 2 ))) and conv ( ( A 1 + F 2 ) ∪ B ) \operatorname{conv}((A_1+F_2)\cup B) conv (( A 1 + F 2 ) ∪ B ) have opposite normal vectors. By Theorem 4, this completes the proof.
In particular, if A A A and B B B are zonotopes, then the class of conv ( A ∪ B ) \operatorname{conv}(A\cup B) conv ( A ∪ B ) is, up to lower dimensional terms, equal to ( − 1 ) dim ( A ) (-1)^{\dim(A)} ( − 1 ) d i m ( A ) times the class of conv ( { 0 } , B + α ( A ) ) \operatorname{conv}(\{0\},B+\alpha(A)) conv ({ 0 } , B + α ( A )) . The latter polytope is a paramid.
So, up to lower dimensional terms, support functions of paramids generate R e L U n , 2 \mathrm{ReLU}_{n,2} ReLU n , 2 . Of course, this follows from Theorem 13 as well.
Remark. Even if polytopes A A A and B B B in R n \mathbb{R}^n R n are equivalent modulo terms of dimension < n <n < n , it is not true in general that pyramids on A A A and B B B in R n + 1 \mathbb{R}^{n+1} R n + 1 are equivalent modulo terms of dimension < n + 1 <n+1 < n + 1 . So Theorem 14 is not so useful for inductive arguments.
The Koszul Complex
The chain complex C ∙ n C_\bullet^n C ∙ n that we define is also known as the Koszul complex of the sequence t 1 − 1 , … , t r − 1 t_1-1,\ldots,t_r-1 t 1 − 1 , … , t r − 1 , viewing t 1 − 1 , … , t r − 1 t_1-1,\ldots,t_r-1 t 1 − 1 , … , t r − 1 as elements of Q [ Γ ] \mathbb{Q}[\Gamma] Q [ Γ ] .
Formally, given a ring U U U and a set of elements x 1 , … , x r x_1,\ldots,x_r x 1 , … , x r , the associated Koszul complex K ∙ K_\bullet K ∙ is defined by K p = ⋀ U p U r K_p=\bigwedge^p_U U^r K p = ⋀ U p U r (so K 0 = U K_0=U K 0 = U ). Viewing U r U^r U r as being generated by e 1 , … , e r e_1,\ldots,e_r e 1 , … , e r , the differential is defined by d ( e i ) = x i d(e_i)=x_i d ( e i ) = x i and graded Leibniz. Note that, if U U U is an Q \mathbb{Q} Q -module (e.g. Q [ Γ ] \mathbb{Q}[\Gamma] Q [ Γ ] ), then K p K_p K p is naturally isomorphic to U ⊗ Q ⋀ Q p Q r U\otimes_{\mathbb{Q}}\bigwedge^p_{\mathbb{Q}}\mathbb{Q}^r U ⊗ Q ⋀ Q p Q r .
A sequence F = ( f 1 , … , f r ) F=(f_1,\ldots,f_r) F = ( f 1 , … , f r ) is called a regular sequence if the ideal ( f 1 , … , f r ) (f_1,\ldots,f_r) ( f 1 , … , f r ) is not equal to U U U and, for each i i i , f i f_i f i is not a zero-divisor in R / ( f 1 , … , f i − 1 ) R/(f_1,\ldots,f_{i-1}) R / ( f 1 , … , f i − 1 ) . If f i = t i − 1 f_i=t_i-1 f i = t i − 1 as in § 4.2 , then regularity says that the translations t i t_i t i freely generate an abelian subgroup of Q n \mathbb{Q}^n Q n .
The homology of a Koszul complex of a regular sequence is well understood:
Theorem 15. (See e.g. [35 ] , Corollary 4.5.5) Let U U U be a ring, let f 1 , … , f r f_1,\ldots,f_r f 1 , … , f r be a regular sequence, and let K ∙ K_\bullet K ∙ be the Koszul complex. Then H 0 ( K ∙ ) = U / ( f 1 , … , f r ) H_0(K_\bullet)=U/(f_1,\ldots,f_r) H 0 ( K ∙ ) = U / ( f 1 , … , f r ) , and all higher homology is zero.
The Action of S S S on H ( C ∙ n ) H(C^n_\bullet) H ( C ∙ n )
Let S S S be the doubling map defined in the proof of Theorem 11 (see also Figure 5 ). Instead of using the augmentation condition for cycle filing in C ∙ n C^n_\bullet C ∙ n , we could instead try to compute the action of S S S on H ∙ ( C ∙ ) H_\bullet(C_\bullet) H ∙ ( C ∙ ) . Note that S S S computes with the boundary on C ∙ n C^n_\bullet C ∙ n , so it induces a map S ∗ : H ∙ ( C ∙ n ) → H ∙ ( C ∙ n ) S_*: H_\bullet(C^n_\bullet) \to H_\bullet(C^n_\bullet) S ∗ : H ∙ ( C ∙ n ) → H ∙ ( C ∙ n ) .
Recall from § 4.2.1 that C ∙ n C^n_\bullet C ∙ n is the quotient of the unit-cubical complex C ^ ∙ n \widehat{C}^n_\bullet C ∙ n of R r \mathbb{R}^r R r by the subgroup of Z r \mathbb{Z}^r Z r representing relations among the simplex edge directions t 1 , … , t r t_1,\ldots,t_r t 1 , … , t r . Now S S S lifts to a map C ^ ∙ n → C ^ ∙ n \widehat{C}^n_\bullet\to\widehat{C}^n_\bullet C ∙ n → C ∙ n in a straightforward way.
Note that C ^ ∙ n \widehat{C}^n_\bullet C ∙ n is a cubical complex for R r \mathbb{R}^r R r and C ∙ n C^n_\bullet C ∙ n is a cubical complex for the product R n × ( S 1 ) r − n \mathbb{R}^n \times(S^1)^{r-n} R n × ( S 1 ) r − n . The map π : R r → R n × ( S 1 ) r − n \pi:\mathbb{R}^r \to\mathbb{R}^n \times(S^1)^{r-n} π : R r → R n × ( S 1 ) r − n is the universal covering map of R n × ( S 1 ) r − n \mathbb{R}^n \times(S^1)^{r-n} R n × ( S 1 ) r − n .
Now S S S gives a map R n × ( S 1 ) r − n → R n × ( S 1 ) r − n \mathbb{R}^n \times(S^1)^{r-n} \to\mathbb{R}^n \times(S^1)^{r-n} R n × ( S 1 ) r − n → R n × ( S 1 ) r − n , which lifts to a map S : R r → R r S:\mathbb{R}^r \to\mathbb{R}^r S : R r → R r , which is given by multiplication by 2 2 2 .
Now π 1 ( R n × ( S 1 ) r − n ) \pi_1(\mathbb{R}^n \times(S^1)^{r-n}) π 1 ( R n × ( S 1 ) r − n ) is naturally associated with the group of deck transformations of R r \mathbb{R}^r R r , which is the kernel of π : Γ ^ → Γ \pi:\widehat{\Gamma} \to\Gamma π : Γ → Γ . So we see that S ∗ : π 1 ( R n × ( S 1 ) r − n ) → π 1 ( R n × ( S 1 ) r − n ) S_*:\pi_1(\mathbb{R}^n \times(S^1)^{r-n}) \to\pi_1(\mathbb{R}^n \times(S^1)^{r-n}) S ∗ : π 1 ( R n × ( S 1 ) r − n ) → π 1 ( R n × ( S 1 ) r − n ) is multiplication by 2 2 2 .
So S ∗ : H 1 ( C ∙ n ) → H 1 ( C ∙ n ) S_*:H_1(C^n_\bullet) \to H_1(C^n_\bullet) S ∗ : H 1 ( C ∙ n ) → H 1 ( C ∙ n ) is multiplication by 2 2 2 . By functoriality of the product structure on the (co)homology of ( S 1 ) r − n (S^1)^{r-n} ( S 1 ) r − n , we see that S ∗ : H k ( C ∙ ) → H k ( C ∙ ) S_*:H_k(C_\bullet) \to H_k(C_\bullet) S ∗ : H k ( C ∙ ) → H k ( C ∙ ) is multiplication by 2 k 2^k 2 k . This gives us a different way of seeing that, for a cycle x ∈ C k n x \in C^n_k x ∈ C k n , 2 k x − S ( x ) 2^k x-S(x) 2 k x − S ( x ) is a boundary.
An Alternative Proof of lem:aug
We can make D ∙ n D^n_\bullet D ∙ n into a chain complex with boundary map 0 0 0 . The map ε : C ∙ n → D ∙ n \varepsilon:C^n_\bullet\to D^n_\bullet ε : C ∙ n → D ∙ n commutes with the boundary maps, so descends to a map ε ∗ \varepsilon_* ε ∗ on homology. Since the boundary on D ∙ n D^n_\bullet D ∙ n is 0 0 0 , the homology of D ∙ n D^n_\bullet D ∙ n is just D ∙ n D^n_\bullet D ∙ n .
Recall that Theorem 10 says that ε : C ∙ n → D ∙ n \varepsilon:C^n_\bullet\to D^n_\bullet ε : C ∙ n → D ∙ n sends a cycle x x x to 0 0 0 if and only x x x is a boundary. This is equivalent to saying that ε ∗ : H ∙ ( C ∙ n ) → H ∙ ( D ∙ n ) \varepsilon_*:H_\bullet(C^n_\bullet) \to H_\bullet(D^n_\bullet) ε ∗ : H ∙ ( C ∙ n ) → H ∙ ( D ∙ n ) is injective.
Now D ∙ n D^n_\bullet D ∙ n is a cubicalization of the quotient of R r \mathbb{R}^r R r by the action of Z r \mathbb{Z}^r Z r . Recall that C ∙ n C^n_\bullet C ∙ n is the cubicalization of the quotient of R r \mathbb{R}^r R r by the group of relations among the t i t_i t i , call this group G G G . Now ε \varepsilon ε corresponds to the natural covering map R r / G → R r / Z r \mathbb{R}^r/G \to\mathbb{R}^r/\mathbb{Z}^r R r / G → R r / Z r .
Now H k ( C ∙ n ) H_k(C^n_\bullet) H k ( C ∙ n ) is identified with ⋀ Q k ( Q ⊗ G ) \bigwedge^k_{\mathbb{Q}}(\mathbb{Q}\otimes G) ⋀ Q k ( Q ⊗ G ) and H k ( D ∙ n ) H_k(D^n_\bullet) H k ( D ∙ n ) is identified with ⋀ Q k ( Q ⊗ Z r ) \bigwedge^k_{\mathbb{Q}}(\mathbb{Q}\otimes\mathbb{Z}^r) ⋀ Q k ( Q ⊗ Z r ) , and ε ∗ \varepsilon_* ε ∗ is the map ⋀ Q k ( Q ⊗ G ) → ⋀ Q k ( Q ⊗ Z r ) \bigwedge^k_{\mathbb{Q}}(\mathbb{Q}\otimes G) \to\bigwedge^k_{\mathbb{Q}}(\mathbb{Q}\otimes\mathbb{Z}^r) ⋀ Q k ( Q ⊗ G ) → ⋀ Q k ( Q ⊗ Z r ) induced by the inclusion G → Z r G \to\mathbb{Z}^r G → Z r . This map is injective, giving an alternate proof of Theorem 10.
An Alternate Proof of lem:lowerdimcharacterization
A result of Koutschan, Ponomarchuk, and Schicho [23 ] gives an exact condition for when a continuous piecewise linear function f f f in n n n inputs can be written as a linear combination of “lower-dimensional” functions. Here we show how to derive Theorem 4 from their result. The results of [23 ] are stated over R \mathbb{R} R , so in this section we work with R \mathbb{R} R coefficients instead of Q \mathbb{Q} Q .
The results of [23 ] are stated over the reals. We expect that the results also hold with rational coefficients, but in this section we will allow arbitrary real coefficients.
Let S S S and Q Q Q be finite dimensional real vector spaces, and let g : S → Q g:S \to Q g : S → Q be a piecewise constant function. We allow g g g to be defined only “almost everywhere” (precisely, we say that for “almost all” x ∈ S x \in S x ∈ S , g ( x ) g(x) g ( x ) is defined and constant on a neighborhood of x x x ). Let H ⊆ S H \subseteq S H ⊆ S be an oriented codimension 1 1 1 subspace. For x ∈ H x \in H x ∈ H and ϵ > 0 \epsilon> 0 ϵ > 0 , let B ϵ + ( x ) B^+_\epsilon(x) B ϵ + ( x ) and B ϵ − ( x ) B^-_\epsilon(x) B ϵ − ( x ) be the two halves of the ball of radius ϵ \epsilon ϵ around x x x , split by H H H , with B ϵ + ( x ) B^+_\epsilon(x) B ϵ + ( x ) being the half on the positive side of H H H . For almost all x ∈ H x \in H x ∈ H , g g g is constant on B ϵ + ( x ) B^+_\epsilon(x) B ϵ + ( x ) and B ϵ − ( x ) B^-_\epsilon(x) B ϵ − ( x ) . We define Δ g ( H ) : H → Q \Delta_g(H):H \to Q Δ g ( H ) : H → Q to be the piecewise constant, almost everywhere defined function that is the difference of the values of g g g on B ϵ + B^+_\epsilon B ϵ + and B ϵ − B^-_\epsilon B ϵ − , when this exists. An oriented flag H = ( H 1 , … , H k ) \mathcal{H}=(H_1,\ldots,H_k) H = ( H 1 , … , H k ) of length k k k in S S S is a sequence of oriented codimension 1 1 1 affine subspaces H 1 ⊆ S H_1\subseteq S H 1 ⊆ S and H i + 1 ⊆ H i H_{i+1}\subseteq H_i H i + 1 ⊆ H i . For g : S → Q g:S\to Q g : S → Q piecewise constant and almost everywhere defined, we define Δ g ( H ) \Delta_g(\mathcal{H}) Δ g ( H ) inductively as follows: we define g 1 = Δ g ( H 1 ) g_1=\Delta_g(H_1) g 1 = Δ g ( H 1 ) and g i + 1 = Δ g i ( H i + 1 ) g_{i+1}=\Delta_{g_i}(H_{i+1}) g i + 1 = Δ g i ( H i + 1 ) , and set Δ g ( H ) = g k \Delta_g(\mathcal{H})=g_k Δ g ( H ) = g k . We say that H \mathcal{H} H is critical for g g g if g k g_k g k is non-zero.
Let H = ( H 1 , … , H k ) \mathcal{H}=(H_1,\ldots,H_k) H = ( H 1 , … , H k ) be a flag, and let v 1 , … , v k v_1,\ldots,v_k v 1 , … , v k be vectors such that v i v_i v i is the normal vector to H i H_i H i in H i − 1 H_{i-1} H i − 1 , viewing H 0 H_0 H 0 as the base space S S S . Then, where Δ g ( H ) \Delta_g(\mathcal{H}) Δ g ( H ) is defined, it is equal to:
Δ g ( H ) ( x ) = lim ϵ k → 0 + ⋯ lim ϵ 1 → 0 + ∑ ( s 1 , … , s k ) ∈ { − 1 , 1 } k g ( x + s 1 ϵ 1 v 1 + ⋯ + s k ϵ k v k ) ⋅ ∏ i = 1 k s i \Delta_g(\mathcal{H})(x)=\lim_{\epsilon_k\to0^+}\cdots\lim_{\epsilon_1\to0^+}\sum_{(s_1,\ldots,s_k)\in\{-1,1\}^k}g(x+s_1\epsilon_1v_1+\cdots+s_k\epsilon_kv_k)\cdot\prod_{i=1}^k s_i Δ g ( H ) ( x ) = ϵ k → 0 + lim ⋯ ϵ 1 → 0 + lim ( s 1 , … , s k ) ∈ { − 1 , 1 } k ∑ g ( x + s 1 ϵ 1 v 1 + ⋯ + s k ϵ k v k ) ⋅ i = 1 ∏ k s i
If f : R n → R f:\mathbb{R}^n\to\mathbb{R} f : R n → R is a continuous piecewise linear function, then the gradient ∇ f : R n → R n \nabla f:\mathbb{R}^n\to\mathbb{R}^n ∇ f : R n → R n is a piecewise constant, almost everywhere defined function. The function f f f is said to be a max k \max_k max k if it can be written f = max ( ℓ 1 , … , ℓ k ) f=\max(\ell_1,\ldots,\ell_k) f = max ( ℓ 1 , … , ℓ k ) , where each ℓ i \ell_i ℓ i is an affine function. The following is proved in [23 ] :
Theorem 16. ([23 ] , Theorem 1) Let f : R n → R f:\mathbb{R}^n\to\mathbb{R} f : R n → R be a continuous piecewise linear function. Then we can express f f f as a linear combination of max k + 1 \max_{k+1} max k + 1 functions if and only if every critical flag for ∇ f \nabla f ∇ f has length ≤ k \leq k ≤ k .
A piecewise linear function is said to be homogeneous if every piece extends to a linear function (i.e. an affine function that is 0 0 0 at 0 0 0 ). Given a polytope X X X in R n \mathbb{R}^n R n , its support function h X : R n → R h_X:\mathbb{R}^n\to\mathbb{R} h X : R n → R is defined by h X ( v ) = max x ∈ X ( v ⋅ x ) h_X(v)=\max_{x\in X}(v\cdot x) h X ( v ) = max x ∈ X ( v ⋅ x ) . This is a homogeneous piecewise linear function. There is a linear map from V S V_S V S to the space of homogeneous piecewise linear functions on S S S that sends ( X , Y ) (X,Y) ( X , Y ) to ( h X , h Y ) (h_X,h_Y) ( h X , h Y ) . This is an isomorphism.
A homogeneous max k + 1 \max_{k+1} max k + 1 (that is, a max of k k k linear functions) is the support function of a polytope with k + 1 k+1 k + 1 vertices, which is at most k k k dimensional. So Theorem 16 is close to giving a characterization of V ‾ S \overline{V}_S V S . We need one more lemma:
Lemma 17. If f : R n → R f:\mathbb{R}^n\to\mathbb{R} f : R n → R is a homogeneous piecewise linear function that can be written as a sum max k \max_k max k functions, then f f f can be written as a sum of homogeneous max k \max_k max k functions.
Proof. We write:
f + ∑ i = 1 k a i − ∑ i = 1 j b i = 0 f+\sum_{i=1}^{k}a_i-\sum_{i=1}^{j}b_i=0 f + i = 1 ∑ k a i − i = 1 ∑ j b i = 0
Where each a i a_i a i and b i b_i b i is a max k \max_k max k term. Now obtain a i ′ a_i' a i ′ from a i a_i a i by adding a constant so that a i ′ ( 0 ) = 0 a_i'(0)=0 a i ′ ( 0 ) = 0 . Since f ( 0 ) = 0 f(0)=0 f ( 0 ) = 0 , all the constant terms added must cancel, so:
h X − h Y + ∑ i = 1 j a i ′ − ∑ i = 1 m b i ′ = 0 h_X-h_Y+\sum_{i=1}^{j}a_i'-\sum_{i=1}^{m}b_i'=0 h X − h Y + i = 1 ∑ j a i ′ − i = 1 ∑ m b i ′ = 0
Now each a i ′ a_i' a i ′ or b i ′ b_i' b i ′ is a max of n n n terms, plus a constant. Write a 1 ′ = c 0 + max ( ℓ 1 + c 1 , … , ℓ n + c n ) = c 0 + max ( ℓ 1 + c 0 + c 1 , … , ℓ n + c 0 + c n ) a_1'=c_0+\max(\ell_1+c_1,\ldots,\ell_n+c_n)=c_0+\max(\ell_1+c_0+c_1,\ldots,\ell_n+c_0+c_n) a 1 ′ = c 0 + max ( ℓ 1 + c 1 , … , ℓ n + c n ) = c 0 + max ( ℓ 1 + c 0 + c 1 , … , ℓ n + c 0 + c n ) , where each ℓ i \ell_i ℓ i is linear and each c i c_i c i is a constant. We know that a 1 ( 0 ) = 0 a_1(0)=0 a 1 ( 0 ) = 0 , so all the c 0 + c i c_0+c_i c 0 + c i are ≤ 0 \leq0 ≤ 0 . Obtain a 1 ′ ′ a_1'' a 1 ′′ from a 1 ′ a_1' a 1 ′ by removing all the ℓ i + c 0 + c i \ell_i+c_0+c_i ℓ i + c 0 + c i terms that have c 0 + c i < 0 c_0+c_i<0 c 0 + c i < 0 . Note that a 1 ′ ′ = a 1 ′ a_1''=a_1' a 1 ′′ = a 1 ′ in a neighbourhood of 0 0 0 . We similarly define a i ′ ′ a_i'' a i ′′ and b i ′ ′ b_i'' b i ′′ for each a i a_i a i , and notice that:
f + ∑ i = 1 j α i ′ ′ − ∑ i = 1 m b i ′ ′ = 0 f+\sum_{i=1}^{j}\alpha_i''-\sum_{i=1}^{m}b_i''=0 f + i = 1 ∑ j α i ′′ − i = 1 ∑ m b i ′′ = 0
in a neighborhood of 0. However, both sides are homogeneous, and a homogeneous piecewise linear function is determined by its behavior near 0, so both sides are equal. □
We now have a characterization of V ~ S \widetilde{V}_S V S . Let ( X , Y ) (X,Y) ( X , Y ) represent a class in V ~ S \widetilde{V}_S V S and let g = ∇ ( h X − h Y ) g=\nabla(h_X-h_Y) g = ∇ ( h X − h Y ) . Then ( X , Y ) = 0 (X,Y)=0 ( X , Y ) = 0 in V ~ S \widetilde{V}_S V S if, for every flag H \mathcal{H} H of length n n n , Δ g ( H ) = 0 \Delta_g(\mathcal{H})=0 Δ g ( H ) = 0 . The converse is also true, but this won’t be relevant for our approach.
We say that a flag H ( H 1 , … , H k ) \mathcal{H}(H_1,\ldots,H_k) H ( H 1 , … , H k ) is homogeneous if every H i H_i H i is a vector space (i.e. it contains 0). The following shows that, if we want to apply Theorem 16 to a homogeneous function, then we only need to consider homogeneous flags.
Lemma 18. If f f f is a homogeneous piecewise linear function, g = ∇ f g=\nabla f g = ∇ f and H \mathcal{H} H is a flag, then Δ g ( H ) = 0 \Delta_g(\mathcal{H})=0 Δ g ( H ) = 0 unless H \mathcal{H} H is homogeneous.
Proof. Straightforward. □
Lemma 19. Let X X X be a polytope in R n \mathbb{R}^n R n . Let H = { H 1 , … , H n } \mathcal{H}=\{H_1,\ldots,H_n\} H = { H 1 , … , H n } be a homogeneous flag (so H n = 0 H_n=0 H n = 0 ). Let v 1 , … , v n v_1,\ldots,v_n v 1 , … , v n be vectors such that v i v_i v i is a normal vector to H i H_i H i in H i − 1 H_{i-1} H i − 1 , viewing H 0 = R n H_0=\mathbb{R}^n H 0 = R n . Let F 1 F_1 F 1 and F 2 F_2 F 2 be the faces of X X X in directions v n v_n v n and − v n -v_n − v n respectively. Let S S S be the orthogonal complement of v n v_n v n in R n \mathbb{R}^n R n . For i = 1 , … , n − 1 i=1,\ldots,n-1 i = 1 , … , n − 1 , let H i ′ H_i' H i ′ be the orthogonal complement of v n v_n v n in H i H_i H i , so H ′ = { H 1 ′ , … , H n − 1 ′ } \mathcal{H}'=\{H_1',\ldots,H_{n-1}'\} H ′ = { H 1 ′ , … , H n − 1 ′ } is a flag on S S S . Let f = ∇ h X f=\nabla h_X f = ∇ h X and let f ′ = ∇ h F 1 − ∇ h F 2 f'=\nabla h_{F_1}-\nabla h_{F_2} f ′ = ∇ h F 1 − ∇ h F 2 , where we restrict f ′ f' f ′ to a function S → R n S\to\mathbb{R}^n S → R n . Then Δ f ( H ) ( 0 ) = Δ f ′ ( H ′ ) ( 0 ) \Delta_f(\mathcal{H})(0)=\Delta_{f'}(\mathcal{H}')(0) Δ f ( H ) ( 0 ) = Δ f ′ ( H ′ ) ( 0 ) .
Proof. We know that:
Δ f ( H ) ( 0 ) = lim ε n → 0 + ⋯ lim ε 1 → 0 ∑ ( s 1 , … , s n ) ∈ { − 1 , 1 } n g ( s 1 ε 1 v 1 + ⋯ + s n ε n v n ) ⋅ ∏ i = 1 n s i \Delta_f(\mathcal{H})(0)=\lim_{\varepsilon_n\to0^+}\cdots\lim_{\varepsilon_1\to0}\sum_{(s_1,\ldots,s_n)\in\{-1,1\}^n}g(s_1\varepsilon_1v_1+\cdots+s_n\varepsilon_nv_n)\cdot\prod_{i=1}^{n}s_i Δ f ( H ) ( 0 ) = ε n → 0 + lim ⋯ ε 1 → 0 lim ( s 1 , … , s n ) ∈ { − 1 , 1 } n ∑ g ( s 1 ε 1 v 1 + ⋯ + s n ε n v n ) ⋅ i = 1 ∏ n s i and:
Δ f ′ ( H ′ ) ( 0 ) = lim ε n − 1 → 0 + ⋯ lim ε 1 → 0 + ∑ ( s 1 , … , s n − 1 ) ∈ { − 1 , 1 } n − 1 f ′ ( s 1 ε 1 v 1 + ⋯ + s n − 1 ε n − 1 v n − 1 ) ⋅ ∏ i = 1 n − 1 s i \Delta_{f'}(\mathcal{H}')(0)=\lim_{\varepsilon_{n-1}\to0^+}\cdots\lim_{\varepsilon_1\to0^+}\sum_{(s_1,\ldots,s_{n-1})\in\{-1,1\}^{n-1}}f'(s_1\varepsilon_1v_1+\cdots+s_{n-1}\varepsilon_{n-1}v_{n-1})\cdot\prod_{i=1}^{n-1}s_i Δ f ′ ( H ′ ) ( 0 ) = ε n − 1 → 0 + lim ⋯ ε 1 → 0 + lim ( s 1 , … , s n − 1 ) ∈ { − 1 , 1 } n − 1 ∑ f ′ ( s 1 ε 1 v 1 + ⋯ + s n − 1 ε n − 1 v n − 1 ) ⋅ i = 1 ∏ n − 1 s i Note that h X h_X h X , h F 1 h_{F_1} h F 1 and h F 2 h_{F_2} h F 2 are homogeneous, so f ( λ x ) = f ( x ) f(\lambda x)=f(x) f ( λ x ) = f ( x ) for λ > 0 \lambda>0 λ > 0 , and similarly for f ′ f' f ′ . We observe that, for almost all x ∈ S x\in S x ∈ S :
∇ h F 1 ( x ) = lim ε → 0 + f ( v n + ε x ) \nabla h_{F_1}(x)=\lim_{\varepsilon\to0^+}f(v_n+\varepsilon x) ∇ h F 1 ( x ) = ε → 0 + lim f ( v n + ε x ) To see this, we notice that, for v v v a direction, ∇ f ( v ) \nabla f(v) ∇ f ( v ) is equal to the vertex u u u of X X X that maximizes u ⋅ v u\cdot v u ⋅ v (∇ f ( x ) \nabla f(x) ∇ f ( x ) is defined when this is unique). Now F 1 F_1 F 1 is the set of points u u u in X X X maximizing u ⋅ v n u\cdot v_n u ⋅ v n . So when x x x is sufficiently small, f ( v n + x ) f(v_n+x) f ( v n + x ) is the vertex u u u of F 1 F_1 F 1 maximizing u ⋅ x u\cdot x u ⋅ x , which is equal to h F 1 ( x ) h_{F_1}(x) h F 1 ( x ) .
Similarly, for almost all x ∈ S x\in S x ∈ S , we have:
∇ h F 2 ( x ) = lim ϵ → 0 + f ( − v n + ϵ x ) \nabla h_{F_2}(x)=\lim_{\epsilon\to0^+}f(-v_n+\epsilon x) ∇ h F 2 ( x ) = ϵ → 0 + lim f ( − v n + ϵ x )
So for almost all x ∈ S x\in S x ∈ S , we have:
f ′ ( x ) = lim ϵ → 0 + ( f ( v n + ϵ x ) − f ( − v n + ϵ x ) ) f'(x)=\lim_{\epsilon\to0^+}\left(f(v_n+\epsilon x)-f(-v_n+\epsilon x)\right) f ′ ( x ) = ϵ → 0 + lim ( f ( v n + ϵ x ) − f ( − v n + ϵ x ) )
It follows that Δ f ( H ) ( 0 ) = Δ f ′ ( H ′ ) ( 0 ) \Delta_f(\mathcal{H})(0)=\Delta_{f'}(\mathcal{H'})(0) Δ f ( H ) ( 0 ) = Δ f ′ ( H ′ ) ( 0 ) .
Proof of the “if” direction of Theorem 4. Let X X X and Y Y Y be polytopes in R n \mathbb{R}^n R n . Suppose that, for every direction v v v , ( F 1 + G 2 , F 2 + G 1 ) = 0 (F_1+G_2,F_2+G_1)=0 ( F 1 + G 2 , F 2 + G 1 ) = 0 in V ~ S \widetilde{V}_S V S , where S S S is the orthogonal complement of v v v , F 1 F_1 F 1 and F 2 F_2 F 2 are the faces of X X X in directions v v v and − v -v − v respectively, and G 1 G_1 G 1 and G 2 G_2 G 2 are faces of Y Y Y in directions v v v and − v -v − v respectively.
We want to show that there are A i A_i A i and B i B_i B i such that X + A 1 + ⋯ + A k = Y + B 1 + ⋯ + B j X+A_1+\cdots+A_k=Y+B_1+\cdots+B_j X + A 1 + ⋯ + A k = Y + B 1 + ⋯ + B j . Let f = ∇ ( h X − h Y ) f=\nabla(h_X-h_Y) f = ∇ ( h X − h Y ) . By Theorem 16 and Theorems 17 and 18, it is sufficient to show that, for any homogeneous flag H = { H 1 , … , H n } \mathcal{H}=\{H_1,\ldots,H_n\} H = { H 1 , … , H n } , we have Δ f ( H ) ( 0 ) = 0 \Delta_f(\mathcal{H})(0)=0 Δ f ( H ) ( 0 ) = 0 . This is by induction on n n n .
Let H = { H 1 , … , H n } \mathcal{H}=\{H_1,\ldots,H_n\} H = { H 1 , … , H n } be a flag and let v v v be a vector in H n H_n H n representing the orientation of H n − 1 H_{n-1} H n − 1 . Let F 1 F_1 F 1 , F 2 F_2 F 2 , G 1 G_1 G 1 and G 2 G_2 G 2 be faces of X X X and Y Y Y in directions ± v \pm v ± v , as in the statement of the lemma, but not translated. Let f ′ = ∇ ( h F 1 + h G 2 − h F 2 − h G 1 ) f'=\nabla(h_{F_1}+h_{G_2}-h_{F_2}-h_{G_1}) f ′ = ∇ ( h F 1 + h G 2 − h F 2 − h G 1 ) . By Theorem 19, we have Δ f ′ ( H ′ ) ( 0 ) = Δ f ( H ) ( 0 ) \Delta_{f'}(\mathcal{H'})(0)=\Delta_f(\mathcal{H})(0) Δ f ′ ( H ′ ) ( 0 ) = Δ f ( H ) ( 0 ) , where H ′ \mathcal{H'} H ′ is the flag obtained as in Theorem 19.
Let F 1 ′ F'_1 F 1 ′ , F 2 ′ F'_2 F 2 ′ , G 1 ′ G'_1 G 1 ′ and G 2 ′ G'_2 G 2 ′ be F 1 F_1 F 1 etc. translated to lie in the subspace S S S orthogonal to v v v . Let f ′ ′ = ∇ ( h F 1 ′ + h G 2 ′ − h F 2 ′ − h G 1 ′ ) f''=\nabla(h_{F'_1}+h_{G'_2}-h_{F'_2}-h_{G'_1}) f ′′ = ∇ ( h F 1 ′ + h G 2 ′ − h F 2 ′ − h G 1 ′ ) . Translating a polytope changes its support function by adding a linear function, so f ′ ′ f'' f ′′ differs from f ′ f' f ′ by a constant. Since H ′ \mathcal{H'} H ′ has length ≥ n − 1 ≥ 1 \ge n-1\ge1 ≥ n − 1 ≥ 1 , we have Δ f ′ ′ ( H ′ ) ( 0 ) = Δ f ′ ( H ′ ) ( 0 ) \Delta_{f''}(\mathcal{H'})(0)=\Delta_{f'}(\mathcal{H'})(0) Δ f ′′ ( H ′ ) ( 0 ) = Δ f ′ ( H ′ ) ( 0 ) .
We know that ( F 1 ′ + G 2 ′ , F 2 ′ + G 1 ′ ) = 0 (F'_1+G'_2,F'_2+G'_1)=0 ( F 1 ′ + G 2 ′ , F 2 ′ + G 1 ′ ) = 0 in V ~ S \widetilde{V}_S V S by assumption. In the base case n = 2 n=2 n = 2 , this means that F 1 ′ + G 2 ′ , F 2 ′ + G 1 ′ F'_1+G'_2,F'_2+G'_1 F 1 ′ + G 2 ′ , F 2 ′ + G 1 ′ are translates of each other, so f ′ ′ f'' f ′′ is constant and Δ f ′ ′ ( H ′ ) = 0 \Delta_{f''}(\mathcal{H'})=0 Δ f ′′ ( H ′ ) = 0 . When n > 2 n>2 n > 2 , the “only if” part of Theorem 4 shows that ( F 1 ′ + G 2 ′ , F 2 ′ + G 1 ′ ) (F'_1+G'_2,F'_2+G'_1) ( F 1 ′ + G 2 ′ , F 2 ′ + G 1 ′ ) satisfies the conditions of the lemma. So we know by inductive assumption that Δ f ′ ′ ( H ′ ) ( 0 ) = 0 \Delta_{f''}(\mathcal{H'})(0)=0 Δ f ′′ ( H ′ ) ( 0 ) = 0 . In either case, we conclude that Δ f ( H ) ( 0 ) \Delta_f(\mathcal{H})(0) Δ f ( H ) ( 0 ) , so h X − h Y h_X-h_Y h X − h Y can be written in terms of homogeneous max n \operatorname{max}_n max n terms, which means that ( X , Y ) = 0 (X,Y)=0 ( X , Y ) = 0 in V ~ R n \widetilde{V}_{\mathbb{R}^n} V R n .
Part 2. A Direct Combinatorial Proof
Here we explicitly construct a signed sum of paramids whose support functions equal MAX n \operatorname{MAX}_n MAX n modulo lower-dimensional terms.
Preliminaries
Throughout this part, let [ n ] : = { 1 , … , n } [n]:=\{1,\ldots,n\} [ n ] := { 1 , … , n } and let
Δ : = conv { e 1 , … , e n } ⊂ H : = { x ∈ R n : ∑ i x i = 1 } \Delta:=\operatorname{conv}\{e_1,\ldots,e_n\}\subset H:=\left\{x\in\mathbb{R}^n:\sum_i x_i=1\right\} Δ := conv { e 1 , … , e n } ⊂ H := { x ∈ R n : i ∑ x i = 1 }
be the standard ( n − 1 ) (n-1) ( n − 1 ) -simplex living in the affine subspace H H H such that h Δ = MAX n h_\Delta=\operatorname{MAX}_n h Δ = MAX n . For every index v ∈ [ n ] v\in[n] v ∈ [ n ] , let
V − v : = [ n ] ∖ { v } , H − v : = { p ∈ H : p v = 0 } , Δ − v : = conv { e i : i ∈ V − v } . V_{-v}:=[n]\setminus\{v\},\qquad H_{-v}:=\{p\in H:p_v=0\},\qquad\Delta_{-v}:=\operatorname{conv}\{e_i:i\in V_{-v}\}. V − v := [ n ] ∖ { v } , H − v := { p ∈ H : p v = 0 } , Δ − v := conv { e i : i ∈ V − v } .
Furthermore, let L n − 2 \mathcal{L}_{n-2} L n − 2 be the span of support functions of polytopes in H H H of dimension at most n − 2 n-2 n − 2 . Write f ≡ g f \equiv g f ≡ g if f − g ∈ L n − 2 f-g \in\mathcal{L}_{n-2} f − g ∈ L n − 2 . We write “almost everywhere” to mean “outside a finite union of lower dimensional spaces”. For a polytope P P P and a point q q q , the pyramid with apex q q q and base P P P is denoted as
pyr q ( P ) : = conv ( { q } ∪ P ) . \operatorname{pyr}_{q}(P) := \operatorname{conv}(\{q\} \cup P). pyr q ( P ) := conv ({ q } ∪ P ) .
Standard Valuations
6.1. Standard Valuations. Theorem 2 gives an inclusion–exclusion identity for support functions of a polytope covered by polytopes. The following lemma uses the same valuation property to handle arbitrary linear relations between indicator functions that hold almost everywhere, yielding an identity of support functions modulo lower-dimensional terms.
Lemma 20 (Valuation). Let A ⊆ H A \subseteq H A ⊆ H be a d d d -dimensional affine subspace, let P 1 , … , P k ⊆ A P_1,\ldots,P_k \subseteq A P 1 , … , P k ⊆ A be polytopes, and let c 1 , … , c k ∈ R c_1,\ldots,c_k \in\mathbb{R} c 1 , … , c k ∈ R . If ∑ i = 1 k c i 1 P i = 0 \sum_{i=1}^{k} c_i \mathbf{1}_{P_i}=0 ∑ i = 1 k c i 1 P i = 0 almost everywhere on A A A , then
∑ i = 1 k c i h P i \sum_{i=1}^{k} c_i h_{P_i} i = 1 ∑ k c i h P i is a linear combination of support functions of polytopes in A A A of dimension at most d − 1 d-1 d − 1 . Moreover, for every q ∈ H ∖ A q \in H \setminus A q ∈ H ∖ A ,
∑ i = 1 k c i h pyr q ( P i ) \sum_{i=1}^{k} c_i h_{\operatorname{pyr}_{q}(P_i)} i = 1 ∑ k c i h pyr q ( P i ) is a linear combination of support functions of polytopes in aff ( A ∪ { q } ) \operatorname{aff}(A \cup\{q\}) aff ( A ∪ { q }) of dimension at most d d d .
Proof. The first assertion follows from full additivity of support functions after a suitable subdivision (see Theorem 2 and e.g. [30 ] ). For the second, fix q ∈ H ∖ A q \in H \setminus A q ∈ H ∖ A and set B = aff ( A ∪ { q } ) B=\operatorname{aff}(A \cup\{q\}) B = aff ( A ∪ { q }) . Every section of the pyramids parallel to A A A , apart from the apex, is a common homothetic image of the original polytopes. Their signed indicators therefore cancel almost everywhere on B B B . Apply the first assertion in the ( d + 1 ) (d+1) ( d + 1 ) -dimensional affine space B B B . □
Replacing Simplices by Paramids
The Parallelepipeds
Here we describe the parallelepipeds that form the bases of the paramids in our construction. For v ∈ [ n ] v \in[n] v ∈ [ n ] , an ordering π = ( π 1 , … , π n − 1 ) \pi=(\pi_1,\ldots,\pi_{n-1}) π = ( π 1 , … , π n − 1 ) of V − v V-v V − v , and a set M ⊆ { 2 , … , n − 1 } M \subseteq\{2,\ldots,n-1\} M ⊆ { 2 , … , n − 1 } of marked indices, define the polytope
B v , π , M : = { p ∈ H − v : 0 ≤ u i ≤ 1 ∀ i ∈ M , − 1 ≤ p π i ≤ 0 ∀ i ∈ { 2 , … , n − 1 } ∖ M } , where u i = ∑ j < i p π j . (3) B_{v,\pi,M}:=\left\{p \in H_{-v} :
\begin{array}{ll}
0 \le u_i \le1 & \forall i \in M,\\
-1 \le p_{\pi_i} \le0 & \forall i \in\{2,\ldots,n-1\}\setminus M
\end{array}
\right\},
\qquad\text{where }u_i=\sum_{j<i}p_{\pi_j}. \tag*{(3)} B v , π , M := { p ∈ H − v : 0 ≤ u i ≤ 1 − 1 ≤ p π i ≤ 0 ∀ i ∈ M , ∀ i ∈ { 2 , … , n − 1 } ∖ M } , where u i = j < i ∑ p π j . (3)
Claim 21. The set B v , π , M B_{v,\pi,M} B v , π , M is a parallelepiped.
Proof. Since p v = 0 p_v=0 p v = 0 and ∑ i p i = 1 \sum_i p_i=1 ∑ i p i = 1 , the coordinates p π 2 , … , p π n − 1 p_{\pi_2},\ldots,p_{\pi_{n-1}} p π 2 , … , p π n − 1 determine p p p uniquely. The change of coordinates
t i = { u i = 1 − ∑ j = i n − 1 p π j i ∈ M , − p π i i ∉ M t_i=
\begin{cases}
u_i=1-\sum_{j=i}^{n-1}p_{\pi_j} & i \in M,\\
-p_{\pi_i} & i \notin M
\end{cases} t i = { u i = 1 − ∑ j = i n − 1 p π j − p π i i ∈ M , i ∈ / M
is triangular with diagonal entries − 1 -1 − 1 , and hence invertible. In these coordinates, B v , π , M B_{v,\pi,M} B v , π , M is the cube [ 0 , 1 ] n − 2 [0,1]^{n-2} [ 0 , 1 ] n − 2 . □
The Replacement Lemma
This is the main step that allows us to replace simplices by paramids. For v ∈ [ n ] v \in[n] v ∈ [ n ] and every nonempty R ⊆ V − v R \subseteq V_{-v} R ⊆ V − v , define the dilated simplex
Q v , R = ( n − ∣ R ∣ ) Δ − v − ∑ i ∉ R ∪ { v } e i ⊂ H − v , Q_{v,R} = (n-|R|)\Delta_{-v} - \sum_{i\notin R\cup\{v\}} e_i \subset H_{-v}, Q v , R = ( n − ∣ R ∣ ) Δ − v − i ∈ / R ∪ { v } ∑ e i ⊂ H − v ,
a dilated and translated copy of the facet Δ − v \Delta_{-v} Δ − v . Recall Figure 7 .
Lemma 22. For each v ∈ [ n ] v \in[n] v ∈ [ n ] , the following identity holds:
∑ π ∑ M ⊆ { 2 , … , n − 1 } ( − 1 ) ∣ M ∣ h p y r e v ( B v , π , M ) ≡ ( n − 1 ) ! ∑ ∅ ≠ R ⊆ V − v ( − 1 ) ∣ R ∣ − 1 ∣ R ∣ n − ∣ R ∣ h p y r e v ( Q v , R ) , \sum_{\pi}\sum_{M\subseteq\{2,\ldots,n-1\}}(-1)^{|M|}h_{\mathrm{pyr}_{e_v}}(B_{v,\pi,M}) \equiv(n-1)!\sum_{\varnothing\ne R\subseteq V_{-v}}\frac{(-1)^{|R|-1}|R|}{n-|R|}h_{\mathrm{pyr}_{e_v}}(Q_{v,R}), π ∑ M ⊆ { 2 , … , n − 1 } ∑ ( − 1 ) ∣ M ∣ h pyr e v ( B v , π , M ) ≡ ( n − 1 )! ∅ = R ⊆ V − v ∑ n − ∣ R ∣ ( − 1 ) ∣ R ∣ − 1 ∣ R ∣ h pyr e v ( Q v , R ) , where π \pi π ranges over all orderings of V − v V_{-v} V − v .
The Thermostat Cancellation
Fix v ∈ [ n ] v \in[n] v ∈ [ n ] . We prove that the signed sum of indicator functions over the parallelepipeds B v , π , M B_{v,\pi,M} B v , π , M defined in Eq. (3) has a remarkably simple expression, when summing over all permutations π \pi π and sets of markings M M M , that only depends on the number of positive entries of the argument.
Lemma 23. For every v ∈ [ n ] v \in[n] v ∈ [ n ] and almost every p p p in H − v H_{-v} H − v ,
∑ π ∑ M ⊆ { 2 , … , n − 1 } ( − 1 ) ∣ M ∣ 1 B v , π , M ( p ) = { ( − 1 ) s − 1 s ! ( n − 1 − s ) ! p i > − 1 for all i ∈ V − v , 0 otherwise , \sum_{\pi}\sum_{M\subseteq\{2,\ldots,n-1\}}(-1)^{|M|}\mathbf{1}_{B_{v,\pi,M}}(p)
=
\begin{cases}
(-1)^{s-1}s!(n-1-s)! & p_i>-1\text{ for all }i\in V_{-v},\\
0 & \text{otherwise},
\end{cases} π ∑ M ⊆ { 2 , … , n − 1 } ∑ ( − 1 ) ∣ M ∣ 1 B v , π , M ( p ) = { ( − 1 ) s − 1 s ! ( n − 1 − s )! 0 p i > − 1 for all i ∈ V − v , otherwise , where s = ∣ { i ∈ V − v : p i > 0 } ∣ s=|\{i\in V_{-v}:p_i>0\}| s = ∣ { i ∈ V − v : p i > 0 } ∣ and π \pi π ranges over all orderings of V − v V_{-v} V − v .
Proof. We may assume that no coordinate is 0 or − 1 -1 − 1 , and no proper partial sum of the coordinates is 0 or 1, as this excludes only a finite number of lower dimensional hyperplanes. Fix an ordering π \pi π . For every M M M , membership in B v , π , M B_{v,\pi,M} B v , π , M requires 0 < u i < 1 0<u_i<1 0 < u i < 1 for i ∈ M i\in M i ∈ M and − 1 < p π i < 0 -1<p_{\pi_i}<0 − 1 < p π i < 0 for i ∉ M i\notin M i ∈ / M . Summing over all M M M ,
∑ M ( − 1 ) ∣ M ∣ 1 B v , π , M ( p ) = ∏ i = 2 n − 1 ( 1 { − 1 < p π i < 0 } − 1 { 0 < u i < 1 } ) . \sum_M(-1)^{|M|}\mathbf{1}_{B_{v,\pi,M}}(p)=\prod_{i=2}^{n-1}\left(\mathbf{1}_{\{-1<p_{\pi_i}<0\}}-\mathbf{1}_{\{0<u_i<1\}}\right). M ∑ ( − 1 ) ∣ M ∣ 1 B v , π , M ( p ) = i = 2 ∏ n − 1 ( 1 { − 1 < p π i < 0 } − 1 { 0 < u i < 1 } ) .
Interpret p π 1 , … , p π n − 1 p_{\pi_1},\ldots,p_{\pi_{n-1}} p π 1 , … , p π n − 1 as steps of a walk whose levels are u 1 = 0 , u 2 , … , u n − 1 , u n = 1 u_1=0,u_2,\ldots,u_{n-1},u_n=1 u 1 = 0 , u 2 , … , u n − 1 , u n = 1 . As we describe next, for the product above to be nonzero, the walk must satisfy the thermostat properties: it is positive, rises below 1 and drops above 1.
The walk cannot reach a negative level because once it does, all subsequent permitted steps are negative, so it cannot finish at level 1. It follows that inside ( 0 , 1 ) (0,1) ( 0 , 1 ) the walk must rise (otherwise, it becomes negative). Above 1 it must fall by less than 1. The first step must be positive as well. In particular, all coordinates exceed − 1 -1 − 1 .
Now, assume that every coordinate exceeds − 1 -1 − 1 . Order the s s s positive coordinates and the n − 1 − s n-1-s n − 1 − s negative coordinates separately. There is a unique way to merge these two lists into a walk of the required type; see Figure 10 . Take a positive step first. Take the next positive step whenever the current level is below 1, and the next negative step whenever it is above 1. The required step is always available. Indeed, the remaining steps sum to 1 − u i 1-u_i 1 − u i , which is positive below 1 and negative above 1. Negative steps have size less than 1, so the walk stays positive. The genericity assumption prevents reaching level 1 before the final step.
Figure 10. A thermostat walk obtained by merging the ordered positive and negative coordinate lists shown above it. Take the next positive step below level 1 and the next negative step above level 1.
We obtained a bijection between nonzero products and pairs of orderings of the positive and negative coordinates. There are s ! ( n − 1 − s ) ! s!(n-1-s)! s ! ( n − 1 − s )! pairs of orderings. Every nonzero product has sign ( − 1 ) s − 1 (-1)^{s-1} ( − 1 ) s − 1 , one ( − 1 ) (-1) ( − 1 ) factor for each positive step after the first.
Proof of the Replacement Lemma
Proof of Theorem 22
Proof. Fix a generic p ∈ H − v \mathbf{p} \in H_{-\mathbf{v}} p ∈ H − v . First we prove
∑ π ∑ M ( − 1 ) ∣ M ∣ 1 B v , π , M = ( n − 1 ) ! ∑ ∅ ≠ R ⊆ V − v ( − 1 ) ∣ R ∣ − 1 ∣ R ∣ n − ∣ R ∣ 1 Q v , R . (4) \sum_{\pi}\sum_{M}(-1)^{|M|}\mathbf{1}_{B_{\mathbf{v},\pi,M}}=(n-1)!\sum_{\varnothing\ne R\subseteq V-\mathbf{v}}\frac{(-1)^{|R|-1}|R|}{n-|R|}\mathbf{1}_{Q_{\mathbf{v},R}}. \tag*{(4)} π ∑ M ∑ ( − 1 ) ∣ M ∣ 1 B v , π , M = ( n − 1 )! ∅ = R ⊆ V − v ∑ n − ∣ R ∣ ( − 1 ) ∣ R ∣ − 1 ∣ R ∣ 1 Q v , R . (4)
If some coordinate is less than − 1 -1 − 1 , both sides of (4) vanish, by Theorem 23 and the definition of Q v , R Q_{\mathbf{v},R} Q v , R . Otherwise, let s s s be the number of positive coordinates. The point p \mathbf{p} p belongs to Q v , R Q_{\mathbf{v},R} Q v , R exactly when R R R is contained in the set of its positive coordinates. Thus, for each r r r , exactly ( s r ) \binom{s}{r} ( r s ) sets R R R of size r r r contribute. To evaluate the right-hand side, the hockey-stick identity gives, for 1 ≤ r ≤ n − 1 1\le r\le n-1 1 ≤ r ≤ n − 1 ,
∑ j = 1 r ( r j ) j ! ( n − 1 − j ) ! = r ! ( n − 1 − r ) ! ∑ j = 1 r ( n − 1 − j r − j ) = r ! ( n − 1 − r ) ! ( n − 1 r − 1 ) = ( n − 1 ) ! r n − r . \begin{aligned}
\sum_{j=1}^{r}\binom{r}{j}j!(n-1-j)!=r!(n-1-r)!\sum_{j=1}^{r}\binom{n-1-j}{r-j} \\
&=r!(n-1-r)!\binom{n-1}{r-1}=\frac{(n-1)!r}{n-r}.
\end{aligned} j = 1 ∑ r ( j r ) j ! ( n − 1 − j )! = r ! ( n − 1 − r )! j = 1 ∑ r ( r − j n − 1 − j ) = r ! ( n − 1 − r )! ( r − 1 n − 1 ) = n − r ( n − 1 )! r .
By binomial inversion, the right-hand side is therefore
( n − 1 ) ! ∑ r = 1 s ( − 1 ) r − 1 ( s r ) r n − r = ( − 1 ) s − 1 s ! ( n − 1 − s ) ! . (n-1)!\sum_{r=1}^{s}(-1)^{r-1}\binom{s}{r}\frac{r}{n-r}=(-1)^{s-1}s!(n-1-s)!. ( n − 1 )! r = 1 ∑ s ( − 1 ) r − 1 ( r s ) n − r r = ( − 1 ) s − 1 s ! ( n − 1 − s )! .
Theorem 23 says that the left-hand side is the same. To conclude the proof, apply the coning part of Theorem 20 to Eq. (4) with q = e v \mathbf{q}=\mathbf{e}_{\mathbf{v}} q = e v .
Remark. Before coning, the right-hand side in Theorem 22 is not a single simplex but a signed combination of dilates of the facet Δ − v \Delta_{-\mathbf{v}} Δ − v . Its simplex content cancels, as it must because a simplex is not a signed sum of parallelepipeds. Indeed, the total coefficient of h Δ − v h_{\Delta_{-\mathbf{v}}} h Δ − v before coning is ( n − 1 ) ! ∑ r = 1 n − 1 ( − 1 ) r − 1 ( n − 1 r − 1 ) = 0 (n-1)!\sum_{r=1}^{n-1}(-1)^{r-1}\binom{n-1}{r-1}=0 ( n − 1 )! ∑ r = 1 n − 1 ( − 1 ) r − 1 ( r − 1 n − 1 ) = 0 for n ≥ 3 n\ge3 n ≥ 3 . The identity acquires content only after coning with the apex e v \mathbf{e}_{\mathbf{v}} e v . The pyramids py e v ( Q v , R ) \operatorname{py}_{\mathbf{e}_{\mathbf{v}}}(Q_{\mathbf{v},R}) py e v ( Q v , R ) are no longer dilates of one another.
Subdividing the Simplex
This section uses the valuation property to relate the cones of the simplices Q v , R Q_{v,R} Q v , R to the full simplex Δ \Delta Δ . Recall Figure 6 .
Lemma 24. For every nonempty proper subset ∅ ≠ R ⊊ [ n ] \varnothing\ne R \subsetneq[n] ∅ = R ⊊ [ n ] ,
∑ v ∉ R h pyr e v ( Q v , R ) ≡ ( n − ∣ R ∣ ) h Δ . (5) \sum_{v\notin R} h_{\operatorname{pyr}_{e_v}(Q_{v,R})} \equiv(n-|R|)h_{\Delta}. \tag*{(5)} v ∈ / R ∑ h pyr e v ( Q v , R ) ≡ ( n − ∣ R ∣ ) h Δ . (5) Proof. Let C : = [ n ] ∖ R C := [n] \setminus R C := [ n ] ∖ R and consider the barycenter
q C : = 1 ∣ C ∣ ∑ i ∈ C e i . q_C := \frac{1}{|C|}\sum_{i\in C}e_i. q C := ∣ C ∣ 1 i ∈ C ∑ e i . For every v ∈ C v \in C v ∈ C , let T v = pyr q C ( Δ − v ) T_v=\operatorname{pyr}_{q_C}(\Delta_{-v}) T v = pyr q C ( Δ − v ) . We claim that the simplices T v T_v T v for v ∈ C v \in C v ∈ C form a subdivision of Δ \Delta Δ up to lower dimensional pieces; see Figure 11 . Indeed, consider a generic
Figure 11. Two subdivisions of the tetrahedron Δ \Delta Δ into the simplices T v = pyr q C ( Δ − v ) T_v=\operatorname{pyr}_{q_C}(\Delta_{-v}) T v = pyr q C ( Δ − v ) for v ∈ C v\in C v ∈ C .
x = ∑ i = 1 n λ i e i ∈ Δ x=\sum_{i=1}^{n}\lambda_i e_i\in\Delta x = ∑ i = 1 n λ i e i ∈ Δ , where λ i ≥ 0 \lambda_i\ge0 λ i ≥ 0 and ∑ i λ i = 1 \sum_i\lambda_i=1 ∑ i λ i = 1 . The key observation is
x ∈ T v ⟺ λ v = min i ∈ C λ i . x\in T_v \quad\Longleftrightarrow\quad\lambda_v=\min_{i\in C}\lambda_i. x ∈ T v ⟺ λ v = i ∈ C min λ i . Indeed, if x = t q C + ( 1 − t ) y x=tq_C+(1-t)y x = t q C + ( 1 − t ) y with y ∈ Δ − v y\in\Delta_{-v} y ∈ Δ − v , then λ v = t / ∣ C ∣ \lambda_v=t/|C| λ v = t /∣ C ∣ and λ i ≥ t / ∣ C ∣ \lambda_i\ge t/|C| λ i ≥ t /∣ C ∣ for every i ∈ C i\in C i ∈ C . Conversely, if λ v \lambda_v λ v is minimal, take t = ∣ C ∣ λ v t=|C|\lambda_v t = ∣ C ∣ λ v and y = ( x − t q C ) / ( 1 − t ) ∈ Δ − v y=(x-tq_C)/(1-t)\in\Delta_{-v} y = ( x − t q C ) / ( 1 − t ) ∈ Δ − v when t < 1 t<1 t < 1 and if t = 1 t=1 t = 1 , then x = q C ∈ T v x=q_C\in T_v x = q C ∈ T v . Thus, by Theorem 20,
∑ v ∈ C h T v ≡ h Δ . \sum_{v\in C}h_{T_v}\equiv h_{\Delta}. v ∈ C ∑ h T v ≡ h Δ . By the definitions,
pyr e v ( Q v , R ) = conv ( e v , ∣ C ∣ Δ − v − ∑ i ∈ C ∖ { v } e i ) \operatorname{pyr}_{e_v}(Q_{v,R})=\operatorname{conv}\left(e_v,|C|\Delta_{-v}-\sum_{i\in C\setminus\{v\}}e_i\right) pyr e v ( Q v , R ) = conv e v , ∣ C ∣ Δ − v − i ∈ C ∖ { v } ∑ e i = ∣ C ∣ T v − ∑ i ∈ C ∖ { v } e i , =|C|T_v-\sum_{i\in C\setminus\{v\}}e_i, = ∣ C ∣ T v − i ∈ C ∖ { v } ∑ e i , because e v = ∣ C ∣ q C − ∑ i ∈ C ∖ { v } e i e_v=|C|q_C-\sum_{i\in C\setminus\{v\}}e_i e v = ∣ C ∣ q C − ∑ i ∈ C ∖ { v } e i . Translation changes a support function by a linear function, which is ≡ 0 \equiv0 ≡ 0 . Consequently,
h pyr e v ( Q v , R ) ≡ ∣ C ∣ h T v . h_{\operatorname{pyr}_{e_v}(Q_{v,R})}\equiv|C|h_{T_v}. h pyr e v ( Q v , R ) ≡ ∣ C ∣ h T v .
Summing over v ∈ C v \in C v ∈ C and applying the above gives
∑ v ∉ R h p y r e v ( Q v , R ) ≡ ∣ C ∣ h Δ = ( n − ∣ R ∣ ) h Δ . \sum_{v\notin R} h_{\mathrm{pyr}_{ev}}(Q_{v,R}) \equiv|C|h_{\Delta}=(n-|R|)h_{\Delta}. v ∈ / R ∑ h pyr e v ( Q v , R ) ≡ ∣ C ∣ h Δ = ( n − ∣ R ∣ ) h Δ .
Putting it Together
The following theorem expresses the simplex as a signed sum of paramids modulo lower dimensional pieces.
Theorem 25.
h Δ ≡ ( − 1 ) n n ! ∑ v = 1 n ∑ π ∑ M ⊆ { 2 , … , n − 1 } ( − 1 ) ∣ M ∣ h p y r e v ( B v , π , M ) . h_{\Delta}\equiv\frac{(-1)^n}{n!}\sum_{v=1}^{n}\sum_{\pi}\sum_{M\subseteq\{2,\ldots,n-1\}}(-1)^{|M|}h_{\mathrm{pyr}_{ev}}(B_{v,\pi,M}). h Δ ≡ n ! ( − 1 ) n v = 1 ∑ n π ∑ M ⊆ { 2 , … , n − 1 } ∑ ( − 1 ) ∣ M ∣ h pyr e v ( B v , π , M ) .
Proof. Summing the identity from Theorem 22 over all v ∈ [ n ] v \in[n] v ∈ [ n ] gives
∑ v = 1 n ∑ π ∑ M ⊆ { 2 , … , n − 1 } ( − 1 ) ∣ M ∣ h p y r e v ( B v , π , M ) ≡ ( n − 1 ) ! ∑ ∅ ≠ R ⊊ [ n ] ( − 1 ) ∣ R ∣ − 1 ∣ R ∣ n − ∣ R ∣ ∑ v ∉ R h p y r e v ( Q v , R ) . \sum_{v=1}^{n}\sum_{\pi}\sum_{M\subseteq\{2,\ldots,n-1\}}(-1)^{|M|}h_{\mathrm{pyr}_{ev}}(B_{v,\pi,M})\equiv(n-1)!\sum_{\varnothing\ne R\subsetneq[n]}\frac{(-1)^{|R|-1}|R|}{n-|R|}\sum_{v\notin R}h_{\mathrm{pyr}_{ev}}(Q_{v,R}). v = 1 ∑ n π ∑ M ⊆ { 2 , … , n − 1 } ∑ ( − 1 ) ∣ M ∣ h pyr e v ( B v , π , M ) ≡ ( n − 1 )! ∅ = R ⊊ [ n ] ∑ n − ∣ R ∣ ( − 1 ) ∣ R ∣ − 1 ∣ R ∣ v ∈ / R ∑ h pyr e v ( Q v , R ) .
By Theorem 24 , this equals (with ≡ \equiv ≡ )
( n − 1 ) ! ∑ ∅ ≠ R ⊊ [ n ] ( − 1 ) ∣ R ∣ − 1 ∣ R ∣ h Δ = ( n − 1 ) ! ( ∑ r = 1 n − 1 ( − 1 ) r − 1 r ( n r ) ) h Δ = ( − 1 ) n n ! h Δ . (n-1)!\sum_{\varnothing\ne R\subsetneq[n]}(-1)^{|R|-1}|R|h_{\Delta}=(n-1)!\left(\sum_{r=1}^{n-1}(-1)^{r-1}r\binom{n}{r}\right)h_{\Delta}=(-1)^n n!h_{\Delta}. ( n − 1 )! ∅ = R ⊊ [ n ] ∑ ( − 1 ) ∣ R ∣ − 1 ∣ R ∣ h Δ = ( n − 1 )! ( r = 1 ∑ n − 1 ( − 1 ) r − 1 r ( r n ) ) h Δ = ( − 1 ) n n ! h Δ .
References
Department of Computer Science, University of Copenhagen, Denmark
Email address: flbr@di.ku.dk
University of Technology Nuremberg, Germany
Email address: christoph.hertrich@utn.de
University of Technology Nuremberg, Germany
Email address: kilian.ruess@utn.de
Department of Computer Science, University of Copenhagen, Denmark
Email address: jast@di.ku.dk
Department of Computer Science, University of Copenhagen, Denmark and Department of Mathematics, Technion–IIT
Email address: amye@di.ku.dk