Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $p$ be a prime. If $1_A(x)$ denotes the indicator function of the set $A\subset\mathbb{Z}/p\mathbb{Z}$ and $$\hat{1}_A(t):=\frac{1}{p}\sum_{n=1}^p 1_A(n)e^{2\pi i \frac{nt}{p}}$$ denotes the Fourier transform of $1_A$, then what can be said about $$\mathbb{E}\left( \sup_{t\neq 0} |\hat{1}_A(t)|\right)?$$ Do we have an upper bound of the form $O\left(\frac{\log p}{\sqrt{p}}\right)$ as $p$ goes to infinity?

Alternate wording: For each subset $A$ of the $p$ roots, let $Sum(A)$ to denote the sum of the elements in $A$, and look at $A^t:=\{a^t:\ a\in A\}$ for integers $0<t<p$. Then, what is the expectation of the maximum of the sum over $t$? How well can we bound $$\mathbb{E}_A\left(\sup_{t} \ \left|Sum\left(A^t\right)\right|\right).$$

Remarks: This question originated from an optional homework problem in my Arithmetic Combinatorics class. I tried some fairly long and drawn out things that did not work. Also, note that since $p$ is prime, taking the power for $0<t<p$ corresponds exactly to the automorphisms.

share|cite|improve this question
This might be a silly question, but how do you take the sup of a set of complex numbers ? – Joel Cohen Jan 19 '12 at 21:49
Just an aside regarding terminology: It might be good to be cautious with the use of the terms "characteristic function" and "Fourier transform" here. Indeed, in probability the use of the term "characteristic function" is interestingly enough a Fourier transform and, the term "indicator function" is used for functions like $1_A$ that are usually referred to as "characteristic functions" in other branches. – cardinal Jan 20 '12 at 1:45
@JoelCohen: Sorry! My mistake, I forgot some critical absolute value bars. – Eric Naslund Jan 20 '12 at 9:05
Disregard my comment last night, I was thinking of a similar but different problem. – anon Jan 20 '12 at 19:41

A simple probabilistic approach works. In fact, I get a bound of $O(\sqrt{p \log p})$ on the expectation of $\sup_t |Sum(A^t)|$.

Step 1: In this step, let's assume $t=1$, and bound the random variable $Sum(A)$ where $A$ is a uniformly random subset of the roots of unity $\{ 1, \zeta, \ldots, \zeta^{p-1} \}$. Let $X_i$ be the complex random variable that counts the contribution of $\zeta^i$ to the sum; i.e., $X_i$ equals $\zeta^{i}$ if $A$ contains it, and zero otherwise.

Since the $X_i$'s are independent, we may think of bounding their sum using the Chernoff-Hoeffding bound. There is a slight annoyance that our random variables are complex-valued; one simple fix is to bound the real and imaginary parts separately, and then combine them using the triangle inequality. Doing this calculation, we find that the probability that $|Sum(A) - E[Sum(A)]| = |Sum(A)|$ exceeds $2c \sqrt{p \log p}$ is at most $\exp \left(- \frac{2 c^2 p \log p}{4p} \right) = p^{-c^2/2}$.

Step 2: For any fixed $t$, the set $B = A^t$ is again a uniformly random subset of the roots of unity, since the $t$-power map simply permutes the roots. So the above analysis, holds if we replace $A$ by $A^t$ (where $t$ is any fixed number). Then, by the union bound, the probability that $\sup_t |Sum(A^t)| \geq 2c \sqrt{p \log p}$ is at most $(p-1) \cdot p^{-c^2/2} = o(1/p)$, choosing $c$ large enough.

This tail inequality can be easily be converted to a bound on the expectation.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.