lemmaroutine

Affine updates on digit fields cost linear time

Affine updates y↦y+a(modqb)y\mapsto y+a \pmod{q^b} on digit fields cost O(V)O(V)
linear-cost shear step for matrix shears and shifts
Lemma·lem:ordered-affine-streams·§2.1 Array order and elementary scans

Statement (paper)

Fix a prime qq, a fixed number of control fields, and finitely many rational coefficients whose denominators are prime to qq. Whenever a coefficient is used as a unit, also require its numerator to be prime to qq. Put Q=qbQ=q^b, b≥1b\ge1. Suppose a target field y∈[Q]y\in[Q] follows its control fields, each control used in an offset having O(b)O(b) digits. An update y⟼y+a(controls)(modQ) y\longmapsto y+a(\text{controls})\pmod Q costs O(V)O(V) if the offset can be prepared in bO(1)b^{O(1)} time from the fixed number of control values. In particular, this holds for a fixed rational linear combination of them, specialized modulo QQ. Multiplication of yy by any of the specified rational units, and its inverse, also costs O(V)O(V). Arbitrarily long intervening spectator fields and suffix records are permitted.

In plain English

For a prime power Q=qbQ=q^b, a target field y∈[Q]y\in[Q] can be updated by y↦y+a(controls)(modQ)y\mapsto y+a(\text{controls})\pmod Q in O(V)O(V) time when the offset has O(b)O(b) digits and is computable in bO(1)b^{O(1)} time from a fixed number of control fields, e.g. a fixed rational linear combination reduced mod QQ. Multiplying yy by a specified rational unit, or its inverse, also costs O(V)O(V), even with arbitrarily long spectator fields or suffix records between the fields.

Why it's here

This is the basic cost bound for shears and controlled shifts: it lets later lemmas treat each affine or unit-multiplication update on an array field as a single linear-time scan. It builds on the elementary digit scans of the previous lemma, which handle moving past spectator data, so that only the small bO(1)b^{O(1)} arithmetic on the fields is charged per item.
Classified routine:
A Turing-machine bookkeeping consequence of the preceding elementary-scan lemma: each per-item update costs b^{O(1)} on O(b)-digit fields, which is absorbed into a linear-time scan over the array. This is standard multitape streaming accounting, not a new idea.

Uses

lemElementary digit scans run in linear time

Used by

lemMatrix shear via few interchangeslemPacked XOR of selected address bitsclaimThree shears interchange the two chunksclaimRotations cost O(V L^τ) via swapsclaimCRT address map via controlled shifts

Sources

PaperOpen
Section
§2.1 Array order and elementary scans
Page
—
Label
lem:ordered-affine-streams
Line
sections/02-streams.tex:124
Leannot aligned

Phase 2 aligns this node to a Lean declaration.