The number of polynomials on a finite group

Question

A function $f:X\to X$ on a group $X$ is called a polynomial if there exist $n\in\mathbb N=\{1,2,3,\dots\}$ and elements $a_0,a_1,\dots,a_n\in X$ such that $f(x)=a_0xa_1x\cdots xa_n$ for all $x\in X$. The smallest possible number $n$ in this representation is called the degree of the polynomial $f$ and is denoted by $\deg(f)$.

Let $\mathrm{Poly}(X)$ be the set of all polynomials on a group $X$.

In fact, $\mathrm{Poly}(X)$ is a submonoid of the monoid $X^X$ of all self-maps of $X$, endowed with the operation of composition of functions.

So, $|\mathrm{Poly}(X)|\le|X^X|=|X|^{|X|}$.

If the group $X$ is commutative, then each polynomial is of the form $f(x)=ax^n$ for some $a\in X$ and $n\in\mathbb N$. This implies that the number of semigroup polynomials on a finite Abelian group $X$ is equal to $|X|\cdot\exp(X)\le |X|^2$ where $\exp(X)=\min\{n\in\mathbb N:\forall x\in X\; (x^n=1)\}$.

Question 1. Is any reasonable upper bound on the number of polynomials on a finite group $X$? For example, is $|\mathrm{Poly}(X)|=o(|X|^{|X|})$?

Each polynomial $f:X\to X$ on a finite Abelian group $X$ has degree $\deg(f)\le\exp(X)$.

Question 2. Is $\deg(f)\le\exp(X)$ for any polynomial $f:X\to X$ on a finite group $X$?

Remark 2. The affirmative answer to Question 2 would imply that $$|\mathrm{Poly}(X)|\le \sum_{n=1}^{\exp(X)}|X|^{k+1}=\frac{|X|^{\exp(X)+2}-|X|^2}{|X|-1}.$$

Remark 3. Finite groups $X$ with $|\mathrm{Poly}(X)|=|X|\cdot\exp(X)$ are characterized in the following theorem.

Theorem. A finite group $X$ has $|\mathrm{Poly}(X)|=|X|\cdot\exp(X)$ if and only if $X$ is either commutative or is isomorphic to $Q_8\times A$ for some nontrivial commutative group $A$ of odd order.

Proof. To prove the ``if'' part, assume that $X$ is either commutative or $X$ is isomorphic to $Q_8\times A$ for some nontrivial commutative group $A$ of odd order. If $X$ is commutative, then the equality $|\mathrm{Poly}(X)|=|X|\cdot\exp(X)$ is clear.

Now assume that $X=Q_8\times A$ for some nontrivial commutative group $A$ of odd order. GAP-calculations of Peter Taylor show that the group $Q_8$ has exactly 32 polynomials of each degree $k\in\{1,2,3,4\}$. This implies that $$|\mathrm{Poly}(Q_8\times A)|=32\cdot|\mathrm{Poly}(A)|=32\cdot |A|\cdot\exp(A)=4\cdot|X|\cdot\exp(A)=|X|\cdot\exp(X).$$

To prove the ``only if'' part, assume that $X$ is a finite non-commutative group with $|\mathrm{Poly}(X)|=|X|\cdot\exp(X)$. For every $a\in X$ and $n\in\mathbb N$, consider the polynomial $p_{a,n}(x)=ax^n$. The definition of $\exp(X)$ implies that the set $\mathrm{Pol}(X):=\{p_{a,n}:a\in X,\;1\le n\le \exp(X)\}$ has cardinality $|X|\cdot\exp(X)$ and hence coincides with the set $\mathrm{Poly}(X)$. So, for any $a\in X$ there exists $n\le\exp(X)$ such that $axa^{-1}=x^n$ for all $x\in X$. This implies that every subgroup of $X$ is normal, so $X$ is a Dedekind group. By the classical Dedekind result, $X$ is isomorphic to the product $Q_8\times A\times B$ where $A$ is a Abelian group of odd order and $B$ is a Boolean group, i.e., a group of exponent $\exp(B)\le 2$.

If the group $A$ and $B$ is trivial, then $|\mathrm{Poly}(X)|=|\mathrm{Poly}(Q_8)|=128\ne |X|\cdot\exp(X)=32$.

Next, assume that the group $A$ is trivial and $B$ is not trivial. Then $|\mathrm{Poly}(B)|=|\{a,ax:a\in B\}|=2|B|$. GAP-calculations of Peter Taylor show that the group $Q_8$ has exactly 32 polynomials of each degree $k\in\{1,2,3,4\}$. In particular, $Q_8$ has exactly 64 polynomials of even degree and 64 polynomials of odd degree. This implies that $|\mathrm{Poly}(X)|=64\cdot 2|B|=16|Q_8\times B|=16|X|\ne 4|X|=|X|\cdot\exp(X)=|\mathrm{Poly}(X)|$. This contradiction shows that the group $A$ is nontrivial.

Taking into account that the group $Q_8$ has exactly 32 polynomials of each degree $k\in\{1,2,3,4\}$, we conclude that $$|X|\cdot\exp(X)=|\mathrm{Poly}(X)|=|\mathrm{Poly}(Q_8\times A\times B|=32\times|\mathrm{Poly}(A\times B)|=32\times |A\times B|\times \exp(A\times B)=4\times|Q_8\times A\times B|\times \exp(A\times B)=4\cdot |X|\cdot\exp(A\times B)$$ and hence $\exp(Q_8\times A\times B)=\exp(X)=4\exp(A\times B)$. Since $\exp(Q_8\times A\times B)=4\exp(A),$ this implies that the Boolean group $B$ is trivial and hence $X=Q_8\times A$. $\square$

Answer 1

$\DeclareMathOperator\Poly{Poly}$Proposition. If $G$ is a simple non-abelian finite group, then $\Poly(G)=G^G$.

(Edit: this observation appears as the main therorem in this paper by Maurer and Rhodes, Proc. AMS 1965. See also Theorem 2 here by Schneider-Thom. Thanks to Benjamin Steinberg for the reference.)

Here is the proof. It uses no machinery.

Lemma. There exists $f\in\Poly(G)$ whose support is a singleton.

[Here the support of $f$ means $f^{-1}(G\smallsetminus\{1\})$.]

Indeed, let $f$ have support $\{g\}$. Considering $x\mapsto hf(x)h^{-1}$ we see that all values in a single nontrivial conjugacy class are achieved by polynomials supported by $\{g\}$. By simplicity and taking products, we see that all maps supported by $g$ are definable as polynomials. Moreover after considering $x\mapsto f(gh^{-1}x)$ we obtain all functions supported by $\{h\}$. Since an arbitrary map is product of maps supported by singletons, we obtain the proposition.

Now let us prove the lemma. Let $X$ be a minimal subset among nonempty supports of elements of $\Poly(G)$ ($X$ exists because there exists a polynomial not constant $=1$). Say $X$ is the support of $f$. We have to show that $X$ is a singleton. Fix $g\in X$. So $u(x)=g^{-1}x$ is a polynomial. Also for each $h\in H$, the self-map $v$ defined $v(x)=hf(x)h^{-1}$ is a polynomial. Then $w_h:x\mapsto [u(x),v(x)]$ is a polynomial as well. Its support is contained in $X\smallsetminus\{g\}$. So we obtain a contradiction (a strictly smaller nonempty support), unless $w_h$ is constant equal to $1$ for each choice of $h$. The latter means that for each $x\in X\smallsetminus\{g\}$, the element $g^{-1}x$ commutes with $hf(x)h^{-1}$. That is, the nontrivial element $g^{-1}x$ commutes with a whole nontrivial conjugacy class. But the centralizer of a nontrivial conjugacy class is trivial (it is a normal subgroup, and can't be the whole group because the center is trivial). This is a contradiction unless $X\smallsetminus\{g\}$ is empty, which is precisely what we want. The proof is complete.

---

Remark (after Taras' comment, and also in the above Maurer-Rhodes reference): conversely, for a finite group $G$, the property $\Poly(G)=G^G$ implies that $G$ is simple non-abelian or $|G|\le 2$.

Indeed if $G$ is non-trivial and non-simple, then it has a non-trivial proper normal subgroup $N$, and polynomials have the nontrivial constraint $f(N)\subset f(1)N$.

Otherwise $G=\mathbf{Z}/p\mathbf{Z}$ for $p$ prime or $1$. For such a group, a "polynomial" has the form (using additive notation) $x\mapsto a+bx$ for some $a,b\in\mathbf{Z}/p\mathbf{Z}$ (i.e. is an affine self-map in this ring). There are thus $p^2$ such functions. And $p^2<p^p$ iff $p>2$.

Answer 2

The fact that $\text{Poly}(G)=G^G$ for simple non-abelian groups extends to multiple variables and this multivariate result also is a consequence of a result in universal algebra. These results can be found in the easily found in the book A Course in Universal Algebra by Stanley Burris and H. P. Sankappanavar.

We say that an algebra $\mathcal{A}$ is congruence permutable if $\phi\circ\theta=\theta\circ\phi$ whenever $\phi,\theta$ are congruences for $\mathcal{A}$. A variety is congruence permutable if each of its algebras are congruence permutable.

Theorem: A variety $V$ is congruence permutable if and only if there exists a term $t$ that satisfies the identities $t(x,x,y)=t(y,x,x)=y$.

For example, the variety of groups (and also heaps) is congruence permutable since the heap operation $t(x,y,z)=xy^{-1}z$ satisfies the identity $t(x,x,y)=t(y,x,x)=y$.

Suppose that $\mathcal{A}$ is an algebra with underlying set $A$. Let $\text{Poly}^*(\mathcal{A})\subseteq \bigcup_{n=0}^{\infty}A^{A^n}$ be the collection of all functions of the form $(x_1,\dots,x_n)\mapsto t^{\mathcal{A}}(x_1,\dots,x_n,a_1,\dots,a_m)$ for some term $t$ and $a_1,\dots,a_m\in A$.

We say that $\mathcal{A}$ is functionally complete if $\text{Poly}^*(G)=\bigcup_{n=0}^{\infty}A^{A^n}.$

Theorem: Let $\mathcal{A}$ be a non-trivial finite algebra where the variety $V(\mathcal{A})$ generated by $\mathcal{A}$ is congruence permutable. Then $\mathcal{A}$ is functionally complete if and only if $|\text{Con}(A^2)|=4$.

Corollary: (Maurer and Rhodes) A finite group $G$ is functionally complete if and only if $G$ is non-abelian and simple or $|G|=1$.

Proof: For this result, we only need to prove $\leftarrow$ since the direction $\rightarrow$ is easy. Suppose $G$ is non-abelian and simple. Then we shall show that $G\times G$ has only four normal subgroups, namely $\{e\}^2,\{e\}\times G,G\times\{e\},G\times G$. Let $N$ be a normal subgroup of $G\times G$.

If $N\subseteq G\times\{e\}$, then since $G$ is simple, we know that $N=G\times\{e\}$ or $N=\{e\}^2$. Similarly, if $N\subseteq\{e\}\times G$, then $N=G\times\{e\}$ or $N=\{e\}^2$.

Suppose now that $N\not\subseteq G\times\{e\}$ and $N\not\subseteq\{e\}\times G$. Then there are $a,b,c,d\in N$ where $(a,b),(c,d)\in N$ but where $a\neq e$ and $d\neq e$. Since $a\neq e$, there is some $r\in G$ with $a\neq rar^{-1}$. In this case $(rar^{-1},b)(a,b)^{-1}=(rar^{-1}a^{-1},e)\in N$. In particular, $N$ contains some element of the form $(\alpha,e)$ where $\alpha\neq e$. Thus, since $N$ is simple, we know that $G\times\{e\}\subseteq N$. By an analogous argument, $\{e\}\times G\subseteq N.$ Therefore, since $(\alpha,\beta)=(\alpha,e)(e,\beta)$ we conclude that $N=G\times G$. But the above theorem and by the fact that the variety of groups is congruence permutable, we conclude that $G$ is functionally complete.

Q.E.D.

The result by Maurer and Rhodes was first mentioned by Benjamin Steinberg in the comments, and the result by Maurer and Rhodes is a generalized of Ycor's answer.