17
$\begingroup$

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.

Improve this question
$\endgroup$
16
  • 2
    $\begingroup$ What is an example of a group and set of generators with nonunimodal growth? $\endgroup$
    – Douglas Zare
    Commented Dec 12, 2013 at 8:01
  • 2
    $\begingroup$ 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. $\endgroup$
    – Qiaochu Yuan
    Commented Dec 12, 2013 at 9:39
  • 3
    $\begingroup$ 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. $\endgroup$
    – Christian Stump
    Commented Dec 12, 2013 at 11:42
  • 4
    $\begingroup$ Should k always be the minimal number of generators? If you use the whole group as generators than trivially you have unimodality. $\endgroup$
    – Benjamin Steinberg
    Commented Dec 12, 2013 at 13:56
  • 1
    $\begingroup$ @AnthonyLabarre I couldn't wait and did the calculations by hand. For words of length 4, (which is the first case where we disagree) using "a" for one permutation and "b" for the other, I find that aaaa = bbbb = the identity, while aabb = bbaa. Then, by my count, there are 16-3 = 13 words of length 4. Is this of some help? $\endgroup$
    – David S. Newman
    Commented Feb 7, 2016 at 15:44

1 Answer 1

Reset to default
3
+50
$\begingroup$

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:

http://math.mit.edu/~rstan/pubs/pubfiles/72.pdf .

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .