My broad question is regarding the lengths of (reduced) words in a subgroup of a free group.

As motivation, consider the free group $Gp(S)$ where $|S|=n$, that is, a free group of rank $n$. Let $S=\{a_1,a_2,\dots,a_n\}$. Now take a subgroup $N$ of $Gp(S)$ of index $2$. It is automatically normal, so is the kernel of a surjective homomorphism from $Gp(S)$ to $C_2=\{1,-1\}$. This means that every subgroup $N$ of index $2$ can be obtained by starting with a function from $S$ to $\{1,-1\}$ and extending it to a homomorphism of $Gp(S)$.

While any such subgroup $N$ has index $2$ (which intuitively can be thought of as roughly half the elements of $Gp(S)$ are in $N$), this intuition does not hold if we work with lengths of reduced words. That is, it is not true that for any given length $k$, the number of reduced words of length $k$ contained in $N$ is exactly half the total number of reduced words of length $k$ in $Gp(S)$. For instance, we could map $a_1 \to -1$ and $a_j \to 1$ for every $2 \leq j \leq n$, and the normal subgroup this gives us, while of index $2$, is certainly not "balanced" with respect to each length.

And as MTyson pointed out in his comment, this is not even possible in most cases. For instance, consider $S=\{a_1,a_2\}$, then the mapping $a_1 \to 1$ and $a_2 \to -1$ would map $8$ reduced words of length $2$ to $-1$, and $4$ of them to $1$. More generally, suppose $S=\{a_1,a_2,\dots,a_n\}$ with even $n$. Then on mapping half the number of generators to $-1$ (and the remaining to $1$), we get, for odd $k$, an equal number of reduced words of length $k$ mapped to $1$ and to $-1$. For even $k$, there are slightly more reduced words of length $k$ mapped to $-1$ than to $1$, the precise values of which can be calculated inductively through straightforward combinatorial arguments.

My question is whether, and how, this approach can be extended to subgroups of $Gp(S)$. Suppose $H$ is a normal subgroup of $Gp(S)$ of index $m$. Then $H$ itself is a free group (Neilsen's theorem) of rank $mn-m+1$, and so has a basis (of reduced words over alphabet $S$) of cardinality $mn-n+1$.

Again, consider an index $2$ subgroup $N$ of $Gp(S)$. The intersection $N \cap H$ is either trivially the whole of $H$ (which we shall ignore), or is an index $2$ subgroup of the group $H$. We can now ask the same question as before for the index $2$ subgroup $N \cap H$ in $H$.

Given the normal subgroup $H$ (using a basis), does there exist an index $2$ subgroup $N$ of $Gp(S)$ such that the number of length $k$ reduced words in $N \cap H$ is roughly half the number of length $k$ reduced words in $H$?

The main difficulty here arises from the fact that length is still with respect to alphabet $S$ (even though $H$ is itself a free group), and so there can be cancellations making matters difficult. It is hard enough to count the number of reduced words of a given length in $H$ (the word problem), but that is not what we care about (or so I believe)! We just want to "bisect" $H$ at each length using an index $2$ subgroup.

The next natural followup question is about quantification: what can be provably achieved?

Given the normal subgroup $H$ (using a basis) and an index $2$ subgroup $N$, let $|N \cap H|_{k}$ and $|H|_{k}$ denote the number of reduced words of length exactly $k$ in $N \cap H$ and $H$ respectively. We are then interested in $N$ that minimizes (asymptotically as a function of $n,m,k$) $$\left| \frac{1}{2} - \frac{|N \cap H|_{k}}{|H|_{k}} \right|$$ for a fixed $H$.

While this is a rather broad question, I'd be satisfied even with pointers to relevant tools and references that could possibly help. As of now, I am just staring at the wall without ideas on where to even begin.

EDIT: MTyson points out that we could ask the same question for a more restricted class of words: cyclically reduced words, and modulo cyclic permutations. Exact balance seems achievable at least for some simple hand-written examples.

  • 1
    $\begingroup$ Under $a_1\mapsto 1$ and $a_2 \mapsto -1$ there are $4$ reduced words in $N=\mathrm{ker}(Gp(\{a_1,a_2\})\to \{-1,1\})$ of length $2$ and $8$ reduced words of length $2$ outside of it. Should "reduced words" be "cyclically reduced words up to cyclic permutation"? $\endgroup$ – MTyson Aug 21 '17 at 16:35
  • $\begingroup$ @MTyson You're right, not sure how I overlooked this. Maybe cyclically reduced is more appropriate. I'll check again before updating the question. Thanks. $\endgroup$ – BharatRam Aug 21 '17 at 16:51
  • $\begingroup$ @MTyson Hey, I have edited the question in light of your comment. I am still interested mainly in reduced words, though as you pointed out, one cannot hope for perfect balance even in the trivial, unrestricted (free) case. Do have a look, I'd love to hear your thoughts. Thanks again. $\endgroup$ – BharatRam Aug 23 '17 at 16:22
  • $\begingroup$ The answer is clearly no if $H$ is the kernel of the natural map $S \to \mathbb F_2^n$, and is also know if the the image of the induced map $H \to S \to \mathbb F_2^n$ is generated by a single nontrivial element of order two where that nontrivial element has odd word length. $\endgroup$ – Will Sawin Aug 24 '17 at 9:51
  • $\begingroup$ @WillSawin An exact balancing may not be possible in most cases. But trivial degeneracies apart, is there some intuition regarding what the best balance possible could be? Or at least some nontrivial bounds that are achievable? I am hoping for some Riemann hypothesis type error bound of $O(n^{k/2})$, though thats just my vague intuition. $\endgroup$ – BharatRam Aug 29 '17 at 12:08

So the right way to look at this is in terms of walks on graphs. Let $G = Gp(S)$, then the Cayley graph of $G/N$ is a $2n$-regular graph on $|G/N|$ vertices. The number of words of length $k$ in $N$ is the same as the number of paths of length $k$ from some fixed point in this graph to itself, where we demand the path never take the same edge in opposite directions in consecutive steps. This is given by

$$ \frac{ (\sqrt{n-1})^k }{|G/N| } \operatorname{tr}\left( U_k \left(\frac{A}{2 \sqrt{n-1}}\right)\right)$$

where $A$ is the adjaceny matrix of the Cayley graph and $U_k$ are the Chebyshev polynomials of the second kind. (This can be proved by letting $A_k$ be the matrix whose $i,j$ entry counts backtracking-free paths of length $k$ from $i$ to $j$ and showing that the $A_k$ satisfy the recurrence relation of the Chebyshev polynoimals in $A$.

If $N'$ is an index $2$ subgroup of $N$, the same count for $N'$ is

$$ \frac{ (\sqrt{n-1})^k }{|G/N'| } \operatorname{tr}\left( U_k \left(\frac{B}{2 \sqrt{n-1}}\right)\right)$$

where $B$ is the adjacency matrix of the Cayley graph of $G/N'$.

You want to know the difference between the number of words of length $k$ in $N'$ and the number in $N$ but not in $N'$, which is twice the second count minus the first. If you express this as a sum over eigenvalues, this cancels all the eigenvalues appearing in $A$, as they also appear in $B$, leaving only the "new" spectrum of $B$.

As soon as either $G/N'$ is not bipartite or $G/N$ is bipartite, the new spectrum will be contained in the interval $(-2n,2n)$ and therefore, because it is finite, bounded away from $N$, giving a power-savings bound for the error term. This is a group-theoretic nondegeneracy condition which says that the unique isomorphism $N/N' \to \mathbb Z/2$ is not equal on $N$ to the word length mod $2$.

If you want the sharpest possible bound, you need the Ramanujan bound: If all the new spectrum of $B$ is in $[-2\sqrt{n-1}, 2\sqrt{n-1}]$, then the Chebyshev polynomial will be bounded by $k+1$, so the difference between the number of length $k$ words in $N'$ and not in $N'$ will be bounded by $(k+1) (\sqrt{n-1})^k$.

If we allow $N'$ to be an arbitrary index $2$ subgroup, and not just $N \cap H$ for an index two subgroup $H$ of $G$, then the Cayley graph of $G/N'$ may be an arbitrary $2$-covering of the Cayley graph of $G/N$. The existence of a $2$-covering with all new eigenvalues in that interval was established by Marcus, Spielman, and Srivastava in 2013 (https://arxiv.org/abs/1304.4132), under the additional assumption that $G/N$ is bipartite (i.e. that $N$ is contained in the subgroup of even length words).

I don't know of any approach to get a sharp bound, or nearly sharp bound, without using their result, but in many cases it might be possible to get some explicit bound on the power savings by controlling the largest eigenvalue.

| cite | improve this answer | |
  • $\begingroup$ Thanks for the write-up. So MSS13 gives an existence result for a signing with small (Ramanujan) spectral radius, and this is equivalent to tight balance in our context. You seem to have worked on a k-cover generalization of their result. Broadly, what do you think is the obstacle in derandomizing the result? As in, do you think it is possible to replicate the original Lubotzky-Phillips-Sarnak type of argument in this special context? Sorry if I'm being vague, but just confused and curious how the Riemann hypothesis, cayley graphs and groups all fit together. $\endgroup$ – BharatRam Aug 29 '17 at 17:09
  • $\begingroup$ @BharatRam The issue is that both the LPS argument and the MSS argument are very specialized. LPS applies only to Cayley graphs of arithmetic groups (though it has since been generalized to more arithmetic groups) and MSS applies only to situations where you have freedom to make many choices independently, and each one is small. There is just a wide gap between these and no current way to "connect them". The underlying issue is that Ramanujan is a very strong bound. We have a lot more ideas to prove some bound on the eigenvalues than we have to prove the strongest possible bound. $\endgroup$ – Will Sawin Aug 29 '17 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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