DIMACS - Graduate Student Combinatorics Seminar

Title: Arithmetic Progressions Instead of Billiard Paths

Speaker: Humberto Montalvan, Rutgers University

Date: Wednesday, October 27, 2010 12:10pm

Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ


Prof. Beck recently discovered a phenomenon that he named super-uniformity of billiard paths. In essence he was able to prove that for an arbitrary measurable subset A of the unit square, most billiard paths of length T approximate the area of A with O(logT) error. This led him to declare that "the set of typical billiard paths represents the family of most uniformly distributed curves in the square."

He then wondered if there were any interesting discrete analogues of this result. In this talk we will consider the following situation. Let N be a fixed large number and S be an arbitrary subset of the discrete interval {1,2,...,N}. Is it true that the density of A is faithfully represented in most full-length arithmetic progressions taken from the set {1,2,...,N}?

More precisely, is #{1 <= n <= N : n = r (mod m) and n is in S} close to #S/m for most choices of m and r? The answer is no, and this is quite obvious and unfortunate. Prof. Beck was nontheless able to prove something! I will present the precise statement of the result, discuss how it is fundamentally different from the billiard paths result, and give a sketch of its proof. If time permits I will also mention some related unanswered questions.