Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Discrepancy of Cartesian Products of Arithmetic Progressions"
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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 e.g. 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 @numerik.uni-kiel.de Supported by the graduate school Effiziente Algorithmen und Multiskalenmethoden Deutsche Forschungsgemeinschaft SAP AG Dusseldorf e-mail petra.wehr@sap-ag.de 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