[Theorem 1 in [1]}]
Any ReLU neural network with input dimension \(t\) , width \(w\) , and depth \(d\)  has at most \(O(w^{d \cdot t})\)  linear regions.


Let \(\Phi _{t,d,w}\)  consist of all ReLU neural networks with input dimension \(t\) , depth \(d\) , and width \(w\) . Suppose that we are in the setting of Theorem REF , except that the neural network is picked from \(\Phi _{t,d,w}\) .
Then the conclusion of the theorem holds as long as \(w^{d \cdot t}\le c F\)  for a small enough constant \(c\) . In particular, to simulate the WL test with neural networks from \(\Phi _{t,d,w}\) , we need \(dw=\Omega (dF^{\frac{1}{dt}})\)  ReLU units.

As an example, for shallow neural networks with low input dimension, say with \(d,t=O(1)\) , this lower bound becomes \(dw=F^{\Omega (1)}\) , i.e. polynomial rather than logarithmic in the size of the underlying field.
