Image for the paper "The popularity gap"
Image for the paper "The popularity gap"
Image for the paper "The popularity gap"
Image for the paper "The popularity gap"
LCP
Image for the paper "The popularity gap"
Image for the paper "The popularity gap"
Image for the paper "The popularity gap"
Image for the paper "The popularity gap"
Image for the paper "The popularity gap"
Image for the paper "The popularity gap"
Image for the paper "The popularity gap"
Image for the paper "The popularity gap"
Image for the paper "The popularity gap"
Image for the paper "The popularity gap"
Image for the paper "The popularity gap"
Image for the paper "The popularity gap"

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.

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.