# A tensor restriction theorem over finite fields

Andreas Blatter  Mathematical Institute, University of Bern, Alpeneggstrasse
22, 3012 Bern, Switzerland<EMAIL_ADDRESS>,  Jan Draisma
Mathematial Institute, University of Bern, Sidlerstrasse 5, 3012 Bern,
Switzerland; and Department of Mathematics and Computer Science, P.O. Box 513,
5600 MB, Eindhoven, the Netherlands<EMAIL_ADDRESS>and  Filip
Rupniewski  Mathematical Institute, University of Bern, Alpeneggstrasse 22,
3012 Bern, Switzerland<EMAIL_ADDRESS>
###### Abstract.

Restriction is a natural quasi-order on $d$-way tensors. We establish a
remarkable aspect of this quasi-order in the case of tensors over a fixed
finite field—namely, that it is a well-quasi-order: it admits no infinite
antichains and no infinite strictly decreasing sequences. This result,
reminiscent of the graph minor theorem, has important consequences for an
arbitrary restriction-closed tensor property $X$. For instance, $X$ admits a
characterisation by finitely many forbidden restrictions and can be tested by
looking at subtensors of a fixed size. Our proof involves an induction over
polynomial generic representations, establishes a generalisation of the tensor
restriction theorem to other such representations (e.g. homogeneous
polynomials of a fixed degree), and also describes the coarse structure of any
restriction-closed property.

AB and FR are supported by Swiss National Science Foundation (SNSF) project
grant 200021_191981, and JD is partially supported by that grant and partially
supported by Vici grant 639.033.514 from the Netherlands Organisation for
Scientific Research (NWO). JD thanks the Institute for Advanced Study for the
excellent working conditions, under which part of this project was carried
out.

##  1\. Introduction and results

###  1.1. Tensor restriction

Let $K$ be a finite field and let $d$ be a natural number. This paper concerns
properties of $d$-way tensors that are preserved under taking linear maps. For
a vector space $V$ over $K$ we denote by $V^{\otimes d}$ the $d$-fold tensor
product $V\otimes V\otimes\cdots\otimes V$ over $K$, and for a linear map
$\varphi:V\to W$ we denote by $\varphi^{\otimes d}:V^{\otimes d}\to W^{\otimes
d}$ the linear map determined by

$\varphi^{\otimes d}(v_{1}\otimes\cdots\otimes
v_{d}):=\varphi(v_{1})\otimes\cdots\otimes\varphi(v_{d}).$

######  Definition 1.1.1.

Let $V,W$ be finite-dimensional vector spaces over $K$ and let $S\in
V^{\otimes d}$ and $T\in W^{\otimes d}$. We call $T$ a restriction of $S$ if
there exists a linear map $\varphi:V\to W$ such that $\varphi^{\otimes d}S=T$.
We then write $S\succeq T$.

The rationale for this terminology is that $S$ can be thought of as a
multilinear map $(V^{*})^{d}\to K$, and composing this map with
$(\varphi^{*})^{d}:(W^{*})^{d}\to(V^{*})^{d}$ gives the multilinear map $T$.
In particular, if $\varphi^{*}$ is injective, so that we can use it to
identify $W^{*}$ with a subspace of $V^{*}$, then we can think of $T$ as the
restriction of $S$ to the subspace $(W^{*})^{d}$.

######  Remark 1.1.2.

Much literature on tensors considers tensor products
$V_{1}\otimes\cdots\otimes V_{d}$ of different vector spaces $V_{i}$, and for
restriction allows the application of distinct linear maps
$\varphi_{i}:V_{i}\to W_{i}$ to the individual factors. The theorems that we
will prove imply the corresponding theorems for this setting; see Remark
1.6.3.

###  1.2. The tensor restriction theorem over finite fields

The relation $\succeq$ is reflexive and transitive, so it is a quasi-order on
tensors over $K$. We will prove that this quasi-order is a well-quasi-order.

######  Theorem 1.2.1 (Tensor restriction theorem).

Fix a natural number $d$. For every $i\in{\mathbb{N}}$ let $V_{i}$ be a
finite-dimensional vector space over the finite field $K$ and let $T_{i}\in
V_{i}^{\otimes d}$. Then there exist $i<j$ such that $T_{j}\succeq T_{i}$.

As the following example shows, the requirement that $K$ be finite is
essential.

######  Example 1.2.2.

If $|K|=\infty$, then the statement of the theorem fails already for $d=2$.
Indeed, if $\operatorname{char}K\neq 2$, then consider the matrices

$M_{a}:=\begin{bmatrix}1&a\\\ -a&1\end{bmatrix}\in(K^{2})^{\otimes 2}$

for $a$ ranging through $K$. If $M_{a}\succeq M_{b}$, then there exists a
matrix $g\in\operatorname{GL}\nolimits_{2}(K)$ such that $gM_{a}g^{T}=M_{b}$.
Looking at the symmetric parts of $M_{a}$ and $M_{b}$, we find that
$gIg^{T}=I$, so $g$ is an orthogonal matrix and $M_{a},M_{b}$ have the same
characteristic polynomial. But the characteristic polynomial of $M_{a}$ equals
$(t-1)^{2}-a^{2}$, so $M_{a}\succeq M_{b}$ holds (if and) only if
$a^{2}=b^{2}$. Since $|K|=\infty$, we have found infinitely many $2$-way
tensors that are incomparable with respect to $\succeq$. A similar
construction works when $\operatorname{char}K=2$. It is easy to see that the
failure for $d=2$ implies the failure for all larger $d$.

###  1.3. Consequences of the tensor restriction theorem

The tensor restriction theorem is reminiscent of the celebrated graph minor
theorem [RS04], which says that finite graphs are well-quasi-ordered by the
minor order. We are not aware of any logical dependence between these
theorems, but the tensor restriction theorem has similar far-reaching
consequences for tensors as the graph minor theorem has for graphs. These
consequences are best formulated using the following notion.

######  Definition 1.3.1.

A restriction-closed property of $d$-way tensors is a property such that if a
tensor $S$ has it, and $S\succeq T$ holds, then also $T$ has it. We can
identify such a property with the data of a subset $X(V)\subseteq V^{\otimes
d}$ for all every finite-dimensional vector space $V$ over $K$, such that if
$\varphi:V\to W$ is a linear map, then $\varphi^{\otimes d}$ maps $X(V)$ into
$X(W)$.

######  Example 1.3.2.

Let $T\in W^{\otimes d}$. Then the property of not having $T$ as a restriction
is restriction-closed. We denote this property by $X_{\not\succeq T}$.

If $X$ is a restriction-closed property, and $T$ is a tensor that does not
satisfy it, then we call $T$ a forbidden restriction for $X$.

######  Corollary 1.3.3.

For $d$-way tensors over the fixed finite field $K$ the following hold.

  1. (1)

Restriction-closed properties satisfy the descending chain condition: any
chain $X_{1}\supseteq X_{2}\supseteq\ldots$ of such properties stabilises.

  2. (2)

Every restriction-closed property $X$ is characterised by finitely many
forbidden restrictions, i.e., we have $X=\bigcap_{i=1}^{k}X_{\not\succeq
T_{i}}$ for some $k$ and some tensors $T_{i}\in V_{i}^{\otimes d}$.

  3. (3)

For every restriction-closed property $X$ there exists a finite-dimensional
vector space $U$ such that for any $V$ and any $T\in V^{\otimes d}$, we have
$T\in X(V)$ if (and only if) $\varphi^{\otimes d}T\in X(U)$ for all linear
maps $\varphi:V\to U$.

  4. (4)

For every restriction-closed property $X$ there exists a number $n_{0}$ such
that a tensor $T\in(K^{n})^{\otimes d}$ satisfies $X$ if and only if for every
subset $S\subseteq[n]:=\\{1,\ldots,n\\}$ of size $n_{0}$ the sub-tensor of $T$
in $(K^{S})^{\otimes d}$ satisfies $X$.

  5. (5)

For every restriction-closed property $X$ there exists a polynomial-time
deterministic algorithm that on input $n$ and a $T\in(K^{n})^{\otimes d}$
decides whether $T$ satisfies $X$.

The proofs of (1), (2), and (3) are straightforward from the tensor
restriction theorem, and conversely the tensor restriction theorem follows
from each of these.

###### Proofs of (1),(2),(3) from the tensor restriction theorem and vice
versa..

Assuming the tensor restriction theorem, we prove (1): whenever $X_{i}$ and
$X_{i+1}$ are not the same property, there exists a tensor $T_{i}$ that
satisfies $X_{i}$ but not $X_{i+1}$. For $i<j$ we then have $T_{j}\not\succeq
T_{i}$, and hence $X_{i}\neq X_{i+1}$ holds only finitely many times.

Next we prove (1) $\Rightarrow$ (2). Start with $k=0$. While $X$ is strictly
contained in $X_{k}:=\bigcap_{i=1}^{k}X_{\not\succeq T_{i}}$, there is a
tensor $T_{k+1}$ that does not satisfy $X$ but does not have any of the
tensors $T_{1},\ldots,T_{k}$ as a restriction. This yields a strictly
descending chain $X_{0}\supsetneq X_{1}\supsetneq\ldots$, which by (1) must
terminate, so that $X$ is equal to $X_{k}$ for some $k$.

For (2) $\Rightarrow$ (3), we take for $U$ any space of dimension at least
that of all of the spaces $V_{i},\ i=1,\ldots,k$, where $T_{i}\in
V_{i}^{\otimes d}$. If $T\in V^{\otimes d}$ does not lie in $X(V)$, then it
has a restriction equal to some $T_{i}$, so that $\psi^{\otimes d}T=T_{i}$ for
some linear map $\psi:V\to V_{i}$. Now $\psi$ factors via a linear map
$\varphi:V\to U$, and it follows that $\varphi^{\otimes d}T\not\in X(U)$.

Finally, (3) implies the tensor restriction theorem: let $T_{i}\in
V_{i}^{\otimes d},\ i=1,2,\ldots$, and define
$X_{n}:=\bigcap_{i=1}^{n}X_{\not\succeq T_{i}}$ and
$X:=\bigcap_{i=1}^{\infty}X_{\not\succeq T_{i}}$. Let $U$ be as in (3) for
$X$. Then, since $X_{0}(U)$ is a finite set, the chain of subsets

$X_{0}(U)\supseteq X_{1}(U)\supseteq\ldots$

stabilises after finitely many steps: $X_{n}(U)=X(U)$. Then in particular
$T_{n+1}$, which is not in $X(V_{n+1})$, is not in $X_{n}(V_{n+1})$, which
means that it must have some $T_{i}$ with $i\leq n$ as a restriction. ∎

Note that the difference between (3) and (4) is that in (4) we only consider
coordinate projections $K^{n}\to K^{I}$. The proof of (4) is slightly more
involved and deferred to §5.1. Once (4) is established, however, (5) is
immediate, since there are only $\binom{n}{n_{0}}$ subsets $I$ of size
$n_{0}$, and this is a polynomial in $n$. Note that for this proof it does not
matter whether the tensor in (5) is given in dense input form (an array of
$n^{d}$ elements from $K$) or in sparse form (a list of tuples
$(i_{1},\ldots,i_{d},a)$ where $(i_{1},\ldots,i_{d})$ specifies the position
of a tensor entry and $a\in K$ its value).

######  Remark 1.3.4.

Versions of (1),(3),(4), and (5) also hold for restriction-closed tensor
properties over an infinite field, provided that the tensor property can be
expressed by polynomial equations in the tensor entries. For (1),(3) this
follows from [Dra19]. For (4),(5), this follows from (1),(3) and the technique
in §5.1 below.

###  1.4. Restriction-monotone functions

Tensor restriction plays an important role in theoretical computer science, in
particular through many notions of tensor rank, of which we briefly discuss
two here.

######  Definition 1.4.1.

The rank $\operatorname{rk}(S)$ of $S\in V^{\otimes d}$ is the minimal $r$
such that $S$ can be written as

$S=\sum_{i=1}^{r}v_{i,1}\otimes\cdots\otimes v_{i,d}$

for suitable vectors $v_{i,1},\ldots,v_{i,d}$. The asymptotic rank of $S$ is
the limit

$\lim_{t\to\infty}\sqrt[t]{\operatorname{rk}(S^{\boxtimes t})},$

where the vertical tensor product $S^{\boxtimes t}$ is the $d$-way tensor in
$(V^{\otimes t})^{\otimes d}$ obtained by tensoring $t$ copies of $S$ and
grouping together the $t$ copies of the first copy of $V$, the $t$ copies of
the second copy, and so on.

If $S\succeq T$, then $\operatorname{rk}(S)\geq\operatorname{rk}(T)$ and
$S^{\boxtimes t}\succeq T^{\boxtimes t}$ for every natural number $t$, so that
also the asymptotic rank of $S$ is at least that of $T$. This shows that rank
and asymptotic rank are both monotone in the following sense.

######  Definition 1.4.2.

A function $f$ that assigns to any $d$-way tensor a real number is called
restriction-monotone if $S\succeq T$ implies that $f(S)\geq f(T)$.

######  Corollary 1.4.3.

Let $f$ be any restriction-monotone function on $d$-way tensors over the
finite field $K$. Then the set of values of $f$ in ${\mathbb{R}}$ is a well-
ordered set.

###### Proof.

If not, then there exist tensors $T_{1},T_{2},\ldots$ on which $f$ takes
values $a_{1}>a_{2}>\ldots$. Let $X_{\leq a_{i}}$ be the tensor property of
having $f$-value $\leq a_{i}$. Since $f$ is restriction-monotone, this
property is restriction-closed. Furthermore, since $T_{i}\in X_{\leq
a_{i}}\setminus X_{\leq a_{i+1}}$, we have

$X_{\leq a_{1}}\supsetneq X_{\leq a_{2}}\supsetneq\ldots$

But this contradicts Corollary 1.3.3, part (1). ∎

In particular, the set of asymptotic ranks of $d$-way tensors over a fixed
finite field is well-ordered.

######  Example 1.4.4.

Take $d=3$. By Corollary 1.4.3, the set $S\subseteq{\mathbb{R}}_{\geq 0}$ of
asymptotic ranks of $3$-way tensors is well-ordered. This means that
$S\setminus[0,4]$ contains a minimal element $4+\epsilon$ with $\epsilon>0$.
Hence in particular, the asymptotic rank of $2\times 2$-matrix multiplication,
a tensor in $K^{4}\otimes K^{4}\otimes K^{4}$, is either $4$ (which is
equivalent to the well-known conjecture that the exponent of matrix
multiplication over $K$ is $2$; see [CGL+21]) or at least $4+\epsilon$. We
point out, though, that we do not know whether asymptotic ranks of tensors
over an infinite field are well-ordered, because the property of having
asymptotic rank at most some real number is not (evidently, at least!) a
Zariski-closed property—see Remark 1.3.4.

######  Example 1.4.5.

Another notion of rank that is restriction-monotone is analytic rank [Lov19].
Fix a non-trivial character (group homomorphism)
$\chi:(K,+)\to({\mathbb{C}}^{*},\cdot)$. Thinking of $T\in V^{\otimes d}$ as a
multilinear form $(V^{*})^{d}\to K$, the analytic rank of $T$ equals

$-\log_{|K|}\mathbb{E}(\chi(T(x_{1},\ldots,x_{d}))),$

where $\mathbb{E}$ stands for expectation in the probabilistic model where
$(x_{1},\ldots,x_{d})$ is picked uniformly at random in $(V^{*})^{d}$. The
analytic rank is restriction-monotone be Lemma 1.4.6 below. Hence, by
Corollary 1.4.3, the set of analytic ranks of $d$-linear forms over $K$ is a
well-ordered subset of the real numbers.

The following is well-known to experts, but we did not find a proof in the
published literature, so we provide one here.

######  Lemma 1.4.6.

The analytic rank is restriction-monotone.

###### Proof.

It is convenient to see this in the more general setting of Remark 1.1.2,
where we have different vector spaces $V_{1},\ldots,V_{d}$ and $T\in
V_{1}\otimes\cdots\otimes V_{d}$ is a regarded as a multilinear function
$V_{1}^{*}\times\cdots\times V_{d}^{*}\to K$.

Consider a linear map $\varphi:V_{d}\to W$ and define
$T^{\prime}:=\operatorname{id}_{V_{1}}\otimes\cdots\otimes\operatorname{id}_{V_{d-1}}\otimes\varphi$.
For fixed $(x_{1},\ldots,x_{d-1})\in V_{1}^{*}\times\cdots\times V_{d-1}^{*}$,
the linear form $T(x_{1},\ldots,x_{d-1},\cdot)$ is either zero, in which case
$\chi(T(x_{1},\ldots,x_{d-1},x_{d}))=1$ for all $|V_{d}|$ choices of $x_{d}$,
or it is nonzero, in which case, as $x_{d}$ varies through $V$,
$T(x_{1},\ldots,x_{d})$ takes all values equally often, and therefore the
values of $\chi$ cancel out. We conclude that the expectation in the analytic
rank of $T$ equals

$a|V_{d}|/(|V_{1}|\cdots|V_{d}|)$

where $a$ is the number of tuples $(x_{1},\ldots,x_{d-1})$ for which the
linear form is zero. By the same reasoning, the expectation in the analytic
rank of $T^{\prime}$ equals

$a^{\prime}|W|/(|V_{1}|\cdots|V_{d-1}|\cdot|W|)$

where now $a^{\prime}$ is the number of tuples $(x_{1},\ldots,x_{d-1},\cdot)$
for which $T(x_{1},\ldots,x_{d-1})$ is zero on the image of
$\varphi^{*}:W^{*}\to V^{*}$. Now $a^{\prime}\geq a$ and therefore the
expression for $T^{\prime}$ is at least that for $T$. Taking $-\log_{|K|}$ on
both sides, and repeating this argument with linear maps in the other $d-1$
tensor factors, we are done. ∎

###  1.5. Generic representations

Let $\mathbf{Vec}$ be the category of finite-dimensional vector spaces over
the finite field $K$.

######  Definition 1.5.1.

A generic representation is a functor $F:\mathbf{Vec}\to\mathbf{Vec}$.

The terminology is explained by the observation that if $F$ is a generic
representation, then for each $n$, $F(K^{n})$ is a representation of the
finite group $\operatorname{GL}\nolimits_{n}(K)$ and of the finite monoid
$\operatorname{End}\nolimits(K^{n})$ of $n\times n$-matrices. Generic
representations can therefore be thought of as sequences of representations of
$\operatorname{End}\nolimits(K^{n})$, one for each $n$, that depend in a
suitably generic manner on $n$. Generic representations form an abelian
category in which the morphisms are natural transformations.

######  Example 1.5.2.

Here are two rather different examples of generic representations:

  1. (1)

the functor $T^{d}$ that sends $V$ to $V^{\otimes d}$ and $\varphi:V\to W$ to
$\varphi^{\otimes d}$; and

  2. (2)

the functor that sends $V$ to the $K$-vector space $KV$ with basis $V$ and
$\varphi:V\to W$ to the unique linear map $KV\to KW$ that sends the basis
vector $v\in V$ to the basis vector $\varphi(v)\in W$.

The following beautiful theorem characterises a particularly nice class of
generic representations.

######  Theorem 1.5.3 ([Kuh94a, Theorem 4.14]).

For a generic representation $F:\mathbf{Vec}\to\mathbf{Vec}$ the following
properties are equivalent:

  1. (1)

$F$ has a finite composition series in the abelian category of generic
representations;

  2. (2)

the function $d_{F}:{\mathbb{Z}}_{\geq 0}\to{\mathbb{Z}}_{\geq 0}$ defined by
$d_{F}(n):=\dim F(K^{n})$ is (bounded above by) a polynomial in $n$; and

  3. (3)

$F$ is a subquotient of a finite direct sum $T^{d_{1}}\oplus\cdots\oplus
T^{d_{n}}$ for suitable $d_{1},\ldots,d_{n}\in{\mathbb{Z}}_{\geq 0}$.

We call a generic representations satisfying any of the equivalent properties
above polynomial. Often, we will drop the adjective generic and just speak of
polynomial representations.

######  Example 1.5.4.

The generic representation $V\mapsto V^{\otimes d}$ is polynomial, and so is
the generic representation $V\mapsto S^{d}V$. The generic representation
$V\mapsto KV$ is not polynomial, because $\dim KV=|V|=|K|^{\dim V}$ is
exponential in $\dim V$.

###  1.6. The restriction theorem for polynomial representations

The tensor restriction theorem generalises as follows.

######  Theorem 1.6.1 (The restriction theorem in polynomial representations).

Let $P$ be a polynomial generic representation over the finite field $K$ and
for $i\in{\mathbb{N}}$ let $T_{i}\in P(V_{i})$. Then there exist $i<j$ and a
linear map $\varphi:V_{j}\to V_{i}$ such that $T_{i}=P(\varphi)T_{j}$.

We will use the term restriction also in this more general context, i.e., the
conclusion of the theorem says that $T_{i}$ is a restriction of $T_{j}$.

######  Remark 1.6.2.

The condition that $P$ be polynomial cannot be dropped. For instance, let $P$
be the functor that sends $V$ to $KV$. For each $n\geq 3$ let $T_{n}\in
P(K^{n-1})$ be the formal sum

$T_{n}:=v_{1}+\cdots+v_{n}\in P(K^{n-1})$

where $\\{v_{1},\ldots,v_{n}\\}\in K^{n-1}$ is a circuit: any $n-1$ of the
$v_{i}$ are a basis of $K^{n-1}$. We stress that in $P(K^{n-1})$ the $v_{i}$
are basis vectors, and $T_{n}$ is the sum of these basis vectors. We claim
that no $T_{n}$ is a restriction of any $T_{m}$ with $m\neq n$. Indeed, if it
were, then writing $T_{m}=v^{\prime}_{1}+\cdots+v^{\prime}_{m}$, there would
be a linear map $K^{m-1}\to K^{n-1}$ that maps the circuit
$\\{v_{1}^{\prime},\ldots,v_{m}^{\prime}\\}$ to the circuit
$\\{v_{1},\ldots,v_{n}\\}$. By basic linear algebra, such linear maps do not
exist.

Corollary 1.3.3 generalises verbatim to polynomial representations, and so
does Corollary 1.4.3.

######  Remark 1.6.3.

Versions of the Theorem 1.6.1 and its corollaries also hold for multivariate
polynomial representations, defined as functors
$P:\mathbf{Vec}^{k}\to\mathbf{Vec}$ for which
$\dim_{K}P(K^{n_{1}},\ldots,K^{n_{k}})$ is a polynomial in
$n_{1},\ldots,n_{k}$. Indeed, given elements $T_{i}\in
P(V_{i}^{(1)},\ldots,V_{i}^{(k)})$ for $i=1,2,\ldots$, we can choose linear
injections $\iota_{i}^{(j)}$ from $V_{i}^{(j)}$ into a $U_{i}\in\mathbf{Vec}$
(which depends only on $i$), and linear surjections $\pi_{i}^{(j)}:U_{i}\to
V_{i}^{(j)}$ with
$\pi_{i}^{(j)}\circ\iota_{i}^{(j)}=\operatorname{id}_{V_{i}^{(j)}}$. Then
define

$T_{i}^{\prime}:=P(\iota_{i}^{(1)},\ldots,\iota_{i}^{(k)})T_{i}\in
P(U_{i},\ldots,U_{i})=:Q(U_{i})$

where $Q$ is now a univariate polynomial generic representation. Theorem 1.6.1
applied to $Q$ says that there exist $i<j$ and a linear map $\psi:U_{j}\to
U_{i}$ such that

$Q(\psi)T_{j}^{\prime}=P(\psi,\ldots,\psi)T_{j}^{\prime}=T_{i}^{\prime}.$

We then have

$P(\pi_{i}^{(1)}\circ\psi\circ\iota_{j}^{(1)},\ldots,\pi_{i}^{(k)}\circ\psi\circ\iota_{j}^{(1)})T_{j}=T_{i},$

as desired.

###  1.7. Proof strategy: the polynomial method

Rather than proving the restriction theorem for polynomial representations
directly, we will prove Noetherianity, corresponding to (1) in Corollary
1.3.3: if $P$ is a polynomial representation, and $X_{1}\supseteq
X_{2}\supseteq\ldots$ are restriction-closed properties, then $X_{n}=X_{n+1}$
for all sufficiently large $n$.

To establish Noetherianity, we adapt the proof method of [Dra19] for
polynomial functors over infinite fields to our current setting. This is far
from straightforward. For instance, a polynomial functor over an infinite
field and its coordinate ring both have a ${\mathbb{Z}}_{\geq 0}$-grading,
whereas a polynomial representation over the finite field $K$ and its
coordinate ring only have a grading by $\\{0,1,\ldots,|K|-1\\}$. Nevertheless,
after introducing the degree $d$ of the polynomial representation $P$, we show
that $P$ has a unique minimal sub-representation $P_{>d-1}$ the quotient by
which has degree at most $d-1$. We think of $P_{>d-1}$ as the top-degree part
of $P$. We then take an irreducible sub-representation $R$ in $P_{>d-1}$, and
assume that the Noetherianity statement holds for $P/R$ and various other
polynomial representations that have the same top-degree part as $P/R$ and are
therefore in a lexicographic sense smaller than $P$. This means that if
$X_{1}\supseteq X_{2}\supseteq\ldots$ is a chain of restriction-closed
properties in $P$, then their projections $X^{\prime}_{1}\supseteq
X^{\prime}_{2}\supseteq\ldots$ in $P/R$ stabilise. Therefore, it suffices to
prove Noetherianity for properties $X\subseteq P$ that have a fixed projection
$X^{\prime}\subseteq P/R$. Then, to prove that any property $X\subseteq P$
with projection $X^{\prime}$ is Noetherian, we think of each $X(V)$ as a
Zariski-closed subset of $P(V)$, i.e., as given by polynomial equations in the
finite vector space $P(V)$. We do induction on the minimal degree of an
equation that vanishes identically on $X$ but not on $X^{\prime}$. Using
spreading operators we show that from such an equation we can construct many
equations of the same degree that are affine-linear in the $R$-direction. This
allows us to embed a certain subset of $X$ into a strictly smaller polynomial
functor, while on the complement of that subset a polynomial of strictly
smaller degree vanishes. Both subsets can therefore be handled by induction.

We stress that this proof never actually looks at concrete tensors or elements
of $P(V)$—all reasoning uses polynomial equations, and exploits the fact that
every subset of a finite vector space is given by polynomial equations. In
this sense, the proof can be regarded an instance of the polynomial method.

We remark that polynomial generic representations are not the same thing as
strict polynomial functors in the sense of Friedlander-Suslin [FS97]. Roughly
speaking, while former deal with sequences of representations of the finite
groups $\operatorname{GL}\nolimits_{n}(K)$, the latter deal with sequences of
algebraic representations of the group schemes
$\operatorname{GL}\nolimits_{n}$. Topological Noetherianity of strict
polynomial functors, over arbitrary rings with Noetherian spectrum and hence
certainly over finite fields, was established in [BDD20], using the techniques
from [Dra19]. However, strict polynomial functors have a scheme structure
built in and are therefore much more amenable to the techniques of [Dra19]
than the polynomial generic representations that we study here. Furthermore,
even if one is interested only in polynomial generic representations that come
from strict polynomial functors by forgetting some of the data—such as the
functor $V\mapsto V^{\otimes d}$—our proof, in which we mod out an irreducible
subrepresentation $R$, requires that one leaves the realm of these special
representations. This explains the need for the new ideas developed in this
paper.

###  1.8. Further relations to the literature

Restriction-closed properties of tensors are a rapidly expanding research
area. Here is a very small selection of recent research related to our work.

In [Kar22] it is proved, for various notions of rank including ordinary tensor
rank, slice rank, and partition rank, that a large tensor of rank $r$ has a
sub-tensor whose size depends only on $r$ and whose rank is at least some
function of $r$. For finite fields, this result also follows from Corollary
1.3.3, item (3)—in fact, by that item, a subtensor of fixed size can be found
of rank equal to $r$. However, Karam also finds an explicit formula for the
size, while our theorem does not give such a bound. It would be very
interesting to see whether the proof of our theorem could shed further light
on such bounds.

In [CM21] it is proved that over sufficiently large fields, partition rank is
bounded by a linear function of the analytic rank of a tensor; and in [MZ22]
the condition on the field size is removed at the cost of a polylogarithmic
factor. This is the culmination of many years of research by many authors into
the relation between bias and rank of tensors, starting with [GT09] via
polynomial bounds in [Mil19] and linear bounds for trilinear forms in [AKZ21].
Using the proof of our tensor restriction theorem and techniques from [BDE19],
it is easy to recover the result that partition rank is bounded from above by
at least some function of the analytic rank. However, again, our techniques do
not yield bounds that can compete with the state of the art.

In [CGL+21], motivated by Strassen’s asymptotic rank conjecture that says that
any tight tensor has the minimal possible asymptotic rank, the authors study
the geometry of various varieties of tensors, such as the (closure of) the set
of tight tensors. It would be interesting to study these varieties from the
perspective of this paper (over finite fields) and from the perspective of
[BDES21] (over infinite fields). In both cases, after a shift and a
localisation, these varieties become of the form a fixed finite-dimensional
variety times an affine space that depends on the size of the tensor. Over
infinite fields, this follows from the shift theorem in [BDES21], and over
finite fields, it follows from the weak shift theorem in this paper.

In [PS17] and [SS17], the long-standing Lannes-Schwartz Artinian conjecture
was resolved, which says that any finitely generated (not necessarily
polynomial!) generic representation $F:\mathbf{Vec}\to\mathbf{Vec}$ is
Noetherian in the module sense: it satisfies the ascending chain condition on
subrepresentations. Dually, this means that any descending chain of
subrepresentations of $F^{*}:V^{*}\mapsto F(V)^{*}$ stabilises. Interpreting
the elements of $F(V)$ as linear functions on $F(V)^{*}$, one may interpret
this as Noetherianity for linear functorial subsets of $F^{*}$. However,
already for $F:V\mapsto K\cdot V$, one can show that $F^{*}$ does not satisfy
the descending chain condition on nonlinear subsets. So topological
Noetherianity as we prove it seems restricted only to polynomial generic
representations. It would be nice to know a precise statement to this effect.
For instance, is it true that the only generic representations for which the
restriction theorem holds are the polynomial representations?

In [Sno21], Snowden extends many results about
$\operatorname{GL}\nolimits$-algebras from [BDES21] to modules over
$\operatorname{GL}\nolimits$-algebras equipped with a compatible
$\operatorname{GL}\nolimits$-action. Along the way, he also gives a proof of
the shift theorem that differs slightly from the proof in [BDES21], and which
uses the search for an element of weight $(1,\ldots,1)$ in a suitable
$\operatorname{GL}\nolimits$-representation. This inspired the development of
weight theory in our current, different context in §3 and the idea that a
suitably spread out element in the vanishing ideal of a tensor property would
have weight $(1,\ldots,1)$—a key insight in the proof of the embedding theorem
in §4.6.

###  1.9. Organisation of this paper

In Section 2 we discuss the theory of generic polynomial representations,
including the definition of top-degree parts and shift functors. In
particular, we will see that the ring of functions on a polynomial
representation is itself a countable union of polynomial representations.

In Section 3, we develop a partial analogue of the classical weight theory for
representations of group schemes $\operatorname{GL}\nolimits_{n}$. This
includes the spreading operators alluded to above. Since functions on a
polynomial representation themselves live in a polynomial representation,
these spreading operators also act on functions.

In Section 4 we prove Noetherianity for polynomial representations over the
fixed finite field $K$, which implies the restriction theorems for tensors and
polynomial representations and items (1)-(3) of Corollary 1.3.3, both for
tensors and for polynomial representations, and also implies the existence of
a unique decomposition of a restriction-closed tensor property into
irreducible such properties; see Theorem 4.2.2. We do so by first deriving
Noetherianity from an auxiliary result that we call the embedding theorem,
since it is the finite-field analogue of the embedding theorem in [BDES21].
The proof of the embedding theorem, then, is the heart of the paper. We also
derive from it a version of the shift theorem in [BDES21].

Finally, in Section 5 we use the theory of finitely generated FI-modules to
prove item (4) from Corollary 1.3.3; as we have seen, (5) is then a direct
consequence.

### Acknowledgments

We thank Nate Harman and Andrew Snowden for useful discussions and for
references to relevant literature.

##  2\. Polynomial generic representations

Throughout the paper, $K$ is a fixed finite field, with $q$ elements. All
linear and multilinear algebra will be over $K$. We denote by $\mathbf{Vec}$
the category of finite-dimensional $K$-vector spaces, and for
$V\in\mathbf{Vec}$ we denote the dual space by $V^{*}$.

###  2.1. Functions as polynomials

We introduce the ring of functions on a vector space; we will also call this
the coordinate ring.

######  Definition 2.1.1.

Given $V\in\mathbf{Vec}$, we write $K[V]$ for the $K$-algebra of functions
$V\to K$. This has a natural algebra filtration

$\\{0\\}=K[V]_{\leq-1}\subseteq K[V]_{\leq 0}\subseteq K[V]_{\leq 1}\subseteq
K[V]_{\leq 2}\subseteq\dots$

where $K[V]_{\leq d}$ is the set of functions $f:V\to K$ for which there
exists an element of $\bigoplus_{e=0}^{d}S^{e}V^{*}$ that defines the function
$f$.

We stress that $K[V]$ is an algebra of functions, not of polynomials. More
precisely, $K[V]$ is the quotient of the symmetric algebra $SV^{*}$ by the
ideal generated by the polynomials $x^{q}-x$ as $x$ runs through (a basis of)
$V^{*}$. Since these polynomials are not homogeneous, $K[V]$ has no natural
grading—but as seen above, it does have a natural filtration.

Note further that $K[V]$ is a finite-dimensional $K$-vector space, of
dimension $q^{\dim(V)}$, the number of elements of $V$.

######  Definition 2.1.2.

Given a basis $x_{1},\dots,x_{n}$ of $V^{*}$, every element $f$ of $K[V]$ has
a unique representative polynomial in which all exponents of all variables are
$\leq q-1$; we will call this representative—which depends on the choice of
basis—the reduced polynomial representation for $f$ relative to the choice of
coordinates.

The following lemma is immediate; the natural isomorphisms in it will be
interpreted as equalities throughout the paper.

######  Lemma 2.1.3.

For $V,W\in\mathbf{Vec}$ we have $K[V\times W]\cong K[V]\otimes K[W]$ via the
$K$-linear map map from right to left that sends $f\otimes g$ to the function
$(v,w)\mapsto f(v)g(w)$; this is a $K$-algebra isomorphism.

Similarly, the set of arbitrary maps $V\to W$ is canonically isomorphic to
$K[V]\otimes W$ via the $K$-linear map from right to left that sends $f\otimes
w$ to the function $v\mapsto f(v)\cdot w$. $\square$

Furthermore, we write $K[V]_{0}=K$ for the sub-$K$-algebra of constant
functions, and $K[V]_{>0}$ for the $K$-vector space spanned by all functions
that vanish at zero.

###  2.2. Polynomial generic representations over $K$

Recall Theorem 1.5.3, which characterises polynomial representations among all
generic representations. We will use the following, alternative
characterisation instead.

######  Definition 2.2.1.

A generic representation $P:\mathbf{Vec}\to\mathbf{Vec}$ is called polynomial
if there exists a $d$ such that for all $U,V\in\mathbf{Vec}$ the map
$P:\operatorname{Hom}\nolimits(U,V)\to\operatorname{Hom}\nolimits(P(U),P(V))$
lies in $K[\operatorname{Hom}\nolimits(U,V)]_{\leq
d}\otimes\operatorname{Hom}\nolimits(P(U),P(V))$. The minimal such
$d\in{\mathbb{Z}}_{\geq-1}$ is called the degree of $P$ and denoted $\deg(P)$.

Polynomial representations form an Abelian category, in which the morphisms
are natural transformations.

Any polynomial representation in the sense of Theorem 1.5.3 is a subquotient
of a direct sum $T^{d_{1}}\oplus\cdots\oplus T^{d_{k}}$’s, and this implies
that it is polynomial in the sense of the definition above, of degree at most
the maximum of the $d_{i}$. In Remark 2.4.2, we will see that, conversely, any
generic representation that is polynomial in the sense of the definition above
is polynomial in the sense of Theorem 1.5.3.

Every finite-degree strict polynomial functor $\mathbf{Vec}\to\mathbf{Vec}$ in
the sense of Friedlander-Suslin [FS97] gives rise to a polynomial
representation. But this forgetful functor is not an equivalence of abelian
categories. For instance, if $Q$ is a strict polynomial functor of degree $d$
over $K$, then its $q$-Frobenius twist is a polynomial functor of degree $dq$
over $K$ and hence not isomorphic to $Q$. However, $Q$ and its $q$-Frobenius
twist give rise to the same generic representation.

###  2.3. Schur algebras over $K$

In spite of the discrepancy between strict polynomial functors and polynomial
generic representations, a version of the theorem by Friedlander and Suslin
that relates polynomial functors to representations of the Schur algebra, does
hold.

Fix a natural number $d$ and a $U\in\mathbf{Vec}$. The composition map
$\operatorname{End}\nolimits(U)\times\operatorname{End}\nolimits(U)\to\operatorname{End}\nolimits(U)$
gives rise, via pullback of functions, to a $K$-linear map

$K[\operatorname{End}\nolimits(U)]_{\leq d}\to
K[\operatorname{End}\nolimits(U)]_{\leq d}\otimes
K[\operatorname{End}\nolimits(U)]_{\leq d}.$

We write $A_{\leq d}(U):=K[\operatorname{End}\nolimits(U)]_{\leq d}^{*}$.
Dualising the map above, we obtain a $K$-bilinear map

$A_{\leq d}(U)\times A_{\leq d}(U)\to A_{\leq d}(U).$

A straightforward computation, using the associativity of composition of
linear maps, shows that this turns $A_{\leq d}(U)$ into a unital, associative
algebra, with unit element $f\mapsto f(\operatorname{id}_{U})$.

######  Definition 2.3.1.

The unital, associative algebra $A_{\leq d}(U)$ with the multiplication above
is called the Schur algebra over $K$.

We remark that this is in fact a subalgebra of the Schur algebra in [FS97],
which is the dual space to the space of degree at most $d$ polynomials on
$\operatorname{End}\nolimits(U)$. Our Schur algebra consists of only those
linear functions that vanish on the ideal of polynomials that define the zero
function on $\operatorname{End}\nolimits(U)$.

The Schur algebra comes with a homomorphism of monoids (not of $K$-algebras)
$\operatorname{End}\nolimits(U)\to A_{\leq d}(U)$ defined by
$\varphi\mapsto(f\mapsto f(\varphi))$. This homomorphism is an embedding if
$d\geq 1$.

###  2.4. A finite-field analogue of the Friedlander-Suslin lemma

Given a polynomial generic representation $P$ of degree at most $d$ and a
vector space $U$, we turn $P(U)$ into an $A_{\leq d}(U)$-module by a
construction very similar to the construction of $A_{\leq d}(U)$: first, the
map

$\operatorname{End}\nolimits(U)\times P(U)\to P(U),(\varphi,p)\mapsto
P(\varphi)(p)$

gives rise, via pull-back, to a $K$-linear map

$P(U)^{*}\to K[\operatorname{End}\nolimits(U)]_{\leq d}\otimes P(U)^{*}.$

Dualising, we obtain a $K$-bilinear map

$A_{\leq d}(U)\times P(U)\to P(U)$

that turns $P(U)$ into a (unital) $A_{\leq d}(U)$-module.

The following proposition is proved exactly as Friedlander-Suslin’s
corresponding theorem, and it is also almost equivalent to [Kuh94a]Proposition
4.10.

######  Proposition 2.4.1.

Fix a natural number $d$ and a $U\in\mathbf{Vec}$ of dimension at least $d$.
Then $P\mapsto P(U)$ is an equivalence of Abelian categories from the category
of polynomial generic representations $\mathbf{Vec}\to\mathbf{Vec}$ of degree
$\leq d$ to the category of $A_{\leq d}(U)$-representations. $\square$

######  Remark 2.4.2.

It follows from this proposition that every polynomial representation of
degree $\leq d$ in the sense of Definition 2.2.1 has finite length. Therefore,
it is also polynomial in the sense of Theorem 1.5.3.

######  Remark 2.4.3.

If $P$ is an irreducible polynomial generic representation, then for each
$U\in\mathbf{Vec}$, $P(U)$ is (zero or) an irreducible
$\operatorname{End}\nolimits(U)$-module. Indeed, if $M$ were a nonzero proper
submodule, then, for varying $V$, $Q(V):=\\{p\in
P(V)\mid\forall\varphi\in\operatorname{Hom}\nolimits_{\mathbf{Vec}}(V,U)P(\varphi)p\in
M\\}$ would define a nonzero proper subrepresentation.

###  2.5. Filtering a polynomial representation by degree

A strict polynomial functor in the sense of Friedlander-Suslin has a grading
by degree. In contrast, we will see that a polynomial generic representation
only has a filtration by degree. One notable exception is the degree-zero part
of a polynomial representation.

######  Definition 2.5.1.

Let $P:\mathbf{Vec}\to\mathbf{Vec}$ be a polynomial generic representation.
Then we define $P_{0}:\mathbf{Vec}\to\mathbf{Vec}$ by $P_{0}(V):=P(0)=:U$ for
all $V\in\mathbf{Vec}$ and $P_{0}(\varphi):=\operatorname{id}_{U}$ for all
$\varphi\in\operatorname{Hom}\nolimits_{\mathbf{Vec}}(V,W)$. This is a direct
summand of $P$ in the Abelian category of polynomial generic representations,
called the degree-zero part or constant part of $P$; we will also informally
say that $U$ is the constant part of $P$. The constant part $P_{0}$ has a
unique complement in $P$, namely,

$\displaystyle P_{>0}(V):=\\{p\in P(V)\mid$ $\displaystyle
P(0\cdot\operatorname{id}_{V})p=0\\}$

A polynomial representation $P$ of degree at most some $e\leq d$ is in
particular a polynomial representation of degree at most $d$. On the Schur
algebra side, this inclusion of Abelian categories is made explicit as
follows: take a vector space $U$ of dimension at least $d$. Then the inclusion
$K[\operatorname{End}\nolimits(U)]_{\leq e}\to
K[\operatorname{End}\nolimits(U)]_{\leq d}$ dualises to a linear surjection
$A_{\leq d}(U)\to A_{\leq e}(U)$. This surjection is an algebra homomorphism,
and hence if $M$ is a module over the latter algebra, then it is also
naturally a module over the former algebra.

This interpretation also shows which $A_{\leq d}(U)$-modules are also $A_{\leq
e}(U)$-modules, namely, those for which the kernel $I$ of the surjection acts
as zero. Furthermore, if $M$ is an $A_{\leq d}(U)$-module, and $N$ is an
$A_{\leq d}(U)$-submodule of $M$, then $M/N$ is an $A_{\leq e}(U)$-module if
and only if $I\cdot(M/N)=0$, i.e., if and only if $N$ contains the $A_{\leq
d}(U)$-submodule $I\cdot M$. We conclude that there is a unique inclusion-wise
minimal $A_{\leq d}(U)$-submodule $N$ of $M$ such that $M/N$ is an $A_{\leq
e}(U)$-module, namely, $N=I\cdot M$.

By Proposition 2.4.1 we may translate this back to polynomial representations:

######  Proposition 2.5.2.

For any polynomial representation $P$ and any $e\in{\mathbb{Z}}_{\geq-1}$,
there is a unique inclusionwise minimal subrepresentation $Q$ such that $P/Q$
is a polynomial representation of degree at most $e$. $\square$

######  Definition 2.5.3.

Let $P$ be a polynomial representation and let $e\in{\mathbb{Z}}_{\geq-1}$.
The unique inclusionwise minimal subrepresentation $Q$ of $P$ such that $P/Q$
has degree $\leq e$ is denoted by $P_{>e}$.

######  Example 2.5.4.

Suppose that $\operatorname{char}K=2$. Consider the polynomial representation
$P:V\mapsto S^{2}V$ and the polynomial representation $Q$ that sends $V$ to
the space of symmetric tensors in $V\otimes V$. Then $P$ has as a
subrepresentation the representation $R$ that maps $V$ to the space of squares
of elements of $V$, and this is the only nontrivial subrepresentation unequal
to $P$ itself. The quotient $P/R$ has degree $2$, so $P_{>1}=P$. On the other
hand, $Q$ has the subrepresentation $T$ that assigns to $V$ the set of skew-
symmetric tensors in $V\otimes V$—i.e., those in the linear span of tensors of
the form $u\otimes v-v\otimes u$ as $u,v$ range through $V$—and the quotient
$Q/T$ is isomorphic to $R$. Now if $K={\mathbb{F}}_{2}$, then $R$ has degree
$1$, so that $Q_{>1}=T$; while if $K={\mathbb{F}}_{2}$, then $R$ has degree
$2$, and therefore $Q_{>1}=Q$.

We clearly have

$P=P_{>-1}\supseteq P_{>0}\supseteq\dots\supseteq P_{>d}=\\{0\\}$

where $d=\deg(P)$; and a straightforward check shows that $P_{>0}$ in this
definition agrees with the direct complement $P_{>0}$ of $P_{0}$ in Definition
2.5.1.

######  Lemma 2.5.5.

If $\alpha:P\to Q$ is a morphism in the Abelian category of polynomial
representations, then for each $e$ we have $\alpha(P_{>e})\subseteq Q_{>e}$.

###### Proof.

We compute

$P/\alpha^{-1}(Q_{>e})\cong\operatorname{im}(\alpha)/(\operatorname{im}(\alpha)\cap
Q_{>e})\subseteq Q/Q_{>e}.$

Since the latter representation has degree at most $e$, so does the first. The
defining property of $P_{>e}$ then implies that
$P_{>e}\subseteq\alpha^{-1}(Q_{>e})$. This is equivalent to the statement in
the lemma. ∎

######  Lemma 2.5.6.

Let $P$ be a polynomial representation, let $e\in{\mathbb{Z}}_{\geq-1}$, and
let $R$ be a subobject of $P_{>e}$, and hence of $P$. Then $(P/R)_{>e}\cong
P_{>e}/R$.

###### Proof.

By Lemma 2.5.5, the morphism $P\to P/R$ maps $P_{>e}$ into $(P/R)_{>e}$, and
its kernel on $P_{>e}$ is $R$, so that $P_{>e}/R$ maps injectively into
$(P/R)_{>e}$. To see that it also maps surjectively, we note that

$(P/R)/(P_{>e}/R)\cong P/P_{>e}$

has degree $\leq e$. Hence $P_{>e}/R$ contains $(P/R)_{>e}$ by definition of
the latter object. ∎

###  2.6. Shifting

Just like a univariate polynomial can be shifted over a constant, and then its
leading term does not change, a polynomial representation can be shifted over
a constant vector space, and we will see that its top-degree part does not
change.

######  Definition 2.6.1.

Given a $U\in\mathbf{Vec}$ and a representation
$P:\mathbf{Vec}\to\mathbf{Vec}$, we define the representation
$\mathrm{Sh}_{U}P$ by $(\mathrm{Sh}_{U}P)(V):=P(U\oplus V)$ and
$(\mathrm{Sh}_{U}P)(\varphi):=P(\operatorname{id}_{U}\oplus\varphi)$ for
$\varphi\in\operatorname{Hom}\nolimits(V,W)$. We call $\mathrm{Sh}_{U}P$ the
shift of $P$ by $U$.

If $P$ is polynomial of degree $\leq d$, then $\mathrm{Sh}_{U}P$ is also
polynomial of degree $\leq d$; below we will prove a more precise statement.

We have a morphism $\alpha:P\to\mathrm{Sh}_{U}P$ in the Abelian category of
polynomial generic representations defined by $\alpha_{V}=P(\iota_{V}):P(V)\to
P(U\oplus V)$, where $\iota_{V}:V\to U\oplus V$ is the inclusion $v\mapsto
0+v$. Indeed, that $(\alpha_{V})_{V}$ is a morphism follows from the
commutativity of the following diagram, for any
$\varphi\in\operatorname{Hom}\nolimits_{\mathbf{Vec}}(V,W)$:

$\textstyle{P(V)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{P(\iota_{V})}$$\scriptstyle{P(\varphi)}$$\textstyle{P(U\oplus
V)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{P(\operatorname{id}_{U}\oplus\varphi)}$$\textstyle{P(W)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{P(\iota_{W})}$$\textstyle{P(U\oplus
W),}$

which in turn follows from the fact that $P$ is a representation and that

$(\operatorname{id}_{U}\oplus\varphi)\circ\iota_{V}=\iota_{W}\circ\varphi.$

Similarly, we have a morphism $\beta:\mathrm{Sh}_{U}P\to P$ defined by
$\beta_{V}=P(\pi_{V}):P(U\oplus V)\to P(V)$, where $\pi:U\oplus V\to V$ is the
projection $u+v\mapsto v$. The relation $\pi\circ\iota=\operatorname{id}_{V}$
translates to $\beta\circ\alpha=\operatorname{id}_{P}$. This implies that
$\mathrm{Sh}_{U}P$ is the direct sum of $\operatorname{im}(\alpha)\cong P$ and
the polynomial representation $Q:=\ker(\beta)$.

The following lemma says, informally, that the top-degree part of a polynomial
representation is invariant under shifting.

######  Lemma 2.6.2.

Assume that $\deg(P)=d\geq 0$. Then $(\mathrm{Sh}_{U}P)_{>d-1}\cong P_{>d-1}$.

###### Proof.

Using the notation $\alpha$ and $\beta$ from above, we have
$\alpha(P_{>d-1})\subseteq(\mathrm{Sh}_{U}P)_{>d-1}$ and
$\beta((\mathrm{Sh}_{U}P)_{>d-1})\subseteq P_{>d-1}$ by Lemma 2.5.5. Combining
these facts shows that $\alpha$ maps $P_{>d-1}$ injectively into
$(\mathrm{Sh}_{U}P)_{>d-1}$. To argue that it also maps surjectively there, it
suffices to show that $(\mathrm{Sh}_{U}P)/\alpha(P_{>d-1})$ has degree $\leq
d-1$.

To see this, we recall that $\mathrm{Sh}_{U}P=\operatorname{im}(\alpha)\oplus
Q$, where $Q=\ker(\beta)$. Accordingly,

$(\mathrm{Sh}_{U}P)/\alpha(P_{>d-1})\cong(\alpha(P)/\alpha(P_{>d-1}))\oplus
Q.$

Here the first summand on the right is isomorphic to $P/P_{>d-1}$, hence of
degree $\leq d-1$. So it suffices to show that $Q$ has degree $\leq d-1$, as
well. Consider a vector $q\in Q(V)$ and a linear map
$\varphi\in\operatorname{Hom}\nolimits(V,W)$. Then we have

$\displaystyle Q(\varphi)(q)$
$\displaystyle=P(\operatorname{id}_{U}\oplus\varphi)(q)=P(\operatorname{id}_{U}\oplus\varphi)(q)-P(\operatorname{id}_{U}\oplus\varphi)(\alpha_{V}(\beta_{V}(q)))$
$\displaystyle=(P(\operatorname{id}_{U}\oplus\varphi)-P(0_{U}\oplus\varphi))(q)$

where the second equality follows from $\beta_{V}(q)=0$ and the last equality
follows from the definition of $\alpha$ and $\beta$. Now, for $\psi$ running
through $\operatorname{Hom}\nolimits(U\oplus V,U\oplus W)$, $P(\psi)$ can be
described by a polynomial map of degree at most $d$. If in this map we
substitute for $\psi$ the maps $\operatorname{id}_{U}\oplus\varphi$ and
$0_{U}\oplus\varphi$, respectively, we obtain the same degree-$d$ parts in
$\varphi$. Hence the map $\varphi\mapsto
P(\operatorname{id}_{U}\oplus\varphi)-P(0_{U}\oplus\varphi)$ is given by a
polynomial map of degree $\leq d-1$ in the entries of $\varphi$. This shows
that $Q$ has degree $\leq d-1$, as desired. ∎

###  2.7. A well-founded order on polynomial representations

######  Definition 2.7.1.

Given polynomial representations $Q,P:\mathbf{Vec}\to\mathbf{Vec}$, we write
$Q\preceq P$ if $Q\cong P$ or else for the largest $e$ such that
$Q_{>e}\not\cong P_{>e}$ the former is a quotient of the latter. We write
$Q\prec P$ to mean $Q\preceq P$ and $Q\not\cong P$.

######  Lemma 2.7.2.

The relation $\preceq$ is a well-founded pre-order on polynomial
representations.

###### Proof.

Reflexivity is immediate. To see transitivity, assume $R\preceq Q\preceq P$.
If one of the inequalities is an isomorphism, it follows immediately that
$R\preceq P$. Suppose that they are both not isomorphisms. Let $e$ be maximal
such that $Q_{>e}\not\cong P_{>e}$ and let $e^{\prime}$ be maximal such that
$R_{>e^{\prime}}\not\cong Q_{>e^{\prime}}$. If $e^{\prime}\geq e$, then
$e^{\prime}$ is maximal such that $R_{>e^{\prime}}\not\cong P_{>e^{\prime}}$,
and the former is a quotient of the latter. If $e^{\prime}<e$, then $e$ is
maximal such that $(Q_{>e}\cong)R_{>e}\not\cong P_{>e}$, and the former is a
quotient of the latter. In both cases, we find $R\prec P$, as desired.

To see that $\preceq$ is well-founded, suppose we had an infinite chain

$P_{1}\succ P_{2}\succ\ldots.$

To each $P_{i}$ we associate a length sequence
$\ell(P_{i})\in{\mathbb{Z}}_{\geq 0}^{\\{-1,0,1,2,\ldots\\}}$, where
$\ell(P_{i})(e)$ is the length of any composition chain of $(P_{i})_{>e}$ in
the abelian category of polynomial representations; by Proposition 2.4.1 this
length is finite.

Note that $\ell(P_{i})(e)=0$ for $e\geq\deg(P_{i})$, i.e., $\ell(P_{i})$ has
finite support. Now $P_{i}\succ P_{i+1}$ implies that $\ell(P_{i+1})$ is
lexicographically strictly smaller than $\ell(P_{i})$. Since the lexicographic
order on sequences with finite support is a well-order, we arrive at a
contradiction. ∎

We will intensively use the following construction.

######  Example 2.7.3.

Let $P\neq 0$ be a polynomial representation of degree $d\geq 0$, and let $R$
be an irreducible sub-object of $P_{>d-1}$. Let $U\in\mathbf{Vec}$ and set
$Q:=\mathrm{Sh}_{U}P$. By Lemma 2.6.2, $R$ is also naturally a sub-object of
$Q_{>d-1}$, which in turn is a sub-object of $Q$. By Lemma 2.5.6, we have
$(Q/R)_{>d-1}\cong Q_{>d-1}/R$, which in turn is $\cong P_{>d-1}/R$, a
quotient of $P_{>d-1}$. Since $P_{>e}=Q_{>e}=0$ for $e\geq d$, we conclude
that $Q/R\prec P$.

###  2.8. The coordinate ring of a polynomial representation

######  Definition 2.8.1.

Let $P:\mathbf{Vec}\to\mathbf{Vec}$ be a polynomial representation. We define
$K[P]$ as the contravariant functor from $\mathbf{Vec}$ to $K$-algebras that
assigns to $V$ the ring $K[P(V)]$ and to a linear map $\varphi:V\to W$ the
pullback $P(\varphi)^{\\#}:K[P(W)]\to K[P(V)]$. We call $K[P]$ the the
coordinate ring of $P$.

Note that $P(\varphi)^{\\#}$ is an algebra homomorphism; this is going to be
of crucial importance in §4.6. The coordinate ring comes with a natural ring
filtration:

$\\{0\\}=K[P]_{\leq-1}\subseteq K[P]_{\leq 0}\subseteq K[P]_{\leq 1}\subseteq
K[P]_{\leq 2}\subseteq\dots$

where $K[P]_{\leq e}$ assigns to $V$ the space $K[P(V)]_{\leq e}$.

######  Lemma 2.8.2.

If $P$ is a polynomial representation of degree $\leq d$, then $V^{*}\mapsto
K[P(V)]_{\leq e}$ is a polynomial representation of degree $\leq d\cdot e$.

###### Proof.

This representation assigns to a linear map $\varphi:V^{*}\to W^{*}$ the
restriction of the pullback $P(\varphi^{*})^{\\#}:K[P(V)]\to K[P(W)]$ to
$K[P(V)]_{\leq e}$. Since $P(\varphi^{*})$ is a linear map, this pullback does
indeed map $K[P(V)]_{\leq e}$ into $K[P(W)]_{\leq e}$, and it does so via a
linear map that is polynomial of degree $\leq e$ in $P(\varphi^{*})$, hence of
degree $\leq d\cdot e$ in $\varphi^{*}$, which in turn depends linearly on
$\varphi$. ∎

######  Example 2.8.3.

Let $P=S^{2}$ and assume $|K|>2$. Take $V=K^{n}$ with basis
$e_{1},\ldots,e_{n}$, so that $P(V)$ has basis $e_{i}e_{j}$ with $i\leq j$.
For $k>l$ distinct, let $g_{kl}(s)\in\operatorname{End}\nolimits(V)$ be the
matrix with $1$’s on the diagonal, an $s$ on position $(k,l)$, and zeros
elsewhere. We have

$\displaystyle P(g_{kl}(s))\sum_{i\leq j}a_{ij}e_{i}e_{j}$
$\displaystyle=\sum_{i\leq j}a_{ij}(g_{kl}(s)e_{i})(g_{kl}(s)e_{j})$
$\displaystyle=\sum_{i\leq
j}a_{ij}(e_{i}+\delta_{il}se_{k})(e_{j}+\delta_{jl}se_{k})$
$\displaystyle=\sum_{i\leq
j}a_{ij}(e_{i}e_{j}+s(\delta_{jl}e_{i}e_{k}+\delta_{il}e_{k}e_{j})+s^{2}\delta_{il}\delta_{jl}e_{k}^{2})$
$\displaystyle=\left(\sum_{i\leq j}a_{ij}e_{i}e_{j}\right)+s\left(\sum_{i\leq
l}a_{il}e_{i}e_{k}+\sum_{j\geq l}a_{lj}e_{k}e_{j}\right)+s^{2}a_{ll}e_{k}^{2}$

Observe that by acting with $g_{kl}$ on (linear combinations of) the basis
vectors $e_{i}e_{j}$, indices $l$ either remain the same or turn into indices
$k$.

We now look at the dual. Let $\\{x_{ij}\mid i\leq j\\}$ be the basis of
$P(V)^{*}$ dual to the given basis of $P(V)$. Then, for instance, for $l<i<k$
we have

$P(g_{kl}(s))^{\\#}x_{ik}=x_{ik}+sx_{li},$

as can be seen by taking the coefficient of $e_{i}e_{k}$ in the expression
above. We observe here that indices $k$ either remain the same or turn into
indices $l$. We can also write the above as

$P(g_{lk}(s)^{T})^{\\#}x_{ik}=x_{ik}+sx_{li}.$

Note that $P(g)^{\\#}$ is contravariant in $g$, and hence $P(g^{T})^{\\#}$ is
again covariant. This explains the $V^{*}$ in Lemma 2.8.2.

##  3\. Weight theory

In the representation theory of the group scheme
$\operatorname{GL}\nolimits_{n}$, the weight space decomposition of a
representation, i.e., its decomposition as a module over the subgroup of
diagonal matrices, is of crucial importance. For the finite group
$G=\operatorname{GL}\nolimits_{n}(K)$ with $K={\mathbb{F}}_{q}$, it was
already observed in [Ste16, Page 129, Remark] that weights alone do not
suffice to distinguish the roles played by various vectors in a
representation. The example given there is that the highest weight vector $1$
in the trivial $\operatorname{GL}\nolimits_{n}(K)$-representation $K^{1}$ and
the highest weight vector $e_{1}^{q-1}$ in the $(q-1)$st symmetric power
$S^{q-1}K^{n}$ of the standard representation both have weight $(0,\ldots,0)$.
It is explained there how to act with elements of the group algebra of $G$ to
distinguish the two.

In this particular example, we can distinguish these vectors by extending the
action of (diagonal matrices in) $\operatorname{GL}\nolimits_{n}(K)$ to
(diagonal matrices in) $\operatorname{End}\nolimits(K^{n})$, as we do in the
context of generic polynomial representations: the first heighest weight
vector then has weight $(0,\ldots,0)$, while the latter has weight
$(q-1,0,\ldots,0)$—see the definitions below. However, the vector
$e_{1}^{\otimes q}$ in the $q$-th tensor power cannot be distinguished from
the vector $e_{1}$ in the standard representation via diagonal matrices.
Therefore we, too, will act with suitable elements of the monoid algebra of
$\operatorname{End}\nolimits(K^{n})$ to get a better grasp on weight vectors.
However, our focus will not be on highest weight vector; rather, we will look
for middle weight vectors, i.e., weight vectors whose weight is maximally
spread out in a sense that we will make precise below.

We are by no means the first to study weights in this context. For instance,
they also feature as reduced weights in [Kuh94b]. However, the procedure of
maximally spreading out weight that we introduce below does seem to be new.

###  3.1. Multiplicative monoid homomorphisms $K\to K$

A monoid homomorphism $(K,\cdot)\to(K,\cdot)$ is a map $\varphi:K\to K$ with
$\varphi(1)=1$ and $\varphi(ab)=\varphi(a)\varphi(b)$ for all $a,b\in K$. In
particular, $\varphi$ restricts to a group homomorphism from the
multiplicative group $K^{\times}:=K\setminus\\{0\\}$ to itself. Since
$K^{\times}$ is cyclic, say with generator $g$, the monoid homomorphism
$\varphi$ is uniquely determined by its values on $g$ and on $0$. Write
$\varphi(g)=g^{e}$ for a unique exponent $e\in\\{1,\ldots,q-1\\}$. If $e\neq
q-1$, so that $\varphi(g)\neq 1$, then $\varphi(0)$ is forced to be $0$, since
otherwise $\varphi(g)\cdot\varphi(0)$ does not equal $\varphi(g\cdot
0)=\varphi(0)$. If $e=q-1$, then there are two possibilities for $\varphi(0)$,
namely, $\varphi(0)=1$ and $\varphi(0)=0$. In the first case, we will denote
$\varphi$ by $c\mapsto c^{0}$, and in the second case, we denote by $c\mapsto
c^{q-1}$. The following is now straightforward.

######  Lemma 3.1.1.

The monoid of monoid homomorphisms $K\to K$ is isomorphic to the monoid
$\\{0,\ldots,q-1\\}$ with operation $i\oplus j$ defined by $i\oplus j=i+j$ if
$i+j\leq q-1$ and $i\oplus j=i+j-(q-1)$ otherwise.

Note that this monoid is not cancellative, since $0\oplus j=(q-1)\oplus j$ for
all $j\in\\{1,\ldots,q-1\\}$. Nevertheless, it will be convenient to have a
notation for subtracting elements in the following sense: for
$i\in\\{1,\ldots,q-1\\}$ and $j\in\\{0,\ldots,q-1\\}$ we write $i\ominus j$
for the unique element in $\\{1,\ldots,q-1\\}$ that equals $i-j$ modulo $q-1$.

###  3.2. Acting with diagonal matrices

Let $P:\mathbf{Vec}\to\mathbf{Vec}$ be a polynomial representation and set
$V:=K^{n}$, so that we may identify $\operatorname{End}\nolimits(V)$ with the
space of $n\times n$-matrices. Then the monoid
$\operatorname{End}\nolimits(V)$ acts linearly on $P(V)$ via the map
$\operatorname{End}\nolimits(V)\to\operatorname{End}\nolimits(P(V)),\varphi\mapsto
P(\varphi)$, and hence so does its submonoid
$D_{n}\subseteq\operatorname{End}\nolimits(V)$ of diagonal matrices.

######  Lemma 3.2.1.

We have

$P(V)=\bigoplus_{\chi:D_{n}\to K}P(V)_{\chi}$

where $\chi$ runs over all monoid homomorphisms $(D_{n},\cdot)\to(K,\cdot)$
and where

$P(V)_{\chi}:=\\{p\in P(V)\mid\forall\varphi\in
D_{n}:P(\varphi)p=\chi(\varphi)p\\}.$

###### Proof.

Each element $\varphi\in D_{n}$ satisfies $\varphi^{q}=\varphi$, and therefore
also $P(\varphi)^{q}=P(\varphi^{q})=P(\varphi)$. Consequently, $P(\varphi)$ is
a root of the polynomial $h=T\cdot(T^{q-1}-1)\in K[T]$. This polynomial is
square-free, so that $P(\varphi)$ is diagonalisable over a separable closure
of $K$. But also the eigenvalues of $P(\varphi)$ are roots of $h$, i.e.,
elements of $K$, so $P(\varphi)$ is diagonalisable over $K$. Moreover, all
elements of $D_{n}$ commute, and therefore so do all elements of $P(D_{n})$.
Hence the latter are all simultaneously diagonalisable. We therefore have

$P(V)=\bigoplus_{\chi:D_{n}\to K}P(V)_{\chi}$

where, a priori, $\chi$ runs through all maps $D_{n}\to K$.

Now if $P(V)_{\chi}\neq 0$, then it follows that
$\chi(\operatorname{diag}\nolimits(1,\ldots,1))=1$ and
$\chi(\varphi\psi)=\chi(\varphi)\chi(\psi)$, i.e., $\chi$ is a monoid
homomorphism $D_{n}\to K$. ∎

Note that monoid homomorphisms $D_{n}\to K$ can be naturally identified with
$n$-tuples of monoid homomorphisms $K\to K$, and hence, by Lemma 3.1.1, with
elements of $\\{0,\ldots,q-1\\}^{n}$. Explicitly, $\chi$ is identified with
the tuple $(a_{1},\ldots,a_{n})$ if
$\chi(\operatorname{diag}\nolimits(t_{1},\ldots,t_{n}))=t_{1}^{a_{1}}\cdots
t_{n}^{a_{n}}$ for all $(t_{1},\ldots,t_{n})\in K^{n}$.

In analogy with the theory of representations of algebraic groups, we will use
the word weight for monoid homomorphisms $\chi:D_{n}\to K$, and we call a
vector in $P(V)_{\chi}$ a weight vector of weight $\chi$.

We use the notation $\oplus$ also in this context: if
$\chi,\mu\in\\{0,\ldots,q-1\\}^{n}$ are weights, then $\chi\oplus\mu$ is their
componentwise sum with respect to $\oplus$. Note that

$(\chi\oplus\mu)(\operatorname{diag}\nolimits(t_{1},\ldots,t_{n}))=\chi(\operatorname{diag}\nolimits(t_{1},\ldots,t_{n}))\cdot\mu(\operatorname{diag}\nolimits(t_{1},\ldots,t_{n})).$

######  Example 3.2.2.

If $U$ is the subspace of $V$ spanned by the first $k$ basis vectors, then
$P(U)$, regarded as a subspace of $P(V)$, is the direct sum of all
$P(V)_{\chi}$ where $\chi$ runs over the characters in
$\\{0,\dots,q-1\\}^{k}\times\\{0\\}^{n-k}$. In particular, the constant part
of $P$ is $P(0)=P(V)_{(0,\ldots,0)}$.

######  Lemma 3.2.3.

Let $\chi=(a_{1},\ldots,a_{n})\in\\{0,\ldots,q-1\\}^{n}$ be a weight such that
$P(K^{n})_{\chi}$ is nonzero. Then $\sum_{i}a_{i}$ is at most $\deg(P)$.

###### Proof.

Choose a nonzero $p\in P(K^{n})_{\chi}$. Then
$P(\operatorname{diag}\nolimits(t_{1},\ldots,t_{n}))p=t_{1}^{a_{1}}\cdots
t_{n}^{a_{n}}p$, and we note that $t_{1}^{a_{1}}\cdots t_{n}^{a_{n}}$ is a
reduced polynomial in $t_{1},\ldots,t_{n}$. On the other hand,
$P(\operatorname{diag}\nolimits(t_{1},\ldots,t_{n}))$ can be expressed as a
reduced polynomial of degree at most $\deg(P)$ in $t_{1},\ldots,t_{n}$ with
coefficients that are linear maps $P(K^{n})\to P(K^{n})$. Evaluating this at
$p$ yields a reduced polynomial of degree at most $\deg(P)$ in
$t_{1},\ldots,t_{n}$ whose coefficients are elements of $P(K^{n})$. But we
already know which polynomial that is, namely $t_{1}^{a_{1}}\cdots
t_{n}^{a_{n}}p$. Hence $\sum_{i}a_{i}\leq\deg(P)$. ∎

###  3.3. Acting with additive one-parameter subgroups

Let $P:\mathbf{Vec}\to\mathbf{Vec}$ be a polynomial representation,
$n\in{\mathbb{Z}}_{\geq 2}$, and $i,j\in[n]$ distinct. Then we have a one-
parameter subgroup

$g_{ij}:(K,+)\to\operatorname{GL}\nolimits_{n}(K),\ g_{ij}(s):=I+sE_{ij},$

where $E_{ij}$ is the matrix with zeroes everywhere except for a $1$ in
position $(i,j)$. For $b=0,\ldots,q-1$ we define the linear map
$F_{ij}[b]:P(K^{n})\to P(K^{n})$ by

$F_{ij}[b]p=\text{ the coefficient of $s^{b}$ in }P(g_{ij}(s))p,$

where we write $P(g_{ij}(s))p$ as a reduced polynomial in $s$ with
coefficients in $P(K^{n})$.

######  Lemma 3.3.1.

For any sub-representation $Q$ of $P$, the linear space $Q(K^{n})$ is stable
under $F_{ij}[b]$.

###### Proof.

Let $p\in Q(K^{n})$. Then for all $s\in K$ the element

$P(g_{ij}(s))p=F_{ij}[0]p+sF_{ij}[1]p+\cdots+s^{q-1}F_{ij}[q-1]p$

lies in $Q(K^{n})$. The Vandermonde matrix $(s^{e})_{s\in
K,e\in\\{0,\ldots,q-1\\}}$ is invertible, and this implies that each of the
$F_{ij}[e]p$ above are linear combinations of the $P(g_{ij}(s))p$, and
therefore in $Q(K^{n})$. ∎

######  Lemma 3.3.2.

Let $p\in P(K^{n})$ be a weight vector of weight $a=(a_{1},\ldots,a_{n})$, let
$b\in\\{0,\ldots,q-1\\}$, and set $\tilde{p}:=F_{ij}[b]p$. Then we have the
following.

  1. (1)

$\tilde{p}=p$ for $b=0$;

  2. (2)

if $a_{j}=0$, then $\tilde{p}=0$ for $b\neq 0$;

  3. (3)

if $0<a_{j}\neq b$, then $\tilde{p}$ is a weight vector of weight
$a\ominus(be_{j})\oplus(be_{i})$;

  4. (4)

if $0<a_{j}=b$, then $\tilde{p}$ is a sum of a weight vector of weight

$a\ominus be_{j}\oplus be_{i}=(a_{1},\ldots,a_{i}\oplus
b,\ldots,q-1,\ldots,a_{n})$

and a weight vector of weight

$a-be_{j}\oplus be_{i}=(a_{1},\ldots,a_{i}\oplus b,\ldots,0,\ldots,a_{n}).$

###### Proof.

We write

$P(g_{ij}(s))p=p_{0}+sp_{1}+\cdots+s^{q-1}p_{q-1}.$

By setting $s$ equal to zero we obtain
$P(g_{ij}(0))p=P(\operatorname{id}_{K^{n}})p=p$ on the left-hand side, and
$p_{0}$ on the right-hand side. This proves the first item.

If $a_{j}=0$, then

$P(\operatorname{diag}\nolimits(1,\ldots,1,0,1\ldots,1))p=p$

where the $0$ is on position $j$. Therefore

$P(g_{ij}(s))p=P(g_{ij}(s)\operatorname{diag}\nolimits(1,\ldots,1,0,1,\ldots,1))p=P(\operatorname{diag}\nolimits(1,\ldots,1,0,1,\ldots,1))p$

does not depend on $s$ and hence $F_{ij}[b]p=0$ for $b\neq 0$.

We now assume $a_{j}>0$. We have $F_{ij}[b]p=p_{b}$. To determine the
weight(s) appearing in $p_{b}$, we act on $p_{b}$ with diagonal matrices. For
$t=(t_{1},\ldots,t_{n})\in K^{n}$ and $t_{j}\neq 0$ we have

$\operatorname{diag}\nolimits(t_{1},\ldots,t_{n})\cdot
g_{ij}(s)=g_{ij}(t_{i}st_{j}^{-1})\cdot\operatorname{diag}\nolimits(t_{1},\ldots,t_{n})$

and therefore

$\displaystyle\sum_{d=0}^{q-1}s^{d}P(\operatorname{diag}\nolimits(t_{1},\ldots,t_{n}))p_{d}$
$\displaystyle=P(\operatorname{diag}\nolimits(t_{1},\ldots,t_{n})g_{ij}(s))p$
$\displaystyle=P(g_{ij}(t_{i}st_{j}^{-1})\operatorname{diag}\nolimits(t_{1},\ldots,t_{n}))p$
$\displaystyle=t_{1}^{a_{1}}\cdots t_{n}^{a_{n}}\cdot
P(g_{ij}(t_{i}st_{j}^{-1}))p$ $\displaystyle=t_{1}^{a_{1}}\cdots
t_{n}^{a_{n}}\cdot\sum_{d=0}^{q-1}(t_{i}st_{j}^{-1})^{d}p_{d}.$

Comparing coefficients of $s^{b}$, we find

$P(\operatorname{diag}\nolimits(t))p_{b}=t^{a-be_{j}+be_{i}}p_{b}$

for all $t\in K^{j-1}\times K^{\times}\times K^{n-j}=:D$. Hence $p_{b}$ is a
linear combination of weight vectors with weights that on $D$ agree with the
weight $a\ominus be_{j}\oplus be_{i}$. If $a_{j}\neq b_{j}$, there is only one
such weight, namely, $a\ominus be_{j}\oplus be_{i}$. If $a_{j}=b$, then there
are two such weights, namely, $a\ominus be_{j}\oplus be_{i}$ and
$a-be_{j}\oplus be_{i}$. ∎

###  3.4. Spreading out weight

Retaining the notation from §3.3, suppose we are given a nonzero weight vector
$p\in P(K^{n})$ of weight $(a_{1},\ldots,a_{n})\in\\{0,\ldots,q-1\\}^{n}$ and
a $j\in[n]$ with $a_{j}>0$. We construct vectors $\tilde{p}\in P(K^{n+1})$ by
identifying $p$ with $P(\iota)p$, where $\iota:K^{n}\to K^{n+1}$ is the
embedding adding a $0$ in the last position. Then $p$ is a vector of weight
$a=(a_{1},\ldots,a_{n},0)$ in $P(K^{n+1})$, and we compute

$\tilde{p}:=F_{n+1,j}[b]p$

for various $b$. The vector $\tilde{p}$ is guaranteed to be nonzero for at
least two values of $b$, namely, for $b=0$ (in which case $\tilde{p}=p$), and,
as we will now see, for $b=a_{j}$. Indeed, in the latter case, by Lemma 3.3.2,
$\tilde{p}$ is the sum of a weight vector $\tilde{p}_{0}$ of weight
$a-a_{j}e_{j}+a_{j}e_{n+1}$ and a weight vector $\tilde{p}_{1}$ of weight
$a+(q-1-a_{j})e_{j}+a_{j}e_{n+1}$.

######  Lemma 3.4.1.

In the case where $b=a_{j}$, we have $\tilde{p}_{0}=P((j,n+1))p$, where
$(j,n+1)$ is short-hand for the permutation matrix corresponding to the
transposition $(j,n+1)$.

###### Proof.

The vector $\tilde{p}_{0}$ is obtained by applying $P(\pi_{j})$ to
$\tilde{p}$, where $\pi_{j}$ is the projection $K^{n+1}\to K^{n+1}$ that sets
the $j$-th coordinate to zero. Furthermore, we have $P(\pi_{n+1})p=p$, where
$\pi_{n+1}$ sets the $(n+1)$st coordinate to zero. We can then compute
$\tilde{p}_{0}$ as the coefficient of $s^{a_{j}}$ in

$\displaystyle P(\pi_{j})P(g_{n+1,j}(s))p$
$\displaystyle=P(\pi_{j}g_{n+1,j}(s)\pi_{n+1})p$
$\displaystyle=P((j,n+1))P(\operatorname{diag}\nolimits(1,\ldots,1,s,1,\ldots,1,0))p$
$\displaystyle=P((j,n+1))s^{a_{j}}p.\qed$

If either $F_{n+1,j}[b]p\neq 0$ for some $b\neq 0,a_{j}$ or if
$F_{n+1,j}[a_{j}]p\neq P((j,n+1))p$, then we find a new vector $p^{\prime}$ in
the subrepresentation of $P$ generated by $p$ whose weight has strictly more
nonzero entries—we have spread out the weight of $p$.

######  Definition 3.4.2.

A nonzero weight vector $p\in P(K^{n})\subseteq P(K^{n+1})$ of weight
$a\in\\{0,\ldots,q-1\\}^{n}$ is called maximally spread out if for all
$j\in[n]$ with $a_{j}>0$ we have

$P(g_{n+1,j}(s))p=p+s^{a_{j}}P((j,n+1))p.$

######  Proposition 3.4.3.

For any nonzero polynomial representation $P$, there exist an $n$ and a
nonzero weight vector $p\in P(K^{n})$ that is maximally spread out.

###### Proof.

Let $p\in P(K^{m})$ be a nonzero weight vector. As long as $p$ is not
maximally spread out, by the above discussion we can replace $p$ by a nonzero
weight vector in $P(K^{m+1})$ whose weight has strictly more nonzero entries.
But by Lemma 3.2.3, the number of nonzero entries is bounded from above by
$\deg(P)$. Hence this process must terminate, with a maximally spread out
vector. ∎

######  Example 3.4.4.

It is not true that every polynomial representation is generated by its
maximally spread out vectors. Consider, for instance, $K$ of characteristic
$2$ and the representation $Q$ that sends $V$ to the space of symmetric
tensors in $V\otimes V$. The weight vectors in $Q(K^{n})$ are of the forms
$e_{i}\otimes e_{i}$ and $e_{i}\otimes e_{j}+e_{j}\otimes e_{i}\in Q(K^{n})$
with $i\neq j$. Only the latter are maximally spread out. But they generate
the sub-representation of $Q$ consisting of all skew-symmetric tensors in
$V\otimes V$.

###  3.5. The prime field case

In this section we assume that $q$ is a prime, so that $K$ is a prime field.
We retain the notation from above.

######  Definition 3.5.1.

Let $\iota:K^{n}\to K^{n+1}$ be the standard embedding and
$F_{n+1,j}=F_{n+1,j}[1]:P(K^{n})\to P(K^{n+1})$ be the operator that sends $p$
to the coefficient of $s^{1}$ in $P(g_{n+1,j}(s)\circ\iota)(p)$.

######  Lemma 3.5.2.

Assume that $K$ is a prime field. Then the operator $F_{n+1,j}:P(K^{n})\to
P(K^{n+1})$ is injective on the direct sum of all weight spaces corresponding
to weights $\chi=(a_{1},\ldots,a_{n})$ with $a_{j}>0$, and it is zero on the
weight spaces corresponding to weights with $a_{j}=0$.

###### Proof.

The last part follows immediately from Lemma 3.3.2; we now prove the first
part. The operator $F_{n+1,j}$ maps the weight space of $\chi$ into that of
$\chi\ominus e_{j}+e_{n+1}$ if $a_{j}>1$ and into the sum of the weight spaces
with weights $\chi-e_{j}+e_{n+1}$ and $\chi\ominus e_{j}+e_{n+1}$ if
$a_{j}=1$. Since these weights are distinct for distinct $\chi$, it suffices
to show that $F_{n+1,j}$ is injective on a single weight space, corresponding
to the weight $(a_{1},\ldots,a_{n})$, where $a_{j}>0$. Let $p$ be a nonzero
vector in this weight space.

Define $\varphi:K^{n+1}\to K^{n}$ by

$\varphi(c_{1},\dots,c_{n+1}):=(c_{1},\ldots,c_{j}+c_{n+1},\ldots,c_{n}).$

We then have

$\varphi\circ
g_{n+1,j}(s)\circ\iota=\operatorname{diag}\nolimits(1,\dots,1+s,\dots,1)$

and therefore

$P(\varphi)P(g_{n+1,j}(s))P(\iota)p=(1+s)^{a_{j}}\cdot p.$

The coefficient of $s^{1}$ in the latter expression is $a_{j}\cdot p$, which
is nonzero since $a_{j}<q$ and $q$ is prime. That coefficient is also equal to
$P(\varphi)\tilde{p}$, where $\tilde{p}:=F_{n+1,j}p$. Hence $\tilde{p}\neq 0$.
∎

By Lemma 3.5.2, if $\chi=(a_{1},\ldots,a_{n})$ with $a_{j}>1$, then
$F_{n+1,j}$ maps $P(K^{n})_{\chi}$ injectively into
$P(K^{n+1})_{\chi^{\prime}}$, where $\chi^{\prime}=\chi-e_{j}+e_{n+1}$. On the
other hand, if $a_{j}=1$, then by Lemma 3.4.1, $F_{n+1,j}$ followed by
projection to the weight space of
$\chi^{\prime}=(a_{1},\ldots,0,\ldots,a_{n},1)$ agrees on $P(K^{n})_{\chi}$
with the map $P((n+1,j))r$, which of course we already knew is injective.

######  Example 3.5.3.

We note that Lemma 3.5.2 is false for non-prime fields. Indeed, take
$K={\mathbb{F}}_{4}$ and $P=S^{2}$. Consider the element $p:=e_{1}^{2}\in
P(K^{1})$, of weight $(2)$. Now
$g_{21}(s)p=(e_{1}+se_{2})^{2}=e_{1}^{2}+s^{2}e_{2}^{2}$, and hence
$F_{2,1}p=0$. On the other hand, if $K={\mathbb{F}}_{2}$, then $s^{2}=s$, and
$F_{21}p=e_{2}^{2}$.

######  Remark 3.5.4.

Note that, as a consequence of the lemma, if a weight vector $p$ of weight
$(a_{1},\ldots,a_{n})$ is maximally spread out, then $a_{j}\in\\{0,1\\}$ for
all $j$, and moreover $F_{n+1,j}p=P((n+1,j))p$ for all $j$ with $a_{j}=1$.
Indeed, if $a_{j}>1$, then $F_{n+1,j}p$ is a weight vector of weight
$(a_{1},\ldots,a_{j}-1,\ldots,a_{n},1)$, and if $a_{j}=1$ but $F_{n+1,j}p\neq
P((n+1,j))p$, then the left-hand side has a component of weight
$(a_{1},\ldots,q-1,\ldots,a_{n},1)$. In either case, $p$ was not maximally
spread out.

######  Remark 3.5.5.

For $\varphi\in\operatorname{Hom}\nolimits_{\mathbf{Vec}}(V,W)$ and $P$ a
generic polynomial representation and $p\in P(V)$, we will sometimes just
write $\varphi p$ instead of $P(\varphi)p$. For instance, we will do this for
$\varphi=g_{n+1,j}(s)$. The advantage of this is that we do not need to make
explicit in which polynomial polynomial representation we are computing.

##  4\. Noetherianity for polynomial representations

###  4.1. The main result

We recall that the tensor testriction theorem, its generalisation to
polynomial representations, and Corollary 1.3.3, concern restriction-closed
properties. We will simply use the term subset for such a property:

######  Definition 4.1.1.

Let $P$ be a polynomial representation. A subset of $P$ is the data of a
subset $X(V)$ of $P(V)$ for every $V\in\mathbf{Vec}$, subject to the condition
that for all $V,W,\varphi\in\operatorname{Hom}\nolimits_{\mathbf{Vec}}(V,W)$,
$P(\varphi)X(V)\subseteq X(W)$.

######  Theorem 4.1.2 (Noetherianity).

Let $P$ be a polynomial representation over the finite field $K$. Then any
descending chain

$P\supseteq X_{1}\supseteq X_{2}\supseteq\ldots$

of subsets stabilises.

###  4.2. Irreducible decomposition of restriction-closed tensor properties

Before proceeding with the proof of Noetherianity, we deduce from it the fact
that any subset of $P$ admits a unique decomposition into irreducible subsets.

######  Definition 4.2.1.

Let $P$ be a polynomial generic representation over the finite field $K$ and
let $X$ be a subset of $P$. We call $X$ irreducible if $X(0)\neq\emptyset$ and
if whenever $X_{1},X_{2}$ are subsets of $P$ such that $X(V)=X_{1}(V)\cup
X_{2}(V)$ holds for all $V\in\mathbf{Vec}$, it follows that $X=X_{1}$ or
$X=X_{2}$.

######  Theorem 4.2.2.

For any subset $X$ of a polynomial representation $P$ over the finite field
$K$, there is a unique decomposition

$X=X_{1}\cup\ldots\cup X_{k}$

where all $X_{i}$ are irreducible and none is contained in any other.

###### Proof.

This is an immediate consequence of Noetherianity 4.1.2, and the proof is
identical to the proof that any Noetherian topological space admits a unique
decomposition into irreducible closed subspaces. ∎

For an instructive example, we need the following lemma.

######  Lemma 4.2.3.

Suppose that $P(0)=0$. Then the subset $X:=P$ is irreducible in the sense
above.

We note that the requirement that $P(0)$ be zero is necessary for
irreducibility; otherwise, one can take any partition $S_{1}\sqcup S_{2}$ of
the finite set $P(0)$ into two nonempty parts, define $X_{i}(V)$ to be the set
of elements in $P(V)$ that map into the $S_{i}$, and note that $P=X_{1}\cup
X_{2}$.

###### Proof.

Suppose that $X=X_{1}\cup X_{2}$ where $X_{i}\subsetneq X$ for $i=1,2$. Then
$X_{1}$ has at least one forbidden restriction $T_{1}\in P(V_{1})$, and
$X_{2}$ has at least one forbidden restriction $T_{2}\in P(V_{2})$. Let
$\iota_{i}:V_{i}\to V_{1}\oplus V_{2}$ be the canonical inclusion, and write
$T:=P(\iota_{1})(T_{1})+P(\iota_{2})(T_{2})$. Let $\pi_{i}:V_{1}\oplus
V_{2}\to V_{i}$ be the projection. Then
$P(\pi_{1}\circ\iota_{2})=P(0_{V_{2}\to V_{1}})$, which is the zero map since
it factors via $P(0)=0$; and similarly $P(\pi_{2}\circ\iota_{1})=0$. We
conclude that

$T_{1}=P(\pi_{1}\circ\iota_{1})T_{1}=P(\pi_{1})(P(\iota_{1})T_{1}+P(\iota_{2})T_{2})=P(\pi_{1})T,$

so $T_{1}$ is a restriction of $T$. Similarly, $T_{2}$ is a restriction of
$T$. It follows that $T$ lies neither in $X_{1}(V_{1}\oplus V_{2})$ nor in
$X_{2}(V_{1}\oplus V_{2})$, a contradiction. Hence $X$ is irreducible as
claimed. ∎

######  Example 4.2.4.

For any $r\in{\mathbb{R}}_{\geq 0}$, let $X_{r}$ be the locus in $T^{d}$ where
the partition rank is at most $r$, and let $Y_{r}$ be the locus in $T^{d}$
where the analytic rank is at most $r$.

For $X_{r}$ (with $r$ an integer) it is easy to write down a decomposition
into irreducible subsets: for any of the $2^{d-1}-1$ unordered partitions
$\\{I,J\\}$ of $[d]$ into two nonempty sets, choose a number $r_{\\{I,J\\}}$
such that these numbers add up to $r$. This choice gives a natural map

$\prod_{\\{I,J\\}}(T^{|I|}\times T^{|J|})^{r_{\\{I,J\\}}}\to T^{d}$

parameterising the locus in $X_{r}$ of tensors with a partition rank $\leq r$
decomposition of a fixed type; this image is irreducible by virtue of Lemma
4.2.3 applied to the left-hand side above. The total number of components of
$X_{r}$ that we find is the number of ways of partitioning $r$ into
$2^{d-1}-1$ nonnegative integers, which is polynomial in $r$.

Given the (almost) linear relation between partition rank and analytic rank
[CM21, MZ22], it is natural to ask whether the number of components of
$Y_{r}$, too, is polynomial in $r$.

###  4.3. The vanishing ideal of a subset

We will prove Noetherianity by looking at functions that vanish identically on
a subset.

######  Definition 4.3.1.

Given a subset $X\subseteq P$, we denote by $I_{X}(V)\subseteq K[P(V)]$ the
ideal of all functions $P(V)\to K$ that vanish identically on $X(V)$.

We stress that conversely, since $K$ is finite, $X(V)$ is also the set of all
common zeros of $I_{X}(V)$ in $P(V)$.

###  4.4. Shifting and localising

Definition 2.6.1 can be extended to subsets of polynomial representations.

######  Definition 4.4.1.

Given a subset $X$ of a polynomial representation $P$ and a
$U\in\mathbf{Vec}$, the shift $\mathrm{Sh}_{U}X$ is the subset of
$\mathrm{Sh}_{U}P$ defined by $(\mathrm{Sh}_{U}X)(V):=X(U\oplus V)$.

######  Definition 4.4.2.

Given a subset $X$ of $P$ and a function $h\in K[P(0)]$, we can think of $h$
as a function on any $P(V)$ via pullback along the linear map $P(V)\to P(0)$,
and hence also as a function on $X(V)$. We define $X[1/h]$ as the functor

$V\mapsto X[1/h](V):=\\{p\in X(V)\mid h(p)\neq 0\\}.$

Clearly, $X[1/h]$ is a subset of $P$.

We will often combine a shift and a localisation: given a function $h\in
K[P(U)]$, we can think of $h$ as a function on $K[(\mathrm{Sh}_{U}P)(0)]$, and
hence localise.

######  Example 4.4.3.

Let $P:V\to V\otimes V$ and let $X(V)$ be the set of tensors (matrices) of
rank $\leq n$ in $P(V)$. Let $h\in K[P(K^{n})]$ be the $n\times n$-determinant
and set $U:=K^{n}$. Then $(\mathrm{Sh}_{U}X)[1/h]$ is isomorphic to the
functor that sends $V$ to $B\times V^{2n}$, where $B:=X(U)[1/h]$ is the set of
invertible $n\times n$-matrices, and the isomorphism
$(\mathrm{Sh}_{U}X)[1/h](V)\to B\times V^{2n}$ comes from observing that

$(\mathrm{Sh}_{U}X)[1/h](V)\subseteq P(U\oplus V)=(K^{n}\otimes
K^{n})\times(K^{n}\otimes V)\times(V\otimes K^{n})\times(V\otimes V),$

and realising that the $V\otimes V$-component of a matrix of rank $\leq n$ is
completely determined by its remaining three components, provided that the
$K^{n}\otimes K^{n}$-component has nonzero determinant. This phenomenon, that
$X$ becomes an affine space up to shifting and localising, holds in greater
generality, at least at a counting level; see Corollary 4.9.1.

###  4.5. Reduction to the prime field case

######  Proposition 4.5.1.

Suppose that Theorem 4.1.2 holds when $K$ is a prime field. Then it also holds
when $K$ is an arbitrary finite field.

###### Proof.

Let $F$ be the prime field of $K$ and set $e:=\dim_{F}K$. For an
$n$-dimensional $K$-vector space $U$, we write $U_{F}$ for the $e\cdot
n$-dimensional $F$-vector space obtained by restricting the scalar
multiplication on $U$ from $K\times U\to U$ to $F\times U\to U$.

Now let $P$ be a polynomial representation over $K$. Define a generic
representation $P_{F}$ over $F$ by setting, for a finite-dimensional
$F$-vector space $U$, $P_{F}(U):=(P(K\otimes_{F}U))_{F}$, and sending an
$F$-linear map $\varphi:U\to V$ to the map $P_{F}(\varphi)$, which is
$K$-linear and therefore also $F$-linear. It is easy to see from the
definitions that $P_{F}$ is polynomial of the same degree as $P$.

For a subset $X$ of $P$, we define a subset of $P_{F}$ via
$X_{F}(U):=X(K\otimes_{F}U)$. If $X_{1}\supseteq X_{2}\supseteq\ldots$ is a
chain of subsets in $P$, then $(X_{1})_{F}\supseteq(X_{2})_{F}\supseteq\ldots$
is a chain of subsets in $P_{F}$. By assumption, the latter stabilises, say at
$(X_{n_{0}})_{F}$. Then it follows that, for any $n\geq n_{0}$ and any $m$,

$X_{n}(K^{m})=X_{n}(K\otimes_{F}F^{m})=(X_{n})_{F}(F^{m})=(X_{n_{0}})_{F}(F^{m})=X_{n_{0}}(K^{m}),$

and this suffices to conclude that $X_{n}=X_{n_{0}}$. ∎

In view of Proposition 4.5.1, from now on we assume that $K$ is a prime field.

An important reason for this assumption is that we can then use Lemma 3.5.2.
We believe that the proof below can be adapted to arbitrary finite fields, and
this might actually give more general results. In particular, in the proof
below we will act with the operators $F_{n+1,j}=F_{n+1,j}[1]$; and in the
general case we would have to work with the operators $F_{n+1,j}[b]$ for
$b\in\\{1,\ldots,q-1\\}$. But the reasoning below is already rather subtle,
and we prefer not to make it more opaque by the additional technicalities
coming from non-prime fields.

###  4.6. The embedding theorem

We will prove Theorem 4.1.2 via an auxiliary result of independent interest.
Let $P$ be a polynomial representation of positive degree $d$ and let $R$ an
irreducible subobject of $P_{>d-1}$. Let $\pi:P\to P/R=:P^{\prime}$ be the
projection. Dually, this gives rise to an embedding $K[P/R]\subseteq K[P]$.
For a fixed $V\in\mathbf{Vec}$, if we choose elements $y_{1},\ldots,y_{n}\in
P(V)^{*}$ that map to a basis of $R(V)^{*}$, then we can write elements of
$K[P(V)]$ as reduced polynomials in $y_{1},\ldots,y_{n}$ with coefficients
that are elements of $K[P^{\prime}(V)]$. We note, however, that $R$ is
typically not a direct summand of $P$. This implies, for instance, that when
acting with $\operatorname{End}\nolimits(V)$ on $y_{i}$, we typically do not
stay within the linear span of the $y_{1},\ldots,y_{n}$ but also get terms
that are linear functions in $K[P^{\prime}(V)]$.

Let $X$ be a subset of $P$, and let $X^{\prime}$ be the image of $X$ in $P/R$,
i.e. $X^{\prime}(V):=\pi(X(V))$ (to simplify notation, we write $\pi$ instead
of $\pi_{V}$).

Now there are two possibilities:

  1. (1)

$X=\pi^{-1}(X^{\prime})$, i.e., $X(V)=\pi^{-1}(X^{\prime}(V))$ for all $V$. In
this case, $I_{X}$ is generated by $I_{X^{\prime}}\subseteq
K[P^{\prime}]\subseteq K[P]$.

  2. (2)

there exists a space $V$ and an element $f\in I_{X}(V)$ such that $f$ does not
lie in $K[P]\cdot I_{X^{\prime}}$.

######  Theorem 4.6.1 (Embedding theorem).

Assume, as above, that $K$ is a prime field. From any $f\in I_{X}(V)\setminus
K[P(V)]\cdot I_{X^{\prime}}(V)$, we can construct a $U\in\mathbf{Vec}$ and a
polynomial $h$ in $K[P(U)]$ of degree strictly smaller than that of $f$, such
that also $h$ does not vanish identically on $\pi^{-1}(X^{\prime}(U))$ and
such that the projection $\mathrm{Sh}_{U}P\to(\mathrm{Sh}_{U}P)/R$ restricts
to a injective map on $(\mathrm{Sh}_{U}X)[1/h]$.

Here $(\mathrm{Sh}_{U}X)(V):=X(U\oplus V)\subseteq P(U\oplus
V)=(\mathrm{Sh}_{U}P)(V)$ and $(\mathrm{Sh}_{U}X)[1/h]$ is the subset of
$\mathrm{Sh}_{U}$ consisting of points $p$ where $h(p)\neq 0$. A warning here
is that $h$ may actually vanish identically on $X(U)$, in which case the
conclusion is trivial because $(\mathrm{Sh}_{U}X)[1/h]$ is empty. But in our
application to the Noetherianity theorem, this will be irrelevant.

###  4.7. Proof of Noetherianity from the embedding theorem

###### Proof.

Proceeding by induction on $P$ along the partial order from §2.7, we may
assume that Noetherianity holds for every representation $Q\prec P$; we call
this the outer induction assumption.

Let $d$ be the degree of $P$. If $d=0$, then $P(V)$ is a fixed finite set, and
clearly any chain of subsets stabilises. So we may assume that $d>0$.

Let $R$ be an irreducible sub-representation in the subrepresentation
$P_{>d-1}$ of $P$. Given a subset $X$ of $P$, we write $X^{\prime}$ for its
projection in $P^{\prime}:=P/R$.

We define $\delta_{X}\in\\{1,2,\ldots,\infty\\}$ as the minimal degree of a
polynomial in $I_{X}\setminus K[P]\cdot I_{X^{\prime}}$; this is $\infty$ if
$I_{X}=K[P]\cdot I_{X^{\prime}}$.

For $X,Y$ subsets of $P$ we write $X>Y$ if either $X^{\prime}\supsetneq
Y^{\prime}$ or else $X^{\prime}=Y^{\prime}$ but
$\delta_{X^{\prime}}>\delta_{Y^{\prime}}$. Since, by the outer induction
assumption, $P^{\prime}$ is Noetherian, this is a well-founded partial order
on subsets of $P$. To prove that a given subset $X\subseteq P$ is Noetherian,
we may therefore assume that all subsets $Y\subseteq P$ with $Y<X$ are
Noetherian; this is the inner induction hypothesis.

Now if $\delta_{X}=\infty$, then any proper subset $Y$ of $X$ satisfies $Y<X$,
so we are done. We are therefore left with the case where
$\delta_{X}\in{\mathbb{Z}}_{\geq 1}$.

Let $f\in I_{X}\setminus(K[P]\cdot I_{X^{\prime}})$ be an element of degree
$\delta_{X}$. By the embedding theorem, there exists an element $h\in
K[P(U)]\setminus I_{X}(U)$ of degree $<\delta_{X}$ such that
$(\mathrm{Sh}_{U}X)[1/h]\to(\mathrm{Sh}_{U}P)/R$ is an injective map. Since
$(\mathrm{Sh}_{U}P)/R\prec P$, $(\mathrm{Sh}_{U}X)[1/h]$ is Noetherian by the
outer induction hypothesis.

Define $Y$ as the subset of $X$ defined by the vanishing of $h$. Explicitly,

$Y(V):=\\{p\in
X(V)\mid\forall\varphi\in\operatorname{Hom}\nolimits_{\mathbf{Vec}}(V,U):h(P(\varphi)p)=0\\}.$

Let $Y^{\prime}\subseteq X^{\prime}$ be the projection of $Y$ in $P/R$. If
$Y^{\prime}\subsetneq X^{\prime}$, then $Y<X$ and hence $Y$ is Noetherian by
the inner induction hypothesis. If $Y^{\prime}=X^{\prime}$, then $h\in
I_{Y}(U)\setminus(K[P(U)]\cdot I_{Y^{\prime}}(U))$, and hence
$\delta_{Y}\leq\deg(h)<\delta_{X}$. So then, too, $Y<X$, and $Y$ is Noetherian
by the induction hypothesis.

Now consider a chain

$X\supseteq X_{1}\supseteq X_{2}\supseteq\ldots$

of subsets. By the above two paragraphs, from some point on both the chain
$(X_{i}\cap Y)_{i}$ and the chain $((\mathrm{Sh}_{U}X_{i})[1/h])_{i}$ have
stabilised. We claim that then also the chain $(X_{i})_{i}$ has stabilised.

Indeed, take $p\in X_{i}(W)$. If $p\in X_{i}(W)\cap Y(W)$, then also $p\in
X_{i+1}(W)\cap Y(W)$ by the first chain, and we are done. If not, then let
$\varphi:W\to U$ be a linear map such that $h(P(\varphi)p)\neq 0$. Let
$\iota:W\to U\oplus W$ be the embedding $w\mapsto(\varphi(w),w)$. Then we find
that

$\displaystyle P(\iota)p\in X_{i}(U\oplus
W)[1/h]=(\mathrm{Sh}_{U}X_{i})(W)[1/h]$
$\displaystyle=(\mathrm{Sh}_{U}X_{i+1})(W)[1/h]\subseteq X_{i+1}(U\oplus W).$

Now if $\rho:U\oplus W\to W$ is the projection, then we find that
$p=P(\rho)P(\iota)p\in P(\rho)X_{i+1}(U\oplus W)=X_{i+1}(W)$, as desired. ∎

###  4.8. Proof of the embedding theorem

###### Proof.

Recall that $P$ has degree $d>0$, $X\subseteq P$ is a subset, $R$ an
irreducible subrepresentaion of $P_{>d-1}$, $\pi:P\to P/R$ is the projection,
$X^{\prime}=\pi(X)$, $X\neq\pi^{-1}(X^{\prime})$, and $f\in
I_{X}(V)\setminus(K[P(V)]\cdot I_{X^{\prime}}(V))$. Assume that $f$ has degree
$\delta$. Recall from Lemma 2.8.2 that $V^{*}\mapsto K[P(V)]_{\leq\delta}$ is
a polynomial representation. Furthermore, this has subrepresentations
$V^{*}\mapsto I_{X}(V)_{\leq\delta}$ and $V^{*}\mapsto(K[P(V)]\cdot
I_{X^{\prime}}(V))_{\leq}\delta$.

We may assume that $V=K^{n}$, and without loss of generality, $f$ is a weight
vector. We will act on $f$ with elements $g_{n+1,j}(s)^{T}$; see Example 2.8.3
for an explanation of the transpose. The part of degree $b$ in $s$ is then
captured by the operator $F_{n+1,j}[b]$.

After acting repeatedly with operators $F_{n+1,j}[b]$ (for increasing values
of $n$ and possibly $j$ and observing that this does not increase the degree
of $f$), we may assume that the image of $f\in K[P(K^{n})]$ in the quotient
representation

$I_{X}(K^{n})_{\leq\delta}/(K[P(K^{n})]\cdot
I_{X^{\prime}}(K^{n}))_{\leq\delta}$

is maximally spread out (see Proposition 3.4.3). After passing to a coordinate
subspace, by Remark 3.5.4, this implies that the weight of $f$ is
$(1,\ldots,1)$. Moreover, it implies that if we split, for any
$j\in\\{1,\ldots,n\\}$, $\tilde{f}:=F_{n+1,j}f$ as
$\tilde{f}_{0}+\tilde{f}_{1}$ where $\tilde{f}_{0}$ has weight
$(1,\ldots,0,\ldots,1,1)$ and $\tilde{f}_{1}$ has weight
$(1,\ldots,q-1,\ldots,1,1)$, then $\tilde{f}_{1}$ vanishes identically on
$X^{\prime}(K^{n+1})$—indeed, otherwise $\tilde{f}_{1}$ would be a more
spread-out polynomial that vanishes identically on $X$ but not on
$X^{\prime}$.

Choose a basis $\mathbf{x}$ of $(P^{\prime}(K^{n}))^{*}\subseteq P(K^{n})^{*}$
consisting of weight vectors, and extend this to a basis
$\mathbf{x},\mathbf{y}$ of $P(K^{n})^{*}$ of weight vectors. This means that
$\mathbf{y}$ maps to a weight basis of $R(K^{n})^{*}$. Relative to these
choices, we can write $f$ as a reduced polynomial

(1) $f=\sum_{\alpha}f_{\alpha}(\mathbf{x})\mathbf{y}^{\alpha}$

for suitable exponent vectors $\alpha$ and nonzero functions $f_{\alpha}\in
K[P^{\prime}(K^{n})]$. We choose this expression reduced relative to
$I_{X^{\prime}}(K^{n})$ in the following sense: no nonempty subset of the
terms of any $f_{\alpha}$ add up to a polynomial in $I_{X^{\prime}}(K^{n})$.
This implies that no $f_{\alpha}$ is in the ideal of $I_{X^{\prime}}(K^{n})$,
but the requirement is a bit stronger than that.

Let $y_{0}$ be one of the elements in $\mathbf{y}$ that appears in $f$; we
further choose $y_{0}$ such that the support in $\\{1,\ldots,n\\}$ of its
weight is inclusion-wise minimal. Consider the expression (coarser than (1)):

$f=f_{0}(\mathbf{x},\mathbf{y}\setminus\\{y_{0}\\})y_{0}^{0}+\dots+f_{c}(\mathbf{x},\mathbf{y}\setminus\\{y_{0}\\})y_{0}^{c}$

where $f_{e}$ is a reduced polynomial in $\mathbf{x}$ and the variables in
$\mathbf{y}$ except for $y_{0}$; and where $f_{c}\neq 0$ and
${c}\in\\{1,\ldots,q-1\\}$. Note that $f_{0}$ is a weight vector of the same
weight as $f$. A priori, the coefficients $f_{e}$ with $e>0$ need not be
weight vectors, since the weight monoid $(\\{0,\ldots,q-1\\}^{n},\oplus)$ is
not cancellative. However, all terms in $f_{e}$ have the same weight up to
identifying $0$ and $q-1$, and upon adding $e$ times the weight of $y_{0}$ to
any of them (using the operation $\oplus$), one obtains the weight
$(1,\ldots,1)$ of $f$.

######  Lemma 4.8.1.

We have ${c}=1$, $f_{1}$ is a weight vector, and after a permutation $f_{1}$
has weight $(1^{m},0^{n-m})$ and $y_{0}$ has weight $(0^{m},1^{n-m})$ for some
$m$.

###### Proof.

To prove the claim, let $j\in[n]$ be such that the weight
$\chi=(a_{1},\ldots,a_{n})$ of $y_{0}$ has $a_{j}>0$.

We partition the variables $\mathbf{y}$ into three subsets: those whose weight
has an entry $0$ in position $j$ are collected in the tuple $\mathbf{y}_{0}$;
those with a $1$ there in the tuple $\mathbf{y}_{1}$; and those with an entry
$>1$ there in the tuple $\mathbf{y}_{>1}$.

We construct a weight basis of $P(K^{n+1})^{*}$ consisting of:

  * •

$\mathbf{x},\mathbf{y}_{0},\mathbf{y}_{1},$ and $\mathbf{y}_{>1}$;

  * •

the tuple $(n+1,j)\mathbf{y}_{1}$ obtained by applying $(n+1,j)$ to each
variable in $\mathbf{y}_{1}$;

  * •

the tuple $F_{n+1,j}\mathbf{y}_{>1}$ obtained by applying $F_{n+1,j}$ to each
variable in the tuple $\mathbf{y}_{>1}$;

  * •

weight elements that together with $\mathbf{x}$ form a basis of
$P(K^{n+1})^{*}$; and

  * •

weight elements that along with
$\mathbf{y}_{0},\mathbf{y}_{1},\mathbf{y}_{>1},(n+1,j)\mathbf{y}_{1},F_{n+1,j}\mathbf{y}_{>1}$
project to a weight basis of $R(K^{n+1})^{*}$.

The only non-obvious thing here is that the elements in
$F_{n+1,j}\mathbf{y}_{>1}$ can be chosen as part of a set mapping to a basis
of $R(K^{n+1})^{*}$, and this follows from Lemma 3.5.2. Note that none of the
variables in the tuples $(n+1,j)\mathbf{y}_{1}$ and $F_{n+1,j}\mathbf{y}_{>1}$
has a $q-1$ on position $j$ of its weight.

Either $y_{0}$ belongs to $\mathbf{y}_{1}$, or to $\mathbf{y}_{>1}$. In the
first case we define $y_{1}:=(n+1,j)y_{0}$, and in the second case we define
$y_{1}:=F_{n+1,j}y_{0}$. In both cases, $y_{1}$ is the (nonzero)
weight-$(a_{1},\ldots,a_{j}-1,\ldots,a_{n},1)$-component of $F_{n+1,j}y_{0}$
and one of the chosen variables. (In the first case, this uses Lemma 3.4.1.)

Consider

(2)
$g_{n+1,j}(s)^{T}f=\sum_{e=0}^{c}(f_{e}(g_{n+1,j}(s)^{T}\mathbf{x},g_{n+1,j}(s)^{T}(\mathbf{y}\setminus\\{y_{0}\\})))(g_{n+1,j}(s)^{T}y_{0})^{e}.$

From the ${c}$-th term we get a contribution $f_{c}\cdot{c}\cdot s\cdot
y_{0}^{{c}-1}\cdot y_{1}$, which is nonzero because ${c}<q-1$ and $q$ is
prime.

Rewriting (2) as a reduced polynomial in $s,y_{0},y_{1}$ with coefficients
that are reduced polynomials in the remaining chosen variables in
$P(K^{n+1})^{*}$, we claim that $f_{c}\cdot{c}$ is precisely the coefficient
of $s\cdot y_{0}^{{c}-1}\cdot y_{1}$. Indeed, $y_{0},y_{1}$ only appear in the
terms $y_{0}=F_{n+1,j}[0]y_{0}$ and $F_{n+1,j}[1]y_{0}$ from
$g_{n+1,j}(s)^{T}y_{0}$ and nowhere in
$f_{e}(g_{n+1,j}(s)^{T}\mathbf{x},g_{n+1,j}(s)^{T}(\mathbf{y}\setminus\\{y_{0}\\}))$
because:

  * •

$g_{n+1,j}(s)^{T}$ maps the coordinates $\mathbf{x}$ into linear combinations
of $\mathbf{x}$ and the further chosen variables in $P^{\prime}(K^{n+1})^{*}$;

  * •

$y_{0},y_{1}$ do not appear in $F_{n+1,j}[b]\mathbf{y}$ for $b>1$ for weight
reasons: expressing the elements in the latter tuple on the basis of the
chosen variables, all variables have weights with a $b>1$ at position $n+1$,
while $y_{0},y_{1}$ have a $0$ and $1$ there, respectively;

  * •

$y_{0}$ does not appear in $F_{n+1,j}[1]y$ for any variable $y$ in
$\mathbf{y}$, again by comparing the weights in position $n+1$;

  * •

$y_{1}$ is different from all variables $F_{n+1,j}[1]y$ where $y$ ranges over
the variables in $\mathbf{y}_{>1}$ (other than $y_{0}$, if $y_{0}$ is in
$\mathbf{y}_{>1}$);

  * •

$y_{1}$ is different from all variables $(n+1,j)y$ where $y$ ranges over the
variables in $\mathbf{y}_{1}$ (other than $y_{0}$, if $y_{0}$ is in
$\mathbf{y}_{1}$); and indeed

  * •

$y_{1}$ does not appear in the weight component
$y^{\prime}=F_{n+1,j}y-(n+1,j)y$ of any variable $y$ in $\mathbf{y}_{1}$.
Indeed, if $(a_{1}^{\prime},\ldots,1,\ldots,a_{n}^{\prime})$ is the weight of
$y$, then $y^{\prime}$ has weight
$(a_{1}^{\prime},\ldots,q-1,\ldots,a_{n}^{\prime},1)$. But, as remarked
earlier, the variable $y_{1}$ constructed from $y_{0}$ does not have a $q-1$
on position $j$ in its weight.

We conclude that, when writing $\tilde{f}=F_{n+1,j}f$ as a polynomial in the
chosen variables, the terms divisible by $y_{0}^{{c}-1}y_{1}$ are precisely
those in ${c}\cdot f_{c}\cdot y_{0}^{{c}-1}y_{1}$. Now in $f_{c}$, expanded as
a reduced polynomial in $\mathbf{y}\setminus\\{y_{0}\\}$ with coefficients
that are reduced polynomials in $\mathbf{x}$, consider any nonzero term
$\ell(\mathbf{x})(\mathbf{y}\setminus\\{y_{0}\\})^{\alpha}$. By reducedness of
$f$, no nonempty subset of the terms of $\ell(\mathbf{x})$ add up to a
polynomial that vanishes identically on $X^{\prime}(K^{n})$. Group the terms
in $\ell(\mathbf{x})$ into two parts:
$\ell(\mathbf{x})=\ell_{0}(\mathbf{x})+\ell_{1}(\mathbf{x})$, in such a manner
that
$\ell_{0}(\mathbf{x})\cdot(\mathbf{y}\setminus\\{y_{0}\\})^{\alpha}y_{0}^{{c}-1}y_{1}$
is the part of
$\ell(\mathbf{x})(\mathbf{y}\setminus\\{y_{0}\\})^{\alpha}y_{0}^{{c}-1}y_{1}$
that has weight $(1,\ldots,0,\ldots,1,1)$ and hence is part of
$\tilde{f}_{0}$, and
$\ell_{1}(\mathbf{x})\cdot(\mathbf{y}\setminus\\{y_{0}\\})^{\alpha}y_{0}^{{c}-1}$
has weight $(1,\ldots,q-1,\ldots,1,1)$ and hence is part of $\tilde{f}_{1}$.
Since $\tilde{f}_{1}$ vanishes identically on $\pi^{-1}(X^{\prime})$, we find
that $\ell_{1}(\mathbf{x})$ does, too. Hence, since no nonempty set of terms
in $\ell$ adds up to a polynomial that vanishes on $X^{\prime}(K^{n})$, we
have $\ell_{1}(\mathbf{x})=0$ and $\ell(\mathbf{x})=\ell_{0}(\mathbf{x})$. It
follows that
$\ell(\mathbf{x})(\mathbf{y}\setminus\\{y_{0}\\}^{\alpha})y_{0}^{{c}-1}y_{1}$
is a weight vector of weight $(1,\ldots,0,\ldots,1,1)$. Since the term
$\ell(\mathbf{x})(\mathbf{y}\setminus\\{y_{0}\\})^{\alpha}$ in
$f_{c}(\mathbf{x},\mathbf{y}\setminus\\{y_{0}\\})$ was arbitrary, we find that
$f_{c}y_{0}^{{c}-1}y_{1}$ is a weight vector of weight
$(1,\ldots,0,\ldots,1,1)$. Since the weight of $y_{0}$ has a positive entry on
position $j$, we find that ${c}-1=0$ and all weights appearing in $f_{c}$ have
a $0$ on position $j$.

Now $j$ was arbitrary in the support of the weight of $y_{0}$, so the weights
appearing in $f_{c}$ all have disjoint support from that of $y_{0}$. But the
only way, in the weight monoid $\\{0,1,\ldots,q-1\\}^{n}$, to obtain the
weight $(1,\ldots,1)$ as a $\oplus$-sum of two weights with disjoint supports
is that, after a permutation, one weight is $(1^{m},0^{n-m})$ and the other
weight is $(0^{m},1^{n-m})$. Hence $f_{b}$ is a weight vector that, after that
permutation, has the former weight, and then $y_{0}$ has the latter. ∎

Now we have found that

$f=f_{0}+f_{1}\cdot y_{0}$

where $f_{1}$ does not vanish identically on $\pi^{-1}(X^{\prime})$; $f_{1}$
has weight $(1^{m},0^{n-m})$, $y_{0}$ has weight $\chi=(0^{m},1^{n-m})$, and
$f_{0}$ does not involve $y_{0}$. It might be, though, that $f_{0}$ still
contains other variables $y$ in $\mathbf{y}$ of the same weight
$\chi=(0^{m},1^{n-m})$. Therefore, among the $\mathbf{y}$-variables, let
$y_{0}=\hat{y}_{1},\hat{y}_{2},\ldots,\hat{y}_{N}$ be those that have weight
equal to $\chi$; so $N$ is the multiplicity of $\chi$ in $R(K^{n})^{*}$. Then
the above implies that

(3) $f=\hat{f}_{1}\hat{y}_{1}+\cdots+\hat{f}_{N}\hat{y}_{N}+r$

where each $\hat{f}_{i}$ has weight $(1^{m},0^{n-m})$ and where the
$\mathbf{y}$-variables that appear in $r$ have weight vectors with at least
one nonzero entry in the first $m$ positions (here we use that $y_{0}$ had a
weight vector of minimal support). Note that $\hat{f}_{1}=f_{0}$ does not
vanish identically on $X^{\prime}(K^{n})$.

Now set $U:=K^{m}$, $W:=K^{n-m}$, and $h:=\hat{f}_{1}$. Note that $h\in
K[P(U)]$, since its weight is $(1^{m},0^{n-m})$. Also, $h$ has lower degree
than $f$, as desired, and does not vanish identically on
$\pi^{-1}(X^{\prime}(U))$. In fact, all $\hat{f}_{i}$ are polynomials in
$K[P(U)]$, the $\hat{y}_{i}$ map to coordinates on $R(W)$, and $r$ is a
polynomial in $K[(\mathrm{Sh}_{U}P)(W)/R(W)]$ because every
$\mathbf{y}$-variable in $r$ has at least one nonzero entry among the first
$m$ entries of its weight.

We claim that $(\mathrm{Sh}_{U}X)[1/h]\to(\mathrm{Sh}_{U}P)/R$ is injective.
We first show that this is the case when evaluating at $W=K^{n-m}$. Consider
two points $p,p^{\prime}\in(\mathrm{Sh}_{U}X)[1/h](W)$ with the same
projection in $(\mathrm{Sh}_{U}P)(W)/R(W)$, so that $p-p^{\prime}\in R(W)$.
Then $f$ vanishes at both $p$ and $p^{\prime}$ and, in (3), we have
$\hat{f}_{i}(p)=\hat{f}_{i}(p^{\prime})=:c_{i}\in K$ for all $i$, as well as
$r(p)=r(p^{\prime})$. Then (3) shows that

$c_{1}\hat{y}_{1}(p)+\cdots+c_{N}\hat{y}_{N}(p)=c_{1}\hat{y}_{1}(p^{\prime})+\cdots+c_{N}\hat{y}_{N}(p^{\prime}).$

This can be expressed as $L(p-p^{\prime})=0$ for a linear form $L\in R(W)^{*}$
which is nonzero because $c_{1}=h(p)=h(p^{\prime})\neq 0$. Now act with an
element $\psi\in\operatorname{End}\nolimits(K^{n-m})$ on (3), and then
substitute $p$ and $p^{\prime}$. This yields the identity
$L(R(\psi)(p-p^{\prime}))=0$. Hence we obtain a nonzero
$\operatorname{End}\nolimits(K^{n-m})$-submodule of linear forms in
$R(K^{n-m})^{*}$ that are zero on $p-p^{\prime}$. But since $R$, and hence
$R^{*}$, are irreducible $\operatorname{End}\nolimits(K^{n-m})$-modules by
Remark 2.4.3, this means that $p-p^{\prime}=0$. The same argument applies when
$W$ is replaced by $K^{s}$ for any $s$. This completes the proof of the
embedding theorem. ∎

###  4.9. The weak shift theorem

The embedding theorem can be used to show that the behaviour of Example 4.4.3
is typical.

######  Corollary 4.9.1 (Weak shift theorem).

Suppose, as in the embedding theorem, that $K$ is a prime field of cardinality
$q$. For any nonempty subset $X$ of some polynomial generic representation
$P$, there exist a $U\in\mathbf{Vec}$, a nonzero function $h$ on $X(U)$, and a
polynomial $A(n)\in{\mathbb{Q}}[n]$ such that for all $n\in{\mathbb{N}}$ the
cardinality of $(\mathrm{Sh}_{U}X)[1/h](K^{n})$ equals $q^{A(n)}$.

In other words, at least in a counting sense, $(\mathrm{Sh}_{U}X)[1/h](K^{n})$
is an affine space of dimension $A(n)$ over $K$. We expect there to be a
stronger version of this theorem, similar to the shift theorem in [BDES21],
which says that this affine space is functorial in $V$. But we do not yet know
the precise statement of this stronger theorem. Note that, by applying the
weak shift theorem to the subset $Y$ of $X$ defined by the vanishing of $h$,
and so on, we obtain a kind of stratification of $X$ by finitely many affine
spaces. A stronger version of the weak shift theorem would therefore give
deeper insight into the geometric structure of general restriction-closed
properties of tensors.

###### Proof of the weak shift theorem from the embedding theorem.

If $P$ has degree $0$, then $X=X(0)$ is a finite set, and we can choose $U=0$
and $h$ to vanish on all but one point of $X(0)$, so that
$(\mathrm{Sh}_{U}X)[1/h]$ is that remaining point.

Now assume that $P$ has degree $d>0$ and that the result holds for all
polynomial representations $Q\prec P$. Let $R$ be an irreducible subobject of
$P_{>d-1}$ and let $X^{\prime}$ be the projection of $X$ in $P^{\prime}:=P/R$.

There are two cases. First assume that $X$ is the preimage of $X^{\prime}$.
Since $P^{\prime}\prec P$, by the induction assumption there exists a $U$ and
an $h\in P^{\prime}(U)$ that does not vanish on $X^{\prime}(U)$ such that
$|(\mathrm{Sh}_{U}X^{\prime})[1/h](K^{n})|=q^{A(n)}$ for some polynomial
$A(n)$. Now $(\mathrm{Sh}_{U}X)[1/h](K^{n})$ is the preimage of
$(\mathrm{Sh}_{U}X^{\prime})[1/h](K^{n})$, with fibres
$(\mathrm{Sh}_{U}R)(K^{n})$. The fibre is a finite-dimensional vector space
over $K$ whose dimension is a polynomial $B(n)$. Hence
$|(\mathrm{Sh}_{U}X)[1/h^{\prime}](K^{n})|=q^{A(n)+B(n)}$, as desired.

If $X$ is not the preimage of $X^{\prime}$, then we have seen that there
exists a $U_{1}\in\mathbf{Vec}$, a polynomial $h_{1}\in K[P(U_{1})]$ that does
not vanish on $X$, and an injection

$(\mathrm{Sh}_{U_{1}}X)[1/h_{1}]\to((\mathrm{Sh}_{U_{1}}P)/R)=:Q.$

Let $Y$ be the image of this injection. Since $Q\prec P$, there exist
$U_{2}\in\mathbf{Vec}$ and $h_{2}\in K[Q(U_{2})]$ such that
$|(\mathrm{Sh}_{U_{2}}Y)[1/h_{2}](K^{n})|=q^{A(n)}$ for some polynomial $n$.
Now set $U:=U_{1}\oplus U_{2}$ and $h:=h_{1}\cdot h_{2}$ and we find that

$|(\mathrm{Sh}_{U}X)[1/h](K^{n})|=q^{A(n)},$

as desired. ∎

##  5\. Relations to $\mathbf{FI}$ and algorithms

###  5.1. $\mathbf{FI}$ and testing properties via subtensors

We recall from [CEF15] that $\mathbf{FI}$ is the category of finite sets with
injections and that an $\mathbf{FI}$-module over $K$ is a functor from
$\mathbf{FI}$ to $\mathbf{Vec}$. The central result that we will use is the
following.

######  Theorem 5.1.1 ([CEF15]).

For any field $K$, any finitely generated $\mathbf{FI}$-module $M$ over $K$ is
Noetherian in the sense that every $\mathbf{FI}$-submodule is finitely
generated.

We now use this to establish item (4) in Corollary 1.3.3.

######  Theorem 5.1.2.

Let $P$ be a polynomial generic representation over the finite field $K$, and
let $X\subseteq P$ be a subset. Then there exists an $n_{0}$ such that for any
$n\in{\mathbb{Z}}_{\geq 0}$, an element $p\in P(K^{n})$ lies in $X(K^{n})$ if
and only if, for every subset $S$ of $[n]$ of size $n_{0}$, the image of $p$
in $P(K^{S})$ under the linear map corresponding to the coordinate projection
$K^{n}\to K^{S}$ lies in $X(K^{S})$.

###### Proof.

Noetherianity for subsets of $P$ (Theorem 4.1.2) implies that the ideal
$I_{X}$ is finitely generated. In particular, $I_{X}$ is generated by
$(I_{X})_{\leq e}$ for some finite degree $e$. Now consider the functor $F$
from $\mathbf{FI}$ to $\mathbf{Vec}$ that assigns to any finite set $S$ the
space $K[P(K^{S})]_{\leq e}$ and to every injection $\iota:S\to T$ the
embedding $K[P(K^{S})]_{\leq e}\to K[P(K^{T})]_{\leq e}$ coming from the
pullback along the linear map $P(K^{T})\to P(K^{S})$ associated to $\iota$.
Since weights in $K[P(K^{S})]_{\leq e}$ have at most $de$ nonzero entries,
where $d=\deg(P)$ (see Lemma 2.8.2), $F$ is generated by $F([de])$, hence a
finitely generated $\mathbf{FI}$-module. By Theorem 5.1.1, the
$\mathbf{FI}$-submodule $S\mapsto I_{X}(K^{S})$ is also finitely generated,
say by $I_{X}(K^{n_{0}})$. This $n_{0}$ has the desired property. ∎

###  5.2. Algorithms

As noted in the introduction, the theorem just established implies the
existence of a polynomial-time algorithm for testing the property $X$.

###  5.3. Infinite tensors

We conclude with a theorem about infinite tensors. Let
$P:\mathbf{Vec}\to\mathbf{Vec}$ be a polynomial generic representation over
the finite field $K$. Define

$P_{\infty}:=\lim_{\leftarrow n}P(K^{n})$

where the limit is along the projections $P(K^{n+1})\to P(K^{n})$ coming from
the projections $K^{n+1}\to K^{n}$ forgetting the last entry. In the case
where $P(V)=V^{\otimes d}$, $P_{\infty}$ can be thought of as the space of
${\mathbb{N}}\times\cdots\times{\mathbb{N}}$-tensors (with $d$ factors
${\mathbb{N}}$). The space $P_{\infty}$ carries the inverse limit of discrete
topologies, or, equivalently, the Zariski topology in which closed subsets are
defined by the vanishing of (possibly infinitely many) functions in the ring

$K[P_{\infty}]:=\lim_{n\to\infty}K[P(K^{n})].$

On $P_{\infty}$ and $K[P_{\infty}]$ acts the monoid $\Pi$ of matrices that
differ from the identity matrix only in finitely many positions. Let
$X\subseteq P$ be a subset in the sense of Definition 4.1.1. Then
$X_{\infty}:=\lim_{\leftarrow n}X(K^{n})$ is a subset of $P_{\infty}$.

######  Proposition 5.3.1.

The correspondence that sends $X\subseteq P$ to $X_{\infty}\subseteq
P_{\infty}$ is a bijection between subsets of $P$ and closed, $\Pi$-stable
subsets of $P_{\infty}$.

###### Proof.

The subset $X_{\infty}$ is clearly closed and $\Pi$-stable. Conversely, let
$Y\subseteq P_{\infty}$ be closed and $\Pi$-stable. Define $Y_{n}\subseteq
P(K^{n})$ as the image of $Y$ under the projection $P_{\infty}\to P_{n}$, and
for any $V\in\mathbf{Vec}$ define $X(V)$ to be the image of $Y_{n}$ under
$P(\varphi)$ for any linear isomorphism $K^{n}\to V$; this is independent of
the choice of $\varphi$.

We claim that $X$ is a subset of $P$. Indeed, if $\psi:V\to W$ is any linear
map and $\varphi:K^{n}\to V$ a bijection, then we have to show that
$P(\psi)P(\varphi)Y_{n}$ is contained in $P(\varphi^{\prime})Y_{m}$ where
$\varphi^{\prime}:K^{n^{\prime}}\to W$ is a bijection. Now the map
$(\varphi^{\prime})^{-1}\psi\varphi:K^{n}\to K^{n^{\prime}}$ extends to a
linear map $\alpha:K^{m}\to K^{m}$, where $m:=\max\\{n,n^{\prime}\\}$ and we
regard $K^{n}$ and $K^{n^{\prime}}$ as the subspaces of $K^{m}$ where the last
$m-n$ and $m-n^{\prime}$ entries, respectively, are zero. The map $\alpha$, in
turn, can be regarded an element of $\Pi$. Consequently, $Y$ is invariant
under $\alpha$, and therefore so is $Y_{m}$. This shows that the map
$P((\varphi^{\prime})^{-1}\psi\varphi)$ maps $Y_{n}$ into $Y_{n^{\prime}}$, so
that $P(\psi)$ maps $X(V)$ into $X(W)$, as desired.

Next we claim that $X_{\infty}=Y$. Indeed, the fact that $Y$ is closed means
precisely that to test whether $(y_{0},y_{1},y_{2},\ldots)$ lies in $Y$, it
suffices to check whether $y_{n}$ lies in $Y_{n}$ for all $y$. And on the
other hand, this is precisely the definition of $X_{\infty}$. ∎

Theorem 4.1.2 now implies the following.

######  Corollary 5.3.2.

Closed, $\Pi$-stable subsets of $P_{\infty}$ satisfy the descending chain
condition. Dually, $\Pi$-stable ideals of $K[P_{\infty}]$ satisfy the
ascending chain condition. $\square$

The latter, ring-theoretic Noetherianity is not known in the context of
infinite fields [Dra19], except in characteristic zero for a few degree-two
polynomial functors [NSS16, SS22]. However, in the current context, all ideals
are radical, since in $K[P_{\infty}]$ every element $f$ satisfies the identity
$f^{q}=f$. This implies that the two statements in the corollary are
equivalent.

## References

  * [AKZ21] Karim Adiprasito, David Kazhdan, and Tamar Ziegler.  On the schmidt and analytic ranks for trilinear forms.  2021\.  Preprint, `arXiv:2102.03659`.
  * [BDD20] Arthur Bik, Alessandro Danelon, and Jan Draisma.  Topological Noetherianity of polynomial functors II: base rings with Noetherian spectrum.  Math. Ann., 2020.  To appear, `arXiv:2011.12739`.
  * [BDE19] Arthur Bik, Jan Draisma, and Rob H. Eggermont.  Polynomials and tensors of bounded strength.  Commun. Contemp. Math., 21(7), 2019.  paper number 1850062 (24 pages).
  * [BDES21] Arthur Bik, Jan Draisma, Rob H. Eggermont, and Andrew Snowden.  The geometry of polynomial representations.  Int. Math. Res. Not., 2021.  To appear, `arXiv:2105.12621`.
  * [CEF15] Thomas Church, Jordan S. Ellenberg, and Benson Farb.  FI-modules and stability for representations of symmetric groups.  Duke Math. J., 164(9):1833–1910, 2015.
  * [CGL+21] Austin Conner, Fulvio Gesmundo, Joseph M. Landsberg, Emanuele Ventura, and Yao Wang.  Towards a geometric approach to Strassen’s asymptotic rank conjecture.  Collect. Math., 72(1):63–86, 2021.
  * [CM21] Alex Cohen and Guy Moshkovitz.  Partition and analytic rank are equivalent over large fields.  Duke Math. J., 2021.  To appear, `arXiv:2102.10509`.
  * [Dra19] Jan Draisma.  Topological Noetherianity of polynomial functors.  J. Am. Math. Soc., 32:691–707, 2019.
  * [FS97] Eric M. Friedlander and Andrei Suslin.  Cohomology of finite group schemes over a field.  Invent. Math., 127(2):209–270, 1997.
  * [GT09] Ben Green and Terence Tao.  The distribution of polynomials over finite fields, with applications to the Gowers norms.  Contrib. Discrete Math., 4(2):1–36, 2009.
  * [Kar22] Thomas Karam.  High-rank minors for high-rank tensors.  2022\.  Preprint, `arXiv:2207.08030`.
  * [Kuh94a] Nicholas J. Kuhn.  Generic representations of the finite general linear groups and the Steenrod algebra. I.  Am. J. Math., 116(2):327–360, 1994.
  * [Kuh94b] Nicholas J. Kuhn.  Generic representations of the finite general linear groups and the Steenrod algebra. II.  $K$-Theory, 8(4):395–428, 1994.
  * [Lov19] Shachar Lovett.  The analytic rank of tensors and its applications.  Discrete Anal., 2019:10, 2019.  Id/No 7.
  * [Mil19] Luka Milićević.  Polynomial bound for partition rank in terms of analytic rank.  Geom. Funct. Anal., 29(5):1503–1530, 2019.
  * [MZ22] Guy Moshkovitz and Daniel G. Zhu.  Quasi-linear relation between partition and analytic rank.  2022\.  Preprint, `arXiv:2211.05780`.
  * [NSS16] Rohit Nagpal, Steven V. Sam, and Andrew Snowden.  Noetherianity of some degree two twisted commutative algebras.  Selecta Math. (N.S.), 22(2):913–937, 2016.
  * [PS17] Andrew Putman and Steven V. Sam.  Representation stability and finite linear groups.  Duke Math. J., 166(13):2521–2598, 2017.
  * [RS04] Neil Robertson and Paul D. Seymour.  Graph minors. XX: Wagner’s conjecture.  J. Comb. Theory, Ser. B, 92(2):325–357, 2004.
  * [Sno21] Andrew Snowden.  Stable representation theory: beyond the classical groups.  2021\.  Preprint, `arXiv:2109.11702`.
  * [SS17] Steven V. Sam and Andrew Snowden.  Gröbner methods for representations of combinatorial categories.  J. Am. Math. Soc., 30(1):159–203, 2017.
  * [SS22] Steven V. Sam and Andrew Snowden.  $\mathrm{Sp}$-equivariant modules over polynomial rings in infinitely many variables.  Trans. Am. Math. Soc., 375(3):1671–1701, 2022.
  * [Ste16] Robert Steinberg.  Lectures on Chevalley groups, volume 66 of Univ. Lect. Ser. Providence, RI: American Mathematical Society (AMS), 2016.