# Symmetric polynomials over finite fields

Mátyás Domokos  Alfréd Rényi Institute of Mathematics, Reáltanoda utca 13-15,
1053 Budapest, Hungary, ORCID iD: https://orcid.org/0000-0002-0189-8831
<EMAIL_ADDRESS>and  Botond Miklósi  Eötvös Loránd University, Pázmány
Péter sétány 1/C, 1117 Budapest, Hungary<EMAIL_ADDRESS>
###### Abstract.

It is shown that two vectors with coordinates in the finite $q$-element field
of characteristic $p$ belong to the same orbit under the natural action of the
symmetric group if each of the elementary symmetric polynomials of degree
$p^{k},2p^{k},\dots,(q-1)p^{k}$, $k=0,1,2,\dots$ has the same value on them.
This separating set of polynomial invariants for the natural permutation
representation of the symmetric group is not far from being minimal when $q=p$
and the dimension is large compared to $p$. A relatively small separating set
of multisymmetric polynomials over the field of $q$ elements is derived.

###### Key words and phrases:

separating sets, elementary symmetric polynomials, finite fields

###### 2010 Mathematics Subject Classification:

Primary 13A50; Secondary 12E20

Partially supported by the Hungarian National Research, Development and
Innovation Office, NKFIH K 138828, K 132002.

##  1\. Introduction

Throughout this paper $F$ stands for an arbitrary field, $q$ stands for a
power of a prime $p$, and $\mathbb{F}_{q}$ stands for the field of $q$
elements. The symmetric group $S_{n}$ acts on the vector space $F^{n}$ by
permuting coordinates: for $\pi\in S_{n}$ and $v=(v_{1},\dots,v_{n})\in F^{n}$
we have $\pi\cdot v=(v_{\pi^{-1}(1)},\dots,v_{\pi^{-1}(n)})$. Denote by
$x_{1},\dots,x_{n}$ the basis of the dual space of $F^{n}$ dual to the
standard basis in $F^{n}$. We have an induced action of $S_{n}$ via
$F$-algebra automorphisms on the polynomial algebra $F[x_{1},\dots,x_{n}]$. In
particular, $\pi\cdot x_{i}=x_{\pi(i)}$ for $\pi\in S_{n}$ and
$i\in\\{1,\dots,n\\}$. The algebra of $S_{n}$-invariant polynomials is
$F[x_{1},\dots,x_{n}]^{S_{n}}=\\{f\in F[x_{1},\dots,x_{n}]\mid\forall\pi\in
S_{n}:\ \pi\cdot f=f\\}$. A subset $T$ of $F[x_{1},\dots,x_{n}]^{S_{n}}$ is
_separating_ if for any $v,w\in F^{n}$ with different $S_{n}$-orbit there
exists an element $f\in T$ such that $f(v)\neq f(w)$. This is a special case
of the notion of _separating set of polynomial invariants_ of (not necessarily
finite) groups; for the general notion and basic facts about it we refer to
[2, Section 2.4]. By a _minimal separating set_ we shall mean a separating set
none of whose proper subsets are separating (i.e. a separating set minimal
with respect to inclusion). It is well known that every separating set has a
finite separating subset (by a straightforward modification of the proof of
[2, Theorem 2.4.8]), therefore any separating set contains a minimal
separating subset, and a minimal separating set is necessarily finite. On the
other hand, different minimal separating sets may have different cardinality,
so a minimal separating set does not necessarily have minimal possible
cardinality.

It is well known that the algebra $F[x_{1},\dots,x_{n}]^{S_{n}}$ is minimally
generated by the _elementary symmetric polynomials_ $s^{(n)}_{k}=\sum_{1\leq
i_{1}<\cdots<i_{k}\leq n}x_{i_{1}}\cdots x_{i_{k}}$. Moreover, when $F$ is
algebraically closed (or $F=\mathbb{R})$, then $\\{s^{(n)}_{k}\mid
k=1,\dots,n\\}$ is a separating set in $F[x_{1},\dots,x_{n}]^{S_{n}}$ having
the least possible number of elements (in particular, it is a minimal
separating set). However, when $F$ is finite, in general the above separating
set is not even minimal with respect to inclusion. For a real number $v$ we
shall write $\lfloor v\rfloor$ for the largest integer not strictly bigger
than $v$, and write $\lceil v\rceil$ for the smallest integer which is not
strictly smaller than $v$. Kemper, Lopatin and Reimers [7, Lemma 4.3] proved
that $\\{s^{(n)}_{2^{k}}\mid k=0,1,\dots,\lfloor\log_{2}n\rfloor\\}$ is a
minimal separating set in $\mathbb{F}_{2}[x_{1},\dots,x_{n}]^{S_{n}}$ (and
this separating set has the least possible number of elements). Our aim in
this note is to extend the above result from the $2$-element field
$\mathbb{F}_{2}$ to any finite field $\mathbb{F}_{q}$. For a positive integer
$n$ set

$[n]_{q}:=\\{jp^{k}\mid j\in\\{1,\dots,q-1\\},\quad k\in\mathbb{Z}_{\geq
0},\quad jp^{k}\leq n\\}.$

We shall prove the following:

######  Theorem 1.1.

The elementary symmetric polynomials $s^{(n)}_{m}$ with $m\in[n]_{q}$ form a
separating subset in $\mathbb{F}_{q}[x_{1},\dots,x_{n}]^{S_{n}}$.

While the study of separating sets of polynomial invariants of groups became
rather popular in the past two decades, as far as we know, the recent paper
[7] is the first studying separating sets of polynomial invariants over finite
fields; see also that paper for motivation (for example, for the connection to
the graph isomorphism problem). On the other hand, Theorem 1.1 has an
equivalent reformulation not referring to the notion of separating sets of
polynomial invariants, but as a statement about univariate polynomials over
finite fields as follows:

######  Theorem 1.2.

Let $f,g\in\mathbb{F}_{q}[x]$ be monic polynomials of degree $n$, such that
both $f$ and $g$ split as a product of root factors over $\mathbb{F}_{q}$.
Assume that for all $j\in[n]_{q}$, the degree $n-j$ coeficient of $f$
coincides with the degree $n-j$ coefficient of $g$. Then we have $f=g$.

We also investigate wether the separating set given in Theorem 1.1 is minimal.
It turns out that it is minimal (with respect to inclusion) for $q=3,4,5$ with
arbitrary $n$ and for $q=7$ with “most” $n$ (see Corollary 4.9). However,
computer calculations show that it is not always minimal (see the case $q=7$,
$n=5$ in Corollary 4.9, or the results in Section 4.5 for $p=11$). On the
other hand, we point out in Proposition 4.12 that when $q=p$ and $n$ is large
compared to $p$, then in a certain sense, the separating set given in Theorem
1.1 is not far from being minimal.

In Section 5 we turn to the study of multisymmetric polynomials over the field
$\mathbb{F}_{q}$. Separating sets of multisymmetric polynomials are studied in
[10], [8], and a minimal separating set of multisymmetric polynomials over
$\mathbb{F}_{2}$ is given in [7, Theorem 4.8]. Here we shall exploit Theorem
1.1 to obtain a relatively small separating set of multisymmetric polynomials
over $\mathbb{F}_{q}$ for an arbitrary prime power $q$ in Theorem 5.3.

##  2\. Preliminaries on polynomials

######  Lemma 2.1.

Let $F$ be an arbitrary field, $f=\sum_{i=0}^{d}c_{i}x^{i}\in F[x]$ a
polynomial whose formal derivative $f^{\prime}$ is not zero (i.e. $c_{i}\neq
0$ for some $i$ not divisible by the characteristic of $F$). Assume that
$c_{0}\neq 0$ and $c_{1}=\dots=c_{m}=0$. Then $f$ has at least $m+1$ distinct
roots in the algebraic closure of $F$.

###### Proof.

The formal derivative of $f$ is

$f^{\prime}=(m+1)c_{m+1}x^{m}+\sum_{j=m+2}^{d}jc_{j}x^{j-1}=x^{m}h$

for some non-zero polynomial $h\in F[x]$. We have

(1) $\deg(h)=\deg(f^{\prime})-m\leq\deg(f)-1-m.$

Recall that the number of distinct roots of $f$ in the algebraic closure of
$F$ is greater than or equal to the difference of the degree of $f$ and the
degree of the greatest common divisor $\mathrm{gcd}_{F[x]}(f,f^{\prime})$ of
$f$ and $f^{\prime}$. As $x$ does not divide $f$ (recall that $c_{0}\neq 0$),
we have

$\mathrm{gcd}_{F[x]}(f,f^{\prime})=\mathrm{gcd}_{F[x]}(f,h).$

Consequently,

$\deg(\mathrm{gcd}_{F[x]}(f,f^{\prime}))\leq\deg(h)\text{ and
}\deg(f)-\deg(\mathrm{gcd}_{F[x]}(f,f^{\prime}))\geq\deg(f)-\deg(h).$

It follows by (1) that the number of distinct roots of $f$ in the algebraic
closure of $f$ is at least

$\deg(f)-\deg(h)\geq m+1.$

∎

We shall denote by $\mathbb{F}_{q}^{\times}$ the set of non-zero elements in
$\mathbb{F}_{q}$

######  Corollary 2.2.

Given a map $\mathcal{O}:\mathbb{F}_{q}^{\times}\to\mathbb{Z}_{\geq 0}$
consider the polynomial

$G_{\mathcal{O}}(x):=\prod_{a\in\mathbb{F}_{q}^{\times}}(1+ax)^{\mathcal{O}(a)}\in\mathbb{F}_{q}[x].$

Assume that all terms of $G_{\mathcal{O}}(x)$ of degree $1,2,\dots,q-1$ have
coefficient zero. Then $p$ divides $\mathcal{O}(a)$ for all
$a\in\mathbb{F}_{q}^{\times}$.

###### Proof.

Suppose for contradiction that $p$ does not divide $\mathcal{O}(a)$ for some
$a\in\mathbb{F}_{q}^{\times}$. Then the formal derivative
$G_{\mathcal{O}}^{\prime}$ of $G_{\mathcal{O}}$ is not the zero polynomial in
$\mathbb{F}_{q}[x]$. Thus Lemma 2.1 applies for $G_{\mathcal{O}}$, and we
conclude that $G_{\mathcal{O}}$ has at least $(q-1)+1=q$ distinct roots in the
algebraic closure of $\mathbb{F}_{q}$. However, $G_{\mathcal{O}}$ splits as a
product of root factors already over $\mathbb{F}_{q}$, and all its roots are
non-zero, so $G_{\mathcal{O}}$ has at most $q-1$ distinct roots in
$\mathbb{F}_{q}$ (and hence in its algebraic closure), a contradiction. ∎

######  Lemma 2.3.

Take two maps
$\mathcal{O},\mathcal{P}:\mathbb{F}_{q}^{\times}\to\\{0,1,\dots,q-1\\}$ and
consider the polynomials

$G_{\mathcal{O}}(x):=\prod_{a\in\mathbb{F}_{q}^{\times}}(1+ax)^{\mathcal{O}(a)}=\sum_{j}b_{j}x^{j}\quad\text{
and }\quad
G_{\mathcal{P}}(x):=\prod_{a\in\mathbb{F}_{q}^{\times}}(1+ax)^{\mathcal{P}(a)}=\sum_{j}c_{j}x^{j}.$

Suppose that $b_{1}=c_{1},b_{2}=c_{2},\dots,b_{q-1}=c_{q-1}$. Then we have
$\mathcal{O}(a)\equiv\mathcal{P}(a)$ modulo $p$ for all
$a\in\mathbb{F}_{q}^{\times}$.

###### Proof.

By assumption the polynomial $G_{\mathcal{O}}-G_{\mathcal{P}}$ is divisible in
$\mathbb{F}_{q}[x]$ by $x^{q}$. Denote by $D$ the greatest common divisor in
$\mathbb{F}_{q}[x]$ of $G_{\mathcal{O}}$ and $G_{\mathcal{P}}$. Set
$g:=G_{\mathcal{O}}/D$ and $h:=G_{\mathcal{P}}/D$, so $x^{q}$ divides
$(g-h)D$. As $x$ does not divide $G_{\mathcal{O}}$, it does not divide $D$,
and therefore $x^{q}$ divides $g-h$ in $\mathbb{F}_{q}[x]$. There exist some
disjoint subsets $A,B$ of $\mathbb{F}_{q}^{\times}$ such that

$g=\prod_{a\in A}(1+ax)^{k_{a}}\ \text{ and }\ h=\prod_{b\in
B}(1+bx)^{m_{b}},$

where $k_{a}$, $m_{b}$ are positive integers less than or equal to $q-1$. Set

$f:=g\prod_{b\in B}(1+bx)^{q-m_{b}}.$

Then

$f=(g-h)\prod_{b\in B}(1+bx)^{q-m_{b}}+\prod_{b\in B}(1+bx)^{q}.$

The first summand on the right hand side above is divisible by $x^{q}$,
whereas the second summand minus $1$ is also divisible by $x^{q}$. This
implies that $f-1$ is divisible by $x^{q}$. On the other hand, we have

$f=\prod_{a\in A}(1+ax)^{k_{a}}\prod_{b\in B}(1+bx)^{q-m_{b}}.$

By Corollary 2.2 we conclude that $p$ divides $k_{a}$ for all $a\in A$ and $p$
divides $q-m_{b}$ (and hence $p$ divides $m_{b}$) for all $b\in B$. Define
$\mathcal{R}:\mathbb{F}_{q}^{\times}\to\\{0,1,\dots,q-1\\}$ by

$D=\prod_{c\in\mathbb{F}_{q}^{\times}}(1+cx)^{\mathcal{R}(c)}.$

Then

$\mathcal{O}(c)=\begin{cases}\mathcal{R}(c)+k_{c}&\text{ for }c\in A\\\
\mathcal{R}(c)&\text{ for }c\notin A\end{cases}\qquad\text{ and
}\qquad\mathcal{P}(c)=\begin{cases}\mathcal{R}(c)+m_{c}&\text{ for }c\in B\\\
\mathcal{R}(c)&\text{ for }c\notin B.\end{cases}$

As $p$ divides $k_{a}$ and $m_{b}$ for all $a\in A$ and $b\in B$, this clearly
implies that both $\mathcal{O}(c)$ and $\mathcal{P}(c)$ are congruent to
$\mathcal{R}(c)$ modulo $p$, hence $p$ divides $\mathcal{O}(c)-\mathcal{P}(c)$
for all $c\in\mathbb{F}_{q}^{\times}$. ∎

##  3\. A separating set of elementary symmetric polynomials

Denote by $\Pi_{q,n}$ the set of functions
$\mathcal{O}:\mathbb{F}_{q}^{\times}\to\mathbb{Z}_{\geq 0}$ satisfying
$\sum_{a\in\mathbb{F}_{q}^{\times}}\mathcal{O}(a)\leq n$. There is a natural
bijection between $\Pi_{q,n}$ and the set of $S_{n}$-orbits in
$\mathbb{F}_{q}^{n}$; namely, associate with $\mathcal{O}\in\Pi_{q,n}$ the set
of vectors in $\mathbb{F}_{q}^{n}$ having $\mathcal{O}(a)$ coordinates equal
to $a$ for each $a\in\mathbb{F}_{q}^{\times}$, and having
$n-\sum_{a\in\mathbb{F}_{q}^{\times}}\mathcal{O}(a)$ zero coordinates. We
shall write $s_{k}(\mathcal{O})$ for the value of the elementary symmetric
polynomial $s^{(n)}_{k}\in\mathbb{F}_{q}[x_{1},\dots,x_{n}]$ on the vectors in
$\mathbb{F}_{q}^{n}$ that belong to the orbit labelled by $\mathcal{O}$. For
$k>n$ we set $s_{k}(\mathcal{O})=0$, and set $s_{0}(\mathcal{O})=1$.

For $\mathcal{O}\in\Pi_{q,n}$ and $a\in\mathbb{F}_{q}^{\times}$ we have

$\mathcal{O}(a)=\sum_{j=0}^{\lfloor\log_{p}n\rfloor}\mathcal{O}(a)_{j}p^{j}$

for some uniquely determined integers
$\mathcal{O}(a)_{j}\in\\{0,1,\dots,p-1\\}$ (i.e. the numbers
$\mathcal{O}(a)_{j}$ are the digits of the non-negative integer
$\mathcal{O}(a)$ in the number system with base $p$). For
$k=0,1,\dots,\lfloor\log_{p}n\rfloor$ denote by
$\mathcal{O}_{\\{k\\}}\in\Pi_{q,n}$ the function given by

$\mathcal{O}_{\\{k\\}}(a)=\sum_{j=0}^{k}\mathcal{O}(a)_{j}p^{j},\quad
a\in\mathbb{F}_{q}^{\times}$

and let $\mathcal{O}^{[k]}\in\Pi_{q,n}$ be the function given by

$\mathcal{O}^{[k]}(a)=\mathcal{O}(a)-\mathcal{O}_{\\{k\\}}(a),\quad
a\in\mathbb{F}_{q}^{\times},$

whereas $\mathcal{O}^{[k]/p^{k+1}}\in\Pi_{q,n}$ is the function given by

$\mathcal{O}^{[k]/p^{k+1}}(a)=\frac{\mathcal{O}^{[k]}(a)}{p^{k+1}},\quad
a\in\mathbb{F}_{q}^{\times}.$

For $\mathcal{O}\in\Pi_{q,n}$ set

(2)
$G_{\mathcal{O}}(x):=\sum_{j=0}^{n}s_{j}(\mathcal{O})x^{j}=\prod_{a\in\mathbb{F}_{q}^{\times}}(1+ax)^{\mathcal{O}(a)}\in\mathbb{F}_{q}[x].$

With this notation we have the obvious equalities

(3) $G_{\mathcal{O}}(x)=G_{\mathcal{O}_{\\{k\\}}}(x)\cdot
G_{\mathcal{O}^{[k]}}(x)\in\mathbb{F}_{q}[x]$

and

(4) $G_{\mathcal{O}^{[k]}}(x)=G_{\mathcal{O}^{[k]/p^{k+1}}}(x)^{p^{k+1}}.$

######  Lemma 3.1.

Suppose that $\mathcal{O},\mathcal{P}\in\Pi_{q,n}$ satisfy

$s_{j}(\mathcal{O})=s_{j}(\mathcal{P})\text{ for }j=1,2,\dots,q-1.$

Then $\mathcal{O}_{\\{0\\}}=\mathcal{P}_{\\{0\\}}$ (i.e. $\mathcal{O}(a)$ is
congruent to $\mathcal{P}(a)$ modulo $p$ for all
$a\in\mathbb{F}_{q}^{\times}$).

###### Proof.

We have $q=p^{e+1}$ for some nonnegative integer $e$. By (3) and (4) we have

$\mathcal{G}_{\mathcal{O}}(x)=G_{\mathcal{O}_{\\{e\\}}}(x)\cdot
G_{\mathcal{O}^{[e]/q}}(x)^{q}.$

The coefficient of $x^{j}$ in $G_{\mathcal{O}^{[e]/q}}(x)^{q}$ is non-zero
only if $q$ divides $j$, and the constant term of
$G_{\mathcal{O}^{[e]/q}}(x)^{q}$ is $1$. Comparing the degree $j$ coefficients
of the two sides of the above equality for $j=1,\dots,q-1$ we get

(5) $s_{j}(\mathcal{O})=s_{j}(\mathcal{O}_{\\{e\\}})\text{ for
}j=1,\dots,q-1.$

Similarly we have

(6) $s_{j}(\mathcal{P})=s_{j}(\mathcal{P}_{\\{e\\}})\text{ for
}j=1,\dots,q-1.$

Note that $\mathcal{O}_{\\{e\\}}$ and $\mathcal{P}_{\\{e\\}}$ are maps from
$\mathbb{F}_{q}^{\times}$ to $\\{0,1,\dots,q-1\\}$. Moreover, for
$j=1,\dots,q-1$ the equality $s_{j}(\mathcal{O})=s_{j}(\mathcal{P})$ implies
by (5) and (6) that the degree $j$ coefficient of
$G_{\mathcal{O}_{\\{e\\}}}(x)$ coincides with the degree $j$ coefficient of
$G_{\mathcal{P}_{\\{e\\}}}(x)$. Consequently, Lemma 2.3 applies for
$\mathcal{O}_{\\{e\\}}$ and $\mathcal{P}_{\\{e\\}}$, and yields the desired
equality $\mathcal{O}_{\\{0\\}}=\mathcal{P}_{\\{0\\}}$. ∎

######  Lemma 3.2.

Suppose that $\mathcal{O},\mathcal{P}\in\Pi_{q,n}$ and for some
$k\in\\{0,1,\dots,\lfloor\log_{p}n\rfloor-1\\}$ we have
$\mathcal{O}_{\\{k\\}}=\mathcal{P}_{\\{k\\}}$ and
$s_{jp^{k+1}}(\mathcal{O})=s_{jp^{k+1}}(\mathcal{P})$ for $j=1,2,\dots,q-1$.
Then $\mathcal{O}_{\\{k+1\\}}=\mathcal{P}_{\\{k+1\\}}$.

###### Proof.

Compare the coefficient of $x^{jp^{k+1}}$ on the two sides of (3). Taking into
account that all non-zero terms of $G_{\mathcal{O}^{[k]}}(x)$ have degree
divisible by $p^{k+1}$ we get that

(7)
$s_{jp^{k+1}}(\mathcal{O})=\sum_{i=0}^{j}s_{ip^{k+1}}(\mathcal{O}^{[k]})s_{(j-i)p^{k+1}}(\mathcal{O}_{\\{k\\}})\quad\text{
for }\quad j=1,\dots,q-1.$

Consider the following system of linear equations for the unknowns
$y_{1},\dots,y_{q-1}$:

(8)
$\sum_{i=1}^{j}s_{(j-i)p^{k+1}}(\mathcal{O}_{\\{k\\}})y_{i}=s_{jp^{k+1}}(\mathcal{O})-s_{jp^{k+1}}(\mathcal{O}_{\\{k\\}}),\quad
j=1,\dots,q-1.$

By (7) we see that $y_{j}=s_{jp^{k+1}}(\mathcal{O}^{[k]})$, $j=1,\dots,q-1$ is
a solution of the system (8). Moreover, the system (8) has a unique solution:
the equation for $j=1$ gives

$y_{1}=s_{p^{k+1}}(\mathcal{O})-s_{p^{k+1}}(\mathcal{O}_{\\{k\\}}),$

and supposing that we have already fixed the values of $y_{1},\dots,y_{j-1}$
for some $j>1$, we have

$y_{j}=s_{jp^{k+1}}(\mathcal{O})-s_{jp^{k+1}}(\mathcal{O}_{\\{k\\}})-\sum_{i=1}^{j-1}s_{(j-i)p^{k+1}}(\mathcal{O}_{\\{k\\}})y_{i}.$

Similar considerations hold for the values of
$s_{jp^{k+1}}(\mathcal{P}^{[k]})$, $j=1,\dots,q-1$. By assumption we have

$s_{ip^{k+1}}(\mathcal{P}_{\\{k\\}})=s_{ip^{k+1}}(\mathcal{O}_{\\{k\\}})\text{
and }s_{ip^{k+1}}(\mathcal{P})=s_{ip^{k+1}}(\mathcal{O})\text{ for
}i=1,\dots,q-1.$

It follows that $y_{j}=s_{jp^{k+1}}(\mathcal{P}^{[k]})$, $j=1,\dots,q-1$ is
also a solution of the system (8), and by uniqueness of the solution we
conclude that

(9) $s_{jp^{k+1}}(\mathcal{O}^{[k]})=s_{jp^{k+1}}(\mathcal{P}^{[k]})\text{ for
}j=1,\dots,q-1.$

By (4) we have

(10)
$s_{jp^{k+1}}(\mathcal{O}^{[k]})=s_{j}(\mathcal{O}^{[k]/p^{k+1}})^{p^{k+1}}$

and

(11)
$s_{jp^{k+1}}(\mathcal{P}^{[k]})=s_{j}(\mathcal{P}^{[k]/p^{k+1}})^{p^{k+1}}$

By (9), (10), (11) we get that

(12) $s_{j}(\mathcal{O}^{[k]/p^{k+1}})=s_{j}(\mathcal{P}^{[k]/p^{k+1}})\text{
for }j=1,\dots,q-1.$

We conclude from (12) by Lemma 3.1 that

(13)
$\mathcal{O}^{[k]/p^{k+1}}_{\\{0\\}}=\mathcal{P}^{[k]/p^{k+1}}_{\\{0\\}}.$

Note finally that

(14)
$\mathcal{O}^{[k]/p^{k+1}}_{\\{0\\}}(a)=\mathcal{O}^{[k]}(a)_{k+1}=\mathcal{O}(a)_{k+1}\text{
for all }a\in\mathbb{F}_{q}^{\times}$

and similarly

(15)
$\mathcal{P}^{[k]/p^{k+1}}_{\\{0\\}}(a)=\mathcal{P}^{[k]}(a)_{k+1}=\mathcal{P}(a)_{k+1}\text{
for all }a\in\mathbb{F}_{q}^{\times}.$

Now (13), (14), (15) show that
$\mathcal{O}(a)_{k+1}=\mathcal{P}(a)_{k+1}\text{ for all
}a\in\mathbb{F}_{q}^{\times}$. As we have
$\mathcal{O}_{\\{k\\}}=\mathcal{P}_{\\{k\\}}$ by assumption, this gives the
desired equality $\mathcal{O}_{\\{k+1\\}}=\mathcal{P}_{\\{k+1\\}}$. ∎

######  Corollary 3.3.

Let $\mathcal{O},\mathcal{P}\in\Pi_{q,n}$ and $t\in\\{1,\dots,n\\}$. Assume
that $s_{jp^{k}}(\mathcal{O})=s_{jp^{k}}(\mathcal{P})$ holds for all
$j\in\\{1,\dots,q-1\\}$ and $k\in\\{0,1,\dots,\lfloor\log_{p}(t)\rfloor\\}$.
Then we have

  * (i)

$\mathcal{O}_{\\{\lfloor\log_{p}(t)\rfloor\\}}=\mathcal{P}_{\\{\lfloor\log_{p}(t)\rfloor\\}}$

  * (ii)

$s_{t}(\mathcal{O})=s_{t}(\mathcal{P})$.

###### Proof.

Lemma 3.1 and an iterated use of Lemma 3.2 yield (i), so setting
$d:=\lfloor\log_{p}(t)\rfloor$ we have
$\mathcal{O}_{\\{d\\}}=\mathcal{P}_{\\{d\\}}$. By (4) we have
$G_{\mathcal{O}^{[d]}}(x)=G_{\mathcal{O}^{[d]/p^{d+1}}}(x)^{p^{d+1}}$, showing
that all non-zero terms of $G_{\mathcal{O}^{[d]}}(x)$ of positive degree have
degree greater than or equal to $p^{d+1}>t$; moreover, the constant term of
$G_{\mathcal{O}^{[d]}}(x)$ is $1$. On the other hand, by (3) we have
$G_{\mathcal{O}}(x)=G_{\mathcal{O}_{\\{d\\}}}(x)\cdot
G_{\mathcal{O}^{[d]}}(x)$. It follows that
$s_{t}(\mathcal{O})=s_{t}(\mathcal{O}_{\\{d\\}})$. Similarly we have
$s_{t}(\mathcal{P})=s_{t}(\mathcal{P}_{\\{d\\}})$. Taking into account (i) we
get

$s_{t}(\mathcal{O})=s_{t}(\mathcal{O}_{\\{d\\}})=s_{t}(\mathcal{P}_{\\{d\\}})=s_{t}(\mathcal{P}),$

so (ii) holds as well. ∎

Proof of Theorem 1.1. Suppose that for the $S_{n}$-orbit corresponding to
$\mathcal{O}\in\Pi_{q,n}$ and the $S_{n}$-orbit corresponding to
$\mathcal{P}\in\Pi_{q,n}$ we have
$s_{jp^{k}}(\mathcal{O})=s_{jp^{k}}(\mathcal{P})$ for all $j=1,\dots,q-1$ and
$k\in\mathbb{Z}_{\geq 0}$ (recall that
$s_{m}(\mathcal{O})=0=s_{m}(\mathcal{P})$ for any $m>n$). Corollary 3.3 (i) in
the special case $n=t$ gives

$\mathcal{O}_{\\{\lfloor\log_{p}n\rfloor\\}}=\mathcal{P}_{\\{\lfloor\log_{p}n\rfloor\\}}.$

Taking into account that
$\mathcal{O}=\mathcal{O}_{\\{\lfloor\log_{p}n\rfloor\\}}$ and
$\mathcal{P}=\mathcal{P}_{\\{\lfloor\log_{p}n\rfloor\\}}$ we conclude the
equality $\mathcal{O}=\mathcal{P}$. This clearly means that the set of
elementary symmetric polynomials in the statement is separating. $\square$

##  4\. Minimality

######  Lemma 4.1.

Suppose that for some subset $A\subseteq\\{1,\dots,n\\}$ we have that
$\\{s_{i}^{(n)}\mid i\in A\\}$ is separating in
$F[x_{1},\dots,x_{n}]^{S_{n}}$. Then for all $m\leq n$ we have that
$\\{s_{j}^{(m)}\mid j\in A\cap\\{1,\dots,m\\}\\}$ is separating in
$F[x_{1},\dots,x_{m}]^{S_{m}}$.

###### Proof.

For $n\geq m$ we shall treat $F^{m}$ as the subspace of $F^{n}$ consisting of
the vectors whose last $n-m$ coordinates are zero. With this convention we
have that for $v\in F^{m}$ and $n>m$,

(16) $s_{j}^{(n)}(v)=\begin{cases}s_{j}^{(m)}(v)&\text{ for }j\leq m\\\
0&\text{ for }m<j\leq n.\end{cases}$

Now take $v,w\in F^{m}$ having different $S_{m}$-orbit. Then viewed as
elements of $F^{n}$, $v$ and $w$ have different $S_{n}$-orbit. Hence by
assumption there exists an $i\in A$ with $s^{(n)}_{i}(v)\neq s^{(n)}_{i}(w)$.
In particular, $s^{(n)}_{i}(v)$ and $s^{(n)}_{i}(w)$ are not both zero, hence
$i\leq m$. Moreover, by (16) we conclude $s^{(m)}_{i}(v)\neq s^{(m)}_{i}(w)$.
∎

######  Lemma 4.2.

Let $K$ be a field containing $F$ as a subfield. If $\\{s_{i}^{(n)}\mid i\in
A\\}$ is a separating set in $K[x_{1},\dots,x_{n}]^{S_{n}}$, then it is also a
separating set in $F[x_{1},\dots,x_{n}]^{S_{n}}$.

###### Proof.

The elementary symmetric polynomials are defined over the prime subfield
$\mathbb{F}_{p}$ of $K$ and $F$. If a set of elementary symmetric polynomials
separates the $S_{n}$-orbits in $K^{n}$, then it necessarily separates the
orbits in the $S_{n}$-stable subset $F^{n}$ of $K^{n}$. ∎

######  Definition 4.3.

We say that the elementary symmetric polynomial $s^{(n)}_{k}$ _is
irreplaceable over $F$_ if any separating subset of
$F[x_{1},\dots,x_{n}]^{S_{n}}$ that consists of elementary symmetric
polynomials necessarily contains $s^{(n)}_{k}$.

######  Remark 4.4.

(i) We would like to emphasize that the question wether the $k$th elementary
symmetric polynomial is irreplaceable depends both on the number of variables
and on the base field considered.

(ii) It follows from Theorem 1.1 that if $s^{(n)}_{m}$ is irreplaceable over
$\mathbb{F}_{q}$, then $m\in[n]_{q}$.

Lemma 4.1 and Lemma 4.2 have the following immediate consequence:

######  Corollary 4.5.

If $s^{(n)}_{k}$ is irreplaceable over $F$, then $s^{(m)}_{k}$ is
irreplaceable over $K$ for all $m\geq n$ and all overfields $K$ of $F$.

Irreplaceable elementary symmetric polynomials have the following obvious
characterization:

######  Lemma 4.6.

The elementary symmetric polynomial $s^{(n)}_{k}$ is irreplaceable over $F$ if
and only if there exist elements $v,w\in F^{n}$ such that

(17) $s_{j}^{(n)}(v)=s_{j}^{(n)}(w)\quad\forall
j\in\\{1,\dots,n\\}\setminus\\{k\\}\text{ and }s_{k}^{(n)}(v)\neq
s_{k}^{(n)}(w).$

######  Lemma 4.7.

If $s_{k}^{(n)}$ is irreplaceable over $\mathbb{F}_{q}$, then
$s^{(m)}_{p^{j}k}$ is irreplaceable over $\mathbb{F}_{q}$ for all
$j\in\mathbb{Z}_{\geq 0}$ and $m\geq p^{j}n$.

###### Proof.

Suppose that $s^{(n)}_{k}$ is irreplaceable over $\mathbb{F}_{q}$. Then by
Lemma 4.6 there exist $v,w\in\mathbb{F}_{q}^{n}$ such that $s^{(n)}_{k}(v)\neq
s^{(n)}_{k}(w)$ and $s^{(n)}_{i}(v)=s^{(n)}_{i}(w)$ for all
$i\in\\{1,\dots,n\\}\setminus\\{k\\}$. Denote by
$\mathcal{O},\mathcal{P}\in\Pi_{q,n}$ the functions
$\mathbb{F}_{q}\to\mathbb{Z}_{\geq 0}$ corresponding to the orbits of $v,w$,
so we have $s_{i}(\mathcal{O})=s_{i}(\mathcal{P})$ for
$i\in\\{1,\dots,n\\}\setminus\\{k\\}$ and $s_{k}(\mathcal{O})\neq
s_{k}(\mathcal{P})$. Consider the polynomials $G_{\mathcal{O}}(x)$ and
$G_{\mathcal{P}}(x)$. Then these are polynomials of degree at most $n$, all
but their degree $k$ coefficients agree and their degree $k$ coefficient is
different. For $m\geq p^{j}n$ denote by $p^{j}\mathcal{O}\in\Pi_{q,m}$,
$p^{j}\mathcal{P}\in\Pi_{q,m}$ the functions $a\mapsto p^{j}\mathcal{O}(a)$
($a\in\mathbb{F}_{q}^{\times}$), $a\mapsto p^{j}\mathcal{P}(a)$
($a\in\mathbb{F}_{q}^{\times}$). We have the equalities

$G_{p^{j}\mathcal{O}}(x)=G_{\mathcal{O}}(x)^{p^{j}}=\sum_{i=0}^{n}s_{i}(\mathcal{O})^{p^{j}}x^{ip^{j}}\text{
and
}G_{p^{j}\mathcal{P}}(x)=G_{\mathcal{P}}(x)^{p^{j}}=\sum_{i=0}^{n}s_{i}(\mathcal{P})^{p^{j}}x^{ip^{j}}.$

This shows that $s_{p^{j}k}(p^{j}\mathcal{O})\neq
s_{p^{j}k}(p^{j}\mathcal{P})$ and
$s_{i}(p^{j}\mathcal{O})=s_{i}(p^{j}\mathcal{P})$ for all
$i\in\\{1,\dots,m\\}\setminus\\{k\\}$. Consequently, $s^{(m)}_{p^{j}k}$ is
irreplaceable over $\mathbb{F}_{q}$ by Lemma 4.6. ∎

######  Corollary 4.8.

Suppose that the elementary symmetric polinomial $s^{(k)}_{k}$ is
irreplaceable over $\mathbb{F}_{q}$ for each $k\in\\{1,2,\dots,q-1\\}$. Then
for an arbitrary $n$ the separating subset $\\{s^{(n)}_{m}\mid m\in[n]_{q}\\}$
of $\mathbb{F}_{q}[x_{1},\dots,x_{n}]^{S_{n}}$ given in Theorem 1.1 is minimal
(with respect to inclusion).

###  4.1. Some irreplaceable elementary symmetric polynomials

Below for certain prime powers $q$ and certain integers $n,k$ we provide pairs
of vectors $v,w$ in $\mathbb{F}_{q}^{n}$ satisfying (17), showing by Lemma 4.6
that $s_{k}^{(n)}$ is irreplaceable over $\mathbb{F}_{q}$. The elements of the
$p$-element field $\mathbb{F}_{p}$ will be denoted by $0,1,2,\dots,p-1$ in the
obvious way.

$\begin{array}[]{c||c|c}q=3&s_{1}^{(1)}&s_{2}^{(2)}\\\ \hline\cr\hline\cr
v&[1]&[1,2]\\\ \hline\cr w&[0]&[0,0]\end{array}$

$\begin{array}[]{c||c|c|c|c}q=5&s_{1}^{(1)}&s_{2}^{(2)}&s_{3}^{(3)}&s_{4}^{(4)}\\\
\hline\cr\hline\cr v&[1]&[1,4]&[1,4,4]&[1,2,3,4]\\\ \hline\cr
w&[0]&[0,0]&[2,2,0]&[0,0,0,0]\end{array}$

$\begin{array}[]{c||c|c|c|c|c|c}q=7&s_{1}^{(1)}&s_{2}^{(2)}&s_{3}^{(3)}&s_{4}^{(4)}&s_{6}^{(6)}&s_{5}^{(6)}\\\
\hline\cr\hline\cr
v&[1]&[1,6]&[1,2,4]&[1,1,6,6]&[1,2,3,4,5,6]&[2,2,2,3,6,6]\\\ \hline\cr
w&[0]&[0,0]&[0,0,0]&[3,4,0,0]&[0,0,0,0,0,0]&[1,1,4,5,5,5]\end{array}$

$\begin{array}[]{c||c|c|c|c|c|c}q=11&s_{1}^{(1)}&s_{2}^{(2)}&s_{3}^{(3)}&s_{4}^{(4)}&s_{5}^{(5)}&s_{6}^{(6)}\\\
\hline\cr\hline\cr v&[1]&[5,6]&[5,7,9]&[1,2,2,5]&[1,3,9,5,4]&[1,1,3,6,8,8]\\\
\hline\cr
w&[0]&[0,0]&[10,0,0]&[10,0,0,0]&[0,0,0,0,0,0]&[9,9,10,10,0,0]\end{array}$

$\begin{array}[]{c||c}q=11&s_{7}^{(8)}\\\ \hline\cr\hline\cr
v&[1,2,2,2,2,4,4,5]\\\ \hline\cr w&[6,7,7,9,9,9,9,10]\end{array}$

###  4.2. The polynomial $s_{k}^{(k)}$ for a divisor $k$ of $q-1$ for an
arbitrary prime power $q$

We may take as $v$ the vector whose coordinates are the $k$ roots in
$\mathbb{F}_{q}$ of the polynomial $x^{k}-1$, and for $w$ the zero vector.
Then we have
$0=s_{1}^{(k)}(w)=s_{1}^{(k)}(v)=s_{2}^{(k)}(w)=s_{2}^{(k)}(v)=\cdots=s_{k-1}^{(k)}(w)=s_{k-1}^{(k)}(v)=s_{k}^{(k)}(w)$
whereas $s_{k}^{(k)}(v)=(-1)^{k+1}\in\mathbb{F}_{q}$.

###  4.3. The polynomial $s_{k}^{(k)}$ for an arbitrary $k$ and $q\geq k!-k+1$

The assumption on $q$ guarantees that the number $\binom{q-1+k}{k}$ of
$S_{k}$-orbits in $\mathbb{F}_{q}^{k}$ is greater than the number $q^{k-1}$
which is an obvious upper bound for the number of possible values of the
$(k-1)$-tuples $(s_{1}^{(k)}(z),\dots,s_{k-1}^{(k)}(z))$ (where
$z\in\mathbb{F}_{q}$), hence the desired pair of vectors in
$\mathbb{F}_{q}^{k}$ exists by the pigeonhole principle. From the special case
$k=3$ we get the $s_{3}^{(3)}$ is irreplaceable over $\mathbb{F}_{q}$ for all
prime powers $q\geq 4$.

###  4.4. Result obtained by computer for $q=7$.

$\\{s_{k}^{(5)}\mid k=1,2,3,4\\}$ is a separating set in
$\mathbb{F}_{7}[x_{1},x_{2},x_{3},x_{4},x_{5}]^{S_{5}}$, hence the elementary
symmetric polynomial $s_{5}^{(5)}$ is not irreplaceable over $\mathbb{F}_{7}$.

###  4.5. Further results obtained by computer for $q=11$.

The elementary symmetric polynomial $s_{7}^{(7)}$ is not irreplaceable over
$\mathbb{F}_{11}$. On the other hand, $\\{s_{i}^{(10)}\mid
i=1,2,3,4,5,6,7,10\\}$ is a minimal separating set in
$\mathbb{F}_{11}[x_{1},\dots,x_{10}]^{S_{10}}$. Consequently, none of
$s_{8}^{(8)},s_{8}^{(9)},s_{8}^{(10)},s_{9}^{(9)},s_{9}^{(10)}$ is
irreplaceable over $\mathbb{F}_{11}$. Further computer calculations showed
that none of $s_{8}^{(11)}$, $s_{8}^{(12)}$, $s_{8}^{(13)}$ is irreplaceable
over $\mathbb{F}_{11}$.

The results of Section 4.1 (and Section 4.4) imply by Lemma 4.7 and Corollary
4.8 the following:

######  Corollary 4.9.

The separating subset $\\{s_{m}^{(n)}\mid m\in[n]_{q}\\}$ of
$\mathbb{F}_{q}[x_{1},\dots,x_{n}]^{S_{n}}$ given in Theorem 1.1 is minimal
(with respect to inclusion) for $q=3$, $4$, $5$ with arbitrary $n$, and for
$q=7$ with $\log_{7}n-\lfloor\log_{7}n\rfloor<\log_{7}5$ or
$\log_{7}n-\lfloor\log_{7}n\rfloor\geq\log_{7}6$. In
$\mathbb{F}_{7}[x_{1},x_{2},x_{3},x_{4},x_{5}]^{S_{5}}$, $\\{s_{i}^{(5)}\mid
i=1,2,3,4\\}$ is a minimal separating subset.

In view of the above results it seems natural to formulate the following
problems:

######  Problem 4.10.

Is it true that for any prime $p$ and any $k\in\\{1,2,\dots,p-1\\}$ there
exists a positive integer $n$ such that $s_{k}^{(n)}$ is irreplaceable over
$\mathbb{F}_{p}$?

######  Problem 4.11.

Given a prime $p$ and positive integers $k\leq n$, determine the minimal
fields $\mathbb{F}_{q}$ of characteristic $p$ such that $s_{k}^{(n)}$ is
irreplaceable over $\mathbb{F}_{q}$.

###  4.6. A bound for the distance from being minimal

We saw above that the separating set given in Theorem 1.1 is not always
minimal. Moreover, even when it is minimal, it may not be of minimal possible
cardinality. For example, for $n=9$ and $q=3$, the minimal cardinality of a
separating set in $\mathbb{F}_{3}[x_{1},\dots,x_{9}]^{S_{3}}$ is
$\lceil\log_{3}\binom{9+2}{2}\rceil=4$ by [7, Theorem 1.1], whereas the
minimal separating set given in Corollary 4.9 has cardinality
$|[9]_{3}|=|\\{1,2,3,6,9\\}|=5$. Our aim here is to point out that however,
for $q=p$ and for large $n$, the separating set given in Theorem 1.1 is not
much bigger than a separating set of minimal cardinality.

Denote by $d_{q}(n)$ the difference of $|[n]_{q}|$ (the number of elements in
the separating subset of $\mathbb{F}_{q}[x_{1},\dots,x_{n}]^{S_{n}}$ given in
Theorem 1.1) and the number of elements in a separating subset of
$\mathbb{F}_{q}[x_{1},\dots,x_{n}]^{S_{n}}$ of minimal possible cardinality.

######  Proposition 4.12.

For any prime $p$ we have the inequality $d_{p}(n)\leq p-2$. Consequently, one
can get a minimal (with respect to inclusion) separating set in
$\mathbb{F}_{p}[x_{1},\dots,x_{n}]^{S_{n}}$ by removing at most $p-2$ elements
from the separating set given in Theorem 1.1.

###### Proof.

By [7, Theorem 1.1] the minimal cardinality of a separating set in
$\mathbb{F}_{p}[x_{1},\dots,x_{n}]^{S_{n}}$ is the upper integer part of the
logarithm with base $p$ of the number of $S_{n}$-orbits in
$\mathbb{F}_{p}^{n}$. The number of $S_{n}$-orbits in $\mathbb{F}_{p}^{n}$ is
$\binom{n+p-1}{p-1}$. There exists an $m\in\\{1,\dots,p-1\\}$ and
$k\in\mathbb{Z}_{\geq 0}$ with

$mp^{k}\leq n<(m+1)p^{k}.$

We have

(18) $\displaystyle\lceil\log_{p}\binom{n+p-1}{p-1}\rceil$
$\displaystyle\geq\lceil\sum_{j=1}^{p-1}\log_{p}(mp^{k}+j)-\log_{p}((p-1)!)\rceil$
$\displaystyle>(p-1)\log_{p}(mp^{k})-\log_{p}((p-1)!)$
$\displaystyle=(p-1)k+(p-1)\log_{p}m-\log_{p}((p-1)!)$
$\displaystyle>(p-1)k+m-(p-1),$

where the last inequality follows from

$\frac{(p-1)!}{m^{p-1}}=\frac{p-1}{m}\cdot\frac{p-2}{m}\cdots\frac{m+1}{m}\cdot\frac{m}{m}\cdot\frac{m-1}{m}\cdots\frac{1}{m}<p^{p-1-m}.$

On the other hand, the number of elements in the separating set given in
Theorem 1.1 is $k(p-1)+m$. Taking into account (18) we get

$d_{p}n)<k(p-1)+m-((p-1)k+m-(p-1))=p-1.$

∎

##  5\. Multisymmetric polynomials over $\mathbb{F}_{q}$

Consider the $m$-fold direct sum of the representation of $S_{n}$ on $F^{n}$.
So the underlying vector space of this representation is
$(F^{n})^{m}=F^{n}\oplus\cdots\oplus F^{n}$. For $j=1,\dots,m$ and
$i=1,\dots,n$ denote by $x_{i}^{(j)}$ the function mapping an $m$-tuple
$(v^{(1)},\dots,v^{(m)})\in(F^{n})^{m}$ of vectors to the $i$th coordinate of
the $j$th vector component $v^{(j)}$. We get an induced action on the
$nm$-variable polynomial algebra $A_{n,m}:=F[x_{i}^{(j)}\mid i=1,\dots,n;\
j=1,\dots,m]$ given by $\pi\cdot x_{i}^{(j)}=x_{\pi(i)}^{(j)}$. The
corresponding algebra $A_{n,m}^{S_{n}}$ of polynomial invariants is called
_the algebra of multisymmetric polynomials_. Our aim in this section is to
give a separating set of multisymmetric polynomials, where a subset $T$ of
$A_{n,m}^{S_{n}}$ is said to be _separating_ if for any $v,w\in(F^{n})^{m}$
with different $S_{n}$-orbit there is a polynomial $f\in T$ with $f(v)\neq
f(w)$.

The algebra $A_{n,m}$ is $\mathbb{Z}_{\geq 0}^{m}$-graded: the
multihomogeneous component $A_{n,m,\alpha}$ of $A_{n,m}$ of multidegree
$\alpha=(\alpha_{1},\dots,\alpha_{m})\in\mathbb{Z}_{\geq 0}^{m}$ is spanned by
polynomials all of whose non-zero terms have total degree $\alpha_{j}$ in the
variables $x_{1}^{(j)},\dots,x_{n}^{(j)}$ for each $j=1,\dots,m$. The
$S_{n}$-action preserves this multigrading, hence the algebra of
multisymmetric polynomials is also multigraded: we have
$A_{n,m}^{S_{n}}=\bigoplus_{\alpha\in\mathbb{Z}_{\geq
0}^{m}}A_{n,m,\alpha}^{S_{n}}$. Denote by $s_{k,\alpha}^{(n)}$ the component
of multidegree $\alpha$ of
$s_{k}^{(n)}(\sum_{j=1}^{m}x_{1}^{(j)},\dots,\sum_{j=1}^{m}x_{n}^{(j)})$.
Clearly $s_{k,\alpha}^{(n)}$ is non-zero only if
$\alpha_{1}+\cdots+\alpha_{m}=k$. The multisymmetric polynomials
$s_{k,\alpha}^{(n)}$ are called the _polarizations of the elementary symmetric
polynomials_. They generate $A_{n,m}^{S_{n}}$ when the characteristic of the
base field $F$ is greater than $n$ or is $0$ (in other words, when
$\mathrm{char}(F)$ does not divide the order of the group $S_{n}$, see for
example [3] and the relevant references therein). However, when
$0<\mathrm{char}(F)\leq n$, the polarizations of the elementary symmetric
polynomials are not suficient to generate the algebra of multisymmetric
polynomials in general. In fact the maximal degree of an element in a minimal
homogeneous generating system of $A_{n,m}^{S_{n}}$ tends to infinity together
with $m$, see [6]. For the modular case generating systems of
$A_{n,m}^{S_{n}}$ are given in [13], [3]. A minimal homogeneous generating
system is obtained in [5] for the case $F=\mathbb{F}_{2}$, and in [11] for an
arbitrary base ring $F$.

######  Proposition 5.1.

For any field $F$, the following is a separating set in $A_{n,m}^{S_{n}}$:

$\left\\{\sum_{\alpha_{2}+2\alpha_{3}+\cdots+(m-1)\alpha_{m}=d}s_{k,\alpha}^{(n)}\
\mid\ k=1,\dots,n;\quad d=0,1,\dots,(m-1)n\right\\}.$

###### Proof.

The elementary symmetric polynomials generate $F[x_{1},\dots,x_{n}]^{S_{n}}$,
therefore by [4, Theorem 3.4] their “cheap polarizations” form a separating
set. It is easy to see that the cheap polarizations of the elementary
symmetric polynomials are the polynomials given in the statement. ∎

Let us recall another class of multisymmetric polynomials. For any
$\alpha\in\mathbb{Z}_{\geq 0}^{m}$ set

$s_{k}^{(n)}(x^{\alpha}):=s_{k}^{(n)}(\prod_{j=1}^{m}{x_{1}^{(j)}}^{\alpha_{j}},\dots,\prod_{j=1}^{m}{x_{n}^{(j)}}^{\alpha_{j}}).$

Note that the formulae from [1] were used in [3, Equation (6)] to express the
polynomials $s_{k,\alpha}^{(n)}$ in terms of the polynomials
$s_{k}^{(n)}(x^{\gamma})$. Write $|\alpha|:=\sum_{j=1}^{m}\alpha_{j}$, and
denote by $\mathrm{gcd}(\alpha)$ the greatest common divisor of
$\alpha_{1},\dots,\alpha_{m}$.

######  Proposition 5.2.

For any field $F$ the elements $s_{k}^{(n)}(x^{\alpha})$ with
$\alpha\in\mathbb{Z}_{\geq 0}^{m}$, $k|\alpha|\leq n$,
$\mathrm{gcd}(\alpha)=1$ constitute a separating set in $A_{n,m}^{S_{n}}$.

###### Proof.

Proposition 5.1 implies in particular that the elements of $A_{n,m}^{S_{n}}$
with degree at most $n$ form a separating subset. It follows that the elements
of degree at most $n$ from any homogeneous system of generators of the algebra
$A_{n,m}^{S_{n}}$ form a separating set. Applying this for the generating
system given in [3, Corollary 5.3] we obtain the desired statement. ∎

######  Theorem 5.3.

For the field $F=\mathbb{F}_{q}$ of $q$ elements the following is a separating
set in $A_{n,m}^{S_{n}}$:

(19) $\displaystyle\\{s_{jp^{k}}^{(n)}(x^{\alpha})\mid\quad$ $\displaystyle
j\in\\{1,\dots,q-1\\},\quad\alpha\in\mathbb{Z}_{\geq 0}^{m},\quad|\alpha|\leq
n,\quad\mathrm{gcd}(\alpha)=1,$ $\displaystyle\alpha_{j}\leq q-1\text{ for
}j=1,\dots,m,\quad
k\in\\{0,1,\dots,\lfloor\log_{p}\frac{n}{|\alpha|}\rfloor\\}\\}.$

###### Proof.

Suppose that $v,w\in(\mathbb{F}_{q}^{n})^{m}$ belong to different
$S_{n}$-orbits. By Proposition 5.2 there exist a $t\in\\{1,\dots,n\\}$,
$\alpha\in\mathbb{Z}_{\geq 0}^{m}$ with $t|\alpha|\leq n$ such that
$s_{t}^{(n)}(v^{\alpha})\neq s_{t}^{(n)}(w^{\alpha})$, where $v^{\alpha}$
(respectively $w^{\alpha}$) stands for the vector in $\mathbb{F}_{q}^{n}$
whose $i$th coordinate is $\prod_{j=1}^{m}{v_{i}^{(j)}}^{\alpha_{j}}$
(respectively $\prod_{j=1}^{m}{w_{i}^{(j)}}^{\alpha_{j}}$). We may assume that
$|\alpha|$ is minimal possible. Then $\alpha_{j}\leq q-1$, because for all $j$
with $\alpha_{j}>0$, denoting by $\gamma_{j}$ the unique element of
$\\{1,\dots,q-1\\}$ which is congruent to $\alpha_{j}$ modulo $q-1$ (and
setting $\gamma_{j}=0$ if $\alpha_{j}=0$), we have $v^{\alpha}=v^{\gamma}$ and
$w^{\alpha}=w^{\gamma}$. Thus by minimality of $|\alpha|$ we must have
$\alpha_{j}\in\\{0,1,\dots,q-1\\}$ for al $j$. Moreover, we must have
$\mathrm{gcd}(\alpha)=1$, since otherwise $s_{t}^{(n)}(x^{\alpha})$ can be
expressed as a polynomial of elements of the form $s_{u}^{(n)}(x^{\gamma})$
with $|\gamma|<|\alpha|$ (see [3, Page 517] for explanation), and some
$s_{u}^{(n)}(x^{\gamma})$ with $|\gamma|<|\alpha|$ would separate $v$ and $w$,
contrary to the minimality of $|\alpha|$. Finally, it follows by Corollary 3.3
(ii) that there exists a $j\in\\{1,\dots,q-1\\}$ and
$k\in\\{0,1,\dots,\lfloor\log_{p}t\rfloor\\}$ such that
$s_{jp^{k}}^{(n)}(v^{\alpha})\neq s_{jp^{k}}^{(n)}(w^{\alpha})$. So we showed
that whenever $v,w\in(\mathbb{F}_{q}^{n})^{m}$ have different $S_{n}$-orbit,
then $v$ and $w$ can be separated by an element from (19). ∎

######  Remark 5.4.

The separating set given in Theorem 5.3 for $F=\mathbb{F}_{q}$ exploits
Theorem 1.1. For fixed $q$ and $m$ and “sufficiently large $n$” it is
significantly smaller than the separating sets given in Proposition 5.1 or
Proposition 5.2 for general $F$, see Example 5.5 for illustration. On the
other hand, in the special case $q=2$ a stronger result is known, since in [7,
Theorem 4.8] a minimal separating subset of $A_{n,m}^{S_{n}}$ is determined
for $F=\mathbb{F}_{2}$; this separating set is a proper subset of the one
given by the special case $q=2$ of our Theorem 5.3, as it involves a stronger
upper bound for the parameter $k$ in the multisymmetric polynomials included
in the separating set.

######  Example 5.5.

  * (i)

Take $q=3$, $m=2$, and $n=26$. The possible $\alpha$ to consider in the
separating set (19) in Theorem 5.3 for $A_{26,2}^{S_{26}}$ are $\alpha=(1,0)$,
$(0,1)$, $(1,1)$, $(2,1)$, $(1,2)$. The corresponding numbers
$\lfloor\log_{3}\frac{26}{|\alpha|}\rfloor$ are $2,2,2,1,1$. Thus in this case
the separating set (19) has $2\cdot(3+3+3+2+2)=26$ elements. The separating
set of $A_{n,m}^{S_{n}}$ given in Proposition 5.1 has $n(n(m-1)+1)$ elements
in general, so it has $26\cdot 27=702$ elements in our case $n=26$, $m=2$.

On the other hand, the number of $S_{26}$-orbits in
$\mathbb{F}_{3}^{26}\oplus\mathbb{F}_{3}^{26}$ is $\binom{34}{8}=18156204$.
Thus by [7, Theorem 1.1], there is a separating set in $A_{26,2}^{S_{26}}$
consisting of $\lceil\log_{3}\binom{34}{8}\rceil=16$ multisymmetric
polynomials.

  * (ii)

Take $q=3$, $m=2$, and $n=8$. The separating set (19) for $A_{8,2}^{S_{8}}$ in
Theorem 5.3 has $16$ elements, the separating set given in Proposition 5.2 has
$44$ elements, whereas the separating set given in Proposition 5.1 has $72$
elements. The minimal cardinality of a separating set for $A_{8,2}^{S_{8}}$
over $\mathbb{F}_{3}$ is $9$.

##  6\. Comment on lacunary polynomials

Lemma 4.6 has the following reformulation in terms of polynomials: The
elementary symmetric polynomial $s_{k}^{(n)}\in F[x_{1},\dots,x_{n}]$ is
irreplaceable if there exist two polynomials $f,g\in F[x]$ having degree at
most $n$ and constant term $1$ such that both $f$ and $g$ split as a product
of linear factors over $F$, the degree $k$ coefficient of $f$ differs from the
degree $k$ coefficient of $g$, and all the other coefficients of $f$ coincide
with the corresponding coefficient of $g$. This is reminiscent of the topic of
the book [9], where lacunary polynomials that split as a product of root
factors over $\mathbb{F}_{q}$ are studied.

In particular, our Corollary 2.2 has similar flavour as the following theorem
of Rédei [9, Paragraph 10]: Suppose that the polynomial $f(x)=x^{q}+g(x)$
splits as a product of root factors over the field $\mathbb{F}_{q}$, and the
formal derivative of $f$ is non-zero. Then $\deg(g)\geq(q+1)/2$ or
$f(x)=x^{q}-x$. For applications of this result in finite geometry see [12].

## References

  * [1] S. A. Amitsur, On the characteristic polynomial of a sum of matrices, Lin. Multilin. Alg. 8 (1980), 177-182.
  * [2] H. Derksen, G. Kemper, Computational Invariant Theory, Second Edition, Encyclopaedia of Mathematical Sciences 130, Invariant Theory of Algebraic Transformation Groups VIII, Springer-Verlag, Berlin, Heidelberg, 2015.
  * [3] M. Domokos, Vector invariants of a class of pseudorelflection groups and multisymmetric syzygies, J. Lie Theory 19 (2009), 507-525.
  * [4] J. Draisma, G. Kemper, D. Wehlau, Polarization of separating invariants, Canad. J. Math. 60 (2008), 556-571.
  * [5] M. Feshbach, The mod 2 cohomology rings of the symmetric groups and invariants, Topology 41 (2002), no. 1, 57-84.
  * [6] P. Fleischmann, A new degree bound for vector invariants of symmetric groups, Trans. Amer. Math. Soc. 350 (1998), no. 4, 1703-1712.
  * [7] G. Kemper, A. Lopatin, F. Reimers, Separating invariants over finite fields, J. Pure Appl. Alg. 226 (2022), paper no. 106904
  * [8] A. Lopatin, F. Reimers, Separating invariants for multisymmetric polynomials, Proc. Amer. Math. Soc. 149 (2021), 497-508.
  * [9] L. Rédei, Lückenhafte Polynome über endlichen Körpern, Birkhäuser Verlag, Basel, 1970 (English translation: Lacunary Polynomials over Finite Fields, North-Holland, Amsterdam, 1973).
  * [10] F. Reimers, Separating invariants for two copies of the natural $S_{n}$-action, Comm. Alg. 48 (2020), 1584-1590.
  * [11] D. Rydh, A minimal set of generators for the ring of multisymmetric functions, Ann. Inst. Fourier (Grenoble) 57 (2007), 1741-1769.
  * [12] T. Szőnyi, Around Rédei’s theorem, Discrete Math. 208/209 (1999), 557-575.
  * [13] F. Vaccarino, The ring of multisymmetric functions, Ann. Inst. Fourier (Grenoble) 55 (2005), no. 3, 717-731.