LCP
The popularity gap
Combinatorics
A cyclic group with small difference set has a nonzero element for which the second largest number of representations is twice the average.
The popularity gap
Suppose that A is a finite, nonempty subset A of a cyclic group of either infinite or prime order. We show that if the difference set A − A is “not too large”, then there is a non zero group element with at least as many as (2 + o(1))|A|^2/|A − A| representations as a difference of two elements of A; that is, the second largest number of representatives is, essentially, twice the average. Here the coefficient 2 is best possible. We also prove continuous and multidimensional versions of this result, and obtain similar results for sufficiently dense subsets of an arbitrary abelian group.