# Are There Always Group Generators Which Give Unimodal Growth?

Suppose $G$ is a $k$-generated finite group. Is there always a set of $k$ elements which generate the group and have a unimodal counting function?

Background: The counting function, $f(n)$, is a function whose value at $n$ is the number of elements of $G$ of length $n$.

The length of an element $x$, relative to a given generating set, is the length of the shortest word, made up only of elements of the generating set, which is equal to $x$. We don't use the inverses of elements of the generating set for the purpose of determining length in this discussion.

A unimodal sequence is a finite sequence that first increases, and then decreases. A sequence $\{s_1, s_2,\ldots,s_n\}$ is unimodal if there exists a $t$ such that $s_1\leq s_2\leq\cdots\leq s_t$, and $s_t \geq s_{t+1} \geq \cdots\geq s_n$. (Weisstein, Eric W. "Unimodal Sequence." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/UnimodalSequence.html)

Discussion: As pointed out in one of the comments, taking $k$ to be the number of elements in the group will trivially give unimodal growth. The question is more interesting if one considers values of k which are less than the number of elements in the group. In a search that I made of some finite groups there was always a set of generators for which the counting function was unimodal. In fact, nonunimodal growth was a rarity. This may just be consequence of the fact that I looked only at groups with a small number of elements. I'm convinced that for commutative groups any choice of generators will yield a unimodal counting function.

Here is an example of a group with non-unimodal growth. The two generators are the permutations:

$a = \{7, 9, 2, 3, 6, 5, 1, 8, 4\}$

$b = \{6, 8, 7, 5, 2, 1, 3, 4, 9\}$

In this notation $a$ is the permutation which takes 1 into 7, 2 into 9, 3 into 2,...

The counting function for this pair of generators is:

1,2,4,8,13,21,33,44,55,75,83,80,85,65,39,27,11,2.

-
What is an example of a group and set of generators with nonunimodal growth? – Douglas Zare Dec 12 '13 at 8:01
In the special case of finite Coxeter groups with their standard generators unimodality should be well-known, e.g. for the Weyl groups it follows from hard Lefschetz applied to flag varieties. – Qiaochu Yuan Dec 12 '13 at 9:39
For a finite Coxeter group of rank $n$ (crystallographic or not) with simple generators $S$ and reflections $T$, the length generating functions are known to be $(1+q+\ldots+q^{e_1}) \cdots (1+q+\ldots+q^{e_n})$ and $(1+e_1q)\cdots(1+e_nq)$ where $e_i$ are the exponents of the group. This implies unimodality in both cases. – Christian Stump Dec 12 '13 at 11:42
Should k always be the minimal number of generators? If you use the whole group as generators than trivially you have unimodality. – Benjamin Steinberg Dec 12 '13 at 13:56
@Douglas Zare I've added an example of a group and two of its generators for which the counting function is not unimodal. – David S. Newman Dec 13 '13 at 5:31

## 1 Answer

In response to the bounty question:

By the fundamental theorem of finitely generated abelian groups, any finite $k$-generated abelian group $G$ is isomorphic to the lattice $\bigoplus_{i=1}^{k} \mathbb{Z}_{r_i}$ for prime powers $r_1, \ldots, r_k$. Then $f(n)$ is the number of solutions to $\sum_{i=1}^{k}x_{i} = n$ in the integers $0 \leq x_i \leq r_i-1$. This is equal to the coefficient of $t^n$ in the generating function $$\prod_{i=1}^{k} (1 + t + \ldots + t^{r_i -1}) .$$ Any polynomial of this form is unimodal, as (I think) Christian Stump alluded to in his comment. Stanley proves this fact in Proposition 1 of this article:

-