  We prove that the set of functions representable by ReLU neural networks with
integer weights strictly increases with the network depth while allowing
arbitrary width. More precisely, we show that $\lceil\log_2(n)\rceil$ hidden
layers are indeed necessary to compute the maximum of $n$ numbers, matching
known upper bounds. Our results are based on the known duality between neural
networks and Newton polytopes via tropical geometry. The integrality assumption
implies that these Newton polytopes are lattice polytopes. Then, our depth
lower bounds follow from a parity argument on the normalized volume of faces of
such polytopes.
