Shallower ReLU Network Representations via Exact Linear Algebra

# Shallower ReLU Network Representations via Exact Linear Algebra
Source: [https://arxiv.org/html/2607.21651](https://arxiv.org/html/2607.21651)
Kilian RueßLead author; all other authors ordered alphabetically\.University of Technology Nuremberg \{kilian\.ruess, christoph\.hertrich, moritz\.stargalla\}@utn\.deFlorestan BrunckUniversity of Copenhagen \{flbr, jast\}@di\.ku\.dkMoritz GrilloMax Planck Institute for Mathematics in the Sciences \{moritz\.grillo, martin\.winter\}@mis\.mpg\.deChristoph HertrichUniversity of Technology Nuremberg \{kilian\.ruess, christoph\.hertrich, moritz\.stargalla\}@utn\.deGeorg LohoFreie Universität Berlin georg\.loho@math\.fu\-berlin\.deJack StadeUniversity of Copenhagen \{flbr, jast\}@di\.ku\.dkMoritz StargallaUniversity of Technology Nuremberg \{kilian\.ruess, christoph\.hertrich, moritz\.stargalla\}@utn\.deMatthew Sunmattsun1@mit\.eduMartin WinterMax Planck Institute for Mathematics in the Sciences \{moritz\.grillo, martin\.winter\}@mis\.mpg\.de

###### Abstract

We prove that the maximum ofnnreal numbers is exactly representable by a ReLU network with two hidden layers for everyn≤10n\\leq 10\. The constructions are obtained by reducing the problem to exact rational linear algebra: after a symmetry reduction, the necessary cancellations are encoded in finite linear systems overℚ\\mathbb\{Q\}, which we solve and verify computationally\. The representation ofmax10\\max\\nolimits\_\{10\}has a structured first hidden layer consisting only of pairwise maxima, a feature that allows it to be recursively substituted into larger networks\. We use this to show that for everyn\>10n\>10, the maximummaxn\\max\\nolimits\_\{n\}can be exactly represented with⌈log5⁡\(n/2\)⌉\+1<log5⁡\(n\)\+1\.5694\\left\\lceil\\log\_\{5\}\(n/2\)\\right\\rceil\+1<\\log\_\{5\}\(n\)\+1\.5694hidden layers\. Via the generalized hinging\-hyperplane representation\[[undefm](https://arxiv.org/html/2607.21651#bib.bibx14)\], the same depth bound holds for all continuous piecewise\-linear functions onℝd\\mathbb\{R\}^\{d\}, withd\+1d\+1in place ofnn\. In particular, every continuous piecewise\-linear function onℝd\\mathbb\{R\}^\{d\}ford≤9d\\leq 9admits a two\-hidden\-layer ReLU representation\. Our results improve on\[[undefb](https://arxiv.org/html/2607.21651#bib.bibx3), STOC’26\]\. In that work, the authors established a two\-hidden\-layer representation formax5\\max\\nolimits\_\{5\}and an upper bound of⌈log3⁡\(n−2\)⌉\+1\\lceil\\log\_\{3\}\(n\-2\)\\rceil\+1hidden layers formaxn\\max\\nolimits\_\{n\}\.

## 1Introduction

A ReLU*network*withDDhidden layers is specified by affine transformationsT\(i\):ℝni−1→ℝniT^\{\(i\)\}\\colon\\mathbb\{R\}^\{n\_\{i\-1\}\}\\to\\mathbb\{R\}^\{n\_\{i\}\}, fori=1,…,D\+1i=1,\\dots,D\+1, and computes

f=T\(D\+1\)∘ReLU∘⋯∘ReLU∘T\(1\),f=T^\{\(D\+1\)\}\\circ\\operatorname\{ReLU\}\\circ\\cdots\\circ\\operatorname\{ReLU\}\\circ T^\{\(1\)\},where the activation functionReLU⁡\(x\)≔max⁡\{0,x\}\\operatorname\{ReLU\}\(x\)\\coloneqq\\max\\\{0,x\\\}is applied coordinate\-wise\. With this convention, the firstDDaffine maps, together with the following applications ofReLU\\operatorname\{ReLU\}, form theDD*hidden layers*, andT\(D\+1\)T^\{\(D\+1\)\}is the output map\.

Every such network computes a*continuous piecewise\-linear function*\(CPWL\\mathrm\{CPWL\}\) with finitely many affine pieces, and conversely everyCPWL\\mathrm\{CPWL\}function can be represented by a ReLU network\[[undef](https://arxiv.org/html/2607.21651#bib.bibx1)\]\. Exact representation by ReLU networks therefore leads to quantitative questions aboutCPWL\\mathrm\{CPWL\}functions: how many neurons are required, and how many hidden layers are required, to represent a given function? This paper concerns the second question when the width is unrestricted\. We study it through the maximum function

maxn⁡\(x\)≔max⁡\{x1,…,xn\}\.\\max\\nolimits\_\{n\}\(x\)\\coloneqq\\max\\\{x\_\{1\},\\dots,x\_\{n\}\\\}\.The reason for this reduction is the generalized hinging\-hyperplane representation of\[[undefm](https://arxiv.org/html/2607.21651#bib.bibx14)\]\[[undefm](https://arxiv.org/html/2607.21651#bib.bibx14)\]\. LetCPWLd\\mathrm\{CPWL\}\_\{d\}denote the space ofCPWL\\mathrm\{CPWL\}functionsf:ℝd→ℝf\\colon\\mathbb\{R\}^\{d\}\\to\\mathbb\{R\}\. Everyf∈CPWLdf\\in\\mathrm\{CPWL\}\_\{d\}can be written as a signed linear combination of maxima ofd\+1d\+1affine functions: there are signsσi∈\{±1\}\\sigma\_\{i\}\\in\\\{\\pm 1\\\}and affine mapsAi:ℝd→ℝd\+1A\_\{i\}\\colon\\mathbb\{R\}^\{d\}\\to\\mathbb\{R\}^\{d\+1\}, fori=1,…,si=1,\\ldots,s, such that

f=∑i=1sσi​maxd\+1⁡\(Ai​\(x\)\)\.f=\\sum\_\{i=1\}^\{s\}\\sigma\_\{i\}\\max\\nolimits\_\{d\+1\}\(A\_\{i\}\(x\)\)\.\(1\)Conversely, a lower bound on the depth for representingmaxd\+1\\max\\nolimits\_\{d\+1\}implies the same lower bound for representingmax⁡\{0,x1,…,xd\}\\max\\\{0,x\_\{1\},\\dots,x\_\{d\}\\\}, and therefore for the worst\-case depth required to represent arbitrary functions inCPWLd\\mathrm\{CPWL\}\_\{d\}, compare the discussion in\[[undeff](https://arxiv.org/html/2607.21651#bib.bibx7)\]\. In that sense, the maximum function can be thought of as being the“hardest”function to represent for neural networks with fixed depth and arbitrary width\.

### 1\.1Known bounds

The starting point is the elementary identity

max⁡\{x1,x2\}=x1\+ReLU⁡\(x2−x1\)\\max\\\{x\_\{1\},x\_\{2\}\\\}=x\_\{1\}\+\\operatorname\{ReLU\}\(x\_\{2\}\-x\_\{1\}\)which gives a one\-hidden\-layer representation ofmax2\\max\\nolimits\_\{2\}\. Iterating this identity in a balanced binary tree givesmaxn\\max\\nolimits\_\{n\}in⌈log2⁡n⌉\\lceil\\log\_\{2\}n\\rceilhidden layers, and hence gives every function inCPWLd\\mathrm\{CPWL\}\_\{d\}in⌈log2⁡\(d\+1\)⌉\\lceil\\log\_\{2\}\(d\+1\)\\rceilhidden layers\[[undef](https://arxiv.org/html/2607.21651#bib.bibx1)\]\.

The corresponding lower\-bound problem is open in general\.\[[undeff](https://arxiv.org/html/2607.21651#bib.bibx7)\]\[[undeff](https://arxiv.org/html/2607.21651#bib.bibx7)\]formulated the unrestricted\-width depth question and connected it with polyhedral and tropical methods\. Their work motivated the conjecture that the binary\-tree depth is optimal for the maximum function\. This conjectured⌈log2⁡n⌉\\lceil\\log\_\{2\}n\\rceillower bound was proved by\[[undefe](https://arxiv.org/html/2607.21651#bib.bibx6)\]\[[undefe](https://arxiv.org/html/2607.21651#bib.bibx6)\]for integral\-weight ReLU networks\. For networks with decimal\-fraction weights\[[undefa](https://arxiv.org/html/2607.21651#bib.bibx2)\]\[[undefa](https://arxiv.org/html/2607.21651#bib.bibx2)\]proved the weaker lower bound⌈log3⁡n⌉\\lceil\\log\_\{3\}n\\rceil\. Further lower bounds are known under braid\-fan compatibility assumptions\[[undefd](https://arxiv.org/html/2607.21651#bib.bibx5)\]and under width restrictions at fixed depth\[[undefk](https://arxiv.org/html/2607.21651#bib.bibx12)\]\.

For unrestricted real weights, however, the binary\-tree construction is not optimal\.\[[undefb](https://arxiv.org/html/2607.21651#bib.bibx3)\]\[[undefb](https://arxiv.org/html/2607.21651#bib.bibx3)\]constructed a two\-hidden\-layer representation ofmax5\\max\\nolimits\_\{5\}and used it to representmaxn\\max\\nolimits\_\{n\}, forn≥4n\\geq 4, with⌈log3⁡\(n−2\)⌉\+1\\lceil\\log\_\{3\}\(n\-2\)\\rceil\+1hidden layers\. Together with the Wang–Sun decomposition, this gives⌈log3⁡\(d−1\)⌉\+1\\lceil\\log\_\{3\}\(d\-1\)\\rceil\+1hidden layers for all functions inCPWLd\\mathrm\{CPWL\}\_\{d\}, ford≥3d\\geq 3\. Thus, over the real numbers, the problem is not only to prove lower bounds\. One must also determine which higher\-arity maximum functions admit shallow representations, and which structural features of such representations allow them to be composed recursively\.

Because ReLU is a nonpolynomial activation function, neural networks with a single hidden layer and affine hidden units can*approximate*any continuous function on a compact domain to arbitrary accuracy\[[undefh](https://arxiv.org/html/2607.21651#bib.bibx9)\]\. The problem of approximatingmaxn\\max\\nolimits\_\{n\}using ReLU neural networks has been studied previously\[[undefl](https://arxiv.org/html/2607.21651#bib.bibx13)\]\. Here, in contrast, we focus on the exact representation of piecewise\-linear functions by ReLU neural networks over the entire spaceℝd\\mathbb\{R\}^\{d\}\.

### 1\.2Our results

We record the three main representation results of this paper below\. They will be restated in their appropriate settings and proved in the subsequent sections\.

###### Theorem 1\.1\.

For everyn≤10n\\leq 10, the function

maxn⁡\(x1,…,xn\)=max⁡\{x1,…,xn\}\\max\\nolimits\_\{n\}\(x\_\{1\},\\ldots,x\_\{n\}\)=\\max\\\{x\_\{1\},\\ldots,x\_\{n\}\\\}admits an exact ReLU representation with two hidden layers\. This representation can be chosen such that the first hidden layer only consists of groups of neurons, each group collectively computing a pairwise maximum of coordinates, that is,max⁡\{xi,xj\}\\max\\\{x\_\{i\},x\_\{j\}\\\}\.

The structured first layer in themaxn\\max\\nolimits\_\{n\}representation is preserved by the recursive substitution introduced in[Section5](https://arxiv.org/html/2607.21651#S5)\. More precisely, a first\-layer comparison between two intermediate maxima can be replaced by a copy of themax10\\max\\nolimits\_\{10\}block\. Each such substitution increases the number of hidden layers by one while multiplying the number of input variables represented by five\. This yields the following general bound\.

###### Corollary 1\.2\.

For every integern≥3n\\geq 3, the functionmaxn\\max\\nolimits\_\{n\}has an exact ReLU representation whose number of hidden layers is bounded by

2\+max⁡\{0,⌈log5⁡\(n10\)⌉\}=⌈log5⁡\(n2\)⌉\+1\.2\+\\max\\left\\\{0,\\left\\lceil\\log\_\{5\}\\left\(\\frac\{n\}\{10\}\\right\)\\right\\rceil\\right\\\}=\\left\\lceil\\log\_\{5\}\\left\(\\frac\{n\}\{2\}\\right\)\\right\\rceil\+1\.

Combining this construction with \([1](https://arxiv.org/html/2607.21651#S1.E1)\) gives the corresponding result for arbitrary continuous piecewise\-linear functions\.

###### Corollary 1\.3\.

Ford≥2d\\geq 2, every function inCPWLd\\mathrm\{CPWL\}\_\{d\}is exactly representable by a ReLU network with at most

⌈log5⁡\(d\+12\)⌉\+1\\left\\lceil\\log\_\{5\}\\left\(\\frac\{d\+1\}\{2\}\\right\)\\right\\rceil\+1hidden layers\. In particular, every function inCPWLd\\mathrm\{CPWL\}\_\{d\}withd≤9d\\leq 9admits an exact representation with two hidden layers\.

### 1\.3Idea of the construction

In describing the construction, it is convenient to allow binary maximum gates with affine inputs\. Such gates are also known as rank\-22maxout units\[[undefc](https://arxiv.org/html/2607.21651#bib.bibx4)\]and have been used in previous work; see, for example,\[[undef](https://arxiv.org/html/2607.21651#bib.bibx1),[undefd](https://arxiv.org/html/2607.21651#bib.bibx5)\]\. This does not change the number of hidden layers, since

max⁡\{L1​\(x\),L2​\(x\)\}=ReLU⁡\(L1​\(x\)\)−ReLU⁡\(−L1​\(x\)\)\+ReLU⁡\(L2​\(x\)−L1​\(x\)\),\\max\\\{L\_\{1\}\(x\),L\_\{2\}\(x\)\\\}=\\operatorname\{ReLU\}\(L\_\{1\}\(x\)\)\-\\operatorname\{ReLU\}\(\-L\_\{1\}\(x\)\)\+\\operatorname\{ReLU\}\\bigl\(L\_\{2\}\(x\)\-L\_\{1\}\(x\)\\bigr\),at the cost of increasing the width of the network by at most a constant factor of33\. Thus, for the depth bounds considered here, this max\-gate model is equivalent to the usual ReLU model\.

Even though it is not necessary for the formal correctness of our construction, for understanding the intuition and some theoretical statements guiding our practical computations, it is useful to take a geometric perspective that relates CPWL functions to polytopes\. This perspective has been used in several previous works on this problem, see\[[undeff](https://arxiv.org/html/2607.21651#bib.bibx7),[undefe](https://arxiv.org/html/2607.21651#bib.bibx6),[undefa](https://arxiv.org/html/2607.21651#bib.bibx2),[undefb](https://arxiv.org/html/2607.21651#bib.bibx3)\]\. A*polytope*is the convex hull of finitely many points\. For a convex, positively homogeneous CPWL functionx↦maxi=1n⁡\{ai⊤​x\}x\\mapsto\\max\_\{i=1\}^\{n\}\\\{a\_\{i\}^\{\\top\}x\\\}, the corresponding*Newton polytope*is defined asconv⁡\{ai:i=1,…,n\}\\operatorname\{conv\}\\\{a\_\{i\}:i=1,\\dots,n\\\}\. Conversely, for a given polytopeP⊂ℝnP\\subset\\mathbb\{R\}^\{n\}, its support function is

hP​\(u\)=maxp∈P⁡⟨u,p⟩\.h\_\{P\}\(u\)=\\max\_\{p\\in P\}\\langle u,p\\rangle\.Taking the Newton polytope and taking support functions are inverse operations of each other, inducing a duality between CPWL functions and polytopes\. This duality is compatible with several operations, namely, function addition corresponds to Minkowski addition of polytopes, taking maxima corresponds to convex hulls, and multiplication with a positive scalar corresponds to dilation of polytopes; effectively turning the duality into an isomorphism with respect to those operations\. This correspondence now allows us to freely switch between the perspectives of CPWL functions and polytopes, thereby enabling proofs about neural network expressivity using polyhedral geometry\.

The targetmaxn\\max\\nolimits\_\{n\}is the support function of the simplexconv⁡\{e1,…,en\}\\operatorname\{conv\}\\\{e\_\{1\},\\ldots,e\_\{n\}\\\}, while each pairwise maximummax⁡\{xi,xj\}\\max\\\{x\_\{i\},x\_\{j\}\\\}is the support function of the segment\[ei,ej\]\[e\_\{i\},e\_\{j\}\]\. Thus, sums of pairwise maxima and maxima of such sums correspond, respectively, to Minkowski sums and convex hulls\. This motivates our ansatz in terms of support functions of explicit polytopes\.

Based on theSnS\_\{n\}\-symmetry of the simplex, one can symmetrize any solution, that is, combine all solutions in the orbit of permuting variables\. Therefore, it suffices to establish the resulting identities on the sorted cone

𝒞=\{x∈ℝn∣x1≤⋯≤xn\}\.\\mathcal\{C\}=\\left\\\{x\\in\\mathbb\{R\}^\{n\}\\mid x\_\{1\}\\leq\\cdots\\leq x\_\{n\}\\right\\\}\.There, each pairwise maximum reduces to a coordinate projection, and the search becomes a finite linear\-algebra problem overℚ\\mathbb\{Q\}: find a signed combination of the symmetrized functions equal toxn=maxn⁡\(x\)x\_\{n\}=\\max\\nolimits\_\{n\}\(x\)\. The resulting rational identities are verified exactly and extend to all ofℝn\\mathbb\{R\}^\{n\}by symmetry\.

### 1\.4Organization

[Section2](https://arxiv.org/html/2607.21651#S2)explains the support\-function linear algebra used to certify identities\.[Section3](https://arxiv.org/html/2607.21651#S3)proves the reduction from symmetric identities to the sorted cone\.[Section4](https://arxiv.org/html/2607.21651#S4)defines the finite ansatz, gives the exact verification method, and states the two\-hidden\-layer result forn≤10n\\leq 10\.[Section5](https://arxiv.org/html/2607.21651#S5)proves the recursive substitution theorem and derives the base\-five depth bound\.

## 2Signed Minkowski identities as linear algebra

Even though our construction developed later in the paper does not explicitly use the perspective of Newton polytopes, our approach is nevertheless inspired by it\. The purpose of this section is to explain this geometric intuition and how it relates to previous work on the problem\.

In\[[undefb](https://arxiv.org/html/2607.21651#bib.bibx3)\], the authors construct neural networks computing the maximum function by showing that a subdivision of the simplex into structured cells makes it possible to express the simplex as a weighted Minkowski difference of polytopes whose support functions are representable with two hidden layers\. This makes it possible to conclude that the maximum function itself can be expressed with two hidden layers\.

We follow this idea, but avoid constructing a subdivision explicitly and instead work directly with the weighted Minkowski difference\. The basic problem is the following\. Given a finite set of promising polytopesQ1,…,QrQ\_\{1\},\\ldots,Q\_\{r\}, for which we already know that they are representable with two hidden layers, we want to find coefficientsci∈ℝc\_\{i\}\\in\\mathbb\{R\}such that the formal Minkowski identity

P=∑i=1rci​QiP=\\sum\_\{i=1\}^\{r\}c\_\{i\}Q\_\{i\}holds, allowing the conclusion thatPPis also representable with two hidden layers\. Note that, in this equation, some of coefficientscic\_\{i\}can be negative\. By definition, such a weighted Minkowski sum with potentially negative weights, means the following equality of ordinary Minkowski sums:

P\+∑ci<0\(−ci\)​Qi=∑ci\>0ci​Qi\.P\+\\sum\_\{c\_\{i\}<0\}\(\-c\_\{i\}\)Q\_\{i\}=\\sum\_\{c\_\{i\}\>0\}c\_\{i\}Q\_\{i\}\.Passing to support functions translates this into the identity of functionsℝd→ℝ\\mathbb\{R\}^\{d\}\\to\\mathbb\{R\}

hP=∑i=1rci​hQi\.h\_\{P\}=\\sum\_\{i=1\}^\{r\}c\_\{i\}h\_\{Q\_\{i\}\}\.Since all support functions involved are piecewise linear, this identity can be reduced to a finite linear system by evaluating it on a suitable finite set of points\. This reduction is justified by the following proposition\. A*complete polyhedral fan*inℝn\\mathbb\{R\}^\{n\}is a finite collection of polyhedral cones with apex at the origin, closed under taking faces, such that the intersection of any two cones is a face of each, and whose union is all ofℝn\\mathbb\{R\}^\{n\}\.

###### Proposition 2\.1\.

LetΣ\\Sigmabe a complete polyhedral fan and consider polytopesP,Q1,…,QrP,Q\_\{1\},\\dots,Q\_\{r\}such that each of the support functionshP,hQ1,…,hQrh\_\{P\},h\_\{Q\_\{1\}\},\\ldots,h\_\{Q\_\{r\}\}is linear on every individual cone ofΣ\\Sigma\. For each coneτ∈Σ\\tau\\in\\Sigma, letUτU\_\{\\tau\}be a set of generators of its extreme rays\. Let

U=⋃τ∈ΣUτ\.U=\\bigcup\_\{\\tau\\in\\Sigma\}U\_\{\\tau\}\.Define

Au​i=hQi​\(u\),bu=hP​\(u\)\(u∈U\)\.A\_\{ui\}=h\_\{Q\_\{i\}\}\(u\),\\qquad b\_\{u\}=h\_\{P\}\(u\)\\qquad\(u\\in U\)\.Then

hP=∑i=1rci​hQi⟺A​c=b\.h\_\{P\}=\\sum\_\{i=1\}^\{r\}c\_\{i\}h\_\{Q\_\{i\}\}\\quad\\Longleftrightarrow\\quad Ac=b\.

###### Proof\.

The functionhP−∑ici​hQih\_\{P\}\-\\sum\_\{i\}c\_\{i\}h\_\{Q\_\{i\}\}is linear on every cone ofΣ\\Sigma\. A linear function on a cone vanishes identically if and only if it vanishes on the extreme rays of that cone\. SinceΣ\\Sigmacoversℝd\\mathbb\{R\}^\{d\}, the global identity is therefore equivalent to the finite systemA​c=bAc=b\. ∎

[Proposition2\.1](https://arxiv.org/html/2607.21651#S2.Thmtheorem1)suggests the following procedure to find a neural network representation ofmaxn\\max\_\{n\}\. LetPPbe the standard simplexconv⁡\{e1,…,en\}\\operatorname\{conv\}\\\{e\_\{1\},\\dots,e\_\{n\}\\\}, which is the Newton polytope ofmaxn\\max\_\{n\}\. Select promising candidate polytopesQ1,…,QrQ\_\{1\},\\dots,Q\_\{r\}, for which we already know that they admit two\-hidden\-layer representations\. Use[Proposition2\.1](https://arxiv.org/html/2607.21651#S2.Thmtheorem1)to reduce the signed Minkowski identity to a finite linear system and check with exact rational arithmetic if it has a solution\. If we find a solution, this implies a representation ofmaxn\\max\_\{n\}with two hidden layers\. If the system has no solution, this means that the set of candidate polytopes is not sufficient to representmaxn\\max\_\{n\}\.

## 3Symmetrization

Let the symmetric groupSnS\_\{n\}act onℝn\\mathbb\{R\}^\{n\}by permuting coordinates\. Explicitly, forx∈ℝnx\\in\\mathbb\{R\}^\{n\}andσ∈Sn\\sigma\\in S\_\{n\}, define

\(σ​x\)i≔xσ−1​\(i\)for​i∈\{1,…,n\}\.\(\\sigma x\)\_\{i\}\\coloneqq x\_\{\\sigma^\{\-1\}\(i\)\}\\qquad\\text\{for \}i\\in\\\{1,\\ldots,n\\\}\.For any functionf:ℝn→ℝf\\colon\\mathbb\{R\}^\{n\}\\to\\mathbb\{R\}, define its*symmetrization*by

fsym​\(x\)=1n\!​∑σ∈Snf​\(σ​x\)\.f^\{\\operatorname\{sym\}\}\(x\)=\\frac\{1\}\{n\!\}\\sum\_\{\\sigma\\in S\_\{n\}\}f\(\\sigma x\)\.We call a functionf:ℝn→ℝf\\colon\\mathbb\{R\}^\{n\}\\to\\mathbb\{R\}*symmetric*iffsym=ff^\{\\operatorname\{sym\}\}=f\.

###### Proposition 3\.1\.

Letg:ℝn→ℝg\\colon\\mathbb\{R\}^\{n\}\\to\\mathbb\{R\}be symmetric\. Ifg=∑i=1nci​fig=\\sum\_\{i=1\}^\{n\}c\_\{i\}f\_\{i\}, then

g=∑i=1nci​fisym\.g=\\sum\_\{i=1\}^\{n\}c\_\{i\}f\_\{i\}^\{\\operatorname\{sym\}\}\.Moreover, iff,h:ℝn→ℝf,h\\colon\\mathbb\{R\}^\{n\}\\to\\mathbb\{R\}are symmetric, thenf=hf=honℝn\\mathbb\{R\}^\{n\}if and only iff=hf=hon

𝒞=\{x∈ℝn:x1≤x2≤⋯≤xn\}\.\\mathcal\{C\}=\\\{x\\in\\mathbb\{R\}^\{n\}:x\_\{1\}\\leq x\_\{2\}\\leq\\cdots\\leq x\_\{n\}\\\}\.

###### Proof\.

Symmetrization is linear and fixes symmetric functions, giving the first claim\. For the second, every point ofℝn\\mathbb\{R\}^\{n\}is carried into𝒞\\mathcal\{C\}by a coordinate permutation\. ∎

Thus, in order to check whether a symmetric candidate equalsmaxn\\max\\nolimits\_\{n\}, it is sufficient to check whether it equalsxnx\_\{n\}on𝒞\\mathcal\{C\}\. Note that𝒞\\mathcal\{C\}is one cell of the braid arrangement, see\[[undefd](https://arxiv.org/html/2607.21651#bib.bibx5)\]\.

## 4Exact search for two\-hidden\-layer identities

This section describes the finite search space used to find the two\-hidden\-layer representations\. The search has three steps\. First we choose a restricted family of two\-hidden\-layer ReLU blocks whose first hidden layer consists only of pairwise maxima\. Then we average these blocks over all coordinate permutations, so that it is enough to test them on the sorted cone\. Finally we expand the resulting functions into linear terms and hinge terms and solve the resulting rational linear system\.

### 4\.1The two\-layer ansatz

Let

ℰn≔\{\(i,j\)∣1≤i≤j≤n\}\\mathcal\{E\}\_\{n\}\\coloneqq\\\{\(i,j\)\\mid 1\\leq i\\leq j\\leq n\\\}denote the set of unordered pairs of indices, represented by listing the smaller index first\. By definition, diagonal elements\(i,i\)\(i,i\)are included\. For\(i,j\)∈ℰn\(i,j\)\\in\\mathcal\{E\}\_\{n\}define

mi​j​\(x\)=max⁡\{xi,xj\}\.m\_\{ij\}\(x\)=\\max\\\{x\_\{i\},x\_\{j\}\\\}\.Fixk∈ℕk\\in\\mathbb\{N\}, and letℳn,k\\mathcal\{M\}\_\{n,k\}denote the set of multisets of cardinalitykkwith elements inℰn\\mathcal\{E\}\_\{n\}\. Thus, an elementA∈ℳn,kA\\in\\mathcal\{M\}\_\{n,k\}is a collection ofkkpairs fromℰn\\mathcal\{E\}\_\{n\}, counted with multiplicity, so the same pair may occur several times\. Sinceℰn\\mathcal\{E\}\_\{n\}is finite, the setℳn,k\\mathcal\{M\}\_\{n,k\}, and hence the set of pairs

ℳn,k×ℳn,k\\mathcal\{M\}\_\{n,k\}\\times\\mathcal\{M\}\_\{n,k\}is finite\. For each\(A,B\)∈ℳn,k×ℳn,k\(A,B\)\\in\\mathcal\{M\}\_\{n,k\}\\times\\mathcal\{M\}\_\{n,k\}, define

ΦA,B​\(x\)=max⁡\{∑\(i,j\)∈Ami​j​\(x\),∑\(i,j\)∈Bmi​j​\(x\)\},\\Phi\_\{A,B\}\(x\)=\\max\\left\\\{\\sum\_\{\(i,j\)\\in A\}m\_\{ij\}\(x\),\\sum\_\{\(i,j\)\\in B\}m\_\{ij\}\(x\)\\right\\\},where each sum is taken with multiplicity\. This is representable with a two\-hidden\-layer network: the first hidden layer computes the pairwise maximami​jm\_\{ij\}, and the second hidden layer computes the maximum of the two displayed linear combinations\.

We ask whethermaxn\\max\\nolimits\_\{n\}lies in the linear span of all symmetrized functions

FA,B​\(x\)=n\!​ΦA,Bsym​\(x\)=∑σ∈SnΦA,B​\(σ​x\),\(A,B\)∈ℳn,k×ℳn,k\.F\_\{A,B\}\(x\)=n\!\\,\\Phi\_\{A,B\}^\{\\operatorname\{sym\}\}\(x\)=\\sum\_\{\\sigma\\in S\_\{n\}\}\\Phi\_\{A,B\}\(\\sigma x\),\\qquad\(A,B\)\\in\\mathcal\{M\}\_\{n,k\}\\times\\mathcal\{M\}\_\{n,k\}\.The factor1/n\!1/n\!appearing in the corresponding group average is omitted, since it merely rescales the solution coefficients\.

For computational or structural purposes, one may restrict the system to a chosen subfamily of pairs\(A,B\)\(A,B\); unless stated otherwise, however, the ansatz includes all pairs in

ℳn,k×ℳn,k\.\\mathcal\{M\}\_\{n,k\}\\times\\mathcal\{M\}\_\{n,k\}\.
By[Proposition3\.1](https://arxiv.org/html/2607.21651#S3.Thmtheorem1), it suffices to work on the sorted cone

𝒞=\{x∈ℝn∣x1≤x2≤⋯≤xn\}\.\\mathcal\{C\}=\\left\\\{x\\in\\mathbb\{R\}^\{n\}\\mid x\_\{1\}\\leq x\_\{2\}\\leq\\cdots\\leq x\_\{n\}\\right\\\}\.
On𝒞\\mathcal\{C\}, the first\-layer functionsmi​jm\_\{ij\}collapse to coordinate projections onto the variable with the larger index: namely,

mi​j​\(σ​x\)=mi​j​\(xσ−1​\(1\),…,xσ−1​\(n\)\)=xmax⁡\{σ−1​\(i\),σ−1​\(j\)\}\.m\_\{ij\}\(\\sigma x\)=m\_\{ij\}\(x\_\{\\sigma^\{\-1\}\(1\)\},\\ldots,x\_\{\\sigma^\{\-1\}\(n\)\}\)=x\_\{\\max\\\{\\sigma^\{\-1\}\(i\),\\sigma^\{\-1\}\(j\)\\\}\}\.Thus, after restriction to𝒞\\mathcal\{C\}, the first layer is linear and introduces no additional breakpoints\. For a multisetA∈ℳn,kA\\in\\mathcal\{M\}\_\{n,k\}andσ∈Sn\\sigma\\in S\_\{n\}, put

ℓσ,A​\(x\)≔∑\(i,j\)∈Axmax⁡\{σ−1​\(i\),σ−1​\(j\)\}\.\\ell\_\{\\sigma,A\}\(x\)\\coloneqq\\sum\_\{\(i,j\)\\in A\}x\_\{\\max\\\{\\sigma^\{\-1\}\(i\),\\sigma^\{\-1\}\(j\)\\\}\}\.Then, on𝒞\\mathcal\{C\},

FA,B​\(x\)=∑σ∈Snmax⁡\{ℓσ,A​\(x\),ℓσ,B​\(x\)\}\.F\_\{A,B\}\(x\)=\\sum\_\{\\sigma\\in S\_\{n\}\}\\max\\\{\\ell\_\{\\sigma,A\}\(x\),\\ell\_\{\\sigma,B\}\(x\)\\\}\.Using

max⁡\{u,v\}=u\+ReLU⁡\(v−u\)\\max\\\{u,v\\\}=u\+\\operatorname\{ReLU\}\(v\-u\)and collecting identical difference vectors, we obtain

FA,B​\(x\)=LA,B​\(x\)\+∑d∈DA,BcA,B,d​ReLU⁡\(d⊤​x\),F\_\{A,B\}\(x\)=L\_\{A,B\}\(x\)\+\\sum\_\{d\\in D\_\{A,B\}\}c\_\{A,B,d\}\\operatorname\{ReLU\}\\left\(d^\{\\top\}x\\right\),whereLA,BL\_\{A,B\}is linear,DA,B⊂ℤnD\_\{A,B\}\\subset\\mathbb\{Z\}^\{n\}is finite, andcA,B,d∈ℤc\_\{A,B,d\}\\in\\mathbb\{Z\}\. Consequently, a representationmaxn=∑A,BλA,B​FA,B\\max\\nolimits\_\{n\}=\\sum\_\{A,B\}\\lambda\_\{A,B\}F\_\{A,B\}is certified by the exact equations

∑A,BλA,B​cA,B,d\\displaystyle\\sum\_\{A,B\}\\lambda\_\{A,B\}c\_\{A,B,d\}=0for all​d∈⋃A,BDA,B\\displaystyle=0\\quad\\text\{for all \}d\\in\\bigcup\_\{A,B\}D\_\{A,B\}\(2\)∑A,BλA,B​LA,B​\(x\)\\displaystyle\\qquad\\sum\_\{A,B\}\\lambda\_\{A,B\}L\_\{A,B\}\(x\)=xn\.\\displaystyle=x\_\{n\}\.\(3\)The first set of equations \([2](https://arxiv.org/html/2607.21651#S4.E2)\) says that every nonlinear hinge term cancels\. The second \([3](https://arxiv.org/html/2607.21651#S4.E3)\) says that the remaining linear function isxnx\_\{n\}, which equalsmaxn\\max\\nolimits\_\{n\}on the sorted cone𝒞\\mathcal\{C\}\.

#### 4\.1\.1Enumeration modulo permutations

The functionFA,BF\_\{A,B\}is invariant under interchangingAAandBB, as well as under simultaneously relabelling all indices in both multisets\. Hence it suffices to consider pairs\(A,B\)\(A,B\)modulo the equivalence relation

\(A,B\)∼\(B,A\)∼\(τ​A,τ​B\)∼\(τ​B,τ​A\),τ∈Sn\.\(A,B\)\\sim\(B,A\)\\sim\(\\tau A,\\tau B\)\\sim\(\\tau B,\\tau A\),\\qquad\\tau\\in S\_\{n\}\.We use\{\{⋯\}\}\\\{\\\!\\\{\\cdots\\\}\\\!\\\}to denote multisets, so repetitions indicate multiplicity\. Here,

τ​A≔\{\{\(min⁡\{τ​\(i\),τ​\(j\)\},max⁡\{τ​\(i\),τ​\(j\)\}\):\(i,j\)∈A\}\}\\tau A\\coloneqq\\\{\\\!\\\{\\bigl\(\\min\\\{\\tau\(i\),\\tau\(j\)\\\},\\max\\\{\\tau\(i\),\\tau\(j\)\\\}\\bigr\):\(i,j\)\\in A\\\}\\\!\\\}with multiplicities retained\. We refer to an equivalence class under this relation as a*template*\.

Equivalently, a pair\(A,B\)\(A,B\)may be regarded as a two\-edge\-colored multigraph on the vertex set\{1,…,n\}\\\{1,\\ldots,n\\\}\. The pairs inAAform the edges of one color, those inBBform the edges of the other color, and all edge multiplicities are retained\. If diagonal pairs are permitted in the ansatz, they are represented by loops\. InterchangingAAandBBcorresponds to exchanging the two edge colors, while simultaneous permutation of the indices corresponds to relabelling the vertices\. Template enumeration is therefore a colored\-multigraph isomorphism problem, with the two colors themselves regarded as interchangeable\.

In the implementation, each isomorphism class is replaced by a canonical labelled representative\. All certificate coefficients are then aggregated according to this canonical unordered pair before the finite linear system is assembled\. The required isomorphism classes can be enumerated efficiently using standard graph\-isomorphism software, such as*nauty*\[[undefi](https://arxiv.org/html/2607.21651#bib.bibx10)\]\.

### 4\.2The smallest useful value ofkk

The parameterkkcontrols the expressive power and the size of the computational ansatz\. Each argument ofΦA,B\\Phi\_\{A,B\}does contain the sum ofkkpairwise maxima, so increasingkkenlarges the class of functions that the ansatz can represent\. At the same time, the number of pairs of multisets\(A,B\)\(A,B\)grows rapidly withkk\. It is therefore natural to ask for the smallest value ofkkthat is not ruled out by theoretical obstructions\.

###### Proposition 4\.2\.

LetΔk=conv⁡\{0,e1,…,ek\}\\Delta\_\{k\}=\\operatorname\{conv\}\\\{0,e\_\{1\},\\ldots,e\_\{k\}\\\}\. There do not exist polytopesP1,…,PmP\_\{1\},\\ldots,P\_\{m\}withdimPr<k\\dim P\_\{r\}<kand coefficientscr∈ℝc\_\{r\}\\in\\mathbb\{R\}such that

hΔk=∑r=1mcr​hPr\.h\_\{\\Delta\_\{k\}\}=\\sum\_\{r=1\}^\{m\}c\_\{r\}h\_\{P\_\{r\}\}\.Equivalently, akk\-simplex is not a signed Minkowski combination of lower\-dimensional polytopes\.

###### Proof\.

This is precisely\[[undefg](https://arxiv.org/html/2607.21651#bib.bibx8), Corollary 5\.2\], translated into support\-function language\. In the terminology of that paper, the assertion is that a simplex is not a zero summand\. ∎

###### Corollary 4\.3\.

The exact systems assembled from the ansatz above are solvable only if

k≥kmin≔⌊n−12⌋\.k\\geq k\_\{\\min\}\\coloneqq\\left\\lfloor\\frac\{n\-1\}\{2\}\\right\\rfloor\.Thus,kmink\_\{\\min\}is the smallest value ofkknot ruled out by[Proposition4\.2](https://arxiv.org/html/2607.21651#S4.Thmtheorem2)\.

###### Proof\.

For each\(i,j\)\(i,j\),mi​j=h\[ei,ej\]m\_\{ij\}=h\_\{\[e\_\{i\},e\_\{j\}\]\}\. Hence

∑\(i,j\)∈Ami​j=hZA,ZA≔∑\(i,j\)∈A\[ei,ej\],\\sum\_\{\(i,j\)\\in A\}m\_\{ij\}=h\_\{Z\_\{A\}\},\\qquad Z\_\{A\}\\coloneqq\\sum\_\{\(i,j\)\\in A\}\[e\_\{i\},e\_\{j\}\],wheredimZA≤k\\dim Z\_\{A\}\\leq k\. Therefore

ΦA,B=max⁡\{hZA,hZB\}=hconv⁡\(ZA∪ZB\)\.\\Phi\_\{A,B\}=\\max\\\{h\_\{Z\_\{A\}\},h\_\{Z\_\{B\}\}\\\}=h\_\{\\operatorname\{conv\}\(Z\_\{A\}\\cup Z\_\{B\}\)\}\.The convex hull of two polytopes of dimensions at mostkkhas dimension at most2​k\+12k\+1\. Expanding each symmetrized block into its summands, any solution of the exact system would therefore expressmaxn=hconv⁡\{e1,…,en\}\\max\\nolimits\_\{n\}=h\_\{\\operatorname\{conv\}\\\{e\_\{1\},\\ldots,e\_\{n\}\\\}\}, the support function of an\(n−1\)\(n\-1\)\-simplex, as a signed Minkowski combination of polytopes of dimension at most2​k\+12k\+1\. If2​k\+1<n−12k\+1<n\-1, this contradicts[Proposition4\.2](https://arxiv.org/html/2607.21651#S4.Thmtheorem2)\. Thus one must have2​k\+1≥n−12k\+1\\geq n\-1, equivalentlyk≥⌊\(n−1\)/2⌋k\\geq\\lfloor\(n\-1\)/2\\rfloor\. ∎

### 4\.3Computational results

See[1\.1](https://arxiv.org/html/2607.21651#S1.Thmtheorem1)

###### Proof\.

The casesn≤4n\\leq 4are immediate\. For each5≤n≤105\\leq n\\leq 10, let

k=⌊\(n−1\)/2⌋\.k=\\lfloor\(n\-1\)/2\\rfloor\.As described in[Section4\.1](https://arxiv.org/html/2607.21651#S4.SS1), we form the linear system indexed by all pairs

\(A,B\)∈ℳn,k×ℳn,k\.\(A,B\)\\in\\mathcal\{M\}\_\{n,k\}\\times\\mathcal\{M\}\_\{n,k\}\.We then apply the reduction from[Remark4\.1](https://arxiv.org/html/2607.21651#S4.Thmtheorem1)\. We solve this system exactly overℚ\\mathbb\{Q\}using an optimized implementation\. The resulting solution provides rational coefficientsλA,B\\lambda\_\{A,B\}such that all hinge coefficients vanish and the remaining linear part equalsxnx\_\{n\}on the sorted cone\. By[Proposition3\.1](https://arxiv.org/html/2607.21651#S3.Thmtheorem1), this implies equality on all ofℝn\\mathbb\{R\}^\{n\}as both functions are symmetric\.

Since each blockFA,BF\_\{A,B\}is constructed from pairwise maxima in the first hidden layer and one further maximum in the second hidden layer, this identity gives a two\-hidden\-layer ReLU representation\.

The resulting certificates can be verified using the conceptually simpler Python verifier provided in the accompanying GitHub repository\. This verifier performs all computations using exact rational arithmetic\. Although it is substantially slower than the optimized implementation used to obtain the certificates, it provides a transparent and directly reproducible check of the identities\. ∎

As a concrete example, taken=6n=6andk=2k=2\. Let

Then one certificate is

max⁡\{x1,…,x6\}=1720​FA1,B1\+1360​FA2,B2−11440​FA3,B3−1360​FA4,B4\.\\max\\\{x\_\{1\},\\ldots,x\_\{6\}\\\}=\\frac\{1\}\{720\}F\_\{A\_\{1\},B\_\{1\}\}\+\\frac\{1\}\{360\}F\_\{A\_\{2\},B\_\{2\}\}\-\\frac\{1\}\{1440\}F\_\{A\_\{3\},B\_\{3\}\}\-\\frac\{1\}\{360\}F\_\{A\_\{4\},B\_\{4\}\}\.HereFA,BF\_\{A,B\}is the symmetrized block defined above\.

The certificates forn=7,…,10n=7,\\ldots,10are much larger and are therefore not reproduced in the body of the paper\. They are provided with the accompanying online material111[https://github\.com/kilianar/max\-relu\-certificates](https://github.com/kilianar/max-relu-certificates)\.

##### Width of the construction\.

The constructions above are designed to make the search for two\-hidden\-layer representations computationally tractable, rather than to minimize network width\. Suppose that the certificate is supported onsstemplates\. Symmetrizing each template produces at mostn\!n\!labelled blocks, so the total numberQQof rank\-22maxout neurons satisfies

By sharing the required pairwise maxima, the rank\-22maxout realization has first\-layer width at most

\(n\+12\)=𝒪​\(n2\)\\binom\{n\+1\}\{2\}=\\mathcal\{O\}\(n^\{2\}\)and second\-layer width at mostQ≤s​n\!Q\\leq sn\!\. The construction can also be converted directly into a standard ReLU network without skip connections\. This yields first\-layer width at most

\(n2\)\+2​n=𝒪​\(n2\)\\binom\{n\}\{2\}\+2n=\\mathcal\{O\}\(n^\{2\}\)and second\-layer width at most3​Q≤3​s​n\!3Q\\leq 3sn\!\. Thus the direct symmetrized realization has quadratic width in the first hidden layer and, in the worst case, factorial width in the second\. We do not attempt to optimize this crude upper bound, which remains far above the quadratic lower bound for two\-hidden\-layer representations established in\[[undefk](https://arxiv.org/html/2607.21651#bib.bibx12)\]\.

## 5Recursive composition and depth bounds

There is a standard way to bootstrap any exact network representation ofmaxl\\max\\nolimits\_\{l\}without imposing assumptions on its internal structure\. Givenn\>ln\>linputs, partition them into groups of size at mostll, apply the network to all groups in parallel, and repeat the procedure on the resulting group maxima\. If the original network hasDDhidden layers, this tournament\-style construction, together with repeated\-coordinate padding for incomplete groups, representsmaxn\\max\\nolimits\_\{n\}withD​⌈logl⁡n⌉D\\left\\lceil\\log\_\{l\}n\\right\\rceilhidden layers\.

The representations constructed in this paper carry additional structure: their first hidden layer consists entirely of pairwise comparisons\. Exploiting this structure gives a more efficient bootstrap\. Each such comparison can be replaced by a copy of the original two\-hidden\-layer representation, increasing the number of hidden layers by only one while multiplying the input arity by⌊l/2⌋\\left\\lfloor l/2\\right\\rfloor\. The following theorem formalizes this substitution and its iteration\.

###### Theorem 5\.1\.

Assume thatmaxl\\max\\nolimits\_\{l\}has a two\-hidden\-layer representationℬl\\mathcal\{B\}\_\{l\}whose first hidden layer consists only of pairwise comparisonsmax⁡\{xi,xj\}\\max\\\{x\_\{i\},x\_\{j\}\\\}, and letr=⌊l/2⌋≥2r=\\left\\lfloor l/2\\right\\rfloor\\geq 2\. Then, for every integers≥0s\\geq 0, the functionmaxl​rs\\max\\nolimits\_\{lr^\{s\}\}has an exact representation with2\+s2\+shidden layers whose first hidden layer again consists only of pairwise comparisons\. Consequently, for everyn≥1n\\geq 1, the functionmaxn\\max\\nolimits\_\{n\}has an exact representation with at most

2\+max⁡\{0,⌈logr⁡nl⌉\}2\+\\max\\left\\\{0,\\left\\lceil\\log\_\{r\}\\frac\{n\}\{l\}\\right\\rceil\\right\\\}hidden layers\.

###### Proof\.

We construct the representations by induction onss, keeping the form of the first hidden layer as an invariant\. Fors=0s=0, the required representation isℬl\\mathcal\{B\}\_\{l\}\.

Suppose that the claim holds for somes≥0s\\geq 0, and setM=l​rsM=lr^\{s\}\. Partitionr​MrMinputs into disjoint blocksS1,…,SMS\_\{1\},\\ldots,S\_\{M\}, each of sizerr, and set

yp=maxi∈Sp⁡xi\.y\_\{p\}=\\max\_\{i\\in S\_\{p\}\}x\_\{i\}\.Evaluating the representation ofmaxM\\max\\nolimits\_\{M\}at\(y1,…,yM\)\(y\_\{1\},\\ldots,y\_\{M\}\)givesmaxp⁡yp=maxi⁡xi\\max\_\{p\}y\_\{p\}=\\max\_\{i\}x\_\{i\}\. In this evaluation, each first\-layer comparison becomes

max⁡\{yp,yq\}=maxi∈Sp∪Sq⁡xi,\\max\\\{y\_\{p\},y\_\{q\}\\\}=\\max\_\{i\\in S\_\{p\}\\cup S\_\{q\}\}x\_\{i\},a maximum of2​r≤l2r\\leq linputs\. Replace every such comparison by a copy ofℬl\\mathcal\{B\}\_\{l\}, using repeated\-coordinate padding when2​r<l2r<lorp=qp=q, and absorb the output affine maps of these copies into the affine map preceding the next hidden layer\. Thus the first hidden layer is replaced by two hidden layers, giving a representation ofmaxr​M=maxl​rs\+1\\max\\nolimits\_\{rM\}=\\max\\nolimits\_\{lr^\{s\+1\}\}with3\+s3\+shidden layers\. Its first hidden layer consists only of the pairwise comparisons from the copies ofℬl\\mathcal\{B\}\_\{l\}, so the invariant is preserved\. This is the substitution illustrated in[Figure1](https://arxiv.org/html/2607.21651#S5.F1)and completes the induction\.

Finally, givenn≥1n\\geq 1, take

s=max⁡\{0,⌈logr⁡nl⌉\}\.s=\\max\\left\\\{0,\\left\\lceil\\log\_\{r\}\\frac\{n\}\{l\}\\right\\rceil\\right\\\}\.Thenl​rs≥nlr^\{s\}\\geq n, so repeating one input coordinate as necessary turns the representation ofmaxl​rs\\max\\nolimits\_\{lr^\{s\}\}into one ofmaxn\\max\\nolimits\_\{n\}without changing its depth\. ∎

xix\_\{i\}xjx\_\{j\}xlx\_\{l\}x1x\_\{1\}max⁡\{x1,…,xl\}\\max\\\{x\_\{1\},\\dots,x\_\{l\}\\\}max⁡\{xi,xj\}\\max\\\{x\_\{i\},x\_\{j\}\\\}SiS\_\{i\}SjS\_\{j\}SlS\_\{l\}S1S\_\{1\}max​⋃i=1lSi\\max\\bigcup\_\{i=1\}^\{l\}S\_\{i\}max⁡\(Si∪Sj\)\\max\(S\_\{i\}\\cup S\_\{j\}\)

Figure 1:The first bootstrap step\. Starting from the two\-hidden\-layer networkℬl\\mathcal\{B\}\_\{l\}computingmaxl\\max\\nolimits\_\{l\}, replace each first\-layer comparisonmax⁡\{xi,xj\}\\max\\\{x\_\{i\},x\_\{j\}\\\}by a copy ofℬl\\mathcal\{B\}\_\{l\}computingmax⁡\(Si∪Sj\)\\max\(S\_\{i\}\\cup S\_\{j\}\), where\|Si\|=\|Sj\|=r=⌊l/2⌋\\lvert S\_\{i\}\\rvert=\\lvert S\_\{j\}\\rvert=r=\\lfloor l/2\\rfloor\(using repeated\-coordinate padding when2​r<l2r<l\)\. The resulting three\-hidden\-layer network computesmaxl​r=maxl​⌊l/2⌋\\max\\nolimits\_\{lr\}=\\max\\nolimits\_\{l\\lfloor l/2\\rfloor\}\.See[1\.2](https://arxiv.org/html/2607.21651#S1.Thmtheorem2)

###### Proof\.

Use the two\-hidden\-layer representation from[Theorem1\.1](https://arxiv.org/html/2607.21651#S1.Thmtheorem1)formax10\\max\\nolimits\_\{10\}and apply[Theorem5\.1](https://arxiv.org/html/2607.21651#S5.Thmtheorem1)withl=10l=10andr=5r=5\. ∎

See[1\.3](https://arxiv.org/html/2607.21651#S1.Thmtheorem3)

###### Proof\.

By \([1](https://arxiv.org/html/2607.21651#S1.E1)\), everyf∈CPWLdf\\in\\mathrm\{CPWL\}\_\{d\}is a signed linear combination of maxima ofd\+1d\+1affine forms\. Apply[Corollary1\.2](https://arxiv.org/html/2607.21651#S1.Thmtheorem2)to these maxima in parallel and implement their signed linear combination in the final affine layer\. This does not increase the number of hidden layers and gives the stated bound\. ∎

## Acknowledgments

The authors thank the members of the Neural Polytopes Zulip community and the participants of the Workshop on Polyhedral Geometry for Neural Networks222[https://neuralpolytopes\.gitlab\.io/workshop2026/](https://neuralpolytopes.gitlab.io/workshop2026/), held in Nuremberg in March 2026, for inspiring exchange\.

## References

- \[undef\]Raman Arora, Amitabh Basu, Poorya Mianjy and Anirbit Mukherjee“Understanding Deep Neural Networks with Rectified Linear Units”, 2018URL:[https://openreview\.net/forum?id=B1J\_rgWRW](https://openreview.net/forum?id=B1J_rgWRW)
- \[undefa\]Gennadiy Averkov, Christopher Hojny and Maximilian Merkert“On the Expressiveness of Rational ReLU Neural Networks With Bounded Depth”, 2025URL:[https://openreview\.net/forum?id=uREg3OHjLL](https://openreview.net/forum?id=uREg3OHjLL)
- \[undefb\]Egor Bakaev et al\.“Better Neural Network Expressivity: Subdividing the Simplex”In*Proceedings of the 58th Annual ACM Symposium on Theory of Computing*Salt Lake City UT USA: ACM, 2026, pp\. 500–507DOI:[10\.1145/3798129\.3800768](https://dx.doi.org/10.1145/3798129.3800768)
- \[undefc\]Ian Goodfellow et al\.“Maxout Networks”In*Proceedings of the 30th International Conference on Machine Learning*PMLR, 2013, pp\. 1319–1327URL:[https://proceedings\.mlr\.press/v28/goodfellow13\.html](https://proceedings.mlr.press/v28/goodfellow13.html)
- \[undefd\]Moritz Grillo, Christoph Hertrich and Georg Loho“Depth\-Bounds for Neural Networks via the Braid Arrangement”In*Advances in Neural Information Processing Systems*38Curran Associates, Inc\., 2025, pp\. 127800–127818URL:[https://papers\.neurips\.cc/paper\_files/paper/2025/hash/b98d5883da07b3b3b8afd3fd654dc57a\-Abstract\-Conference\.html](https://papers.neurips.cc/paper_files/paper/2025/hash/b98d5883da07b3b3b8afd3fd654dc57a-Abstract-Conference.html)
- \[undefe\]Christian Alexander Haase, Christoph Hertrich and Georg Loho“Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes”, 2023URL:[https://openreview\.net/forum?id=2mvALOAWaxY](https://openreview.net/forum?id=2mvALOAWaxY)
- \[undeff\]Christoph Hertrich, Amitabh Basu, Marco Di Summa and Martin Skutella“Towards Lower Bounds on the Depth of ReLU Neural Networks”In*SIAM Journal on Discrete Mathematics*37\.2, 2023, pp\. 997–1029DOI:[10\.1137/22M1489332](https://dx.doi.org/10.1137/22M1489332)
- \[undefg\]Christoph Koutschan, Bernhard Moser, Anton Ponomarchuk and Josef Schicho“Representing Piecewise Linear Functions by Functions with Small Arity”In*Applicable Algebra in Engineering, Communication and Computing*36\.4, 2025, pp\. 595–610DOI:[10\.1007/s00200\-023\-00627\-1](https://dx.doi.org/10.1007/s00200-023-00627-1)
- \[undefh\]Moshe Leshno, Vladimir Ya\. Lin, Allan Pinkus and Shimon Schocken“Multilayer Feedforward Networks with a Nonpolynomial Activation Function Can Approximate Any Function”In*Neural Networks*6\.6, 1993, pp\. 861–867DOI:[10\.1016/S0893\-6080\(05\)80131\-5](https://dx.doi.org/10.1016/S0893-6080(05)80131-5)
- \[undefi\]Brendan D\. McKay and Adolfo Piperno“Practical Graph Isomorphism, II”In*Journal of Symbolic Computation*60, 2014, pp\. 94–112DOI:[10\.1016/j\.jsc\.2013\.09\.003](https://dx.doi.org/10.1016/j.jsc.2013.09.003)
- \[undefj\]Anirbit Mukherjee and Amitabh Basu“Lower Bounds over Boolean Inputs for Deep Neural Networks with ReLU Gates”, 2017URL:[https://eccc\.weizmann\.ac\.il/report/2017/190](https://eccc.weizmann.ac.il/report/2017/190)
- \[undefk\]Itay Safran“A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theory”In*Proceedings of Thirty Ninth Conference on Learning Theory*336PMLR, 2026, pp\. 5721–5742URL:[https://proceedings\.mlr\.press/v336/safran26a\.html](https://proceedings.mlr.press/v336/safran26a.html)
- \[undefl\]Itay Safran, Daniel Reichman and Paul Valiant“How Many Neurons Does It Take to Approximate the Maximum?”In*Proceedings of the 2024 ACM\-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7\-10, 2024*SIAM, 2024, pp\. 3156–3183DOI:[10\.1137/1\.9781611977912\.113](https://dx.doi.org/10.1137/1.9781611977912.113)
- \[undefm\]S\. Wang and X\. Sun“Generalization of Hinging Hyperplanes”In*IEEE Transactions on Information Theory*51\.12, 2005, pp\. 4425–4431DOI:[10\.1109/TIT\.2005\.859246](https://dx.doi.org/10.1109/TIT.2005.859246)