Convexity and nonemptiness are immediate from the definition. For compactness, \(P = \mathrm{conv}\{ v_1, \dots , v_m\} \) is the image of the standard simplex \(\{ \lambda \in \mathbb {R}^m_{\ge 0} : \sum _i \lambda _i = 1\} \), a compact set, under the continuous map \(\lambda \mapsto \sum _i \lambda _i v_i\).

\(\supseteq \): \(\mathrm{conv}(A) + \mathrm{conv}(B)\) is convex (a sum of convex sets) and contains \(A + B\), hence contains \(\mathrm{conv}(A+B)\). \(\subseteq \): let \(p = \sum _i \lambda _i a_i\) and \(q = \sum _j \mu _j b_j\) be convex combinations. Then \(p + q = \sum _{i,j} \lambda _i \mu _j (a_i + b_j)\) is a convex combination of points of \(A + B\). The polytope statement follows by taking \(A, B\) finite.

\(\ge \) holds since \(S \subseteq \mathrm{conv}(S)\). For \(\le \), every \(p \in \mathrm{conv}(S)\) is a convex combination \(p = \sum _i \lambda _i v_i\), so \(\langle x, p \rangle = \sum _i \lambda _i \langle x, v_i\rangle \le \max _i \langle x, v_i\rangle \).

By Lemma 71, \(h_P\) is the pointwise maximum of the finitely many linear functions \(x \mapsto \langle x, v_i\rangle \). A finite maximum of linear functions is convex, positively homogeneous, and continuous, and at every point it agrees with one of the finitely many linear functions, so it is CPWL.

Suppose \(p \in K \setminus K'\). Since \(K'\) is nonempty, compact, and convex, the separating hyperplane theorem yields \(u \in \mathbb {R}^d\) with \(\langle u, p\rangle {\gt} \max _{q \in K'} \langle u, q\rangle = h_{K'}(u)\). Then \(h_K(u) \ge \langle u, p\rangle {\gt} h_{K'}(u)\), a contradiction. By symmetry \(K = K'\).

\(K + K'\) is the image of the compact set \(K \times K'\) under addition, hence compact; convexity and nonemptiness are clear. For every \(x\),

since the two maximizations are independent.

Compactness: the convex hull of a compact subset of \(\mathbb {R}^d\) is compact. Fix \(x\). Since \(K \cup K' \subseteq K * K'\) we get \(h_{K*K'}(x) \ge \max (h_K(x), h_{K'}(x))\). Conversely, every point of \(K * K'\) has the form \((1-t)p + tq\) with \(p \in K\), \(q \in K'\), \(t \in [0,1]\), and \(\langle x, (1-t)p + tq\rangle \le (1-t)h_K(x) + t\, h_{K'}(x) \le \max (h_K(x), h_{K'}(x))\).

Nonemptiness: pick \(p \in K\), \(q \in K'\); the segment \([p, q]\) lies in the convex set \(K \cup K'\), and the closed sets \(\{ t \in [0,1] : (1-t)p + tq \in K\} \) and \(\{ t : (1-t)p + tq \in K'\} \) cover the connected interval \([0,1]\) and are nonempty, hence intersect; any common parameter gives a point of \(K \cap K'\). Compactness and convexity are clear. The inequality \(h_{K\cap K'} \le \min (h_K, h_{K'})\) holds since \(K \cap K' \subseteq K, K'\). For the converse, fix \(x\) and assume without loss of generality \(h_K(x) \le h_{K'}(x)\); we must find \(z \in K \cap K'\) with \(\langle x, z\rangle \ge h_K(x)\). Choose \(p \in K\) with \(\langle x, p\rangle = h_K(x)\) and \(q \in K'\) with \(\langle x, q\rangle = h_{K'}(x)\). If \(p \in K'\) take \(z = p\). Otherwise, as above the segment \([p,q]\) contains a point \(z \in K \cap K'\), say \(z = (1-t)p + tq\); then \(\langle x, z\rangle = (1-t)h_K(x) + t\, h_{K'}(x) \ge h_K(x)\).

Since \(K \cup K'\) is convex and compact, \(K \cup K' = \mathrm{conv}(K \cup K') = K * K'\). Using Lemmas 74, 75 and 76, both sides are nonempty compact convex sets with support function

By Lemma 73 the two sides are equal.

Existence: by Lemma 78 write \(f = \max _i \langle a_i, \cdot \rangle \) and set \(P = \mathrm{conv}\{ a_1, \dots , a_m\} \); then \(f = h_P\) by Lemma 71. Uniqueness: polytopes are nonempty, compact, and convex (Lemma 67), so Lemma 73 applies.

By Lemma 71, \(h_{\Delta _{n-1}}(x) = \max _i \langle x, e_i\rangle = \max _i x_i = \mathrm{MAX}_n(x)\). The reformulation via \(N\) is Definition 80 together with Lemma 72.

Induction on \(k\). A point is a polytope. If \(P = \mathrm{conv}(A)\) and \(Q = \mathrm{conv}(B)\) with \(A, B\) finite, then \(P * Q = \mathrm{conv}(P \cup Q) = \mathrm{conv}(A \cup B)\) is a polytope, and Minkowski sums of polytopes are polytopes by Lemma 68.

For \(P \in \mathcal{P}_k\) we have \(P = P * P\) (the join of a convex set with itself is itself), so \(P\) is a sum with one summand of joins of members of \(\mathcal{P}_k\), i.e. \(P \in \mathcal{P}_{k+1}\). For \(k = 0\), note that a one-point set is the join of itself with itself.

For \(k = 0\): the sum of two points is a point. For \(k \ge 1\): both \(P\) and \(Q\) are finite Minkowski sums of joins of members of \(\mathcal{P}_{k-1}\), and the concatenation of the two sums is again such a finite sum.

Write \(A(x) = L(x) + t\) with \(L\) linear. Induct on \(k\). For \(k = 0\), the image of a point is a point. For the step, affine maps commute with convex hulls and unions, so \(A(P' * Q') = A(P') * A(Q')\) for all polytopes \(P', Q'\). For sums, \(A(P_1 + \dots + P_r) = A(P_1) + L(P_2) + \dots + L(P_r)\), since the translation \(t\) is applied once. Each \(A(P_i * Q_i)\) and each \(L(P_i * Q_i)\) lies in \(\mathcal{P}_{k}\) by the induction hypothesis (both \(A\) and \(L\) are affine) applied inside the join, and \(\mathcal{P}_k\) is closed under Minkowski sums (Lemma 86).

By Lemma 71, \(h_P(u) = \max _i \langle u, v_i\rangle \), so the set \(I\) of indices attaining the maximum is nonempty. A convex combination \(p = \sum _i \lambda _i v_i\) satisfies \(\langle u, p\rangle = h_P(u)\) if and only if all weight is on indices in \(I\); both inclusions follow.

Let \(x \in F_u(P) \cap F_v(P)\). For every \(p \in P\), \(\langle u+v, p\rangle \le h_P(u) + h_P(v) = \langle u+v, x\rangle \), so \(h_P(u+v) = h_P(u) + h_P(v)\) and \(x \in F_{u+v}(P)\). Conversely, if \(y \in F_{u+v}(P)\) then \(\langle u, y\rangle + \langle v, y\rangle = h_P(u) + h_P(v)\), and since neither summand can exceed its own maximum, both are attained, i.e. \(y \in F_u(P) \cap F_v(P)\).

Write \(F = F_u(P)\) and \(G = F_v(F)\), and let \(v_1, \dots , v_m\) be a finite spanning set for \(P\) as in Lemma 89. For \(\varepsilon {\gt} 0\) consider \(w = u + \varepsilon v\). For vertices \(v_i \in F\) we have \(\langle w, v_i\rangle = h_P(u) + \varepsilon \langle v, v_i \rangle \), while for \(v_i \notin F\) the value \(\langle u, v_i\rangle \) is smaller than \(h_P(u)\) by at least some fixed \(\delta {\gt} 0\) (finitely many values). Choosing \(\varepsilon \) small enough that \(\varepsilon \, |\langle v, v_i\rangle | {\lt} \delta /2\) for all \(i\), the maximizers of \(w\) over \(\{ v_1, \dots , v_m\} \) are exactly the maximizers of \(v\) among the vertices lying in \(F\). By Lemma 89 applied twice, \(F_w(P) = F_v(F) = G\).

By Lemma 74, \(h_{P+Q}(u) = h_P(u) + h_Q(u)\). A point \(p + q\) with \(p \in P\), \(q \in Q\) attains this value if and only if \(\langle u, p\rangle = h_P(u)\) and \(\langle u, q\rangle = h_Q(u)\), since neither term can exceed its own maximum.

By Lemma 75, \(h_{P*Q}(u) = \max (h_P(u), h_Q(u))\). Every point of \(P * Q\) is \((1-t)p + tq\) with \(p \in P\), \(q \in Q\), \(t \in [0,1]\), and \(\langle u, (1-t)p + tq\rangle \le (1-t)h_P(u) + t\, h_Q(u)\). If \(h_P(u) {\gt} h_Q(u)\), equality with \(h_{P*Q}(u) = h_P(u)\) forces \(t = 0\) and \(p \in F_u(P)\) (if \(t{\gt}0\) the convex combination is strictly below \(h_P(u)\)); the case \(h_P(u) {\lt} h_Q(u)\) is symmetric. If the two values agree, equality holds precisely when every point of \(P\) or \(Q\) carrying positive weight is a maximizer, i.e. exactly on \(\mathrm{conv}(F_u(P) \cup F_u(Q)) = F_u(P) * F_u(Q)\).

Induction on \(k\). For \(k = 0\) the only face of a point is the point. For the step, let \(P = \sum _i P_i * Q_i \in \mathcal{P}_{k+1}\) with \(P_i, Q_i \in \mathcal{P}_k\) and let \(F = F_u(P)\). By Lemma 92, \(F = \sum _i F_u(P_i * Q_i)\), and by Lemma 93 each \(F_u(P_i * Q_i)\) is \(F_u(P_i)\), \(F_u(Q_i)\), or \(F_u(P_i) * F_u(Q_i)\). By induction each \(F_u(P_i)\) and \(F_u(Q_i)\) lies in \(\mathcal{P}_k\); writing single polytopes \(R\) as the join \(R * R\), every summand is a join of members of \(\mathcal{P}_k\), so \(F \in \mathcal{P}_{k+1}\).

By Lemma 97, \(\Delta _{n-1} + P = Q\) where \(P = \sum _{S \in \mathcal{T}^0} Q_S\) and \(Q = \sum _{S \in \mathcal{T}^1} Q_S\). All the summands lie in \(\mathcal{P}_k\) by hypothesis (they are polytopes by Lemma 84), so \(P, Q \in \mathcal{P}_k\) by Lemma 86 (both index families are nonempty: the singletons lie in \(\mathcal{T}^1\); if \(\mathcal{T}^0\) is empty, replace \(P\) by a point, which lies in \(\mathcal{P}_0 \subseteq \mathcal{P}_k\), translating \(Q\) accordingly). Hence \(\Delta _{n-1}\) is a formal Minkowski difference of members of \(\mathcal{P}_k\), and by Theorem 96 the function \(h_{\Delta _{n-1}} = \mathrm{MAX}_n\) (Lemma 82) lies in \(\mathrm{ReLU}_{n,k}\).

We verify the hypothesis of Theorem 98. Let \(S \subseteq [m]\) be nonempty with \(Q_S \neq \emptyset \); we show by induction on \(|S|\) that \(Q_S\) is a face of \(Q_i\) for each \(i \in S\); the case \(|S| = 1\) is trivial (\(Q_i\) is a face of itself), and \(|S| = 2\) is the subdivision property. For the step, write \(Q_{S \cup \{ j\} } = Q_S \cap (Q_i \cap Q_j)\) for some fixed \(i \in S\): both \(Q_S\) and \(Q_i \cap Q_j\) are faces of \(Q_i\), so their nonempty intersection is a face of \(Q_i\) (Lemma 90), and it is contained in the face \(Q_i \cap Q_j\) of \(Q_j\); a face of \(Q_i\) contained in a common face of \(Q_i\) and \(Q_j\) is a face of that common face by Lemma 90, hence a face of \(Q_j\) by Lemma 91. Finally, faces of \(Q_i \in \mathcal{P}_k\) lie in \(\mathcal{P}_k\) by Lemma 94, so all nonempty \(Q_S\) lie in \(\mathcal{P}_k\) and Theorem 98 applies.

First, \(T = \{ y \in \mathbb {R}^3 : \langle x_i, y\rangle \ge -1 \text{ for } i = 1, \dots , 4\} \): each inequality is verified on the four vertices (\(\langle x_i, x_j\rangle \) equals \(3\) if \(i = j\) and \(-1\) otherwise), giving \(T \subseteq \{ \dots \} \) by convexity, and conversely the four half-space constraints define a bounded set whose extreme points are among solutions of three tight constraints, which are exactly the \(x_i\). Intersecting the \(H\)-description of \(T\) with the sign constraints \(\pm y_1 \le 0\), \(\pm y_2 \le 0\) and enumerating the vertices of each resulting polytope (points where three of the defining inequalities are tight) yields precisely the five listed vertices of each \(Q^{(i)}\); for instance for \(\{ y_1 \le 0, y_2 \le 0\} \) these are \(x_1\), \(x_{12} = (0,0,-1)\), \(x_{13} = (-1,0,0)\), \(x_{14} = (0,-1,0)\) and \(x_{34} = (0,0,1)\). The four sign regions cover \(\mathbb {R}^3\), so the pieces cover \(T\). Pairwise intersections: adjacent pieces meet in \(T \cap \{ y_1 = 0, \pm y_2 \le 0\} \) or \(T \cap \{ y_2 = 0, \pm y_1 \le 0\} \) (triangles, e.g. \(\mathrm{conv}\{ x_{12}, x_{34}, x_{14}\} \)), and opposite pieces meet in \(T \cap \{ y_1 = y_2 = 0\} = \mathrm{conv}\{ x_{12}, x_{34}\} \); each of these is the face of the adjacent pieces in the direction of the corresponding signed coordinate functional(s), by Lemma 89.

Consider \(Q^{(1)}\); the others are analogous (in fact congruent). The base \(Z_1 = \mathrm{conv}\{ x_1, x_{14}, x_{34}, x_{13}\} \) satisfies \(x_1 + x_{34} = x_{14} + x_{13} = (-1,-1,0)\), so it is a parallelogram: \(Z_1 = x_1 + [0, w] + [0, w']\) with \(w = x_{14} - x_1 = (1,0,1)\) and \(w' = x_{13} - x_1 = (0,1,1)\), a Minkowski sum of two segments (and both edge lengths are equal, so it is a rhombus). A segment is the join of its two endpoints, so each segment lies in \(\mathcal{P}_1\), and \(Z_1 \in \mathcal{P}_1\) by Lemma 86. The apex satisfies \(\{ p_1\} \in \mathcal{P}_0 \subseteq \mathcal{P}_1\) (Lemma 85). Since a pyramid is the convex hull of its apex and its base, \(Q^{(1)} = \mathrm{conv}(\{ p_1\} \cup Z_1) = p_1 * Z_1 \in \mathcal{P}_2\).

Taking convex hulls is idempotent and monotone, and \(\mathrm{conv}(A \cup \mathrm{conv}(B)) = \mathrm{conv}(A \cup B)\) for all sets \(A, B\): the left side contains the right since \(A \cup B \subseteq A \cup \mathrm{conv}(B)\), and conversely every convex set containing \(A \cup B\) contains \(\mathrm{conv}(B)\), hence contains \(A \cup \mathrm{conv}(B)\). Apply this twice.

Every point \(z\) of \(v * F = \mathrm{conv}(\{ v\} \cup F)\) has a representation \(z = (1-t)v + t f\) with \(f \in F\) and \(t \in [0,1]\), and for \(z \neq v\) this representation is unique because \(v \notin H\): the coefficient \(t\) is determined by the affine functional that is \(0\) at \(v\) and \(1\) on \(H\), and then \(f\) is determined. Covering: \(f\) lies in some \(Q_i\), so \(z \in v * Q_i\). Intersections: by uniqueness, for \(i \neq j\), \((v * Q_i) \cap (v * Q_j) = v * (Q_i \cap Q_j)\). It remains to show that if \(G = Q_i \cap Q_j\) is a common face, then \(v * G\) is a face of \(v * Q_i\) (and likewise of \(v * Q_j\)). Write \(G = F_u(Q_i)\); we may modify \(u\) by adding multiples of the linear functional defining \(H\) (constant on \(H\), hence not changing maximizers over \(Q_i \subseteq H\)) so that additionally \(\langle u, v \rangle = h_{Q_i}(u)\). For this modified \(u\), the maximizers of \(u\) over the finite spanning set consisting of \(v\) and the vertices of \(Q_i\) are \(v\) together with the maximizers in \(Q_i\), so by Lemma 89, \(F_u(v * Q_i) = v * F_u(Q_i) = v * G\). The empty intersection case is trivial.

\(T\) lies in the hyperplane \(\mathbb {R}^3 \times \{ 0\} \) and \(x_5\) does not, so Lemma 105 applied to the subdivision of Proposition 102 shows that the \(x_5 * Q^{(i)}\) subdivide \(x_5 * T\) (which is a \(4\)-simplex: the join of a point with a \(3\)-simplex not containing it). By Lemma 104 and Lemma 103, \(x_5 * Q^{(i)} = x_5 * (p_i * Z_i) = (x_5 * p_i) * Z_i\). Here \(x_5 * p_i\) is a segment, hence lies in \(\mathcal{P}_1\), and \(Z_i \in \mathcal{P}_1\), so \((x_5 * p_i) * Z_i \in \mathcal{P}_2\).

The \(4\)-simplex \(x_5 * T \subseteq \mathbb {R}^4\) of Proposition 106 is affinely isomorphic to \(\Delta _4 \subseteq \mathbb {R}^5\): an affine isomorphism between their affine hulls carrying vertices to vertices exists, and it extends to an affine map between the ambient spaces composed with an affine retraction onto the affine hull of \(\Delta _4\). Affine isomorphisms carry polyhedral subdivisions to polyhedral subdivisions (they preserve convex hulls, intersections, and faces, by Lemma 89) and preserve membership in \(\mathcal{P}_2\) by Lemma 87. Hence \(\Delta _4\) admits a polyhedral subdivision into four members of \(\mathcal{P}_2\), and Corollary 100 gives \(\mathrm{MAX}_5 \in \mathrm{ReLU}_{5,2}\).

The tetrahedron \(T\) is affinely isomorphic to \(\Delta _3 \subseteq \mathbb {R}^4\); as in Corollary 107, transporting the subdivision of Proposition 102 (whose pieces lie in \(\mathcal{P}_2\) by Lemma 103 and Lemma 87) to \(\Delta _3\) and applying Corollary 100 yields \(\mathrm{MAX}_4 \in \mathrm{ReLU}_{4,2}\).