Width needed to represent a piecewise linear function

ProofAdvanced⏱ 1 hourDeep Learningreluexpressivitydepthpiecewise linear

Problem

Show that a one-hidden-layer ReLU network with $m$ units on $\R$ computes a piecewise linear function with at most $m+1$ pieces.
Show that a depth- $L$ network of width $2$ can compute a sawtooth with $2^L$ pieces.
Deduce a depth separation and state its scope carefully.

Write a complete argument. Every inequality you use should be one you could state precisely.

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Problem	Field	Type	Difficulty	Time
XOR is not linearly separable	Deep Learning	Proof	Foundation	15 min
Derive the backpropagation recursion	Deep Learning	Proof	Intermediate	30 min
Gradient magnitude through a deep chain	Deep Learning	Proof	Intermediate	30 min
Implement backpropagation from scratch run	Deep Learning	Coding	Intermediate	3 hours