Lower Bounds for Expressions of Large Sieve Type

We show that the large sieve is optimal for almost all exponential sums, thus proving a conjecture by Erd"os and Renyi.