TheoremStatement: AI-adaptedProof: AI-adaptedPipeline-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.

Finite-candidate information design returns an exact or certified approximate optimum

Statement

Assume AC for the library KL/EIG convention.

Assume the finite-candidate algorithm's hypotheses. A candidate is admissible when it is dimension-valid and its symmetric noise covariance is positive definite; let $V$ be the ordered list of admissible candidates and let $F = (d \in V : c_{d} \leq B)$ in the inherited order. For each $d \in F$ , let $U_{d} = EIG (d) - c_{d}$ be its exact utility. In exact-real mode, if $F$ is nonempty, the algorithm returns the first index in $F$ attaining $\max_{d \in F} U_{d}$ ; if $V$ is empty it returns all-inadmissible, and if $V$ is nonempty but $F$ is empty it returns budget-exhausted.

For the floating-point mode, suppose each $d \in F$ has a computed score ${\hat{U}}_{d}$ , a symmetric positive-semidefinite matrix ${\hat{Z}}_{d}$ , a successful factor ${\hat{R}}_{d}$ , and certified radii $δ_{d} \geq 0$ , $0 \leq ρ_{d} < 1$ , and $λ_{d} \geq 0$ such that $∥ {\hat{Z}}_{d} - Z_{d} ∥_{2} \leq δ_{d}, ∥ {\hat{R}}_{d} {\hat{R}}_{d}^{T} - (I_{m_{d}} + {\hat{Z}}_{d}) ∥_{2} \leq ρ_{d},$ where $Z_{d}$ is the exact Cholesky-whitened matrix in the algorithm's Definition, and $∣ {\hat{U}}_{d} - (\frac{1}{2} \log \det ({\hat{R}}_{d} {\hat{R}}_{d}^{T}) - c_{d}) ∣ \leq λ_{d} .$ For example, the matrix-radius component can use the information-matrix perturbation result in its single-design, unit-weight $W = I$ specialization: if $Z_{d} = J_{d}^{T} J_{d}$ , ${\hat{Z}}_{d} = {\hat{J}}_{d}^{T} {\hat{J}}_{d}$ , $∥ J_{d} ∥_{2} \leq K_{d}$ , and $∥ {\hat{J}}_{d} - J_{d} ∥_{2} \leq η_{d}$ , then $δ_{d} \geq 2 K_{d} η_{d} + η_{d}^{2}$ is sufficient, with any separate formation residual added. A rounded triangular-solve backward-error bound must be converted to the needed forward matrix error using a verified conditioning bound. The rounded-Cholesky residual must follow from a successful factorization under its stated floating-point assumptions; in particular, the cited bound assumes $m u < 1 / 5$ , where $m = 20 m_{d} + 20$ and $u$ is unit roundoff. The value $λ_{d}$ must bound the rounded logarithms, their summation, and cost evaluation. Set $ε_{d} = \frac{m_{d}}{2} (δ_{d} + \frac{ρ_{d}}{1 - ρ_{d}}) + λ_{d}$ . If the algorithm returns a candidate $\hat{d}$ with ${\hat{U}}_{\hat{d}} \geq \max_{d \in F} {\hat{U}}_{d} - τ$ , then $\max_{d \in F} U_{d} - U_{\hat{d}} \leq τ + ε_{d^{*}} + ε_{\hat{d}} \leq τ + 2 \max_{d \in F} ε_{d},$ where $d^{*}$ is any exact maximizer. If the certified score intervals show that the selected candidate's lower endpoint exceeds every earlier candidate's upper endpoint and is at least every later candidate's upper endpoint, it is the first exact maximizer. The matrix and factor radii must be certified under the published solve, information-matrix, rounded-Cholesky, and log-determinant error hypotheses; $λ_{d}$ must additionally cover rounded logarithm, summation, and cost evaluation.

Statement references

The exact scan, feasible set, tie rule, and floating-point certificate interface.

Uniform sensitivity errors control the weighted information-matrix error.

A one-point design with the linear sensitivity maps and unit weight instantiates the finite-design perturbation setting.

A common positive eigenvalue floor controls log-determinant error.

A successful rounded Cholesky factorization supplies a residual bound under its operationwise hypotheses.

The natural logarithm turns positive products into sums.

Facts & Assumptions

Given: The algorithm and candidate data in the Statement, and, for each floating-point candidate, the certified matrices and error radii stated there.

[A1]

AC is inherited through the algorithm's EIG/KL convention. The Axiom of Choice

[F1]

The exact candidate utility is the linear-Gaussian EIG minus its declared cost; exact-mode updates replace the stored candidate only on a strictly greater score, and floating mode selects the first score at least $\max_{d} {\hat{U}}_{d} - τ$ . Finite-candidate information design

[F2]

For $C ⪰ 0$ and $Γ_{d} ≻ 0$ , $EIG (d) = \frac{1}{2} \log \det (I + Γ_{d}^{- 1 / 2} A_{d} C A_{d}^{T} Γ_{d}^{- 1 / 2})$ . Linear Gaussian information gain has a log-determinant formula

[F3]

A symmetric positive-definite matrix has a unique Cholesky factor; its triangular solves are the unique exact solutions and its triangular determinant is the product of its diagonal entries. A matrix admits a Cholesky factorisation with positive diagonal exactly when it is Hermitian positive definite, and that factor is unique Cholesky solves Hermitian positive-definite systems and has about half the factorisation cost of LU The determinant of a triangular matrix is the product of its diagonal entries

[F4]

Determinants are multiplicative on same-sized finite square matrices. For same-sized finite square matrices over a commutative ring, $\det (A B) = \det (A) \det (B)$

[F5]

A positive-semidefinite matrix has a unique positive-semidefinite square root. A non-negative operator has a unique non-negative square root

[F6]

For a one-point approximate design with $ξ = 1$ , linear sensitivity maps on $R^{m_{d}}$ , and symmetric positive-definite weight $W = I$ , if $Z = J^{T} J$ , $\hat{Z} = {\hat{J}}^{T} \hat{J}$ , $∥ J ∥_{2} \leq K$ , and $∥ \hat{J} - J ∥_{2} \leq η$ , the information-matrix perturbation is at most $2 K η + η^{2}$ . Finite nonlinear observation designs, local identifiability, and weighted information Computed Jacobian error controls the weighted information-matrix error

[F7]

For symmetric matrices on a segment with eigenvalue floor $α > 0$ , $∣ \log \det B - \log \det A ∣ \leq p ∥ B - A ∥_{2} / α$ in dimension $p$ . A uniform positive eigenvalue floor controls log-determinant error

[F8]

A successful rounded Cholesky factorization has its stated spectral residual bound when the operationwise arithmetic and unit-roundoff hypotheses hold. A successful rounded Cholesky factorization has componentwise and normwise backward error bounds

[F9]

A successful rounded triangular solve has a componentwise backward-error bound under its stated normal-range and unit-roundoff hypotheses. Rounded triangular substitution has a componentwise matrix backward error

[F10]

The natural logarithm is multiplicative on positive products: $\log (x y) = \log x + \log y$ , and $\log (x^{2}) = 2 \log x$ for $x > 0$ . Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm

Proof

Given: The hypotheses and notation in the Statement.

1.1givenF1F3algebra

For a valid candidate, $Γ_{d} = L_{d} L_{d}^{T}$ and $V_{d} = L_{d}^{- 1} A_{d}$ , so $Z_{d} = V_{d} C V_{d}^{T}$ is symmetric positive semidefinite. Hence $H_{d} = I_{m_{d}} + Z_{d}$ is positive definite and has the Cholesky factor used by the exact algorithm.

1.2givenF6F7algebra

In floating-point mode, when ${\hat{Z}}_{d} = {\hat{J}}_{d}^{T} {\hat{J}}_{d}$ and $Z_{d} = J_{d}^{T} J_{d}$ , [F6] supplies $δ_{d} \geq 2 K_{d} η_{d} + η_{d}^{2}$ from certified bounds $∥ J_{d} ∥_{2} \leq K_{d}$ and $∥ {\hat{J}}_{d} - J_{d} ∥_{2} \leq η_{d}$ ; any rounded matrix-formation residual is included in the supplied $δ_{d}$ . Both $I + Z_{d}$ and $I + {\hat{Z}}_{d}$ have eigenvalues at least $1$ , and every matrix on their segment does too. Applying [F7] gives $∣ \log \det (I + {\hat{Z}}_{d}) - \log \det (I + Z_{d}) ∣ \leq m_{d} δ_{d}$ .

1.3givenF7F8F9algebra

Put $E_{d} = {\hat{R}}_{d} {\hat{R}}_{d}^{T} - (I + {\hat{Z}}_{d})$ . Every matrix $I + {\hat{Z}}_{d} + t E_{d}$ has quadratic form at least $(1 - t ρ_{d}) ∥ v ∥_{2}^{2} \geq (1 - ρ_{d}) ∥ v ∥_{2}^{2}$ , since $I + {\hat{Z}}_{d} ⪰ I$ and $∥ E_{d} ∥_{2} \leq ρ_{d} < 1$ . Applying [F7] on this segment yields $∣ \log \det ({\hat{R}}_{d} {\hat{R}}_{d}^{T}) - \log \det (I + {\hat{Z}}_{d}) ∣ \leq m_{d} ρ_{d} / (1 - ρ_{d})$ . Under the successful rounded-factorization hypotheses, [F8] provides such a residual radius. [F9] supplies only a backward-error constraint for triangular solves; any forward matrix error used in $δ_{d}$ must additionally account for conditioning.

2.1A1givenF2F3F4F5F10step 1.1algebra

Put $Q_{d} = A_{d} C A_{d}^{T}$ and $W_{d} = Γ_{d}^{- 1 / 2}$ . The square-root identity [F5] gives $Γ_{d} + Q_{d} = Γ_{d}^{1 / 2} (I_{m_{d}} + W_{d} Q_{d} W_{d}) Γ_{d}^{1 / 2}$ . By [F4], $\det (Γ_{d} + Q_{d}) = \det (Γ_{d}^{1 / 2})^{2} \det (I_{m_{d}} + W_{d} Q_{d} W_{d}) = \det (Γ_{d}) \det (I_{m_{d}} + W_{d} Q_{d} W_{d})$ . Also step 1.1 gives $Γ_{d} + Q_{d} = L_{d} H_{d} L_{d}^{T}$ , so [F3]–[F4] give $\det (Γ_{d} + Q_{d}) = \det (Γ_{d}) \det (H_{d})$ with $\det (Γ_{d}) = (\det L_{d})^{2} > 0$ . Dividing proves $\det (I_{m_{d}} + W_{d} Q_{d} W_{d}) = \det (H_{d})$ . By [F2], the exact EIG is $\frac{1}{2} \log \det (H_{d})$ . By [F3], $\det (H_{d}) = \det (R_{d} R_{d}^{T}) = (\prod_{j} (R_{d})_{j j})^{2}$ ; all Cholesky diagonal entries are positive, so [F10] gives $\frac{1}{2} \log \det (H_{d}) = \sum_{j} \log (R_{d})_{j j}$ . Thus the algorithm's exact score equals $U_{d}$ .

2.2givenF7step 1.2step 1.3algebra

The certificate's $λ_{d}$ bounds the remaining rounded log, summation, and cost evaluation. Combining it with steps 1.2, 1.3, the log-determinant perturbation [F7], and the factor $1 / 2$ in the EIG formula gives $∣ {\hat{U}}_{d} - U_{d} ∣ \leq ε_{d}$ .

3.1givenF1step 2.1algebra

For the exact scan, after the first feasible candidate the stored candidate is the first maximum of that one-element prefix. When the next candidate is processed, [F1] says a strictly larger score replaces it; an equal or smaller score leaves it in place, preserving the earliest maximizing index. Repeating this finite comparison through the ordered feasible list proves the final stored candidate is the first global maximizer. The validity and budget tests likewise make all-inadmissible and budget-exhausted exactly the two stated empty-feasible-set cases.

3.2givenF1step 2.2algebra

Let $d^{*}$ maximize exact utility and let $\hat{d}$ be the selected computed $τ$ -maximizer. By [F1] and the hypothesis, ${\hat{U}}_{\hat{d}} \geq \max_{d} {\hat{U}}_{d} - τ$ . Then $U_{d^{*}} \leq {\hat{U}}_{d^{*}} + ε_{d^{*}} \leq \max_{d} {\hat{U}}_{d} + ε_{d^{*}}$ , while $U_{\hat{d}} \geq {\hat{U}}_{\hat{d}} - ε_{\hat{d}} \geq \max_{d} {\hat{U}}_{d} - τ - ε_{\hat{d}}$ . Subtracting gives the stated gap bound.

4.1givenalgebra∎

If the selected interval's lower endpoint exceeds each earlier upper endpoint and is at least each later upper endpoint, then every earlier exact utility is strictly smaller and every later exact utility is no larger. Thus the selected candidate is the first exact maximizer.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

60 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

Stephen Boyd and Lieven Vandenberghe, Convex Optimization, §3.1.5 (standard reference, not scraped)
Tobin A. Driscoll and Richard J. Braun, Fundamentals of Numerical Computation, §§2.8–2.9 (standard reference, not scraped)