For every \(x\in \mathbb {R}^n\),

A linear functional attains its maximum over a simplex at a vertex, so this equals \(\max _i\langle x,e_i\rangle =\max _i x_i=\operatorname {MAX}_n(x)\). Hence \(\operatorname {Newt}(\operatorname {MAX}_n)=\Delta _{n-1}\) by uniqueness in the definition of Newton polytope.

For \(k=0\), a finite sum of one-point polytopes is a one-point polytope. For \(k+1\), write each summand as a finite sum of joins \(P_i*Q_i\) with \(P_i,Q_i\in \mathcal{P}_k\). Concatenating all these finite lists gives a single finite sum of such joins, which is precisely an element of \(\mathcal{P}_{k+1}\).

It suffices to compare support functions, because a polytope is determined by its support function. For every direction \(u\), the support function of \(P\cup Q\) is \(\max (h_P(u),h_Q(u))\). Under the hypothesis that \(P\cup Q\) is convex, the smaller of the two exposed support values is attained on the common part \(P\cap Q\), so \(h_{P\cap Q}(u)=\min (h_P(u),h_Q(u))\). Hence

Support functions add under Minkowski sum, so the two Minkowski sums have the same support function and are equal.

Apply Lemma 57 to \(X=\Delta _{n-1}\) and the cover \(Q_1,\ldots ,Q_m\). It yields

By hypothesis every \(Q_S\) lies in \(\mathcal{P}_k\), and Lemma 53 keeps both finite sums in \(\mathcal{P}_k\). Thus \(\Delta _{n-1}\) is a formal Minkowski difference of two polytopes in \(\mathcal{P}_k\). Lemma 55 converts this into a \(k\)-hidden-layer representation of \(h_{\Delta _{n-1}}\), which is \(\operatorname {MAX}_n\) by Lemma 50.

The classes \(\mathcal{P}_k\) are closed under taking faces: a face of a one-point polytope is one point; a face of a finite Minkowski sum is the sum of the corresponding exposed faces; and a face of a join is the join of the exposed faces. Induction on \(k\) proves the closure claim. Since each \(Q_S\) is assumed to be a face of some cell \(Q_i\in \mathcal{P}_k\), it also belongs to \(\mathcal{P}_k\).

The four vertices form an affine copy of \(\Delta _3\). Orthogonal projection to the plane perpendicular to the third coordinate sends them to the four vertices of a square. Cutting the simplex by the two coordinate planes perpendicular to the first and second coordinates separates this square into four quadrants, and lifting these cuts back to the simplex gives the four listed cells. In each cell, the four base points form a parallelogram, hence a rhombus affinely equivalent to the convex hull of two line segments and so in \(\mathcal{P}_1\). Joining that base to the listed apex gives the corresponding rhombic pyramid.

Since \(\Delta _4\) is the join of \(x_5\) with the face \(X\), joining \(x_5\) to each cell of a subdivision of \(X\) subdivides all of \(\Delta _4\). For each cell \(p_i*Z_i\), the segment \(x_5*p_i\) belongs to \(\mathcal{P}_1\), and \(Z_i\) belongs to \(\mathcal{P}_1\) by Construction 60. Their join is therefore an allowed summand in the definition of \(\mathcal{P}_2\).

Taking support functions turns convex hulls into maxima and Minkowski sums into sums. The four cells \((x_5*p_i)*Z_i\) therefore produce the four functions \(P_1,P_2,P_3,P_4\), while the nonempty pairwise and higher intersections of the cells are precisely the lower-dimensional faces whose support functions are \(Q\) and the four \(R\) terms. The alternating inclusion-exclusion identity of Lemma 57 is exactly the signed half-sum in Definition 24.

Construction 60 is the geometric move: a triangle in the join description is replaced by a parallelogram cell. Claim 5 is the algebraic encoding of the same move, converting four extra scalar alternatives into one new paired-sum block and one extra scalar. Claim 7 then implements the paired-sum blocks by one additional ReLU layer. Iterating these two steps gives the depth bound of Theorem 40.