Expectation of a Random Subset of the Roots of Unity. 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.
 A: 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. 
