Suppose $L$ is a regular language. Let’s define its automatic complexity $ac(L)$ as the minimal possible number of states of a DFA, that recognizes $L$.
Now, suppose $G$ is a finite group. $A \subset G$, $\langle A \rangle = G$. Let’s define the map $\pi: A^* \to G$ using the following recurrence:
$$\pi(\Lambda) = e$$ $$\pi(a \alpha) = a \pi(\alpha), a \in A, \alpha \in A^*$$
Now define $L(G) := \{ \alpha \in A^*| \pi(\alpha) = e\}$. It is not hard to see, that $ac(L(G)) \leq |G|$. Indeed, one can take DFA, where states correspond to the elements of $G$, $e$ is both initial and terminal states and the transition function os defined by left multiplication. However, I wonder, whether this bound is tight or not.
So, my question is:
What is the asymptotic of $max_{|G| \leq n} ac(L(G))$ as $n \to \infty$?
I think that $L(G)$ must have at least $|G|$ states, which proves that in fact $|G|$ is the smallest number possible.
Let $v,w \in A^*$ represent two distinct elements of $G$, and let $\bar{v} \in A^*$ represent the inverse of the group element represented by $v$.
Then, after reading the word $v$, the DFA accepting $L(G)$ must be in a different state from what it is after reading $w$. Since otherwise it would accept the word $v\bar{v}$, which represents the identity of $G$, but then it will also accept the word $w\bar{v}$, which does not represent the identity.
So $L(G)$ must have at least $|G|$ states.