Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 7 down vote accepted

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

share|cite|improve this answer
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

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.

share|cite|improve this answer
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

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.