# An inequality on some pairs of orthogonal vectors

Let $$n,k\geq 1$$. Suppose that $$a_1, \ldots, a_n\in \mathbb{R}^k$$, $$b_1, \ldots, b_n\in \mathbb{R}^k$$ and $$a_i^T b_i = 0$$ for $$i=1,\dots, n$$. Is it true that $$\sum_{i=1}^n \|a_i\|_2^2 + \sum_{i=1}^n \|b_i\|_2^2 \geq \frac3n \sum_{i,j=1}^n | a_i^T b_j |$$

A matrix reformulation of the problem: Let $$A$$ be a matrix, we have (e.g. see here) $$\|A\|_{(1)} = \frac 12 \min_{A=U^TV} (\|U\|_F^2 + \|V\|_F^2)$$ where $$\|A\|_{(1)}$$ is the sum of singular values of $$A$$ (known as the trace/nuclear norm). Now, the above problem could be stated as follows

Let $$A = [a_{ij}]$$ be an $$n \times n$$ matrix with zero diagonal. Is it true $$\|A\|_{(1)} \geq \frac12\frac{3}{n} \sum_{i,j}|a_{ij}|$$

• Using $2|a^Tb|\le \|a\|^2+\|b\|^2$ you get the inequality with a factor $2/(n-1)$ instead of $3/n$. – Jochen Wengenroth Sep 28 '20 at 7:12
• @IosifPinelis Good question; I wonder it too. On the plane (i.e., when $k=2$) $3=\pi$. It looks to me like the uniform distribution on the 2-dimensional circle is the worst case scenario in any dimension, but I cannot prove it. $\sqrt{2+2\sqrt 5}$ instead of $3$ is easy. That's all I currently know. What can you prove? – fedja Sep 29 '20 at 13:04
• @fedja : I can only prove it with $4/\sqrt3$ in place of $3$ (don't have the time to type this out now). Your $\sqrt{2+2\sqrt5}$ is better. I think it could be useful if you would present your solution. – Iosif Pinelis Sep 29 '20 at 14:39
• @GiorgioMetafune As I said, just take huge $n$ and $a_i$ equidistributed on the unit circle (and $b_i$ to be orthogonal to $a_i$ of length $1$ too). By now I'm up to $1+\sqrt 3$ but it is still short even of the requested $3$, forget the optimal $\pi$. – fedja Oct 1 '20 at 18:02
• Has anyone tried thinking about this for skew-symmetric $A$? It might be easier, since then the condition of having $0$ diagonal is automatic. – David E Speyer Oct 21 '20 at 16:25

We shall prove the inequality $$\begin{equation*} \sum_{i=1}^n|a_i|^2+\sum_{i=1}^n|b_i|^2\ge\frac Cn \sum_{i,j=1}^n|a_ib_j| \tag{0} \end{equation*}$$ with $$C:=4/\sqrt3=2.309\dots$$. We use the notations $$|a|:=\|a\|_2$$ and $$ab:=a^Tb$$. Without loss of generality, the $$a_i$$ and $$b_j$$'s are nonzero vectors.

For two nonzero vectors $$a$$ and $$b$$, let $$d(a,b)\in[0,\pi/2]$$ denote the angle between the straight lines carrying the vectors $$a$$ and $$b$$. The function $$d$$ is a pseudometric, since the big circles are the geodesic lines on the 2D sphere.

For $$i,j$$ in $$[n]:=\{1,\dots,n\}$$, let then $$d_{ij}:=d(a_i,b_j)=\arccos c_{ij},\quad c_{ij}:=\frac{|a_ib_j|}{|a_i|\,|b_j|},$$ so that $$d_{ij}\in[0,\pi/2]$$ is the angle between the straight lines carrying the vectors $$a_i$$ and $$b_j$$.

Take any $$i,j,k$$ in $$[n]:=\{1,\dots,n\}$$. Since $$a_ib_i=0$$ and $$d$$ is a pseudometric, $$\begin{equation*} |d_{ki}-\pi/2|=|d_{ki}-d_{ii}|\le d(a_i,a_k)=:t \end{equation*}$$ and hence $$\begin{equation*} |a_kb_i|\le|a_k|\,|b_i|\sin t. \tag{1} \end{equation*}$$ Moreover, again because $$d$$ is a pseudometric, $$\begin{equation*} t\le d_{ij}+d_{kj}. \tag{2} \end{equation*}$$

If $$d_{ij}+d_{kj}\ge\pi/2$$, then $$d_{kj}\in[\pi/2-d_{ij},\pi/2]\subseteq[0,\pi/2]$$ and hence $$c_{ij}^2+c_{kj}^2\le\cos^2 d_{ij}+\cos^2(\pi/2-d_{ij})=1\le5/4$$, so that $$\begin{equation*} c_{ki}^2+c_{ij}^2+c_{kj}^2\le9/4. \tag{3} \end{equation*}$$ If $$d_{ij}+d_{kj}<\pi/2$$, then (2) implies $$\sin t\le\sin(d_{ij}+d_{kj})$$. So, by (1), $$\begin{equation*} c_{ki}\le c_{kj}\sqrt{1-c_{ij}^2}+c_{ij}\sqrt{1-c_{kj}^2}. \end{equation*}$$ Now the Cauchy--Schwarz inequality yields $$\begin{equation*} c_{ki}^2\le(c_{kj}^2+c_{ij}^2)(2-c_{kj}^2-c_{ij}^2). \end{equation*}$$ The latter inequality together with the conditions that $$c_{ki}^2,c_{kj}^2,c_{ij}^2$$ are in $$[0,1]$$ implies (3). Thus, (3) holds for any $$i,j,k$$.

Therefore, $$\begin{equation*} \frac94\,n^3\ge\sum_{i,j,k\in[n]}(c_{ki}^2+c_{ij}^2+c_{kj}^2) =3n\sum_{i,j\in[n]}c_{ij}^2, \end{equation*}$$ so that $$\begin{equation*} \sum_{i,j\in[n]}c_{ij}^2\le\frac34\,n^2, \end{equation*}$$ which further implies \begin{align*} \sum_{i,j\in[n]}|a_ib_j|&=\sum_{i,j\in[n]}c_{ij}|a_i|\,|b_j| \\ &\le\sqrt{\sum_{i,j\in[n]}c_{ij}^2} \sqrt{\sum_{i,j\in[n]}|a_i|^2\,|b_j|^2} \\ &=\sqrt{\sum_{i,j\in[n]}c_{ij}^2} \sqrt{\sum_{i\in[n]}|a_i|^2}\,\sqrt{\sum_{j\in[n]}|b_j|^2} \\ &\le\sqrt{\frac34\,n^2}\times\frac12\,\Big(\sum_{i\in[n]}|a_i|^2+\sum_{j\in[n]}|b_j|^2\Big), \end{align*} so that we do have (0) with $$C=4/\sqrt3$$.

I guess it is time to post the proof for the constant $$\pi$$ in the $$k=2$$ case to avoid any further controversy there. It won't hurt because it is rather clear what its boundaries are, so nobody will get stuck with a dead end idea (which might happen if I post the $$1+\sqrt 3$$ argument in higher dimension).

As Ivan observed, we need to estimate the integral $$\langle (f\mu)*K,g\mu\rangle=\int_{\mathbb T}[(f \mu)*K]\,d(g \mu)$$ where $$\mu$$ is the (let's say, normalized to $$\mu(\mathbb T)=1$$) counting measure of the set of directions of $$a_i$$, $$f$$ describes the lengths of $$a_i$$, $$g$$ describes the lengths of $$b_i$$, $$\mathbb T=\mathbb R/\mathbb Z$$ and $$K(t)=|\sin 2\pi t|$$. Since $$K$$ is real even, we can write $$f=u+v$$, $$g=u-v$$ and get $$\langle (f\mu)*K,g\mu\rangle=\langle (u\mu)*K,u\mu\rangle-\langle (v\mu)*K,v\mu\rangle$$. Now, going to the Fourier side and observing that $$\widehat K(n)=\frac 1\pi\frac{1+\cos(\pi n)}{1-n^2}$$ (i.e., $$\widehat K(0)=\frac 2\pi$$ and $$\widehat K(n)\le 0$$ for $$n\ne 0$$, $$\sum_{n\ne 0}\widehat K(n)=-\frac 2\pi$$), we get $$\langle (u\mu)*K,u\mu\rangle=\sum_n \widehat K(n)|\widehat{(u\mu)}(n)|^2\le \frac 2\pi|\widehat{(u\mu)}(0)|^2\le \frac 2\pi\int_{\mathbb T} u^2\,d\mu$$ and $$-\langle (v\mu)*K,v\mu\rangle=-\sum_n \widehat K(n)|\widehat{(v\mu)}(n)|^2\le \frac 2\pi\max_{n\ne 0}|\widehat{(v\mu)}(n)|^2\le \frac 2\pi\int_{\mathbb T} v^2\,d\mu\,,$$ so $$\langle (f\mu)*K,g\mu\rangle\le \frac 2\pi\left[\int_{\mathbb T} u^2\,d\mu+ \int_{\mathbb T} v^2\,d\mu\right]=\frac 1\pi\left[\int_{\mathbb T} f^2\,d\mu+\int_{\mathbb T} g^2\,d\mu\right]\,,$$ which is equivalent to the original inequality with constant $$\pi$$ instead of $$3$$. The example showing that $$\pi$$ is sharp has already been mentioned.

Unfortunately, this simple argument seems rather hard to generalize to higher dimensions (though I may miss some trick). However, it may be possible to reduce the general case to the 2-dimensional one somehow (though I don't know how), in which case the above proof may become useful.

• Thank you for the very nice proof. It is short, but not really "simple". – Giorgio Metafune Oct 3 '20 at 10:27
• Very interesting thank you! Do you have any references that might help one understand the proof. Also would you mind clarifying the case for equality in terms of the vectors $a_i$? – Ivan Meir Oct 3 '20 at 10:45
• Also can you generalise your proof to the case where the orthogonality condition is replaced by $a_i^Tb_i=|a_i||b_i|\cos(\theta_i)$ so the $a_i$'s and $b_i$'s differ by fixed angles rather than $\pi/2$? I was wondering what might be the equality condition in this case for $k=2$? – Ivan Meir Oct 3 '20 at 13:11
• @IvanMeir I'm not sure what references you want: the only thing I use is the identity $\int(\mu*K)d\bar\nu=\sum_n \widehat K(n)\widehat\mu(n)\overline{\widehat\nu(n)}$. The only equality case is that of uniformly distributed on the circle directions and equal lengths, so no finite $n$ configuration can attain it. As to fixed angle, no, the proof doesn't generalize to that case because a) you have two options now, so it is no longer a pure convolution and b) even if you fix the orientation, the Fourier coefficients of the kernel are no longer nice enough to run the argument. – fedja Oct 3 '20 at 14:32
• @DavidESpeyer The difficulty is that the extreme case is still the uniform distribution on the 1-dimensional circle, which, even after your parameterization, is not a uniform distribution on the full space, i.e., we cannot just reduce the game to a single "Fourier coefficient" (let's just assume that all vectors have unit length, say, so the second trick with $f,g$ is not needed). But, of course, I'll be happy to be proved wrong in my skeptical view :-) – fedja Oct 27 '20 at 0:10

$$\def\Tr{\mathrm{Tr}}\def\Mat{\mathrm{Mat}}$$I've been thinking about this problem a bunch, and I think the correct bound is $$\sum_{i,j} |A_{ij}| \leq \left( \cot \frac{\pi}{2n} \right)|A|_{(1)}.$$ As $$n \to \infty$$, we have $$\cot \tfrac{\pi}{2n} \sim \tfrac{2n}{\pi}$$, so this matches the $$\pi$$ bound that fedja proved for $$k=2$$. In particular, I will prove that this bound is correct for skew-symmetric $$A$$; almost all the work is not due to me but to a paper of Grzesik, Kral, Lovasz and Volec which was pointed out in a deleted answer by another user.

I'll write $$\sigma_1(A) \geq \sigma_2(A) \geq \cdots$$ for the singular values of $$A$$. Note that we have $$\sum |A_{ij}| = \max_{P \in \mathrm{Mat}_n(\pm 1)} \Tr(AP)$$ and $$|A|_{(1)} = \max_{Q \in O(n)} \Tr(AQ).$$ Here $$P$$ is ranging over $$\pm 1$$ matrices, and $$Q$$ is ranging over the orthogonal group.

We may replace the orthogonal group by its convex hull without changing the max. The convex hull of $$O(n)$$ is the set of matrices of operator norm $$\leq 1$$; call that $$B_1$$. So $$|A|_{(1)} = \max_{R \in B_1} \Tr(AR).$$

As a warm up, let's consider the best inequality we can prove of the form $$\sum |A_{ij}| \leq C |A|_{(1)}$$ without imposing that the diagonal is $$0$$. The answer is that the best is $$C = n$$, and that is easy to prove by elementary means, but I want to demonstrate my approach instead. So we want to find a $$C$$ such that, for every $$\pm 1$$ matrix $$P$$ and for every matrix $$A$$, we have $$\Tr(AP) \leq C \max_{R \in B_1} \Tr(AR)$$. Since $$B_1$$ is convex, this is the same as asking for $$C$$ such that $$P \in C B_1$$. In other words, we want to bound $$\sigma_1(P)$$ for $$P$$ in $$\Mat_n(\pm 1)$$. It wouldn't be hard to obtain the bound $$n$$ from here, but we move on.

Let's leave the warm up and get to the real problem. What we actually want is that $$\Tr(AP) \leq C \max_{R \in B_1} \Tr(AR)$$ for $$A$$ having zero diagonal. Thus, we only need $$\pi(P)$$ to lie in $$\pi(C B_1)$$, where $$\pi$$ is orthogonal projection onto matrices of diagonal $$0$$. In other words, we want $$P$$ to lie in $$CB_1 + \Delta$$ where $$\Delta$$ is the vector space of diagonal matrices. So we come to the following problem:

Problem 1: Find the best constant $$C_1$$ such that, for every $$\pm 1$$ matrix $$P$$, there is a diagonal matrix $$D$$ with $$\sigma_1(P+D) \leq C_1$$.

Unfortunately, it seems hard to even guess a rule for choosing the optimal $$D$$. For example, if $$P$$ is identically $$1$$, the best choice of $$D$$ is $$-\frac{n}{2} \mathrm{Id}_n$$.

Having no success here, I move on to the case of $$A$$ skew symmetric. We now can consider only skew symmetric $$P$$ (which are $$0$$ on the diagonal and $$\pm 1$$ off the diagonal.) For such a $$P$$, we now want to solve the problem:

Problem 2: Find the best constant $$C_1$$ such that, for every skew-symmetric $$\pm 1$$ matrix $$P$$, there is a symmetric matrix $$H$$ with $$\sigma_1(P+H) \leq C_1$$.

Fortunately, here I can make a little progress. It turns out that the symmetric matrix is irrelevant!

Lemma: Let $$P$$ be a skew symmetric matrix and $$H$$ a symmetric matrix. Then $$\sigma_1(P+H) \geq \sigma_1(P)$$.

Proof: Since $$P$$ is skew symmetric, it is diagonalizable over $$\mathbb{C}$$ with purely imaginary eigenvalues, and the largest such is $$i \sigma_1(P)$$. Let $$v$$ be an eigenvector with $$P v = i \sigma_1 v$$. Writing $$\dagger$$ for the conjugate transpose, normalize $$v^{\dagger} v =1$$. Then $$\sigma_1(P+H) \geq | v^{\dagger} (P+H) v | = |i \sigma_1 + v^{\dagger} H v|$$. But $$v^{\dagger} H v$$ is real, so $$|i \sigma_1 + v^{\dagger} H v| \geq \sigma_1$$. $$\square$$.

Thus, we have reduced to the problem:

Problem 3: Find the largest operator norm of any skew-symmetric $$\pm 1$$ matrix.

Another poster answered and then deleted his answer to point out that this problem is solved in Lemma 11 of Cycles of a given length in tournaments! (On reflection, I have removed this poster's name since they choose to self-delete, but I hope they will identify themselves and claim the credit; this is useful!) The largest operator norm is always achieved by the matrix which is $$1$$'s above the diagonal and $$-1$$'s below it. (As well as by the many other matrices which are conjugate to this one by signed permutation matrices.)

This matrix can be explicitly diagonalized: The eigenvectors are of the form $$(1, \zeta, \zeta^2, \ldots, \zeta^{n-1})$$ where $$\zeta = \exp(\pi i (2j+1)/(2n))$$. The corresponding eigenvalues are $$i \cot \tfrac{(2j+1) \pi}{2n}$$. In particular, the largest singular value is $$\cot \tfrac{\pi}{2n}$$, thus explaining my guess.

I am guessing this is optimal for Problem 1 as well as Problem 2, but this is based on a very weak intuition that skew symmetric choices are good, plus fedja's answer.

In the following we use the following notation: for $$a, b \in \mathbb{R}^k$$, $$a\cdot b:=a^Tb$$ and $$|a|^2:=a\cdot a$$

Let $$n,k\geq 1$$.

Define $$C(n,k)$$ to be the maximum value of $$C$$ s.t. the following inequality holds for all $$a_1, \ldots, a_n\in \mathbb{R}^k$$, $$b_1, \ldots, b_n\in \mathbb{R}^k$$ with $$a_i^T b_i = 0$$ for $$i=1,\dots, n$$: $$\sum_{i=1}^n |a_i|^2 + \sum_{i=1}^n |b_i|^2 \geq \frac{C}{n} \sum_{i,j=1}^n | a_i^T b_j |.$$

Then,

$$C(n,1) = 4$$ for $$n$$ even and $$4n^2/(n^2-1)\leq C(n,1)\leq 4$$ for $$n$$ odd.

$$C(n,2)\geq 2\sqrt{2}=2.83$$ and $$\lim_{n\rightarrow \infty} C(n,2)\leq \pi$$ as also observed by fedja.

Iosif proves in his answer that $$C(n,k)\geq 4/\sqrt {3}$$ which I also prove by a different argument.

Proof:

$$k=1$$.

$$\sum_{i,j=1}^{n}|a_ib_j|=\sum_{i=1}^{n}|a_i|\sum_{j=1}^{n}|b_j|$$ $$a_ib_i=0$$ for all $$1\leq i\leq n$$ implies that if $$A,B$$ are the number of non-zero $$a_i, b_i$$ respectively then $$A+B \leq n$$. Hence by Cauchy-Schwartz

$$\sum_{i,j=1}^{n}|a_ib_j|\leq\sqrt{AB}\sqrt{\sum_{i=1}^{n}|a_i|^2\sum_{j=1}^{n}|b_j|^2}$$

$$\leq (1/4) (A+B)(\sum_{i=1}^{n}|a_i|^2+\sum_{j=1}^{n}|b_j|^2)\leq \frac{n}{4} (\sum_{i=1}^{n}|a_i|^2+\sum_{j=1}^{n}|b_j|^2).$$

Thus we have $$\sum_{i=1}^{n}|a_i|^2+\sum_{j=1}^{n}|b_j|^2 \geq \frac{4}{n}\sum_{i,j=1}^{n}|a_ib_j|.$$

This proves that $$C(n,1)\geq 4$$.

For the upper bound for $$n$$ even we can take the $$a_i$$'s to have $$n/2$$ 1's and the rest 0's, swapping 1 and 0 for the $$b_i$$'s hence satisfying $$a_ib_i=0$$. A quick calculation shows that $$n (\sum_{i=1}^{n}|a_i|^2+\sum_{j=1}^{n}|b_j|^2 )/\sum_{i,j=1}^{n}|a_ib_j| = 4$$ in this case and hence that $$C(n,1)\geq 4$$ in this case.

For $$n$$ odd we take the $$a_i$$'s to have $$(n-1)/2$$ 1's and the rest 0's and again a quick calculation gives $$4n^2/(n^2-1)$$ for the same estimate showing that $$C(n,1)\geq 4n^2/(n^2-1)$$ in this case.

For $$k>1$$ we need a few preliminaries:

Lemma

For vectors $$a,b,c \in \mathbb{R}^k$$ with $$a \cdot b=0$$, by changing the signs of $$a$$, $$b$$ and $$c$$ we can arrange that $$b \cdot c\geq 0$$ and $$a \cdot c \geq 0$$.

Proof Clearly we can arrange that $$a \cdot b$$, $$b \cdot c$$ and $$a \cdot c$$ all have the same sign. if the common sign is positive we are done otherwise just change the sign of $$a$$ and $$b$$. $$\blacksquare$$

Consider the expression $$\sum_{i,j=1}^{n}|a_i \cdot b_j|$$. Since $$b_j\cdot a_j=0$$ we can apply the lemma to the vectors $$a_i$$, $$b_j$$ and $$a_j$$ . Hence by changing signs we can guarantee that $$b_j\cdot a_i \geq 0$$ and $$a_j\cdot a_i \geq 0$$ which shows that $$0\leq |\measuredangle a_i b_j| \leq \pi/2$$ and $$0\leq |\measuredangle a_i a_j| \leq \pi/2$$.

By the triangle inequality for arc lengths we have $$\pi \geq |\measuredangle a_i b_j|+|\measuredangle a_i a_j|\geq \pi/2$$ and thus $$\pi/2 \geq |\measuredangle a_i a_j|\geq \pi/2 -|\measuredangle a_i b_j|\geq 0$$ and since $$\sin$$ is monotonically increasing in the range $$[0, \pi/2]$$ we have $$1\geq \sin(|\measuredangle a_i a_j|) \geq \sin(\pi/2 -|\measuredangle a_i b_j|)=\cos(|\measuredangle a_i b_j|) \geq 0$$.

Thus $$|a_i \cdot b_j|=|a_i||b_j||\cos(\measuredangle a_i b_j)|\leq |a_i||b_j||\sin(\measuredangle a_i a_j)|$$ and this also holds for the original vectors $$a_i$$, $$b_j$$ and $$a_j$$.

So $$\sum_{i,j=1}^{n}|a_i \cdot b_j|\leq \sum_{i,j=1}^{n}|a_i||b_j||\sin(\measuredangle a_i a_j)|\leq \sqrt{\frac{1}{2} \sum_{i,j=1}^{n}\sin^2(\measuredangle a_i a_j)}(\sum_{i=1}^{n}|a_i|^2 + \sum_{i=1}^n |b_i|^2)$$ by Cauchy's inequality.

Hence we need to upper bound $$\sum_{i,j=1}^{n}\sin^2(\measuredangle a_i a_j)=\sum_{i,j=1}^{n}u_{ij}^2$$ with $$u_{ij}:=\sin(\measuredangle a_i a_j)$$

$$k=2$$

In this case since the points $$a_i$$ lie in the plane we can write $$a_i=|a_i|(\cos(\theta_i),\sin(\theta_i)):=|a_i| r(\theta_i)$$ giving $$u_{ij}:=\sin(\theta_i-\theta_j)$$.

Note that in this case we actually have an equality $$\sum_{i,j=1}^{n}|a_i \cdot b_j|= \sum_{i,j=1}^{n}|a_i||b_j||\sin(\theta_i-\theta_j)|$$.

Now consider the expression $$R=\sum_{i,j=1}^{n}r(2\theta_i)\cdot r(2\theta_j)$$. Clearly $$R=|\sum_{i=1}^{n}r(2\theta_i)|^2.$$ But also $$R=\sum_{i,j=1}^{n}\cos(2(\theta_i-\theta_j))=\sum_{i,j=1}^{n}(1-2\sin^2(\theta_i-\theta_j))$$

Therefore $$\sum_{i,j=1}^{n}\sin^2(\theta_i-\theta_j) = \sum_{i,j=1}^{n}1/2-R/2 =n^2/2-R/2.$$ Hence $$\sum_{i,j=1}^{n}\sin^2(\theta_i-\theta_j)\leq n^2/2$$ with equality iff $$\sum_{i=1}^{n}r(2\theta_i)=0$$ or where the centroid of the points $$r(2\theta_i)$$ is at the origin.

This gives $$\sum_{i,j=1}^{n}|a_i \cdot b_j|\leq \frac{1}{2}\sqrt{\sum_{i,j=1}^{n}\sin^2(\theta_i-\theta_j)}(\sum_{i=1}^{n}|a_i|^2 + \sum_{i=1}^n |b_i|^2)=\frac{n}{2\sqrt{2}}(\sum_{i=1}^{n}|a_i|^2 + \sum_{i=1}^n |b_i|^2)$$ implying that $$C(n,2)\geq 2\sqrt{2}$$.

For an upper bound we can take $$a_i=r(\theta_i)$$ to be uniformly distributed on the unit circle then noting as above that we have the equality $$\sum_{i,j=1}^{n}|a_i \cdot b_j|= \sum_{i,j=1}^{n}|a_i||b_j||\sin(\theta_i-\theta_j)|=\sum_{i,j=1}^{n}|\sin(2\pi i/n-2\pi j/n)|$$ and taking the limit as $$n\rightarrow \infty$$ this is equal to $$\frac{n^2}{4\pi^2}\int_0^{2\pi}\int_0^{2\pi}|\sin(x-y)|\,dx\,dy = \frac{n^2}{4\pi^2}8 \pi=\frac{2n^2}{\pi}.$$

Hence $$\lim_{n\rightarrow \infty} C(n,2)\leq \pi$$ as observed by fedja.

k>2

Here we simply observe that for any set of 3 points $$\{a_i$$, $$a_j$$, $$a_k\}$$, $$u_{ij}^2+u_{jk}^2+u_{ki}^2$$ is maximised when the points lie on a great circle with centroid at the origin. Therefore they form an equilateral triangle centred at the origin.

Hence $$u_{ij}^2+u_{jk}^2+u_{ki}^2\leq 3\sin(2\pi/3)^2=3(\sqrt{3}/2)^2=9/4.$$

Giving $$\sum_{i,j=1}^{n} u_{ij}^2\leq 3n^2/4$$ and $$C(n,k)\geq 4/\sqrt {3}$$ as proved by Iosif.

• Something is fishy. First of all, if the unit vectors $a_i$ on the plane have just $2$ directions (say $n_1$ vectors in one direction and $n_2$ in the other direction), then, clearly, the average scalar product $|a_i\cdot b_j|$ is $\frac {2n_1n_2}{n^2}\le \frac 12$, so we are rather far from the factor $2\sqrt 2$ or even $\pi$ in the original inequality: we get $4$ instead). Second, while you can arrange $a_i\cdot b_j\ge 0$, for any fixed $i,j$, you may fail to do it for all $i,j$ simultaneously. Am I missing something? – fedja Oct 2 '20 at 18:09
• It seems that you get $4$ instead of $2\sqrt 2$ when $4$ divides $n$ (there is another inequality in Cauchy Schwartz, I guess). – Giorgio Metafune Oct 2 '20 at 18:12
• @fedja Yes you are right I actually get 4 rather than $2\sqrt{2}$ in my example, embarrassing mistake. I'll update my answer. Appreciate the correction, thank you. – Ivan Meir Oct 2 '20 at 18:34
• I edited to add links. I tried to link to @fedja's observation that you mention, but I couldn't figure out which of their comments here makes that observation. – LSpice Oct 2 '20 at 19:18
• @LSpice I posted the $\pi$ bound for $k=2$. I'm still reluctant to post my arguments for higher dimensions because they give constants rather short of the requested $3$, so they may be merely dead-ends that can divert somebody else from the right path :-) – fedja Oct 2 '20 at 19:25