One-dimensional and multidimensional ReLU region lower bounds

Compose the width-$n_{\mathrm{\ell }}$ blocks from [F1]. Each existing interval is divided into $n_{\mathrm{\ell }+1}+1$ intervals, each mapped onto $[0,1]$, so after all $L$ layers the number is ${\prod }_{\mathrm{\ell }=1}^L(n_{\mathrm{\ell }}+1)$.

For $n_0=1$, each index $j_{\mathrm{\ell }}$ in [F2]'s upper sum is $0$ or $1$: the previous factors leave $n_i-j_i\ge 2$ for every $n_i\ge 3$. Thus the sum factors as ${\prod }_{\mathrm{\ell }=1}^L(1+n_{\mathrm{\ell }})$, so the count in step 1.1 is exact. For the multidimensional construction, in each of the first $L-1$ layers allocate $q_{\mathrm{\ell }}=\lfloor n_{\mathrm{\ell }}\mathrm{/}{n}_0\rfloor \ge 3$ units to each coordinate and implement an independent width-$q_{\mathrm{\ell }}$ fold on that coordinate; set any remaining units constantly inactive. Each prior box is thereby subdivided into $(q_{\mathrm{\ell }}+1{)}^{n_0}$ boxes, each mapped bijectively onto $[0,1{]}^{n_0}$.

Take an arrangement of $n_L$ hyperplanes in general position in ${\mathbb{R}}^{n_0}$. It has $S={\sum }_{j=0}^{n_0}\left(\genfrac{}{}{0px}{}{n_L}{j}\right)$ chambers by [F3], and there are finitely many chambers. Choose one point $y_C$ in each chamber and set $A={\max }_C\mathrm{\parallel }{y}_C{\mathrm{\parallel }}_{\mathrm{\infty }}$. With $c=(1\mathrm{/}2,\dots ,1\mathrm{/}2)$ and $\lambda =1\mathrm{/}(4(1+A))$, all points $c+\lambda y_C$ lie in the interior of $[0,1{]}^{n_0}$. Translate and scale the arrangement by $y\mapsto c+\lambda y$; it remains in general position and each of its $S$ chambers now meets the interior of the image cube. Use these transformed hyperplanes as the last layer's preactivation zero sets. Each preceding folded box maps affinely and bijectively onto $[0,1{]}^{n_0}$, so every last-layer chamber has a preimage in the interior of every such box. The earlier layers distinguish different boxes, and the last-layer patterns distinguish the $S$ chambers within each box. Multiplying the number of boxes from step 2.1 by $S$ proves the stated lower bound.