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.



Maximal $L_1$ norm of Fourier Transform of a Subset
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](http://www.ams.org/mathscinet-getitem?mr=2456890) 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](http://www.ams.org/mathscinet-getitem?mr=621019) and [by Konyagin](http://www.ams.org/mathscinet-getitem?mr=616222)) to be of interest.


