ExampleConstruction: Literature-sourcedVerification: 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.

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.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

6 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

Matus Telgarsky, Benefits of Depth in Neural Networks, §3.4 (standard reference, not scraped)
Matus Telgarsky, Deep learning theory lecture notes, Chapter 5 (standard reference, not scraped)