# Sums over products over short paths in an expander graph

Let $$\Gamma=(V,E)$$ be an undirected graph of degree $$d$$. (Say $$d$$ is a large constant and the number of vertices $$n=|V|$$ is much larger.) Let $$W_0$$ be the space of functions $$f:V\to \mathbb{C}$$ with average $$0$$. Assume $$\Gamma$$ is a strong expander graph, meaning that, for $$A$$ the adjacency operator $$Af(w) = \sum_{\{w,v\}\in E} f(v)$$ of $$\Gamma$$ restricted to $$W_0$$, all the eigenvalues of $$A$$ are considerably smaller than $$d$$. Say they are all $$\leq 2 \sqrt{d}$$, i.e., the graph is basically a Ramanujan graph.

Then, by definition, for all $$f\in W_0$$ and $$\sum_{v\in V} |f(v)|^2\leq n$$, $$\left|\sum_{v_1,v_2\in V: \{v_1,v_2\}\in E} f(v_1) \overline{f(v_2)}\right| \leq 2\sqrt{d} \cdot n.$$ Is it possible to give a nontrivial upper bound on $$\left|\sum_{v_1,v_2,v_3\in V: \{v_1,v_2\},\{v_2,v_3\}\in E} f(v_1) f(v_2) f(v_3)\right|?$$ Assume that $$f$$ is real-valued and $$|f|_\infty=1$$, if it helps.

(If yes: what about sums of longer products $$f(v_1) f(v_2) \dotsc f(v_k)$$, over $$v_1,\dotsc,v_k\in V$$ such that $$\{v_1,v_2\},\dotsc,\{v_{k-1},v_k\}\in E$$? Assume $$k$$ bounded.

If no: what sort of auxiliary hypothesis might help?)

• Let's begin with the trivial upper bound $$|\sum f(v_1)f(v_2)f(v_3)|=|\sum_{v_2} (Af)(v_2)f(v_2)(Af)(v_2)| \le \|f\|_\infty\|Af\|_2^2,$$ where $(Af)(v)=\sum_{w: \{w,v\}\in E}f(v)$. – Narutaka OZAWA Aug 18 at 3:00

I don't know your purpose, but here's some not-probably-sharp estimate that works for any $$k$$. Put $$\rho=\frac{1}{d}\|A|_{({\mathbb C}1)^\perp}\|$$ and $$\gamma$$ to be the positive root of $$t^2-\rho t -\rho=0$$. One has $$\gamma<\sqrt{2\rho}<1$$ when $$\rho<\frac{1}{2}$$. Then for any $$f$$ with $$\sum f(v)=0$$ and $$\|f\|_\infty\le1$$, one has $$\frac{1}{|V|\cdot d^{k-1}}\left|\sum_{v_1,v_2,\ldots,v_k : \{v_i,v_{i+1}\}\in E} f(v_1)\cdots f(v_k)\right| \le \gamma^k.$$
Proof. For $$D:=\mathrm{diag}\,f \in B(\ell_2V)$$ and $$B:=\frac{1}{d}AD$$, the LHS is $$\frac{1}{|V|}|\langle B^{k-1}1_V,f\rangle|$$. With respect to the orthogonal decomposition $$\ell_2V={\mathbb C}1_V\oplus ({\mathbb C}1_V)^\perp$$, one writes $$B$$ as an operator matrix $$B=\left[\begin{smallmatrix} 0 & b \\ c & d \end{smallmatrix}\right]$$, where $$\| b\|\le 1$$, $$\|c\|\le\rho$$, and $$\|d\|\le\rho$$. Hence for $$C:=\left[\begin{smallmatrix} 0 & 1 \\ \rho & \rho \end{smallmatrix}\right] \in M_2({\mathbb R})$$ with the eigenvalue $$\gamma>0$$ and the eigenvector $$\left[\begin{smallmatrix} 1 \\ \gamma \end{smallmatrix}\right]$$, one gets $$\frac{1}{|V|}|\langle B^{k-1}1_V,f\rangle| \le \left[\begin{smallmatrix} 0 & 1 \end{smallmatrix}\right] C^{k-1} \left[\begin{smallmatrix} 1 \\ 0 \end{smallmatrix}\right] \le \left[\begin{smallmatrix} 0 & 1 \end{smallmatrix}\right] C^{k-1} \left[\begin{smallmatrix} 1 \\ \gamma \end{smallmatrix}\right]=\gamma^k.$$
It's probably worth noting that the same proof shows $$\frac{1}{|V|}\sum_{v_1\in V}\left|\frac{1}{d^{k-1}}\sum_{v_2,\ldots,v_k : \{v_i,v_{i+1}\}\in E} f_1(v_1)\cdots f_k(v_k)\right|^2 \le 2\gamma^{2(k-1)}.$$