2025/04/17 by Lily Li, Li, Lily, Aleksandar Nikolov +1
Mathematics · #11K38 (Primary) 11B25 (Secondary) #Analytic Number Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Mathematical Approximation and Integration
paper · pdf · doi:10.48550/arxiv.2504.12598
openalex publication_date 2025/04/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The combinatorial discrepancy of arithmetic progressions inside [N] := \1, …, N\ is the smallest integer D for which [N] can be colored with two colors so that any arithmetic progression in [N] contains at most D more elements from one color class than the other. Bounding the discrepancy of such set systems is a classical problem in discrepancy theory. More recently, this problem was generalized to arithmetic progressions in grids like [N]d (Valkó) and [N1]× … × [Nd] (Fox, Xu, and Zhou). In the latter setting, Fox, Xu, and Zhou gave upper and lower bounds on the discrepancy that match within a (log |Ω|)/(log log |Ω|) factor, where Ω:= [N1]× … × [Nd] is the ground set. In this work, we use the connection between factorization norms and discrepancy to improve their upper bound to be within a √(log|Ω|) factor from the lower bound. We also generalize Fox, Xu, and Zhou's lower bound, and our upper bounds to arithmetic progressions in arbitrary convex bodies.