The Setting
Take a real matrix with rows, indexed by , and columns, indexed by , every entry in , and a vector whose entries have a small sum. The problem is a rounding problem of discrepancy theory: replace by a vector with entries and , without raising that sum, so that every row sum moves by an amount controlled by the size of the sum and by .
Write for real . Let be a positive integer. When the rows of are the real and imaginary parts of the characters , for , the row sums against a vector of coefficients are the real and imaginary parts of a polynomial at the -th roots of unity . The size of such a polynomial, a function of the form (2) defined below, on the whole circle is then controlled by its size on this grid.
Masses, Signings and Dyadic Vectors
The mass of a vector is the sum of its entries. For a second vector , the row errors of against are the numbers (1)
A signing of the columns of is a vector ; its row sums are the numbers .
A dyadic vector of level , for an integer , is a vector in whose entries are with integers . The dyadic vectors of level are the vectors in .
A polynomial of degree below with complex coefficients is a function of a complex variable of the form (2)
The Claim
Theorem 1. Let be a real matrix with rows and columns, with for all and .
There is a signing with whose row sums satisfy, for every row , (3)✦
Let be a real number with , let be an integer, and let be a dyadic vector of level with mass at most . Then there is a dyadic vector of level , with mass at most that of , whose row errors (1) satisfy, for every row , (4)✦
Let and be as in (b), and let be a dyadic vector of level with mass at most . Then there is a vector , with mass at most that of , whose row errors satisfy, for every row , (5)✦
Let be as in (b), and let have mass at most . Then there is a vector , with mass at most that of , whose row errors satisfy, for every row , (6)✦
Let and be integers, let be a polynomial (2) of degree below with complex coefficients, and let be a number with for every . Then, for every on the unit circle, (7)✦
In the paper, the result reads: signs reversed so that keep the mass from increasing, the dyadic steps give for a constant , and a bound on a grid of points passes to the whole circle.
What Is Checked
The claim is stated over real matrices with rows, columns and entries in , over signings of their columns, over vectors in and dyadic vectors of each level with mass at most a number satisfying , and over complex polynomials of degree below bounded at the -th roots of unity for .