9
$\begingroup$

A function $f:X\to X$ on a group $X$ is called a polynomial if there exists $n\in\mathbb N=\{1,2,\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 number $n\in\mathbb N$ in such a representation is called the degree of the polynomial $X$.

The constant function $1_X:X\to\{1\}\subseteq X$ on a finite group $X$ is a polynomial of degree $\le\exp(X):=\min\{n\in\mathbb N:\forall x\in X\;\;(x^n=1)\}$ because $f(x)=1=x^{\exp(X)}$ for any $x\in X$.

Each polynomial $f$ on a commutative group $X$ is of form $f(x)=ax^n$ for some $a\in X$ and $n\le\exp(X)$, which implies that $\deg(1_X)=\exp(X)$ for any finite commutative group $X$.

Problem 1. Given a non-commutative finite group $X$, calculate (or evaluate) the degree $\deg(1_X)$ of the constant polynomial $1_X:X\to\{1\}\subseteq X$.

Remark 1. Calculations in GAP show that for any non-commutative group $X$ of order $|X|<20$, except for $A_4$ and $C_3\times S_3$, the degree of the constant function $1_X$ is equal $4$. For the groups $A_4$ and $C_3\times S_3$ this degree equals $6$.

Remark 2. It can be shown that $\deg(1_X)=4$ for any dihedral group $X=D_{2n}$ (because for any non-central element $b$ of order $2$ in $D_{2n}$ we have $bxxbxx=1$ for all $x\in D_{2n}$).

Remark 3. It is easy to see that $\deg(1_X)\ge \exp(Z(X))$, where $Z(X)=\{z\in X:\forall x\in X\;\;(xz=zx)\}$ is the center of $X$.

Keith Kearnes in his comment observed that $\deg(1_X)\ge\deg(1_{X/N})\ge\exp(Z(X/N))$ for any normal subgroup $N$ of $X$. In particular, $\deg(1_X)\ge \exp(X/[X,X])$.

Problem 2. What can be said about the degree of the constant polynomial $1_X$ on a finite simple group $X$. Is $\deg(1_X)=\exp(X)$? Is this equality true for the simple group $X=A_5$?

Remark 4. It seems that this problem has been considered by various authors in the contexts of strong laws on groups. In particular, by Corollary 1 in this paper of Schneider and Thom, for the symmetric group $X=S_n$ we have $\deg(1_X)\ge \frac{n}4$, which implies that the alternating group $X=A_n$ has $\deg(1_X)\ge\frac{n}8$.

$\endgroup$
9
  • 8
    $\begingroup$ Why do you not allow polynomials of degree zero? Zero seems like the natural answer to your question. $\endgroup$ Sep 3, 2022 at 17:21
  • 2
    $\begingroup$ @KeithKearnes Because allowing the degree of a constant map to be zero yields zero information about constant maps and also about the group. In contrast, the current definition (wich only positive degrees) generates many interesting and non-trivial questions. $\endgroup$ Sep 3, 2022 at 17:34
  • 5
    $\begingroup$ I would find the following approach clearer: polynomials are defined as syntactic objects; degree is defined for every polynomial as the number of occurrences of variables; one defines how to interpret these syntactic objects as concrete functions. Finally, the question posted here would be about when two polynomials interpret as the same function. (E.g., when a polynomial of positive degree interprets as a constant function.) $\endgroup$ Sep 3, 2022 at 18:13
  • 2
    $\begingroup$ Remark 5: $\deg(1_G)\geq \deg(1_{G/N})$. Hence $\textrm{exp}(G)\geq \deg(1_G)\geq \textrm{exp}([G/[G,G])$. $\endgroup$ Sep 3, 2022 at 21:11
  • 2
    $\begingroup$ (21, 1): the constant function has degrees 0, 9, 12, 15, 18, ... For what it's worth, I'm not actually doing the calculations with GAP. I'm using GAP from Sage then building Cayley tables using ints as aliases, and things go much much faster that way. $\endgroup$ Sep 4, 2022 at 21:58

1 Answer 1

12
$\begingroup$

If $X = A_5$ then $\exp(X) = \mathop{\rm lcm}(2,3,5) = 30$ but $\deg 1_X \leq 10$. Indeed if $c \in X$ is a 5-cycle then $$ f(x) := x c x c^2 x c^3 x c^4 x $$ satisfies $f(x)^2 = 1$ for all $x \in X$ (in fact $f(x)$ is a double transposition unless $x$ is in the subgroup generated by $c$ in which case of course $f(x)=1$).

added later:

To answer questions in the comments: I don't have a structural explanation why $f$ works, and a similar construction barely fails in $S_5$ (see below) and doesn't seem to work at all in $A_6$, $A_7$ and beyond.

This $f$ was found computationally by constructing the $A_5$ multiplication table and searching for "polynomials" whose image misses some exponents. Here's what the same technique finds for some other small groups:


$X = S_4$ (exponent $12$): $\deg 1_X = 6$, attained for example by $(x c x c^2 x)^2$ where $c$ is a 3-cycle. If I computed correctly, all degree-6 polynomials that represent $1_{S_4}$ are squares.


$X = S_5$ (exponent $60$): $\deg 1_X \leq 20$. This follows from $\deg 1_{A_5} \leq 10$ and the inequality $$ \deg 1_X \leq \deg 1_N \cdot \deg 1_{X/N} $$ for any normal subgroup $N$ of $X$. To prove this inequality, let $g$ be a polynomial on $X/N$ that represents the identity, and lift it arbitrarily to a polynomial $\tilde g$ on $X$. Then $\tilde g$ maps $X$ to $N$, so $\phi \circ \tilde g = 1_X$ for any polynomial $\phi$ on $N$ that represents $1_N$, and $\deg(\phi \circ \tilde g) = (\deg \phi) (\deg \tilde g) = (\deg \phi) (\deg g)$.

Taking $N = A_5$ this yields the degree-20 polynomial $f(x^2)^2$ where $f(x) = x c x c^2 x c^3 x c^4 x$ as before. In the comments Taras Banakh asked whether $f^2$ itself would work; curiously it almost does: for an odd permutation $x$, the exponent of $f(x)$ is still $2$ $-$ except when $x$ is one of the 10 $4$-cycles in the normalizer of $\langle c \rangle$, when $f(x)$ has exponent $4$. This does mean that $f(x)^4$ is another degree-$20$ representation of $1_{S_5}$.


$X = {\rm GL}_3({\bf Z}/2{\bf Z})$ (the second-smallest noncyclic simple group, which has order $168$ and exponent $84)$: $\deg 1_X \leq 36$, attained by $(xbxcx)^{12}$ where $b$ and $c$ have order $2$ and $bc$ has order $4$. (It turns out that for such $b,c$ no value of $xbxcx$ has exponent $7$, though each of the remaining exponents $1,2,3,4$ does occur.)


Probably the upper bounds for $S_5$ and ${\rm GL_3}({\bf Z}/2{\bf Z})$ are not optimal; I wouldn't even be too surprised if $\deg 1_{A_5}$ is smaller than $10$.

$\endgroup$
4
  • 1
    $\begingroup$ Is there a slick way to see the fact that you mention about $f(x)$, or is it just a computation? $\endgroup$
    – LSpice
    Sep 4, 2022 at 3:21
  • 1
    $\begingroup$ For now, just a computation. I tried all $f$ of the form $x a_1 x a_2 x a_3 x a_4 x$ up to conjugation, and the only ones that satisfied $f(x)^2 = 1$ for all $x \in A_5$ were those with $\vec a = (c,c^2,c^3,c^4)$ for some 5-cycle $c$. $\endgroup$ Sep 4, 2022 at 3:34
  • $\begingroup$ @NoamD.Elkies Is your polynomial $f$ constant also on the group $S_5$? $\endgroup$ Sep 4, 2022 at 5:45
  • $\begingroup$ @NoamD.Elkies What about the polynomial $f(x)=xcxc^2xc^3x\dots xc^{n-1}x$ for $n>5$, where $c$ is an $n$-cycle. Is $f(x)^2=1$ for all $x\in A_n$? or better $x\in S_n$? $\endgroup$ Sep 4, 2022 at 5:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.