An inequality about unit vector orthogonal to $(1,1,...,1)$

Does there exist a constant $$\alpha>0$$ such that the following holds? $$\liminf_{n\to\infty}\inf_{x\in\mathbb{R}^n, \sum_{i=1}^nx_i^2=1, \sum_{i=1}^nx_i=0}\frac{\sum_{i This is related to the Laplacian of a special graph with adjacency matrix $$A_{ij}=1$$ when $$|i-j|\leq n/4$$ and 0 otherwise. This conjecture essentially says that the second smallest eigenvalue of the unnormalized Laplacian will grow linearly in $$n$$. This is definitely true if the graph is fully connected.

• Did you try approaching it via the Cheeger inequality? It shouldn't be too hard to find a good lower bound on the Cheeger constant for these graphs. Nov 25 '20 at 23:38
• @BrendanMcKay: doesn’t a lower bound on the Cheeger constant give you an upper bound on the second eigenvalue, rather than a lower bound? Nov 26 '20 at 7:53
• @AnthonyQuas Actually both. If $h$ is the Cheeger constant, $\lambda_2$ is the second smallest eigenvalue, and $\varDelta$ is the maximum degree, then $\frac12\lambda_2\le h\le \sqrt{\lambda_2(2\varDelta-\lambda_2)}$. (B. Mohar, JCT(B), 47 (1989) 274-291) Nov 26 '20 at 11:30
• @BrendanMcKay How to calculate the Cheeger constant for this graph? Nov 26 '20 at 16:27

$$\newcommand\Om\Omega\newcommand\de\delta\newcommand\tL{\tilde L}$$ It will be useful to restate the problem in probabilistic terms.

Consider the probability space $$\Om_n:=[n]^2$$ with $$P(\{(i,j)\})=1/n^2$$ for all $$(i,j)\in[n]^2$$, where $$[n]:=\{1,\dots,n\}$$. Let $$Y$$ and $$Z$$ be random variables (r.v.'s) defined on $$\Om_n$$ as follows: $$\begin{equation*} Y((i,j)):=x_i\sqrt n,\quad Z((i,j)):=x_j\sqrt n \end{equation*}$$ for all $$(i,j)\in[n]^2$$, so that $$Y$$ and $$Z$$ are iid zero-mean unit-variance r.v.'s.

It suffices to show that $$\begin{equation*} E(Y-Z)^2\,1_C\ge c \tag{-2} \end{equation*}$$ for some universal constant $$c>0$$ and all large enough $$n$$, where $$\begin{equation*} C:=\{(i,j)\in[n]^2\colon|i-j|\le n/4\}. \end{equation*}$$

Suppose that $$n\ge8$$. Partition the interval $$[n]$$ into intervals $$\de_1,\dots,\de_8$$ in $$\mathbb N$$ of lengths as equal as possible, so that for any $$k$$ and $$l$$ in $$$$ such that $$k the interval $$\de_k$$ is to the left of $$\de_l$$, and $$\begin{equation*} p_k:=P(A_k)=P(B_k)\ge p:=1/15 \tag{-1} \end{equation*}$$ for all $$k\in$$, where $$\begin{equation*} A_k:=\de_k\times[n],\quad B_k:=[n]\times\de_k. \tag{-0.5} \end{equation*}$$ Note that events $$A_k$$ and $$B_l$$ are independent for any $$k,l$$ in $$[n]$$.

The first crucial observation is that
\begin{equation*} \begin{aligned} C\supseteq D&:=\bigcup_{j=1}^4\big((A_{2j-1}\cup A_{2j})\cap(B_{2j-1}\cup B_{2j})\big) \\ &\cup\bigcup_{j=1}^3(A_{2j}\cap B_{2j+1}) \cup\bigcup_{j=1}^3(A_{2j+1}\cap B_{2j}), \end{aligned} \tag{0} \end{equation*} and all these intersections are pairwise disjoint. Therefore, letting $$\begin{equation*} I_k:=1_{A_k},\quad J_k:=1_{B_k} \tag{0.5} \end{equation*}$$ for each $$k\in$$, we get \begin{equation*} \begin{aligned} E(Y-Z)^2\,1_C\ge L&:=E(Y-Z)^2\,1_D \\ &=E(Y-Z)^2\,\Big(\sum_{j=1}^4\big((I_{2j-1}+I_{2j})(J_{2j-1}+J_{2j})\big) \\ & +\sum_{j=1}^3 I_{2j} J_{2j+1}+\sum_{j=1}^3 I_{2j+1} J_{2j}\Big). \end{aligned} \tag{1} \end{equation*} Writing now $$(Y-Z)^2=Y^2+Z^2-2YZ$$, recalling that $$Y$$ and $$Z$$ are iid r.v.'s, and introducing $$\begin{equation*} m_{2,k}:=EY^2I_k=EZ^2J_k, \quad m_{1,k}:=EYI_k=EZJ_k, \tag{1.5} \end{equation*}$$ we see that \begin{equation*} \begin{aligned} L&=\tL:=2\sum_{j=1}^4 \big((m_{2,2j-1}+m_{2,2j})(p_{2j-1}+p_{2j})-(m_{1,2j-1}+m_{1,2j})^2\big) \\ & +2\sum_{j=1}^3 \big(m_{2,2j} p_{2j+1}+m_{2,2j+1} p_{2j}-2m_{1,2j+1} m_{1,2j}\big). \end{aligned} \tag{2} \end{equation*}

The conditions that $$Y$$ is zero-mean and unit-variance imply that $$\begin{equation*} \sum_{k=1}^8 m_{1,k}=0,\quad \sum_{k=1}^8 m_{2,k}=1. \tag{3} \end{equation*}$$ Moreover, by the Cauchy--Schwarz inequality, $$\begin{equation*} m_{2,k}\ge m_{1,k}^2/p_k\quad \forall k\in. \tag{4} \end{equation*}$$ Finally, by (-1), $$\begin{equation*} p_k\in[1/15,1], \quad \sum_{k=1}^8 p_k=1. \tag{5} \end{equation*}$$

By compactness, the minimum -- say $$\tL_{\min}$$ -- of $$\tL$$ given (3)--(5) is attained. So, it remains to show that $$\tL_{\min}>0$$. Suppose otherwise: that $$\tL=\tL_{\min}\le0$$.

The second crucial point is that for any $$m_{2,1},\dots,m_{2,8},m_{1,1},\dots,m_{1,8},p_1,\dots,p_8$$ satisfying conditions (3)--(5), there exist r.v.'s $$Y$$ and $$Z$$ (defined, say, on the standard probability space over $$\Om:=[0,1]^2$$) and events $$A_1,\dots,A_8,B_1,\dots,B_8$$ such that, with the $$I_k$$'s and $$J_k$$'s still defined by (0.5), the nonuples $$(Y,I_1,\dots,I_8)$$ and $$(Z,J_1,\dots,J_8)$$ are iid, $$(A_1,\dots,A_k)$$ is a partition of $$\Om$$, $$(B_1,\dots,B_k)$$ is also a partition of $$\Om$$, $$P(A_k)=P(B_k)=p_k$$ for all $$k\in$$ (cf. (-1)), and $$Y$$ and $$Z$$ are iid zero-mean unit-variance r.v.'s such that
$$EY^2I_k=EZ^2J_k=m_{2,k}$$ and $$EYI_k=EZJ_k=m_{1,k}$$ (cf. (1.5)).

$$\Big($$Indeed, all these conditions can be satisfied e.g. as follows. Re-define here $$\de_1,\dots,\de_8$$ as non-overlapping subintervals $$[0,1]$$ of lengths $$p_1,\dots,p_8$$, and then re-define $$A_1,\dots,A_8,B_1,\dots,B_8$$ by the formula $$\begin{equation*} A_k:=\de_k\times[0,1],\quad B_k:=[0,1]\times\de_k; \end{equation*}$$ cf. (-0.5). Finally, for each $$k\in$$ partition the interval $$\de_k$$ (of length $$p_k$$) into two subintervals, say $$\eta_k$$ and $$\zeta_k$$, each of length $$p_k/2$$, and let $$\begin{equation*} Y:=\sum_{k=1}^8(u_k\,1_{\eta_k\times[0,1]}+v_k\,1_{\zeta_k\times[0,1]}), \quad Z:=\sum_{k=1}^8(u_k\,1_{[0,1]\times\eta_k}+v_k\,1_{[0,1]\times\zeta_k}), \end{equation*}$$ where $$\begin{equation*} u_k:=\frac{m_{1,k}-\sqrt{p_k m_{2,k}-m_{1,k}^2}}{p_k}, \quad v_k:=\frac{m_{1,k}+\sqrt{p_k m_{2,k}-m_{1,k}^2}}{p_k}. \end{equation*}$$ Then all the conditions on events $$A_1,\dots,A_8,B_1,\dots,B_8$$ and r.v.'s $$Y,Z$$ listed in the paragraph just above will be satisfied.$$\Big)$$

So, the minimum value of $$L$$ coincides with $$\tL_{\min}$$, which was assumed to be $$\le0$$. Since $$L\ge0$$, we may now assume without loss of generality that $$L=0$$. Looking now back at (1), we see that then $$Y=Z$$ almost surely (a.s.) on the event $$D$$, still defined as in (0).

Therefore and because $$Y$$ and $$Z$$ are iid, it follows (i) that $$Y$$ is a.s. constant on $$A_{2j-1}\cup A_{2j}$$ for each $$j\in$$ and (ii) $$Y$$ is a.s. constant on $$A_{2j}\cup A_{2j+1}$$ for each $$k\in$$. So, $$Y$$ is a.s. constant on $$\Om$$. Since $$EY=0$$, we have $$Y=0$$ a.s., which contradicts the condition that $$Y$$ is of unit variance. $$\Box$$

If one is curious, numerical minimization of $$L$$ given (3) and (4) with $$p_1=\dots=p_8=1/8$$ gives about the same result by three different methods: $$L\ge0.038060$$. So, it appears that, at least for large enough $$n$$, the best constant $$c$$ in (-2) is $$>3/100$$. Here is an image of the corresponding Mathematica notebook: • Doesn't $A_3\cap B_4$ show up twice in the union, equation (0)? Nov 25 '20 at 18:55
• The proof is very interesting! Any intuition how you came up with this? Nov 25 '20 at 22:02
• @AnthonyQuas : Thank you for your comment. This is now fixed. Nov 26 '20 at 1:28
• @neverevernever : I am glad you liked the proof. I guess the main idea was this: I had to be able to make the "chain" statement (i)--(ii) in the last paragraph of the proof. To that end, the needed "links" of the desired "chain" were added in the second line of the definition of $D$ in (0). Nov 26 '20 at 1:35