Return to Answer

There is no generating set for which this is possible (actually this is true for any graph with an infinite connected component). Furthermore, your claim that (in non-amenable groups) such $f_n$ cannot exist if $f_n \geq 0$ is false. Here is a detailed proof.

Lemma 1: If $0 \leq v,w \in \ell^1G$ then $\|v+w\|_{\ell^1} = \|v \|_{\ell^1} + \|w\|_{\ell^1}$.

Proof: for all $g \in G$, $|v(g) + w(g)| = v(g) + w(g) = |v(g)| + |w(g)|$ this passes to the $\ell^1$-norm (by summing both sides over all $g$). $\hspace{10.5cm} \square$

Lemma 2: For any function $v \in \ell^1G$ and for any $g \in G$, $\|gv\|_{\ell^1} = \|v\|_{\ell^1}$. If further $v \geq 0$, $gv \geq 0$.

Proof: $gv$ has the same values as $v$ but permuted by the group action, so the norm is the same. The same reasoning shows that $Pv$ is positive when $v$ is. $\hspace{7.5cm} \square$

Definition: Let $P$ be the random walk operator: $P = \frac{1}{|S|} \sum_{g \in S} g$ or $P = L+I$ (where $I$ is the identity).

Lemma 3: for any $0 \leq v \in \ell^1G$, $\|Pv\|_{\ell^1} = \|v\|_{\ell^1}$ and $Pv \geq 0$.

Proof: Note that for any $g \in G$, $gv \geq 0$. $$ \begin{array}{rll} \|Pv\|_{\ell^1} &= \| \tfrac{1}{|S|} \sum_{g \in S} gv \|_{\ell^1} & = \tfrac{1}{|S|} \| \sum_{g \in S} gv \|_{\ell^1} \\ &\overset{Lemma 1}{=} \tfrac{1}{|S|} \sum_{g \in S} \| gv \|_{\ell^1} &\overset{Lemma 2}{=} \tfrac{1}{|S|} \sum_{g \in S} \| v \|_{\ell^1} \\ &= \| v \|_{\ell^1} \end{array} $$ $Pv$ is a strictly positive scalar times a sum of positive function, so it is positive. $\hspace{3cm} \square$

Notation: $P^k$ is $P$ applied $k$ times (e.g. $P^3 v= PPPv$) and $P^0 = I$.

Lemma 4: Let $f_n = \displaystyle \sum_{i=0}^n P^i v$ where $v \geq 0$ and $\|v\|_{\ell^1} =1$. Then $\|f_n\|_{\ell^1}= n+1$.

Proof: $$ \begin{array}{rll} \|f_n\|_{\ell^1} &= \displaystyle \| \sum_{i=0}^n P^i v\|_{\ell^1} & \overset{Lemma 1}{=} \displaystyle \sum_{i=0}^n \| P^i v\|_{\ell^1}\\ & \overset{Lemma 3}{=} \displaystyle \sum_{i=0}^n \|v\|_{\ell^1} & = n+1. \\ \end{array} $$

Lemma 5: Let $f_n = \displaystyle \sum_{i=0}^n P^i v$ where $v \geq 0$ and $\|v\|_{\ell^1} =1$. Then $\displaystyle \frac{\|L f_n\|_{\ell^1}}{\| f_n \|_{\ell^1}} \to 0$.

Proof: Let's compute $Lf_n$ using $L=P-I$: $$ Lf_n = \displaystyle \sum_{i=0}^n LP^i v = \displaystyle \sum_{i=0}^n (P-I)P^i v = \displaystyle \sum_{i=0}^n (P^{i+1}-P^i) v = P^{n+1}v -v $$ Now $\|Lf_n\|_{\ell^1} = \|P^{n+1}v -v\|_{\ell^1} \overset{TI}{\leq} \|P^{n+1}v\|_{\ell^1} + \|v\|_{\ell^1} = 2$ where $TI$ stands for the triangle inequality.

Using Lemma 4 $\displaystyle \frac{ \|L f_n\|_{\ell^1}}{\|f_n\|_{\ell^1}} \leq \frac{2}{n+1}$ which obviously tends to 0.

Corollary: 0 is in the spectrum of $L_1$ and the Laplacian cannot be inverted $\ell^1$.

Note the argument is true in any graph. If $v$ is supported on a finite component, then $f_n$ tends to the constant function, which is indeed in the kernel.

As a complementary remark the image of the Laplacian is not dense (in a graph with an infinite connected component). By taking $v = \delta_x$, the Dirac mass at some vertex $x$, the sequence $f_n$ above shows its image is weak$^*$ dense. It's easy to check that its image lies in $\ell^1_0X = \lbrace f \in \ell^1X \mid \sum_{x \in X} f(x) =0 \rbrace$. One can further check that $\overline{\mathrm{Im} \Delta} = \ell^1_0 X$ if and only if the graph has no non-constant bounded harmonic functions. Non-amenable groups always have non-constant bounded harmonic functions so that the (norm) closure of the image of $\Delta$ is strict subspace of $\ell^1_0 X$.

There is no generating set for which this is possible (actually this is true for any graph with an infinite connected component). Furthermore, your claim that (in non-amenable groups) such $f_n$ cannot exist if $f_n \geq 0$ is false. Here is a detailed proof.

Lemma 1: If $0 \leq v,w \in \ell^1G$ then $\|v+w\|_{\ell^1} = \|v \|_{\ell^1} + \|w\|_{\ell^1}$.

Proof: for all $g \in G$, $|v(g) + w(g)| = v(g) + w(g) = |v(g)| + |w(g)|$ this passes to the $\ell^1$-norm (by summing both sides over all $g$). $\hspace{10.5cm} \square$

Lemma 2: For any function $v \in \ell^1G$ and for any $g \in G$, $\|gv\|_{\ell^1} = \|v\|_{\ell^1}$. If further $v \geq 0$, $gv \geq 0$.

Proof: $gv$ has the same values as $v$ but permuted by the group action, so the norm is the same. The same reasoning shows that $Pv$ is positive when $v$ is. $\hspace{7.5cm} \square$

Definition: Let $P$ be the random walk operator: $P = \frac{1}{|S|} \sum_{g \in S} g$ or $P = L+I$ (where $I$ is the identity).

Lemma 3: for any $0 \leq v \in \ell^1G$, $\|Pv\|_{\ell^1} = \|v\|_{\ell^1}$ and $Pv \geq 0$.

Proof: Note that for any $g \in G$, $gv \geq 0$. $$ \begin{array}{rll} \|Pv\|_{\ell^1} &= \| \tfrac{1}{|S|} \sum_{g \in S} gv \|_{\ell^1} & = \tfrac{1}{|S|} \| \sum_{g \in S} gv \|_{\ell^1} \\ &\overset{Lemma 1}{=} \tfrac{1}{|S|} \sum_{g \in S} \| gv \|_{\ell^1} &\overset{Lemma 2}{=} \tfrac{1}{|S|} \sum_{g \in S} \| v \|_{\ell^1} \\ &= \| v \|_{\ell^1} \end{array} $$ $Pv$ is a strictly positive scalar times a sum of positive function, so it is positive. $\hspace{3cm} \square$

Notation: $P^k$ is $P$ applied $k$ times (e.g. $P^3 v= PPPv$) and $P^0 = I$.

Lemma 4: Let $f_n = \displaystyle \sum_{i=0}^n P^i v$ where $v \geq 0$ and $\|v\|_{\ell^1} =1$. Then $\|f_n\|_{\ell^1}= n+1$.

Proof: $$ \begin{array}{rll} \|f_n\|_{\ell^1} &= \displaystyle \| \sum_{i=0}^n P^i v\|_{\ell^1} & \overset{Lemma 1}{=} \displaystyle \sum_{i=0}^n \| P^i v\|_{\ell^1}\\ & \overset{Lemma 3}{=} \displaystyle \sum_{i=0}^n \|v\|_{\ell^1} & = n+1. \\ \end{array} $$

Lemma 5: Let $f_n = \displaystyle \sum_{i=0}^n P^i v$ where $v \geq 0$ and $\|v\|_{\ell^1} =1$. Then $\displaystyle \frac{\|L f_n\|_{\ell^1}}{\| f_n \|_{\ell^1}} \to 0$.

Proof: Let's compute $Lf_n$ using $L=P-I$: $$ Lf_n = \displaystyle \sum_{i=0}^n LP^i v = \displaystyle \sum_{i=0}^n (P-I)P^i v = \displaystyle \sum_{i=0}^n \big( P^{i+1}v-P^i v \big) = P^{n+1}v -v $$ Now $\|Lf_n\|_{\ell^1} = \|P^{n+1}v -v\|_{\ell^1} \overset{TI}{\leq} \|P^{n+1}v\|_{\ell^1} + \|v\|_{\ell^1} = 2$ where $TI$ stands for the triangle inequality.

Using Lemma 4 $\displaystyle \frac{ \|L f_n\|_{\ell^1}}{\|f_n\|_{\ell^1}} \leq \frac{2}{n+1}$ which obviously tends to 0.

Corollary: 0 is in the spectrum of $L_1$ and the Laplacian cannot be inverted $\ell^1$.

Note the argument is true in any graph. If $v$ is supported on a finite component, then $\tfrac{1}{n+1} f_n$ tends to the constant function, which is indeed in the kernel. Otherwise $\tfrac{1}{n+1} f_n$ tends weak$^*$ to 0 but not in norm.

As a complementary remark the image of the Laplacian is not dense (in a graph with an infinite connected component). By taking $v = \delta_x$, the Dirac mass at some vertex $x$, the sequence $f_n$ above shows its image is weak$^*$ dense. It's easy to check that its image lies in $\ell^1_0X = \lbrace f \in \ell^1X \mid \sum_{x \in X} f(x) =0 \rbrace$. One can further check that $\overline{\mathrm{Im} \Delta} = \ell^1_0 X$ if and only if the graph has no non-constant bounded harmonic functions. Non-amenable groups always have non-constant bounded harmonic functions so that the (norm) closure of the image of $\Delta$ is strict subspace of $\ell^1_0 X$.

There is no generating set for which this is possible (actually this is true for any graph with an infinite connected component).

Remark: There are 2 conventions for the Laplacian with opposite sign, so $\Delta = -L$ has positive spectrum (in $\ell^2$) and $L$ has negative spectrum.

Let $I$ be the identity. Let $P$ be the random walk operator, $\Delta = I-P$ so $P = I+L$, or, more simply $P = \displaystyle \frac{1}{|S|} \sum_{g \in S} g$.

Denote by $P^i$ the $i^\text{th}$ iterate of $P$ (for example: $P^2 = P P$) and $P^0 = I$)

Let $g_n = \displaystyle \sum_{i=0}^n P^n \delta_x$ where $\delta_x$ is a Dirac mass at some vertex $x$. Since $P^i \delta_x$ is the probability distribution of the random walk at time $i$, $\|P^i\delta_x\|_{\ell^1} =1$. (In fact, $P$ preserves the $\ell^1$-norm of positive fucntions.) Next, since all the $P^i\delta_x$ are positive functions, their norm add up in $\ell^1$: hence $\| g_n\|_{\ell^1}= n+1$

On the other hand, $L = P-I$ and so $$ L g_n = P\bigg( \sum_{i=0}^n P^n \delta_x\bigg) - \bigg( \sum_{i=0}^n P^n \delta_x\bigg) = P^{n+1} \delta_x -\delta_x $$ So $\| L g_n\|_{\ell^1} \leq \|\delta_x\|_{\ell^1} + \| P^{n+1} \delta_x\|_{\ell^1} = 2$ by the triangle inequality.

This shows that $\displaystyle \frac{ \|L g_n\|_{\ell^1}}{\|g_n\|_{\ell^1}} \leq \frac{2}{n+1}$ which obviously tends to 0. So 0 is in the spectrum and the Laplacian cannot be inverted $\ell^1$.

Note the argument is true in any graph (without finite connected components).

Also the image of the Laplacian is not dense (it is weak$^*$ dense as the sequence $g_n$ above shows). It's easy to check that its image lies in $\ell^1_0X = \lbrace f \in \ell^1X \mid \sum_{x \in X} f(x) =0 \rbrace$. One can further check that $\overline{\mathrm{Im} \Delta} = \ell^1_0 X$ if and only if the graph has no non-constant bounded harmonic functions. Non-amenable groups always have non-constant bounded harmonic functions so that the closure of the image of $\Delta$ is strict subspace of $\ell^1_0 X$.

There is no generating set for which this is possible (actually this is true for any graph with an infinite connected component). Furthermore, your claim that (in non-amenable groups) such $f_n$ cannot exist if $f_n \geq 0$ is false. Here is a detailed proof.

Lemma 1: If $0 \leq v,w \in \ell^1G$ then $\|v+w\|_{\ell^1} = \|v \|_{\ell^1} + \|w\|_{\ell^1}$.

Proof: for all $g \in G$, $|v(g) + w(g)| = v(g) + w(g) = |v(g)| + |w(g)|$ this passes to the $\ell^1$-norm (by summing both sides over all $g$). $\hspace{10.5cm} \square$

Lemma 2: For any function $v \in \ell^1G$ and for any $g \in G$, $\|gv\|_{\ell^1} = \|v\|_{\ell^1}$. If further $v \geq 0$, $gv \geq 0$.

Proof: $gv$ has the same values as $v$ but permuted by the group action, so the norm is the same. The same reasoning shows that $Pv$ is positive when $v$ is. $\hspace{7.5cm} \square$

Definition: Let $P$ be the random walk operator: $P = \frac{1}{|S|} \sum_{g \in S} g$ or $P = L+I$ (where $I$ is the identity).

Lemma 3: for any $0 \leq v \in \ell^1G$, $\|Pv\|_{\ell^1} = \|v\|_{\ell^1}$ and $Pv \geq 0$.

Proof: Note that for any $g \in G$, $gv \geq 0$. $$ \begin{array}{rll} \|Pv\|_{\ell^1} &= \| \tfrac{1}{|S|} \sum_{g \in S} gv \|_{\ell^1} & = \tfrac{1}{|S|} \| \sum_{g \in S} gv \|_{\ell^1} \\ &\overset{Lemma 1}{=} \tfrac{1}{|S|} \sum_{g \in S} \| gv \|_{\ell^1} &\overset{Lemma 2}{=} \tfrac{1}{|S|} \sum_{g \in S} \| v \|_{\ell^1} \\ &= \| v \|_{\ell^1} \end{array} $$ $Pv$ is a strictly positive scalar times a sum of positive function, so it is positive. $\hspace{3cm} \square$

Notation: $P^k$ is $P$ applied $k$ times (e.g. $P^3 v= PPPv$) and $P^0 = I$.

Lemma 4: Let $f_n = \displaystyle \sum_{i=0}^n P^i v$ where $v \geq 0$ and $\|v\|_{\ell^1} =1$. Then $\|f_n\|_{\ell^1}= n+1$.

Proof: $$ \begin{array}{rll} \|f_n\|_{\ell^1} &= \displaystyle \| \sum_{i=0}^n P^i v\|_{\ell^1} & \overset{Lemma 1}{=} \displaystyle \sum_{i=0}^n \| P^i v\|_{\ell^1}\\ & \overset{Lemma 3}{=} \displaystyle \sum_{i=0}^n \|v\|_{\ell^1} & = n+1. \\ \end{array} $$

Lemma 5: Let $f_n = \displaystyle \sum_{i=0}^n P^i v$ where $v \geq 0$ and $\|v\|_{\ell^1} =1$. Then $\displaystyle \frac{\|L f_n\|_{\ell^1}}{\| f_n \|_{\ell^1}} \to 0$.

Proof: Let's compute $Lf_n$ using $L=P-I$: $$ Lf_n = \displaystyle \sum_{i=0}^n LP^i v = \displaystyle \sum_{i=0}^n (P-I)P^i v = \displaystyle \sum_{i=0}^n (P^{i+1}-P^i) v = P^{n+1}v -v $$ Now $\|Lf_n\|_{\ell^1} = \|P^{n+1}v -v\|_{\ell^1} \overset{TI}{\leq} \|P^{n+1}v\|_{\ell^1} + \|v\|_{\ell^1} = 2$ where $TI$ stands for the triangle inequality.

Using Lemma 4 $\displaystyle \frac{ \|L f_n\|_{\ell^1}}{\|f_n\|_{\ell^1}} \leq \frac{2}{n+1}$ which obviously tends to 0.

Corollary: 0 is in the spectrum of $L_1$ and the Laplacian cannot be inverted $\ell^1$.

Note the argument is true in any graph. If $v$ is supported on a finite component, then $f_n$ tends to the constant function, which is indeed in the kernel.

As a complementary remark the image of the Laplacian is not dense (in a graph with an infinite connected component). By taking $v = \delta_x$, the Dirac mass at some vertex $x$, the sequence $f_n$ above shows its image is weak$^*$ dense. It's easy to check that its image lies in $\ell^1_0X = \lbrace f \in \ell^1X \mid \sum_{x \in X} f(x) =0 \rbrace$. One can further check that $\overline{\mathrm{Im} \Delta} = \ell^1_0 X$ if and only if the graph has no non-constant bounded harmonic functions. Non-amenable groups always have non-constant bounded harmonic functions so that the (norm) closure of the image of $\Delta$ is strict subspace of $\ell^1_0 X$.

There is no generating set for which this is possible (actually this is true for any graph with an infinite connected component).

The functions $g_n$ which show 0 are in the spectrum are constructed by trying to invert the Laplacian naively

Remark: My convention for the Laplacian seem to have the opposite sign as yours, so I'm using $\Delta = -L$

Let $P$ be the random walk operator, $P = I- \Delta$ or $P = \frac{1}{|S|} \sum_{g \in S} g$.

Let $g_n = \sum_{i=0}^n P^n \delta_x$ where $\delta_x$ is a Dirac mass at some vertex $x$. Since $P^i \delta_x$ is the probability distribution of the random walk at time $i$, $\|P^i\delta_x\|_{\ell^1}$. These are positive functions, so their norm add up in $\ell^1$: hence $\| g_n\|_{\ell^1}= n+1$

On the other hand, $\Delta = I-P$ so and $\Delta g_n = \delta_x - P^{n+1} \delta_x$. So $\| \Delta g_n\|_{\ell^1} \leq \|\delta_x\|_{\ell^1} + \| P^{n+1} \delta_x\|_{\ell^1} = 2$ by the triangle inequality.

This shows that $\displaystyle \frac{ \|\Delta g_n\|_{\ell^1}}{\|g_n\|_{\ell^1}} \leq \frac{2}{n+1}$ which obviously tends to 0. So 0 is in the spectrum and the Laplacian cannot be inverted $\ell^1$.

Note the argument is true in any graph (without finite connected components).

Also the image of the Laplacian is not dense (it is weak$^*$ dense as the sequence $g_n$ above shows).

It's easy to check that its image lies in $\ell^1_0X = \lbrace f \in \ell^1X \mid \sum_{x \in X} f(x) =0 \rbrace$.

One can further check that $\overline{\mathrm{Im} \Delta} = \ell^1_0 X$ if and only if the graph has no non-constant bounded harmonic functions.

Non-amenable groups always have non-constant bounded harmonic functions so that the closure of the image of $\Delta$ is strict subspace of $\ell^1_0 X$.

There is no generating set for which this is possible (actually this is true for any graph with an infinite connected component).

Remark: There are 2 conventions for the Laplacian with opposite sign, so $\Delta = -L$ has positive spectrum (in $\ell^2$) and $L$ has negative spectrum.

Let $I$ be the identity. Let $P$ be the random walk operator, $\Delta = I-P$ so $P = I+L$, or, more simply $P = \displaystyle \frac{1}{|S|} \sum_{g \in S} g$.

Denote by $P^i$ the $i^\text{th}$ iterate of $P$ (for example: $P^2 = P P$) and $P^0 = I$)

Let $g_n = \displaystyle \sum_{i=0}^n P^n \delta_x$ where $\delta_x$ is a Dirac mass at some vertex $x$. Since $P^i \delta_x$ is the probability distribution of the random walk at time $i$, $\|P^i\delta_x\|_{\ell^1} =1$. (In fact, $P$ preserves the $\ell^1$-norm of positive fucntions.) Next, since all the $P^i\delta_x$ are positive functions, their norm add up in $\ell^1$: hence $\| g_n\|_{\ell^1}= n+1$

On the other hand, $L = P-I$ and so $$ L g_n = P\bigg( \sum_{i=0}^n P^n \delta_x\bigg) - \bigg( \sum_{i=0}^n P^n \delta_x\bigg) = P^{n+1} \delta_x -\delta_x $$ So $\| L g_n\|_{\ell^1} \leq \|\delta_x\|_{\ell^1} + \| P^{n+1} \delta_x\|_{\ell^1} = 2$ by the triangle inequality.

This shows that $\displaystyle \frac{ \|L g_n\|_{\ell^1}}{\|g_n\|_{\ell^1}} \leq \frac{2}{n+1}$ which obviously tends to 0. So 0 is in the spectrum and the Laplacian cannot be inverted $\ell^1$.

Note the argument is true in any graph (without finite connected components).

Also the image of the Laplacian is not dense (it is weak$^*$ dense as the sequence $g_n$ above shows). It's easy to check that its image lies in $\ell^1_0X = \lbrace f \in \ell^1X \mid \sum_{x \in X} f(x) =0 \rbrace$. One can further check that $\overline{\mathrm{Im} \Delta} = \ell^1_0 X$ if and only if the graph has no non-constant bounded harmonic functions. Non-amenable groups always have non-constant bounded harmonic functions so that the closure of the image of $\Delta$ is strict subspace of $\ell^1_0 X$.