Groups and generating sets

This question feels completely trivial and I am somewhat embarrassed to be asking it, but I am having a brain dead moment and failing to prove what I'm sure is a completely trivial statement about groups; I think the proof will probably be a 1- or 2-line affair.

I have a finite connected Cayley graph with $n$ vertices (or elements), with generating set $S \cup S^{-1}$ (so we assume $S$ spans the group), and I want to write a general element $x$ in terms of the generators. I wish to show that we can always write as a product of generators $x = g_1 \ldots g_m$, where $m \leq n/2$; i.e. we can always write an element as a product of generators of length at most half the order of the group.

For the theorem I am using this to prove, I also assume $S \cup S^{-1}$ is closed under conjugation, i.e. contains full conjugacy classes, but I don't think this is needed here. In case I'm actually not being stupid (though I'm 95% sure I am), the shorter the proof possible, the better.

Thanks for your help, and for putting me out of my misery!

Solution 1:

This might not be the best argument, but it seems to work. First, no nontrivial finite, connected, vertex-transitive graph has a cutpoint (nontrivial here means something like cardinality at least $3$ to avoid having to define cutpoint carefully). If it did, then every vertex would be a cutpoint, so you could inductively build an arbitrarily long finite path of distinct vertices $(v_n)$ by choosing $v_{n+1}$ to live in a connected component of $G \setminus \{v_n\}$ which does not contain any of $v_1, \ldots, v_{n-1}$ (which necessarily live in the same component, as they are a path).

So any set whose deletion disconnects the graph has cardinality at least $2$. We claim in this case that the graph-theoretic distance between any two vertices is at most one half the total number $n$ of vertices, which is enough to get what you want. Fix any vertex $v$ and put $S_i$ to equal the set of points of distance $i$ from $v$. So $S_0 = \{v\}$, $S_1$ is the neighbors of $v$, and so on. Say $r \geq 1$ is maximal such that $S_r$ is nonempty; we want to show that $r \leq n/2$.

Note that for each $i \in \{1, \ldots, r-1\}$, $S_i$ is a cutset of the graph, since any path from $v$ to a point in $S_r$ must pass through a point in $S_i$. So the cardinality of $S_i$ is at least $2$. Then $$ n = |S_0| + |S_1| + \cdots + |S_r| \geq 1 + 2(r-1) + 1, $$ from which we conclude $r \leq n/2$.

Solution 2:

I can think of another proof in your specific situation ($S\cup S^{-1}$ closed under conjugation), but I don't see how to modify it to not need that assumption, and I prefer ccc's proof.

For $g\in G$, let $|g|_S$ denote the minimum length of a word in elements of $S\cup S^{-1}$ representing $g$. Note that $S\cup S^{-1}$ being closed under conjugation implies that for any $g,h\in G$ we have $|g^{-1}hg|_S = |h|_S$.

Suppose $x\in G$ with $|x|_S = m>\frac{n}{2}$ and write $x = g_1 g_2\ldots g_m$ with $g_i\in S\cup S^{-1}$. Then the prefixes $g_1\ldots g_i$ are all distinct. Also $g_m^{-1}\ldots g_1^{-1}$ is a shortest word representing $x^{-1}$ and so the prefixes $g_m^{-1}\ldots g_i^{-1}$ are all distinct.

Now, including $1_G$, we have found $2m+1\geq n+2$ elements of $G$, and so $g_1\ldots g_i =_G g_m^{-1}\ldots g_j^{-1}$ for some $1\leq i,j <m$. But then $x = g_1 \ldots g_i g_{i+1}\ldots g_m = g_m^{-1}\ldots g_j^{-1} g_{i+1}\ldots g_m$. So $x = g_m^{-1}hg_m$, where $|h|_S \leq m - 2$. But this implies $|x|_S \leq m-2$, a contradiction.