PRP0090canonicalv1Polynomial Refinement
Per-prime witness space |W(x, p_i)| ≤ p_i. Total refined search: O(∑ p_i) = O(k² log k) by PNT. Exponential product space collapses to polynomial sum.
Payload
Polynomial Refinement
| Per-prime witness space | W(x, p_i) | ≤ p_i. Total refined search: O(∑ p_i) = O(k² log k) by PNT. Exponential product space collapses to polynomial sum. |
Polynomial Refinement
Summary
| Per-prime witness space | W(x, p_i) | ≤ p_i. Total refined search: O(∑ p_i) = O(k² log k) by PNT. Exponential product space collapses to polynomial sum. |
Statement
\label{prop:polynomial-refinement}
Let $\Pi$ be $\tau$-admissible with verifier width $W(V) = k_0$, and
let $x$ be a ``yes'' instance at depth $k \geq k_0$. Then:
\begin{enumerate}
\item \textbf{Per-prime bound.}
$|W(x, p_i)| \leq p_i$ for each $1 \leq i \leq k$.
\item \textbf{Search cost.}
\begin{equation}\label{eq:ch57-polynomial-cost}
\operatorname{Cost}(x, k) \;=\;
\sum_{i=1}^{k} |W(x, p_i)|
\;\leq\; \sum_{i=1}^{k} p_i
\;=\; O(k^2 \log k).
\end{equation}
\item \textbf{Comparison.}
Brute-force cost $\operatorname{Prim}(k) \sim e^{k \ln k}$
(exponential); the CRT replaces $\prod$ with $\sum$.
\end{enumerate}
Proof / Justification
No immediate manuscript proof block was extracted in this pilot run.
Source Context
- Registry source:
book-03.jsonlline 154 - Manuscript source:
2nd-edition/book-iii-categorical-spectrum/02_mainmatter/part09/ch57-witness-search-as-address-resolution.texlines 186-204
Lean / Formalization Notes
- Formalization:
formalized - Module:
TauLib.BookIII.Computation.WitnessSearch - Name:
polynomial_refinement_check
Dependencies
- Canonical: III.P22, III.D55
Related Results
Generated by later projection phases.
Related Publications
Generated by later projection phases.
Revision Notes
- 2026-04-24: Initial pilot migration.
Identifiers
Aliases & legacy IDs
III.P23polynomial-refinementprop:polynomial-refinementRelease lines
corpus_v3_workingcorpus_v2Relations
Formalized by (1)
Appears in (1)
Downstream uses (computed) (2)
Items in the corpus that reference this one via load-bearing relations. Computed from the full corpus-v3 graph at build time.
Sources
Version & History
Status disclaimer
A Corpus Item page reports the program's current internal record for this item. It does not imply external verification, scientific consensus, or final proof unless explicitly stated. Read it together with its dependencies, formalization status, and the program's overall stance.