tailieunhanh - Báo cáo toán học: "Discrepancy of Cartesian Products of Arithmetic Progressions"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Discrepancy of Cartesian Products of Arithmetic Progressions. | Discrepancy of Cartesian Products of Arithmetic Progressions Benjamin Doerr 1 Anand Srivastav Petra Wehr Dedicated to the memory of Walter Deuber Submitted Jul 31 2003 Accepted Sep 3 2003 Published Jan 2 2004 MR Subject Classifications 11B25 11K38 22B05 05C15 Keywords arithmetic progressions discrepancy harmonic analysis locally compact abelian groups. Abstract We determine the combinatorial discrepancy of the hypergraph H of cartesian products of d arithmetic progressions in the N d-lattice N 0 1 . N 1 . The study of such higher dimensional arithmetic progressions is motivated by a multi-dimensional version of van der Waerden s theorem namely the Gallai-theorem 1933 . We solve the discrepancy problem for d-dimensional arithmetic progressions by proving disc H 0 Nd for every fixed integer d 1. This extends the famous lower bound of Q N1 4 of Roth 1964 and the matching upper bound O N1 4 of Matousek and Spencer 1996 from d 1 to arbitrary fixed d. To establish the lower bound we use harmonic analysis on locally compact abelian groups. For the upper bound a product coloring arising from the theorem of Matousek and Spencer is sufficient. We also regard some special cases . symmetric arithmetic progressions and infinite arithmetic progressions. Mathematisches Seminar II Christian-Albrechts-Universitat zu Kiel Christian-Albrechts-Platz 4 24098 Kiel Germany e-mail bed asr @ Supported by the graduate school Effiziente Algorithmen und Multiskalenmethoden Deutsche Forschungsgemeinschaft SAP AG Dusseldorf e-mail THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R5 1 1 Introduction Let H X E denote a hypergraph i. e. X is a finite set and E is a family of subsets of X. Let X X 1 1 be a 2-coloring of X. For E E E define x E 52. E x x . The discrepancy of H is defined by disc H min max x E . X E m We are interested in arithmetic progressions in more than one dimension but let us briefly review the one-dimensional case. Let X N 0 . N 1 and