# Prove an inequality on $l^2$ sequences over $F_2$

Denote $F_2$ the free non-abelian group on two letters $a, b$.

Note that any element in $F_2$ is just a word formed by letters from the set $\{a,b,a^{-1},b^{-1}\}$, and the group structure is given by word concatenation, i.e., $(aba^{-1})(a^2b)=abab$.

I want to prove that:

For any $\{x_g\}_{g\in F_2}\in \mathbb{C}$ with $\sum_{g\in F_2}|x_g|^2=1$, we have $|\sum_{g\in F_2}x_g\overline{x_{ag}}|^2$ or $|\sum_{g\in F_2}x_g\overline{x_{bg}}|^2\leq \frac{1}{2}$.

Here, $ag$ ( or $bg$ ) denote the concatenation of $a, g$ ( or $b, g$ )in $F_2$, and $\overline{x_g}$ is the usual conjugation of complex numbers.

Could anyone help prove this or give a counterexample?

Here are some simple observations:

Denote $S=support(x)=\{g\in F_2|x_g\neq 0\}$, and note that we have a disjoint union (or partition) $$F_2=\{e\}\cup S_a\cup S_{a^{-1}}\cup S_b\cup S_{b^{-1}}$$

where $e$ denotes the empty word in $F_2$, $S_a$ denotes the subset of all words (in reduced form) in $F_2$ that start with letter $a$, $S_{a^{-1}}, S_b, S_{b^{-1}}$ are defined similarly.

Then, suppose $aS\cap bS=\emptyset$, then it is clear

$$|\sum_{g\in F_2}x_g\overline{x_{ag}}|^2\leq (\sum_{g\in F_2}|x_g|^2)(\sum_{g\in F_2}|x_{ag}|^2)\leq \sum_{g\in F_2}|x_{ag}|^2= \sum_{g\in aS}|x_g|^2$$

$$|\sum_{g\in F_2}x_g\overline{x_{bg}}|^2\leq (\sum_{g\in F_2}|x_g|^2)(\sum_{g\in F_2}|x_{bg}|^2)\leq \sum_{g\in F_2}|x_{bg}|^2= \sum_{g\in bS}|x_g|^2$$

since $aS\cap bS=\emptyset$, $\sum_{g\in aS}|x_g|^2 +\sum_{g\in bS}|x_g|^2\leq \sum_{g\in F_2}|x_g|^2=1$, so the claim holds.

Note that if $S\subset S_a\cup S_b\cup\{e\}$, then $aS\cap bS=\emptyset$ holds by considering the first letter is a word; but in general, $aS\cup bS\neq \emptyset$ can happen, for example, if $S\subset S_{a^{-1}}$, then $aS\cup bS\neq \emptyset$ iff $S$ contains some reduced words of the form $a^{-1}ba^{-1}t, a^{-1}t$. (Using the fact $a(a^{-1}ba^{-1}t)=b(a^{-1}t)$). Similarly, you can find a result when $S\subset S_{b^{-1}}$.

Based on the above simple observations, clearly, this problem involves very complicated stuff on combinatorics and inequality estimate, I get stuck in proving the general case, i.e., $S=support(x)$ is arbitrary set of $F_2$. So I believe if the claim holds in general, then there should be some advanced theory behind it that I do not know, perhaps group cohomology method etc.

Note also that the claim can be thought as a claim on the upper norm bound gap (since it is clear that both are no bigger than 1 by Cauchy-Schwarz inequality), so maybe some known rigidity result might be helpful to this problem, but still, I have no idea how to proceed the argument.

-
When you say $x_g$, do you mean a complex number indexed by a free word? – Ian Coley Apr 1 '13 at 2:24
@ Frank, exactly! – ougao Apr 1 '13 at 2:31
And are we running over all possibilities of $g\in F_2$? – Ian Coley Apr 1 '13 at 2:33
Are your sequences $\{x_g\}_{g\in F_2}$ finite or infinite? – Boris Novikov Apr 4 '13 at 6:49
In fact, note that $F_2$ is a countable group. – ougao Apr 4 '13 at 17:03

This counterexample seems to work for $\frac{1}{2}$, and beyond:

$$x_g:=Cr^{\ell(g)}\qquad\forall g\in F_2$$

for the right choices of constants

$$C>0\qquad\mbox{and}\qquad 0\leq r<\frac{1}{\sqrt{3}}.$$

Here $\ell(g)$ denotes the word length of the element $g$, i.e. the minimal number of letters needed in the alphabet $\{a,a^{-1},b,b^{-1}\}$ to write it down.

First note that there is one element of length $0$, i.e. $1$. There are $4$ elements of length $1$, i.e. $a,a^{-1},b,b^{-1}$. And more generally, there are $4\cdot 3^{n-1}$ elements of length $n$. Indeed, writing them without allowing cancellations from left to right, there are $4$ choices for the first letter, and then only $3$ choices for each additional letter.

With $x$ defined as above, note that $0\leq 3r^2<1$ so $$\sum_{g\in F_2}|x_g|^2=C^2\sum_{g\in F_2}r^{2\ell(g)}=C^2(1+\sum_{n\geq 1}\sum_{\ell(g)=n}r^{2n})=C^2(1+\sum_{n\geq 1}4\cdot3^{n-1}r^{2n})$$ $$=C^2\left(1+\frac{4}{3}\frac{3r^2}{1-3r^2}\right)=C^2\frac{1+r^2}{1-3r^2}.$$ So

$$C:=\sqrt{\frac{1-3r^2}{1+r^2}}\quad\mbox{yields}\quad \sum_{g\in F_2}|x_g|^2=1$$

as desired.

Now we compute $$\sum_{g\in F_2}x_g\overline{x_{ag}}=C^2\left(r+\sum_{n\geq 1}\sum_{\ell(g)=n}r^{\ell(g)+\ell(ag)}\right).$$ Observe that the elements of length $n$ split into two disjoint sets:

1) $3^{n-1}$ elements starting with $a^{-1}$ and such that $\ell(ag)=n-1$.

2) $3\cdot 3^{n-1}=3^n$ elements starting with $a,b,$ or $b^{-1}$ and such that $\ell(ag)=n+1$.

Hence $$r+\sum_{n\geq 1}\sum_{\ell(g)=n}r^{\ell(g)+\ell(ag)}=r+\sum_{n\geq 1}3^{n-1}r^{2n-1}+\sum_{n\geq 1}3^{n}r^{2n+1}$$ $$=r+\left(\frac{1}{3r}+r\right)\sum_{n\geq 1}(3r^2)^n=r+\left(\frac{1}{3r}+r\right)\frac{3r^2}{1-3r^2}=\frac{2r}{1-3r^2}.$$ So $$\sum_{g\in F_2}x_g\overline{x_{ag}}=C^2 \frac{2r}{1-3r^2}=\frac{2r}{1+r^2}$$ For symmetry reasons, we find the same sum for $\sum_{g\in F_2}x_g\overline{x_{bg}}$. Therefore

$$\left|\sum_{g\in F_2}x_g\overline{x_{ag}}\right|^2= \left|\sum_{g\in F_2}x_g\overline{x_{bg}}\right|^2=\left(\frac{2r}{1+r^2} \right)^2\qquad \mbox{with}\quad 0\leq r<\frac{1}{\sqrt{3}}.$$

Now $$\lim_{r\rightarrow \frac{1}{\sqrt{3}}}\left(\frac{2r}{1+r^2} \right)^2=\frac{3}{4}.$$ And to be more precise, this rational function is increasing on $(0,1/\sqrt{3})$. So we get a counterexample to your conjecture for $r$ close enough to the left of $\frac{1}{\sqrt{3}}$. And actually, we get a stronger result: for every $\alpha < \frac{3}{4}$ there exists $x$ of norm $1$ which violates the inequalities:

$$\forall \alpha<\frac{3}{4}\qquad\exists \sum_{g\in F_2}|x_g|^2=1\qquad \left|\sum_{g\in F_2}x_g\overline{x_{ag}}\right|^2= \left|\sum_{g\in F_2}x_g\overline{x_{bg}}\right|^2>\alpha.$$

-
I wonder if you can do something like this answer, but set part of the $x_g$ values to zero, so that the amount of nonzero elements of length $n$ is $o(2^n)$ instead of $4 \cdot 3^{n-1}$. How to choose the elements so that the conclusion still holds? – Yoni Rozenshein Apr 4 '13 at 21:11
@YoniRozenshein Actually, I made an exact computation instead of an estimate, and it seems to work like that. ANd it even gives a significantly sharper estimate. Unless I made a mistake, of course... – 1015 Apr 4 '13 at 22:39
@julien This is awesome! – Norbert Apr 5 '13 at 8:11
Do you have any idea if $\frac{3}{4}$ is optimal in your last statement? – 23rd Apr 5 '13 at 13:00
@julien: Thank you for your response and +1 for your elegant argument. – 23rd Apr 5 '13 at 13:14

I want to give some explanation on Julien's choice of $x_g=Cr^{l(g)}$ based on my understanding.

Suppose we have further assumptions that $x_g's$ are all positive real numbers and $\sum_{g\in F_2}x_g^2=1$, then we want to find the maximal value of $J=\sum_{g\in F_2}x_gx_{ag}+\sum_{g\in F_2}x_gx_{bg}$.

Then, we use Lagrange multiplier method (perhaps not applicable to deal with infinite sums, anyway, let us see what happens).

Def $L=\sum_{g\in F_2}x_gx_{ag}+\sum_{g\in F_2}x_gx_{bg}+\lambda(1-\sum_{g\in F_2}x_g^2)$,

then $\frac{\partial L}{\partial x_g}=x_{ag}+x_{a^{-1}g}+x_{bg}+x_{b^{-1}g}-2\lambda x_g=0$, for all $g\in F_2$.

So $\frac{x_{ag}+x_{a^{-1}g}+x_{bg}+x_{b^{-1}g}}{x_g}$ are constant for all $g\in F_2$.

Now note for any fixed $e\neq g\in F_2$, then in the four words $\{ag, a^{-1}g, bg, b^{-1}g\}$ we has exactly three words with length $l(g)+1$, and one word with length $l(g)-1$.

So, in Julien's choice $x_g=Cr^{l(g)}$, we can check that

When $g\neq e$, $\frac{x_{ag}+x_{a^{-1}g}+x_{bg}+x_{b^{-1}g}}{x_g}=\frac{3Cr^{l(g)+1}+Cr^{l(g)-1}}{Cr^{l(g)}}=3r+\frac{1}{r}$.

When $g=e$, $\frac{x_{ag}+x_{a^{-1}g}+x_{bg}+x_{b^{-1}g}}{x_g}=4r$.

So, at least under our assumptions and the above explanation, we see that Julien's choice of $x_g$ is almost the best one, but still note that we actually want to find the maximal value $J'=(\sum_{g\in F_2}x_gx_{ag})^2+(\sum_{g\in F_2}x_gx_{bg})^2$ and $4r\neq 3r+\frac{1}{r}$ in general.

So perhaps there might be a better choice of $x_g$ to give a bigger upper bound.

Now, here are some further results. We consider $x_g=C_{l(g)}r^{l(g)}$, as usual, $l(g)$ is the word length of $g$.

Then, follow the above idea, if we assume that $\frac{x_{ag}+x_{a^{-1}g}+x_{bg}+x_{b^{-1}g}}{x_g}$ are constant $k$ for all $g\in F_2$.

Then, we would have a recurrence relation for $C_{l(g)}$, i.e., $k=\frac{4C_1r}{C_0}=\frac{3C_{n+1}r+C_{n-1}r^{-1}}{C_n}, \forall n\geq 1$.

Then under the assumption that $\sum_{g\in F_2}x_g^2=1$, which is equivalent to the relation that $\sum_{n=1}^{\infty}C_n^2r^{2n}3^{n-1}=\frac{1-C_0^2}{4}$ now, then computation shows that $I:=\sum_{g\in F_2}x_gx_{ag}=\sum_{g\in F_2}x_gx_{bg}=\frac{k}{4}$, and it is not hard (by writing down the expression for $C_{n}$ using the recurrence relation) to show that still in this case, for any fixed $\epsilon>0$, we can find $\{C_{l(g)}\}$ such that $\frac{\sqrt{3}}{2}-\epsilon \leq I$ and always $I\leq \frac{\sqrt{3}}{2}$.

So, this shows that in a slight broader situation, Julien's example is still efficient.

-

For an element $g=x_1 x_2 ... x_n$ in $F_2$, where $x_i \in \{a,b,a^{-1},b^{-1}\}$, there is a shortest expression. For example, if $g=baa^{-1}b$, the shortest expression is $bb$. We define $\ell(g)$, that is the length of the shortest expression of the word $g$.

For all $g \in F_2$, $|\ell(ag)-\ell(g)| \leq 1$ and $|\ell(bg)-\ell(g)| \leq 1$.

Let $L \in \mathbb{N}$, and let $x^L:F_2 \rightarrow \mathbb{C}$ such that $x^L_g = 1$ if $\ell(g)\leq L$ and $x^L_g=0$ if $\ell(g)>L$.

Let $E_L= \{ g \in F_2| \ell(g)\leq L\}$, $A_L= \{g \in E_L| \ell(ag)\leq L\}$, $B_L= \{g \in E_L| \ell(bg)\leq L\}$

$\sum_g |x^L_g|^2 = \# E_L$.

$\sum_g x^L_g \overline{x^L_{ag}}= \# A_L$

$\sum_g x^L_g \overline{x^L_{bg}}= \# B_L$

$\frac{\# A_L}{\# E_L} \mapsto 1$ and $\frac{\# B_L}{\# E_L} \mapsto 1$ when $L \mapsto + \infty$.

There is a $L$ such that $\frac{\# A_L}{\# E_L} > 1/\sqrt{2}$ and $\frac{\# B_L}{\# E_L} > 1/\sqrt{2}$.

So,$(\frac{1}{\sqrt{\# E_L}}x^L_g)$ is a counterexample.

-
Why does $\dfrac{\#A_L}{\#E_L}\to 1$ as $L\to\infty$? Since $\#E_{=L}\approx 3\cdot \#E_{=L-1}$ ($E_{=L}$ here of course being the set of words of length $=L$) a positive fraction of the words in $E_L$ are 'concentrated' on the words of length exactly $L$, and it certainly seems as though a positive fraction of those will have $\ell(ag)=L+1$, so I see no reason why $\#A_L$ should be asymptotic to $\#E_L$... – Steven Stadnicki Apr 4 '13 at 19:16
Yes, you are right ... – francis-jamet Apr 4 '13 at 19:21