8
$\begingroup$

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:

  1. What can be said about $f(n,w):=\max_{v\in\{0,1\}^n, |v|_1=w} |A_n( v)|_1$?
  2. 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.

$\endgroup$

1 Answer 1

6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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