Báo cáo toán học: "Discrepancy of Sums of Three Arithmetic Progressions"

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

Không thể tạo bản xem trước, hãy bấm tải xuống
TÀI LIỆU LIÊN QUAN
TÀI LIỆU XEM NHIỀU
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
59    237    1    29-03-2024
124    539    16    29-03-2024
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.