Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Discrepancy of Sums of Three Arithmetic Progressions. | Discrepancy of Sums of Three Arithmetic Progressions Ales Prívẽtivý Department of Applied Mathematics of Charles University Malostranske nám. 25 11800 Praha Czech Republic privetivy@ Submitted Jul 24 2005 Accepted Dec 5 2005 Published Jan 25 2006 Mathematics Subject Classification 11K38 Abstract The set system of all arithmetic progressions on n is known to have a discrepancy of order n1 4. We investigate the discrepancy for the set system s n formed by all sums of three arithmetic progressions on n and show that the discrepancy of s n is bounded below by Q n1 2 . Thus s n is one of the few explicit examples of systems with polynomially many sets and a discrepancy this high. 1 Introduction Let X F be a set system on a finite set. The discrepancy problem is to color each point of X either red or blue in such a way that any of the sets of F has roughly the same number of red points and blue points. The maximum deviation from an even splitting over all sets of F is the discrepancy of F denoted by disc F . Formally disc F min max X T -1 1 S2F JA x x2S For further information see Beck and Sós BS95 Chazelle Cha00 and Matousek Mat99 . Let n be a positive integer and let n denote the set 0 1 . n 1 . For any a 2 Z and d1 n1 2 N we define the arithmetic progression AP a d1 n1 as the set a id1 i 2 n1 . The set system formed by all arithmetic progressions on n we denote by n Sn where Sn AP a d1 n1 n n a d1 n1 2 N . The lower bound Q n1 4 on the discrepancy of arithmetic progressions Sn proved by Roth Rot64 was one of the early results in combinatorial discrepancy. In 1974 Sarkozy see ES74 established an O n1 3 e upper bound. This was improved by Beck Bec81 Supported by Czech Science Foundation grant 201 05 H014. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R5 1 who obtained the near-tight upper bound of O n1 4 log5 2 n inventing the powerful partial coloring method for that purpose. The asymptotically tight upper bound O n1 4 was hnally proved by MatouSek and