An Optimization Problem with Complex Variables, regarding Eigenvalues of Circulant Matrices

Question

Let $S$ be a finite subset of the complex unit circle and $1 \in S$. For each $n \in \mathbb N $, define $f_n\colon S^{n-1}\to\mathbb R$ by $$f_n(x) := \sum_{w^{n}=1}|x_1w+ x_2w^2\cdots+x_{n-1}w^{n-1}|$$ Denote $z^*_n := \min_{S^{n-1}} f_n$.

Is it true that for sufficiently large $n$s (which depend on $S$), we have $z_n^* = 2(n-1)$?

Remarks:

• $f_n(x)$ is sum of the absolute values of eigenvalues of a circulant matrix generated by $(0,x_1,x_2,\ldots,x_{n-1})$.

• $f_n(x) = 2(n-1)$, when $x$ is all ones vector.

• Above question stems from this question and may be related to the Littlewood problem, as a comment of Tao to the last linked question.

Answer 1

The answer is no if there exists $z \in S$ with $z \neq 1$ and $\vert 1 - z\vert \leq \frac{1}{2}$ and $\bar{z} \in S$ :

Let $$p(x) = \sum_{k=0}^{n-1} b_k x^k$$ and $x_k = p(w^k)$ , where $w=e^{\frac{2 \pi i}{n}}$ .

Then the $n b_k$ are the eigenvalues of the circulant matrix.

Now choose
$$p(x) = 1 - \frac{1}{n} \sum_{k=0}^{n-1} x^k + (z-1) \frac{1}{n} \sum_{k=0}^{n-1} w^k x^k + (\bar{z}-1) \frac{1}{n} \sum_{k=0}^{n-1} w^{-k} x^k$$

Then $p(1)=0$, $p(w)=\bar{z}$, $p(w^{-1})=z$ and $p(w^k)=1$ otherwise.

Furthermore we have $b_0 = 1 - \frac{1}{n}(3 - 2 Re (z))$ and $b_k = \frac{1}{n}(-1 + 2 Re ((z-1)w^k)) \leq 0$ for $k \neq 0$.

Therefore $$\sum_{k=0}^{n-1} \vert b_k\vert = 2 b_0 < 2 (1 - \frac{1}{n})$$