CounterexampleConstruction: 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.

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.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

3 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, Theorem 1.1 and §3.4 (standard reference, not scraped)