2
$\begingroup$

Given a (finite) abelian group $G = \langle S \mid R \rangle$, has the problem of counting the number of elements which can be expressed as a word (in $S$) of length $\leq k$ been studied? If so, where can I read more about it?

The question, rephrased: How big is the set $S_k$: $$S_k = \{ g \in G \mid |g| \leq k\}$$ where $|g|$ is the minimal word size for $g$ in $S$?

Would it be simpler if we knew that $G$ is a $p$-group?

I am interested in cases where "analytical" solutions can be found, e.g. a generating function or a recurrence relation for $|S_k|$.

I think that this problem will be easy or hard depending on what $S$ is.

Improve this question
$\endgroup$
2
  • $\begingroup$ Just a remark: this is not trivial even for cyclic groups. $\endgroup$
    – Igor Rivin
    Commented Jul 29, 2015 at 21:15
  • 1
    $\begingroup$ For sufficiently large $k$, $|S_k|$ will be a polynomial function of $k$; I believe this was first shown by Khovanskii ams.org/mathscinet-getitem?mr=1209944 , although there are now several proofs (as can be seen by browsing the followup literature). $\endgroup$
    – Terry Tao
    Commented Jul 30, 2015 at 7:51

1 Answer 1

Reset to default
2
$\begingroup$

The papers of Bela Bajnok and Ryan Matzke have some answers for you, and a good summary of what is known.

Improve this answer
$\endgroup$

You must log in to answer this question.

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