ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedjudge pass (gpt-6-luna)verified 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.

Identity design: noiseless recovery and a noisy minimax lower bound

Example

Assume the Axiom of Choice. Let $n, d, s \in N$ with $n \geq 1$ , $d \geq 2$ , $1 \leq s \leq d / 2$ , and $σ > 0$ . Use one-based coordinate labels $j = 1, \dots, d$ , with coordinate $j$ identified with the library's coordinate $j - 1$ , and put $Θ_{s, d} : = {θ \in R^{d} : ∣ {j \in {1, \dots, d} : θ_{j} \neq 0} ∣ \leq s},$ and let $I_{d}$ be the $d \times d$ identity matrix. For $θ \in Θ_{s, d}$ , observe independent coordinates $Y_{j} \sim N ((I_{d} θ)_{j}, σ^{2} / n), 1 \leq j \leq d .$ The zero kernel of $I_{d}$ implies the strict nullspace property of order $s$ , so the noiseless basis-pursuit problem uniquely recovers each $s$ -sparse $θ$ . In this noisy Gaussian model, every Borel estimator $T : R^{d} \to R^{d}$ satisfies $\sup_{θ \in Θ_{s, d}} E_{θ} [\sum_{j = 1}^{d} (T (Y)_{j} - θ_{j})^{2}] \geq \frac{σ^{2} s \log (e d / s)}{200000 n} .$

Example references

Axiom of Choice

Strict nullspace property and coordinate conventions

Finite-dimensional one-norm and two-norm

Identity matrix and matrix multiplication

Exact recovery under the strict nullspace property

Gaussian sparse-sequence minimax lower bound

Facts & Assumptions

Given: The Axiom of Choice; integers $n \geq 1$ , $d \geq 2$ , and $1 \leq s \leq d / 2$ ; $σ > 0$ ; the class $Θ_{s, d}$ and independent Gaussian observation law in the Example; and a Borel estimator $T : R^{d} \to R^{d}$ .

[A1]

The Axiom of Choice: the Axiom of Choice states that every family of nonempty sets has a choice function; the minimax supplier used below explicitly assumes this axiom.

[F1]

The strict nullspace property: the strict nullspace property tests every nonzero $h \in \ker A$ ; if $\ker A = {0}$ , the condition is vacuous for every admissible order $1 \leq s \leq d$ .

[F2]

Exact basis-pursuit recovery under the strict nullspace property: strict NSP of order $s$ implies unique noiseless $ℓ_{1}$ recovery for every vector with at most $s$ nonzero coordinates.

[F3]

Gaussian sparse-sequence minimax lower bound: under AC, for $n, d \geq 1$ , $σ > 0$ , and $1 \leq s \leq d / 2$ , independent $N (θ_{j}, σ^{2} / n)$ coordinates over $Θ_{s, d}$ give every Borel estimator squared- $ℓ_{2}$ risk at least $σ^{2} s \log (e d / s) / (200000 n)$ in the worst case.

[F4]

The $p$ -norms $∥ x ∥_{p}$ for rational $p \geq 1$ , and $∥ x ∥_{\infty}$ : $∥ u ∥_{2}^{2} = \sum_{j = 1}^{d} u_{j}^{2}$ for $u \in R^{d}$ .

[F5]

Each $∥ \cdot ∥_{p}$ is a norm on $R^{n}$ , and the induced metrics are exactly $d_{1}$ , $d_{2}$ and $d_{\infty}$ of the published metric-spaces page: the defined $ℓ_{2}$ function is a norm on $R^{d}$ .

[F6]

Rectangular matrix multiplication and the identity matrix $I_{n}$ , including zero-sized shapes: $I_{d}$ has diagonal entries $1$ and off-diagonal entries $0$ .

[F7]

The strict nullspace property: $(A u)_{i} = \sum_{j = 1}^{d} A_{i j} u_{j}$ under the one-based coordinate relabeling.

[F8]

Laws of finite sums and finite products: finite sums split at an index, and the sum of a list with exactly one nonzero term is that term.

Verification

1.1givenF1F2F6F7F8algebra

For each $i \in [d]$ , [F6] and [F7] give $(I_{d} h)_{i} = \sum_{j = 1}^{d} δ_{i j} h_{j} = h_{i}$ by [F8], so $I_{d} h = 0$ forces $h = 0$ and $\ker I_{d} = {0}$ . Hence $I_{d}$ satisfies strict NSP of order $s$ vacuously by [F1], and [F2] gives unique noiseless $ℓ_{1}$ recovery for every $θ \in Θ_{s, d}$ .

2.1givenA1F3F4F5algebra∎

For each $θ \in Θ_{s, d}$ , $(I_{d} θ)_{j} = θ_{j}$ , so the stated independent observation coordinates have exactly the Gaussian sequence laws in [F3]. The parameter, sample-size, noise, sparsity, estimator, and AC hypotheses in [A1] and [F3] are all among the Given; applying [F3] proves the displayed minimax lower bound in its sum-of-squares form by [F4], where [F5] confirms that the displayed squared error is the squared Euclidean norm.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

62 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.