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: On the Discrepancy of Quasi-progressions. | On the Discrepancy of Quasi-progressions Sujith Vijay Department of Mathematics Rutgers The State University of New Jersey USA sujith@ Submitted Apr 30 2006 Accepted Aug 1 2008 Published Aug 11 2008 Mathematics Subject Classification 05C65 11B25 Abstract A quasi-progression also known as a Beatty sequence consists of successive multiples of a real number with each multiple rounded down to the largest integer not exceeding it. In 1986 Beck showed that given any 2-colouring the hypergraph of quasi-progressions contained in 0 1 . n corresponding to almost all real numbers in 1 1 have discrepancy at least log n the inverse of the tower function. We improve the lower bound to log n 1 4-o 1 and also show that there is some quasi-progression with discrepancy at least 1 50 n1 6. The results remain valid even if the 2-colouring is replaced by a partial colouring of positive density. Introduction A classic result in discrepancy theory is the theorem of Roth 2 stating that if the elements of 0 1 2 . ng are 2-coloured red blue there exists an arithmetic progression a a d . a k 1 dg of discrepancy . difference in the number of reds and blues at least 1 20 n1 4 with 0 a d yVn. In 1996 Matousek and Spencer 10 building upon results by Sarkozy see 3 and Beck 5 showed that apart from constants this result is the best possible. The situation is quite different however for homogeneous arithmetic progressions HAPs the subfamily of arithmetic progressions containing 0. It turns out that there are extremely balanced colourings for such arithmetic progressions. Consider the following examples. X3 3k 1 1 X3 3k 2 1 X3 3k X3 k x3 3k 1 1 x3 3k 2 -1 X 3k 0 Current Address Department of Mathematics University of Illinois at Urbana-Champaign Urbana IL 61801. E-mail sujith@ THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R104 1 It is easy to show that all HAPs contained in 0 1 . ng have discrepancy O log n under the colouring X3 and discrepancy at most 1 under
