Rutgers Discrete Mathematics Seminar

Title: A Cauchy-Davenport Theorem for Linear Maps

Speaker: John Kim, Rutgers University

Date: Monday, October 12, 2015 2:00 pm

Location: Hill center, room 425, Rutgers University, Busch Campus, Piscataway, NJ


We prove a version of the Cauchy-Davenport theorem for general linear maps. For subsets A and B of the finite field F_p, the classical Cauchy-Davenport theorem gives a lower bound for the size of the sumset A+B in terms of the sizes of the sets A and B. Our theorem considers a general linear map L:F_p^n -> F_p^m and subsets A_1, ..., A_n of F_p, and gives a lower bound on the size of L(A_1 x A_2 x ... x A_n) in terms of the sizes of A_1, ..., A_n. Our proof uses Alon's Combinatorial Nullstellensatz and a variation of the polynomial method.

Joint work with Simao Herdade and Swastik Kopparty