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

Question

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<j, |i-j|\leq\frac{n}{4}}(x_i-x_j)^2}{n}\geq\alpha$$ 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.

Answer 1

$\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 $[8]$ such that $k<l$ 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[8]$, 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[8]$, 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[8]. \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[8]$ (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[8]$ 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[4]$ and (ii) $Y$ is a.s. constant on $A_{2j}\cup A_{2j+1}$ for each $k\in[3]$. 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: