% -------------------------------------------------------------
% NOTE ON THE DETAILED AND SHORT VERSIONS:
% -------------------------------------------------------------
% This paper comes in two versions, a detailed and a short one.
% The short version should be more than sufficient for any
% reasonable use; the detailed one was written purely to
% convince the author of its correctness.
% To switch between the two versions, find the line containing
% "\newenvironment{noncompile}{}{}" in this LaTeX file.
% Look at the two lines right beneath this line.
% To compile the detailed version, they should be as follows:
%   \includecomment{verlong}
%   \excludecomment{vershort}
% To compile the short version, they should be as follows:
%   \excludecomment{verlong}
%   \includecomment{vershort}
% As a rule, the line
%   \excludecomment{noncompile}
% should stay as it is.
% -------------------------------------------------------------
% NOTES ON SOME HACKS USED IN THIS FILE:
% -------------------------------------------------------------
% One of my pet peeves with amsthm is its use of italics in the theorem and
% proposition environments; this makes math and text indistinguishable in said
% enviroments. To avoid this, I redefine the enviroments to use the standard
% font and to use a hanging indent, along with a bold vertical bar to its
% left, to distinguish these environments from surrounding text. (Along with
% the advantage of distinguishing math from text, this also allows nesting
% several such environments inside each other, like a definition inside a
% remark. I'm not sure how good of an idea this is, though. There are also
% downsides related to the hanging indentation, such as footnotes out of it
% being painful to do right.) This is done starting from the line
%   \theoremstyle{definition}
% and until the line
%   {\end{leftbar}\end{exmp}}
% The two lines
%   \newenvironment{proof2}[1][]
%   {\begin{proof}[#1]}{\end{proof}}
% are merely a hack to make Scientific WorkPlace show proofs in its editor.
% Nothing is lost if these lines are removed, provided that all occurrences of
% "proof2" are replaced by "proof" in the document.

\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{framed}
\usepackage{amsmath}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{amsthm}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Wednesday, October 26, 2016 00:16:22}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exmp}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\kk}{\mathbf{k}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\ev}{\operatorname{ev}}
\newcommand{\Comp}{\operatorname{Comp}}
\newcommand{\bk}{\mathbf{k}}
\newcommand{\Nplus}{\mathbb{N}_{+}}
\newcommand{\NN}{\mathbb{N}}
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\setlength\textheight{22.5cm}
\setlength\textwidth{15cm}
\ihead{$p$-polynomials from subspaces}
\ohead{\today}
\begin{document}

\title{On $p$-polynomials and $\mathbb{F}_{p}$-vector subspaces of fields}
\author{Darij Grinberg}
\date{\today}
\maketitle
\tableofcontents

\section{The goals}

This expository note is devoted to some apocryphal properties of fields of
positive characteristic. We shall use the following notations:

\begin{definition}
In the following, rings are always assumed to be associative and with $1$. If
$R$ is a commutative ring, then an $R$\textit{-algebra} means a ring $A$
endowed with an $R$-module structure such that the map $A\times A\rightarrow
A,\ \left(  a,b\right)  \mapsto ab$ is $R$-bilinear. The characteristic of a
field $L$ is denoted by $\operatorname*{char}L$.

The word \textquotedblleft prime\textquotedblright\ always stands for
\textquotedblleft prime number\textquotedblright. Neither $0$ nor $1$ counts
as a prime. The notation $\mathbb{N}$ stands for the set $\left\{
0,1,2,\ldots\right\}  $.
\end{definition}

\begin{definition}
Let $p\in\mathbb{N}$. Let $L$ be a commutative ring. A polynomial $f\in
L\left[  X\right]  $ is said to be a $p$\textit{-polynomial} if $f$ is an
$L$-linear combination of the monomials $X^{p^{0}},X^{p^{1}},X^{p^{2}},\ldots
$. For instance, the polynomial $3X-7X^{2}+X^{4}\in\mathbb{Z}\left[  X\right]
$ is a $2$-polynomial but not a $3$-polynomial.
\end{definition}

Our main goal in this note is to demonstrate the following four interrelated facts:

\begin{theorem}
\label{thm.prod-is-p}Let $V$ be a finite additive subgroup of a field $L$. Let
$p=\operatorname*{char}L$. Then, $\prod\limits_{v\in V}\left(  X+v\right)  \in
L\left[  X\right]  $ is a $p$-polynomial.
\end{theorem}

\begin{theorem}
\label{thm.sum-prod}Let $V$ be a finite additive subgroup of a field $L$. Let
$t\in L\setminus V$. Then,%
\[
\sum\limits_{v\in V}\dfrac{1}{t+v}=\left(  \prod\limits_{v\in V}\dfrac{1}%
{t+v}\right)  \cdot\left(  \prod\limits_{v\in V\setminus0}v\right)  .
\]

\end{theorem}

\begin{theorem}
\label{thm.prod-is-q}Let $q$ be a prime power. Let $L$ be a field extension of
the finite field $\mathbb{F}_{q}$. Let $V$ be a finite $\mathbb{F}_{q}$-vector
subspace of $L$. Then, $\prod\limits_{v\in V}\left(  X+v\right)  \in L\left[
X\right]  $ is a $q$-polynomial.
\end{theorem}

\begin{theorem}
\label{thm.prod-is-q-alg}Let $q$ be a prime power. Let $L$ be a commutative
$\mathbb{F}_{q}$-algebra. Let $V$ be a finite $\mathbb{F}_{q}$-vector subspace
of $L$. Then, $\prod\limits_{v\in V}\left(  X+v\right)  \in L\left[  X\right]
$ is a $q$-polynomial.
\end{theorem}

Note that these four theorems are essentially about fields of positive
characteristic. Indeed, it is easy to show that in Theorem \ref{thm.prod-is-p}
and in Theorem \ref{thm.sum-prod}, the finite subgroup $V$ must be $0$ if
$\operatorname*{char}L=0$; thus, the two theorems become fairly trivial if
$\operatorname*{char}L=0$, and only the case of positive characteristic is interesting.

Let us first comment on the origins of these results:

Theorem \ref{thm.prod-is-q} is a known fact (e.g., it immediately follows from
\cite[Theorem A.1 2) and Corollary A.3]{kc-carlitz}, from \cite[(7.7)]%
{mac-schurvar} or from \cite[Theorem 3.17]{gri-bor-carl}). Theorem
\ref{thm.prod-is-p} is a particular case of Theorem \ref{thm.prod-is-q}
(obtained by setting $q=p=\operatorname*{char}L$ when $\operatorname*{char}%
L\neq0$), and is due to Oystein Ore (\cite[the $\Longrightarrow$ direction of
Theorem 8]{Ore33}).

Theorem \ref{thm.sum-prod} is an auxiliary result from unfinished work
\cite[Proposition 5.3]{gri-bor-carl} of mine and James Borger on Carlitz polynomials.

Theorem \ref{thm.prod-is-q-alg} is also not new (it is precisely \cite[Theorem
3.17]{gri-bor-carl}, and appears implicitly in \cite{mac-schurvar}). Clearly,
it generalizes Theorem \ref{thm.prod-is-q} (since any field extension of
$\mathbb{F}_{q}$ is a commutative $\mathbb{F}_{q}$-algebra).

All of the above four theorems are accessible without much preknowledge (basic
theory of finite fields should be sufficient), and the purpose of this note is
to collect elementary and self-contained proofs.

Theorem \ref{thm.prod-is-p} and Theorem \ref{thm.sum-prod} were posed as a
problem in the PRIMES 2015 application contest\footnote{See problem M6 in
\url{https://math.mit.edu/research/highschool/primes/materials/2015/entpro2015math.pdf}
.}. Some of the proofs below were found by students taking part in the contest.

\section{\label{sect.preps}Preparations}

Before we start proving the above theorems, let us prove some auxiliary facts
that will be useful. Some of these facts are actually well-known results.

\begin{lemma}
\label{lem.Fp-subspace}Let $V$ be a finite additive subgroup of a field $L$.
Let $p=\operatorname*{char}L$. Assume that $V\neq0$.

\textbf{(a)} The number $p$ is prime.

\textbf{(b)} The field $L$ is a field extension of $\mathbb{F}_{p}$.

\textbf{(c)} The subset $V$ is a finite-dimensional $\mathbb{F}_{p}$-vector
subspace of $L$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.Fp-subspace}.]\textbf{(a)} We have $V\neq0$. Thus,
there exists a nonzero vector $v\in V$. Consider such a $v$. Every element of
the additive group $V$ has finite order (because $V$ is finite). In
particular, $v$ has finite order (since $v$ is an element of $V$). In other
words, there exists some positive integer $N$ such that $Nv=0$. Consider this
$N$.

We have $v\in V\subseteq L$. We can divide the equality $Nv=0$ by $v$ (since
$v$ is a nonzero element of the field $L$). We thus obtain $N\cdot1_{L}=0$
(where $1_{L}$ denotes the one of the field $L$). Thus, the field $L$ cannot
have characteristic $0$. In other words, $\operatorname*{char}L$ is positive.
In other words, $p$ is positive (since $p=\operatorname*{char}L$). Hence, $p$
is a prime (since $p=\operatorname*{char}L$ is the characteristic of a field,
and thus is either prime or $0$).
This completes the proof of Lemma \ref{lem.Fp-subspace} \textbf{(a)}.

\textbf{(b)} We know that $\operatorname*{char}L=p$ is prime (by Lemma
\ref{lem.Fp-subspace} \textbf{(a)}). Hence, $L$ is a field extension of
$\mathbb{F}_{p}$. This proves Lemma \ref{lem.Fp-subspace} \textbf{(b)}.

\textbf{(c)} Lemma \ref{lem.Fp-subspace} \textbf{(b)} shows that $L$ is a
field extension of $\mathbb{F}_{p}$. Hence, $L$ is an $\mathbb{F}_{p}$-vector space.

Let $\lambda\in\mathbb{F}_{p}$ and $v\in V$.

We have $\lambda\in\mathbb{F}_{p}=\mathbb{Z}/p\mathbb{Z}$. Hence, there exists
some $n\in\mathbb{Z}$ such that $\lambda=\overline{n}$ (where $\overline{n}$
denotes the residue class of $n$ modulo $p$). Consider such an $n$. We have
$\lambda=\overline{n}$ and thus $\lambda v=n\underbrace{v}_{\in V}\in
nV\subseteq V$ (because $V$ is an additive group).

Now, forget that we fixed $\lambda$ and $v$. We thus have shown that $\lambda
v\in V$ for every $\lambda\in\mathbb{F}_{p}$ and $v\in V$. Thus, $V$ is an
$\mathbb{F}_{p}$-vector subspace of $L$ (since we already know that $V$ is an
additive subgroup of $L$). Moreover, $V$ is finite-dimensional (since $V$ is
finite). This proves Lemma \ref{lem.Fp-subspace} \textbf{(c)}.
\end{proof}

\begin{lemma}
\label{lem.idiot-binom}Let $p$ be a prime. Let $L$ be a commutative
$\mathbb{F}_{p}$-algebra. Any two elements $u$ and $v$ of $L$ satisfy%
\begin{equation}
\left(  u+v\right)  ^{p}=u^{p}+v^{p}. \label{2.sol.a.idiot-binom}%
\end{equation}

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.idiot-binom}.]For every $i\in\left\{  1,2,\ldots
,p-1\right\}  $, the binomial coefficient $\dbinom{p}{i}$ is divisible by $p$
(since $p$ is prime), and thus reduces to $0$ in $L$ (since $L$ is an
$\mathbb{F}_{p}$-algebra). In other words, for every $i\in\left\{
1,2,\ldots,p-1\right\}  $, we have%
\begin{equation}
\dbinom{p}{i}=0\ \ \ \ \ \ \ \ \ \ \text{in }L.
\label{2.sol.a.idiot-binom.pf.1}%
\end{equation}
But $L$ is commutative. Hence, the binomial formula yields%
\begin{align*}
\left(  u+v\right)  ^{p}  &  =\sum_{i=0}^{p}\dbinom{p}{i}u^{i}v^{p-i}%
=u^{p}+\sum_{i=1}^{p-1}\underbrace{\dbinom{p}{i}}_{\substack{=0\text{ in
}L\\\text{(by (\ref{2.sol.a.idiot-binom.pf.1}))}}}u^{i}v^{p-i}+v^{p}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have split off the addends for }i=0\\
\text{and for }i=p\text{ from the sum}%
\end{array}
\right) \\
&  =u^{p}+v^{p}.
\end{align*}
This proves Lemma \ref{lem.idiot-binom}.
\end{proof}

\begin{lemma}
\label{lem.idiot-binom-n}Let $p$ be a prime. Let $L$ be a commutative
$\mathbb{F}_{p}$-algebra. Any two elements $u$ and $v$ of $L$ and any
$n\in\mathbb{N}$ satisfy%
\begin{equation}
\left(  u+v\right)  ^{p^{n}}=u^{p^{n}}+v^{p^{n}}.
\label{2.sol.a.idiot-binom-n}%
\end{equation}

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.idiot-binom-n}.]Lemma \ref{lem.idiot-binom-n} follows
by induction on $n$, using (\ref{2.sol.a.idiot-binom}) and the fact that
$w^{p^{n}}=\left(  w^{p^{n-1}}\right)  ^{p}$ for every $w\in L$
and every positive integer $n$%
.\ \ \ \ \footnote{Here is the argument in more detail:
\par
\textit{Proof of \textit{(\ref{2.sol.a.idiot-binom-n})}:} We shall prove
(\ref{2.sol.a.idiot-binom-n}) by induction on $n$:
\par
\textit{Induction base:} Any $u\in L$ and $v\in L$ satisfy%
\begin{align*}
\left(  u+v\right)  ^{p^{0}}  &  =\left(  u+v\right)  ^{1}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }p^{0}=1\right) \\
&  =\underbrace{u}_{\substack{=u^{1}=u^{p^{0}}\\\text{(since }1=p^{0}\text{)}%
}}+\underbrace{v}_{\substack{=v^{1}=v^{p^{0}}\\\text{(since }1=p^{0}\text{)}%
}}=u^{p^{0}}+v^{p^{0}}.
\end{align*}
In other words, (\ref{2.sol.a.idiot-binom-n}) holds for $n=0$. This completes
the induction base.
\par
\textit{Induction step:} Let $N\in\mathbb{N}$ be positive. Assume that
(\ref{2.sol.a.idiot-binom-n}) holds for $n=N-1$. We must now show that
(\ref{2.sol.a.idiot-binom-n}) holds for $n=N$.
\par
Let $u\in L$ and $v\in L$. We have assumed that (\ref{2.sol.a.idiot-binom-n})
holds for $n=N-1$. Hence, (\ref{2.sol.a.idiot-binom-n}) (applied to $n=N-1$)
yields $\left(  u+v\right)  ^{p^{N-1}}=u^{p^{N-1}}+v^{p^{N-1}}$. But every
$w\in L$ satisfies $w^{p^{N}}=\left(  w^{p^{N-1}}\right)  ^{p}$. Applying this
to $w=u+v$, we find%
\begin{align*}
\left(  u+v\right)  ^{p^{N}}  &  =\left(  \underbrace{\left(  u+v\right)
^{p^{N-1}}}_{=u^{p^{N-1}}+v^{p^{N-1}}}\right)  ^{p}=\left(  u^{p^{N-1}%
}+v^{p^{N-1}}\right)  ^{p}\\
&  =\underbrace{\left(  u^{p^{N-1}}\right)  ^{p}}_{=u^{p^{N}}}%
+\underbrace{\left(  v^{p^{N-1}}\right)  ^{p}}_{=v^{p^{N}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{2.sol.a.idiot-binom}), applied
to }u^{p^{N-1}}\text{ and }v^{p^{N-1}}\text{ instead of }u\text{ and }v\right)
\\
&  =u^{p^{N}}+v^{p^{N}}.
\end{align*}
Thus, we have shown that (\ref{2.sol.a.idiot-binom-n}) holds for $n=N$. This
completes the induction step. The proof of (\ref{2.sol.a.idiot-binom-n}) is
thus finished. In other words, Lemma \ref{lem.idiot-binom-n} is proven.}
\end{proof}

\begin{lemma}
\label{lem.lambdap}Let $p$ be a prime. Any $\lambda\in\mathbb{F}_{p}$
satisfies%
\begin{equation}
\lambda^{p}=\lambda. \label{2.sol.a.lambdap}%
\end{equation}

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.lambdap}.]Let $\lambda\in\mathbb{F}_{p}$. We must
prove (\ref{2.sol.a.lambdap}). If $\lambda=0$, then (\ref{2.sol.a.lambdap}) is
obviously true. Hence, we WLOG assume that $\lambda\neq0$. Thus, $\lambda
\in\mathbb{F}_{p}\setminus\left\{  0\right\}  $.

The multiplicative group $\left(  \mathbb{F}_{p}\right)  ^{\times}%
=\mathbb{F}_{p}\setminus\left\{  0\right\}  $ of the field $\mathbb{F}_{p}$
has $p-1$ elements (since $\left\vert \mathbb{F}_{p}\setminus\left\{
0\right\}  \right\vert =\underbrace{\left\vert \mathbb{F}_{p}\right\vert
}_{=p}-1=p-1$). Hence, the order of any element of this group $\left(
\mathbb{F}_{p}\right)  ^{\times}$ divides $p-1$ (by Lagrange's theorem). In
particular, the order of the element $\lambda$ of $\left(  \mathbb{F}%
_{p}\right)  ^{\times}$ divides $p-1$ (since $\lambda\in\mathbb{F}%
_{p}\setminus\left\{  0\right\}  =\left(  \mathbb{F}_{p}\right)  ^{\times}$).
Hence, $\lambda^{p-1}=1$. Now, $\lambda^{p}=\lambda\underbrace{\lambda^{p-1}%
}_{=1}=\lambda$. This proves (\ref{2.sol.a.lambdap}). Thus, Lemma
\ref{lem.lambdap} is proven.
\end{proof}

\begin{lemma}
\label{lem.lambdap-n}Let $p$ be a prime. Any $\lambda\in\mathbb{F}_{p}$ and
any $n\in\mathbb{N}$ satisfy%
\begin{equation}
\lambda^{p^{n}}=\lambda. \label{2.sol.a.lambdap-n}%
\end{equation}

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.lambdap-n}.]Lemma \ref{lem.lambdap-n} follows by
induction on $n$, using (\ref{2.sol.a.lambdap}) and the fact that
$\lambda^{p^{n}}=\left(  \lambda^{p^{n-1}}\right)  ^{p}$ for every $\lambda
\in\mathbb{F}_{p}$ and every positive integer $n$.
\end{proof}

\begin{lemma}
\label{lem.f(u+v)}Let $p$ be a prime. Let $L$ be a commutative $\mathbb{F}%
_{p}$-algebra. Let $f\in L\left[  X\right]  $ be a $p$-polynomial. Then,%
\begin{equation}
f\left(  u+v\right)  =f\left(  u\right)  +f\left(  v\right)
\label{2.sol.f(u+v)}%
\end{equation}
for every $u\in L$ and $v\in L$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.f(u+v)}.]We know that $f\in L\left[  X\right]  $ is a
$p$-polynomial. Thus, $f$ has the form $f=\sum_{n=0}^{d}a_{n}X^{p^{n}}$ for
some $d\in\mathbb{N}$ and some $a_{0},a_{1},\ldots,a_{d}\in L$. Consider this
$d$ and these $a_{0},a_{1},\ldots,a_{d}$. Every $u\in L$ and $v\in L$ satisfy%
\begin{align*}
f\left(  u+v\right)   &  =\sum_{n=0}^{d}a_{n}\underbrace{\left(  u+v\right)
^{p^{n}}}_{\substack{=u^{p^{n}}+v^{p^{n}}\\\text{(by
(\ref{2.sol.a.idiot-binom-n}))}}}\ \ \ \ \ \ \ \ \ \ \left(  \text{since
}f=\sum_{n=0}^{d}a_{n}X^{p^{n}}\right) \\
&  =\sum_{n=0}^{d}a_{n}\left(  u^{p^{n}}+v^{p^{n}}\right)  =\underbrace{\sum
_{n=0}^{d}a_{n}u^{p^{n}}}_{=f\left(  u\right)  }+\underbrace{\sum_{n=0}%
^{d}a_{n}v^{p^{n}}}_{=f\left(  v\right)  }=f\left(  u\right)  +f\left(
v\right)  .
\end{align*}
This proves Lemma \ref{lem.f(u+v)}.
\end{proof}

\begin{lemma}
\label{lem.f(lu)}Let $p$ be a prime. Let $L$ be a commutative $\mathbb{F}_{p}%
$-algebra. Let $f\in L\left[  X\right]  $ be a $p$-polynomial. Then,%
\begin{equation}
f\left(  \lambda u\right)  =\lambda f\left(  u\right)  \label{2.sol.f(lu)}%
\end{equation}
for every $u\in L$ and $\lambda\in\mathbb{F}_{p}$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.f(lu)}.]We know that $f\in L\left[  X\right]  $ is a
$p$-polynomial. Thus, $f$ has the form $f=\sum_{n=0}^{d}a_{n}X^{p^{n}}$ for
some $d\in\mathbb{N}$ and some $a_{0},a_{1},\ldots,a_{d}\in L$. Consider this
$d$ and these $a_{0},a_{1},\ldots,a_{d}$. Every $u\in L$ and $\lambda
\in\mathbb{F}_{p}$ satisfy%
\begin{align*}
f\left(  \lambda u\right)   &  =\sum_{n=0}^{d}a_{n}\underbrace{\left(  \lambda
u\right)  ^{p^{n}}}_{=\lambda^{p^{n}}u^{p^{n}}}\ \ \ \ \ \ \ \ \ \ \left(
\text{since }f=\sum_{n=0}^{d}a_{n}X^{p^{n}}\right) \\
&  =\sum_{n=0}^{d}a_{n}\underbrace{\lambda^{p^{n}}}_{\substack{=\lambda
\\\text{(by (\ref{2.sol.a.lambdap-n}))}}}u^{p^{n}}=\sum_{n=0}^{d}a_{n}\lambda
u^{p^{n}}=\lambda\underbrace{\sum_{n=0}^{d}a_{n}u^{p^{n}}}%
_{\substack{=f\left(  u\right)  \\\text{(since }\sum_{n=0}^{d}a_{n}X^{p^{n}%
}=f\text{)}}}=\lambda f\left(  u\right)  .
\end{align*}
This proves Lemma \ref{lem.f(lu)}.
\end{proof}

\begin{definition}
Let $L$ be a commutative ring. For every polynomial $f\in L\left[  X\right]
$, we let $\mathcal{R}\left(  f\right)  $ be the set of all roots of $f$
(inside $L$).
\end{definition}

\begin{lemma}
\label{lem.R(f)-subsp}Let $p$ be a prime. Let $L$ be a commutative
$\mathbb{F}_{p}$-algebra. Let $f\in L\left[  X\right]  $ be a $p$-polynomial.
Then,%
\begin{equation}
\mathcal{R}\left(  f\right)  \text{ is a }\mathbb{F}_{p}\text{-vector subspace
of }L. \label{2.sol.R(f)-subsp}%
\end{equation}

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.R(f)-subsp}.]If $u\in L$ and $v\in L$ are such that
$f\left(  u\right)  =0$ and $f\left(  v\right)  =0$, then
\begin{align*}
f\left(  u+v\right)   &  =\underbrace{f\left(  u\right)  }_{=0}%
+\underbrace{f\left(  v\right)  }_{=0}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{2.sol.f(u+v)})}\right) \\
&  =0.
\end{align*}
In other words, if $u$ and $v$ are two roots of $f$, then $u+v$ is a root of
$f$. In other words, the set $\mathcal{R}\left(  f\right)  $ of all roots of
$f$ is closed under addition. Furthermore, (\ref{2.sol.f(lu)}) (applied to
$\lambda=0$ and $u=0$) yields $f\left(  0\right)  =0f\left(  0\right)  =0$.
Hence, $0$ is a root of $f$. In other words, $0\in\mathcal{R}\left(  f\right)
$.

Moreover, (\ref{2.sol.f(lu)}) (applied to $\lambda=-1$) shows that $f\left(
-u\right)  =-f\left(  u\right)  $ for every $u\in L$. Hence, every
$u\in\mathcal{R}\left(  f\right)  $ must satisfy $f\left(  -u\right)
=-\underbrace{f\left(  u\right)  }_{\substack{=0\\\text{(since }%
u\in\mathcal{R}\left(  f\right)  \text{)}}}=0$ and therefore $-u\in
\mathcal{R}\left(  f\right)  $. In other words, the set $\mathcal{R}\left(
f\right)  $ is closed under taking negatives.

Now, we know that the set $\mathcal{R}\left(  f\right)  $ contains $0$ (since
$0\in\mathcal{R}\left(  f\right)  $) and is closed under addition and taking
negatives. In other words, $\mathcal{R}\left(  f\right)  $ is an additive
subgroup of $L$.

Finally, if $u\in\mathcal{R}\left(  f\right)  $ and $\lambda\in\mathbb{F}_{p}%
$, then (\ref{2.sol.f(lu)}) yields $f\left(  \lambda u\right)  =\lambda
\underbrace{f\left(  u\right)  }_{\substack{=0\\\text{(since }u\in
\mathcal{R}\left(  f\right)  \text{)}}}=0$ and therefore $\lambda
u\in\mathcal{R}\left(  f\right)  $. Therefore, the set $\mathcal{R}\left(
f\right)  $ is an $\mathbb{F}_{p}$-vector subspace of $L$ (since we already
know that $\mathcal{R}\left(  f\right)  $ is an additive subgroup of $L$).
This proves Lemma \ref{lem.R(f)-subsp}.
\end{proof}

\begin{lemma}
\label{lem.deriv}Let $p$ be a prime. Let $L$ be a commutative $\mathbb{F}_{p}%
$-algebra. Let $f\in L\left[  X\right]  $ be a $p$-polynomial. Then,%
\begin{equation}
\text{the derivative }f^{\prime}\text{ of }f\text{ equals the coefficient of
}f\text{ before }X^{1}. \label{2.sol.deriv}%
\end{equation}

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.deriv}.]We know that $f\in L\left[  X\right]  $ is a
$p$-polynomial. Thus, $f$ has the form $f=\sum_{n=0}^{d}a_{n}X^{p^{n}}$ for
some $d\in\mathbb{N}$ and some $a_{0},a_{1},\ldots,a_{d}\in L$. Consider this
$d$ and these $a_{0},a_{1},\ldots,a_{d}$. From $f=\sum_{n=0}^{d}a_{n}X^{p^{n}%
}$, we obtain%
\[
f^{\prime}=\sum_{n=0}^{d}a_{n}p^{n}X^{p^{n}-1}=a_{0}\underbrace{p^{0}}%
_{=1}\underbrace{X^{p^{0}-1}}_{=X^{0}=1}+\sum_{n=1}^{d}a_{n}\underbrace{p^{n}%
}_{\substack{=0\text{ in }L\\\text{(since }p\mid p^{n}\text{)}}}X^{p^{n}%
-1}=a_{0}.
\]
But this is clearly the coefficient of $f$ before $X^{1}$. Thus, Lemma
\ref{lem.deriv} is proven.
\end{proof}

\begin{lemma}
\label{lem.f=0}Let $L$ be a field. If $f\in L\left[  X\right]  $ is a
polynomial which has more than $\deg f$ roots in $L$, then $f=0$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.f=0}.]This is a general (and well-known) fact about
univariate polynomials over a field: If the number of roots of such a
polynomial exceeds its degree, then the polynomial is $0$.
\end{proof}

\section{Proofs of Theorem \ref{thm.prod-is-p}}

We now come to the proofs of Theorem \ref{thm.prod-is-p}.

\subsection{First proof}

The following proof of Theorem \ref{thm.prod-is-p} was found by Meghal Gupta
in the PRIMES 2015 application contest:

\begin{proof}
[First proof of Theorem \ref{thm.prod-is-p}.]We WLOG assume that $V\neq0$
(since otherwise, Theorem \ref{thm.prod-is-p} is evident). Lemma
\ref{lem.Fp-subspace} \textbf{(a)} yields that the number $p$ is prime. Lemma
\ref{lem.Fp-subspace} \textbf{(b)} shows that the field $L$ is a field
extension of $\mathbb{F}_{p}$. Lemma \ref{lem.Fp-subspace} \textbf{(c)} says
that the subset $V$ is a finite-dimensional $\mathbb{F}_{p}$-vector subspace
of $L$.

Now, let $W$ be the polynomial $\prod\limits_{v\in V}\left(  X+v\right)  \in
L\left[  X\right]  $. We need to prove that $W$ is a $p$-polynomial.

Let $\left(  e_{1},e_{2},\ldots,e_{k}\right)  $ be a basis of the
$\mathbb{F}_{p}$-vector space $V$. Thus, $\dim V=k$, so that $\left\vert
V\right\vert =p^{k}$.

There exists a nonzero vector $\left(  a_{0},a_{1},\ldots,a_{k}\right)  \in
L^{k+1}$ satisfying%
\begin{equation}
\sum_{j=0}^{k}a_{j}e_{i}^{p^{k-j}}=0\ \ \ \ \ \ \ \ \ \ \text{for every }%
i\in\left\{  1,2,\ldots,k\right\}  . \label{2.sol.a.linsys}%
\end{equation}
(\textit{Proof:} Let us regard (\ref{2.sol.a.linsys}) as a system of $k$
homogeneous linear equations in the $k+1$ unknowns $a_{0},a_{1},\ldots,a_{k}$
over the field $L$. This system has at least one solution (namely, $\left(
0,0,\ldots,0\right)  $), and is underdetermined (since it has more unknowns
than it has equations). Hence, it has at least one nonzero solution (where
\textquotedblleft nonzero\textquotedblright\ means that at least one of
$a_{0},a_{1},\ldots,a_{k}$ is nonzero). This means that there exists a nonzero
vector $\left(  a_{0},a_{1},\ldots,a_{k}\right)  \in L^{k+1}$ satisfying
(\ref{2.sol.a.linsys}), qed.)

So let us fix some nonzero vector $\left(  a_{0},a_{1},\ldots,a_{k}\right)
\in L^{k+1}$ satisfying (\ref{2.sol.a.linsys}) (now that we know that such a
vector exists). Define a polynomial $\widetilde{W}\in L\left[  X\right]  $ by
$\widetilde{W}=\sum_{j=0}^{k}a_{j}X^{p^{k-j}}$. Then, (\ref{2.sol.a.linsys})
rewrites as follows:%
\[
\widetilde{W}\left(  e_{i}\right)  =0\ \ \ \ \ \ \ \ \ \ \text{for every }%
i\in\left\{  1,2,\ldots,k\right\}  .
\]
In other words,%
\begin{equation}
e_{i}\in\mathcal{R}\left(  \widetilde{W}\right)  \ \ \ \ \ \ \ \ \ \ \text{for
every }i\in\left\{  1,2,\ldots,k\right\}  \label{2.sol.a.linsys3}%
\end{equation}
(since $\mathcal{R}\left(  \widetilde{W}\right)  $ is the set of all roots of
$\widetilde{W}$).

The polynomial $\widetilde{W}$ is not identically $0$ (since $\left(
a_{0},a_{1},\ldots,a_{k}\right)  $ is a nonzero vector). Notice that
\textquotedblleft identically $0$\textquotedblright\ means \textquotedblleft
all coefficients are $0$\textquotedblright; this is not the same thing as
saying that $\widetilde{W}\left(  x\right)  =0$ for all $x\in L$. (Actually,
$\widetilde{W}\left(  x\right)  =0$ might hold for all $x\in L$ is small enough!)

Also, $\widetilde{W}$ is a $p$-polynomial (by its very definition). Hence,
(\ref{2.sol.R(f)-subsp}) (applied to $f=\widetilde{W}$) shows that
$\mathcal{R}\left(  \widetilde{W}\right)  $ is a $\mathbb{F}_{p}$-vector
subspace of $L$. Since this subspace $\mathcal{R}\left(  \widetilde{W}\right)
$ contains each vector in the basis $\left(  e_{1},e_{2},\ldots,e_{k}\right)
$ of $V$ (by (\ref{2.sol.a.linsys3})), we can thus conclude that
$\mathcal{R}\left(  \widetilde{W}\right)  $ contains $V$ as a subset. In other
words, every $w\in V$ is an element of $\mathcal{R}\left(  \widetilde{W}%
\right)  $, thus a root of $\widetilde{W}$. In other words, every $w\in V$
satisfies $\widetilde{W}\left(  w\right)  =0$.

On the other hand, $W=\prod\limits_{v\in V}\left(  X+v\right)  $. Hence, every
$w\in V$ satisfies $W\left(  w\right)  =0$\ \ \ \ \footnote{\textit{Proof.}
Let $w\in V$. Then, $-w\in V$ (since $V$ is an additive subgroup of $L$).
Hence, the product $\prod\limits_{v\in V}\left(  w+v\right)  $ contains the
factor $w+\left(  -w\right)  $ (this is its factor for $v=-w$), which is $0$.
Therefore, the whole product $\prod\limits_{v\in V}\left(  w+v\right)  $ must
be $0$. Now, evaluating both sides of the equality $W=\prod\limits_{v\in
V}\left(  X+v\right)  $ at $X=w$, we obtain $W\left(  w\right)  =\prod
\limits_{v\in V}\left(  w+v\right)  =0$. Qed.}.

So we conclude that every $w\in V$ satisfies both $\widetilde{W}\left(
w\right)  =0$ and $W\left(  w\right)  =0$. Hence, every $w\in V$ satisfies
\[
\left(  \widetilde{W}-a_{0}W\right)  \left(  w\right)
=\underbrace{\widetilde{W}\left(  w\right)  }_{=0}-a_{0}\underbrace{W\left(
w\right)  }_{=0}=0.
\]
In other words, every $w\in V$ is a root of $\widetilde{W}-a_{0}W$. Hence, the
polynomial $\widetilde{W}-a_{0}W$ has at least $p^{k}$ roots (since
$\left\vert V\right\vert =p^{k}$).

The polynomial $W$ is a product of $\left\vert V\right\vert =p^{k}$ terms of
the form $X+v$, and therefore is a monic polynomial of degree $p^{k}$. Hence,
both polynomials $\widetilde{W}$ and $a_{0}W$ have degree $\leq p^{k}$, and
moreover, their coefficients before $X^{p^{k}}$ are equal (namely, both are
$a_{0}$). Therefore, the difference $\widetilde{W}-a_{0}W$ is a polynomial of
degree $<p^{k}$ (since the equal coefficients before $X^{p^{k}}$ cancel out in
the subtraction). In other words, $\deg\left(  \widetilde{W}-a_{0}W\right)
<p^{k}$. But we have just proven that this difference $\widetilde{W}-a_{0}W$
has at least $p^{k}$ roots; thus, it has more than $\deg\left(  \widetilde{W}%
-a_{0}W\right)  $ roots (since $\deg\left(  \widetilde{W}-a_{0}W\right)
<p^{k}$). Hence, Lemma \ref{lem.f=0} (applied to $f=\widetilde{W}-a_{0}W$)
shows that $\widetilde{W}-a_{0}W=0$, so that $\widetilde{W}=a_{0}W$. Since
$\widetilde{W}$ is not identically $0$, this shows that $a_{0}\neq0$. Hence,
$\widetilde{W}=a_{0}W$ becomes $W=\dfrac{1}{a_{0}}\widetilde{W}$. But
$\widetilde{W}$ is a $p$-polynomial. Hence, $W$ is a $p$-polynomial (since
$W=\dfrac{1}{a_{0}}\widetilde{W}$). Hence, Theorem \ref{thm.prod-is-p} is proven.
\end{proof}

\subsection{Second proof}

The following proof of Theorem \ref{thm.prod-is-p} appears in \cite[(7.7)]%
{mac-schurvar}; it was also found by Jessica Lai in the PRIMES 2015
application contest:

\begin{proof}
[Second proof of Theorem \ref{thm.prod-is-p}.]We WLOG assume that $V\neq0$
(since otherwise, Theorem \ref{thm.prod-is-p} is evident). Lemma
\ref{lem.Fp-subspace} \textbf{(a)} yields that the number $p$ is prime. Lemma
\ref{lem.Fp-subspace} \textbf{(b)} shows that the field $L$ is a field
extension of $\mathbb{F}_{p}$. Lemma \ref{lem.Fp-subspace} \textbf{(c)} says
that the subset $V$ is a finite-dimensional $\mathbb{F}_{p}$-vector subspace
of $L$.

Now, let $W$ be the polynomial $\prod\limits_{v\in V}\left(  X+v\right)  \in
L\left[  X\right]  $. We need to prove that $W$ is a $p$-polynomial.

Let $\left(  e_{1},e_{2},\ldots,e_{k}\right)  $ be a basis of the
$\mathbb{F}_{p}$-vector space $V$. Thus, $\dim V=k$, so that $\left\vert
V\right\vert =p^{k}$. Also, $e_{1},e_{2},\ldots,e_{k}$ are $\mathbb{F}_{p}%
$-linearly independent.

For every $n\in\left\{  0,1,\ldots,k\right\}  $, we let $\mathfrak{m}_{n}$ be
the $n\times n$-matrix%
\[
\left(
\begin{array}
[c]{cccc}%
e_{1}^{p^{0}} & e_{1}^{p^{1}} & \cdots & e_{1}^{p^{n-1}}\\
e_{2}^{p^{0}} & e_{2}^{p^{1}} & \cdots & e_{2}^{p^{n-1}}\\
\vdots & \vdots & \ddots & \vdots\\
e_{n}^{p^{0}} & e_{n}^{p^{1}} & \cdots & e_{n}^{p^{n-1}}%
\end{array}
\right)  \in L^{n\times n},
\]
and we let $\mathfrak{M}_{n}$ be the $\left(  n+1\right)  \times\left(
n+1\right)  $-matrix%
\[
\left(
\begin{array}
[c]{ccccc}%
e_{1}^{p^{0}} & e_{1}^{p^{1}} & \cdots & e_{1}^{p^{n-1}} & e_{1}^{p^{n}}\\
e_{2}^{p^{0}} & e_{2}^{p^{1}} & \cdots & e_{2}^{p^{n-1}} & e_{2}^{p^{n}}\\
\vdots & \vdots & \ddots & \vdots & \vdots\\
e_{n}^{p^{0}} & e_{n}^{p^{1}} & \cdots & e_{n}^{p^{n-1}} & e_{n}^{p^{n}}\\
X^{p^{0}} & X^{p^{1}} & \cdots & X^{p^{n-1}} & X^{p^{n}}%
\end{array}
\right)  \in\left(  L\left[  X\right]  \right)  ^{\left(  n+1\right)
\times\left(  n+1\right)  }.
\]
These two matrices are related to each other by the following properties:

\begin{itemize}
\item The matrix $\mathfrak{m}_{n}$ consists of the first $n$ rows and the
first $n$ columns of $\mathfrak{M}_{n}$.

\item The matrix $\mathfrak{m}_{n+1}$ (for $n<k$) is obtained from
$\mathfrak{M}_{n}$ by substituting $e_{n+1}$ for $X$.
\end{itemize}

Now, we shall prove the following\footnote{Lemma \ref{lem.moore.1} is a
classical result; its part \textbf{(a)} is essentially \cite[Proposition 1.3.5
2)]{Goss98}.}:

\begin{lemma}
\label{lem.moore.1}Let $L$, $V$, $p$, $\left(  e_{1},e_{2},\ldots
,e_{k}\right)  $, $\mathfrak{m}_{n}$ and $\mathfrak{M}_{n}$ be as above.

Let $n\in\left\{  0,1,\ldots,k\right\}  $. Let $V_{n}$ be the $\mathbb{F}_{p}%
$-vector subspace of $V$ spanned by $e_{1},e_{2},\ldots,e_{n}$. (In
particular, $V_{0}$ is spanned by nothing, and thus equals $0$. On the other
hand, $V_{k}=V$.)

\textbf{(a)} We have%
\[
\det\left(  \mathfrak{M}_{n}\right)  =\det\left(  \mathfrak{m}_{n}\right)
\cdot\prod_{v\in V_{n}}\left(  X+v\right)  .
\]


\textbf{(b)} The polynomial $\det\left(  \mathfrak{M}_{n}\right)  \in L\left[
X\right]  $ is a $p$-polynomial of degree $\leq p^{n}$, and its coefficient
before $X^{p^{n}}$ is $\det\left(  \mathfrak{m}_{n}\right)  $.
\end{lemma}

The determinants $\det\left(  \mathfrak{m}_{n}\right)  $ are known as the
\textit{Moore determinants}, and we will compute them soon enough. First, let
us prove the above lemma:

\begin{proof}
[Proof of Lemma \ref{lem.moore.1}.]\textbf{(b)} In the matrix $\mathfrak{M}%
_{n}$, the indeterminate $X$ appears only in the last row. If we expand
$\det\left(  \mathfrak{M}_{n}\right)  $ with respect to the last row (Laplace
expansion), then we obtain%
\begin{equation}
\det\left(  \mathfrak{M}_{n}\right)  =\sum_{j=0}^{n}X^{p^{j}}a_{j},
\label{pf.lem.moore.1}%
\end{equation}
where $a_{j}$ is the appropriate cofactor of $\mathfrak{M}_{n}$ (namely,
$\left(  -1\right)  ^{n+j}$ times the determinant of the matrix obtained from
$\mathfrak{M}_{n}$ by removing the $\left(  n+1\right)  $-th row and the
$\left(  j+1\right)  $-th column). All of these cofactors $a_{0},a_{1}%
,\ldots,a_{n}$ belong to $L$ (since they are determinants of matrices whose
entries all lie in $L$; here we are using the fact that the indeterminate $X$
appears only in the last row of $\mathfrak{M}_{n}$). Thus,
(\ref{pf.lem.moore.1}) shows that $\det\left(  \mathfrak{M}_{n}\right)  $ is a
$p$-polynomial of degree $\leq p^{n}$. It also shows that its coefficient
before $X^{p^{n}}$ is $a_{n}=\left(  -1\right)  ^{n+n}\det\left(
\mathfrak{m}_{n}\right)  $ (because the matrix obtained from $\mathfrak{M}%
_{n}$ by removing the $\left(  n+1\right)  $-th row and the $\left(
n+1\right)  $-th column is $\mathfrak{m}_{n}$). Since $\left(  -1\right)
^{n+n}=1$, this simplifies to $\det\left(  \mathfrak{m}_{n}\right)  $. This
concludes the proof of Lemma \ref{lem.moore.1} \textbf{(b)}.

\textbf{(a)} Let $f$ denote the polynomial $\det\left(  \mathfrak{M}%
_{n}\right)  \in L\left[  X\right]  $. Lemma \ref{lem.moore.1} \textbf{(b)}
shows that $f$ is a $p$-polynomial of degree $\leq p^{n}$, and its coefficient
before $X^{p^{n}}$ is $\det\left(  \mathfrak{m}_{n}\right)  $. Thus,
(\ref{2.sol.R(f)-subsp}) shows that $\mathcal{R}\left(  f\right)  $ is an
$\mathbb{F}_{p}$-vector subspace of $L$.

Let $i\in\left\{  1,2,\ldots,n\right\}  $. We have%
\[
f=\det\left(  \mathfrak{M}_{n}\right)  =\det\left(
\begin{array}
[c]{ccccc}%
e_{1}^{p^{0}} & e_{1}^{p^{1}} & \cdots & e_{1}^{p^{n-1}} & e_{1}^{p^{n}}\\
e_{2}^{p^{0}} & e_{2}^{p^{1}} & \cdots & e_{2}^{p^{n-1}} & e_{2}^{p^{n}}\\
\vdots & \vdots & \ddots & \vdots & \vdots\\
e_{n}^{p^{0}} & e_{n}^{p^{1}} & \cdots & e_{n}^{p^{n-1}} & e_{n}^{p^{n}}\\
X^{p^{0}} & X^{p^{1}} & \cdots & X^{p^{n-1}} & X^{p^{n}}%
\end{array}
\right)  .
\]
Substituting $e_{i}$ for $X$ in this equality, we obtain%
\[
f\left(  e_{i}\right)  =\det\underbrace{\left(
\begin{array}
[c]{ccccc}%
e_{1}^{p^{0}} & e_{1}^{p^{1}} & \cdots & e_{1}^{p^{n-1}} & e_{1}^{p^{n}}\\
e_{2}^{p^{0}} & e_{2}^{p^{1}} & \cdots & e_{2}^{p^{n-1}} & e_{2}^{p^{n}}\\
\vdots & \vdots & \ddots & \vdots & \vdots\\
e_{n}^{p^{0}} & e_{n}^{p^{1}} & \cdots & e_{n}^{p^{n-1}} & e_{n}^{p^{n}}\\
e_{i}^{p^{0}} & e_{i}^{p^{1}} & \cdots & e_{i}^{p^{n-1}} & e_{i}^{p^{n}}%
\end{array}
\right)  }_{\substack{\text{This matrix has two equal rows}\\\text{(the last
row and the }i\text{-th row)}}}=0.
\]
In other words, $e_{i}\in\mathcal{R}\left(  f\right)  $ (recall that
$\mathcal{R}\left(  f\right)  $ denotes the set of all roots of $f$).

Now, let us forget that we fixed $i$. We thus have shown that $e_{i}%
\in\mathcal{R}\left(  f\right)  $ for every $i\in\left\{  1,2,\ldots
,n\right\}  $. Since $\mathcal{R}\left(  f\right)  $ is an $\mathbb{F}_{p}%
$-vector subspace of $L$, this yields that $\mathcal{R}\left(  f\right)  $
contains the $\mathbb{F}_{p}$-vector subspace of $V$ spanned by $e_{1}%
,e_{2},\ldots,e_{n}$ as a subset. In other words, $\mathcal{R}\left(
f\right)  \supseteq V_{n}$ (since the $\mathbb{F}_{p}$-vector subspace of $V$
spanned by $e_{1},e_{2},\ldots,e_{n}$ is $V_{n}$).

But the vectors $e_{1},e_{2},\ldots,e_{k}$ are linearly independent. Hence, so
are the vectors $e_{1},e_{2},\ldots,e_{n}$. Thus, the $\mathbb{F}_{p}$-vector
subspace $V_{n}$ spanned by these latter vectors has dimension $n$. In other
words, $\dim\left(  V_{n}\right)  =n$, so that $\left\vert V_{n}\right\vert
=p^{n}$.

Let $g$ denote the polynomial $f-\det\left(  \mathfrak{m}_{n}\right)
\cdot\prod_{v\in V_{n}}\left(  X+v\right)  \in L\left[  X\right]  $. Then,
$\deg g<p^{n}$\ \ \ \ \footnote{\textit{Proof.} As we know, the polynomial $f$
has degree $\leq p^{n}$, and its coefficient before $X^{p^{n}}$ is
$\det\left(  \mathfrak{m}_{n}\right)  $. On the other hand, $\prod_{v\in
V_{n}}\left(  X+v\right)  $ is a monic polynomial of degree $p^{n}$ (since it
is the product of $\left\vert V_{n}\right\vert =p^{n}$ terms of the form
$X+v$), and therefore $\det\left(  \mathfrak{m}_{n}\right)  \cdot\prod_{v\in
V_{n}}\left(  X+v\right)  $ is a polynomial of degree $\leq p^{n}$ whose
coefficient before $X^{p^{n}}$ is $\det\left(  \mathfrak{m}_{n}\right)  $.
\par
So both polynomials $f$ and $\det\left(  \mathfrak{m}_{n}\right)  \cdot
\prod_{v\in V_{n}}\left(  X+v\right)  $ have degree $\leq p^{n}$, and their
coefficients before $X^{p^{n}}$ are $\det\left(  \mathfrak{m}_{n}\right)  $.
Thus, their difference $f-\det\left(  \mathfrak{m}_{n}\right)  \cdot
\prod_{v\in V_{n}}\left(  X+v\right)  $ has degree $<p^{n}$ (since their equal
coefficients before $X^{p^{n}}$ cancel out when they are subtracted). In other
words, $g$ has degree $<p^{n}$ (since $g=f-\det\left(  \mathfrak{m}%
_{n}\right)  \cdot\prod_{v\in V_{n}}\left(  X+v\right)  $), qed.}.

Now, let $w\in V_{n}$. Then, $w\in\mathcal{R}\left(  f\right)  $ (since
$\mathcal{R}\left(  f\right)  \supseteq V_{n}$) and thus $f\left(  w\right)
=0$. On the other hand, $-w\in V_{n}$ (since $w\in V_{n}$ and since $V_{n}$ is
a vector space). Hence, the product $\prod_{v\in V_{n}}\left(  w+v\right)  $
contains the factor $w+\left(  -w\right)  =0$, and therefore vanishes. Hence,
$\underbrace{f\left(  w\right)  }_{=0}-\det\left(  \mathfrak{m}_{n}\right)
\cdot\underbrace{\prod_{v\in V_{n}}\left(  w+v\right)  }_{=0}=0$. In other
words, $w$ is a root of the polynomial $f-\det\left(  \mathfrak{m}_{n}\right)
\cdot\prod_{v\in V_{n}}\left(  X+v\right)  =g$.

Now, let us forget that we fixed $w$. We thus have proven that every $w\in
V_{n}$ is a root of the polynomial $g$. Thus, this polynomial $g$ has at least
$\left\vert V_{n}\right\vert =p^{n}$ roots. Hence, this polynomial $g$ has
more than $\deg g$ roots (since $\deg g<p^{n}$). Applying Lemma \ref{lem.f=0}
to $g$ instead of $f$, we thus conclude that $g=0$. Since $g=f-\det\left(
\mathfrak{m}_{n}\right)  \cdot\prod_{v\in V_{n}}\left(  X+v\right)  $, this
rewrites as $f-\det\left(  \mathfrak{m}_{n}\right)  \cdot\prod_{v\in V_{n}%
}\left(  X+v\right)  =0$. In other words, $f=\det\left(  \mathfrak{m}%
_{n}\right)  \cdot\prod_{v\in V_{n}}\left(  X+v\right)  $. Since
$f=\det\left(  \mathfrak{M}_{n}\right)  $, this means that Lemma
\ref{lem.moore.1} \textbf{(a)} is proven.
\end{proof}

Now we can compute the Moore determinants\footnote{Corollary \ref{cor.moore.2}
is \cite[Corollary 1.3.7]{Goss98}.}:

\begin{corollary}
\label{cor.moore.2}Let $n\in\left\{  0,1,\ldots,k\right\}  $. Let $L$, $V$,
$p$, $\left(  e_{1},e_{2},\ldots,e_{k}\right)  $, $\mathfrak{m}_{n}$ and
$\mathfrak{M}_{n}$ be as above. Let $V_{n}$ be as in Lemma \ref{lem.moore.1}.

\textbf{(a)} We have%
\begin{equation}
\det\left(  \mathfrak{m}_{n}\right)  =\prod_{i=1}^{n}\prod_{v\in V_{i-1}%
}\left(  e_{i}+v\right)  . \label{eq.cor.moore.2.a.eq}%
\end{equation}


\textbf{(b)} We have $\det\left(  \mathfrak{m}_{n}\right)  \neq0$.
\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.moore.2}.]\textbf{(a)} Corollary
\ref{cor.moore.2} \textbf{(a)} is proven by induction over $n$.

The \textit{induction base} (i.e., the case $n=0$) is easy: If $n=0$, then the
left hand side of (\ref{eq.cor.moore.2.a.eq}) is $1$ (because $\mathfrak{m}%
_{0}$ is a $0\times0$-matrix, and the determinant of a $0\times0$-matrix is
defined to be $1$), whereas the right hand side is also $1$ (because it is an
empty product, and empty products too are defined to be $1$).

\textit{Induction step:} Fix $n\in\left\{  0,1,\ldots,k-1\right\}  $. Assume
that
\begin{equation}
\det\left(  \mathfrak{m}_{n}\right)  =\prod_{i=1}^{n}\prod_{v\in V_{i-1}%
}\left(  e_{i}+v\right)  . \label{pf.cor.moore.2.a.hyp}%
\end{equation}
We now must prove that%
\begin{equation}
\det\left(  \mathfrak{m}_{n+1}\right)  =\prod_{i=1}^{n+1}\prod_{v\in V_{i-1}%
}\left(  e_{i}+v\right)  . \label{pf.cor.moore.2.a.goal}%
\end{equation}


Lemma \ref{lem.moore.1} \textbf{(a)} shows that%
\begin{equation}
\det\left(  \mathfrak{M}_{n}\right)  =\det\left(  \mathfrak{m}_{n}\right)
\cdot\prod_{v\in V_{n}}\left(  X+v\right)
\label{pf.cor.moore.2.a.lem-moore-1-a}%
\end{equation}


Recall that the matrix $\mathfrak{m}_{n+1}$ is obtained from $\mathfrak{M}%
_{n}$ by substituting $e_{n+1}$ for $X$. Hence, $\det\left(  \mathfrak{m}%
_{n+1}\right)  $ is obtained from $\det\left(  \mathfrak{M}_{n}\right)  $ by
substituting $e_{n+1}$ for $X$. Thus, substituting $e_{n+1}$ for $X$ in the
equality (\ref{pf.cor.moore.2.a.lem-moore-1-a}) yields%
\begin{align*}
\det\left(  \mathfrak{m}_{n+1}\right)   &  =\underbrace{\det\left(
\mathfrak{m}_{n}\right)  }_{\substack{=\prod_{i=1}^{n}\prod_{v\in V_{i-1}%
}\left(  e_{i}+v\right)  \\\text{(by (\ref{pf.cor.moore.2.a.hyp}))}}%
}\cdot\prod_{v\in V_{n}}\left(  e_{n+1}+v\right) \\
&  =\left(  \prod_{i=1}^{n}\prod_{v\in V_{i-1}}\left(  e_{i}+v\right)
\right)  \cdot\prod_{v\in V_{n}}\left(  e_{n+1}+v\right)  =\prod_{i=1}%
^{n+1}\prod_{v\in V_{i-1}}\left(  e_{i}+v\right)  .
\end{align*}
This proves (\ref{pf.cor.moore.2.a.goal}), and thus completes the induction
step. Corollary \ref{cor.moore.2} \textbf{(a)} is thus proven.

\textbf{(b)} We need to prove that $\det\left(  \mathfrak{m}_{n}\right)
\neq0$. According to (\ref{eq.cor.moore.2.a.eq}), this boils down to showing
that $e_{i}+v\neq0$ for every $i\in\left\{  1,2,\ldots,n\right\}  $ and every
$v\in V_{i-1}$. So let us fix an $i\in\left\{  1,2,\ldots,n\right\}  $ and an
$v\in V_{i-1}$. We need to show that $e_{i}+v\neq0$.

Assume the contrary. Thus, $e_{i}+v=0$. But $V_{i-1}$ (by definition) is the
$\mathbb{F}_{p}$-vector subspace of $V$ spanned by $e_{1},e_{2},\ldots
,e_{i-1}$. Since $v\in V_{i-1}$, we thus can write $v$ as an $\mathbb{F}_{p}%
$-linear combination of $e_{1},e_{2},\ldots,e_{i-1}$. In other words,
$v=a_{1}e_{1}+a_{2}e_{2}+\cdots+a_{i-1}e_{i-1}$ for some $a_{1},a_{2}%
,\ldots,a_{i-1}\in\mathbb{F}_{p}$. Consider these $a_{1},a_{2},\ldots,a_{i-1}%
$. Then, $e_{i}+v=0$ becomes $e_{i}+a_{1}e_{1}+a_{2}e_{2}+\cdots
+a_{i-1}e_{i-1}=0$. But this contradicts the fact that $e_{1},e_{2}%
,\ldots,e_{k}$ are $\mathbb{F}_{p}$-linearly independent. This contradiction
proves that our assumption was wrong. Hence, $e_{i}+v\neq0$ is proven. This
completes the proof of Corollary \ref{cor.moore.2} \textbf{(b)}.
\end{proof}

Now, Lemma \ref{lem.moore.1} \textbf{(b)} (applied to $n=k$) yields that the
polynomial $\det\left(  \mathfrak{M}_{k}\right)  \in L\left[  X\right]  $ is a
$p$-polynomial of degree $\leq p^{k}$, and its coefficient before $X^{p^{k}}$
is $\det\left(  \mathfrak{m}_{k}\right)  $.

But Lemma \ref{lem.moore.1} \textbf{(a)} (applied to $n=k$) yields%
\[
\det\left(  \mathfrak{M}_{k}\right)  =\det\left(  \mathfrak{m}_{k}\right)
\cdot\prod_{v\in V_{k}}\left(  X+v\right)  =\det\left(  \mathfrak{m}%
_{k}\right)  \cdot\prod_{v\in V}\left(  X+v\right)
\]
(since $V_{k}=V$). Since $\det\left(  \mathfrak{m}_{k}\right)  \neq0$ (by
Corollary \ref{cor.moore.2} \textbf{(b)}, applied to $n=k$), this yields%
\[
\prod_{v\in V}\left(  X+v\right)  =\dfrac{1}{\det\left(  \mathfrak{m}%
_{k}\right)  }\cdot\det\left(  \mathfrak{M}_{k}\right)  .
\]
Hence, $\prod_{v\in V}\left(  X+v\right)  $ is a $p$-polynomial (since
$\det\left(  \mathfrak{M}_{k}\right)  $ is a $p$-polynomial, while $\dfrac
{1}{\det\left(  \mathfrak{m}_{k}\right)  }$ is just an element of $L$). This
proves Theorem \ref{thm.prod-is-p} again.
\end{proof}

\subsection{Third proof}

We shall soon give a third proof of Theorem \ref{thm.prod-is-p}. This proof is
more complicated than the preceding ones, but it is (from certain viewpoints)
the most natural, and also possibly the oldest. It appears in \cite[proof of
Theorem 7]{Ore33} and also (implicitly) in \cite{mac-schurvar}. In the PRIMES
2015 application contest, it was also found by Mehtaab Sawhney.

Before we come to this proof, let us prove a few more elementary facts:

\begin{lemma}
\label{lem.idiot-binoms}Let $p$ be a prime. Let $L$ be a commutative
$\mathbb{F}_{p}$-algebra. Any finitely many elements $u_{1},u_{2},\ldots
,u_{k}$ of $L$ satisfy%
\begin{equation}
\left(  u_{1}+u_{2}+\cdots+u_{k}\right)  ^{p}=u_{1}^{p}+u_{2}^{p}+\cdots
+u_{k}^{p}. \label{2.sol.a.idiot-binoms}%
\end{equation}

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.idiot-binoms}.]This follows from
(\ref{2.sol.a.idiot-binom}) by induction over $k$.
\end{proof}

\begin{lemma}
\label{lem.gp}Let $p$ be a prime. Let $L$ be a commutative $\mathbb{F}_{p}%
$-algebra. Let $g\in L\left[  X\right]  $ be a $p$-polynomial. Then, $g^{p}$
is a $p$-polynomial as well.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.gp}.]We know that $g\in L\left[  X\right]  $ is a
$p$-polynomial. Thus, $g$ has the form $g=\sum_{n=0}^{d}a_{n}X^{p^{n}}$ for
some $d\in\mathbb{N}$ and some $a_{0},a_{1},\ldots,a_{d}\in L$. Consider this
$d$ and these $a_{0},a_{1},\ldots,a_{d}$.

We know that $L$ is a commutative $\mathbb{F}_{p}$-algebra. Thus, $L\left[
X\right]  $ also is a commutative $\mathbb{F}_{p}$-algebra. Now, any finitely
many elements $u_{1},u_{2},\ldots,u_{k}$ of $L\left[  X\right]  $ satisfy%
\begin{equation}
\left(  u_{1}+u_{2}+\cdots+u_{k}\right)  ^{p}=u_{1}^{p}+u_{2}^{p}+\cdots
+u_{k}^{p}. \label{pf.lem.gp.idiot-binoms}%
\end{equation}
(Indeed, this follows from Lemma \ref{lem.idiot-binoms}, applied to $L\left[
X\right]  $ instead of $L$.)

From $g=\sum_{n=0}^{d}a_{n}X^{p^{n}}=a_{0}X^{p^{0}}+a_{1}X^{p^{1}}%
+\cdots+a_{d}X^{p^{d}}$, we obtain%
\begin{align*}
g^{p}  &  =\left(  a_{0}X^{p^{0}}+a_{1}X^{p^{1}}+\cdots+a_{d}X^{p^{d}}\right)
^{p}=\left(  a_{0}X^{p^{0}}\right)  ^{p}+\left(  a_{1}X^{p^{1}}\right)
^{p}+\cdots+\left(  a_{d}X^{p^{d}}\right)  ^{p}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{pf.lem.gp.idiot-binoms}),
applied to }k=d+1\text{ and }u_{i}=a_{i-1}X^{p^{i-1}}\right) \\
&  =a_{0}^{p}\underbrace{X^{p^{0}p}}_{=X^{p^{1}}}+a_{1}^{p}%
\underbrace{X^{p^{1}p}}_{=X^{p^{2}}}+\cdots+a_{d}^{p}\underbrace{X^{p^{d}p}%
}_{=X^{p^{d+1}}}\\
&  =a_{0}^{p}X^{p^{1}}+a_{1}^{p}X^{p^{2}}+\cdots+a_{d}^{p}X^{p^{d+1}}.
\end{align*}
This is clearly a $p$-polynomial. Thus, Lemma \ref{lem.gp} is proven.
\end{proof}

\begin{lemma}
\label{lem.prod1}Let $p$ be a prime. We have%
\begin{equation}
\prod_{\lambda\in\mathbb{F}_{p}}\left(  X-\lambda\right)  =X^{p}-X
\label{2.sol.a.prod1}%
\end{equation}
in the polynomial ring $\mathbb{F}_{p}\left[  X\right]  $.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.prod1}.]This is a well-known identity, and can be
proven, e.g., by comparing the roots and the leading terms of both sides. For
the sake of completeness, let us give its proof in more details:

Let $G$ be the polynomial $\prod_{\lambda\in\mathbb{F}_{p}}\left(
X-\lambda\right)  -\left(  X^{p}-X\right)  \in\mathbb{F}_{p}\left[  X\right]
$.

Both polynomials $\prod_{\lambda\in\mathbb{F}_{p}}\left(  X-\lambda\right)  $
and $X^{p}-X$ in the ring $\mathbb{F}_{p}\left[  X\right]  $ are monic
polynomials of degree $p$ (in fact, $\prod_{\lambda\in\mathbb{F}_{p}}\left(
X-\lambda\right)  $ is a product of $\left\vert \mathbb{F}_{p}\right\vert =p$
linear polynomials, and thus has degree $p$; it is furthermore monic because
those linear polynomials all are monic). Hence, their difference
$\prod_{\lambda\in\mathbb{F}_{p}}\left(  X-\lambda\right)  -\left(
X^{p}-X\right)  $ is a polynomial of degree $<p$ (because the coefficients of
$X^{p}$ in these two polynomials cancel out when we subtract them). In other
words, $G$ is a polynomial of degree $<p$ (since $G=\prod_{\lambda
\in\mathbb{F}_{p}}\left(  X-\lambda\right)  -\left(  X^{p}-X\right)  $). Thus,
$\deg G<p$.

But every $\mu\in\mathbb{F}_{p}$ satisfies%
\begin{align*}
G\left(  \mu\right)   &  =\underbrace{\prod_{\lambda\in\mathbb{F}_{p}}\left(
\mu-\lambda\right)  }_{\substack{\text{This product has a zero factor}%
\\\text{(indeed, its factor for }\lambda=\mu\text{ is }\mu-\mu=0\text{),}%
\\\text{and thus equals }0}}-\left(  \underbrace{\mu^{p}}_{\substack{=\mu
\\\text{(by (\ref{2.sol.a.lambdap}), applied}\\\text{to }\lambda=\mu\text{)}%
}}-\mu\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }G=\prod_{\lambda\in\mathbb{F}_{p}%
}\left(  X-\lambda\right)  -\left(  X^{p}-X\right)  \right) \\
&  =0-\left(  \mu-\mu\right)  =0.
\end{align*}
In other words, each $\mu\in\mathbb{F}_{p}$ is a root of the polynomial $G$.
Thus, the polynomial $G$ has at least $\left\vert \mathbb{F}_{p}\right\vert
=p$ roots. Consequently, the polynomial $G$ has more than $\deg G$ roots
(since $\deg G<p$). But if a polynomial $Q$ over a field has more than $\deg
Q$ roots, then $Q$ must be $0$. Applying this to $Q=G$, we conclude that
$G=0$. Hence, $\prod_{\lambda\in\mathbb{F}_{p}}\left(  X-\lambda\right)
-\left(  X^{p}-X\right)  =G=0$, so that $\prod_{\lambda\in\mathbb{F}_{p}%
}\left(  X-\lambda\right)  =X^{p}-X$. This proves Lemma \ref{lem.prod1}.
\end{proof}

\begin{lemma}
\label{lem.prod2}Let $p$ be a prime. We have%
\begin{equation}
\prod_{\lambda\in\mathbb{F}_{p}}\left(  X+\lambda Y\right)  =X^{p}-XY^{p-1}
\label{2.sol.a.prod2}%
\end{equation}
in the polynomial ring $\mathbb{F}_{p}\left[  X,Y\right]  $.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.prod2}.]Consider the ring $\mathbb{F}_{p}\left[
X,Y\right]  $ as a subring of the ring $\mathbb{F}_{p}\left(  X,Y\right)  $ of
rational functions in $X$ and $Y$. We can substitute $X/Y$ for $X$ in
(\ref{2.sol.a.prod1}); as a result, we obtain $\prod_{\lambda\in\mathbb{F}%
_{p}}\left(  X/Y-\lambda\right)  =\left(  X/Y\right)  ^{p}-X/Y$. Multiplying
both sides of this equality by $Y^{p}$, we obtain%
\[
Y^{p}\prod_{\lambda\in\mathbb{F}_{p}}\left(  X/Y-\lambda\right)  =Y^{p}\left(
\left(  X/Y\right)  ^{p}-X/Y\right)  =X^{p}-XY^{p-1}.
\]
Thus,%
\begin{align*}
X^{p}-XY^{p-1}  &  =Y^{p}\prod_{\lambda\in\mathbb{F}_{p}}\left(
X/Y-\lambda\right)  =\prod_{\lambda\in\mathbb{F}_{p}}\underbrace{\left(
Y\left(  X/Y-\lambda\right)  \right)  }_{=X-\lambda Y}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since the product has }\left\vert
\mathbb{F}_{p}\right\vert =p\text{ terms}\right) \\
&  =\prod_{\lambda\in\mathbb{F}_{p}}\left(  X-\lambda Y\right)  =\prod
_{\lambda\in\mathbb{F}_{p}}\left(  X+\lambda Y\right)
\end{align*}
(here, we have substituted $\lambda$ for $-\lambda$ in the product, since the
map $\mathbb{F}_{p}\rightarrow\mathbb{F}_{p},\ \lambda\mapsto-\lambda$ is a
bijection). This proves Lemma \ref{lem.prod2}.
\end{proof}

\begin{lemma}
\label{lem.f(u+v)-X}Let $p$ be a prime. Let $L$ be a commutative
$\mathbb{F}_{p}$-algebra. Let $f\in L\left[  X\right]  $ be a $p$-polynomial.
Then,%
\begin{equation}
f\left(  u+v\right)  =f\left(  u\right)  +f\left(  v\right)
\label{2.sol.a.f(u+v)}%
\end{equation}
for every $u\in L\left[  X\right]  $ and $v\in L\left[  X\right]  $.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.f(u+v)-X}.]The proof of Lemma \ref{lem.f(u+v)-X} is
analogous to the proof of Lemma \ref{lem.f(u+v)} (except that $u$ and $v$ now
belong to $L\left[  X\right]  $ instead of $L$).
\end{proof}

\begin{lemma}
\label{lem.f(lu)-X}Let $p$ be a prime. Let $L$ be a commutative $\mathbb{F}%
_{p}$-algebra. Let $f\in L\left[  X\right]  $ be a $p$-polynomial. Then,%
\begin{equation}
f\left(  \lambda u\right)  =\lambda f\left(  u\right)  \label{2.sol.a.f(lu)}%
\end{equation}
for every $u\in L\left[  X\right]  $ and $\lambda\in\mathbb{F}_{p}$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.f(lu)-X}.]The proof of Lemma \ref{lem.f(lu)-X} is
analogous to the proof of Lemma \ref{lem.f(lu)} (except that $u$ now belongs
to $L\left[  X\right]  $ instead of $L$).
\end{proof}

We are now ready to prove Theorem \ref{thm.prod-is-p} again:

\begin{proof}
[Third proof of Theorem \ref{thm.prod-is-p}.]We WLOG assume that $V\neq0$
(since otherwise, Theorem \ref{thm.prod-is-p} is evident). Lemma
\ref{lem.Fp-subspace} \textbf{(a)} yields that the number $p$ is prime. Lemma
\ref{lem.Fp-subspace} \textbf{(b)} shows that the field $L$ is a field
extension of $\mathbb{F}_{p}$. Lemma \ref{lem.Fp-subspace} \textbf{(c)} says
that the subset $V$ is a finite-dimensional $\mathbb{F}_{p}$-vector subspace
of $L$.

Now, we shall prove Theorem \ref{thm.prod-is-p} by induction over $\dim V$.

The \textit{induction base} (that is, the case when $\dim V=0$) is easy and
left to the reader.

\textit{Induction step:} Let $N\in\mathbb{N}$. Assume (as the induction
hypothesis) that Theorem \ref{thm.prod-is-p} is proven in the case when $\dim
V=N$. We must then show that Theorem \ref{thm.prod-is-p} holds in the case
when $\dim V=N+1$.

So let us assume that $\dim V=N+1$. Thus, $\dim V=N+1>0$; hence, $V$ has a
nonzero element $e$. Fix such an $e$. Then, the $\mathbb{F}_{p}$-vector
subspace $\mathbb{F}_{p}e$ of $V$ has dimension $1$. By a basic fact in linear
algebra, there exists a complement to the subspace $\mathbb{F}_{p}e$ of the
vector space $V$ -- that is, there exists an $\mathbb{F}_{p}$-vector subspace
$W$ of $V$ such that $V=W\oplus\mathbb{F}_{p}e$ (internal direct sum). Fix
such a $W$.

From $V=W\oplus\mathbb{F}_{p}e$, we obtain $\dim V=\dim W+\underbrace{\dim
\left(  \mathbb{F}_{p}e\right)  }_{=1}=\dim W+1$. Thus, $\dim W+1=\dim V=N+1$,
so that $\dim W=N$. Hence (by our induction hypothesis) Theorem
\ref{thm.prod-is-p} can be applied to $W$ instead of $V$. As a result, we
conclude that $\prod\limits_{v\in W}\left(  X+v\right)  \in L\left[  X\right]
$ is a $p$-polynomial. Let us denote this $p$-polynomial by $g$. Thus,%
\begin{equation}
\prod\limits_{v\in W}\left(  X+v\right)  =g. \label{2.sol.a.sol3.1}%
\end{equation}
From Lemma \ref{lem.gp}, we conclude that $g^{p}$ is a $p$-polynomial as well.

Now, $V=W\oplus\mathbb{F}_{p}e$. Thus, every $v\in V$ can be uniquely written
in the form $w+\lambda e$ for some $\left(  w,\lambda\right)  \in
W\times\mathbb{F}_{p}$. Thus, we can substitute $w+\lambda e$ for $v$ in the
product $\prod\limits_{v\in V}\left(  X+v\right)  $. We hence obtain%
\begin{align*}
\prod\limits_{v\in V}\left(  X+v\right)   &  =\underbrace{\prod
\limits_{\left(  w,\lambda\right)  \in W\times\mathbb{F}_{p}}}_{=\prod
_{\lambda\in\mathbb{F}_{p}}\prod_{w\in W}}\underbrace{\left(  X+w+\lambda
e\right)  }_{=X+\lambda e+w}=\prod_{\lambda\in\mathbb{F}_{p}}\prod_{w\in
W}\left(  X+\lambda e+w\right) \\
&  =\prod_{\lambda\in\mathbb{F}_{p}}\underbrace{\prod_{v\in W}\left(
X+\lambda e+v\right)  }_{\substack{=g\left(  X+\lambda e\right)  \\\text{(this
follows by substituting }X+\lambda e\\\text{for }X\text{ in
(\ref{2.sol.a.sol3.1}))}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have renamed the index }w\text{
as }v\right) \\
&  =\prod_{\lambda\in\mathbb{F}_{p}}\underbrace{g\left(  X+\lambda e\right)
}_{\substack{=g\left(  X\right)  +g\left(  \lambda e\right)  \\\text{(by
(\ref{2.sol.a.f(u+v)}), applied to }f=g\text{,}\\u=X\text{ and }v=\lambda
e\text{)}}}=\prod_{\lambda\in\mathbb{F}_{p}}\left(  \underbrace{g\left(
X\right)  }_{=g}+\underbrace{g\left(  \lambda e\right)  }_{\substack{=\lambda
g\left(  e\right)  \\\text{(by (\ref{2.sol.a.f(lu)}), applied to
}f=g\\\text{and }u=e\text{)}}}\right) \\
&  =\prod_{\lambda\in\mathbb{F}_{p}}\left(  g+\lambda g\left(  e\right)
\right)  =g^{p}-g\left(  g\left(  e\right)  \right)  ^{p-1}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{this follows by substituting }g\text{ and
}g\left(  e\right)  \text{ for }X\text{ and }Y\text{ in (\ref{2.sol.a.prod2}%
)}\right)  .
\end{align*}
But this is clearly a $p$-polynomial (since both $g^{p}$ and $g$ are
$p$-polynomials, while $\left(  g\left(  e\right)  \right)  ^{p-1}$ is just a
constant in $L$). Thus, we have proven that $\prod\limits_{v\in V}\left(
X+v\right)  $ is a $p$-polynomial. In other words, Theorem \ref{thm.prod-is-p}
holds in the case when $\dim V=N+1$. This completes the induction step, and
Theorem \ref{thm.prod-is-p} is proven once again.
\end{proof}

\section{Proofs of Theorem \ref{thm.sum-prod}}

\subsection{First proof}

\begin{proof}
[First proof of Theorem \ref{thm.sum-prod}.]We WLOG assume that $V\neq0$
(since otherwise, Theorem \ref{thm.sum-prod} is evident). Let
$p=\operatorname*{char}L$. Lemma \ref{lem.Fp-subspace} \textbf{(a)} yields
that the number $p$ is prime. Lemma \ref{lem.Fp-subspace} \textbf{(b)} shows
that the field $L$ is a field extension of $\mathbb{F}_{p}$. Lemma
\ref{lem.Fp-subspace} \textbf{(c)} says that the subset $V$ is a
finite-dimensional $\mathbb{F}_{p}$-vector subspace of $L$.

Define a polynomial $W\in L\left[  X\right]  $ by $W=\prod\limits_{v\in
V}\left(  X+v\right)  $. Then, Theorem \ref{thm.prod-is-p} yields that the
polynomial $W$ is a $p$-polynomial. Hence, its derivative equals its
coefficient before $X^{1}$ (by (\ref{2.sol.deriv}), applied to $f=W$). But
this coefficient is $\prod\limits_{v\in V\setminus0}v$. Thus, we know that the
derivative of $W$ equals $\prod\limits_{v\in V\setminus0}v$. Hence,
$W^{\prime}\left(  t\right)  =\prod\limits_{v\in V\setminus0}v$.

On the other hand, since $W=\prod\limits_{v\in V}\left(  X+v\right)  $, the
Leibniz formula yields%
\begin{align*}
W^{\prime}  &  =\sum\limits_{w\in V}\underbrace{\left(  X+w\right)  ^{\prime}%
}_{=1}\cdot\prod\limits_{\substack{v\in V;\\v\neq w}}\left(  X+v\right)
=\sum\limits_{w\in V}\prod\limits_{\substack{v\in V;\\v\neq w}}\left(
X+v\right)  =\sum\limits_{w\in V}\dfrac{\prod\limits_{v\in V}\left(
X+v\right)  }{X+w}\\
&  =\left(  \prod\limits_{v\in V}\left(  X+v\right)  \right)  \cdot\left(
\sum\limits_{w\in V}\dfrac{1}{X+w}\right)  .
\end{align*}
Applying this to $X=t$, we obtain%
\[
W^{\prime}\left(  t\right)  =\left(  \prod\limits_{v\in V}\left(  t+v\right)
\right)  \cdot\left(  \sum\limits_{w\in V}\dfrac{1}{t+w}\right)  ,
\]
so that%
\[
\sum\limits_{w\in V}\dfrac{1}{t+w}=\underbrace{\dfrac{1}{\prod\limits_{v\in
V}\left(  t+v\right)  }}_{=\prod\limits_{v\in V}\dfrac{1}{t+v}}\cdot
\underbrace{W^{\prime}\left(  t\right)  }_{=\prod\limits_{v\in V\setminus0}%
v}=\left(  \prod\limits_{v\in V}\dfrac{1}{t+v}\right)  \cdot\left(
\prod\limits_{v\in V\setminus0}v\right)  .
\]
Rename the index $w$ as $v$ and obtain the claim of Theorem \ref{thm.sum-prod}.
\end{proof}

\subsection{Second proof}

The following alternative proof of Theorem \ref{thm.sum-prod} was found by
Meghal Gupta, Mehtaab Sawhney, Brandon Epstein and Girishvar Venkal during the
PRIMES application contest 2015:

\begin{proof}
[Second proof of Theorem \ref{thm.sum-prod}.]Define a polynomial $f\in
L\left[  X\right]  $ by%
\begin{equation}
f=\sum_{v\in V}\prod_{w\in V\setminus\left\{  v\right\}  }\left(  X+w\right)
-\prod_{v\in V\setminus\left\{  0\right\}  }v. \label{2.sol.b.def-f}%
\end{equation}
Clearly, $\deg f\leq\left\vert V\right\vert -1$ (since each of the products
$\prod_{w\in V\setminus\left\{  v\right\}  }\left(  X+w\right)  $ has at most
$\left\vert V\right\vert -1$ terms).

Now, let $u\in V$. We shall prove that $f\left(  u\right)  =0$.

Indeed, substituting $u$ for $X$ in the identity (\ref{2.sol.b.def-f}), we
obtain%
\begin{equation}
f\left(  u\right)  =\sum_{v\in V}\prod_{w\in V\setminus\left\{  v\right\}
}\left(  u+w\right)  -\prod_{v\in V\setminus\left\{  0\right\}  }v.
\label{2.sol.b.1}%
\end{equation}
Since $u\in V$, we have $-u\in V$ (since $V$ is an additive group). Thus,%
\begin{align*}
\sum_{v\in V}\prod_{w\in V\setminus\left\{  v\right\}  }\left(  u+w\right)
&  =\prod_{w\in V\setminus\left\{  -u\right\}  }\left(  u+w\right)
+\sum_{\substack{v\in V;\\v\neq-u}}\underbrace{\prod_{w\in V\setminus\left\{
v\right\}  }\left(  u+w\right)  }_{\substack{\text{This product contains the
factor }u+\left(  -u\right)  \\\text{(because }-u\in V\setminus\left\{
v\right\}  \text{ (since }-u\in V\text{ and }-u\neq v\text{))}\\\text{and thus
is }0\text{ (because this factor is }0\text{)}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have split off the addend for }v=-u\\
\text{from the sum}%
\end{array}
\right) \\
&  =\prod_{w\in V\setminus\left\{  -u\right\}  }\left(  u+w\right)
+\underbrace{\sum_{\substack{v\in V;\\v\neq-u}}0}_{=0}=\prod_{w\in
V\setminus\left\{  -u\right\}  }\left(  u+w\right)  =\prod_{v\in
V\setminus\left\{  0\right\}  }v
\end{align*}
(here, we have substituted $v$ for $u+w$ in the product, since the map
$V\setminus\left\{  -u\right\}  \rightarrow V\setminus\left\{  0\right\}
,\ w\mapsto u+w$ is a bijection\footnote{Check this!}). Therefore,
(\ref{2.sol.b.1}) rewrites as%
\[
f\left(  u\right)  =\prod_{v\in V\setminus\left\{  0\right\}  }v-\prod_{v\in
V\setminus\left\{  0\right\}  }v=0.
\]
In other words, $u$ is a root of $f$.

Now, let us forget that we fixed $u$. We thus have proven that every $u\in V$
is a root of $f$. Thus, $f$ has at least $\left\vert V\right\vert $ roots.
Since $\left\vert V\right\vert >\deg f$ (because $\deg f\leq\left\vert
V\right\vert -1$), this shows that $f$ has more than $\deg f$ roots. According
to Lemma \ref{lem.f=0}, this entails that $f=0$. Because of
(\ref{2.sol.b.def-f}), this yields%
\[
\sum_{v\in V}\prod_{w\in V\setminus\left\{  v\right\}  }\left(  X+w\right)
=\prod_{v\in V\setminus\left\{  0\right\}  }v.
\]
Substituting $t$ for $X$ in this equality, we obtain%
\[
\sum_{v\in V}\prod_{w\in V\setminus\left\{  v\right\}  }\left(  t+w\right)
=\prod_{v\in V\setminus\left\{  0\right\}  }v.
\]
Dividing both sides by $\prod_{w\in V}\left(  t+w\right)  $, we obtain%
\begin{align*}
\dfrac{\sum_{v\in V}\prod_{w\in V\setminus\left\{  v\right\}  }\left(
t+w\right)  }{\prod_{w\in V}\left(  t+w\right)  }  &  =\dfrac{\prod_{v\in
V\setminus\left\{  0\right\}  }v}{\prod_{w\in V}\left(  t+w\right)  }=\left(
\prod_{w\in V}\dfrac{1}{t+w}\right)  \cdot\left(  \prod_{v\in V\setminus
\left\{  0\right\}  }v\right) \\
&  =\left(  \prod\limits_{v\in V}\dfrac{1}{t+v}\right)  \cdot\left(
\prod\limits_{v\in V\setminus\left\{  0\right\}  }v\right)  .
\end{align*}
Comparing this with%
\[
\dfrac{\sum_{v\in V}\prod_{w\in V\setminus\left\{  v\right\}  }\left(
t+w\right)  }{\prod_{w\in V}\left(  t+w\right)  }=\sum_{v\in V}%
\underbrace{\dfrac{\prod_{w\in V\setminus\left\{  v\right\}  }\left(
t+w\right)  }{\prod_{w\in V}\left(  t+w\right)  }}_{=\dfrac{1}{t+v}}%
=\sum\limits_{v\in V}\dfrac{1}{t+v},
\]
we obtain
\[
\sum\limits_{v\in V}\dfrac{1}{t+v}=\left(  \prod\limits_{v\in V}\dfrac{1}%
{t+v}\right)  \cdot\left(  \prod\limits_{v\in V\setminus\left\{  0\right\}
}v\right)  .
\]
This proves Theorem \ref{thm.sum-prod} again.
\end{proof}

\subsection{A generalization}

The second proof of Theorem \ref{thm.sum-prod} shown above can be easily
adapted to the following generalization:

\begin{theorem}
\label{thm.sum-prod-s}Let $V$ be a finite additive subgroup of a field $L$.
Let $s\in L\left[  X\right]  $ be a polynomial of degree $\leq\left\vert
V\right\vert -1$. Let $t\in L\setminus V$. Then,%
\[
\sum\limits_{v\in V}\dfrac{s\left(  v\right)  }{t+v}=\left(  \prod
\limits_{v\in V}\dfrac{1}{t+v}\right)  \cdot\left(  \prod\limits_{v\in
V\setminus0}v\right)  \cdot s\left(  -t\right)  .
\]

\end{theorem}

\begin{proof}
[Proof of Theorem \ref{thm.sum-prod}.]The polynomial $s\left(  -X\right)  $
has degree $\leq\left\vert V\right\vert -1$ (since the polynomial $s$ has
degree $\leq\left\vert V\right\vert -1$).

Define a polynomial $f\in L\left[  X\right]  $ by%
\begin{equation}
f=\sum_{v\in V}s\left(  v\right)  \prod_{w\in V\setminus\left\{  v\right\}
}\left(  X+w\right)  -\left(  \prod_{v\in V\setminus\left\{  0\right\}
}v\right)  \cdot s\left(  -X\right)  . \label{pf.thm.sum-prod.def-f}%
\end{equation}
Clearly, $\deg f\leq\left\vert V\right\vert -1$ (since each of the products
$\prod_{w\in V\setminus\left\{  v\right\}  }\left(  X+w\right)  $ has at most
$\left\vert V\right\vert -1$ terms, and since the polynomial $s\left(
-X\right)  $ has degree $\leq\left\vert V\right\vert -1$).

Now, let $u\in V$. We shall prove that $f\left(  u\right)  =0$.

Indeed, substituting $u$ for $X$ in the identity (\ref{pf.thm.sum-prod.def-f}%
), we obtain%
\begin{equation}
f\left(  u\right)  =\sum_{v\in V}s\left(  v\right)  \prod_{w\in V\setminus
\left\{  v\right\}  }\left(  u+w\right)  -\left(  \prod_{v\in V\setminus
\left\{  0\right\}  }v\right)  \cdot s\left(  -u\right)  .
\label{pf.thm.sum-prod.1}%
\end{equation}
Since $u\in V$, we have $-u\in V$ (since $V$ is an additive group). Thus,%
\begin{align*}
&  \sum_{v\in V}s\left(  v\right)  \prod_{w\in V\setminus\left\{  v\right\}
}\left(  u+w\right) \\
&  =s\left(  -u\right)  \prod_{w\in V\setminus\left\{  -u\right\}  }\left(
u+w\right)  +\sum_{\substack{v\in V;\\v\neq-u}}s\left(  v\right)
\underbrace{\prod_{w\in V\setminus\left\{  v\right\}  }\left(  u+w\right)
}_{\substack{\text{This product contains the factor }u+\left(  -u\right)
\\\text{(because }-u\in V\setminus\left\{  v\right\}  \text{ (since }-u\in
V\text{ and }-u\neq v\text{))}\\\text{and thus is }0\text{ (because this
factor is }0\text{)}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have split off the addend for }v=-u\\
\text{from the sum}%
\end{array}
\right) \\
&  =s\left(  -u\right)  \prod_{w\in V\setminus\left\{  -u\right\}  }\left(
u+w\right)  +\underbrace{\sum_{\substack{v\in V;\\v\neq-u}}s\left(  v\right)
0}_{=0}\\
&  =s\left(  -u\right)  \prod_{w\in V\setminus\left\{  -u\right\}  }\left(
u+w\right)  =s\left(  -u\right)  \prod_{v\in V\setminus\left\{  0\right\}  }v
\end{align*}
(here, we have substituted $v$ for $u+w$ in the product, since the map
$V\setminus\left\{  -u\right\}  \rightarrow V\setminus\left\{  0\right\}
,\ w\mapsto u+w$ is a bijection\footnote{Check this!}). Therefore,
(\ref{pf.thm.sum-prod.1}) rewrites as%
\[
f\left(  u\right)  =s\left(  -u\right)  \prod_{v\in V\setminus\left\{
0\right\}  }v-\left(  \prod_{v\in V\setminus\left\{  0\right\}  }v\right)
\cdot s\left(  -u\right)  =0.
\]
In other words, $u$ is a root of $f$.

Now, let us forget that we fixed $u$. We thus have proven that every $u\in V$
is a root of $f$. Thus, $f$ has at least $\left\vert V\right\vert $ roots.
Since $\left\vert V\right\vert >\deg f$ (because $\deg f\leq\left\vert
V\right\vert -1$), this shows that $f$ has more than $\deg f$ roots. According
to Lemma \ref{lem.f=0}, this entails that $f=0$. Because of
(\ref{pf.thm.sum-prod.def-f}), this yields%
\[
\sum_{v\in V}s\left(  v\right)  \prod_{w\in V\setminus\left\{  v\right\}
}\left(  X+w\right)  =\left(  \prod_{v\in V\setminus\left\{  0\right\}
}v\right)  \cdot s\left(  -X\right)  .
\]
Substituting $t$ for $X$ in this equality, we obtain%
\[
\sum_{v\in V}s\left(  v\right)  \prod_{w\in V\setminus\left\{  v\right\}
}\left(  t+w\right)  =\left(  \prod_{v\in V\setminus\left\{  0\right\}
}v\right)  \cdot s\left(  -t\right)  .
\]
Dividing both sides by $\prod_{w\in V}\left(  t+w\right)  $, we obtain%
\begin{align*}
\dfrac{\sum_{v\in V}s\left(  v\right)  \prod_{w\in V\setminus\left\{
v\right\}  }\left(  t+w\right)  }{\prod_{w\in V}\left(  t+w\right)  }  &
=\dfrac{\left(  \prod_{v\in V\setminus\left\{  0\right\}  }v\right)  \cdot
s\left(  -t\right)  }{\prod_{w\in V}\left(  t+w\right)  }\\
&  =\left(  \prod_{w\in V}\dfrac{1}{t+w}\right)  \cdot\left(  \prod_{v\in
V\setminus\left\{  0\right\}  }v\right)  \cdot s\left(  -t\right) \\
&  =\left(  \prod\limits_{v\in V}\dfrac{1}{t+v}\right)  \cdot\left(
\prod\limits_{v\in V\setminus\left\{  0\right\}  }v\right)  \cdot s\left(
-t\right)  .
\end{align*}
Comparing this with%
\[
\dfrac{\sum_{v\in V}s\left(  v\right)  \prod_{w\in V\setminus\left\{
v\right\}  }\left(  t+w\right)  }{\prod_{w\in V}\left(  t+w\right)  }%
=\sum_{v\in V}s\left(  v\right)  \underbrace{\dfrac{\prod_{w\in V\setminus
\left\{  v\right\}  }\left(  t+w\right)  }{\prod_{w\in V}\left(  t+w\right)
}}_{=\dfrac{1}{t+v}}=\sum\limits_{v\in V}\dfrac{s\left(  v\right)  }{t+v},
\]
we obtain
\[
\sum\limits_{v\in V}\dfrac{s\left(  v\right)  }{t+v}=\left(  \prod
\limits_{v\in V}\dfrac{1}{t+v}\right)  \cdot\left(  \prod\limits_{v\in
V\setminus\left\{  0\right\}  }v\right)  \cdot s\left(  -t\right)  .
\]
This proves Theorem \ref{thm.sum-prod-s}.
\end{proof}

Theorem \ref{thm.sum-prod} is the particular case of Theorem
\ref{thm.sum-prod-s} for $s=1$.

\section{Proofs of Theorem \ref{thm.prod-is-q}}

Many of the facts shown in Section \ref{sect.preps} have analogues in which
$\mathbb{F}_{p}$ is replaced by $\mathbb{F}_{q}$. In preparation for the proof
of Theorem \ref{thm.prod-is-q}, we shall now prove some of these analogues:

\begin{lemma}
\label{lem.q.idiot-binom}Let $q>1$ be a prime power. Let $L$ be a commutative
$\mathbb{F}_{q}$-algebra. Any two elements $u$ and $v$ of $L$ satisfy%
\begin{equation}
\left(  u+v\right)  ^{q}=u^{q}+v^{q}. \label{2.sol.c.idiot-binom}%
\end{equation}

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.q.idiot-binom}.]We know that $q>1$ is a prime power.
In other words, $q=p^{N}$ for some prime $p$ and some positive integer $N$.
Consider these $p$ and $N$. Now, $\mathbb{F}_{q}$ is a $\mathbb{F}_{p}%
$-algebra (since $q=p^{N}$). Hence, $L$ is a commutative $\mathbb{F}_{p}%
$-algebra. Let $u\in L$ and $v\in L$. Applying (\ref{2.sol.a.idiot-binom-n})
to $n=N$, we obtain $\left(  u+v\right)  ^{p^{N}}=u^{p^{N}}+v^{p^{N}}$. Since
$q=p^{N}$, this rewrites as $\left(  u+v\right)  ^{q}=u^{q}+v^{q}$. This
proves Lemma \ref{lem.q.idiot-binom}.
\end{proof}

\begin{lemma}
\label{lem.q.idiot-binom-n}Let $q>1$ be a prime power. Let $L$ be a
commutative $\mathbb{F}_{q}$-algebra. Any two elements $u$ and $v$ of $L$ and
any $n\in\mathbb{N}$ satisfy%
\begin{equation}
\left(  u+v\right)  ^{q^{n}}=u^{q^{n}}+v^{q^{n}}.
\label{2.sol.c.idiot-binom-n}%
\end{equation}

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.q.idiot-binom-n}.]To obtain a proof of Lemma
\ref{lem.q.idiot-binom-n}, just replace every \textquotedblleft$p$%
\textquotedblright\ by a \textquotedblleft$q$\textquotedblright\ in the proof
of Lemma \ref{lem.idiot-binom-n}, and replace the reference to
(\ref{2.sol.a.idiot-binom}) by a reference to (\ref{2.sol.c.idiot-binom}).
\end{proof}

\begin{lemma}
\label{lem.c.lambdap}Let $q>1$ be a prime power. Any $\lambda\in\mathbb{F}%
_{q}$ satisfies%
\begin{equation}
\lambda^{q}=\lambda. \label{2.sol.c.lambdap}%
\end{equation}

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.c.lambdap}.]To obtain a proof of Lemma
\ref{lem.c.lambdap}, just replace every \textquotedblleft$p$\textquotedblright%
\ by a \textquotedblleft$q$\textquotedblright\ in the proof of Lemma
\ref{lem.lambdap}.
\end{proof}

\begin{lemma}
\label{lem.c.lambdap-n}Let $q>1$ be a prime power. Any $\lambda\in
\mathbb{F}_{q}$ and any $n\in\mathbb{N}$ satisfy%
\begin{equation}
\lambda^{q^{n}}=\lambda. \label{2.sol.c.lambdap-n}%
\end{equation}

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.c.lambdap-n}.]To obtain a proof of Lemma
\ref{lem.c.lambdap-n}, just replace every \textquotedblleft$p$%
\textquotedblright\ by a \textquotedblleft$q$\textquotedblright\ in the proof
of Lemma \ref{lem.lambdap-n}, and replace the reference to
(\ref{2.sol.a.lambdap}) by a reference to (\ref{2.sol.c.lambdap}).
\end{proof}

\begin{lemma}
\label{lem.c.f(u+v)}Let $q>1$ be a prime power. Let $L$ be a commutative
$\mathbb{F}_{q}$-algebra. Let $f\in L\left[  X\right]  $ be a $q$-polynomial.
Then,%
\begin{equation}
f\left(  u+v\right)  =f\left(  u\right)  +f\left(  v\right)
\label{2.sol.c.f(u+v)}%
\end{equation}
for every $u\in L$ and $v\in L$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.c.f(u+v)}.]To obtain a proof of Lemma
\ref{lem.c.f(u+v)}, just replace every \textquotedblleft$p$\textquotedblright%
\ by a \textquotedblleft$q$\textquotedblright\ in the proof of Lemma
\ref{lem.f(u+v)}, and replace the reference to (\ref{2.sol.a.idiot-binom-n})
by a reference to (\ref{2.sol.c.idiot-binom-n}).
\end{proof}

\begin{lemma}
\label{lem.c.f(lu)}Let $q>1$ be a prime power. Let $L$ be a commutative
$\mathbb{F}_{q}$-algebra. Let $f\in L\left[  X\right]  $ be a $q$-polynomial.
Then,%
\begin{equation}
f\left(  \lambda u\right)  =\lambda f\left(  u\right)  \label{2.sol.c.f(lu)}%
\end{equation}
for every $u\in L$ and $\lambda\in\mathbb{F}_{q}$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.c.f(lu)}.]To obtain a proof of Lemma
\ref{lem.c.f(lu)}, just replace every \textquotedblleft$p$\textquotedblright%
\ by a \textquotedblleft$q$\textquotedblright\ in the proof of Lemma
\ref{lem.f(lu)}, and replace the reference to (\ref{2.sol.a.lambdap-n}) by a
reference to (\ref{2.sol.c.lambdap-n}).
\end{proof}

\begin{lemma}
\label{lem.c.R(f)-subsp}Let $q>1$ be a prime power. Let $L$ be a commutative
$\mathbb{F}_{q}$-algebra. Let $f\in L\left[  X\right]  $ be a $q$-polynomial.
Then,%
\begin{equation}
\mathcal{R}\left(  f\right)  \text{ is a }\mathbb{F}_{q}\text{-vector subspace
of }L. \label{2.sol.c.R(f)-subsp}%
\end{equation}

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.c.R(f)-subsp}.]To obtain a proof of Lemma
\ref{lem.c.R(f)-subsp}, just replace every \textquotedblleft$p$%
\textquotedblright\ by a \textquotedblleft$q$\textquotedblright\ in the proof
of Lemma \ref{lem.R(f)-subsp}, and replace the references to
(\ref{2.sol.f(u+v)}) and (\ref{2.sol.f(lu)}) by references to
(\ref{2.sol.c.f(u+v)}) and (\ref{2.sol.c.f(lu)}).
\end{proof}

\begin{lemma}
\label{lem.c.deriv}Let $q>1$ be a prime power. Let $L$ be a commutative
$\mathbb{F}_{q}$-algebra. Let $f\in L\left[  X\right]  $ be a $q$-polynomial.
Then,%
\begin{equation}
\text{the derivative }f^{\prime}\text{ of }f\text{ equals the coefficient of
}f\text{ before }X^{1}. \label{2.sol.c.deriv}%
\end{equation}

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.c.deriv}.]To obtain a proof of Lemma
\ref{lem.c.deriv}, just replace every \textquotedblleft$p$\textquotedblright%
\ by a \textquotedblleft$q$\textquotedblright\ in the proof of Lemma
\ref{lem.deriv}, and then replace the words \textquotedblleft(since $q\mid
q^{n}$)\textquotedblright\ by \textquotedblleft(since $\operatorname*{char}%
\left(  \mathbb{F}_{q}\right)  \mid q\mid q^{n}$ and thus $q^{n}=0$ in
$\mathbb{F}_{q}$)\textquotedblright.
\end{proof}

\begin{proof}
[Proof of Theorem \ref{thm.prod-is-q}.]We know that $q>1$ is a prime power. In
other words, $q=p^{N}$ for some prime $p$ and some positive integer $N$.
Consider these $p$ and $N$. We have $\operatorname*{char}\left(
\mathbb{F}_{q}\right)  =p$ (since $q=p^{N}$).

In order to obtain a proof of Theorem \ref{thm.prod-is-q}, it suffices to take
any of our three proofs of Theorem \ref{thm.prod-is-p}, and replace every
appearance of \textquotedblleft$p$\textquotedblright\ by \textquotedblleft%
$q$\textquotedblright\ while simultaneously replacing all references to
(\ref{2.sol.a.idiot-binom}), (\ref{2.sol.a.idiot-binom-n}),
(\ref{2.sol.a.lambdap}), (\ref{2.sol.a.lambdap-n}), (\ref{2.sol.f(u+v)}),
(\ref{2.sol.f(lu)}), (\ref{2.sol.R(f)-subsp}), (\ref{2.sol.deriv}), Lemma
\ref{lem.f(u+v)} and Lemma \ref{lem.f(lu)} by references to
(\ref{2.sol.c.idiot-binom}), (\ref{2.sol.c.idiot-binom-n}),
(\ref{2.sol.c.lambdap}), (\ref{2.sol.c.lambdap-n}), (\ref{2.sol.c.f(u+v)}),
(\ref{2.sol.c.f(lu)}), (\ref{2.sol.c.R(f)-subsp}), (\ref{2.sol.c.deriv}),
Lemma \ref{lem.c.f(u+v)} and Lemma \ref{lem.c.f(lu)}.\footnote{Here we are
regarding Lemma \ref{lem.idiot-binoms}, Lemma \ref{lem.gp}, Lemma
\ref{lem.prod1}, Lemma \ref{lem.prod2}, Lemma \ref{lem.f(u+v)-X}, Lemma
\ref{lem.f(lu)-X} (as well as the proofs of these lemmas) as parts of the
proof. So the same replacements must be made inside these lemmas and inside
their proofs.} Thus, three different proofs of Theorem \ref{thm.prod-is-q} can
be obtained.
\end{proof}

\section{Proofs of Theorem \ref{thm.prod-is-q-alg}}

\begin{proof}
[First proof of Theorem \ref{thm.prod-is-q-alg}.]As we have seen above, each
of our three proofs of Theorem \ref{thm.prod-is-p} can be turned into a proof
of Theorem \ref{thm.prod-is-q} by certain replacements. In particular,
applying these replacements to the third proof of Theorem \ref{thm.prod-is-p},
we obtain a proof of Theorem \ref{thm.prod-is-q}. It is straightforward to
observe that the latter proof of Theorem \ref{thm.prod-is-q} doubles as a
proof of Theorem \ref{thm.prod-is-q-alg} (i.e., it works just as well if $L$
is a commutative $\mathbb{F}_{q}$-algebra instead of being a field extension
of $\mathbb{F}_{q}$). Thus, Theorem \ref{thm.prod-is-q-alg} is proven.
\end{proof}

\begin{proof}
[Second proof of Theorem \ref{thm.prod-is-q-alg}.]We can also derive Theorem
\ref{thm.prod-is-q-alg} from Theorem \ref{thm.prod-is-q} as follows:

The $\mathbb{F}_{q}$-vector space $V$ is finite, and thus finite-dimensional.
Hence, it has a basis $\left(  e_{1},e_{2},\ldots,e_{n}\right)  $. Fix such a basis.

Let $M$ be the $\mathbb{F}_{q}$-algebra $\mathbb{F}_{q}\left[  X_{1}%
,X_{2},\ldots,X_{n}\right]  $ (the polynomial ring over $\mathbb{F}_{q}$ in
$n$ indeterminates $X_{1},X_{2},\ldots,X_{n}$). Then, the universal property
of the polynomial ring $M$ shows that there exists a unique $\mathbb{F}_{q}%
$-algebra homomorphism $\Phi:M\rightarrow L$ satisfying%
\begin{equation}
\left(  \Phi\left(  X_{i}\right)  =e_{i}\ \ \ \ \ \ \ \ \ \ \text{for every
}i\in\left\{  1,2,\ldots,n\right\}  \right)  .
\label{pf.thm.prod-is-q-alg.Phi=}%
\end{equation}
Consider this $\Phi$.

Let $N=\mathbb{F}_{q}\left(  X_{1},X_{2},\ldots,X_{n}\right)  $ be the
fraction field of $M$. This $N$ is clearly a field extension of $\mathbb{F}%
_{q}$. Let $W$ be the $\mathbb{F}_{q}$-vector subspace of $M$ spanned by
$X_{1},X_{2},\ldots,X_{n}$. Then, $W\subseteq M\subseteq N$. Also, the
$\mathbb{F}_{q}$-vector space $W$ is finite-dimensional, and thus finite.
Hence, Theorem \ref{thm.prod-is-q} (applied to $N$ and $W$ instead of $L$ and
$V$) yields that $\prod\limits_{v\in W}\left(  X+v\right)  \in N\left[
X\right]  $ is a $q$-polynomial. In other words, $\prod\limits_{v\in W}\left(
X+v\right)  \in M\left[  X\right]  $ is a $q$-polynomial (since $\prod
\limits_{v\in W}\left(  X+v\right)  $ belongs to $M\left[  X\right]  $
(because $W\subseteq M$)).

The $\mathbb{F}_{q}$-vector space $W$ has basis $\left(  X_{1},X_{2}%
,\ldots,X_{n}\right)  $, whereas the $\mathbb{F}_{q}$-vector space $V$ has
basis $\left(  e_{1},e_{2},\ldots,e_{n}\right)  $. The map $\Phi:M\rightarrow
L$ sends the former basis to the latter basis (because of
(\ref{pf.thm.prod-is-q-alg.Phi=})). Hence, the map $\Phi$ restricts to an
$\mathbb{F}_{q}$-vector space isomorphism $W\rightarrow V$. In other words,
the map $W\rightarrow V,\ v\mapsto\Phi\left(  v\right)  $ is well-defined and
is an $\mathbb{F}_{q}$-vector space isomorphism. In particular, this map is a bijection.

But the $\mathbb{F}_{q}$-algebra homomorphism $\Phi:M\rightarrow L$
canonically induces an $\mathbb{F}_{q}\left[  X\right]  $-algebra homomorphism
$\Phi\left[  X\right]  :M\left[  X\right]  \rightarrow L\left[  X\right]
$\ \ \ \ \footnote{Explicitly, this homomorphism $\Phi\left[  X\right]  $ is
given by
\[
\left(  \Phi\left[  X\right]  \right)  \left(  \sum_{i\geq0}a_{i}X^{i}\right)
=\sum_{i\geq0}\Phi\left(  a_{i}\right)  X^{i}%
\]
for every polynomial $\sum_{i\geq0}a_{i}X^{i}\in M\left[  X\right]  $ (with
$a_{i}\in M$).}. This latter homomorphism $\Phi\left[  X\right]  $ clearly
sends $q$-polynomials to $q$-polynomials. In other words, if $f\in M\left[
X\right]  $ is a $q$-polynomial, then $\left(  \Phi\left[  X\right]  \right)
\left(  f\right)  \in L\left[  X\right]  $ is a $q$-polynomial. Applying this
to $f=\prod\limits_{v\in W}\left(  X+v\right)  $, we conclude that $\left(
\Phi\left[  X\right]  \right)  \left(  \prod\limits_{v\in W}\left(
X+v\right)  \right)  \in L\left[  X\right]  $ is a $q$-polynomial. Since%
\begin{align*}
\left(  \Phi\left[  X\right]  \right)  \left(  \prod\limits_{v\in W}\left(
X+v\right)  \right)   &  =\prod\limits_{v\in W}\left(  X+\Phi\left(  v\right)
\right)  =\prod\limits_{v\in V}\left(  X+v\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have substituted }v\text{ for }\Phi\left(  v\right)  \text{ in
the}\\
\text{product, since the map }W\rightarrow V,\ v\mapsto\Phi\left(  v\right) \\
\text{is a bijection}%
\end{array}
\right)  ,
\end{align*}
this rewrites as follows: $\prod\limits_{v\in V}\left(  X+v\right)  \in
L\left[  X\right]  $ is a $q$-polynomial. Thus, Theorem
\ref{thm.prod-is-q-alg} is proven again.
\end{proof}

We note in passing that Lemma \ref{lem.moore.1} and Corollary
\ref{cor.moore.2} \textbf{(a)} can also be generalized to the situation where
$L$ is just a commutative $\mathbb{F}_{p}$-algebra (not necessarily a field).
Again, the generalizations can be derived from the original statements using
the same trick that we used in our second proof of Theorem
\ref{thm.prod-is-q-alg}.

\begin{thebibliography}{99999999}                                                                                         %


\bibitem[Conrad14]{kc-carlitz}Keith Conrad, \textit{Carlitz extensions}%
.\newline\url{http://www.math.uconn.edu/~kconrad/blurbs/gradnumthy/carlitz.pdf}

\bibitem[Goss98]{Goss98}David Goss, \textit{Basic Structures of Function Field
Arithmetic}, Springer, 1st edition 1998.

\bibitem[Macdon92]{mac-schurvar}I. G. Macdonald, \textit{Schur functions:
Theme and variations}, S\'{e}minaire Lotharingien de Combinatoire 28, B28a
(1992).\newline\url{http://www.emis.de/journals/SLC/opapers/s28macdonald.html}

\bibitem[Grinbe16]{gri-bor-carl}Darij Grinberg, \textit{Do the symmetric
functions have a function-field analogue?}, draft, 4 November 2016.
\newline\url{http://www.cip.ifi.lmu.de/~grinberg/algebra/schur-ore.pdf}

\bibitem[Ore33]{Ore33}Oystein Ore, \textit{On a special class of polynomials},
Trans. Amer. Math. Soc. \textbf{35} (1933), pp. 559--584.\newline\url{http://www.ams.org/journals/tran/1933-035-03/S0002-9947-1933-1501703-0/}
\end{thebibliography}


\end{document}