claimroutine

Immediate paths and factor values certified

Immediate paths have

2^{O(d)}

short descriptors and factor values fit the interface

certifies the immediate-path and factor parts of the recipes

Claim·§11.4 Certificates for the estimator recipes·inside lemEstimator recipes have regenerable records and bounded control

Statement (paper)

A group has at most

2^{O(d)}

immediate descriptors, each stored literally in

O(d)

bits without storing any discovered endpoint, and all factor budgets are at most

M-d

. Index, range and constituent existence tests call only these lower factors, factor digits can be requested separately by an arithmetic evaluation path, and the rate factors have logarithmic range

O(d)

, so the fixed number of bounded-factor products, coefficients and

O(d)

scale shifts obey Theorem .

In plain English

A group has at most

2^{O(d)}

immediate descriptors, each stored literally in

O(d)

bits with no discovered endpoint stored, and all factor budgets are at most

M-d

. Existence tests call only these lower factors, factor digits can be requested separately by an arithmetic evaluation path, and the rate factors have logarithmic range

O(d)

, so the fixed number of bounded-factor products, coefficients and

O(d)

scale shifts fall under Theorem thm:arith-interface.

Why it's here

This is the step of the recipe-certificate proof that shows the immediate-path and factor-value parts of an estimator operation have short regenerable records and bounded numerical control. It combines the short descriptors and budget drop of the immediate-candidate lemma with the ordered path shape of the unbalanced-path lemma, so the arithmetic interface bound applies to the factor products directly. That supplies the

c_{\mathrm{str}}d+c_{\mathrm{num}}(t-j)

record bound stated in the parent lemma.

Classified routine:

This step assembles earlier results. It applies the short-descriptor and budget-drop bounds of lem-est-paths and the ordered path form of lem-ctrl-paths, then checks the hypotheses of the paper's arithmetic interface theorem (thm-arith-interface) for the factor products.

Uses

lemImmediate candidates are short and well-formedlemUnbalanced estimator paths have ordered restoring formthmUniform numerical interface for arithmetic recipes

Used by

Nothing in the paper

Sources

PaperOpen

Section: §11.4 Certificates for the estimator recipes
Page: —
Label: —
Line: sections/implementation.tex:808

Leannot aligned

Phase 2 aligns this node to a Lean declaration.