claimroutine

Per-line setup cost is negligible

Per-line setup totals o(Tp)o(Tp) since there are at most 2dT/r2dT/r lines
lets per-line overhead be ignored
Claim·§8.2 Growing dimension and the padded array·inside lemTensor resampling across d dimensions

Statement (paper)

Since ti≥r/2t_i\geq r/2, each tensor map invokes at most ∑iT/ti≤2dT/r\sum_iT/t_i\leq 2dT/r lines. Hence for any fixed setup degree cc, work O(pc)O(p^c) per line totals O(dTpc/r)=o(Tp)O(dTp^c/r)=o(Tp), because after division by TpTp the ratio is O(dpc−1/r)O(dp^{c-1}/r), which tends to zero when rr grows faster than every fixed polynomial in pp and dd is polynomially bounded in pp.

In plain English

Because each ti≥r/2t_i\geq r/2, a tensor map handles at most 2dT/r2dT/r lines, so any fixed polynomial O(pc)O(p^c) setup per line totals O(dTpc/r)O(dTp^c/r), which is o(Tp)o(Tp) when rr outgrows every fixed polynomial in pp and dd is polynomially bounded in pp.

Why it's here

This justifies the last sentence of the lemma: line-by-line setup overhead can be ignored next to the TpTp cost of moving the padded array. The key is that the number of lines is only about dT/rdT/r, so dividing by TpTp leaves O(dpc−1/r)→0O(dp^{c-1}/r)\to 0.
Classified routine:
A direct counting estimate: since each t_i ≥ r/2, the number of lines is at most 2dT/r, and the asymptotic comparison then follows from the stated growth assumptions on r and d. This is elementary bookkeeping inside the tensor resampling lemma.

Uses

Nothing else in the paper

Used by

Nothing in the paper

Sources

PaperOpen
Section
§8.2 Growing dimension and the padded array
Page
—
Label
—
Line
sections/07-resampling.tex:396
Leannot aligned

Phase 2 aligns this node to a Lean declaration.