Concept icon
Concept

Combining recovery weights with bounded rational arithmetic

Each weight E_t(0)(-t/alpha)^j, j<q_t, is a product of polynomially many rational factors with O(a) bits per factor. Its numerator and denominator therefore have polynomial bit length in M,L,a. There are polynomially many weights, so even multiplying their denominators gives a polynomial-bit common denominator. Combine coordinates exactly, cancel powers of two after addition, and reduce the remaining odd-denominator rationals modulo 2^p. Individual terms may have even denominators; reducing them modulo 2^p before the precision argument and rational combination would be invalid. Recovery is polynomial in the stated dimensions and precisions, not in their logarithms.

0

1

Concept icon
Updated 2026-11-08

Contributors are:

Who are from:

Tags

Math