lemmaroutine

Tapered Hermite recovery of F(0)

Lemma·lem:tapered-hermite·§D.4.4 Tapered Hermite recovery

Statement (paper)

Let integers

u,M

satisfy

1\le u\le a

and

M\ge u

, and put

h=\lceil3M/u\rceil

. For

t\in S\setminus\{0\}

set

i=v_2(t),\qquad q_t=q(i)=h\max(0,u-i),\qquad D_t=L/2^i.

Suppose

F\in(\mathcal K[V]/(V^\ell))[T]

has degree at most

M(2L-1)

F(0)\in\mathcal A

, and

F(t+\alpha z)\in\mathcal A[z]

for every

t\in S

. For

p\ge1

, its value

F(0)

modulo

2^p

can be recovered from

F(t+\alpha z)\pmod{2^{p_t}}, \qquad p_t=p+8hD_t+8M(a+1),\qquad q_t>0.

Only the first

q_t

coefficients of each polynomial are needed. Recovery takes polynomial time and space in

M,L,\ell,e

and the precisions.

In plain English

A polynomial

F

of degree at most

M(2L-1)

over

\mathcal K[V]/(V^\ell)

with

F(0)\in\mathcal A

and

F(t+\alpha z)\in\mathcal A[z]

for all

t\in S

has its value

F(0)

modulo

2^p

recoverable in polynomial time and space. The inputs are only the first

q_t=h\max(0,u-v_2(t))

coefficients of each

F(t+\alpha z)

, taken modulo

2^{p_t}

with

p_t=p+8hD_t+8M(a+1)

Why it's here

This lemma lets the tensor contraction algorithm recover a value from evaluations at the points of

S

with 2-adic precision that depends on the 2-adic valuation of each point, instead of a uniform precision. The tapered multiplicities

q_t

still exceed the degree bound, so Hermite interpolation determines

F(0)

. The extra

8hD_t

bits in

p_t

cover the bounded precision loss from

E_t(0)

, so a tapered precision budget suffices for correct recovery in polynomial time and space.

Classified routine:

A Hermite-interpolation argument with p-adic precision bookkeeping: multiplicities are tapered by the 2-adic valuation of each node, and the bits lost to the denominators of the interpolation weights are bounded. It follows from classical Hermite interpolation with error accounting and introduces no new idea of its own.

Uses

Nothing else in the paper

Used by

thmSubexponential Boolean tensor network contractionclaimRecursive contraction algorithm is correctclaimTotal number of recursive callsclaimDepth-first traversal gives polynomial space

Inside the proof

claimTapered multiplicities permit Hermite recovery of F(0)claimDivision by E_t loses no precisionclaimTwo-adic loss of E_t(0) is at most 6DhclaimStated precisions recover F(0) mod 2^pclaimRecovery runs in polynomial time

Sources

PaperOpen

Section: §D.4.4 Tapered Hermite recovery
Page: —
Label: lem:tapered-hermite
Line: quantitative-contraction.tex:250

Leannot aligned

Phase 2 aligns this node to a Lean declaration.