On the Expressiveness of Rational ReLU Neural Networks With Bounded Depth
Authors: Gennadiy Averkov
Christopher Hojny
Maximilian Merkert
Venue: ICLR 2025 Spotlight (2025)
Keywords: expressive power
depth
exact representations
ReLU networks
mixed volumes
lattice polytopes
number theory
Primary area: learning theory
TL;DR: $\max \{0,x_1,\ldots,x_n\}$ requires depth $\Omega(\log n)$ to be exactly described with ReLUs and weights being decimal fractions.

Abstract: To confirm that the expressive power of ReLU neural networks grows with their depth, the function $F_n = \max (0,x_1,\ldots,x_n )$ has been considered in the literature.
  A conjecture by Hertrich, Basu, Di Summa, and Skutella [NeurIPS 2021] states that any ReLU network that exactly represents $F_n$ has at least $\lceil \log_2 (n+1) \rceil$ hidden layers.
  The conjecture has recently been confirmed for networks with integer weights by Haase, Hertrich, and Loho [ICLR 2023].

  We follow up on this line of research and show that, within ReLU networks whose weights are decimal fractions, $F_n$ can only be represented by networks with at least $\lceil \log_3 (n+1) \rceil$ hidden layers.
  Moreover, if all weights are $N$-ary fractions, then $F_n$ can only be represented by networks with at least $\Omega( \frac{\ln n}{\ln \ln N})$ layers.
  These results are a  partial confirmation of the above conjecture for rational ReLU networks, and provide the first non-constant lower bound on the depth of practically relevant ReLU networks.

Published as a conference paper at ICLR 2025
ON THE EXPRESSIVENESS OF RATIONAL RELU NEURAL NETWORKS WITH BOUNDED DEPTH
Gennadiy Averkov
Christopher Hojny TU Eindhoven
Maximilian Merkert
BTU Cotthus-Senftebergg
TU Braunschweig me warkertt@tu--bbuusscheee
averkovbb-tu.de
c. c.hojny@tue.. n1
ABSTRACT
To confirm that the expressive power of ReLU neural networks grows with their depth, the function F, = m # :.....; In } has been considered in the litera- ture. A conjecture by Hertrich, Basu, Di Summa, and Skutella [NeurIPS 2021] states that any ReLU network that exactly represents F, has at least [log2 (n + +1) hidden layers. The conjecture has recently been confirmed for networks with in- teger weights by Haase, Hertrich, and Loho [ICLR 2023].
We follow up on this line of research and show that, within ReLU networks whose weights are decimal fractions, F2 can only be represented by networks with least [log, (n + 1)1 hidden layers. Moreover, if all weights are N-ary fractions, then F2 can only be represented by networks with at least Q In N layers. These results are a partial confirmation of the above conjecture for rational ReLU net- works, and provide the first non-constant lower bound on the depth of practically relevant ReLU networks.
INTRODUCTION
important aspect of designing neural network architectures understand which functions can be exactly represented by specific architecture. Here, we say that a neural network, transforming input values into single output value, (exactly) represents function f: R + IR if, for every input E IR",, the neural network reports output (xx). Understanding the expressiveness of neural network architectures can help to, among others, derive algorithms (Arora et al., 2018 Khalife et al. 2024 Hertrich & Sering 2024) and complexity results (Goel et al. 2021|02211 Froese al. 2022 Bertschinger et al. 2023 Froese & Hertrich, 2023) for training networks.
One of the most popular classes of neural networks are feedforward neural networks with ReLU activation (Goodfellow et al., 2016). Their capabilities to approximate functions is well-studied and led to several so-called universal approximation theorems, e.g., (Cybenko) 1989 Homik 1991}. For example, from a result by [eshno et al.) (1993) it follows that any continuous function can be approximated arbitrarily well by ReLU networks with single hidden layer. In contrast to approximating functions, the understanding of which functions can be exactly represented by a neural network much less mature. A central result by Arora al. (2018) states that the class of functions that are exactly representable by ReLU networks is the class of continuous piecewise linear (CPWL) functions. In particular, they show that every CPWL. function with n inputs can be represented by ReLU network with [log2 (n- + 1)] hidden layers. It is an open question though for which functions this number of hidden layers also necessary.
An active research field is therefore to derive lower bounds on the number of required hidden layers. Arora et al. (2018) show that two hidden layers are necessary and sufficient to repre- sent max(0, 22,22) by ReLU network. However, there is single function which is known to require more than two hidden layers in an exact representation. In fact, Hertrich et al. (2021) formulate the following conjecture.
k 1 that can be represented by a ReLU network with l. hidden layers, but not with k: hidden layers.
Conjecture 1. For every integer k with 1
[logz(n
(n + 1)], there exists a function f: R" + R
Herrrich et al. (202I) also show that this conjecture is equivalent to the statement that any ReLU network representing max (0, -1,-.. -.. (24) requires k + hidden layers. That is, if the conjecture

---

Published as a conference paper at ICLR 2025
holds true, the lower bound of [loge + 1)] by Arora al. (2018) is tight. While Conjecture is open in general, has been confirmed for two subclasses of ReLU networks, namely networks all of whose weights only take integer values (Haase et al., (023) and, for 4, so-called H -conforming neural networks (Hertrich et al. 2021).
In this article, we follow this line of research by deriving non-constant lower bound the number of hidden layers in ReLU networks all of whose weights are N-ary fractions. Recall that a rational number is an N-ary fraction if it can be written as अे. for some integer and non-negative integer
Theorem 2. Let and N be positive integers, and let be a prime number that does not divide N. Every ReLU network with weights being N -arr fractions requires at least [logp(1 (n + 1)] hidden layers exactly represent the function
Corollary 3. Every ReLU network all of whose weights are decimal fractions requires at least [loga (n + 1)] hidden layers to exactly represent max(0, ,1,...,,Tr! Fn].
While Theorem 2 does not resolve Conjecture | because it makes no statement about general real weights, note that in most applications floating point arithmetic is used (TEEE) 2019). That is, in neural network architectures used in practice, one is actually restricted to weights being N-ary frac- tions. Moreover, when quantization, see, e.g.. (Gholami et al. 2022) is used make neural networks more efficient in terms of memory and speed, weights can become low-precision decimal numbers, cf., e.g., (Nagel et al. 2020p. Consequently, Theorem provides, to the best of our knowledge, the first non-constant lower bound on the depth of practically relevant ReLU networks.
2
Relying on Theorem 2 we also derive the following lower bound.
Theorem 4. There is constant C' 0 such that, for all integers n, 2 3, every ReLU network with weights being N ary fractions that represents max -i,...... .nn) has depth at least C-
In In N
Theorem 4 in particular, shows that there is constant-depth ReLU network that exactly repre- sents max (0, 21, .1,..., } if all weights are rational numbers all having a common denominator N.
In view of the integral networks considered by Haase et al. (2023), stress that our results do not simply follow by scaling integer weights to rationals, which has already been discussed in Haase let al. (2023 Sec. 1.3). We therefore extend the techniques by |Hasse et al. (2023) make use of number theory and polyhedral combinatorics to prove our results that cover standard number representations of rationals a computer.
Outline To prove our main results, Theorems and the rest of the paper is structured as follows. throughout the article,
First, we provide some basic definitions regarding neural networks that and we provide a brief overview of related literature. Section 2 then provides a short summary of our overall strategy to prove Theorems 2 concepts of polyhedral theory and volumes needed in our proof strategy are detailed in Section 2.1 whereas Section 222 recalls a characterization of functions representable by a ReLU neural network from the literature, which forms the basis of our proofs. In Section 3 we derive various properties of polytopes associated with functions representable by ReL.U neural network, which ultimately allows us to prove our main results in Section 3.3 The paper is concluded in Section E
and 4 as well as some basic notation. The different
Basic Notation for ReLU Networks To describe the neural networks considered in this article, we introduce some notation. We denote by E, N, and IR the sets of integer, positive integer, and real numbers, respectively. Moreover, E and R, denote the sets of non-negative integers and reals, respectively.
Let l E Z+. A feedforward neural network with rectified linear units (ReLU) (or simply ReLU network in the following) with k + layers can be described by k + affine transformations (1) Ro + I (k+11) R + g=++ It exactly represents function f: R + R if
and only r0g = n. n 1, and the alternating composition
((++1) o (()) o.... {(2) (1)
coincides with f. where, by slightly overloading notation, denotes the component wise application of the ReLU activation function a: R + R, (xx) = max (0, x to vectors in any dimension. For
each é E 11....,k + 1) and x E IR---1 let (() = (6) x + ((0) for some (( E R x and ((6) E : The entries of A are called weights and those of b(0) are called biases of the network. The network's depth is k 1, and the number of hidden layers is k.
2

---

Published as a conference paper at ICLR 2025
The set of all functions Rd + R that can be represented exactly by ReLU network of depth is + is denoted by R,, U, (At). Moreover, if R C E is ring, we denote by ReLU, (k) the set of all functions IR" + IR that can be represented exactly by a ReLU network of depth k + 1 all of whose weights are contained in R. Throughout this paper, we will mainly work with the rings Z, IR, the ring of N-ary fractions.
The set ReLU, (0) is the set of affine functions and ai...... On E R. It can be directly seen from the definition of ReLU networks that, for & E N, one has f E ReLU, (k) if and only if f(x) uo + #n max (1)))))(())))))))))))))()))))( +
2n) = b 21 + +... an with E R.
Um max Im (x)) holds for some m E N, uo IR, u1,..... Um R. and functions 91, 91..... Im E ReLU, 1).
Related Literature Regarding the expressiveness of ReLU networks, Hertrich et al. (2021) show that four layers needed exactly represent max (0, #1, -.,,...,3E. ...., if the network satisfies the tech- nical condition of being H --conforming, By restricting the weights of ReLU network to be integer, Haase et al. (023) prove that (e - 1) S (k) for every k < [log2(n + 1)7. In particular, max m 0, Lzz. & ReLUZ. (R+). If the activation function is changed from ReLU to x + 1 (z>0), Khalife et al. (2024) show that two hidden layers are both necessary and sufficient for all functions representable by such a network.
If one is only interested in approximating that max
2024 show can be approximated arbitrarily well by (2) of width n(n + 1) with respect to the Lg norm for continuous distributions. By increasing the depth of these networks, they also derive upper bounds on the required width in such an approximation. The results by Safrra et al. (2024) belong to the class of so-called universal approximation theorems, which describe the ability to approximate classes of functions by specific types of neural networks, see, e.g., (Cybenko, 1989; Hornik 1991; Barron 1993, Pinkus 1999; Kidger & Lyons, 2020). How- ever, Vardi & Shamir (2020) show that there are significant theoretical barriers for depth-separation results for polynomially sized ReLU,, (A) (k)-ntwtoorss for k 2 3, by establishing links to the separa- tion of threshold circuits as well as to so-called natural-proof barriers. When taking specific data into account, Lee et al. (2024) derive lower and upper bounds on both the depth and width of a neural network that correctly classifies a given data set. More general investigations of the relation between the width and depth of neural network are discussed, among others, by Arora al. (2018) : Eldan & Shamir 6)
function, Safran et
Hanin (2019): ; Raghu et al. (2017); Safran & Shamir 201
Telgarsky (0016)
PROOF STRATEGY AND THEORETICAL CONCEPTS
To prove Theorems 2 and we extend the ideas of Haase et al. 2023) We therefore provide a very concise summary of the arguments of Haase al. 2023). Afterwards, we briefly mention the main ingredients needed in our proofs, which are detailed in the following subsections.
A central ingredient for the results by Haase et al. (2023) is a polyhedral characterization of all fune- tions in ReLU, (k:), which has been derived by Hertrich (2022). This characterization links functions representable by a ReI.U network and so-called support functions of polytopes P C RD all of whose vertices belong to Z", so-called lattice polytopes. It turns out that the function max (0, 01,......... ..,) in Theorems 2 and can be expressed as the support function of particular lattice polytope P. S R". By using suitably scaled version Vol, of the classical Euclidean volume in R", one can achieve Vol,,()),
Σ for all lattice polytopes P C R.. Haase al. (0223) then show that, if the support function hp of a lattice polytope P S R" can be exactly represented by ReLU net- work with ie hidden layers, all faces of P of dimension at least 2 have an even normalized volume. For n 29, however, Vol,, (P.) is odd. Hence, its support function cannot be represented by ReLU network with & hidden layers.
We show that the arguments of Haase et al. (023)) can be adapted by replacing the divisor 2 with an arbitrary prime number p. Another crucial insight is that the theory of mixed volumes can be used to analyze the behavior of Vol,, (A + B) for the Minkowski sum A + B = {a + b: a E A, E B} operation is also involved in the polyhedral characterization of Hertrich| (2022). and it is also used by Haase et al.] (2023), who provide version of Theorem? f integer weights. They, however, do not directly use mixed volumes. A key observation used in our proofs, and obtained by direct application of mixed volumes, is that the
of lattice polytopes A, B C R". The Minkowski
3

---

Published as a conference paper at ICLR 2025
map associating to lattice polytope P the coset of Vol, (P) modulo prime number is additive when n is power of Combining these ingredients yields Theorems and
Some Basic Notation The standard basis vectors in I are denoted by ei....,, En. whereas 0 denotes the null vector in R". Throughout the article, all vectors a E In are column vectors, and denote the transposed vector by If x: is contained in the integer lattice Z", call it lattice point. For vectors x. y E R"", their scalar product is given by x y. For m E N, we will write [m]] for the set (I...., m.. The convex-hull operator denoted by conv, and the base-b logarithm by logg while the natural logarithm is denoted In.
The central function of this article is m1, which abbreviate by F...
2.1 BASIC PROPERTIES OF POLYTOPES AND LATTICE POLYTOPES
As outlined above, the main tools needed to prove Theorems 2 and are polyhedral theory and different concepts of volumes. This section summarizes the main concepts and properties that we need in argumentation in Section 3 For more background, we refer the reader to the monographs
BBeck& & Robins| 2020; Hug & Weil 2020 Schneider 2014).
Polyhedra, Lattice Polyhedra, and Their Normalized Volume convex hull conv (p1.... ........P... finitely many points PL...., R", introduce the family
A polytope P C R is the
P(S) = {conv(pt..... Pm)): m N, Pı....,,P Pm S}
of all non-empty polytopes with vertices in S S R". Thus, P(R") is the family of all polytopes in In and P(Z") is the family of all lattice polytopes R.. For {O,...,n., n.,, we also introduce the family
= (P dim(P)
of polytopes of dimension at most d, where the dimension of polytope P is defined as the dimen- sion of its affine hull, i.e., the smallest affine subspace of I² containing P. The Euclidean volume vol, on Ra is the n-dimensional Lebesgue measure, scaled so that vol, is equal to on the unit cube [0, 1]d. Note that weasure-theoretic subtleties play role in context since restrict the use of vol, to P.R"). The normalized volume Vol, in R" is the n--imennsional Lebesgue measure normalized that Vol,, is equal to on the standard simplex A, conv (0, e en). Clearly, Vol, = n!. vol, and Vol, takes non-negative integer values on lattice polytopes.
Support Functions
For polytope P conv(p1,.... ... Pm)) S IR" its support function is
hr(z) == max(# y: y:ye P}.
and it is well-known that hx(x)) max I.... P Consequently, max Fn from Theorems 2 and 4 is the support function An.
Mixed Volumes
For sets A, C R", we introduce the Minkowski sum
A+ B = ba+b: DE
and the multiplication
AA= 1A=
of A by a non-negative factor E R4. For an illustration of the Minkowski sum, we refer to Figure 2 Note that, if 5 E [R,", Zn) and A, B E P(S), then + B E PPS), too. If and are (lattice) polytopes, then A + B is also (lattice) polytope, and the support functions of A, B and A + B are related by A = A + hh.
If (G,+) +) is Abelian semi-group (i.e., set with an associative and commutative binary opera- tion), we call a map Φ: P(R") + G Minkowski additive if the Minkowski addition on P(R)) gets preserved by ő in the sense that Φ(A B) d(A) + ((B) holds for all A. B E P(R").
The following a classical result of Minkowski.
Theorem (see, e.g., (Schneider 2014 Ch. 5)). There exists a unique functional,, called the mixed volume,
V: P(RR)" R.
with the following properties valid for all Pı..... Pa, A, B P(R") and a, B R4:
4

---

Published as a conference paper at ICLR 2025
(a) V is invariant under permutations. i.e. V(P1..... Pw) ((P. "att)))...,,,())) Pain))oo every permu- tation a on [n].
(b) V is Minkowski linear in all input parameters, for all i E [n], it holds that
BB, BB,,,.e P.t1...., Pn) ((P P.-1, P4+1, Pr)
P P:-1, B, ,,t1,...,,P,
(c) V is equal to Voln on the diagonal, ie.,
A) (A).
We refer to Chapter 5 of the monograph by Schneider (2014) on the Brunn-Minkowski theory for more information on mixed volumes, where also an explicit formula for the mixed volume is pre- sented. Our definition of the mixed volume differs by factor of n! from the definition in inSchneiderr (2014) since we use the normalized volume Vol, rather than the Euclidean volume vol,, to fix V(P...... Pn) in the case P1 = in the context of algebraic geometry. It is known that, for this normalization, ((P....... ..... Pn)) E Z+ when Pt..... Pr are lattice polytopes; see, for example, (Maclagan & Sturmfels 2015 Ch. 4.6). From the defining properties one can immediately see that, for A, B E P(RR",, one has the analogue of the binomial formula, which we will prove in Appendix A.2 for the sake of completeness:
Pn-- Our way of introducing mixed volumes is customary
(A
n
V
A, B B)..., B).
(I)
Normalized Volume of Non-Full-Dimensional Polytopes So far, we have introduced the nor-
malized volume Vol,: : P(RR)) + R., i.e., if P E P(R") is not full-dimensional, then Vol,, (P)
0. We also associate with polytope / Pa(Z") of dimension at most d an appropriately normal- ized d-dimensional volume by extending the use of Vola: P(Zd) + 2+ to Vola: Pa(Z") + žạ. In the case dim P) < d, we define Vola(P) 0. If d = O, let Vola(P)
1. In the non-degenerate case d = dim P) E N, we fix Y to be the affine hull of P and consider a bijective affine map T: Rd Y satisfying T Y 2" For such choice T, we have T ((P) E P(Z*). It turns out that the d-dimensional volume of TP)(P) depends only on P and not on T so that we define Vola = (P))( Based on (Beck & Robins 2020 Corollary 3.17 and $5.4), there is the following intrinsic way of introducing (ol.(P). Let GTP) denote the number of lattice points in P. Then, for t E4, one has Vola(P) d! lime++00 + G(tP).
Remark 6. For every d-dimensional affine subspace Y C Th which is affinely spanned by d + lattice points, we can define Vola for every polytope P E P(Y), which not necessarily lattice polytope, by the same formula Vol, -oola(T- using an auxiliary map T: IRd + Y described above. Consequently, by replacing the dimension n with and the family of polytopes P(R")) with the family P(Y) in Minkowski's Theorem 5 we introduce the notion of mixed volumes for polytopes in P(Y). More specifically, we will make use of the mixed volumes of lattice polytopes in P(Y n )
Normalized Volume of the Affine Join
The following proposition, borrowed from Haase et al. (2023). addresses the divisibility properties of the convex hull of the union of lattice polytopes that lie in skew affine subspaces.
Proposition 7 (Haase et al. 2023 Lemma 6). Let A, B P(Z") be polytopes of dimensions E 24 and j 2.. respectively, such that P= conv(AU AUBB B) is of dimension i i+j+ ++1 1. Then Vol++ (P) is divisible by (ol, (B), In particular. if O, then a pyramid over B whose normalized volume (B)) is divisible by the normalized volume Vol,(B) of its base B.
For an example illustration, see Figure I Since P1 and Pa lie in skew affine subspaces, Proposition applies. Indeed, Vola(conv( U Pa)) = 12 is divisible by Volz = 6 (and Volo(P2) 1).
2.2 A POLYHEDRAL CRITERION FOR FUNCTIONS REPRESENTABLE WITH & HIDDEN LAYERS
Next to the geometric concepts that we discussed before. the second main building block of our proofs is the polyhedral characterization of ReLU,, by Hertrich| (2022). In the following, we introduce the necessary concepts and present Hertrich's characterization.
5

---

Published as a conference paper at ICLR 2025
P1 + P3
P
P2
conv P2)
I
2
Figure 1: Illustration of the convex hull of a
Illustration of the Minkowski sum of Figure 2:
polytope and point, relating Proposition 7
two polytopes, relating Example 12
Note that F2 is positively homogeneous, i.c., for all E R. and r IR", one has (r()x) = AF, For positively homogeneous functions f. Hertrihh et al. (021) show that f E ReLU,, if and only there exists a ReLU network depth ++ 1 all of whose blases are 0. This result easily generalizes to ReLU networks with weights being restricted to a ring R. We therefore denote by ReLUR (k) the set of all n-variate positively homogeneous functions representable by ReLU networks with hidden layers, weights in R, and all biases being 0. Morcover, ReLU = U ReLu, (k)..
To formulate the characterization by Hertrich (002),, we define the sum-union clasure for family of polytopes X' in R"
m
SU(X)= =
Σ
conv Conv(A, m E N, AG, B, X.i [m]]
The k-fold application of the operation gives the k-fold sum-union closure (2). In other words, SU"(X) X' and (X) SU(SU*-((X)) for l N. We will apply the k-fold sum-union closure to (S)) the set of all O-dimensional polytopes of the form {s}. with s e S.
The set SU*(2) forms semi-group with respect to Minkowski-addittinn since, directly from the representation of elements of SU* (X) as sums with arbitrarily many summands, one sees that (X') is closed under Minkowski addition.
Theorem 8 ((Hertrich) 2022 Thm. 3.35) for R = R and Haase et al. 2023 Thm. 8) for R Z).
Let R be I or 2. Then
ReLUR (k) = (hA hn: A, (PuR))))
Corollary 9. Let ls E Z4 and R be TR. or Z. Let P E P(R"). Then, the support function hp of P satisfies hp E (eLUU if and only if P + A = B for some A, B E Su* (Po(It))).
Proof. By Theorem we have that hp E RcLU (k) if and only if hp = hg h for some A, B E SU* R).)). The equation hp hB hA can be rewritten as h hp + h hp-A- as support functions are Minkowski additive. Furthermore, every polytope uniquely determined by its support function, see (Hug & Weil 2020), so hp+A hg is equivalent P A B.
The characterization of ReLU via SU*
well as the geometric concepts of vol- umes will allow us to prove Theorem 2 The core step of our proof is to show that F,, which is the support function of A,, is not contained RcLU2.0 (k) for small k. As we will see later, turns out to be useful to not work exclusively with full-dimensional polytopes in (Po(P)))) but with some their tower-dimensional faces. The next lemma provides the formal mechanism that we use, namely if P SU* (Po SU*(P (Po(2") and F' face of P. then fF & ReLU implies also hp & 2 (k)). We defer the lemma's proof to Appendix A.1.1
Lemma 10. Let & E Z4. Then, for all P E SU (Po(Z") and R", the face of P in direction u, given by
= f E P: TT = hr(u)}. belongs (Po(E)). In other words, SU (Po(Z)) (Z))) closed under taking non-empty faces.

---

Published as a conference paper at ICLR 2025
3 RESULTS AND PROOFS
The goal of this section is to prove Theorems 2 and 4 for the ring R of N-ary fractions. To this end, we will rescale Fn. by a suitable scalar E N such that the containment Fn E ReLU, is equivalent to x E (k). To show that XFn & (k) if k is too small, we use volume-based argument. More precisely, we show that, for lattice polytopes P _ R² whose support functions hp are contained in ReLU and suitably defined dimensions and prime numbers p. their volumes (P) are divisible by p. In contrast, (ol.(AA,.)) is not divisible by p, and thus, XF, & ReL.U, This strategy is inspired by the proof of Haase et al. (002)) for Fn & ReLU, a (k)), where related results are shown for the special case p = Our results, however, are more general and do not follow directly from their results.
To pursue this strategy, Sections 3.1 and 3.2 derive novel insights into volumes Vola(P) of lattice polytopes P whose support functions h are contained in (k). These insights are then used in Section 3.3 to prove Theorems and
3.1 DIVISIBILITY OF NORMALIZED VOLUMES BY A PRIME
To understand the divisibility of Vola by prime number mentioned above, we investigate cases in which Volg: Pz( - Z modulo a prime Minkowski additive. To make this precise, we introduce some notation.
and m E N we write a =m if a - b is divisible by m. This is called the congruence of a and b modulo m. The coset [=]m of = E E modulo m is the set of all integers congruent to & modulo m, and we denote the set of all such cosets by Zm The addition of cosets is defined by [a]m + [b] = b) for b Z. Endowing Σm with the addition operation + yields group of order m.
For a,
The following is an easy-to- to-povve but crucial observation. It states that when consider lattice polytopes in a d-dimenensional subspace Y S R" spanned by d lattice points, the volume Vold, taken modulo prime number p, is an additive functional when d is a power of p.
Proposition 11. Let d = p' < be power of prime number p. with E N. Let Pi..... P. Pa(Z") ) be such that Em Pa E Pz Then,
172
1
Vold Σ
Ps
(ola
Proof. Note that by the assumption Em= P. E Pu(Z")) all of the Pt's lie, up appropriate trans- lation, in d-dimensional vector subspace Y of Rdd, which is spanned by d lattice points. There is no loss of generality in assuming that P. S Y and, in view of Remark 6 we can use the mixed volume functional on d-tuples of polytopes from P(Y), which will give an integer value for poly- topes in P(Y n 2²). By an inductive argument, is sufficient to consider the case m = 2. It is well known that if d is power of p, the binomial coefficients (i).... (Q)....(__) in ① are divisible by p. see, e.g., Mihet (2010) Cor. 2.9). Thus, ① implies Vola(Pi + P2) =p Vola(Pi) + Vola(P) for P2 P(Y)22).
Example 12. Consider the polytope P1 + P2 E P2(Z²) for the rectangle P1 = [2.5] x [0,
(Z2 and the shifted standard simplex P2 = A2 {(0, 2) E P2(Z²) depicted in Figure In the picture. P1 + P2 is decomposed into regions in such way that the volume of the mixed area V(P,, , P2) can be read off. In view of the equality Vol, (P) + P2) V(P, + Pa, P, + Pa) V(P,, P1) + 2 (P1, , P2) + ((P2, P2) = Volz(Pi) + (V,,,, P2) + Vol2(P2), see (T. the total volume of the unshaded part of P1 + P2 must be exactly 2 ((P,, P2). For p = 2 we have Vol2(P, +
P2) = 15 2 6 6 = Volg + (o2)(P)). i.c., the parity of Volz(P1 + P2) is indeed that of Volg (P)) + Volg (P2). In contrast, divisibility by p 3 does not match, as 15 Ag 7. However, this does not contradict Proposition as d 2 is not power of = 3.
To derive divisibility properties of Vola(P) for lattice polytopes P with hp E ReLU we make use of the characterization of ReI.U via the SU-operator. Recall that one of the two defining
7

---

Published as a conference paper at ICLR 2025
operations of SU is conv(A B) for suitable polytopes A and B. A crucial observation is that for certain dimensions d, the divisibility of Vold(conv(A) B)) by prime number inherited from particular lower-dimensional faces of A and B.
Proposition 13. Let d =p' p' S be a power of a prime number p. with t E N. Moreover, let P = conv(A U B) E Pa(Z") for of A and B, then Volgt (P) Ep 0.
for A, B E Pa(z"). Volpt.)) for all p dimensioonll faces F
Note that this result also holds trivially if no face of dimension p' exists. We defer the proof of this result to Appendix A.112
3.2 MODULAR OBSTRUCTION ON VOLUME FOR REALIZABILITY WITH HIDDEN LAYERS
Equipped with the previously derived results, we have all ingredients together to prove the afore- mentioned results the divisibilityy of Vola(P) for lattice polytopes P with hp E (e)
Theorem 14. Let d = p' I be power of a prime number p. with E N. Let E [1] and P E SU* (Po(Z")). Then Volp= (F) =p for all p³ --ddmensionnl faces Fof P.
Proof. We argue by induction on k: If l: 1, then SU (2" consists of lattice zonotopes.
These are polytopes of the form P = S + ..... Sm. where S Sm are line segments joining Vol,(S.). by Proposition dim(S;).
S)) arriving at (Pl p O, since Vol,(S;) = 0 for all as d
pair of lattice points. One has Vola =p Vola
In the inductive step, assume k 2 2 and that the assertion has been verified for (Po Recall that every P E SU* (Po(Z") can be written as P = Σ conv for some polytopes A, B, E SU*- (Po(")) By the induction hypothesis, the p -dimensional normalized volumes of the f dimeensionl faces of A; and B; are divisible by p. Consequently, by Proposition 13 the p* oi-dimensional normalized volumes of the pi-dieensooa faces of conv (A,UB,) are divisible by p. Since SU* (Po()") is closed under taking faces (see Lemma 10p, Proposition applied to the p²- dimensional faces of P implies that the p" -ddmensioonll normalized volume of the p dimensioonl faces of P is divisible by
Let be lattice Theorem 15. Let d p² S be power of a prime number p, with (k) ks E [t], then Vola(P) is divisible by p.
polytope in PA)) hf
Proof. By Corollary 9 we have P A B for some A, B E SU*(P)(Z")). Then, by
Proposition 11 one has Vola(P PP + A) Ep (Pl Vola(A) =p Vola(B), which means that Vola(P) Ep (o) - Vola(B). By Theorem 14. both Vola(A) and (ola(B) are divisible by p. This shows that Vola(P) is divisible by p.
3.3 PROOFS OF MAIN RESULTS
We now turn to the proofs of Theorems and Let N E N and recall that rational number is an N-ary fraction is of the form 3. with z E Z and Z4. For N 2 and N 10, one has binary and decimal fractions, used in practice in floating point calculations. Clearly, every binary 5'= T0
fraction is also decimal fraction, because
In order to relate ReLU networks with fractional weights to ReLU networks with integer weights, simply clear denominators, made precise in the following lemma.
Lemma 16. Let f: IR" + R be exactly representable by ReLU network with k hidden layers and with rational weights all having M as common denominator. Then M (k).
Proof. We proceed by induction on For the base case tion (ZI,..., which the claim is immediately evident. Now let 2 and consider a k-layer network with rational weights with common denominator M representing f. Then f is of the form f(x) Up + u, max(O, O, 91 (x)} + ..... + un (0, 9m (z)) with m E N. where all ....... 9m are functions representable with l- hidden layers and all the weights, i.e., u1,..-p Uym and the ones used in
0. is an affine func- b aιιι + .... an with b E IR and Mai...., Ma, Z, from
8

---

Published as a conference paper at ICLR 2025
expressions for 91.... ... are rational numbers with M common denominator. Multiplying with M++1 we obtain
un + Mun max MM gi (a)) +... Mum max M 9m (x)); where the weights Muj,... M um are integer. By the induction hypothesis, for every [m]. we have M g; E ReLU 1), and hence M (k).
M f(x) wu
We now ready prove our main results.
Proof of Theorem 2 Let k [nx + 1)7 - 1, i.e., k is the unique non-negative integer satisfy- ing pt < &n+1 p If F2 was representable by ReLU network with hidden layers and N-ary fractions as weights, max(0, (1............... Tpz (T Tphh ......) would also be representable in this way. Thus, it suffices to consider the case n = p².
Recall that Fn is the support function ha, of the standard simplex. Suppose, for the sake of con- tradiction, that F can be represented by ReLU network with & hidden layers and weights be- ing N-ary fractions. Let & be large enough such that all weights are representable as No. for some = E Z. use Lemma 16 with M = N to clear denominators. That is, N*(++1) Fn representable by an anteger-weiggh ReLU network with l hidden layers. Since F, is homogeneous, we can assume that the network is homogeneous, too (Hertrich et al. 202T Proposition 2.3). Ob- serve that ( F,, is the support function of (d((+1) An. whose normalized volume satisfies Vol, (NT*((+++))))) A..) Ep ( Vol,, (A,,) N= -1 0. Hence, (=*(+++1) A,, is polytope in R8"" whose normalized volume is not divisible by p. but whose support function is represented by an feteger-weight ReLU network with hidden layers. This contradicts Theorem 15 Hence, F, is not representable by a ReLU network with & hidden layers and weights being N N-ary fractions. C
If N 10, we can use p = in Theorem 2 so Corollary 3 is an immediate consequence. The bound [logs (n + 1)1 in Corollary 3 is optimal up to constant factor, as F, is representable through a network with integral weights and [log2(2 + 1)] hidden layers (Arora et al. 2018). A major open question raised by Herttrchh et al. (2021) is whether this kind of result can be extended networks whose weights belong to a larger domain like the rational numbers or, ideally, the real numbers.
We also show that the expressive power of ReLU U networks with weights being decimal fractions grows gradually when the depth is increasing in the range from 1 to O(logn)
Corollary 17. For each that are described by ReLU networks with weights being decimal fractions, there are functions representable using 2k but not using k hidden layers.
N and each integer k E {l,..., [logs }. within n-variate functions
Proof. Function Fyt is not representable through hidden layers and weights being decimal frac- tions. Since 3* < 22h Ezg is representable with 2k hidden layers (and integer weights).
By making use of Theorem we now present the proof of Theorem
Proof of Theorem To make use of Theorem we need find prime number p that does not divide N. Let denote the i-th prime number, I.e,, Pi = 2, 3, 5 etc. Moreover, assume that the prime number decomposition of N consists of distinct primes, i.e., N ......... where . my E N and i < ... it. Choose the minimal prime that is not contained in {pi...... P., ). that is, the minimal prime not dividing N. Since Pt-1) has a prime not contained in .P......, J.
..p., -,, Ti
that p Pt+1-
To get more concrete upper bound on p. we make use of the prime number theorem (Hardy & Wright 2008 Ch. XXII). which is fundamental result in number theory. The theorem states that lim flms enough. We first stick to the case > T and then handle the border case < T.
Pi = 1. Consequently, I Pi+1 S 2t Int when 2 T, where T E is large
For In we have
(0 Inzdr- 1) + -
1+1
In Σ my Inps Piy
In Pig
2
In(j + +1) 2
1=1
==1
9

---

Published as a conference paper at ICLR 2025
for all t 2 T. Thus, In 2 1/2f In This implies In In 2 Int In In 2. Compare this to Inp I lm2 + Int + In So, we see that in N 2 C'Ipp with an absolute constant C > 0. invoke Theorem 2 for p. getting that the number of layers needed to represent F, with integer weights is at least log, ?t where log, n 2 Inn/mp p 2 C In Inn/tnin In..n. N. In the case / < T, we observe that S Pr and obtain the lower bound log, n = In mn/ppp 2 Inn/ppr. Since T is fixed, the factor In pr in the denominator is absolute constant.
Hence,
CONCLUSIONS
In summary, we proved that lower bound for the number of hidden layers needed to exactly repre- sent the function max ;i...., :nn with a ReLU network with weights being N-ary fractions is
[n 1)], where p is prime number that does not divide N. For p = 3, this covers the cases of binary fractions as well as decimal fractions, two of the most common practical settings. Moreover, it shows that the expressive power of ReLU networks grows for every N up to O n)). In the case of rational weights that are N-ary fractions for any fixed N, even allowing arbitrarily large denominators and arbitrary width does not facilitate exact representations of low constant depth.
Theorem 4 can be viewed as partial confirmation of Conjecture ! for rational weights, as the term In In N is growing extremely slowly in N. If one could replace In In N by a constant, the conjecture would be confirmed for rational weights, up to constant multiple. As already highlighted in Haase jtt al. (2023), confirmation of the conjecture would theoretically explain the significance of max- pooling in the context of ReLU networks: It seems that the expressive power of ReLU is not enough to model the maximum of a large number of input variables unless network architectures of high- enough depth are used. So, enhancing ReLU networks with max-pooling layers could be a way to reach higher expressive power with shallow networks.
Methodologically, algebraic invariants such the d-dimensional volume Volg modulo a prime number p when dl is a power of p- play a key role in showing lower bounds for the depth of neural networks. Our proof approach provides algebraic template for a general "separation strategy" to tackle problems on separation by depth. In the ambient Abelian group (G,-) of all possible functions that can be represented within given model, one has a nested sequence of subgroups Go S G1 C G2 C ..., with G3 consisting of functions representable by k layers. To demonstrate that an inclusion G2 C Gk+1 strict, one could look for an invariant that can distinguish G2 from Gk+11 this is group homomorphism & on G' that is zero on G3 but not zero on some f E Gk+1- Most likely, the invariant needs to be "global" in the sense that, if d(J) is computed from the NN representation of f, then it would accumulate the contribution of all the nodes of the NN in one single value and would not keep track of the number of the nodes and, by this, disregard the widths of the layers. In the concrete case we handled in this contribution, the group we choose is ReLu².0 whereas the invariant that employ has values in 2, and is based on the computation of the volume of lattice polytopes. In the original setting of Conjecture I one has to deal with the nested chain vector space G = ReLuR.0 which makes it natural to choose an invariant linear functional Φ: G - R. To make further progress, is therefore worthwhile continuing to investigate the connection between ReLU networks and discrete polyhedral geometry, algebra, and number theory in order to settle Conjecture I
of subspaces G₁ = ReLU (kk) of the the
in general.
Finally, we raise a question on the role of the field of real numbers in Conjecture I] Does the choice of subfield of R matter in terms of the expressiveness? More formally, we phrase
Question 18. Let S be subfield of R and k E N and let f: R - RR be function expressible via a ReLU network with weights in S. If is expressible by a ReLU network with k hidden layers and weights in R. is it also expressible by ReLU network with k hidden layers and weights in S? What is the answer for S = Q?
If, for S = Q, the answer to the above question positive, then the version of Conjecture I with rational weights is equivalent to the original conjecture with real weights, which might be helpful insight towards solving Conjecture []] If the answer negative, then the conjecture would have a subtle dependence the underlying field of weights.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We would like thank Sergey Grosman from Siemens (Konstanz, Germany) for his feedback on the practical role of quantization. The research of GA was partially supported by the DFG Project 539867386 "Extremal bodies with respect lattice functionals", which carried out within the DFG Priority Program 2458 "Combinatorial Synergies".
REFERENCES
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference on Learning Representations (ICLR), 2018.
A.R. Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions Information Theory, 39(3):33-994,, 1993. doi: 10.1109/18,200 2526500.
Matthias Beck and Sinai Robins. Computing the continuous discretely, 2020.
Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut, Tillmann Miltzow, and Simon We- ber. Training fully connected neural networks ]RRccmplete. In A. Oh, Nau- mann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 36222-36237. Curran Associates, Inc., 2023. http:pts//poooeeccossssseeee neuris cappaper files/paper/2023/ Ellee//siaas777fafff44455aaaa222 www.ppperrrceeeeeee.e.. pdf
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(303-314), 1989.
Ronen Fldan and Ohad Shamir. The power of depth for feedforward neural networks. In JMLR: Workshop and Conference Proceedings, volume 49, pp. 1-34, 2016.
Vincent Froese and Christoph Hertrich. Training neural networks is NP-hard in fixed dimension. In A. Oh, Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 44039 Curran Associates, Inc., 2023. URL. httpppp://rrocceeeeeggg...o wwtps//eee.pppps.cpppree...e.ee. pttp:/pppeerllleeeapp////333333 File F222B www.raapppperraeeeeeeeeeeeeeeeee
Vincent Froese, Christoph Hertrich, and Rolf Niedermeier. The computational complexity of ReLU network training parameterized by data dimensionality. Journal of Artificial Intelligence Re- search, 74:1775-1790 2022.
Amir Gholami, Sehoon Kim, Zhen Dong, Zhewei Yao, Michael W. Mahoney, and Kurt Keutzer. Low-Power Computer Vision: Improving the Efficiency of Artificial Intelligence, chapter Survey of Quantization Methods for Efficient Neural Network Inference. Chapman and Hall/CRC, edition, 2022.
Surbhi Goel, Adam R. Klivans, Pasin Manurangsi, and Daniel Reichman. Tight hardness results for training depth-2 ReL.U networks. In /2th Innovations in Theoretical Computer Science Confer- ence (IT'S), 2021.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. http:
//www. //ww.deeplearnnnngooo... org
Christian Alexander Haase, Christoph Hertrich, and Georg Loho. Lower bounds on the depth of integral ReLU neural networks via lattice polytopes. In International Conference on Learning Representations (ICLR), 2023.
Boris Hanin. Universal function approximation by deep neural nets with bounded width and ReLU activations. Mathematics, 7(10):992, 2019.
Godfrey Harold Hardy and Edward Maitland Wright. An Introduction To The Theory Of Num-
bers. Oxford University Press, 6th edition, 07 2008. ISBN 9780199219858. doi: 10.1093/oso 9780199219858 001.1001. URL [RL|attps: //ooi. org/ /ttt://///ool.oorr//00.////////0 0TT.:////00000001922091299929999
001 0001

---

Published as a conference paper at ICLR 2025
Christoph Hertrich. Facets of Neural Network Complexity. PhD thesis, Technische Universität Berlin, Berlin, 2022. URLhttp:: ax..ao. wtt..a.....oo/...11//////oooooo.
Christoph Hertrich and Leon Sering. ReLU neural networks of polynomial size for exact maximum flow computation. Mathematical Programming, 2024. doi: 10.10077110007--220000--
Christoph Hertrich, Amitabh Basu, Marco Di Summa, and Martin Skutella. Towards lower bounds on the depth of ReLU neural networks. Advances Neural Information Processing Systems, 34: 3336-3348, 2021.
Kurt Horni.. Approximation capabilities of multilayer feedforward networks. Neural Net- works, 4(2):251-22) 12111 1991. ISSN 0893-6080. doi: https//dbb.orr///00011//999995.9
90009-T. URL https::/wwwet www.::ecieccciiccccm htt.://eeeerrr...ocococcceee///e comm//cieence//rtticlee///
089360909 90009T
Daniel Hug and Wolfgang Weil. Lectures on Convex Geometry. Springer Cham, 2020.
IEEE. IEEE standard for floating- point arithmetic. IEEE Std 754-2019 (Revision of IEEE 754- 2008), pp. 1-84, 2019. doi: 10. D.LUU//EEESTD2221995722222 URL https: /ccii org/
10. 11.11199/I0 SEIP/EEEESTDD... 2012E.TD......... 2019. 8766229
Sammy Khalife, Hongyu Cheng, and Amitabh Basu. Neural networks with linear threshold tivations: structure and algorithms. Mathematical Programming, 206:333-356, 2024. doi: 10.10077/10100-022--00066
Patrick Kidger and Terry Lyons. Universal Approximation with Deep Narrow Networks. In Jacob Abernethy and Shivani Agarwal (eds.), Proceedings of Thirty Third Conference on Learning The- ory, volume 125 of Proceedings of Machine Learning Research, pp. 2306-2327. PMLR, 09-12 12 Jul 2020. httpsts:::/ http::::/pppcceedinng.. mir. press http///12//kiice httpp/////////iier2a.a...o html
Carl W. Lee and Francisco Santos. Handbook of Discrete and Computational Geometry, chapter 16: Subdivisions and Triangulations of Polytopes. Discrete Mathematics and Its Applications. CRC Press, Boca Raton, FL, 3rd edition, 2017.
Sangmin Lee, Abbas Mammadov, and Jong Chul Ye. Defining neural network architecture through polytope structures of datasets. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 26789-26836. PMLR, 21-27 Jul 2024. URL attps: :estps://pree http::://proceeeingg. .ml...nn............m........... mmr. press/ v 2eee35511ee24.hhe
Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken. Multilayer feed- forward networks with nonpolynomial activation function can approximate any func- tion. Neural Networks, 6(6):861 867, 1993. ISSN 0893-6080. doi: https://do.orr/10
1016/50889-6000005)880113311 URL https: //ww scl.sciieen www.:/innnweee...ccooooooo aaticclee/11/8883300000000
Diane Maclagan and Bernd Sturmfels. Introduction to Tropical Geometry, volume 161 of Graduate Studies in Mathematics. American Mathematical Society, 2015.
Dorel Mihet.
Legendre's and Kummer's theorems again. Resonance, 15(12):1111 doi: 10.10077112245-00000222-4
1121, 2010.
URL bttps::/aci.org//// 1007/
s12045- 010-0123---00---
Markus Nagel, Rana Ali Amjad, Mart Van Baalen, Christos Louizos, and Tijmen Blankevoort. Up or down? adaptive rounding for post-training quantization. In Proceedings of the 37th International Conference on Machine Learning, (CML'20. JMLR.org, 2020.
Allan Pinkus. Approximation theory of the MLP model in neural networks. Acta Numerica, 8: 143-195, 1999. doi: 10.1011 01.17770006222290029999
12

---

Published as a conference paper at ICLR 2025
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the expressive power of deep neural networks. Doina Precup and Yee Whye Teh (eds.). Pro- ceedings the 34th International Conference on Machine Learning, volume 70 of Proceed- ings of Machine Learning Research, pp. 2847-2854. PMLR, 06-11 Aug 2017. URL https: //proceedi ngs. ml wtt.:/peea////0//apppe/
htmml
Itay Safran and Ohad Shamir. Depth- width tradeoffs in approximating natural functions with neural networks. In Proceedings the 34th International Conference on Machine Learning, Sydney, Australia, PMLR 70, pp. 2979-2987, 2017.
Itay Safran, Daniel Reichman, and Paul Valiant. How many neurons does it take approximate the maximum? Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp- 3156-11611183 3183, 2024. doi: 1137/1 01117//...77111117777711.
URL https:/:: /tttps://epp /ppbbs.
S siam. wttp:///////.ooooo/o/
Rolf Schneider. Convex bodies: the press, 2014.
theory, volume 151. Cambridge university
Matus Telgarsky. Benefits of depth in neural networks. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir (eds.), 29th Annual Conference on Learning Theory, volume 49 of Proceed- ings of Machine Learning Research, pp. 1517-1539, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR. URL lttpp::/ mwr...m.....p... telgarskyle 6.hml
Gal Vardi and Ohad Shamir. Neural networks with small weights and In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20 Red Hook, NY, USA, 2020, Curran Associates Inc. ISBN 9781713829546.
barriers.
A APPENDIX
A.1 DEFERRED PROOFS
In this appendix, we provide the proofs missing in the main part of the article. For convenience of reading, restate the corresponding statements.
A.1.1 PROOF OF LEMMA
10
This appendix provides the missing proof of the following lemma.
Lemma 10. Let l E E4. Then, for all P SU (Po(Z")) and u E R", the face of P in direction u, given by
pd == fxr E P: u hr(u)).
belongs SU* (Po(E")) In other words, (Po(Po(Z) closed under taking non-empty faces.
Proof. Throughout the proof, let X' = Poo (Z"). The proof is by induction on k. For k: O, we have SU (x') X. Since every polytope in Po(2)) consists of a single point every non-empty face of such a polytope also just consists of s, and is therefore contained in (2(2)) Thus, the claim holds.
Now let A 2 and assume the assertion holds for - 1. Furthermore, let u E R" and P E SU* (x') with = Σm conv(A; U B₂) for some m E N, A,, B, E S (2), E [m]. By definition and Minkowski additivity of the support function, we have pu = (E conv (Anv(A, U B.)) Em (conv( (A; U B.)) Moreover, for each E [m], conv(A, U B,) is equal to AY, By, or CAnv(Ap U B depending on whether (u, > hB, hn,(u). (u), (1,(() < has (u), (u, = hb, (u),
respectively. In any case, we obtain representation of pa that shows its membership in SU* (2)), since A,, B; SUk-1(A)) for all E [m] by the induction hypothesis.
13

---

Published as a conference paper at ICLR 2025
A.1.2 PROOF OF PROPOSITION 13
The goal of this section to prove the following statement.
Proposition 13. Let d = pt I be a power of a prime number p. with t E N. Moreover, let P conv(A U B) E PZ(Z") ) )or A, B E P.(Z"). (F) for all p- dimensional faces F of A and B, then Vol,a (P) =p 0.
To prove this result, we need two auxiliary results that we provide next.
Proposition 19. Let m, 8, E N and < d S n. P E Pa(2") such that Vol,(F) =m for all s-dimensional faces F of P. then (P) =m 0.
1: Once the case d is settled, it follows that the divisibility of (F); by m for i-dimensional faces F of P' implies divisibility of Vol++1 by m for all 1-dimmnsiooa faces G of P. Hence, iterating from i to i = d 1, we obtain the desired assertion. So, assume d = 8 +.
Proof. Note that
restrict our attention to the case d
Let be d-dimensional lattice polytope with facets having a normalized (d didmeensio vol- ume divisible by m. We pick a vertex a of P and subdivide P into the union of the non-overiapping pyramids of the form conv {a} U F). where F' is facet of By Proposition 7 the normalized d- dimensional volume of conv(fa) U F) ) is divisible by Volg-1 (F). Since by assumption Vola-1(F) divisible by m, we conclude that also (Pla(P) is divisible by m, because Vola is additive as based on Lebesgue measure.
The second result analyzes the structure of conv U B) in terms of particular subdivision. Given a polytope E P(R")) of dimension d, subdivision of P is finite collection C P(R") such that (i) P = UCec C; (ii) for each C E C, the polytope C' has dimension d; (iii) for any two distinct C, C" E C. the polytope C' e C' is a proper face of both C and C". The elements C E C are called the cells of subdivision C, (Lee & Santos 2017).
Proposition 20 (Haase et al. [023] Prop. 10). For two polytopes A, E P(R"), there exists subdivision of (AUB) such that each full-dimessiiond cell is of the form (FU), where F and G are faces of and B, respectively, such that dim + dim(G) + d.
The term "full-dimensionaa" in Proposition 20 well in the original formulation of Haase et al. [003 Prop. 10) refers to faces that have the same dimension as conv (A B), while its authors make no assumption whether that dimension is equal to n (but Haase et al. (2023) note in their proof that such an assumption would be without loss of generality).
We now able to prove Proposition 13
Proof of Proposition 13 Let P = conv(A B). We apply Proposition 20 for obtaining subdivi- sion of P into d-dimensional polytopes Pi = conv(E, U G.,....,, Pm. conv(Fm. U Umm), where for each E [m]) F, and G, are faces of A and B, respectively, and dim (F.) + diimdiGa (G.) +1+ d. That is, P is the union of polytopes whose relative interiors are disjoint. Consequently, Vola(P) =
(ol, +....+. (..)..... Vola(P..) It therefore suffices show that Vola(P.) =p 0 for every such polytope
P. with s E [m²]
For given s [m]] and faces F, and G2 of A and B, respectively, denote their dimensions i resp. j. Since i + = the case, would have i + 2(p'-1 1) p² 1, which is contradiction). By symmetry reasons, we assume without loss of generality that i 2 p² 1, Then, by Proposition 19 Vol,(F.) is divisible by p. Consequently, by Proposition 7 the normalized volume of conv (P. G.) is also divisible by
= p² 1, the dimension of F, or G, is at least p' (if this was not
A.2 PROOF OF BINOMIAL FORMULA FOR MIXED VOLUMES
The symmetry and multilinearity of the mixed-volume functional makes computations with it similar in nature calculations with n-term product. Say, the identity (x+y)² = 2² +2ryty² over reals corresponds to the identity (Al B) V(A + B, A B) = ()A.A)+2VE B) 2 ((4, B)+ Volz B) for planar polytopes A, B and the way of deriving the latter identity
14

---

Published as a conference paper at ICLR 2025
is completely analogous to deriving the identity for (x y)² by expanding brackets. Very much in
the same way, the binomial identity (x + y)" > === (i) x'y" corresponds to the identity (T) Here a formal proof:
We use the notation Po B and P1 = A. Then
Vol. + Pt) = + Pi...
Po Pi)
by Property (c) in Theorem 5 Using Property (b) in Theorem 5 for each of the n inputs of the
mixed-volume functional, we obtain
Vol, Pi)
E (1E().1)
Σ V(P., ... ,P.). (,((1,1)
where the right-had side is with 2" terms. However, many of the terms are actually repeated, because V(P,,.... P...) does not depend on the order the polytopes in the input: this mixed volume contains +.... in copies of P1 and (i1 +.... in) copies of Po. Hence,
V(P...... P...) = V(Po...,,PP Po. Pi.
(. 4
In order to convert our 2t sum into an (n+1)) sum, for each choice of = i .... +....... in E {0, ......... nt), we can determine the number of choices of ii,..., in [0,1} that satisfy
+ ... + in. This corresponds to choosing an i-element subset (t E [n]: i 1} in the n-element set (1, (I. That is, the number of such choices is the binomial coefficient (?). Hence, our representation with 2 terms amounts
Vol, (Po + P1) =
Σ 1=0
12 V Po.
Po. P P1).
n-i
15


Reviews:
[{"review_id": "vXgklAZxeV", "reviewer": "Reviewer_eDpF", "summary": "The authors present new results about the impact of depth on the capacity of ReLU Neural Networks to exactly compute $F= x \\mapsto \\max \\{ 0, x_1, \\cdots, x_n \\} $. More precisely, they investigate possible lower-bounds on the depth needed to compute $F$. This problem has direct consequences on the capacity of such Neural Networks to compute all piecewise-linear functions $\\mathbb{R}^{n} \\rightarrow \\mathbb{R}$. They show that if the weights of the ReLU network are N-ary fractions (i.e. fractions of the form $ \\frac{z}{N^{t}}$ where $z, N > 0, t \\geq 0$ are integers), then there is a general logarithmic lower-bound.", "questions": "Do the authors believe that an entirely new approach should be adopted to obtain results in the rational case?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper makes progress towards a complete answer to an open and (believed to be) difficult conjecture.\n \n- The class of ReLU neural networks considered are practically relevant.\n\n- The technical parts are well-presented for readers not fluent in discrete geometry.", "weaknesses": "- There is no major weakness to this paper in my opinion. The minor weakness is that the paper is heavily inspired by a previous paper in the approach and only limited technical ingredients are added.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iY9W5IJeOp", "reviewer": "Reviewer_1gfZ", "summary": "In this paper, the authors identified the lower bound of the depth to exactly represent the function $F_n = \\max (0,x_1,\\dots,x_n) $. In particular, they focused on the rational neural networks whose weights are $N$-ary fractions, and showed that the depth $\\lceil \\log_p(n+1) \\rceil$ and $\\Omega(\\frac{\\ln n }{\\ln\\ln N})$ is necessary. These main results partially answer the conjecture by Hertrich et al. (2021).", "questions": "**Width and complexity**\n\nAs the depth, understanding the expressive power with respect to the width and # of parameters is also important. How do you expect the effect of the width or the number of parameters in your context? Suppose that $f$ can be represented by a ReLU network $g$ with $k$ hidden layers, but not with $k-1$ hidden layers. How do you expect the width and # of parameters of $g$? Can we use similar approaches (modulo, mixed-volume, etc.)?\n\n\n**ReLU to other piecewise linear activation**\n\nOnce we shift our attention from ReLU to other piecewise linear activation (e.g. Leaky-ReLU), can we get similar results? Unlike ReLU, conjecture 1 may not be equivalent to the statement that any ReLU network representing $\\max \\\\{ 0,x_1,...,x_n \\\\}$ requires $\\log_2(n)+1$ hidden layers.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Extend previous works**\n\nIndependent of studying whether NNs can approximate a class of functions, identifying the class of functions that can be exactly implemented by NNs is one of the fundamental studies for the expressive power of NNs. The authors consider networks whose weights are $N$-ary fractions which represent floating point/fixed point arithmetic networks. Importantly, they exploit mixed-volume theory to prove the statement, which is not directly used in the previous works.\nOverall, the results certainly help us have a better understanding of deep neural networks in view of a theoretical and practical way.\n\n**Clarity and Quality**\n\nwell-written and clearly structured paper. The problem has been motivated nicely in the introduction. The related work section is rigorous and clearly details the current results for this problem.", "weaknesses": "**Partially answer conjecture 1 by Hertrich et al. (2021)**\n\nNonetheless, it is not a critical issue. As mentioned earlier, I think considering weights with $N$-ary fractions is more reasonable compared to real weights, since computers use floating/fixed point arithmetic. Thus, to highlight the novelty, it would be better to pose another conjecture, not focusing on conjecture 1, about a ReLU network using $N$-ary fractions weights.\n\n**Proof technique**\n\nThough the authors apply mixed-volume theory, most of the key lemma are based on previous works [Hertrich et al. (2021); Haase et al. (2023)].\nCompared to the previous works, the proof strategy seems similar. Thus, I think this makes the contribution of this paper incremental. To highlight the novelty, it would be better to clarify why mixed-volume theory is necessary to extend the argument of Haase et al. (2023) (divisor 2 -> prime $p$).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RSdVUBHjBt", "reviewer": "Reviewer_oyU3", "summary": "The authors provide new lower bounds on the number of layers that a ReLU neural network needs in order to represent the function $\\max$ {$0, x_1, \\ldots, x_n$}.\nThe main result is that if all weights are $N$-ary fractions and $p$ is a prime number that does not divide $N$, then at least $\\lceil \\log_p(n+1) \\rceil$ layers are needed to represent the function $\\max$ {$0, x_1, \\ldots, x_n$}.\nThe proof relies on a duality between continuous piecewise linear functions and polytopes, as well as on the additivity of the mapping from lattice polytopes to their normalized volume modulo a prime number $p$. The authors extend results from Haase et al., who (implicitly) showed a lower bound of $\\lceil \\log_2(n+1) \\rceil$ if the weights are $N$-ary fractions for odd $N$.\nAdditionally, for a given $N$, they provide an upper bound on a prime number $p$ that does not divide $N$, resulting in a non-constant lower bound for representing $\\max$ {$0, x_1, \\ldots, x_n$} with a rational neural network using $N$-ary weights.", "questions": "- Do you see any potential to bound the denominator of the weights needed to represent the max function with fewer than logarithmic layers (and rational weights) so that your results would yield a non-constant lower bound?\n\nMinor issues: \n- On Line 151, should it be \"faces of dimension at least $2^k$ for $k$ hidden layers\"? \n- The sentence in the conclusion, \"In the case of rational weights, even allowing arbitrarily large denominators for any given $N$ and arbitrary width does not facilitate exact representations of low constant depth,\" might be slightly misleading. Perhaps consider phrasing it as \"In the case of rational weights that are $N$-ary fractions...\"", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper should be accepted because it strengthens results in an important research area. Additionally, the paper is very well-written. \n- The expressiveness of ReLU neural networks is an active research field, and understanding the functions that are exactly representable with a specific architecture is a fundamental question. Finding lower bounds on the number of layers needed to compute all piecewise linear functions has remained an open problem for some years. \n-  The lower bound of $\\lceil \\log_3(n+1) \\rceil$ layers to represent the function $\\max$ {$0, x_1, \\ldots, x_n$} for neural networks with decimal or binary fractions is a notable result. It contributes further to resolving the conjecture of a non-constant lower bound on the number of layers needed to represent all piecewise linear functions. \n-  The paper is well-organized, self-contained, and accessible. It effectively balances providing intuition with rigorous proofs.", "weaknesses": "While the results provide a meaningful strengthening, the methodology may appear somewhat incremental. The approach builds on Haase et al.'s method for networks with integer weights. Proposition 11 (the additivity of the mapping from a lattice polytope to its normalized volume modulo a prime number) is the main new technical component, derived from mixed volumes, which generalizes the parity of the normalized volume of certain polytopes associated with neural networks with integer weights to the divisibility of the normalized volume by a prime number.\n\nThat said, I still believe the paper is a valuable contribution, potentially opening the door to find other (algebraic) invariants for resolving (other special cases of) the conjecture. Moreover, the authors did an excellent job of bringing together these elements in a self-contained manner.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LVJJs5eZkR", "reviewer": "Reviewer_ojAS", "summary": "The main result in the paper is a lower bound on the depth of the network for exactly representing the max function over the coordinates of the inputs. Namely, a ReLU feed-forward network with N-ary weights requires depth log_p(n+1) to represent the max over n coordinates, where p doesn’t divide N. Another result provides depth lower bound which relies on loglog(N).", "questions": "1) Is there a more high-level intuition on why divisibility by p means that ReLU networks of a certain depth cannot approximate the target? The lower bounds on approximation usually use some measure of complexity that grows gradually with the depth, e.g. the number of linear regions that can be represented by the network. Is there a similar measure here?\n\n2) Why the width doesn’t play any role in exact representation, contrary to approximation?\n\n3) How do residual connections affect the result? Does the characterization of Theorem 8 still hold?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1) The paper makes an important step toward solving the conjecture from Hertrich et al (2021), improving the previous depth lower bound which was restricted to networks with integer weights to networks with N-ary weights.\n\n2) The presentation of the paper is clear and easy to follow.\n\n3) I think the proof methods used in this paper are pretty unique in the literature of machine learning and may be used beyond the scope of this paper (although this could also be said to Haase et al. 2023).", "weaknesses": "I think this is a strong submission, and the weaknesses I write here are somewhat minor.\n\n1) There are some definitions missing in the paper that are not common in the machine learning community, and it would be helpful to define everything formally. For example, semigroup (line 206). How is the dimension of a polytope defined (line 182)? \n\n2) Although the paper is fairly self-contained, there are parts that are left without proof. Some examples: Lines 230-231. Why is SU closed under Minkowski addition? I think these are “easy” exercises but for a machine learning paper, it would be better to show it directly.\n\n3) I suggest also citing https://arxiv.org/pdf/2006.00625, which proves that if a similar depth separation result for depth k>= 5 can be proven for approximation (rather than exact representation), then it would solve a longstanding open question in TCS about the separation of threshold circuits. In other words, it is highly unlikely that a similar result can be proven for approximation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jVKccRszXd", "reviewer": "Reviewer_eki2", "summary": "This paper proves two lower bounds for the depth of a ReLU network with rational weights that exactly represents the maximum coordinate function.", "questions": "1. Theorem 2 and 4 seem to have basically the same assumptions and yield two lower bounds. In which circumstances, should I care about one over the other?\n\n2. Can you show or discuss the implications of Theorem 2 and 4 in the flavor of Conjecture 1 rather than approximation $F_n$?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "1. This work extends the previous work by [Hasse et al., 2023]. It proves some statements for rational weighted neural networks, which is new to the literature. It seems to make a step towards understanding the exact functions representable by neural networks.\n\n2. The presentation of the work is very clear. The results are very well-connected to the existing literature, their implications are made explicit, and the intuitions of the proofs are stated clearly.", "weaknesses": "1. The main weakness of this paper is the significance of the result. These analyses are interesting intellectual challenges, but I do not see too many practical implications. Studying the exact representations of neural networks is even a step back from the universal approximation results. This makes the results very brittle. For instance, I am not convinced by the argument that all weights in a computer are ultimately rational: while this is true, in a computer, one can neither represent the $F_n$ function studied in this paper exactly. Moreover, one can use a p-ary number to approximate any q-ary number arbitrarily well, which makes the results purely algebraic.\n\n2. While the paper definitely contains interesting ideas, it seems to be fairly incremental and relies heavily on the mechanisms developed in [Hasse et al., 2023]. I don't see an exciting analysis tool that is invented in this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)