Event Series
Event Type
Seminar
Thursday, November 18, 2021 3:00 PM
Yunkun Zhou (Stanford University)
Given a set X and a family F of subsets of X, we would like to choose a two-coloring of X so that the absolute differences of the numbers of elements of each color in each set in F is small. Formally, we define the discrepancy of the set family F to be the largest number t so that no matter how we color X with two colors, there exists a set in F in which the numbers of elements in each color differ by at least t. In the case where X is the first n positive integers and F is the set of arithmetic progressions in X, celebrated theorems of Roth (using Fourier analytic method) and of Matoušek and Spencer (using entropy method) show that the discrepancy is n^{1/4} up to a  constant factor. In joint work with Jacob Fox and Max Wenqiang Xu, we extend their methods to study the analogous question when X = Z_n and F is the set of modular arithmetic progressions in Z_n. We determine the discrepancy up to constant factor when n is a prime power, and up to a n^{o(1)} factor for all n.