Maximal $L_1$ norm of Fourier Transform of a Subset

Question

Let $A_n$ be the following $n\times n$ matrix: $(A_n)_{i,j}= \frac{1}{\sqrt{n}}\omega_n^{i\cdot j}$ for all $0 \le i,j <n$, where $\omega_n=e^{\frac{2\pi i}{n}}$.

I want to understand how $A_n$ acts on the set $\{0,1\}^n \subseteq \mathbb{C}^n$ in the following specific sense:

1. Let $f(n)= \max_{v\in\{0,1\}^n} |A_n( v)|_1$. What upper bounds on $f$ exist? What is its asymptotic behavior? Is there a general form for some $v\in \{0,1\}^n$ at which $f$ attains its maximum, or is relatively close to its maximum?

Here are more delicate questions:

2. What can be said about $f(n,w):=\max_{v\in\{0,1\}^n, |v|_1=w} |A_n( v)|_1$?
3. What can be said about $g(n,C):=2^{-n} \{v \in \{0,1\}^n \mid |A_n (v)|_1 \le C\}$?

For the $L_2$ norm these questions are much easier as $A_n$ is unitary and preserves the norm.

Answer 1

Regarding Q1, if one selects $v$ randomly and uses Khintchines's inequality one obtains a lower bound $f(n) \gg n$, which complements the trivial upper bound of $f(n) \leq n$ coming from Plancherel and Cauchy-Schwarz. It looks like the same argument should also show that $f(n,w)$ is comparable to $w^{1/2} n^{1/2}$ for Q2.

For Q3, Theorem 1.3 of this paper of Green and Sanders should (in principle at least) answer the question in the regime where $C$ is a bounded multiple of $n^{1/2}$ (which is the smallest possible nontrivial value of $|A_n(v)|_1$, if I understand your normalisations correctly) and $n$ is large.

While not directly related to your questions (as they are more concerned with the min value of the $L^1$ norm rather than the max, and involve Fourier analysis on the unit circle rather than a cyclic group), you may find the work on Littlewood's conjecture on exponential sums (solved independently by McGehee-Pigno-Smith and by Konyagin) to be of interest.