A Cauchy-Davenport theorem for linear maps

Abstract

We prove a version of the Cauchy-Davenport theorem for general linear maps. For subsets $A,B$ of the finite field ${\mathbb{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:{\mathbb{F}}_p^n\to {\mathbb{F}}_p^m$, and subsets $A_1,\dots ,A_n\subseteq {\mathbb{F}}_p$, and gives a lower bound on the size of $L(A_1\times A_2\times \dots \times A_n)$ in terms of the sizes of the sets $A_1,\dots ,A_n$. Our proof uses Alon's Combinatorial Nullstellensatz and a variation of the polynomial method.

16 pages, 0 figures