6
$\begingroup$

This question is motivated by the comments and the answer to this MO-question.

First let us recall some definitions.

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_1\cdots xa_n$ for all $x\in X$. The smallest possible number $n$ in such a representation is called the degree of the polynomial $f$ and denoted by $\deg(f)$.

For a finite abelian group $X$, any polynomial is of the form $f(x)=ax^n$, so the degree of $f$ does not exceed the exponent $\exp(X)=\min\{n\in\mathbb N:\forall x\in X\;\;(x^n=1)\}$ of $X$.

In particular, any constant function on an finite abelian group is a polynomial of degree $\exp(X)$.

On the other hand, the constant function $f:X\to\{1\}\subseteq X$ on any dihendral group $X=D_{2n}$ is a polynomial of degree $\le 4$ as $f(x)=bxxbxx$ where $b$ is a non-central element of order $2$ in $D_{2n}$.

Peter Taylor in his comment to this MO-question observed that the group $A_4$ has exponent $\exp(A_4)=6$ but possesses a polynomial of degree 8, see here for more information on his calculations.

Emil Jeřábek in his comment to @YCor's answer observed that every nonabelian simple group $X$ has a polynomial $f:X\to X$ of degree $\deg(f)\ge|X|-1$.

Those facts motivate the following

Problem 1. Has each finite simple group $X$ a polynomial $f:X\to X$ of degree $\deg(f)=|X|$?

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

Remark. It is easy to see that each polynomial $f:X\to X$ on a finite group $X$ has $\deg(f)\le|X|^{|X|-1}$. @YCor in the comment to his answer has an exponential upper bound for degrees of polynomials on finite simple groups, but this upper bound (being exponential) is quite far from the hypothetic upper bound $\deg(f)\le|X|$ in the problem.

Added in Edit. Benjamin Steinberg in his comment suggested to look at Theorem 2 of this preprint of Schneider and Thom whose proof implies the upper bound $2|X|^3\exp(X)cn(X)$ for the largest degree of a polynomial on a finite simple group $X$. The number $cn(X)$ is defined as the smallest number $m$ such that for any normal subset $S\ne\{1\}$ in a finite simple group $X$ we have $S^m=X$. By a result of Liebeck and Shalev, $cn(X)=O(\ln(|X|))$, which yields the upper bound $O(|X|^3\exp(|X|)\ln(|X|))$ for the largest degree of a polynomial on a finite simple group $X$.

Improve this question
$\endgroup$
8
  • $\begingroup$ If such a bound is true for nonabelian simple groups then there is very little redundancy in representing functions by polynomial expressions (since every function is a polynomial and the number of functions is $|X|^{|X|}$). Is that plausible? $\endgroup$
    – Will Sawin
    Commented Sep 2, 2022 at 14:52
  • $\begingroup$ @WillSawin Maybe you are right: since the exponent of a finite simple group is rather small comparing to the cardinality of the group there are many polynomial representations of the constant unit function, so many polynomial representations of a given function. On the other hand, there are $\frac{|X|^{|X|+2}-|X|^2}{|X|-1}$ polynomials of degree $\le|X|$, which is almost $|X|$ times larger than the number $|X|^{|X|}$ of all functions. $\endgroup$
    – Taras Banakh
    Commented Sep 2, 2022 at 15:04
  • 1
    $\begingroup$ I asked it as a question for a reason because I wasn't sure if I thought it was plausible. I note that it's probably more natural to let constant functions have degree $0$ in which case the lower bound is $|X|-1$ in both finite simple and abelian cyclic cases, which is suggestive that $|X|-1$ is the right conjecture in this version, but then $|X|-1$ really is somewhat implausibly (but not entirely implausibly) tight. $\endgroup$
    – Will Sawin
    Commented Sep 2, 2022 at 15:07
  • 1
    $\begingroup$ (BTW in the linked answer I claimed "roughly" $\le 2^n$ for $n=|G|$. I didn't claim $O(2^n)$, since the proof more likely yields $O(n2^n)$ or $O(n^22^n)$, I didn't carefully check, since it's unimportant — there is certainly a much better upper bound.) $\endgroup$
    – YCor
    Commented Sep 2, 2022 at 15:32
  • 2
    $\begingroup$ This is studied where inverses are allowed in arxiv.org/pdf/2206.11956.pdf. See theorem 2 $\endgroup$
    – Benjamin Steinberg
    Commented Sep 2, 2022 at 16:36

0

Reset to default

You must log in to answer this question.