ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck passverified 2026-10-22 (gpt-6.1-sol)

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.

Finite samples cannot identify every Lipschitz function uniformly

Example

Let $N \geq 1$ and let $x_{1}, \dots, x_{N} \in [0, 1]$ be arbitrary training inputs. For every deterministic learning rule that returns a prediction function $g : [0, 1] \to R$ from the observed pairs $(x_{i}, f (x_{i}))$ , there are two $1$ -Lipschitz functions $f_{0}, f_{1} : [0, 1] \to R$ agreeing with each other and taking the common value $0$ at every training input but satisfying $∥ f_{1} - f_{0} ∥_{\infty} \geq \frac{1}{2 (N + 1)} .$ Consequently, at the midpoint of a largest sample-free interval, the returned prediction function $g$ has absolute prediction error at least $1 / (4 (N + 1))$ for at least one of these two indistinguishable target functions.

Example references

A finite-sample limit that motivates explicit inverse-map and architecture classes. ‡

Facts & Assumptions

Given: $N \geq 1$ , arbitrary sample sites $x_{1}, \dots, x_{N} \in [0, 1]$ , exact labels $f (x_{i})$ , and a deterministic learning rule depending only on these observed pairs.

[A1]

A function is $1$ -Lipschitz when $∣ f (x) - f (y) ∣ \leq ∣ x - y ∣$ for all $x, y \in [0, 1]$ .

Verification

1.1givenA1construct

Sort the distinct sample sites together with endpoints $0$ and $1$ . The at most $N + 1$ consecutive gaps have total length one, so one open gap $(a, b)$ has length $ℓ = b - a \geq 1 / (N + 1)$ . Let $x_{*} = (a + b) / 2$ , $r = ℓ / 2$ , $f_{0} (x) = 0$ , and $f_{1} (x) = \max {0, r - ∣ x - x_{*} ∣}$ . The tent has slopes of magnitude at most one, vanishes at every sample site, and has height $r \geq 1 / (2 (N + 1))$ at $x_{*}$ . Thus $f_{0}, f_{1}$ are both $1$ -Lipschitz and yield identical training pairs.

2.1givenstep 1.1algebra∎

Because the training pairs are identical, the deterministic rule returns the same value $g (x_{*})$ for both target functions. Since $∣ g (x_{*}) - f_{0} (x_{*}) ∣ + ∣ g (x_{*}) - f_{1} (x_{*}) ∣ \geq ∣ f_{1} (x_{*}) - f_{0} (x_{*}) ∣ = r$ , one of the two errors is at least $r / 2 \geq 1 / (4 (N + 1))$ . Their uniform distance is $r \geq 1 / (2 (N + 1))$ , proving both claims.

Used by

Nothing in the library uses this result yet.

Dependency tree · 0 levels

Nothing. This result depends on no other item in the library.