Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

ReLU approximation rates, depth separation, and linear regions — Examples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

CounterexampleConstruction: Literature-sourcedVerification: AI-adaptedjudge pass (gpt-6-luna)Open item page →

A single high-degree gate defeats the stated small-k separation

Statement refuted

For every integer $k \geq 1$ and dimension $d \geq 1$ , the stated Telgarsky bound asserts that there is a function $f (x) = h^{k^{3} + 4} (x_{1})$ , where $h (z) = ρ (2 ρ (z) - 4 ρ (z - 1 / 2))$ , computed by a ReLU network with $2 k^{3} + 8$ layers, $3 k^{3} + 12$ computation nodes, and $4 + d$ distinct parameters, such that for every positive integer triple $t, α, β$ its $L^{1} ([0, 1]^{d})$ distance from every function in the following union is at least $1 / 64$ : functions computed in at most $k$ computational layers by networks with at most $2^{k / (t α β)}$ gate nodes whose gates are $(t, α, β)$ -semi-algebraic; and sums of at most $t$ affine-threshold decision trees, each with at most $2^{k^{3} / t}$ total nodes, including leaves. Here a $(t, α, β)$ -semi-algebraic gate is a map $g : R^{q} \to R$ expressible as a finite sum of polynomial pieces $p_{j}$ of degree at most $β$ , each multiplied by indicators of conjunctions of signs of at most $t$ predicate polynomials $q_{i}$ of degree at most $α$ ; an affine-threshold decision tree recursively branches on tests $⟨ a, x ⟩ - b \geq 0$ and has constant real outputs at its leaves.

Statement references

Telgarsky, Theorem 1.1: the claimed gate-parameter range

Facts & Assumptions

Given: The parameters and target in the counterexample description.

[F1]

The map $τ (x) = 2 ρ (x) - 4 ρ (x - 1 / 2)$ maps $[0, 1]$ to itself and is $2$ -Lipschitz (Tent-map iterates and ReLU implementation).

[F2]

A degree- $N$ Bernstein polynomial approximates an $L$ -Lipschitz function on $[0, 1]$ within $L / (2 \sqrt{N})$ (Uniform error bound for Bernstein approximation of a Lipschitz function).

Counterexample

Take $d = k = t = α = 1$ and $β = 2^{22}$ . The target is $h^{5} (x)$ on $[0, 1]$ , where $h (x) = ρ (2 ρ (x) - 4 ρ (x - 1 / 2))$ . A single polynomial gate of degree at most $2^{22}$ can compute the Bernstein polynomial of $h^{5}$ of degree $2^{22}$ ; the gate-node cap $2^{1 / 2^{22}}$ permits one node.

1.1givenF1F2algebra

On $[0, 1]$ , $h (x) = 2 x$ for $x \leq 1 / 2$ and $h (x) = 2 - 2 x$ for $x \geq 1 / 2$ , so it equals the tent map in [F1], maps the interval into itself, and is $2$ -Lipschitz. Thus $h^{5}$ is $32$ -Lipschitz. For $N = 2^{22}$ , [F2] gives a degree- $N$ polynomial $P_{N}$ with $\sup_{[0, 1]} ∣ h^{5} - P_{N} ∣ \leq 32 / (2 \sqrt{N}) = 1 / 128$ .

2.1step 1.1algebra∎

A single gate with the constant predicate polynomial $q_{1} (z) = 1$ , condition $q_{1} (z) \geq 0$ , and polynomial piece $P_{N}$ is $(1, 1, N)$ -semi-algebraic; the predicate is always true and has degree $0$ . Since $2^{1 / N} < 2$ , the allowed integer node count is one. The normalized Lebesgue integral on $[0, 1]$ of its error is at most $1 / 128 < 1 / 64$ , so this is a counterexample to the claimed uniform lower bound.

ExampleConstruction: Literature-sourcedVerification: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Tent-map composition gives exponentially many intervals

Example

The scalar ReLU network computing the tenth iterate of the tent map has $20$ hidden units, depth $12$ counting the input and output layers, and $1024$ affine intervals on $[0, 1]$ , each with a distinct full-dimensional activation pattern on its interior. Any one-hidden-layer scalar-input ReLU network of width $20$ has at most $21$ full-dimensional activation-pattern regions.

Example references

Telgarsky, §3.4: tent-map iterates

Telgarsky, Chapter 5: depth and approximation context

Facts & Assumptions

Given: The tent map and region-count conventions in the statement.

[F1]

The $q$ th tent-map iterate has $2^{q}$ affine intervals and is implemented with $2 q$ hidden ReLU units at depth $q + 2$ (Tent-map iterates and ReLU implementation).

[F2]

For a one-hidden-layer scalar-input ReLU network of width $n_{1}$ , the upper region sum is $\sum_{j = 0}^{\min (1, n_{1})} (\binom{n_{1}}{j})$ (Rank-sensitive upper bound for ReLU linear regions).

Verification

1.1givenF1algebrainduction

Set $q = 10$ in [F1]. Then the iterate has $2^{10} = 1024$ dyadic affine intervals, $20$ hidden units, and depth $12$ . In the construction, each layer's second unit is active exactly when its preceding iterate value is greater than $1 / 2$ . The two restrictions of the tent map to $[0, 1 / 2]$ and $[1 / 2, 1]$ are bijections onto $[0, 1]$ , so induction gives a one-to-one correspondence between length-ten branch words and the dyadic intervals. These branch bits are activation bits, and each word is constant on the interior of its interval. Hence the intervals give distinct full-dimensional activation-pattern regions under the zero-inactive convention.

2.1step 1.1F2algebra∎

With $n_{0} = 1$ and $n_{1} = 20$ , [F2] gives at most $(\binom{20}{0}) + (\binom{20}{1}) = 21$ regions. Since the deep network has $1024$ full-dimensional activation-pattern regions by step 1.1, while the shallow bound counts the same quantity, $1024 > 21$ proves the claimed depth-width difference.

ExampleConstruction: Literature-sourcedVerification: AI-adaptedOpen item page →

Same target with adaptive and target-independent architectures

Example

Assume the Axiom of Choice. For $f (x) = x^{2} / 2$ on $[0, 1]$ , which belongs to the unit ball of $W^{1, \infty} ((0, 1))$ , the target-independent theorem supplies one architecture that works for the whole unit ball with size $O (ε^{- 1} \log (1 / ε))$ , while the adaptive theorem supplies an architecture chosen for this $f$ with size $O (1 / [ε \log (1 / ε)])$ and depth $6$ . The ratio of these two upper bounds is $O ((\log (1 / ε))^{- 2})$ as $ε ↓ 0$ .

Example references

Yarotsky, Theorems 1–2: target-independent and adaptive rates

Telgarsky, Chapter 5: depth and approximation context

Facts & Assumptions

Given: The Axiom of Choice, $f (x) = x^{2} / 2$ on $[0, 1]$ , and $0 < ε < 1 / 2$ .

[F1]

The $W^{1, \infty}$ norm is the maximum of the function and weak-derivative essential suprema (Integer-order Sobolev spaces and their norms).

[F2]

Every target in the unit $W^{1, \infty}$ ball has a target-independent architecture of size $O (ε^{- 1} (1 + \log (1 / ε)))$ (Target-independent ReLU rate on the unit Sobolev ball).

[F3]

Every target in the unit $W^{1, \infty}$ ball in one dimension has an adaptive depth-six architecture of size $O (1 / [ε \log (1 / ε)])$ (Target-dependent depth-six approximation of Lipschitz functions).

[A1]

The Axiom of Choice is assumed by both approximation theorems (The Axiom of Choice).

Verification

1.1givenF1algebra

The derivative of $f$ is $f^{'} (x) = x$ , so $∥ f ∥_{L^{\infty}} = 1 / 2$ and $∥ f^{'} ∥_{L^{\infty}} = 1$ . By [F1], $∥ f ∥_{W^{1, \infty}} = 1$ . Directly, $∣ x^{2} - y^{2} ∣ / 2 = ∣ x - y ∣ ∣ x + y ∣ / 2 \leq ∣ x - y ∣$ on $[0, 1]$ , so $f$ is unit-Lipschitz.

2.1step 1.1F2F3A1algebra∎

Under [A1], apply [F2] and [F3] to this same target. Writing $t = \log (1 / ε)$ , the target-independent size is bounded by $C_{1} ε^{- 1} (1 + t)$ and the adaptive size by $C_{2} / (ε t)$ . The quotient of these explicit upper-bound functions is $(C_{2} / C_{1}) / [t (1 + t)] = O (t^{- 2})$ , which tends to zero. Upper bounds alone give no ratio of the actual architecture sizes or of optimal sizes. This comparison makes no claim about optimization or training.

ExampleConstruction: Literature-sourcedVerification: AI-adaptedOpen item page →

Many linear regions give no training or generalization guarantee

Example

Choose a one-hidden-layer ReLU network with input dimension $2$ , hidden width $10$ , and hidden preactivation hyperplanes in general position. Its hidden activation pattern has $56$ full-dimensional regions. If every output weight and the output bias are set to zero, the represented function is identically zero; on the regression distribution with $X$ uniform on $[0, 1]^{2}$ and target $Y = 1$ , its squared prediction risk is exactly $1$ .

Example references

Serra et al., §1 and Theorem 1: region count as an expressivity proxy

Telgarsky, Chapter 5: depth and approximation context

Facts & Assumptions

Given: The one-hidden-layer network, the uniform input distribution, and the constant target in the example.

[F1]

Ten hyperplanes in general position in dimension $2$ induce $\sum_{j = 0}^{2} (\binom{10}{j})$ full-dimensional regions (Hyperplane arrangement upper count and general-position count).

[F2]

The network output is an affine unit applied to input coordinates and hidden-unit values (ReLU feedforward networks and complexity conventions).

Verification

1.1givenF1algebra

By [F1], the activation cells number $(\binom{10}{0}) + (\binom{10}{1}) + (\binom{10}{2}) = 1 + 10 + 45 = 56$ .

2.1givenF2algebra∎

Set all coefficients into the affine output unit and its bias to zero. By [F2], the prediction is then $0$ at every input. Since $Y = 1$ surely, $(0 - Y)^{2} = 1$ surely, so the expected squared risk is $1$ despite the $56$ activation cells.

ReLU approximation rates, depth separation, and linear regions — Examples

2 · Logical flowchart

3 · Definitions, theorems and proofs

4 · Examples, counterexamples and false statements

A single high-degree gate defeats the stated small-k separation

Statement refuted

Statement references

Facts & Assumptions

Counterexample

Tent-map composition gives exponentially many intervals

Example

Example references

Facts & Assumptions

Verification

Same target with adaptive and target-independent architectures

Example

Example references

Facts & Assumptions

Verification

Many linear regions give no training or generalization guarantee

Example

Example references

Facts & Assumptions

Verification

Sources