The Setting
Let be a real matrix with rows and columns and every entry in , the rows indexed by and the columns by . Putting a sign on each column, one asks how small all row sums can be made at once. This is the question of Spencer’s theorem in discrepancy theory, whose bound for is of order .
On the circle the question concerns Littlewood polynomials. Let be the circle and write . For points of , the rows and have entries in , and for signs in their row sums are the real and imaginary parts of the values of the Littlewood polynomial .
Signings and Partial Colorings
A signing of the columns of is a vector in . A partial coloring of the columns of is a vector in ; it fixes the columns with .
For a vector in , the row sums of at are the coordinates of , (1) and is the largest of them in absolute value.
The Claim
Theorem 1. Let be a real matrix with every entry in , and let .
(a) There is a signing of the columns of with (2)✦
(b) There is a signing of the columns of with (3)✦
(c) If , there is a partial coloring of the columns of that fixes at least columns and has (4)✦
In the paper, the result reads: there is an absolute constant such that for integers and every some has .
The bound (2) gives this with .
What Is Checked
The bounds (2), (3) and (4) are stated over real matrices with entries in whose rows and columns are indexed by finite sets of sizes and with , and over the signings and partial colorings of their columns, measured by the row sums (1).