Concept
Bounding every partial sum despite exponentially many updates
Suppose each cleared factor has coefficient norm at most B>=1, there are m factors, and n Boolean variables. Products of group sums contribute numerators of norm at most 2^n*B^m over Omega. If N_updates signed contributions are added, every partial accumulator has numerator norm at most N_updates*2^n*B^m, not just the final answer. Thus its bit length is O(log2(N_updates+1)+n+m*log2 B). Here N_updates<=C_q*(2D+1)^c<=3^n*(2D+1)^c, where c is the total number of measurement rows. Processing another tuple adds a contribution; it does not multiply it into the previous accumulator. Cancellation is not needed to justify the bound.
0
1
Updated 2026-11-07
Tags
Math