TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

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.

Rank-sensitive upper bound for ReLU linear regions

Statement

Let $n_{0}, L, n_{1}, \dots, n_{L} \geq 1$ be integers and consider a standard adjacent-layer ReLU network with input dimension $n_{0}$ and $L$ hidden layers of widths $n_{1}, \dots, n_{L}$ . Define $J$ to be the set of integer tuples $(j_{1}, \dots, j_{L})$ satisfying $0 \leq j_{ℓ} \leq \min {n_{0}, n_{1} - j_{1}, \dots, n_{ℓ - 1} - j_{ℓ - 1}, n_{ℓ}} (1 \leq ℓ \leq L),$ where for $ℓ = 1$ the terms between $n_{0}$ and $n_{ℓ}$ are absent. The number of full-dimensional activation-pattern regions is at most $\sum_{(j_{1}, \dots, j_{L}) \in J} \prod_{ℓ = 1}^{L} (\binom{n_{ℓ}}{j_{ℓ}}) .$ For one hidden layer, the bound is attained by hyperplanes in general position.

Statement references

Serra et al., Theorem 1 and proof: exact ReLU region upper bound

Telgarsky, Chapter 5: depth and approximation context

Facts & Assumptions

Given: The layer widths and region convention in the statement, and the recursion in Rank-sensitive layer recursion for ReLU regions.

[F1]

Starting from an affine image of dimension $n_{0}$ , the continuation count satisfies the recurrence defining $R_{1} (n_{0})$ (Rank-sensitive layer recursion for ReLU regions).

[F2]

An arrangement of $n_{1}$ hyperplanes in general position in dimension $n_{0}$ has exactly $\sum_{j = 0}^{\min (n_{0}, n_{1})} (\binom{n_{1}}{j})$ regions (Hyperplane arrangement upper count and general-position count).

Proof

1.1givenF1algebra

Expand [F1]'s recurrence successively for $ℓ = 1, \dots, L$ . At layer $ℓ$ , the prior choices have reduced the available affine dimension to at most $\min (n_{0}, n_{1} - j_{1}, \dots, n_{ℓ - 1} - j_{ℓ - 1})$ , so the allowed next indices are exactly those in $J$ . Each term contributes the factor $(\binom{n_{ℓ}}{j_{ℓ}})$ , and the terminal continuation is $1$ . This gives the displayed sum.

2.1F2step 1.1∎

If $L = 1$ , the first layer is an arrangement of $n_{1}$ affine hyperplanes in the input space. By [F2], a general-position choice attains the sum, proving tightness for one hidden layer.

Depends on

Used by

Dependency tree · two levels

4 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Serra, Tjandraatmadja, and Ramalingam, Bounding and Counting Linear Regions of Deep Neural Networks, Theorem 1 (standard reference, not scraped)
Matus Telgarsky, Deep learning theory lecture notes, Chapter 5 (standard reference, not scraped)