Show that $(\sum_{k=1}^{n}x_{k}\cos{k})^2+(\sum_{k=1}^{n}x_{k}\sin{k})^2\le (2+\frac{n}{4})\sum_{k=1}^{n}x^2_{k}$

Question

Let $x_{1},x_{2},\cdots,x_{n}>0$, show that
$$\left(\sum_{k=1}^{n}x_{k}\cos{k}\right)^2+\left(\sum_{k=1}^{n}x_{k}\sin{k}\right)^2\le \left(2+\dfrac{n}{4}\right)\sum_{k=1}^{n}x^2_{k}$$

This question was posted some time ago at MSE. A bounty was placed on it, but no complete solution was received.
The only solution there claims to solve the problem when $n \le 10^9$.

It's easy to see that the inequality can be proved when $(2+n/4)$ is replaced by $n$ (in fact, this follows directly from Cauchy-Schwarz inequality).
Also the LHS is equal to: $\sum_{k=1}^n x_k^2 + 2\sum_{i < j} x_ix_j\cos(i - j)$.

I'm looking for a proof or any reference of this result.
Any help would be appreciated.

Answer 1

It is a bit long for a comment.

Your question is about the matrix $A=(\cos((i-j)))_{i,j=1\ldots n}$, specifically, the maximum of the quadratic form $q(x)=(Ax,x)$ on the subset $M_+$ of the unit sphere $(x,x)=1$ consisting of the vectors with positive coordinates.

Since the sphere is compact, the maximum is attained, but in general it would be attained in the closure of the set $M_+$. So in fact, we have some subset $I\subset\{1,\ldots,n\}$ where the desired point has zero coordinates, and its complement where the coordinates are positive, and the correct Lagrange multiplier problem involves the function $$ (Ax,x)-\lambda((x,x)-1)-\sum_{i\in I}\mu_i x_i . $$ Taking derivatives gives us conditions $$ Ax-\lambda x-\frac12\sum_i \mu_i e_i=0,\quad (x,x)=1, \quad x_i=0 \text{ for } i\in I, $$ or in plain language, $x$ is a unit vector that is a combination of vectors $e_i$ for $i\notin I$, and such that $Ax$, up to a vector proportional to $x$, is a combination of vectors $e_i$ for $i\in I$.

I did not follow it through fully, but I convinced myself that the maximum is indeed contained in a nontrivial boundary point of $M_+$. In fact, it is possible to describe eigenvalues and eigenvectors of $A$ in a very cute way. Consider the matrix $$ A(t)=(\cos((i-j)t))_{i,j=1\ldots n} $$ Suppose that $t$ is not a rational multiple of $\pi$. First, I claim that this matrix has $n-2$ zero eigenvalues. To show that, I shall exhibit $n-2$ linearly independent elements in the kernel (here $e_i$ are standard unit vectors of $\mathbb{R}^n$): $$ v_i=\sin(t)e_i-\sin((n-i)t)e_{n-1}+\sin((n-1-i)t)e_n,\quad i=1,\ldots,n-2 . $$ Next, I claim that two remaining eigenvalues are $$ \frac{n}{2}\pm\sum_{j=1}^k\cos((2j-1)t) $$ for even $n=2k$ and $$ \frac{n-1}{2}+\sum_{j=1}^{k-1}\cos(2jt),\quad \frac{n+1}{2}-\sum_{j=1}^{k-1}\cos(2jt) $$ for odd $n=2k+1$. Moreover, the corresponding eigenvectors are as follows $$ \sum_{j=1}^n \cos((k-j)t)e_j,\quad \sum_{j=1}^n \sin((k-j)t)e_j $$ for even $n=2k$ $$ \sum_{j=1}^n (\sin((k-j)t-\sin((k-1-j)t))e_j,\quad \sum_{j=1}^n (\sin((k-j)t+\sin((k-1-j)t))e_j $$ for odd $n=2k+1$. All these claims are checked by a rather direct calculation. Now, if the maximum of $(Ax,x)$ were attained at an interior point, we would need to look at eigenvectors, and the maximum would be given by the respective eigenvalue. Vectors of the kernel do not interest us, clearly. From the explicit formulas above, the other two eigenvectors almost immediately start having negative coordinates too (some silly exceptions for small $n$ exist).

Not sure if it is easy to finish this, I might revisit it later.

Answer 2

It is possible to prove that the inequality holds for sufficiently large $n$ with $1/4$ replaced by $1/4+\epsilon$ for any $\epsilon>0$ .

(Update - see below for a stronger result conditional on the irrationality measure of $\pi$)

In fact we have:

Theorem

For any $\epsilon>0$ and large enough $n$, depending on $\epsilon$ only, the following inequality holds for any real $a_i\geq 0$

$$|\sum_{k=1}^n a_k e^{ik}|\leq (1/2+\epsilon) \sqrt n (\sum_{k=1}^{n}a_k^2)^{1/2}.$$

Proof

We know that $$|\sum_{k=1}^n a_k e^{ik}| = e^{ i\theta}\sum_{k=1}^n a_k e^{ik}$$ for some $\theta \in [0,2\pi]$. Hence

$$|\sum_{k=1}^n a_k e^{ik}| = \sum_{k=1}^n a_k e^{i(k+\theta)}=\sum_{k=1}^n a_k\cos(k+\theta).$$

Define a function $ \cos_{+}:\mathbb{R}\to[0,1]$ by $\cos_{+}(x)=\cos(x)$ if $\cos(x)\geq 0$ and $0$ otherwise.

Then using $a_k\geq0$ and Cauchy's Theorem,

$$\sum_{k=1}^n a_k\cos(k+\theta)\leq\sum_{k=1}^n a_k\cos_+(k+\theta)\leq(\sum_{k=1}^n a_k^2)^{1/2}(\sum_{k=1}^n {\cos_+}^2(k+\theta))^{1/2}.$$

Now the equidistribution theorem says that $\{\frac{i}{2\pi}\}$ is uniformly distributed in $[0,1]$. Hence by the Riemann integral criterion for equidistribution,

$$\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^{n} f\left(s_k\right) = \frac{1}{b-a}\int_a^b f(x)\,dx$$

with $f(x)={\cos_+}^2(2\pi x+\theta)$, $s_k=\{\frac{k}{2\pi}\}$ and $a=0$, $b=1$.

In other words,

\begin{equation} \begin{split} & \lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^n {\cos_+}^2(k+\theta)=\int_0^1 {\cos_+}^2(2\pi x+\theta)\,dx =\frac{1}{2\pi}\int_{\theta}^{2\pi+\theta} {\cos_+}^2(\phi)\,d\phi \\ & =\frac{1}{2\pi}\int_{-\pi/2}^{+\pi/2} \cos^2(\phi)\,d\phi=1/4. \end{split} \end{equation}

Hence

$$\frac{|\sum_{k=1}^n a_k e^{ik}|}{\sqrt n (\sum_{k=1}^n a_k^2)^{1/2} }\leq \left(\frac{1}{n}\sum_{k=1}^n {\cos_+}^2(k+\theta)\right)^{1/2}\rightarrow 1/2 \ \text{ as } \ n\rightarrow \infty$$

and the result follows.

$\blacksquare$

In addition I can prove the following estimate, conditional on the irrationality measure of $\pi$ being less than 3:

Theorem

If the irrationality measure for $\pi$, $\mu(\pi)$ is strictly less than 3 then $$\frac{|\sum_{k=1}^n a_k e^{ik}|^2}{ \sum_{k=1}^n a_k^2 }\leq\frac{n}{4}+D.$$

for some fixed constant $D$.

Proof

We know from the above that

$$|\sum_{k=1}^n a_k e^{ik}|^2\leq (\sum_{k=1}^n a_k^2) \sum_{k=1}^n {\cos_+}^2(k+\theta)$$ for some $\theta \in [0,2\pi]$.

Also, ${\cos_+}^2(x) = (\cos^2 x+\cos x|\cos x|)/2$.

Hence $$\sum_{k=1}^n {\cos_+}^2(k+\theta)=\sum_{k=1}^n (\cos^2 (k+\theta)+\cos (k+\theta)|\cos (k+\theta)|)/2\\=\frac{1}{2}\sum_{k=1}^n \cos^2 (k+\theta)+\frac{1}{2}\sum_{k=1}^n (\cos (k+\theta)|\cos (k+\theta)|)$$.

Clearly $\sum_{k=1}^n \cos^2 (k+\theta)\leq n/2+B$ for some constant $B$ so it remains to bound the other term which is more complicated.

Let $f(x) = |\cos{(x)}| \cos{(x)}$. Here it is noted by Andreas that the expression $|\sin{(x)}| \sin{(x)}$ can be written as a Fourier series, which we modify to provide a series for $f$,

$$ f(x) = \frac{8}{\pi}\sum_{m=0}^\infty \frac{(-1)^m}{4(2m+1)-(2m+1)^3} \cos((2m+1)x). $$ Now we can sum $$ S_n = \sum_{k=1}^{n} f{(k + \phi)} = \frac{8}{\pi}\sum_{m=0}^\infty \frac{(-1)^n}{4(2m+1)-(2m+1)^3} \sum_{k=1}^{n}\cos((2m+1)(k + \phi)) $$ where $$ \sum_{k=1}^{n}\cos((2m+1)(k + \phi)) = \frac{\sin(n(m + \frac12)) \cdot \cos((1 + n + 2 \phi)(m + \frac12)) }{ \sin(m + \frac12)}. $$

Thus

$$ S_n = \frac{8}{\pi}\sum_{m=0}^\infty \frac{(-1)^n}{4(2m+1)-(2m+1)^3} \frac{\sin(n(m + \frac12)) \cdot \cos((1 + n + 2 \phi)(m + \frac12)) }{ \sin(m + \frac12)}. $$ Taking absolute values and using the triangle inequality $$ |S_n| \leq \frac{8}{\pi}\sum_{m=0}^\infty \frac{1}{|4(2m+1)-(2m+1)^3|\sin(m + \frac12)|}\\=\frac{8}{\pi}\sum_{m=0}^\infty \frac{|2\cos (m+\frac12)|}{|4(2m+1)-(2m+1)^3||\sin(2 m + 1)|} \\ \leq \frac{16}{\pi}\sum_{m=0}^\infty \frac{1}{|(2m+1)^3-4(2m+1)||\sin(2 m + 1)|} \\ =\frac{16}{3 \pi \sin 1}+\frac{16}{15 \pi \sin 3}+\frac{16}{\pi}\sum_{m=2}^\infty \frac{1}{|(2m+1)^3-4(2m+1)||\sin(2 m + 1)|} \\ \leq \frac{16}{3 \pi \sin 1}+\frac{16}{15 \pi \sin 3}+\frac{16}{\pi}\sum_{m=2}^\infty \frac{1.3}{(2m+1)^3|\sin(2 m + 1)|} $$

To complete the estimate we note that Theorem 5 of Max A. Alekseyev's paper "On convergence of the Flint Hills series" implies that if $\mu(\pi)<3$ then $\sum_{n=1}^{\infty}\frac{1}{n^3|\sin n|}$ converges, hence $\sum_{n=1}^{\infty}\frac{1}{(2n+1)^3|\sin (2n+1)|}$ converges also and we have

$$|S_n| \leq C$$ for some fixed constant $C$. Combining the two estimates we have on the assumption that $\mu(\pi)<3$,

$$\sum_{k=1}^n {\cos_+}^2(k+\theta)=\frac{1}{2}\sum_{k=1}^n \cos^2 (k+\theta)+\frac{1}{2}\sum_{k=1}^n (\cos (k+\theta)|\cos (k+\theta)|)\\ \leq n/4+(B+C)/2$$

and the result is proved. $\blacksquare$

Unfortunately although most irrational numbers have irrationality measure 2, and this is probably the true value of $\mu(\pi)$, the best upper bound for $\mu(\pi)$ is 7.103205334137 due to Doron Zeilberger and Wadim Zudilin - see here for their paper so we are a long way from being able to prove the inequality this way at least.

Answer 3

Too long for a comment. Let us consider for $X\in \mathbb S^{n-1}$, $ \langle X,(e^{i \alpha k})_{1\le k\le n}\rangle_{\mathbb C^n}. $ The question at hand is $$ \max_{X\in \mathbb S^{n-1}}\vert\langle X,(e^{i \alpha k})_{1\le k\le n}\rangle_{\mathbb C^n}\vert\le \sqrt{2+\frac n4}, \tag{$\ast$}$$ for $\alpha =1$. Of course, the above inequality does not hold when $\alpha =π$ since in that case ($\ast$) means $$ \max_{X\in \mathbb S^{n-1}}\vert\langle X,((-1)^k)_{1\le k\le n}\rangle_{\mathbb C^n}\vert\le \sqrt{2+\frac n4} $$ and choosing $ X_{2l+1}=0, X_{2l}>0, $ the lhs is $\sqrt{n/2}$. The question for a given $\alpha$ is related to the closedness in $\mathbb C^n$ of the vector $(e^{i \alpha k})_{1\le k\le n}$ to a real-valued unit vector (i.e. in $\mathbb S^{n-1}$). In fact one may write $$ \langle X,\underbrace{(e^{i \alpha k})_{1\le k\le n}}_{\mathbf e_\alpha \sqrt n}\rangle_{\mathbb C^n}=\frac14\Vert X+\mathbf e_\alpha\sqrt n\Vert^2_{\mathbb C^n}-\frac14 \Vert X-\mathbf e_\alpha\sqrt n\Vert^2_{\mathbb C^n}, $$ so that $(\ast)$ means that for $X\in \mathbb S^{n-1}$ $$ \vert\langle X,\mathbf e_\alpha \rangle_{\mathbb C^n}\vert\le\sqrt{\frac 2n+\frac 14,}\quad \text{i.e.}\quad \cos(\mathbb S^{n-1}, \mathbf e_\alpha ) \le\sqrt{\frac 2n+\frac 14}. $$ Passing to the limit when $n\rightarrow+\infty$ we would get $ \text{angle}(\mathbb S^{n-1}, \mathbf e_\alpha )\ge π/3. $

Going back to the case $\alpha =1$ the subgroup $\{e^{ik}\}_{k\in \mathbb Z}$ is dense in the unit circle (it cannot be discreet), which implies that for a given $\epsilon >0$, you can find infinitely many $k\in \mathbb Z$ such that $ \vert e^{ik}-1\vert <\epsilon. $ This is probably not enough to violate your property, since what would be needed is a fixed proportion (more that $1/4$) of integers like this, but the property at hand seems related to diophantine properties of the above subgroup.