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](https://gist.github.com/pjt33/b9e1e62291110b164e091ef7c2f7ead5) 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](https://en.wikipedia.org/wiki/Dedekind_group). By the [classical Dedekind result](https://en.wikipedia.org/wiki/Dedekind_group), $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](https://gist.github.com/pjt33/b9e1e62291110b164e091ef7c2f7ead5) 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$



The number of polynomials on a finite group
$\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](https://www.ams.org/journals/proc/1965-016-03/S0002-9939-1965-0175971-0/) by Maurer and Rhodes, Proc. AMS 1965. See also Theorem 2 [here](https://arxiv.org/abs/2206.11956) 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$.


