claimroutineinferred_dep

Recovery runs in polynomial time

Claim·§D.4.4 Tapered Hermite recovery·inside lemTapered Hermite recovery of F(0)

Statement (paper)

The final combination can be carried out by rational arithmetic in the specified bases: the multipliers

E_t(0)(-t/\alpha)^j

j<q_t

, have numerators and denominators of bit length polynomial in

M,L,a

, there are polynomially many such coefficients, so a common denominator of polynomial bit length exists (e.g. the product of all denominators). After adding, cancelling the powers of two in this common denominator and reducing the resulting integral coordinates modulo

2^p

yields

F(0)

modulo

2^p

in polynomial time and space.

In plain English

The recombination formula for

F(0)

can be evaluated with exact rational arithmetic: the multipliers

E_t(0)(-t/\alpha)^j

for

j<q_t

have polynomial bit length, there are polynomially many, and a common denominator of polynomial size exists, so

F(0)

modulo

2^p

is computed in polynomial time and space.

Why it's here

This is the complexity step that completes the lemma's last assertion. The preceding precision claim shows the stated precisions suffice; here the multipliers are shown to be small rational numbers, so clearing a common denominator, cancelling powers of two, and reducing modulo

2^p

is efficient.

Classified routine:

This is a standard bit-complexity check: there are polynomially many rational multipliers of polynomial bit length, so exact rational arithmetic with a common denominator, followed by reduction modulo 2^p, runs in polynomial time. It follows directly from the preceding precision claim.

Uses

claimStated precisions recover F(0) mod 2^p

Used by

Nothing in the paper

Sources

PaperOpen

Section: §D.4.4 Tapered Hermite recovery
Page: —
Label: —
Line: quantitative-contraction.tex:327

Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

info
inferred_dep
outline: "Polynomial-time rational recombination" rests on claim-lem-tapered-hermite-4