13
$\begingroup$

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}| $$

$\endgroup$
14
  • 1
    $\begingroup$ Using $2|a^Tb|\le \|a\|^2+\|b\|^2$ you get the inequality with a factor $2/(n-1)$ instead of $3/n$. $\endgroup$ – Jochen Wengenroth Sep 28 '20 at 7:12
  • 1
    $\begingroup$ @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? $\endgroup$ – fedja Sep 29 '20 at 13:04
  • 1
    $\begingroup$ @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. $\endgroup$ – Iosif Pinelis Sep 29 '20 at 14:39
  • 2
    $\begingroup$ @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$. $\endgroup$ – fedja Oct 1 '20 at 18:02
  • 1
    $\begingroup$ Has anyone tried thinking about this for skew-symmetric $A$? It might be easier, since then the condition of having $0$ diagonal is automatic. $\endgroup$ – David E Speyer Oct 21 '20 at 16:25
10
$\begingroup$

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$.

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Thank you for the very nice proof. It is short, but not really "simple". $\endgroup$ – Giorgio Metafune Oct 3 '20 at 10:27
  • $\begingroup$ 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$? $\endgroup$ – Ivan Meir Oct 3 '20 at 10:45
  • $\begingroup$ 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$? $\endgroup$ – Ivan Meir Oct 3 '20 at 13:11
  • 1
    $\begingroup$ @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. $\endgroup$ – fedja Oct 3 '20 at 14:32
  • 1
    $\begingroup$ @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 :-) $\endgroup$ – fedja Oct 27 '20 at 0:10
9
$\begingroup$

$\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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ 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? $\endgroup$ – fedja Oct 2 '20 at 18:09
  • $\begingroup$ It seems that you get $4$ instead of $2\sqrt 2$ when $4$ divides $n$ (there is another inequality in Cauchy Schwartz, I guess). $\endgroup$ – Giorgio Metafune Oct 2 '20 at 18:12
  • $\begingroup$ @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. $\endgroup$ – Ivan Meir Oct 2 '20 at 18:34
  • 1
    $\begingroup$ 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. $\endgroup$ – LSpice Oct 2 '20 at 19:18
  • 1
    $\begingroup$ @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 :-) $\endgroup$ – fedja Oct 2 '20 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.