Return to Revisions

$\DeclareMathOperator\re{Re}\DeclareMathOperator\im{Im}\DeclareMathOperator\sgn{sgn}$Let me write $$\begin{align*} A(n)&=\max_{x\in[-1,1]^n}\biggl|\sum_{j<n}x_j\omega^j\biggr|,\\ R(n)&=\max_{x\in[-1,1]^n}\re\sum_{j<n}x_j\omega^j,\\ I(n)&=\max_{x\in[-1,1]^n}\im\sum_{j<n}x_j\omega^j. \end{align*}$$ First, it’s clear that $\re\sum_{j<n}$ is maximized if we maximize the $\re$ of each individual term of the sum, which is done by putting $x_j=\sgn\re\omega^j$. Thus, using also $\sum_{j<n}\omega^j=0$, $$\begin{align*} R(n)&=2\re\sum_{-\frac n4<j<\frac n4}\omega^j,\tag1\\ I(n)&=2\im\sum_{j<n/2}\omega^j.\tag2 \end{align*}$$ That is, the maximum is attained by setting $x_j\in\{-1,+1\}$, where we consider a line going through the origin, and set $x_j=+1$ in one half-plane determined by the half-plane, and $x_j=-1$ in the other half-plane; for $R(n)$, we take the vertical line, and for $I(n)$, the horizontal line.

I claim that the same holds for $A(n)$, for an arbitrary choice of the dividing line. (Edge cases: if the line meets two $\omega^j$’s, one of these $x_j$ gets $+1$ and the other one $-1$; if the line meets one $\omega^j$, the choice of $x_j$ does not matter.) That is, for any $k<n$, $$\tag3A(n)=\biggl|\sum_{j<\lfloor n/2\rfloor}\omega^{k+j}-\sum_{j<\lceil n/2\rceil}\omega^{k+\lfloor n/2\rfloor+j}\biggr|=2\biggl|\sum_{j<\lfloor n/2\rfloor}\omega^{k+j}\biggr|=2\biggl|\sum_{j<\lceil n/2\rceil}\omega^{k+j}\biggr|.$$ That all these expressions are equal follows from $\bigl|\sum_j\omega^{k+j}\bigr|=\bigl|\omega^k\sum_j\omega^j\bigr|=\bigl|\sum_j\omega^j\bigr|$ and from $\sum_{j<n}\omega^j=0$. It’s also obvious that the expression in (3) is a lower bound on $A(n)$. To prove that it is an upper bound, consider $$z=\sum_{j<n}x_j\omega^j$$ for some $x\in[-1,1]^n$, and put $\alpha=\overline z/|z|$ so that $|\alpha|=1$ and $|z|=z\alpha$. Then $$|z|=\sum_{j<n}\alpha x_j\omega^j=\re\sum_{j<n}\alpha x_j\omega^j=\sum_{j<n}x_j\re(\alpha\omega^j),$$ thus putting $x'_j=\sgn\re(\alpha\omega^j)$, $$|z|\le\sum_{j<n}x'_j\re(\alpha\omega^j)=\re\sum_{j<n}x'_j\alpha\omega^j\le\biggl|\sum_{j<n}x'_j\alpha\omega^j\biggr|=\biggl|\sum_{j<n}x'_j\omega^j\biggr|,$$ which is a sum as in (3) as long as $x'_j\in\{-1,+1\}$. (I leave it as an exercise to fix the issues with $x'_j=0$.)

Now we need to evaluate the given expressions. To simplify matters, first observe $$R(n)=\begin{cases}A(n),&n\not\equiv0\pmod4,\\I(n),&n\equiv0\pmod4.\end{cases}$$ Indeed, the sum in (1) is real positive, hence its real part is also its absolute value, and can serve as (3) as long as the vertical axis does not hit any $\omega^j$; in the latter case (i.e., $n\equiv0\pmod4$), the sums in (1) and (2) differ by rotation by $\pi/2$ (ignoring the points that hit the line, which do not contribute to the final expression).

For $n$ even, the geometric series formula gives $$A(n)=2\biggl|\sum_{j<n/2}\omega^j\biggr|=2\frac2{|1-\omega|}=\frac2{\sin\frac\pi n}=2\csc\frac\pi n$$ and $$I(n)=2\im\frac2{1-\omega}=2\im\frac{2(1-\overline\omega)}{|1-\omega|^2}=\frac{\sin\frac{2\pi}n}{\sin^2\frac\pi n}=\frac{2\sin\frac\pi n\cos\frac\pi n}{\sin^2\frac\pi n}=2\cot\frac\pi n.$$ For $n$ odd, symmetry along the vertical axis yields $$I(n)=\frac12I(2n)=\cot\frac\pi{2n},$$ and I omit the details of $$A(n)=2\biggl|\sum_{j<\lfloor n/2\rfloor}\omega^j\biggr|=2\frac{|1+\omega^{1/2}|}{|1-\omega|}=\frac{2\cos\frac\pi{2n}}{\sin\frac\pi n}=\csc\frac\pi{2n}.$$

All in all, we have (for all $n\ge1$):