> Let ({fω}ω∈Ω,Ω) be the decomposition that corresponds to N. Label the parts 1,...,p.

p is the number of regions the deep network divides R^n into, and is in general exponential in the network depth. (Eg consider R^1 = [-1,+1], L[k](x) = 2*abs(x)-1 ∀k (where abs(x) = x - 2*ReLU(-x), IIRC), which divides R^1 into 2^D equal segments using only D individual ReLUs, assuming I wrote the formulas down correctly.)

So for a arbitrary deep network the shallow network size is definitely exponential in input depth, and while it's not clear whether that's true for typical 'trained' deep networks, I would be surprised if it wasn't.