4

I am reading the paper and got stuck at the formula above (5.13):

Let $n\geq 4$.

(1) why

$$\sum_{i\neq j\in[n]}\cos^2(\theta_i-\theta_j)\geq n^2/2$$

holds?

Note that this corresponds to the formula $$n^2/2\leq \|X\|_F^2$$ in the paper, where $X$ is matrix with $X_{ij}=\cos(\theta_i-\theta_j)$.

Note that $i<j$, $i>j$ are considered separatly thus there are $n^2-n$ terms in the summation.

(2) does it also hold $$\sum_{i\neq j\in[n]}\cos(\theta_i-\theta_j)\geq n^2/2$$

chloe
  • 512
  • 1
    Any assumptions on $\theta_1, \dots, \theta_n$? If not, it is already false for $n=2$: $\cos^2(\theta_1 - \theta_2) + \cos^2(\theta_2 - \theta_1)$ could be as low as $0$ if we take, say, $\theta_1=0$ and $\theta_2=\pi/2$. – Misha Lavrov Mar 22 '24 at 21:25
  • @MishaLavrov I don't think there are any assumption on $\theta$ because see on page 19, the region of $\theta$ is $[0,2\pi]^n$..... – chloe Mar 22 '24 at 21:29
  • @MishaLavrov Would it be correct for larger n? let say n>10? – chloe Mar 22 '24 at 21:29
  • Are $n$, $\theta_i$, and $\theta_j$ all just arbitrarily selected? – Dan Mar 22 '24 at 21:41
  • 1
    @Dan yes assumption is just $n$ is an integer ($\geq 4$), and $\theta_i\in[0,2\pi]$. – chloe Mar 22 '24 at 21:47
  • Does the summation count $\cos^2(\theta_i - \theta_j)$ and $\cos^2(\theta_j - \theta_i)$ separately, or as one term (in which case specifying $i < j$ or $j < i$ would be a clearer wording)? – Dan Mar 22 '24 at 22:17
  • 1
    @Dan $i<j$ and $i>j$ should be considered seperatly, thus in the summation there are $n^2-n$ terms I think. – chloe Mar 22 '24 at 22:51
  • @chloe: OK. You might want to edit your post to make that point more clear. Also the minimum value of $n$ to which it applies (because it's not true for $n = 1$ which is an empty sum, and not true for $n = 2$ because, as Misha pointed out, you can take two angles 90° apart and get a sum of 0). – Dan Mar 22 '24 at 22:56
  • 1
    @Dan Thanks, I just did – chloe Mar 22 '24 at 22:58
  • @chloe I don't think there's an alert that I've edited my answer, so I'll just point out in a comment that I've edited my answer to prove a tight lower bound. It is not quite $n^2/2$, but it is $n^2/2 - n$, which is almost as good. – Misha Lavrov Mar 23 '24 at 00:44
  • Perhaps a proof by induction could work? Start with the base case of $n = 4$. Then assume that the inequality is true for $n = k - 1$, and then show that the additional $k - 1$ terms added by $n = k$ have a sum of at least $k - \frac{1}{2}$, so that the inequality is true for $n = k$. – Dan Mar 23 '24 at 00:51

1 Answers1

3

Let's start with the unsquared sum: $$\sum_{i \ne j} \cos(\theta_i - \theta_j).$$ We can expand $\cos(\theta_i - \theta_j)$ as $\cos \theta_i \cos\theta_j + \sin\theta_i \sin\theta_j$. We'll be summing this over all pairs $(i,j)$ with $i \ne j$, but that's awkward, so let's add and then subtract the diagonal sum: $$\sum_{i=1}^n \sum_{j=1}^n \left(\cos\theta_i \cos\theta_j + \sin\theta_i \sin\theta_j\right) - \sum_{i=1}^n (\cos^2 \theta_i + \sin^2\theta_i).$$ We can rewrite this as $$\left(\sum_{i=1}^n \cos\theta_i\right)^2 + \left(\sum_{i=1}^n \sin\theta_i\right)^2 - n.$$ A lower bound on this is $-n$ (since the squared sums are nonnegative) and this can be achieved by spacing out $\theta_1, \dots, \theta_n$ symmetrically around the unit circle. To see this, think of the two squared sums here as the $x$- and $y$-coordinates of the vector sum of $(\cos \theta_i, \sin\theta_i)$ for $i=1, \dots, n$; if these vectors point in evenly spaced directions, then their sum is the zero vector!

Meanwhile, since $\cos^2 x = \frac{1+\cos 2x}{2}$, the sum with the squared cosine terms can be rewritten as follows: $$\sum_{i\ne j} \cos^2(\theta_i - \theta_j) = \sum_{i\ne j} \frac{1 + \cos(2\theta_i - 2\theta_j)}{2} = \sum_{i\ne j} \frac12 + \frac12 \sum_{i \ne j} \cos(2\theta_i - 2\theta_j).$$ The first sum simplifies to $n(n-1)/2$, and the second sum (up to the factor of $\frac12$) is the same as the sum we previously looked at. (All the angles are doubled, but that's irrelevant, since we know nothing about the angles anyway.) So we get the lower bound $$\sum_{i\ne j} \cos^2(\theta_i - \theta_j) \ge n(n-1)/2 - n/2 = n^2/2 - n.$$ This can be achieved by choosing $\theta_1, \dots, \theta_n$ so that doubling them mod $2\pi$ produces evenly spaced angles around the unit circle.

So, in summary, the lower bound of $n^2/2$ isn't quite true for any $n$, but $n^2/2 - n$ is almost as good.

Misha Lavrov
  • 142,276