claimroutineinferred_dep

Transform sizes and precision satisfy band bounds

Sizes

Tp=\Theta(n)

d=\Theta(p^\epsilon)

\ell=\Theta(p^{1-\epsilon})

\gamma=o(b)

fixes the parameter scales for later lemmas

Claim·§9.2 Input and transform sizes·inside thmInteger multiplication in O(n (lg n)^{1-κ}) time

Statement (paper)

For all sufficiently large

n

, the parameters

b=\lceil\log_2n\rceil

p=6b

d=\lfloor b^\epsilon\rfloor

K=\lfloor d^c\rfloor

T\in[4n/b,8n/b)

r=2^{\lceil(\log_2T)/d\rceil}

and

\ell=\log_2r

satisfy

Tp=\Theta(n)

d=\Theta(p^\epsilon)

K=\Theta(p^{\epsilon c})

\ell=\Theta(p^{1-\epsilon})

and

r=2^{\Theta(p^{1-\epsilon})}

, with the explicit bounds

\frac1{12}p^\epsilon\le d\le p^\epsilon

and

\frac{p}{12d}\le\ell\le\frac{p}{3d}

, so that one may take

a_d=a_r=1/12

b_d=1

b_r=1/3

C_\ell=1

. Moreover, with

\alpha=\lceil(12d^2b)^{1/4}\rceil

and

\gamma=2d\alpha^2

, one has

\gamma<28b^{2/3}

2\le\alpha<\sqrt p

and

\gamma=o(b)

eventually, and

\gamma\le b/4

for

b\ge2^{24}

In plain English

For large

n

, with

b=\lceil\log_2 n\rceil

p=6b

d=\lfloor b^\epsilon\rfloor

K=\lfloor d^c\rfloor

T\in[4n/b,8n/b)

and

r=2^\ell

the smallest such power of two with

r\ge T^{1/d}

, one has

Tp=\Theta(n)

d=\Theta(p^\epsilon)

K=\Theta(p^{\epsilon c})

and

\ell=\Theta(p^{1-\epsilon})

, with explicit bounds

\frac1{12}p^\epsilon\le d\le p^\epsilon

and

\frac{p}{12d}\le\ell\le\frac{p}{3d}

. Also, with

\alpha=\lceil(12d^2b)^{1/4}\rceil

and

\gamma=2d\alpha^2

, we get

\gamma<28b^{2/3}

2\le\alpha<\sqrt p

\gamma=o(b)

and

\gamma\le b/4

once

b\ge2^{24}

Why it's here

This pins down how the dimension, transform length, radix and guard-width parameters scale with the word size

p

, so later steps can invoke the layer and cost-table results with explicit constants (

a_d=a_r=1/12

b_d=1

b_r=1/3

C_\ell=1

). The bound

\gamma=o(b)

(and

\gamma\le b/4

for large

b

) shows the guard region is negligible next to the precision, and it relies on the exponent choices checked in the previous claim, such as

\epsilon<1/12

Classified routine:

Elementary parameter bookkeeping: the asymptotic and explicit bounds follow by direct calculation from the definitions of b, p, d, T, r and α, using the exponent constraints (e.g. ε<1/12) verified in the previous claim.

Selected node

Statement (paper)

In plain English

Why it's here