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

Solution 1:

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.$$