\section{Introduction} \label{sec:intro}

This article finds certain natural subsets of ${{\mathbb F}}_q^\x$ 
that are stabilized or permuted by Dickson or Chebyshev polynomials, where $q$ is a prime power.
This analysis leads to discovery of 
a factorization formula for Dickson and Chebyshev polynomials and some 
new results in elementary number theory.  

The $k$th Dickson polynomial of the first kind, $D_k(x)\in{{\mathbb Z}}[x]$, is determined by the recursion
$D_0(x)=2$, $D_1(x)=x$, and $D_{k+2}(x)=xD_{k+1}(x)-D_k(x)$ for $k\ge0$. It can be shown by induction
that\footnote{There is a more general definition of Dickson polynomial of the first kind that depends on a parameter~$a$.
In the more general definition, $D_k(x,a)$ is determined
by the formula $D_k(u+a/u,a) = u^k + (a/u)^k$.  However, for this article we are interested only in the case $a=1$.}
$$D_k(u+1/u) = u^k + 1/u^k,$$
where $k\ge 0$ and $u$ is an indeterminate. In fact, this functional equation determines $D_k$ uniquely and hence
can serve as an alternate definition.  Substituting $-u$ for $u$ in the functional equation implies the well-known fact that $D_k(-x)=(-1)^k D_k(x)$.

Any polynomial in ${{\mathbb Z}}[x]$ determines a function from ${{\mathbb F}}_q$ to itself.
Leonard Eugene Dickson proved in his Ph.D.\ thesis (1896)
that $D_k(x)$ permutes ${{\mathbb F}}_{q}$ if and only if ${{\rm GCD}}(k,q^2-1)=1$.
The Chebyshev polynomial of the first kind, $T_k(x)$, is related to the Dickson polynomial
by the formula $2T_k(x) = D_k(2x)$.  (Here $T$ stands for Tchebycheff, which is the French transliteration of Chebyshev.)
If 2 is invertible (e.g. in odd characteristic fields), $D_k$ and $T_k$ are essentially equivalent (in fact, conjugate), and in particular
Dickson's result carries over to Chebyshev polynomials when $q$ is odd.
However, in characteristic~2, the Dickson polynomials have a theory while the Chebyshev polynomials do not.
For this reason, we focus mainly on Dickson polynomials, although we do summarize our results in terms of Chebyshev polynomials
in Section~\ref{sec:Chebyshev}.

If $q=2^n$, then it was shown by Dillon and Dobbertin \cite{DD} that $D_k({{\cal T}}_0)\subset {{\cal T}}_0\sqcup \{0\}$
and $D_k({{\cal T}}_1) \subset {{\cal T}}_1 \sqcup \{0\}$, where ${{\cal T}}_j= \left\{ a \in {{\mathbb F}}_q^\x : \Tr(1/a)=j \right\}$.
A main theme of this article is to produce odd-characteristic analogues of this result, as described 
below.  

If $q$ is odd and $a\in{{\mathbb F}}_q$ then let $\jacobi aq$ denote the Legendre symbol:
\begin{equation}
 \jacobi a q = \begin{cases} 1 & \text{if $a$ is a square in ${{\mathbb F}}_q^\x$} \\
$-1$ & \text{if $a$ is a nonsquare in ${{\mathbb F}}_q^\x$} \\ 0 & \text{if $a=0$}. \end{cases}  \label{jacobiDef}
\end{equation}
For $\varepsilon_1,\varepsilon_2 \in \{1,-1\}$ and $\lambda \in {{\mathbb F}}_q^\x$, define
\begin{equation}{{\cal A}}_\lambda^{\varepsilon_1,\varepsilon_2}
= \left\{\, u \in {{\mathbb F}}_q : \jacobi {u-\lambda}q = \varepsilon_1,\quad
\jacobi {u+\lambda}q = \varepsilon_2 \,\right\}\label{Aij}. \end{equation}
We often write $+,-$ instead of 1, $-1$, {\it e.g.} ${{\cal A}}^{+-}_\lambda$ instead of ${{\cal A}}^{1,-1}_\lambda$.
Note that  ${{\mathbb F}}_q$ is a disjoint union:
\begin{equation*} {{\mathbb F}}_q = {{\cal A}}_\lambda^{++} \sqcup {{\cal A}}_\lambda^{+-} \sqcup {{\cal A}}_\lambda^{-+} \sqcup {{\cal A}}_\lambda^{--} \sqcup \{\lambda,-\lambda\}. \end{equation*}
We prove that $D_k(x)$ permutes each set ${{\cal A}}_2^{\pm,\pm}$ and
$T_k(x)$ permutes each set ${{\cal A}}_1^{\pm,\pm}$ when ${{\rm GCD}}(k,q^2-1)=1$. 
Even when $k$ is not assumed to be relatively
prime to $q^2-1$, we can still
say a lot about the image sets $D_k({{\cal A}}_2^{\varepsilon_1,\varepsilon_2})$
or $T_k({{\cal A}}_1^{\varep_1,\varep_2})$. The following theorem about Dickson polynomials will be
proved in Section~\ref{sec:refinements}. A corresponding theorem for Chebyshev polynomials is
stated in Theorem~\ref{thm:ChebyshevRefinements}.


\begin{theorem}  \label{thm:Aij} ($q$ odd.) Let $\varepsilon=(-1)^{(q-1)/2}$, so $q \equiv \varepsilon \pmod 4$ and $\varepsilon = \jacobi{-1}q$.
For any $k\ge1$, $D_k(2)=2$, $D_k(-2)=(-1)^k \cdot 2$, and
\begin{enumerate}
\item[{\it (i)}] $D_k({{\cal A}}_2^{++}) \subset {{\cal A}}_2^{++} \sqcup \{2,-2\varepsilon \}$ and $D_k({{\cal A}}_2^{-+}) \subset {{\cal A}}_2^{-+} \sqcup \{2,2\varepsilon\}$.  
\item[{\it (ii)}] If $k$ is odd then $D_k({{\cal A}}_2^{\varepsilon,-})\subset {{\cal A}}_2^{\varepsilon,-} \sqcup \{-2\}$ and
$D_k({{\cal A}}_2^{-\varepsilon,-}) \subset {{\cal A}}_2^{-\varepsilon,-}$. 
\item[{\it (iii)}] If $k$ is even then $D_k({{\cal A}}_2^{--}) \subset {{\cal A}}_2^{++}\sqcup \{2,-2\varepsilon \}$ and 
$D_k({{\cal A}}_2^{+-})\subset {{\cal A}}_2^{-+}\sqcup \{2,2\varepsilon \}$. 
\item[{\it (iv)}] If $(q-1)/2$ divides $k$, then $D_k({{\mathbb F}}_q) \subset {{\cal A}}_2^{+-} \sqcup {{\cal A}}_2^{-+} \sqcup \{2,-2\}$.
If in addition $k$ is even, then $D_k({{\mathbb F}}_q) \subset {{\cal A}}_2^{-+} \sqcup \{2,-2\}$.
\item[{\it (v)}] If $(q+1)/2$ divides $k$, then $D_k({{\mathbb F}}_q) \subset {{\cal A}}_2^{++} \sqcup {{\cal A}}_2^{--} \sqcup \{2,-2\}$. 
If in addition $k$ is even, then $D_k({{\mathbb F}}_q) \subset {{\cal A}}_2^{++} \sqcup \{2,-2\}$.
\item[{\it (vi)}] If ${{\cal A}}_2^{\varepsilon_1,\varepsilon_2}$ is nonempty, then 
$D_k$ permutes ${{\cal A}}_2^{\varepsilon_1,\varepsilon_2}$ iff ${{\rm GCD}}(k,d^{\varepsilon_1,\varepsilon_2})=1$, where
$d^{++}=(q-1)/2$, $d^{+-}=q+1$, $d^{-+}=(q+1)/2$, $d^{--} = q-1$. 
\end{enumerate}
\end{theorem}

The above theorem is related to some identities of Dickson polynomials.
For example, if $k$ is odd, then one can deduce from the theorem
that if $a-2$ is a square in ${{\mathbb F}}_q$, then so is $D_k(a)-2$, and if
$a-2$ is a nonsquare, then $D_k(a)-2$ is either a nonsquare or 0.
Therefore $(D_k(a)-2)/(a-2)$ should always be a square when $a\ne2$,
and since this is true for every field ${{\mathbb F}}_q$, it leads one to suspect that $(D_k(x)-2)/(x-2)$ is the square of a polynomial.
Indeed, Schur \cite{Schur} proved
$$ (D_{2k+1}(x)-2)/(x-2) = A_k(x)^2, $$
where $A_0(x)=1$, $A_1(x)=x+1$, and $A_{k+2}(x)=xA_{k+1}(x)-A_k(x)$ for $k\ge0$. 
See Theorem~\ref{thm:perfectSquares} for this and other identities.  

Another result of this article concerns the factorization of Dickson polynomials. Assuming $q$ is odd,
let $\varepsilon=(-1)^{(q-1)/2}$ and $m=(q-\varepsilon)/4$.  Then $\jacobi 2q = (-1)^m$ (see \cite[eq. (26)]{wilson-like}),
so $D_m(-2)=\jacobi2q\cdot 2$.
We prove in Theorem~\ref{thm:fijDE} that
$$ D_m(x) = \prod_{b \in {{\cal A}}_2^{-\varepsilon,-}} (x-b). $$
As shown in Theorem~\ref{thm:wilson-like}, evaluating the above formula at $x=2$ and $x=-2$ gives
\begin{equation}
\prod \left\{ a \in {{\mathbb F}}_q^\x : \text{$a$ and $4-a$ are nonsquares} \right\} = 2,
\label{T40}
\end{equation}
\begin{equation}
\prod \left\{ a \in {{\mathbb F}}_q^\x : \text{$-a$ and $4+a$ are nonsquares} \right\} = \jacobi 2 q\cdot  2.\label{T04}
\end{equation}
These formulas are striking for their similarity to Wilson's Theorem, which states that 
the product of all nonzero elements of a field ${{\mathbb F}}_q$ is $-1$.  
We decided to continue the development of Wilson-like theorems in a separate 
article \cite{wilson-like}, as it was too lengthy to include in the current work.
The article \cite{wilson-like} finds explicit formulas for
$\prod {{\cal T}}_{j,\ell}^{\varep_1,\varep_2}$
for all $j,\ell\in{{\mathbb F}}_q$ and for all $\varepsilon_1,\varepsilon_2\in \{1,-1\}$,
where
\begin{equation}
{{\cal T}}_{j,\ell}^{\varep_1,\varep_2}=
\left\{ a \in {{\mathbb F}}_q^\x : \jacobi{j-a}q=\varepsilon_1,\ \jacobi{\ell+a}q=\varepsilon_2\right\}.\label{TjellDef}
\end{equation}
The above two formulas are the special cases: $\prod{{\cal T}}_{4,0}^{--}=2$
and $\prod{{\cal T}}_{0,4}^{--}=\jacobi2q \cdot 2$.

Several other new results of a number-theoretic flavor are given in Section~\ref{sec:numberTheory} for
$q$ even or odd. 
For example, Theorem~\ref{thm:D2}({\it i}) states that 
$b \mapsto b^2-2$ is a permutation of $\left\{b\in{{\mathbb F}}_q : \jacobi{2-b}q=-1,\ \jacobi{2+b}q = 1 \,\right\}$, and the inverse of this permutation is
$$b \mapsto \prod \{(b-a) : \text{$2-a$ and $2+a$ are nonsquares} \}.$$
Another new formula is the identity for all $c \in{{\mathbb F}}_q$ ($q$ odd):
\begin{eqnarray}\label{jacc}
&&\prod\left\{c-a : a \in{{\mathbb F}}_q,\ \jacobi{a(a+4)}q= 1 \right\} + \\ \nonumber
&&\prod\left\{c-b : b \in{{\mathbb F}}_q,\ \jacobi{b(b+4)}q= -1 \right\} = \jacobi{c}q. 
\end{eqnarray}
In Theorem~\ref{thm:sqrtc} we demonstrate that if $q=2^n$, then for any $c \in {{\mathbb F}}_q$,
\begin{equation} \label{sqrtc}
 \prod \{ c + 1/a : a \in {{\mathbb F}}_q^\x,\ \Tr(a) = 0 \} 
+ \prod \{ c + 1/b : b \in {{\mathbb F}}_q^\x,\ \Tr(b)=1 \} = c^{1/2}. 
\end{equation}

Formulas~(\ref{T40}) and (\ref{sqrtc}), although discovered using Dickson
polynomials, also admit direct proofs. One-line proofs were communicated
to the author by
Richard Stong, Bradley Brock, and John Dillon and are presented in
Section~\ref{sec:oneline}.  Since the product in (\ref{T04})  can
be obtained from the product in (\ref{T40}) by substituting $-a$ for~$a$,
a direct proof of~(\ref{T04}) is also easily obtained.
It is an open question which other number-theoretic results from this
article or \cite{wilson-like} have alternative proofs.
For example, simple closed formulas for
$\prod {{\cal T}}_{j,\ell}^{\varep_1,\varep_2}$ for all $j,\ell \in{{\mathbb F}}_q$
and $\varep_1,\varep_2\in\{1,-1\}$ were discovered in \cite{wilson-like}
using Dickson polynomials, and (\ref{T40}), (\ref{T04}) are special cases
with $(j,\ell)=(4,0)$ or $(0,4)$.
It is an open problem to find alternative proofs of these formulas
when neither $j$ nor $\ell$ is zero.

\medskip
\noindent{\it Generalities. } 
Throughout this article, $p$ denotes a prime and $q=p^n$.  
Here, $p=2$ is allowed.  We use the notation:
$$\ang{u} = u + 1/u,$$
where $u\ne 0$.
Then the defining equation for $D_k$ is
$$D_k(\ang u) = \ang{u^k}.$$
In other words, there is a commutative square:
\begin{equation*}
\xymatrix{ u \ar[r]^{x^k} \ar[d] &  u^k \ar[d] \\
\ang{u} \ar[r]^{D_k} & \ang{u^k} }
\end{equation*}
Observe that $\ang{u^k}\ang{u^\ell} = \ang{u^{k+\ell}} + \ang{u^{k-\ell}}$, and so (setting
$x=\ang u$) one deduces the well-known formula if $k \ge \ell$,
\begin{equation}D_k(x) D_\ell(x) = D_{k+\ell}(x) + D_{k-\ell}(x).\label{DkDl} \end{equation}

\medskip
\noindent{\it Notation.}
We use much notation that is by now very standard: 
${{\mathbb Z}}$ denotes the ring of integers, ${\mathbb Q}$ denotes the field of 
rational numbers, and
${{\mathbb F}}_q$ denotes the unique field with $q$ elements.
If $R$ is a ring then $R^\x$ denotes the group of invertible
elements of $R$ and $R[x]$ is the polynomial ring over $R$; if $S$ is a set then $|S|$ denotes its cardinality. The symbol for union is $\cup$.
$S_1\sqcup S_2 \sqcup \cdots \sqcup S_k$ denotes 
the union of sets $S_1,\ldots,S_k$ that are known to be pairwise disjoint. 
If $F$ is a field, then $\cj F$ denotes its algebraic closure. 
We sometimes write iff or $\iff$ as an abbreviation for ``if and only if''.
We assume the reader has background in finite fields, as can be found for example in \cite[Chapter 2]{LN}. Throughout, $q=p^n$ denotes a prime power.
If $q$ is odd, then we set $\varepsilon=(-1)^{(q-1)/2}=\jacobi{-1}q$ and $m=(q-\varep)/4\in{{\mathbb Z}}$.

\section{Analysis of Dickson polynomials over finite fields} 
\label{sec:analysis}

For $d\in{{\mathbb Z}}$ not divisible by $p$, define (in characteristic~$p$)
\begin{equation} \mu_d = \left\{a \in \cj{{\mathbb F}}_p^\x : a^d = 1 \right\},\qquad 
\del d = \left\{\ang{a} : a \in \mu_d \right\}. \label{mu_delta_def}
\end{equation}
The characteristic~$p$ is not included in the notation for $\mu_d$ and $\del d$, but it will be clear from the context.
It is well known from the theory of finite fields that $\mu_d$ is a cyclic group of order~$d$ and that
$\mu_{p^n-1} = {{\mathbb F}}_{p^n}^\x$. We have $\mu_k \cap \mu_d = \mu_g$, where $g = {{\rm GCD}}(k,d)$.
If $uv\ne 0$, then $\ang u = \ang v \iff u^2v + v = uv^2 + u \iff (uv-1)(u-v)=0$, and so
\begin{equation} \ang u = \ang v \iff v \in \{u,1/u\}.\label{angEquality} \end{equation}
In particular, $u$ and $v$ have the same multiplicative order. From this, we see that 
\begin{equation} \del k \cap \del d = \del g,\qquad \text{where $g={{\rm GCD}}(k,d)$} \label{delg}
\end{equation}
and
\begin{equation}
\ang{\mu_k} \subset \ang{\mu_d} \iff k|d,\qquad
\ang{\mu_k} = \ang{\mu_d} \iff k = d. \label{delEquality}
\end{equation}

It has been noted in \cite{Brewer}, \cite[Lemma~3.5]{Lidl}, and \cite[p.~356]{DD} that 
$u+1/u \in {{\mathbb F}}_q$ iff $u^{q+1}=1$ or $u^{q-1}=1$. In our notation, 
this observation takes the form of Lemma~\ref{lem:FqDecomposition}, below.

\begin{lemma} ($q$ even or odd.) \label{lem:FqDecomposition} ${{\mathbb F}}_q = \del{q-1} \cup \del{q+1}$. Also, $\del{q-1} \cap \del{q+1} = \{2,-2\}$. \end{lemma}

\begin{proof} 
Given $a \in {{\mathbb F}}_q$, let $u \in \cj {{\mathbb F}}_q^\x$ such that $u^2-au+1=0$. Then $u\ne 0$ and $a=u+1/u$.
By~(\ref{angEquality}),
$$a\in{{\mathbb F}}_q\iff \ang u = \ang {u^q} \iff u^q \in \{u,1/u\} \iff u \in \mu_{q-1}\cup \mu_{q+1}.$$  
If $q$ is odd, then $\del{q-1}\cap\del{q+1}=\del 2 = \{\ang 1,\ang{-1}\}=\{2,-2\}$ by (\ref{delg}).
If $q$ is even, then $\{2,-2\}=\{0\}$ and also $\del{q-1}\cap\del{q+1}=\del 1 = \{0\}$. 
\end{proof}

Define the following subsets of $\cj{{\mathbb F}}_p$:
\begin{equation} {{\cal Z}} = \{2,-2\},\qquad \delstar d = \del d \setminus {{\cal Z}}, \label{deltaStar} \end{equation}
where $p \nmid d$.  
Note that ${{\cal Z}} = \del 2$ if $p$ is odd, and ${{\cal Z}} = \{0 \} = \del 1$ if $p=2$.
By Lemma~\ref{lem:FqDecomposition}, ${{\mathbb F}}_q$ is a disjoint union:
\begin{equation} {{\mathbb F}}_q = \delstar {q-1} \sqcup \delstar {q+1} \sqcup {{\cal Z}}. \label{FqDisjoint} \end{equation}
By (\ref{angEquality}), $u \mapsto \ang u $ is 2-to-1 from $\mu_d$ to $\del d$ unless $u \in \{1,-1\}$, in which case it is 1-to-1.
Noting that $\mu_d\cap\{\,1,-1\} = \{1\}$ if $d$ is odd and $\{1,-1\}$ if $d$ is even, it follows that
\begin{equation}|\delstar d|= \begin{cases} (d-1)/2 &\text{if $d$ is odd} \\  (d-2)/2 & \text{if $d$ is even} \end{cases} = \lfloor (d-1)/2 \rfloor.
\label{deltaCard} \end{equation}
In particular,
\begin{equation}
|\del {q-1}^*| = \begin{cases} q/2 - 1 & \text{if $q$ is even,} \\
(q-3)/2 & \text{if $q$ is odd,} \end{cases} \qquad
|\del {q+1}^*| = \begin{cases} q/2  & \text{if $q$ is even,} \\
(q-1)/2 & \text{if $q$ is odd.} \end{cases} \label{deltaCount}
\end{equation}
The next lemmas are well known.  As usual, assume $p\nmid d$.

\begin{lemma} \label{powerMap} Let $k\ge 1 $ and $g={{\rm GCD}}(d,k)$. The map $a \mapsto a^k$ gives a $g$-to-1 map from $\mu_d$ onto $\mu_{d/g}$.
\end{lemma}
\begin{proof} 
Write $k=gk_0$ and $d=gd_0$. 
If $a \in \mu_d$, then $a^k \in \mu_{d_0}$ because
$(a^k)^{d_0} = (a^d)^{k_0}=1$.  Conversely, if $b \in \mu_{d_0}$ then
we must show $b=a^k$ for some $a\in \mu_d$. Let $c$ be a $g$-th root of $b$;
then $c \in \mu_d$. By the Euclidean 
algorithm \cite{Niven-Zuckerman}, there are
$r,s\in{{\mathbb Z}}$ such that $rk+sd=g$. 
Then $b=c^g = c^{rk+sd}=(c^r)^k\cdot (c^d)^s = a^k$, where $a=c^r \in\mu_d$.
We have shown that $a \mapsto a^k$ is a homomorphism from $\mu_d$ onto $\mu_{d/g}$. The kernel must have order
$d/(d/g)=g$, so the map is $g$-to-1.
\end{proof}

\begin{lemma} \label{Dkdelta} Let $k\ge 1$ and $g={{\rm GCD}}(d,k)$. Then $D_k(\del d) = \del {d/g}\subset \del d$. In particular, $D_k$
permutes $\del d$ if and only if ${{\rm GCD}}(d,k)=1$. \end{lemma}
\begin{proof} Let $\ang a \in \del d$. Then $D_k(\ang a)=\ang{a^k} \in \del {d/g}$ by Lemma~\ref{powerMap}. To prove surjectivity, let
$\ang b \in \del {d/g}$, where $b\in \mu_{d/g}$. By Lemma~\ref{powerMap}, $b=a^k$ for some $a\in\mu_d$. Then $D_k(\ang a)=\ang{a^k}=\ang b$.
We have shown that $D_k(\ang{\mu_d})=\mu_{d/g}$.  
In particular, $D_k$ permutes $\del d$ iff
$\ang{\mu_{d/g}}=\ang{\mu_d}$ iff $g=1$ by (\ref{delEquality}).
\end{proof}

\begin{proposition}   \label{prop:dicksonImage} 
Let $q=p^n$ (even or odd), $k \ge 1$,  $r = {{\rm GCD}}(k,q-1)$, and $s={{\rm GCD}}(k,q+1)$. Then
$$D_k({{\mathbb F}}_q) = \del {(q-1)/r} \cup \del {(q+1)/s}.$$
\end{proposition}
\begin{proof} This is immediate from Lemmas \ref{lem:FqDecomposition} 
and~\ref{Dkdelta}. 
\end{proof}

Dickson's result, that $D_k$ permutes ${{\mathbb F}}_q$ if and only if ${{\rm GCD}}(k,q^2-1)=1$, follows immediately from Proposition~\ref{prop:dicksonImage}, 
Lemma~\ref{lem:FqDecomposition}, and (\ref{delEquality}).

\begin{corollary} \label{cor:DkeqDl} $D_k({{\mathbb F}}_q) = D_\ell({{\mathbb F}}_q)$ iff ${{\rm GCD}}(k,q-1)={{\rm GCD}}(\ell,q-1)$ and ${{\rm GCD}}(k,q+1) = {{\rm GCD}}(\ell,q+1)$.
\end{corollary}

Corollary~\ref{cor:DkeqDl} was observed by Dillon and Dobbertin \cite[pages 355--356]{DD} and was used to prove 
their beautiful theorem:

\begin{theorem} (Dillon and Dobbertin, \cite[Theorem 7]{DD}) 
Let $k=2^e+1$ or $k=2^e-1$ and $q=2^n$, and assume that $(k,n)=1$. Then $D_k({{\mathbb F}}_q)={{\mathbb F}}_q$ if ${{\rm GCD}}(k,2^{2n}-1)=1$, and otherwise $D_k({{\mathbb F}}_q)=D_3({{\mathbb F}}_q)$.
\end{theorem}

In summary, if $p\nmid d$, $k\ge1$, and $g = {{\rm GCD}}(d,k)$, then the commutative diagram shown in Figure~\ref{fig:commutativeDiagram} holds.
The map $x \mapsto x + 1/x$ is 2-to-1 unless $x=1/x$, {\it i.e.} $x\in \{1,-1\}$,
in which case $\ang x \in {{\cal Z}}$.
Using this, one can work out the multiplicities of $D_k$; see \cite[Theorem 3.26]{Lidl}.
Here we just present the simplest case.

\begin{figure}[h]
\begin{equation*}
\xymatrix{ a \in \mu_d \ar[r]^{x^k} \ar[d]_{x+1/x} &  a^k \in \mu_{d/g} \ar[d]^{x+1/x}\\
\ang{a} \in \del d \ar[r]^{D_k} & \ \ang{a^k} \in \del {d/g} }
\end{equation*}
\caption{Commutative diagram}
\label{fig:commutativeDiagram}
\end{figure}



\begin{proposition} \label{Dk_multiplicity} ($q$ even or odd.) Consider $D_k : \del d \to \del {d/g}$, where $g={{\rm GCD}}(d,k)$. If $y \in \delstar {d/g}=\del {d/g} \setminus {{\cal Z}}$, then $y$ has
exactly $g$ preimages in $\del d$ under $D_k$, which all belong to $\delstar d$.
\end{proposition}
\begin{proof} By Lemma~\ref{Dkdelta}, the horizontal arrows in Figure~\ref{fig:commutativeDiagram} are surjective. 
Let $y \in \ang{\mu_{d/g}^*}$ and let $t$ denote the number of preimages of $y$ in $\ang{\mu_d}$; we will show that
$t=g$.
Let $\ang a\in\del d $ be a preimage of $y$, so
$y = D_k(\ang a) = \ang{a^k}$. By hypothesis, $y \not \in {{\cal Z}}$. Since $D_k({{\cal Z}}) \subset {{\cal Z}}$, none of the preimages of
$y$ under the map $D_k$ belong to ${{\cal Z}}$, either. Note that $\ang a \not \in{{\cal Z}}$ implies that $\ang a $ has exactly two preimages in $\mu_d$ under the map
$x + 1/x$ (namely $a$ and $1/a$).  Now consider the commutative diagram, 
and count the number of preimages of $y$ in the top left of the diagram in two ways.  We can pull back vertically to $\mu_{d/g}$ to obtain two preimages, and then pull back by the power map to obtain $2\x g$ preimages in $\mu_d$.
Alternatively, pull back by $D_k$ to get $t$ preimages in $\delstar d$, and then by the vertical map to obtain $2 \x t$ preimages in $\mu_d$.  Thus, $2g=2t$ and so $t=g$.
\end{proof}

\begin{corollary} \label{cor:permuteDel} ($q$ even or odd.) Suppose that $\delstar d \ne \emptyset$ (equivalently, $d>2$). Then $D_k(x)$ permutes $\delstar d$
iff GCD$(d,k)=1$.
\end{corollary}
 

\section{Alternative descriptions of $\delstar{q-1}$ and $\delstar{q+1}$ in even characteristic} \label{sec:evenq}

The sets $\delstar{q-1}$ and $\delstar{q+1}$ have interesting alternative descriptions. In the characteristic two case, this is well known, due to Dillon
and Dobbertin.  
Since $D_k(\del{q-1}) \subset \del{q-1}$
and $D_k(\del{q+1}) \subset \del{q+1}$, these alternative descriptions lead to interesting results 
(Proposition~\ref{DTq} and Theorem~\ref{thm:oddq})
about subsets of ${{\mathbb F}}_q$ that are preserved by Dickson polynomials. 

For $j=0,1$ and $q=2^n$ define
\begin{equation} {{\cal T}}_j = \{ a \in {{\mathbb F}}_{q}^\x : \Tr_{{{\mathbb F}}_{q}/{{\mathbb F}}_2}(1/a) = j \}. \label{TqjDef}
\end{equation}
Since $\Tr_{{{\mathbb F}}_q/{{\mathbb F}}_2}$ is a surjective homomorphism, its kernel has order $q/2$, and so $|{{\cal T}}_0\sqcup \{0\}|=|{{\cal T}}_1|=q/2$.
${{\mathbb F}}_q$ is a disjoint union:
\begin{equation} {{\mathbb F}}_q = {{\cal T}}_{0} \sqcup {{\cal T}}_{1} \sqcup \{0\},\quad \text{and $|{{\cal T}}_{0}|=q/2-1$, $|{{\cal T}}_{1}|=q/2$.} \label{decomp1}\end{equation}
On the other hand, by (\ref{FqDisjoint}) and (\ref{deltaCount}), ${{\mathbb F}}_q$ may also be written as a disjoint union:
\begin{equation} {{\mathbb F}}_q = \delstar{q-1} \sqcup \delstar{q+1} \sqcup \{0\},\quad 
\text{and $|\delstar{q-1}|=q/2-1$, $|\delstar{q+1}|=q/2$.}\label{decomp2}\end{equation}
The following was observed by Dillon and Dobbertin.

\begin{proposition} (\cite[page 355]{DD}) \label{calT_prop}
Let $q=2^n$. Then $\del{q-1} = {{\cal T}}_{0}\sqcup\{0\}$ and $ \del{q+1}= {{\cal T}}_{1}  \sqcup\{0\}$.
\end{proposition}
\begin{proof} 
Since ${{\cal Z}} = \{0\}$ in characteristic~2, we see in the notation of (\ref{deltaStar}) and~(\ref{FqDisjoint}) that $\delstar{q\pm1}=\del{q\pm1} \cap {{\mathbb F}}_q^\x$,
so the proposition is equivalent to
\begin{equation}\delstar{q-1} = {{\cal T}}_{0}, \qquad \delstar{q+1} = {{\cal T}}_{1}  \qquad\text{when $q=2^n$.} \label{Tq01} \end{equation}
We will prove $\delstar{q-1} \subset {{\cal T}}_{0}$. Since the cardinalities of these sets are the same, this will imply they are equal.
Then, (\ref{decomp1}) and (\ref{decomp2}) together will imply that $\delstar{q+1}={{\cal T}}_{1}$ as well.

Let $a \in \delstar{q-1}$;  then $a\ne 0$ and $a=r+1/r$ with $r \in {{\mathbb F}}_q^\x$.  We have $(r/a^2)(a+r+1/r)=0$, or equivalently $r/a + (r/a)^2 = 1/a^2$.
Then $\Tr_{{{\mathbb F}}_q/{{\mathbb F}}_2}(1/a)=0$, {\it i.e.} $a\in {{\cal T}}_{0}$. Thus, $\delstar{q-1}\subset {{\cal T}}_{0}$ as claimed.
\end{proof}

\begin{proposition} \cite[page 356]{DD}  \label{DTq} ($q$ even.)
$D_k({{\cal T}}_{0}) \subset {{\cal T}}_{0} \cup \{0\}$ and $D_k({{\cal T}}_{1}) \subset {{\cal T}}_{1}\cup \{0\}$.
$D_k$ permutes ${{\cal T}}_{0}$ iff ${{\rm GCD}}(k,q-1)=1$, and it 
permutes ${{\cal T}}_{1}$ iff ${{\rm GCD}}(k,q+1)=1$.
\end{proposition}

\begin{proof} The first sentence is immediate from 
Proposition~\ref{calT_prop} and Lemma~\ref{Dkdelta}. 
By Lemma~\ref{Dkdelta}, $D_k$ permutes $\del{q-1}$ iff ${{\rm GCD}}(k,q-1)=1$. 
Since $D_k(0)=D_k(\ang 1) = \ang{1^k}=0$, 
we see that $D_k$ permutes $\del{q-1}$ 
iff it permutes $\del{q-1} \setminus \{0\} = {{\cal T}}_{0}$.  
A similar argument applies to $\del{q+1}$ and ${{\cal T}}_{1}$.
\end{proof}

Flori and Mesnager (\cite[Section 2]{FM}) have a different proof that
$D_k({{\cal T}}_{i}) \subset {{\cal T}}_{i} \cup \{0\}$.  Namely, they
compute a rational function $R_k$ such that
$1/D_k(x) + 1/x = R_k(x)^2 + R_k(x)$. From this, they deduce that if $a\in{{\mathbb F}}_q^\x$ and $D_k(a)$ is nonzero, then 
$1/D_k(a)$ and $1/a$ have the same absolute trace.
Thus, $D_k({{\cal T}}_{i})\subset {{\cal T}}_{i} \cup \{0\}$. 

\begin{proposition} \label{prop:evenPermute} ($q$ even.) 
({\it i})\  
$D_k({{\cal T}}_{1})=\{0\}$ iff $q+1$ divides $k$.  
If $q>2$ then $D_k({{\cal T}}_{0})=\{0\}$ iff $q-1$ divides $k$. \\
({\it ii})\   
$D_k(b)=b^2$ for all $b \in {{\cal T}}_{1}$ iff $k \equiv \pm2 \pmod {q+1}$. 
If $q>2$ then 
$D_k(a)=a^2$ for all $a \in {{\cal T}}_{0}$ iff $k \equiv \pm2 \pmod {q-1}$. \\
({\it iii}) Let $e\ge 0$. If $e$ is even, then $D_{q^e-1}(a)=0$ and $D_{q^e+1}(a)=a^2$ for all $a\in{{\mathbb F}}_q$.  If $e$ is odd, then
$$D_{q^e-1}(a) = \begin{cases} 0 & \text{if $a\in{{\cal T}}_0 \cup \{0\}$} \\
a^2 & \text{if $a\in{{\cal T}}_1$,} \end{cases}
\qquad
D_{q^e+1}(a) = \begin{cases} a^2 & \text{if $a \in {{\cal T}}_{0} \cup \{0\}$}\\
0 & \text{if $a\in{{\cal T}}_1$.} \end{cases}
$$
\end{proposition}

\begin{proof}  For arbitrary $k\ge 1$ and any odd $d > 1$,
$D_k(\del d)=\del 1=\{0\}$ iff $d$ divides $k$
by Lemma~\ref{Dkdelta}.   Since $D_k(0)=0$ always and $D_0(x)=2=0$, 
it follows that for any $k\ge0$ and any odd $d>1$,
$D_k(\delstar d)=\{0\}$ iff $d$ divides $k$.  
By Proposition~\ref{calT_prop},
$\delstar {q-1}={{\cal T}}_{0}$ and $\delstar{q+1}={{\cal T}}_{1}$.
({\it i}) now follows.
For ({\it ii}), let $k=\pm 2 \pmod{q+1}$. Let
$b=\ang u\in {{\cal T}}_{1}$, so $u^{q+1}=1$. Then
$D_k(b) = \ang{u^k}=\ang{u^{\pm2}}=\ang{u^2}=\ang u^2=b^2$.
Conversely, suppose $D_k(b)=b^2$ for all $b \in {{\cal T}}_{1}$.
Let $u$ have order exactly $q+1$ and $b=\ang u$. Since $b\in{{\cal T}}_{1}$,
$D_k(b)=b^2$.  Then $\ang{u^k}=\ang{u^2}$, so 
$u^k \in \{u^2,u^{-2}\}$ by~(\ref{angEquality}). Thus, $u^{k-2}=1$ or 
$u^{k+2}=1$.
It follows that $q+1$ divides $k-2$ or $k+2$, {\it i.e.} $k=\pm2 \pmod{q+1}$.
The second statement in ({\it ii}) is proved analogously.  Statement
({\it iii}) follows from ({\it i}) and ({\it ii})
by noting that
$$q^e= ((q-1)+1)^e \equiv 1 \pmod{q-1},\qquad
q^e= ((q+1)-1)^e \equiv (-1)^e \pmod{q+1}$$
and $D_k(a)=0=a^2$ when $a=0$.
\end{proof}

\section{Alternative descriptions of $\delstar{q-1}$ and $\delstar{q+1}$ in odd characteristic} \label{sec:oddq}

Proposition~\ref{calT_prop} provides an alternative description of the sets 
$\del{q-1}$ and $\del{q+1}$ in characteristic~2. 
We have found alternative descriptions in odd characteristic as well.
If $q$ is odd, define the following subsets of ${{\mathbb F}}_q$:
\begin{equation}{{\cal Z}} = \{2,-2\},\qquad {{\cal S}}_q = \{ a \in {{\mathbb F}}_q : \text{$a^2-4 $ is a nonzero square in ${{\mathbb F}}_q$}\},\label{ZSN} \end{equation}
$${{\cal N}}_q = \{ a \in {{\mathbb F}}_q : \text{$a^2-4$ is a nonsquare in ${{\mathbb F}}_q$}\}.$$
Note that ${{\mathbb F}}_q$ is a disjoint union:
\begin{equation} {{\mathbb F}}_q = {{\cal S}}_q \sqcup {{\cal N}}_q \sqcup {{\cal Z}}.   \label{FqDecomp} \end{equation}
Proposition~\ref{prop:calT_prop2} below was observed by Brewer \cite{Brewer}. Theorem~\ref{thm:oddq} seems to be new.

\begin{proposition} \label{prop:calT_prop2} ($q$ odd.) 
${{\cal S}}_q = \delstar{q-1}$, ${{\cal N}}_q = \delstar{q+1}$, and $|{{\cal S}}_q| = (q-3)/2$, $|{{\cal N}}_q|=(q-1)/2$.
\end{proposition}
\begin{proof}  Let $a \in{{\mathbb F}}_q$, and write $a = u + 1/u$, or equivalently $u^2 - a u + 1 = 0$. 
By the quadratic formula, $u=(a \pm \sqrt{a^2-4})/2$.  Thus, $u\in{{\mathbb F}}_q^\x$ iff $a^2-4$ is a square iff $a\in{{\cal S}}_q\sqcup{{\cal Z}}$.
In other words, $a=\ang u\in{{\cal S}}_q\sqcup{{\cal Z}}$ iff $u\in\mu_{q-1}$.
This shows that ${{\cal S}}_q\sqcup{{\cal Z}}=\del{q-1}=\delstar{q-1}\sqcup{{\cal Z}}$, {\it i.e.}, ${{\cal S}}_q=\delstar{q-1}$.
Now (\ref{FqDisjoint}) and (\ref{FqDecomp}) together imply ${{\cal N}}_q=\delstar{q+1}$.
The last assertion follows from (\ref{deltaCount}). 
\end{proof}

\begin{theorem}  \label{thm:oddq} ($q$ odd.) 
For any $k\ge 1$, $D_k({{\cal Z}}) \subset {{\cal Z}}$, $D_k({{\cal S}}_q) \subset {{\cal S}}_q \sqcup {{\cal Z}}$, and 
$D_k({{\cal N}}_q) \subset {{\cal N}}_q \sqcup {{\cal Z}}$. Further, $D_k$ permutes ${{\cal Z}}$ iff $k$ is odd, and
it permutes ${{\cal N}}_q$ iff ${{\rm GCD}}(k,q+1)=1$. If ${{\cal S}}_q$ is nonempty (equivalently, $q>3$), then 
$D_k$ permutes ${{\cal S}}_q$ iff ${{\rm GCD}}(k,q-1)=1$. If $(q-1)/2$ divides $k$ then $D_k({{\mathbb F}}_q)\subset {{\cal N}}_q \sqcup {{\cal Z}}$.
If $(q+1)/2$ divides $k$ then $D_k({{\mathbb F}}_q) \subset {{\cal S}}_q \sqcup {{\cal Z}}$.
\end{theorem}
\begin{proof} Since $2=\ang{1}$ and $-2=\ang{-1}$, 
\begin{equation} \text{$D_k(2)=\ang{1^k}=2$ and $D_k(-2)=\ang{(-1)^k} = (-1)^k 2$.} \label{DkZ} \end{equation}
This shows that $D_k({{\cal Z}})
\subset {{\cal Z}}$, and that $D_k$ permutes ${{\cal Z}}$ exactly when $k$ is odd.
Next, since $D_k(\del d) \subset \del d$ for any~$d$, Proposition~\ref{prop:calT_prop2} implies that
$$D_k({{\cal S}}_q) \subset D_k({{\cal S}}_q \sqcup {{\cal Z}}) = D_k(\del {q-1}) \subset \del {q-1} = {{\cal S}}_q \sqcup {{\cal Z}}$$
and
$$D_k({{\cal N}}_q) \subset D_k({{\cal N}}_q \sqcup {{\cal Z}}) = D_k(\del {q+1}) \subset \del{q+1} = {{\cal N}}_q \sqcup {{\cal Z}}.$$
Since ${{\cal N}}_q=\delstar{q+1}$, $D_k(x)$ permutes ${{\cal N}}_q$ iff GCD$(k,q+1)=1$
by Corollary~\ref{cor:permuteDel}. Likewise,
since ${{\cal S}}_q = \delstar{q-1}$, if $q-1>2$ then $D_k$ permutes
${{\cal S}}_q$ iff GCD$(k,q-1)=1$.
If $(q-1)/2$ divides~$k$, then by
Propositions~\ref{prop:dicksonImage} and~\ref{prop:calT_prop2},
$$D_k({{\mathbb F}}_q) \subset \del2 \cup \del{q+1}
={{\cal Z}} \sqcup \delstar{q+1} = {{\cal Z}} \sqcup {{\cal N}}_q.$$
Similarly, if $(q+1)/2$ divides~$k$, then 
$D_k({{\mathbb F}}_q) \subset \del{q-1} \cup \del{2}
={{\cal S}}_q \sqcup {{\cal Z}}$.
\end{proof}

\begin{lemma} \label{lem:oddq}  ($q$ odd.) Let $k,\ell \ge 0$. If ${{\cal S}}_q$ is nonempty, then
$D_k(a)=D_\ell(a)$ for all $a \in {{\cal S}}_q$ iff $k\equiv \pm \ell \pmod{q-1}$. 
Also,  
$D_k(b)=D_\ell(b)$ for all $b \in {{\cal N}}_q$ iff $k\equiv \pm \ell \pmod{q+1}$.
\end{lemma}
\begin{proof} In general, $D_k(a)=D_\ell(a)$ for all $a \in \del d$
iff $\ang{u^k}=\ang{u^\ell}$ for all $u\in \mu_d$ iff 
$u^k \in \{u^\ell,u^{-\ell}\}$ for all $u \in \mu_d$ iff 
$k \equiv \pm \ell\pmod d$. 
If $d>2$, then by taking $u$ primitive of order $d$, the above argument 
tells us that
$D_k(a)=D_\ell(a)$ for all $a \in \delstar d$ iff $k\equiv \pm\ell
\pmod d$. Now the result follows by noting that ${{\cal S}}_q = \delstar{q-1}$
and ${{\cal N}}_q = \delstar{q+1}$.
\end{proof}

\begin{corollary} ($q$ odd.) Let $e\ge0$. If $e$ is even, then $D_{q^e-1}(a)=2$ and $D_{q^e+1}(a)=
a^2-2$ for all $a \in {{\mathbb F}}_q$.  If $e$ is odd, then for $a \in {{\mathbb F}}_q$,
\begin{equation*}
D_{q^e-1}(a) = \begin{cases} a^2 - 2 & \text{if $a\in{{\cal N}}_q$}\\
2 & \text{otherwise;} \end{cases}
\qquad
D_{q^e+1}(a) = \begin{cases} 2 & \text{if $a\in{{\cal N}}_q$}\\
a^2-2 & \text{otherwise.} \end{cases}
\end{equation*}
\end{corollary}
\begin{proof}
Apply Lemma~\ref{lem:oddq} and eq.~(\ref{DkZ}),  noting that 
$q^e \equiv 1 \pmod {q-1}$,
$q^e \equiv (-1)^e \pmod{q+1}$, and $D_2(x)=x^2-2$.
Note that when $k$ is even, $D_k(a)=2=a^2-2$ for $a\in\{2,-2\}$.
\end{proof}


\section{Further refinements when $q$ is odd} \label{sec:refinements}
Theorem~\ref{thm:oddq} shows that $D_k$ preserves certain subsets of ${{\mathbb F}}_q$: it maps ${{\cal Z}}$ to itself, ${{\cal S}}_q$ to ${{\cal S}}_q \sqcup {{\cal Z}}$,
and ${{\cal N}}_q$ to ${{\cal N}}_q \sqcup {{\cal Z}}$.  Further, precise conditions on $k$ are given that determine when $D_k$ permutes ${{\cal Z}}$, ${{\cal S}}_q$, and
${{\cal N}}_q$.
It turns out we can obtain finer results of this type when $q$ is odd, as we now describe.
Let $\jacobi aq$ denote the Legendre symbol, defined by (\ref{jacobiDef}).
It is well known that ${{\mathbb F}}_q^\x$ is cyclic; if $g$ is a generator then $g^i$ is a square in ${{\mathbb F}}_q^\x$ iff $i$ is even.
From this, we see that $\jacobi {g^k}q = (-1)^k$, and so the Legendre symbol is multiplicative:
$\jacobi a q \jacobi b q = \jacobi {ab}q$.
Define ${{\cal A}}_\lambda^{\varepsilon_1,\varepsilon_2}$ by (\ref{Aij}). 
Noting that $\jacobi {a^2-4}q = \jacobi {a-2}q \jacobi {a+2}q$, we see that ${{\cal S}}_q$ and ${{\cal N}}_q$ break into disjoint unions:
\begin{eqnarray}
{{\cal S}}_q &=& {{\cal A}}_2^{++} \sqcup {{\cal A}}_2^{--} = \{ a \in {{\mathbb F}}_q : \text{$a^2-4 $ is a nonzero square in ${{\mathbb F}}_q$}\},\label{ZSN2} \\
{{\cal N}}_q &=& {{\cal A}}_2^{+-} \sqcup {{\cal A}}_2^{-+} = \{ a \in {{\mathbb F}}_q : \text{$a^2-4$ is a nonsquare in ${{\mathbb F}}_q$}\}. 
\end{eqnarray}
In addition,  ${{\mathbb F}}_q$ is a disjoint union:
\begin{equation} {{\mathbb F}}_q = {{\cal A}}_2^{++} \sqcup {{\cal A}}_2^{+-} \sqcup {{\cal A}}_2^{-+} \sqcup {{\cal A}}_2^{--} \sqcup {{\cal Z}} = {{\cal S}}_q \sqcup {{\cal N}}_q \sqcup {{\cal Z}}.   \label{FqDecomp2} \end{equation}

\begin{theorem} \label{thm:AijDescription} ($q$ odd.)
For each $\varepsilon_1,\varepsilon_2 \in \{1,-1\}$,
\begin{equation}
{{\cal A}}_2^{\varepsilon_1,\varepsilon_2} = \left\{ v^2 + v^{-2} : v^{q-\varepsilon_1\varepsilon_2} = \varepsilon_2, v^4 \ne 1\right \}.
\label{AijCharacterization}
\end{equation}
Further, 
$${{\cal A}}_2^{++} = \delstar{(q-1)/2},\quad {{\cal A}}_2^{--} = \delstar{q-1}\setminus \delstar{(q-1)/2},$$ 
$${{\cal A}}_2^{-+}=\delstar{(q+1)/2},\quad {{\cal A}}_2^{+-}=\delstar{q+1}\setminus \delstar{(q+1)/2},$$
$$|{{\cal A}}_2^{++}| = \lfloor (q-3)/4 \rfloor,\quad |{{\cal A}}_2^{+-}| = \lfloor (q+1)/4 \rfloor,\quad 
|{{\cal A}}_2^{-+}| = \lfloor (q-1)/4 \rfloor,\quad |{{\cal A}}_2^{--}|=\lfloor (q-1)/4 \rfloor. $$
\end{theorem}
\begin{proof}   If $a=\ang{v^2}$, where $v\in\cj{{\mathbb F}}_q$, then by Lemma~\ref{lem:FqDecomposition},
$$a \in {{\mathbb F}}_q \iff v^2 \in \mu_{q-1} \cup \mu_{q+1} \iff v \in \mu_{2q-2}\cup\mu_{2q+2}.$$
Now $v^{2q-2}=1 \iff v^{q-1}\in\{1,-1\}$, and similarly $v^{2q+2}=1 \iff v^{q+1}\in\{1,-1\}$.  
Thus, there are integers $c,d\in \{1,-1\}$ such that $v^{q-c}=d$.
Note that $v^4=1$ iff $\ang{v^2} \in \ang{\mu_2}={{\cal Z}}$. Assume now that $v^4\ne 1$, therefore $\ang{v^2}\not \in {{\cal Z}}$. 
Then the integers 
$c,d\in \{1,-1\}$ such that $v^{q-c}=d$ are uniquely determined. Define 
${{\rm Type}}(v)=(c,d)$. Let $a=\ang{v^2}\in{{\mathbb F}}_q$. Then 
$$a - 2 = (v-1/v)^2, \qquad a + 2 = (v+1/v)^2 $$
and these are nonzero because of the assumption that $v^4 \ne 1$. Now $a-2$ is a square iff $v-1/v \in {{\mathbb F}}_q$.
In general, if $v,w$ are nonzero then $v-1/v=w-1/w$ iff $w \in \{v,-1/v\}$. Thus, $(v-1/v)=(v-1/v)^q$ iff $v^q \in \{v,-1/v\}$,
which is equivalent to ${{\rm Type}}(v) \in \{(1,1),(-1,-1)\}$.  It follows that if ${{\rm Type}}(v)=(c,d)$ then $\jacobi{a-2}q = cd$.
Similarly, $a+2$ is a square iff $v+1/v \in {{\mathbb F}}_q$
iff $v^q \in \{v,1/v\}$ iff ${{\rm Type}}(v) \in \{(1,1),(-1,1)\}$. It follows that $\jacobi{a+2}q=d$.
This proves (\ref{AijCharacterization}). In particular,
\begin{eqnarray*}
{{\cal A}}_2^{++} &=& \{ \ang{v^2} : v^{q-1}=1,\ v^4\ne 1 \} \\
&=&  \{\ang u : u^{(q-1)/2} = 1,\ u^2 \ne 1 \} = \del{(q-1)/2}\setminus \del 2  \\
&=& \delstar {(q-1)/2},
\end{eqnarray*}
and ${{\cal A}}_2^{-+} = \delstar {(q+1)/2}$ by a similar computation.  Next,
 ${{\cal A}}_2^{--} = {{\cal S}}_q \setminus {{\cal A}}_2^{++} = \delstar{q-1} \setminus \delstar{(q-1)/2}$, and ${{\cal A}}_2^{+-}={{\cal N}}_q\setminus {{\cal A}}_2^{-+}
=\delstar{q+1} \setminus \delstar{(q+1)/2}$. 
By (\ref{deltaCard}), $|{{\cal A}}_2^{++}| =  \lfloor (d-1)/2 \rfloor$, 
where $d=(q-1)/2$; this proves $|{{\cal A}}_2^{++}|= \lfloor (q-3)/4 \rfloor$. The same computation with $d=(q+1)/2$ shows $|{{\cal A}}_2^{-+}|=
\lfloor (q-1)/4 \rfloor$.  Next, $|{{\cal A}}_2^{--}| = |\delstar{q-1}|-|\delstar{(q-1)/2}| = (q-3)/2 - \lfloor (q-3)/4 \rfloor = \lceil (q-3)/4 \rceil$.
In general, if $2m$ is an integer, then $\lceil m\rceil=\lfloor m+1/2 \rfloor$.
Thus, $\lceil{(q-3)/4}\rceil = \lfloor  (q-1)/4 \rfloor$. The formula $|{{\cal A}}_2^{+-}|=\lfloor (q+1)/4 \rfloor$ may be computed similarly.
\end{proof}

\begin{lemma} \label{lemma:Z01}  ($q$ odd.)
${{\cal Z}} \cap \del{(q-1)/2} = \{2,-2\varepsilon\}$
and ${{\cal Z}} \cap \del{(q+1)/2} = \{2,2\varepsilon\}$, 
where $\varepsilon=(-1)^{(q-1)/2}$. 
\end{lemma}
\begin{proof} In general, $\mu_d\cap{{\cal Z}}=\mu_d\cap\mu_2=\mu_g$, where
$g={{\rm GCD}}(d,2)$. Thus, $\mu_d\cap{{\cal Z}}={{\cal Z}}$ if $d$ is even, 
and $\mu_d\cap{{\cal Z}}=\mu_1=\{2\}$
if $d$ is odd. Noting that $(q-\varepsilon)/2$ is even and $(q+\varepsilon)/2$
is odd, the result follows.
\end{proof}

Because of Theorem~\ref{thm:AijDescription}, $D_k$ maps the sets ${{\cal A}}_2^{\varepsilon_1,\varepsilon_2}$ to one another in patterned ways, as described in 
Theorem~\ref{thm:Aij}.  We are now ready  to prove that theorem.

\noindent {\it Proof of Theorem~\ref{thm:Aij}.}\qquad 
If ${{\rm Type}}(v)=(c,d)$, {\it i.e.}, $v^{q-c}=d$ and $v^4\ne 1$, then $(v^k)^{q-c}=d^k$.   
Thus, either $v^{4k} = 1$ or ${{\rm Type}}(v^k)=(c,d^k)$.
By (\ref{AijCharacterization}),
${{\rm Type}}(v)=(c,d)$ iff $\ang{v^2} \in {{\cal A}}_2^{cd,d}$,  therefore
$$D_k({{\cal A}}_2^{cd,d}) \subset {{\cal A}}_2^{cd',d'} \cup \{2,-2\},\quad\text{where $d'=d^k$.}$$
To complete the proof of ({\it i})--({\it iii}), we need only consider 
$D_k({{\cal A}}_2^{\varepsilon_1,\varepsilon_2})\cap {{\cal Z}}$.
First, $D_k({{\cal A}}_2^{++}) \subset D_k( \del{(q-1)/2}) \subset \del{(q-1)/2}$,
so $D_k({{\cal A}}_2^{++})\cap{{\cal Z}} \subset \{2,-2\varepsilon\}$ by 
Lemma~\ref{lemma:Z01}.
Similarly, $D_k({{\cal A}}_2^{-+}) \subset \del{(q+1)/2}$, so 
$D_k({{\cal A}}_2^{-+})\cap{{\cal Z}} \subset \{2,2\varepsilon\}$ by Lemma~\ref{lemma:Z01}. 
This proves ({\it i}).
For ({\it ii}), let $\ang{v^2} \in {{\cal A}}_2^{-c,-}$, so ${{\rm Type}}(v)=(c,-1)$, and let $k$ be odd. Then $(v^k)^{q-c}=-1$. 
If $c=\varepsilon$, then
$(v^k)^{q-c}$ is a power of $v^{4k}$, therefore $v^{4k}\ne 1$, showing $D_k(\ang{v^2}) \not \in{{\cal Z}}$.  
Thus, $D_k({{\cal A}}_2^{-\varepsilon,-}) \cap {{\cal Z}} = \emptyset$. Next, if 
$c=-\varepsilon$ then
$(v^k)^{q-c}$ is an odd power of $v^{2k}$. Since $(v^k)^{q-c}=-1$, we see that $v^{2k}\ne 1$, and therefore $D_k(\ang{v^2})\ne 2$. Thus,
$D_k({{\cal A}}_2^{-\varepsilon,-}) \cap {{\cal Z}} \subset \{-2\}$. 
To prove ({\it iii}), let $k$ be even. 
Then 
$D_k({{\cal A}}_2^{--}) \subset D_k(\del{q-1}) \subset \del{(q-1)/2}$,
so $D_k({{\cal A}}_2^{--})\cap{{\cal Z}} \subset \{2,-2\varepsilon\}$.  Likewise,
$D_k({{\cal A}}_2^{+-}) \subset D_k(\del{q+1}) \subset \del{(q+1)/2}$, so
$D_k({{\cal A}}_2^{+-})\cap{{\cal Z}} \subset \{2,2\varepsilon\}$.

For ({\it iv}), if $(q-1)/2$ divides $k$ then $D_k(\del{q-1}) \subset \del 2 = {{\cal Z}}$, so
$D_k({{\mathbb F}}_q) \subset D_k(\del{q+1}) \cup {{\cal Z}} \subset \del{q+1}  \cup {{\cal Z}} = {{\cal A}}_2^{+-} \cup {{\cal A}}_2^{-+} \cup {{\cal Z}}$.
If in addition $k$ is even, then $D_k({{\mathbb F}}_q)\subset D_k(\del{q+1})\cup{{\cal Z}} \subset \del{(q+1)/2}\cup{{\cal Z}}=
{{\cal A}}_2^{-+} \cup{{\cal Z}}$.
The statement ({\it v}) is proved similarly.

Finally, we prove ({\it vi}). In general, if $p\nmid d$ and ${{\rm GCD}}(k,d)=1$ then $D_k$ permutes $\del d$. Since $D_k$ takes ${{\cal Z}}$ to itself,
$D_k$ must also permute $\delstar d$.  If in addition $d'$ divides $d$, then since $D_k$ takes $\delstar{d'}$ to itself, we see that 
$D_k$ must permute $\delstar{d} \setminus \delstar{d'}$. These considerations show that $D_k$ permutes ${{\cal A}}_2^{\varepsilon_1,\varepsilon_2}$
when ${{\cal A}}_2^{\varep_1,\varep_2}$ is nonempty and GCD$(k,d^{\varepsilon_1,\varepsilon_2})=1$. Now we prove the converse. Since ${{\cal A}}_2^{++}=\delstar{(q-1)/2}$, 
if this set is nonempty then there is $\ang b \in {{\cal A}}_2^{++}$ with order$(b)=(q-1)/2$.
If ${{\rm GCD}}(k,(q-1)/2)) > 1$, then every element $\ang {u} \in D_k({{\cal A}}_2^{++})$ has order$(u) < (q-1)/2$,
showing that $\ang b$ is not in the image.  Thus, $D_k$ permutes ${{\cal A}}_2^{++}$
if and only if ${{\rm GCD}}(k,(q-1)/2)=1$. The other cases are proved similarly.
\qed



\medskip
\noindent{\bf Example.} 
In ${{\mathbb F}}_{29}$, the nonzero squares are $\{1,4,5,6,7,9,13,16,20,22,23,24,25,28\}$.
By the definition of ${{\cal A}}_2^{\varepsilon_1,\varepsilon_2}$, 
$${{\cal A}}_2^{++}=\{3,7,11,18,22,26\}, \qquad {{\cal A}}_2^{+-}=\{1,6,8,9,15,24,25\},$$
$${{\cal A}}_2^{-+}=\{4,5,14,20,21,23,28\},  \qquad {{\cal A}}_2^{--} = \{\, 0, 10, 12, 13, 16, 17, 19 \,\}. $$
We will demonstrate Theorem~\ref{thm:Aij} in some special cases.
One assertion is that if $k$ is odd, then $D_k({{\cal A}}_2^{--})\subset {{\cal A}}_2^{--}$, and 
$D_k$ permutes ${{\cal A}}_2^{--}$ if
and only if $(k,29-1)=1$. We test this in a few cases. 
For $k=5$, $D_5(x) = x^5-5 x^3 + 5x$. 
$D_5(x)$ permutes ${{\cal A}}_2^{--}$ as follows: it takes $0,10,12,13,16,17,19$ to $0,17,16,19,10,13,12$, respectively. 
This is the permutation $(0)(10,17,13,19,12,16)$.
On the other hand, $D_7=x^7 - 7 x^5 + 14 x^3 - 7 x$ maps ${{\cal A}}_2^{--}$ to $\{0\}$, so $D_7$ maps ${{\cal A}}_2^{--}$ to itself but is not a permutation. 
In this case, the seven elements of ${{\cal A}}_2^{--}$ are roots of $D_7$, so
$$D_7(x)=\prod_{a \in {{\cal A}}_2^{--}} (x-a) \pmod{29}.$$ 

The above formula for $D_7$ is quite interesting, and the phenomenon generalizes: If
$q\equiv 1 \pmod 4$ then $D_{(q-1)/4}(x) = \prod_{a \in {{\cal A}}_2^{--}} (x-a)$. This and 
similar results 
will be shown in the next section.

\section{Wilson-like theorems} \label{sec:wilson-like}

In this section, we use Dickson polynomials to obtain some Wilson-like theorems and other results in elementary
number theory.  The starting point is
Theorem~\ref{thm:fijDE} below, which generalizes the phenomenon that was observed for $D_7(x)$ at the end of the preceding section. 
First we need to introduce more sets and polynomials.

For $\varepsilon_1,\varepsilon_2 \in \{1,-1\}$ and $\lambda \in {{\mathbb F}}_q^\x$, 
define for $q$ odd:
\begin{equation} {{\cal B}}_\lambda^{\varepsilon_1,\varepsilon_2} = 
\left\{ b \in {{\mathbb F}}_q : \jacobi{\lambda-b}q=\varepsilon_1,\
\jacobi{\lambda+b}q=\varepsilon_2 \right\}. \label{BDef}
\end{equation}
Note that ${{\cal B}}_\lambda^{\varepsilon_1,\varepsilon_2} = {{\cal A}}_\lambda^{\varepsilon\varepsilon_1,\varepsilon_2}$,
where as usual $\varepsilon = \jacobi{-1}q=(-1)^{(q-1)/2}$. Also note that $b \mapsto -b$ gives
a bijection from ${{\cal B}}_\lambda^{\varepsilon_1,\varepsilon_2}$ to ${{\cal B}}_\lambda^{\varepsilon_2,\varepsilon_1}$.
As usual, we often write the superscripts as $+$ and $-$ instead of 1 and $-1$.
Let $m = (q-\varep)/4$, which is always an integer. By Theorem~\ref{thm:AijDescription},
\begin{eqnarray}  
{{\cal B}}_2^{++} &=& {{\cal A}}_2^{\varep,+} = \delstar{2m}, \qquad
{{\cal B}}_2^{--} = {{\cal A}}_2^{-\varep,-} = \delstar{4m} \setminus \delstar{2m},  \label{BppBmm} \\
{{\cal B}}_2^{-+} &=& {{\cal A}}_2^{-\varep,+} = \delstar{2m+\varep}, \qquad
{{\cal B}}_2^{+-} = {{\cal A}}_2^{\varep,-} = \delstar{4m+2\varep} \setminus \delstar{2m+\varep}.  \label{BpmBmp} 
\end{eqnarray}

Define the following polynomials in ${{\mathbb F}}_q[x]$ for $\varep_1,\varep_2 \in \{1,-1\}$:
\begin{equation} \label{fijDef}
f^{\varepsilon_1,\varepsilon_2}(x) = \prod_{a \in {{\cal A}}_2^{\varepsilon_1,\varepsilon_2}} (x-a), \qquad 
g^{\varepsilon_1,\varepsilon_2}(x) = \prod_{a \in {{\cal B}}_2^{\varepsilon_1,\varepsilon_2}} (x-a) = f^{\varep\varep_1,\varep_2}(x)
\end{equation}
\begin{equation} \label{fSfNdef}
f_{{\cal S}} = \prod_{a\in{{\cal S}}_q} (x-a), \qquad
 f_{{\cal N}} = \prod_{a\in{{\cal N}}_q} (x-a), \qquad
 f_{{\cal Z}} = \prod_{a \in {{\cal Z}}}(x-a) = x^2-4. 
\end{equation}
Since ${{\cal S}}_q = {{\cal A}}_2^{++} \sqcup {{\cal A}}_2^{--}$ and ${{\cal N}}_q = {{\cal A}}_2^{+-}\sqcup {{\cal A}}_2^{-+}$,
$$ f_{{\cal S}} = f^{++} f^{--},\qquad f_{{\cal N}} = f^{+-} f^{-+}.$$
Also, since $\prod_{a\in{{\mathbb F}}_q}(x-a) = x^q-x$, (\ref{FqDecomp}) implies that 
$$f_{{\cal S}}(x) f_{{\cal N}}(x) f_{{\cal Z}}(x) = x^q-x.$$

Define $E_k\in{{\mathbb Z}}[x]$ for $k\ge 0$ by 
\begin{equation} \label{Edef} \text{$E_0(x)=1$, $E_1(x)=x$, and 
$E_{k+2}(x) = x E_{k+1}(x) - E_k(x)$.} \end{equation}
This is called a Dickson polynomial of the second kind, and like $D_k$, it has
been widely studied. It is well known (and can easily be shown by 
induction on $k$) that 
\begin{equation} \label{Efunctional} E_{k-1}(\ang u) = \frac{u^k - 1/u^k}{u-1/u}
\end{equation}
Parts {(\it i}) and {(\it ii)} of the next theorem are known. (See \cite{chou1,BZ}).

\begin{theorem} \label{thm:fijDE} ($q$ odd.)  In ${{\mathbb F}}_q[x]$, the following holds. \\
({\it i})\quad If $k>1$, then 
\begin{equation}
E_{k-1}(x) = \prod_{a \in \delstar{2k}} (x-a). \label{Edelta}
\end{equation}
({\it ii})\quad If $k\ge 1$, then 
\begin{equation} 
D_k(x) = \prod_{ a \in \delstar {4k}\setminus \delstar {2k}} (x-a).
\label{Ddelta}
\end{equation}
({\it iii})\quad $f_{{\cal S}}(x) = E_{(q-3)/2}(x)$ and $f_{{\cal N}}(x) = E_{(q-1)/2}(x)$. \\
({\it iv})\quad Let $m=(q-\varep)/4$. Then $D_{m}(x) = g^{--}(x)$
and $E_{m-1}(x) = g^{++}(x)$, where $g^{\pm,\pm}(x)$ is defined in~(\ref{fijDef}). \\
\end{theorem}

\begin{proof}  First we prove the assertions about $E_k$.
The two polynomials in (\ref{Edelta}) have the same degree by (\ref{deltaCard}), 
so to prove equality it suffices
to show that if $a = \ang u \in \delstar{2k}$ then $E_{k-1}(a) = 0$.
Here $u \in \mu_{2k}$ and $u^2\ne 1$. Since $u^{2k}=1$, $u^k = 1/u^k$.
On the other hand, $u \ne 1/u$. Thus, $E_{k-1}(\ang u)=0$ by (\ref{Efunctional}), as
required.   All the assertions about $E_k$ follow from this observation, together
with the fact that ${{\cal S}}_q = \delstar{q-1}$, ${{\cal N}}_q = \delstar{q+1}$,
and ${{\cal B}}_2^{++} = \delstar{(q-\varep)/2} = \delstar{2m}$. 

It remains to prove the assertions about $D_k$. 
The polynomials in (\ref{Ddelta}) are monic and have the same degree by
(\ref{deltaCard}), so to show equality, it suffices to show that $a \in \delstar{4k} \setminus
\delstar{2k}$ implies $D_k(a)=0$. Indeed, writing $a=\ang u$ we have
$u^{4k}=1$ but $u^{2k}\ne 1$, so $u^{2k}=-1$ and $u^k=i$ is a square root of
$-1$. Then $D_k(a)=\ang{u^k}=\ang{i}=0$, as required. This proves ({\it ii}), and ({\it iv}) follows
immediately by (\ref{BppBmm}).
\end{proof}

We are ready to prove the Wilson-like theorems.  For many more theorems of this sort, see the sequel to this article, \cite{wilson-like}.

\begin{theorem} \label{thm:wilson-like}
($q$ odd.) ({\it i})\ $\prod \{\,a\in{{\mathbb F}}_q^\x : \text{$a$ and $4-a$ are nonsquares} \,\}=2$. \\
({\it ii})\  $\prod \{\,a \in {{\mathbb F}}_q^\x : \text{$-a$ and $4+a$ are nonsquares} \,\} = \begin{cases} 2 & \text{if $q\equiv \pm1\pmod8$}
\\ - 2 & \text{if $q\equiv \pm3 \pmod8$.}\end{cases}$
\end{theorem}

\begin{proof} Let $m=(q-\varep)/4$. Substituting $x=2$ into the formula $D_m(x) = g^{--}(x)$ gives
$$\prod \{ (2-b) : b \in {{\cal B}}_2^{--} \} = 2,$$
since $D_n(2)=2$ for all $n$. Set $a=2-b$. Then $2+b=4-a$. The condition that $b \in {{\cal B}}_2^{--}$ is
therefore equivalent to $a$ and $4-a$ being nonsquares.  This proves~({\it i}).

For the second statement, evaluate $D_m(x) = g^{--}(x)$ at $x=-2$. Since $D_n(-2)=D_n(\ang{-1})=\ang{(-1)^n} = (-1)^n \cdot 2$ for all~$n$,
we obtain:
$$\prod \{ (-2-b) : b \in {{\cal B}}_2^{--} \} = (-1)^{m}2,$$
Set $a=-2-b$. Then $2+b=-a$ and $2-b=4+a$, so $b\in{{\cal B}}_2^{--}$ iff $-a$ and $4+a$ are nonsquares.
This proves~({\it ii}).
\end{proof}

\section{More number-theoretic results} \label{sec:numberTheory}

The statements of the next few theorems do not mention 
Dickson polynomials, although they are certainly working behind the scenes! Let ${{\cal B}}_\lambda^{\varep_1,\varep_2}$ be as in (\ref{BDef}).

\begin{theorem} \label{thm:D2}  ($q$ odd.) ({\it i})\ The map $b \mapsto b^2-2$ gives a permutation $\pi$ on ${{\cal B}}_2^{-+}$, and the inverse permutation is
$$ \pi^{-1}(b) = \prod\{b-a : a \in {{\cal B}}_2^{--} \}\qquad\text{for $b \in{{\cal B}}_2^{-+}$.}$$
Further,  $\pi^{-1}(b)$ is the unique square root of $2+b$ such that $2+\sqrt{2+b}$ is a square. \\
({\it ii}) The map $b \mapsto 2-b^2$ gives a permutation $\sigma$ of ${{\cal B}}_2^{+-}$, 
and the inverse permutation is
$$ \sigma^{-1}(b) = -\jacobi{2}q\prod\{b-a : a \in {{\cal B}}_2^{--} \}
\qquad\text{for $b \in{{\cal B}}_2^{+-}$.}$$
Further, $\sigma^{-1}(b)$ is the unique square root of $2-b$ such that $\sqrt{2-b}+2$ is a nonsquare.
({\it iii}) Let $\lambda \in {{\mathbb F}}_q^\x$ and $\nu = \jacobi{2\lambda} q$. Then 
$$b\mapsto \pi_{\lambda}(b) = (2\nu/\lambda) b^2 - \nu\lambda$$
is a permutation of ${{\cal B}}_{\lambda}^{-+}$, and
$$b\mapsto \sigma_{\lambda}(b) = -(2\nu/\lambda) b^2 + \nu\lambda $$
is a permutation of ${{\cal B}}_{\lambda}^{+-}$.
The inverse permutations are 
$$\pi_{\lambda}^{-1}(b) = (2\nu/\lambda)^{m-1} \prod \left\{b-a : a \in {{\cal B}}_{\lambda}^{-\nu,-\nu}\right\}
\qquad\text{for $b \in{{\cal B}}_\lambda^{-+}$,}$$
$$\sigma_{\lambda}^{-1}(b) = -\jacobi2q(2\nu/\lambda)^{m-1} \prod \left\{b-a : a \in {{\cal B}}_{\lambda}^{-\nu,-\nu}\right\}
\qquad\text{for $b \in{{\cal B}}_\lambda^{+-}$,}$$
where $m=(q-\varep)/4$.
If $b\in{{\cal B}}_\lambda^{-+}$ and $c=\pi_\lambda^{-1}(b)$, then $c=\sqrt{(\lambda\nu b+\lambda^2)/2}$, where the choice of square root is uniquely determined by the property
that $c+\lambda$ is a square.
If $b\in{{\cal B}}_\lambda^{+-}$ and $c=\sigma_\lambda^{-1}(b)$, then $c=\sqrt{(-\lambda\nu b+\lambda^2)/2}$, where the choice of square root is uniquely determined by the property
that $c+\lambda$ is a nonsquare.
\end{theorem}

\begin{proof}  Noting that ${{\cal B}}_2^{-+}=\delstar{2m+\varep}$ by (\ref{BpmBmp}), both $D_2$ and $D_m$ permute it by Corollary~\ref{cor:permuteDel}. 
Further, if $b=\ang u \in {{\cal B}}_2^{-+}$ then $D_2(b)=\ang{u^2}=\ang{u}^2-2=b^2-2=\pi(b)$, and
$$D_m \circ \pi(b) = D_m(\ang{u^2})=\ang{u^{2m}}=\ang{u^{-\varep}}=\ang u=b.$$
Thus, $D_m=\pi^{-1}$.  By Theorem~\ref{thm:fijDE}({\it iv}), $D_m(b)=\prod\{b-a : a \in {{\cal B}}_2^{--}\}$. 
Let $c=\pi^{-1}(b)$. Then $b=c^2-2$, so $c$ is a square root of $b+2$. Noting that $c\in{{\cal B}}_2^{-+}$ and
$-c \in {{\cal B}}_2^{+-}$, the choice of square root is determined by the property that $\sqrt{b+2}+2$ is a square.
This proves~({\it i}).

Since $b\mapsto -b$ is a bijection from ${{\cal B}}_2^{+-}$ onto ${{\cal B}}_2^{-+}$, we see that
$\sigma(b) = -\pi(-b)=-((-b)^2-2)=2-b^2$ is a bijection from ${{\cal B}}_2^{+-}$ onto itself.  The inverse maps $b$ to the
unique square root of $2-b$ such that $2+\sqrt{2-b}$ is a nonsquare. Such exists because $(2-\sqrt{2-b})(2+\sqrt{2-b})=b+2$ is a nonsquare.
Also, $\sigma^{-1}(b)=-\pi^{-1}(-b)=-D_m(-b)=-(-1)^m D_m(b)$. By \cite[Eq. (26)]{wilson-like}, $(-1)^m=\jacobi 2q$. Part~({\it ii}) of the theorem
follows.

To prove ({\it iii}), note that $b \mapsto (\lambda/2) b $ is a bijection from 
${{\cal B}}_2^{\varep_1,\varep_2}$ onto ${{\cal B}}_\lambda^{\nu\varep_1,\nu\varep_2}$, because $\jacobi{2-b}q=\varep_1$ iff 
$\jacobi{\lambda-\lambda b/2}q = \jacobi{\lambda/2}q\jacobi{2-b}q=\nu\varep_1$, and likewise $\jacobi{2+b}q=\varep_2$ iff
$\jacobi{\lambda+\lambda b/2}q = \nu\varep_2$.  Noting that $-{{\cal B}}_\lambda^{\varep_1,\varep_2} = {{\cal B}}_\lambda^{\varep_2,\varep_1}$,
it follows that $\nu{{\cal B}}_\lambda^{\nu,-\nu}={{\cal B}}_\lambda^{+-}$ and
$\nu{{\cal B}}_\lambda^{-\nu,\nu}={{\cal B}}_\lambda^{-+}$,
so $b\mapsto (\lambda\nu/2) b$ is a bijection from ${{\cal B}}_2^{+-}$ onto ${{\cal B}}_\lambda^{+-}$ 
and also from ${{\cal B}}_2^{-+}$ onto ${{\cal B}}_\lambda^{-+}$.
The composition of the bijections
$${{\cal B}}_\lambda^{-+} \stackrel{2\nu/\lambda}\longrightarrow{{\cal B}}_2^{-+} \stackrel\pi\longrightarrow {{\cal B}}_2^{-+} 
\stackrel{\lambda\nu/2}\longrightarrow {{\cal B}}_\lambda^{-+}$$
determines a permutation $\pi_\lambda$ of ${{\cal B}}_\lambda^{-+}$. Likewise, the composition of bijections
$${{\cal B}}_\lambda^{+-} \stackrel{2\nu/\lambda}\longrightarrow {{\cal B}}_2^{+-} \stackrel\sigma\longrightarrow {{\cal B}}_2^{+-} 
\stackrel{\lambda\nu/2}\longrightarrow {{\cal B}}_\lambda^{+-}$$
determines a permutation $\sigma_\lambda$ of ${{\cal B}}_\lambda^{+-}$. 
If $b\in {{\cal B}}_\lambda^{-+}$, then $\pi_\lambda(b) = (\lambda\nu/2) \pi(2\nu b/\lambda) = (\lambda \nu/2) ((2\nu b/\lambda)^2-2)
= (2\nu/\lambda) b^2 - \lambda \nu$. By a similar computation, if $b\in {{\cal B}}_\lambda^{+-}$ then 
$\sigma_\lambda(b)= (-2 \nu/\lambda)b^2+\lambda\nu$.  Next, if $b\in{{\cal B}}_\lambda^{-+}$ then
\begin{eqnarray*}
\pi_\lambda^{-1}(b) &=& (\lambda\nu/2) \pi^{-1} (2\nu b/\lambda)  \\
&=& \lambda\nu/2 \prod \left\{ (2\nu b/\lambda) - a : a \in {{\cal B}}_2^{--} \right\} \\
&=& (2\nu/\lambda)^{m-1} \prod \left\{ b - (\lambda\nu/2) a : a \in {{\cal B}}_2^{--} \right\}\\
&=& (2\nu/\lambda)^{m-1} \prod \left\{ b - a : a \in {{\cal B}}_{\lambda}^{-\nu,-\nu} \right\},\\
\end{eqnarray*}
and a similar computation implies the formula for $\pi_\sigma^{-1}$.  For the last assertion, suppose that $c=\pi_\lambda^{-1}(b)$, 
where $b,c\in{{\cal B}}_\lambda^{-+}$.
Note that $-c\in{{\cal B}}_\lambda^{+-}$.  Since $b=\pi_\lambda(c)=(2\nu/\lambda)c^2-\nu\lambda$, we see that $c$ is a square root of $(b+\nu\lambda)\nu\lambda/2$.
The correct square root belongs to ${{\cal B}}_\lambda^{-+}$, and the incorrect one belongs to ${{\cal B}}_\lambda^{+-}$. Thus, $c=\sqrt{(\nu\lambda b + \lambda^2)/2}$,
where the choice of square root is uniquely determined by the property that $c+\lambda$ is a square.  The statement for $\sigma_\lambda^{-1}(b)$ is proved similarly.
\end{proof}

\begin{theorem} ($q$ odd.) Let $c \in {{\mathbb F}}_q$, so $c \in \{2,-2\}$ or $c$ belongs to one of the sets ${{\cal B}}_2^{\varepsilon_1,\varepsilon_2}$.  Then
$$ \prod\left\{c-a : a \in {{\cal B}}_2^{--}\right\} = \begin{cases} 2 & \text{if $c=2$} \\
\jacobi 2q 2 & \text{if $c=-2$} \\
\sqrt{c+2}  & \text{if $c\in {{\cal B}}_2^{-+}$} \\
-\jacobi2q\sqrt{2-c\,}  & \text{if $c\in {{\cal B}}_2^{+-}$} \\
2 & \text{if $c\in {{\cal B}}_2^{++}$ and $\sqrt{c+2} \in {{\cal B}}_2^{++}$} \\
-2 
& \text{if $c\in {{\cal B}}_2^{++}$ and $\sqrt{c+2} \not \in {{\cal B}}_2^{++}$} \\
0 & \text{if $c\in {{\cal B}}_2^{--}$} 
\end{cases}
$$
where in line~3, $\sqrt{c+2}$ is selected so that $\sqrt{c+2}+2$ is a square, and in line~4, $\sqrt{2-c\,}$ is selected so that $\sqrt{2-c\,}+2$ is a nonsquare.
Further, if $c \in {{\cal B}}_2^{++}$ then $\pm\sqrt{c+2}$ both belong to $ {{\cal B}}_2^{++}$ or both belong to ${{\cal B}}_2^{--}$.
\end{theorem}

\begin{proof} 
By Theorem~\ref{thm:fijDE}, the left side equals $D_m(c)$, 
where $m=(q-\varepsilon)/4$. 
Then $D_m(2)=2$ and $D_m(-2)=(-1)^m 2 = \jacobi2q 2$.
The result when $c \in {{\cal B}}_2^{+-}$ or $c \in {{\cal B}}_2^{-+}$ follows from Theorem~\ref{thm:D2}, since in line~3, $\sqrt{c+2}=\pi^{-1}(c)$ 
and in line~4, $\sqrt{2-c\,}=\sigma^{-1}(c)$. If $c\in {{\cal B}}_2^{++}$ then $c = \ang{v^2}$, where
$v^{q-\varepsilon}=1$ and $v^4\ne 1$. 
In this case, $D_m(c)=\ang{(v^2)^m}=\ang{v^{(q-\varepsilon)/2}}$. Since $v^{q-\varepsilon}=1$, we know $v^{(q-\varepsilon)/2}=\kappa$,
where $\kappa \in \{1,-1\}$. Then $D_m(c) = \ang\kappa =\kappa\cdot 2$.  Now $c+2=\ang{v^2}+2=\ang{v}^2$, so $\sqrt{c+2}=\pm\ang v$. 
Let $w$ be a square root of $v$. Then $w^{q-\varepsilon}=(w^2)^{(q-\varepsilon)/2}=\kappa$,
and $w^8=v^4\ne 1$. Consequently, $\ang v = \ang{w^2} \in {{\cal B}}_2^{\kappa,\kappa}$ by (\ref{AijCharacterization}).
Since $a \mapsto -a$ maps ${{\cal B}}_2^{\kappa,\kappa}$
to itself, the other square root of $c+2$, namely $-\ang v$, also belongs to ${{\cal B}}_2^{\kappa,\kappa}$.
We have shown that if $c \in {{\cal B}}_2^{++}$ then there is
$\kappa \in \{1,-1\}$ such that $D_m(c)=\kappa \cdot 2$  and
$\pm\sqrt{c+2} \in {{\cal B}}_2^{\kappa,\kappa}$. When $\kappa=1$, 
$D_m(c)=2$ and $\pm\sqrt{c+2} \in {{\cal B}}_2^{++}$. When $\kappa=-1$,
$D_m(c)=-2$ and $\pm\sqrt{c+2} \in {{\cal B}}_2^{--}$.
This proves the formula when $c\in {{\cal B}}_2^{++}$ and also demonstrates the final
assertion of the theorem. Finally,
if $c \in {{\cal B}}_2^{--}$ then one of the factors in the product is $c-c=0$, so the left side vanishes.
\end{proof}

\begin{proposition} ($q$ odd.) \label{prop:D2plus}  $b \mapsto b^2-2$ is a two-to-one map from $({{\cal B}}_2^{++} \sqcup {{\cal B}}_2^{--}) \setminus \{0\}$ onto ${{\cal B}}_2^{++}$.
\end{proposition}

\begin{proof} Note that $b^2-2=D_2(b)$, and $D_2$ maps ${\del{2d}}$ onto 
${\del{d}}$. By~(\ref{BppBmm}), ${{\cal B}}_2^{++} \sqcup {{\cal B}}_2^{--} = \delstar{q-\varep}$, so
$D_2\left({{\cal B}}_2^{++} \sqcup {{\cal B}}_2^{--}\setminus\{0\}\right) \subset  \del{(q-\varepsilon)/2}$.  
The solutions to $b^2-2=2$ are $b\in\{2,-2\}$, so 2 is not in the range.
Since we exclude $b=0$ from the domain, $-2$ also is not in the range.   Thus, the image is contained in $\delstar{(q-\varep)/2}={{\cal B}}_2^{++}$.
Note that $D_2(b) = D_2(b')$ iff $b = \pm b'$. Since $b \mapsto -b$
stabilizes ${{\cal B}}_2^{++}$ and ${{\cal B}}_2^{--}$, and since $b=0$ is excluded, 
every image point has exactly two preimages, showing that the map is two-to-one.
\end{proof}

\begin{proposition} ($q$ odd.)  \label{prop:fSfNvalues} Let $c \in {{\mathbb F}}_q$. Then
$$\prod \left\{ c-a : a \in {{\mathbb F}}_q,\ \jacobi{a^2-4}q=1\right\} = \begin{cases} 
0 & \text{if $\jacobi{c^2-4}q=1$} \\
\jacobi{c-2} q & \text{if $\jacobi{c^2-4}q=-1$} \\
-1/2 & \text{if $c=2$ } \\
\jacobi{-1}q/2 & \text{if $c=-2$ }
\end{cases}
$$
$$\prod \left\{ c-b : b \in {{\mathbb F}}_q,\ \jacobi{b^2-4}q=-1\right\} = \begin{cases} 
\jacobi{c-2} q & \text{if $\jacobi{c^2-4}q=1$} \\
0 & \text{if $\jacobi{c^2-4}q=-1$} \\
1/2 & \text{if $c=2$ } \\
\jacobi{-1}q/2 & \text{if $c=-2$. }
\end{cases}
$$
\end{proposition}

\begin{proof} We prove the first formula only, as the second is similar. If $q=3$ the product on the left is an empty product, which by convention equals~1.
The expression on the right is 1 for each $c\in \{0,1,2\}={{\mathbb F}}_3$.  Thus, the two sides agree if $q=3$. Now suppose that $q>3$. 
By Theorem~\ref{thm:fijDE}, the left side equals $E_{(q-3)/2}(c)$.
If $\jacobi{c^2-4}q=1$ then the left side vanishes since it contains a factor $(c-c)$. If $\jacobi{c^2-4}q=-1$ then $c \in {{\cal A}}_2^{+-} \sqcup {{\cal A}}_2^{-+}$
and consequently $c = \ang{w^2}$, where $w^{q+1}=\jacobi{c+2}q$ and $w^4\ne 1$, by Theorem~\ref{thm:AijDescription}. Then
\begin{eqnarray*}
E_{(q-3)/2}(c) &=& (w^{q-1}-w^{1-q})/(w^2-w^{-2}) \\
&=&  ( w^{q+1-2} - w^{-(q+1-2)} )/(w^2-w^{-2}) \\
&=& \jacobi{c+2}q (w^{-2}-w^2)/(w^2-w^{-2})=-\jacobi{c+2}q=\jacobi{c-2}q.
\end{eqnarray*}

For any $k$,
$$E_{k-1}(\ang u)=\frac{u^k-u^{-k}}{u-u^{-1}} = u^{1-k} \frac{u^{2k}-1}{u^2-1}.$$
By expanding the right side as $u^{1-k}(1+u^2+u^4 + \cdots u^{2k-2})$ and then evaluating at $u = \pm1$, we obtain that $E_{k-1}(2)=k$
and $E_{k-1}(-2)=(-1)^{k-1}k$.  Applying this with $k-1=(q-3)/2$, 
and observing that $(-1)^k=\jacobi{-1}q$, 
we obtain the formula when $c=\pm2$.
\end{proof}

On summing the two formulas in Proposition~\ref{prop:fSfNvalues}, we obtain the following
corollaries.

\begin{corollary} ($q$ odd.) \label{cor:fSfNvalues} For any $c \in {{\mathbb F}}_q$, 
the equation (\ref{jacc}) holds.
\end{corollary}
\begin{proof} In Proposition~\ref{prop:fSfNvalues}, the sum of the two right-hand sides
is $0+\jacobi{c-2}q$ or $\jacobi{c-2}q+0$ if $c^2-4\ne 0$, $(-1/2)+(1/2)=0$ if $c=2$,
and $\jacobi{-1}q/2+\jacobi{-1}q/2 = \jacobi{-1}q$ if $c=-2$. In each case, this sum
is $\jacobi{c-2}q$. If we shift $c$ by~2, and also shift $a$ and $b$ by 2 in the left-hand sides,
then we obtain the formula~(\ref{jacc}).
\end{proof}

\begin{corollary} \label{cor:fSfNvalues2} If $q=p^n$ is odd,
then $E_{(q-3)/2}(x) + E_{(q-1)/2}(x) \equiv (x-2)^{(q-1)/2} \pmod p$.
\end{corollary}
\begin{proof}  In Proposition~\ref{prop:fSfNvalues}, the sum of the two left sides is
$E_{(q-3)/2}(c)+E_{(q-1)/2}(c)$ by Theorem~\ref{thm:fijDE}, and the sum of the two
right sides  is $(c-2)^{(q-1)/2}$. Thus,
$E_{(q-3)/2}(x)+E_{(q-1)/2}(x)-(x-2)^{(q-1)/2}$ has $q$ roots in ${{\mathbb F}}_q$.
Since its degree is less than $q$, the polynomial must vanish identically in ${{\mathbb F}}_q[x]$.
Since the polynomial has integer coefficients, this is equivalent to vanishing mod~$p$.
\end{proof}

Our next goal is to find 
analogues to the above theorems when $q$ is even. 
Let $q=2^n$. Part~({\it i}) of the following proposition is known (see \cite{chou1,BZ}).

\begin{proposition}   \label{prop:Dqpm1Factor} ($q$ even.) Let ${{\cal T}}_{i}$ be as in~(\ref{TqjDef}) for $i\in\{0,1\}$, and consider
$D_k(x)$ as a polynomial in ${{\mathbb F}}_q[x]$. \\
{\it (i)}\  If $k$ is odd, then $D_k(x) = x f(x)^2$, where $f(x) = \prod_{a \in \delstar k} (x-a)$. \\
{\it (ii)}\ $D_{q+1}(x) = x f_1(x)^2$ and $D_{q-1}(x) = x f_0(x)^2$, where 
$f_i(x) = \prod_{a \in {{\cal T}}_{i} } (x-a)$.
\end{proposition}
\begin{proof} It is well known (or can be easily shown by induction) that if $k$ is odd, then the coefficients
of $D_k(x)$ are zero for even powers of $x$. Thus, $D_k(x) = x f(x)^2$, where $f \in {{\mathbb F}}_2[x]$ and $f$ is monic.
Since $D_k(\delstar k)=\{0\}$, we see that every element of $\delstar k$ is a root of $f$.
Since ${{\rm deg}}(f) = (k-1)/2 = |\delstar k|$, we conclude that $f(x) = \prod_{a\in \delstar k} (x-a)$.
This proves~({\it i}), and ({\it ii}) now follows from~(\ref{Tq01}).
\end{proof}

\begin{theorem} \label{thm:sqrtc} ($q$ even.) Let ${{\cal T}}_{0}$ and ${{\cal T}}_{1}$ be as in (\ref{TqjDef}).
For all $c \in {{\mathbb F}}_q$,
$$\prod_{a \in {{\cal T}}_{0}} (c+a) + \prod_{b \in {{\cal T}}_{1}} (c+b) = c^{1/2}.$$ 
\end{theorem}
\begin{proof}  
By Proposition~\ref{prop:Dqpm1Factor}, $D_{q+1}(x) = x \prod_b (x+b)^2$ and
$D_{q-1}(x) = x \prod_a (x+a)^2$, where $b$ runs through ${{\cal T}}_1$ and $a$ runs through ${{\cal T}}_0$.  
On the other hand, if $c_0\in {{\cal T}}_{0}$ 
and $c_1\in {{\cal T}}_{1}$ then $D_{q+1}(c_0)=c_0^2$ and $D_{q-1}(c_1)=c_1^2$ by Proposition~\ref{prop:evenPermute}.
Thus, $c_0 \prod_b(c_0+b)^2 = c_0^2$ and $c_1 \prod_a(c_1+a)^2=c_1^2$.
It follows that $\prod_b (c_0+b)^2=c_0$, {\it i.e.} $\prod_b (c_0+b) = \sqrt{c_0}$,
and similarly $\prod_a (c_1+a) = \sqrt {c_1}$. 

Let $c\in{{\mathbb F}}_q$. 
Since ${{\mathbb F}}_q = {{\cal T}}_{0} \sqcup {{\cal T}}_{1} \sqcup \{0\}$, it suffices to prove the result in the cases
$c \in {{\cal T}}_{0}$, $c\in {{\cal T}}_{1}$, and $c=0$.

If $c \in {{\cal T}}_{0}$, then $\prod_a (c+a) = 0 $ and $\prod_b (c+b) = c^{1/2}$. 
If $c \in {{\cal T}}_{1}$, then $\prod_a (c+a) = c^{1/2} $ and $\prod_b (c+b) = 0$.
Thus, the theorem holds in those two cases.

Finally, if $c=0$ then we claim that $\prod_a (0+a) = \prod_b (0+b)=1$, so that again the theorem holds.
We have $\prod_a (1/a) = \prod \{v\in {{\mathbb F}}_q^\x : \Tr(v) = 0 \}$. Every such $v$ can be written
in exactly two ways as $r^2+r$, where $r \not \in {{\mathbb F}}_2$, so
$\prod_a (1/a)^2 = \prod_{r \in {{\mathbb F}}_q \setminus {{\mathbb F}}_2 } (r^2+r) = \prod_{r \in{{\mathbb F}}_q\setminus {{\mathbb F}}_2} r(r+1)$.
We break this as $\prod r \x \prod (r+1) = \left(\prod r\right)^2$, where these products are over ${{\mathbb F}}_q \setminus {{\mathbb F}}_2$.
By Wilson's Theorem, this equals $1$. We showed $\prod_a (1/a)^2=1$, therefore $\prod a = 1$. Since
${{\cal T}}_{0}\sqcup {{\cal T}}_{1} = {{\mathbb F}}_q^\x$, we also have $\prod a \prod b = \prod F_q^\x = 1$.
So $\prod b = 1$ as well.
\end{proof}


We close this section with one further remark.  Let $q$ be odd.
Theorem~\ref{thm:fijDE} says that $g^{--}(x)=D_m(x)$ and $g^{++}(x)=E_{m-1}(x)$, where $m=(q-\varep)/4$ and $g^{\pm,\pm}(x)$
is defined by~(\ref{fijDef}). 
Thus, the $j$th elementary symmetric function of the set ${{\cal B}}_2^{--}$ (respectively, ${{\cal B}}_2^{++}$) can be expressed
in terms of a coefficient of $D_m(x)$ (respectively, $E_{m-1}(x)$). The coefficients of $D_k$ and $E_k$
are known in closed form \cite{Lidl}, 
so we obtain an interesting result. Specifically, 
it is shown in \cite[Definitions~2.1 and~2.2]{Lidl} that for any integer $k\ge 1$,
$$D_k(x) = \sum_{i=0}^{\lfloor k/2 \rfloor} \frac k{k-i} \left( {k-i} \atop i \right) (-1)^i x^{k-2i},$$
$$E_k(x) = \sum_{i=0}^{\lfloor k/2 \rfloor} \left( {k-i} \atop i \right) (-1)^i x^{k-2i}.$$
Since $D_k$ has integer coefficients, the  above coefficients are integers.
By Theorem~\ref{thm:fijDE},
$$D_m(x) = \prod_{a \in {{\cal B}}_2^{--}}(x-a) = \sum_{j=0}^m (-1)^j \sigma_j^- x^{m-j},$$
$$E_{m-1}(x) = \prod_{a \in {{\cal B}}_2^{++}}(x-a) = \sum_{j=0}^{m-1} (-1)^j \sigma_j^+ x^{m-j-1},$$
where $\sigma_j^\mu$ denotes the $j$th elementary symmetric function of ${{\cal B}}_2^{\mu,\mu}$,
for $\mu \in \{+,-\}$, { \it i.e.}, the sum of the products of all unordered $j$-tuples of distinct elements in ${{\cal B}}_2^{\mu,\mu}$. 
Note that for both $D_k$ and $E_k$, every other coefficient is zero. This implies that 
$\sigma_j^- = \sigma_j^+ = 0$ if $j$ is odd. When $j=2i$ is even, explicit formulas for
$\sigma_j^-$  are obtained when $j\le m$ (equivalently, when $8i\le q+1$), and also explicit formulas for $\sigma_j^+$ when $j\le m-1$ (equivalently,
when $8i \le q-3$):
\begin{eqnarray} \sigma_{2i}^- &=& \frac{m}{m-i} \left( {m-i} \atop i \right) (-1)^i \qquad \text{if $8i \le q+1$} \label{sigmaMinus}  \\
\sigma_{2i}^+ &=& \left( {m-1-i} \atop i \right) (-1)^i \qquad \text{if $8i \le q-3$.} \label{sigmaPlus}
\end{eqnarray}
In particular, since $m=-\varep/4$ in ${{\mathbb F}}_q$,
$$\sigma_2^- = (-1) \frac m {m-1} \left({m-1} \atop 1 \right) = -m = \varepsilon/4 \qquad\text{if $q \ge 7$} $$
$$\sigma_4^- = \frac m {m-2} \left({m-3} \atop 2 \right) = \frac {m (m-3)} 2 
= \frac{\varepsilon(\varepsilon+12)}{32}\qquad \text{if $q\ge 17$,} $$
$$\sigma_2^+ = -(m-2) = \varepsilon/4 + 2  \qquad \text{if $q\ge 11$,}$$
$$\sigma_4^+ = (m+12)(m+16)/2 = (\varepsilon+12)(\varepsilon+16)/32\qquad 
\text{if $q\ge 19$.}$$

The fact that the odd elementary symmetric functions are zero can be easily explained by the fact that ${{\cal B}}_2^{\mu,\mu}$ is
closed under negation. If $j$ is odd, then
any product of $j$ distinct elements $a_1a_2\cdots a_j$ is canceled by its ``partner'' $(-a_1)(-a_2)\cdots(-a_j)$.

In the example of ${{\mathbb F}}_{29}$ that was given near the end of Section~\ref{sec:refinements}, we have
${{\cal B}}_2^{++} = \{3,7,11,18,22,26\}$, ${{\cal B}}_2^{--} = \{0,10,12,13,16,17,19\}$, and
$$\sigma_2^+ = 3\cdot 7 + 3 \cdot 11 + \cdots + 22 \cdot 26 = 24$$
$$\sigma_4^+ = 3 \cdot 7 \cdot 11 \cdot 18 + \cdots + 11\cdot18\cdot22\cdot26 =6$$
$$\sigma_2^- = 10\cdot 12 + 10 \cdot 13 + \cdots + 17\cdot 19 = 22$$
$$\sigma_4^- = 10 \cdot 12 \cdot 13 \cdot 16 + \cdots + 13\cdot16\cdot17\cdot19 =14.$$
The predicted formulas are $\sigma_2^+=1/4+2=-7+2=-5=24$, $\sigma_4^+=13\cdot 17/32 =6$,
$\sigma_2^-=1/4=-7=22$, and $\sigma_4^-=13/32=14$, in agreement.

A similar analysis applied to the identities
$f_{{\cal S}}(x)=E_{(q-3)/2}(x)$ and $f_{{\cal N}}(x)=E_{(q-1)/2}(x)$ finds closed expressions for
the elementary symmetric functions of ${{\cal S}}_q$ and ${{\cal N}}_q$.  The result is as follows.
Let $q$ be odd and let $\sigma_j({{\cal S}}_q)$, $\sigma_j({{\cal N}}_q)$ denote the $j$-th elementary symmetric
functions on ${{\cal S}}_q$ and ${{\cal N}}_q$, respectively. If $j$ is odd then these are zero. If $j=2i$  then
$$\sigma_{2i}({{\cal S}}_q) = \left( {(q-3)/2 - i} \atop i \right) (-1)^i\qquad \text{if $q \ge 4i+3$},$$
$$\sigma_{2i}({{\cal N}}_q) = \left( {(q-1)/2 - i} \atop i \right) (-1)^i\qquad \text{if $q \ge 4i+1$}.$$
Here, the condition $q \ge 4i+3$ is equivalent to $2i \le (q-3)/2=|{{\cal S}}_q|$ and
the condition $q \ge 4i+1$ is equivalent to $2i \le (q-1)/2=|{{\cal N}}_q|$.


\section{Identities} \label{sec:recursions}

Theorem~\ref{thm:oddq} implies that for $q$ odd and $x \in {{\mathbb F}}_q$: 
\begin{itemize}
\item If $x^2-4$ is a square then $D_k(x)^2-4$ is a square, and if
$x^2-4$ is a non-square then $D_k(x)^2-4$ is a nonsquare or zero;
\end{itemize}
and Theorem~~\ref{thm:Aij} implies:
\begin{itemize}
\item If $x-2$ is a square then so is $D_{2k+1}(x)-2$, and if
$x-2$ is a non-square then $D_{2k+1}(x)-2$ is a nonsquare or zero;
\item If $x+2$ is a square then so is $D_{2k+1}(x)+2$, and if
$x+2$ is a non-square then $D_{2k+1}(x)+2$ is a nonsquare or zero;
\item $D_{2k}(x) + 2$ is always a square.
\item If $x^2-4$ is a square then so is $D_{2k}(x)-2$, and if
$x^2-4$ is a non-square then $D_{2k}(x)-2$ is a nonsquare or zero;
\end{itemize}
Thus, the next theorem should not be a surprise.
\begin{theorem} \label{thm:perfectSquares} (Schur)\ The following are all perfect squares in ${{\mathbb Z}}[x]$:
 $(D_k(x)^2-4)/(x^2-4)$, $(D_{2k+1}(x)-2)/(x-2)$, $(D_{2k+1}(x)+2)/(x+2)$, 
$D_{2k}(x) + 2$, and $(D_{2k}(x)-2)/(x^2-4)$.  In fact, 
\begin{equation} D_{2k}(x) + 2 = D_k(x)^2 \label{Dk2} \end{equation}
\begin{equation} (D_k(x)^2-4)/(x^2-4) = (D_{2k}(x)-2)/(x^2-4)=J_k(x)^2 \label{Jk2} \end{equation}
\begin{equation} (D_{2k+1}(x)-2)/(x-2) = A_k(x)^2, \label{Ak2} \end{equation}
\begin{equation} (D_{2k+1}(x)+2)/(x+2) = B_k(x)^2, \label{Bk2} \end{equation} 
where $J_k$, $A_k$, $B_k$ are sequences in ${{\mathbb Z}}[x]$ satisfying the recursion $F_{k+2}(x)=xF_{k+1}(x)-F_k(x)$ for $k\ge0$ and with initial conditions:
$$J_0(x)=0,\quad J_1(x)=1, \quad A_0(x)=1,\quad A_1(x)=x+1, \quad B_0(x)=1,\quad B_1(x)=x-1.$$ 
\end{theorem}

\noindent {\bf Remark.} These identities are due to Schur \cite{Schur}. (See \cite[Theorem 2.20]{Lidl},
where they are stated in terms of Chebyshev polynomials\footnote{There is a typographical error in Theorem 2.20({\it iv}) of \cite{Lidl}.
Namely, the quantity $E_{2n+1}^*(x,a)$ on the right-hand side should instead be $E_{n+1}^*(x,a)$.}.)
Note that the formula $D_{2k}(x)+2=D_k(x)^2$ could be deduced by setting $k=\ell$ in 
equation~(\ref{DkDl}), or from the formula $D_{2k}=D_2 \circ D_k$. If $k\ge1$, then $J_k(x) = E_{k-1}(x)$.
\medskip


\begin{proof} 
We use Fibonacci-like arguments.   Recall that $D_k(x)$ satisfies the recursion 
$D_{k+2}(x)=xD_k(x)-D_{k-1}(x)$.  Let $\alpha,\beta$ denote the roots of $T^2-xT+1=0$ in
the algebraic closure of ${{\mathbb Q}}(x)$ (where $x$ is transcendental over ${{\mathbb Q}}$); 
so $\alpha+\beta=x$ and $\alpha\beta=1$. Let ${\cal S}$ denote
all sequences $F_0,F_1,F_2,\ldots$ in ${{\mathbb Q}}(\alpha)$ that satisfy $F_{k+2}(x)=xF_k(x)-F_{k-1}(x)$.
The set of such sequences form a 2-dimensional vector space over ${{\mathbb Q}}(\alpha)$, and one basis is
$\{\alpha^k\}_{k=0}^\infty$, $\{\beta^{k}\}_{k=0}^\infty$.
Let ${{\cal T}}$ denote the set of sequences spanned by $\{\alpha^{2k}\}_{k=0}^\infty$, $\{\beta^{2k}\}_{k=0}^\infty$, and $\{1\}_{k=0}^\infty$.
If $\{A_k\}$ and $\{B_k\}$ are in ${{\cal S}}$, then $\{A_k B_k\}$ and $\{A_{2k}\}$ are in ${{\cal T}}$.
In particular, the left and right sides of each identity listed above is in ${{\cal T}}$.
For example, the expression
\begin{eqnarray*} \frac{D_{2k+1}-2}{x-2} &=& \frac{\a^{2k+1}+\beta^{2k+1}-2}{\alpha+\alpha^{-1} -2}  \\
&=& \left(\frac \a {\a + \a^{-1}-2}\right) \a^{2k} +
\left(\frac {\a^{-1}} {\a + \a^{-1}-2}\right) \b^{2k} +
\left(\frac{-2} {\a + \a^{-1}-2}\right) 1 
\end{eqnarray*}
shows that $\{(D_{2k+1}-2)/(x-2)\}_{k=1}^\infty \in {{\cal T}}$.
We claim that elements of ${\cal T}$ are completely determined by their first three terms. This is 
seen by noting that $(Y-1)(Y-\alpha^2)(Y-\alpha^{-2})=(Y-1)(Y^2-(x^2-2)Y+1) 
= Y^3-(x^2-1)Y^2+(x^2-1)Y-1$,
therefore each basis element of ${\cal T}$ satisfies the recursion
\begin{equation} T_{k+3} = (x^2-1) T_{k+2} -(x^2-1) T_{k+1} + T_k. \label{Trecursion} \end{equation}
By linearity, each element of ${\cal T}$ satisfies this recursion, which proves the claim that the first 
three terms determine the entire sequence. In particular, if two sequences both belong to ${\cal T}$ 
and agree in their
first three terms, then they are identical. Thus, we can verify each identity given above by
simply checking they are true for $k=0$, $k=1$, and $k=2$.
\end{proof}

\section{Chebyshev polynomials} \label{sec:Chebyshev} 

As is well known, Dickson polynomials are closely related to Chebyshev polynomials.
The Chebyshev polynomials of the first kind, denoted $T_k(x)$, and Chebyshev polynomials of
the second kind, denoted $U_k(x)$,  belong to ${{\mathbb Z}}[x]$ and are given by the recursions:
\begin{eqnarray*} 
T_0(x)=1,&& T_1(x)=x,\qquad \,T_{k+2}(x) = 2x T_{k+1}(x) - T_k(x), \\
U_0(x)=1,&& U_1(x)=2x,\qquad \!\!U_{k+2}(x) = 2x U_{k+1}(x) - U_k(x). 
\end{eqnarray*}
These are related to Dickson polynomials of the first and second kind by the formulas
\begin{equation} D_k(2x)=2T_k(x),\qquad E_k(2x)=U_k(x). \label{DTEU} \end{equation}
Recall that the Dickson polynomials satisfy the functional equations
$$D_k(u+1/u) = u^k + 1/u^k,\qquad E_k(u+1/u) = \frac{u^{k+1}-1/u^{k+1}}{u-1/u},$$
where $k\ge 0$ and $u$ is an indeterminate. 
If we set $u=e^{i\theta}$, then $u+1/u=2\cos\theta$ and $u-1/u=2\sin\theta$.
Thus, the functional equations may be written as $D_k(2\cos\theta) = 2 \cos(k\theta)$ and $E_k(2\cos\theta) = \sin((k+1)\theta)/\sin\theta$.
This explains the famous functional equations for the Chebyshev polynomials that aid with trig substitutions 
in calculus:
$$T_k(\cos\theta) = \cos(k\theta),\qquad U_k(\cos\theta) \sin\theta = \sin((k+1)\theta).$$

Note that $D_k(x)$ and $E_k(x)$ are monic polynomials when $k\ge1$; whereas $T_k(x)$ has leading term $2^{k-1}x^k$
and $U_k(x)$ has leading term $2^kx^k$. Also, the Dickson polynomials have a characteristic~2 theory, while the Chebyshev
polynomials do not.   In that sense, the Dickson polynomials are more ``natural'' than the Chebyshev polynomials.
On the other hand, Chebyshev polynomials predate Dickson polynomials by about 40 years, they
have a wide range of applications, and thousands of articles have been written about them.
In this section, we restate theorems about Dickson polynomials in terms of their more famous cousin, the Chebyshev polynomials.

In odd characteristic, the formula (\ref{DTEU}) shows that $D_k$ and $T_k$ are conjugate: if $M_2$ denotes
the multiplication-by-2 map, then $T_k=M_2^{-1} \circ D_k \circ M_2$ and $U_k = E_k \circ M_2$.  
Thus, the theories of Dickson and Chebyshev polynomials are nearly identical in odd characteristic.



\begin{theorem} \label{thm:ChebyshevRefinements} ($q$ odd.) Let $\varep = \jacobi{-1}q$ and $\nu=\jacobi2q$, and let
${{\cal A}}_\lambda^{\varep_1,\varep_2}$ be as in (\ref{Aij}).
For any $k\ge 1$, $T_k(1)=1$, $T_k(-1)=(-1)^k$, and
\begin{enumerate}
\item[({\it i})] $T_k({{\cal A}}_1^{\nu,\nu}) \subset {{\cal A}}_1^{\nu,\nu} \sqcup \{1,-\varep\}$ and 
$T_k({{\cal A}}_1^{-\nu,\nu}) \subset {{\cal A}}_1^{-\nu,\nu}\sqcup \{1,\varep\}$.
\item[({\it ii})] If $k$ is odd then $T_k({{\cal A}}_1^{\varep\nu,-\nu}) \subset {{\cal A}}_1^{\varep\nu,-\nu}\sqcup \{-1\}$
and $T_k({{\cal A}}_1^{-\varep\nu,-\nu}) \subset {{\cal A}}_1^{-\varep\nu,-\nu}$.
\item[({\it iii})] If $k$ is even then $T_k({{\cal A}}_1^{-\nu,-\nu}) \subset {{\cal A}}_1^{\nu,\nu}\sqcup \{1,-\varep\}$
and $T_k({{\cal A}}_1^{\nu,-\nu}) \subset {{\cal A}}_1^{-\nu,\nu} \sqcup \{1,\varep\}$.
\item[({\it iv})] If $(q-1)/2$ divides $k$, then 
$$T_k({{\mathbb F}}_q) \subset {{\cal A}}_1^{+-} \sqcup {{\cal A}}_1^{-+} \sqcup \{1,-1\}
= \left\{a \in {{\mathbb F}}_q : \text{$a^2-1$ is a nonsquare}\right\} \sqcup \{1,-1\}.$$ 
If in addition $k$ is even,
then $T_k({{\mathbb F}}_q)\subset {{\cal A}}_1^{-\nu,\nu} \sqcup \{1,-1\}$.
\item[({\it v})] If $(q+1)/2$ divides $k$, then 
$$T_k({{\mathbb F}}_q)\subset {{\cal A}}_1^{++} \sqcup {{\cal A}}_1^{--} \sqcup \{1,-1\}
= \left\{a \in {{\mathbb F}}_q : \text{$a^2-1$ is a square}\right\}.$$ 
If in addition $k$ is even, then
$T_k({{\mathbb F}}_q) \subset {{\cal A}}_1^{\nu,\nu} \sqcup \{1,-1\}$.
\item[({\it vi})] If ${{\cal A}}_1^{\varep_1,\varep_2}$ is nonempty, then $T_k$ permutes ${{\cal A}}_1^{\varep_1,\varep_2}$ iff GCD$(k,d^{\nu\varep_1,\nu\varep_2})
= 1$, where $d^{++} = (q-1)/2$, $d^{+-}=q+1$, $d^{-+}=(q+1)/2$, $d^{--} = q-1$.
\end{enumerate}
\end{theorem}
\begin{proof}
Recall that $T_k(x)=(1/2)D_k(2x)$.  Then
$D_k(a)=a'$ iff $T_k(a/2) = a'/2$. Since $D_k$ respects the sets ${{\cal A}}_2^{\varepsilon_1,\varepsilon_2}$,
we see that $T_k$ respects the sets $\left\{a/2 : a \in {{\cal A}}_2^{\varepsilon_1,\varepsilon_2}\right\}$.
Note that
\begin{eqnarray*}
\left\{a/2 : a \in {{\cal A}}_2^{\varepsilon_1,\varepsilon_2} \right\} &=& \left\{ b \in {{\mathbb F}}_q : \jacobi{2b-2}q=\varepsilon_1,\ 
\jacobi{2b+2}q= \varepsilon_2 \right\} \\
&=& \left\{ b \in {{\mathbb F}}_q : \jacobi{b-1}q=\varepsilon_1 \jacobi 2q,\  \jacobi{b+1}q=\varepsilon_2 \jacobi 2q \right\} \\
&=& {{\cal A}}_1^{\nu\varep_1,\nu\varep_2}.
\end{eqnarray*}
Using these observations, Theorem~\ref{thm:ChebyshevRefinements} follows immediately from Theorem~\ref{thm:Aij}.
\end{proof}

\begin{theorem} ($q$ odd.) ({\it i}) If $(k,q^2-1)=1$, so that $D_k$ and $T_k$ permute ${{\mathbb F}}_q$, then the permutations of ${{\mathbb F}}_q$ that are induced by $D_k$ and $T_k$ 
are conjugate in the symmetric group on ${{\mathbb F}}_q$ and therefore have the same cycle structure. \\
({\it ii}) Let $\varep_1,\varep_2 \in \{1,-1\}$ and $\nu = \jacobi 2q$. If $(k,d^{\varep_1,\varep_2}) = 1$, so that $D_k$ permutes ${{\cal A}}_2^{\varep_1,\varep_2}$ and
$T_k$ permutes ${{\cal A}}_1^{\nu\varep_1,\nu\varep_2}$, then the cycle structures of these two permutations are the same.
\end{theorem}
\begin{proof} We observed in the paragraph preceding Theorem~\ref{thm:ChebyshevRefinements} that $T_k=M_2^{-1}\circ D_k \circ M_2$, where $M_2$ is the multiplication-by-2 map;
{ \it i.e.}, $T_k$ takes $a$ to $b$ iff $D_k$ takes $2a$ to $2b$. Thus, in the case that they are permutations,
a cycle $(a_1,a_2,\ldots,a_r)$ of $T_k$ corresponds to a cycle $(2a_1,2a_2,\ldots,2a_r)$ of $D_k$. This establishes ({\it i}). Noting that
$a\in{{\cal A}}_1^{\nu\varep_1,\nu\varep_2} \iff 2a \in {{\cal A}}_2^{\varep_1,\varep_2}$, the above observation also implies that ({\it ii}) holds.
\end{proof}

\begin{theorem} \label{thm:gijTU} ($q$ odd.)  Let $\varep=\jacobi{-1}q$, $\nu=\jacobi2q$, and ${{\cal B}}_\lambda^{\varep_1,\varep_2}$ as in~(\ref{BDef}). 
Let $m=(q-\varep)/4$, which is an integer.  In ${{\mathbb F}}_q[x]$, the following holds. 
{} 

\medskip
\noindent
({\it i})\quad $T_m(x) = 2^{m-1} \prod\left\{x-b : b \in {{\cal B}}_1^{-\nu,-\nu}\right\}$ and $U_{m-1}(x) = 2^{m-1}\prod \left\{ x-b : b \in {{\cal B}}_1^{\nu,\nu} \right\}$.
({\it ii})\quad $U_{(q-3)/2}(x) = 2^{(q-3)/2} \prod \left\{ x - b : \jacobi{b^2-1}q = 1 \right \}$ and \\
$U_{(q-1)/2} = 2^{(q-1)2} \prod \left\{ x - b : \jacobi{b^2-1}q = -1 \right\}$.
\end{theorem}
\begin{proof} 
Since $T_k(x)=(1/2)D_k(2x)$ and $D_k$ is monic of degree~$k$, we see that $T_k$ has leading term $2^{k-1}x^k$, and if $D_k(x) = \prod_{b\in B} (x-b)$ then
$T_k(x) = 2^{k-1} \prod_{b \in B} (x-b/2)$.
Likewise, since $U_k(x)=E_k(2x)$ and $E_k$ is monic of degree~$k$, we see that $E_k$ has leading term $2^kx^k$ and if $E_k(x) = \prod_{b\in B'}(x-b)$ then
$U_k(x)=2^k \prod_{b\in B'}(x-b/2)$.
By Theorem~\ref{thm:fijDE}({\it iv}), $D_m(x) = \prod \{x-b : b \in {{\cal B}}_2^{--}\}$ and $E_{m-1}(x) = \prod \{x-b : b \in {{\cal B}}_2^{++} \}$.
Thus, $T_m(x)= 2^{m-1} \prod \{x-b : b \in (1/2) {{\cal B}}_2^{--} \}$ and $U_{m-1}(x) = 2^{m-1} \prod \{ x-b : b \in (1/2){{\cal B}}_2^{++} \}$.
Since $(1/2){{\cal B}}_2^{\varep_1,\varep_2}={{\cal B}}_1^{\nu\varep_1,\nu\varep_2}$, ({\it i}) follows.
By Theorem~\ref{thm:fijDE}({\it iii}), $E_{(q-3)/2}(x) = \prod\{x-b : b \in {{\cal S}}_q \}$ and $E_{(q-1)/2}(x) = \prod \{x-b : b \in {{\cal N}}_q\}$,
where ${{\cal S}}_q$ and ${{\cal N}}_q$ are defined by (\ref{ZSN}). Then $U_{(q-3)/2}=2^{(q-3)/2} \prod\{x-b : b \in (1/2){{\cal S}}_q \}$ and
$U_{(q-1)/2} = 2^{(q-1)/2}\prod \{x-b : b \in (1/2) {{\cal N}}_q \}$. Now 
$$(1/2){{\cal S}}_q = \left\{ a/2\in{{\mathbb F}}_q : \jacobi{a^2-4}q=1 \right\} = \left\{b\in{{\mathbb F}}_q : \jacobi{b^2-1}q=1 \right\}$$
and similarly $(1/2){{\cal N}}_q = \left\{b\in{{\mathbb F}}_q : \jacobi{b^2-1}q=-1\right\}$.  Part~({\it ii}) follows.
\end{proof}

\begin{proposition} If $q=p^n$ is odd, then $$U_{(q-1)/2}(x) + U_{(q-3)/2}(x) = \jacobi 2 q (x-1)^{(q-1)/2} \pmod p.$$
\end{proposition}
\begin{proof} By Corollary~\ref{cor:fSfNvalues2}, $E_{(q-1)/2}(x) + E_{(q-3)/2}(x) = (x-2)^{(q-1)/2}$.  Since $U_k(x)=E_k(2x)$,
\begin{equation*} U_{(q-1)/2}(x) + U_{(q-3)/2}(x) = (2x-2)^{(q-1)/2} = \jacobi 2q (x-1)^{(q-1)/2}.  \end{equation*}
\end{proof}

\section{Conclusions} \label{sec:conclusions}

A common theme in the study of finite fields is to describe a set
in multiple ways.  A simple example is $\{a \in {{\mathbb F}}_q^\x : a^k = 1 \} = \{ a^g : a \in {{\mathbb F}}_q^\x \}$, where $g = (q-1)/{{\rm GCD}}(q-1,k)$.
Two other examples are known as Hilbert's Theorem~90:
\begin{eqnarray}
\{ a \in {{\mathbb F}}_{q^e} : \Tr_{{{\mathbb F}}_{q^e}/{{\mathbb F}}_q}(a)=0 \} &=& \{ b - b^q : b \in {{\mathbb F}}_{q^e} \},\\
 \{a\in{{\mathbb F}}_{q^e}^\x : {{\rm N}}_{{{\mathbb F}}_{q^e}/{{\mathbb F}}_q}(a)=1 \} &=& \{ b^{q-1} : b \in {{\mathbb F}}_{q^e}^\x \}. \label{Hilbert90} 
\end{eqnarray}
Another example (due to Dillon and Dobbertin \cite{DD}) is $\delstar{q-1} = {{\cal T}}_{0}$ and $\delstar{q+1} = {{\cal T}}_{1}$ when $q=2^n$, where we recall $\del d = \{ a + 1/a : a^d = 1 \}$
and $\delstar d = \del d \setminus \{2,-2\}$ when $(d,q)=1$.
We note that if $q=2^n$ and $1\ne r\in \mu_{q-1}$ then
$$\frac 1 {r + 1/r} = \frac r {r^2+1} = \frac{ (r+1)+1 }{(r+1)^2} = \frac 1{r+1} + \frac 1{(r+1)^2};$$
this gives another way to see that $\Tr(1/y)=0$ when $0\ne y \in \del{q-1}$.

In similar vein, Brewer showed that
$\del{q-1} = \{2,-2\} \sqcup {{\cal S}}_q$ and $\del{q+1} = \{2,-2\} \sqcup {{\cal N}}_q$ when $q$ is odd, where
${{\cal S}}_q$ and ${{\cal N}}_q$ are defined by (\ref{ZSN}).
We showed in Theorem~\ref{thm:AijDescription} that
$$\delstar{(q-1)/2} = \left\{ a \in {{\mathbb F}}_q : \jacobi{a-2}q = \jacobi{a+2}q = 1 \right\}$$
$$\delstar{(q+1)/2} = \left\{ a \in {{\mathbb F}}_q : \jacobi{a-2}q = -1, \jacobi{a+2}q = 1 \right\}$$
$$\delstar{(q+1)} \setminus \delstar{(q+1)/2}
= \left\{ a \in {{\mathbb F}}_q : \jacobi{a-2}q = 1, \jacobi{a+2}q = -1 \right\} $$
$$\delstar{(q-1)} \setminus \delstar{(q-1)/2}
= \left\{ a \in {{\mathbb F}}_q : \jacobi{a-2}q = \jacobi{a+2}q = -1 \right\}.$$ 
The above four  sets are denoted by ${{\cal A}}_2^{++}$, ${{\cal A}}_2^{-+}$, ${{\cal A}}_2^{+-}$, and ${{\cal A}}_2^{--}$, respectively.

Since the Dickson polynomial of the first kind satisfies $D_k(u+1/u)=u^k + 1/u^k$, it maps $\del d$ to $\del {d/g}$, where $g = {{\rm GCD}}(d,k)$. Because of
this, these polynomials respect the above sets in structured ways.  For example, $D_k$ always maps
$\{ a \in {{\mathbb F}}_q : \text{$a+2$ and $a-2$ are squares} \}$ to itself, and $D_k$ permutes that set iff GCD$(k,q-1)=1$. 
See Theorems~\ref{thm:oddq} and \ref{thm:Aij}. 
Our results about Dickson polynomials translate easily into new results about Chebyshev polynomials; see Section~\ref{sec:Chebyshev}.

Another result of this article is that
\begin{eqnarray*} D_m(x) &=& \prod\left \{ x - b : \jacobi{2-b}q=\jacobi{2+b}q = -1 \right\}\\
E_{m-1}(x) &=& \prod\left \{ x - b : \jacobi{2-b}q=\jacobi{2+b}q = 1 \right\},
\end{eqnarray*}
where $m= \lfloor (q+1)/4  \rfloor$.
By evaluating the first identity at $x=2$ and $x=-2$, we obtain
the ``Wilson-like theorems'' that were presented  in Section~\ref{sec:wilson-like}.
Many more formulas of this type are proved in the sequel to this article, \cite{wilson-like}.
Also, since closed-form expressions are known for the coefficients of $D_m(x)$ and $E_{m-1}(x)$, the above equations
yield explicit formulas for $\sigma_j^+$ and $\sigma_j^-$, where $\sigma_j^\mu$ is $j$th elementary symmetric function of
$\left\{ b \in {{\mathbb F}}_q : \jacobi{2-b}q=\jacobi{2+b}q = \mu \right\}$.
See the discussion
at the end of Section~\ref{sec:numberTheory}.

Finally, we found some curious identities such as (\ref{jacc}), (\ref{sqrtc}), and
Corollary~\ref{cor:fSfNvalues2}.

\section{Alternate proofs}  \label{sec:oneline}

Some results of this article are proved using Dickson polynomials, but may be stated without them.
One can ask whether there is an alternate proof that uses cleverness instead of Dickson polynomials.
Here we give three such examples that were communicated to the author.

\subsection{Richard Stong.} 

We showed in this
article that if $q$ is an odd prime power, then 
$$\prod\left\{a\in{{\mathbb F}}_q^\x : \text{$a$ and $4-a$ are nonsquares} \right\}=2.$$  
The following ``one-line proof'' was proffered by Richard Stong:

Start with the product in question {\it except} that it runs over the residues:
\begin{equation*} Q = \prod\left\{ b\in{{\mathbb F}}_q^\x : \jacobi bq = \jacobi {4-b}q = 1 \right\}. \end{equation*}
Write $b=x^2=4-y^2$, where $x,y\in {{\mathbb F}}_q^\x$. Note that $x,y\ne0$ implies $x \not\in \{0,2,-2\}$
and $y \not\in\{0,2,-2\}$. Let $R$ denote a complete set of representatives for $({{\mathbb F}}_q\setminus\{0,2,-2\})/\{\pm1\}$.
\begin{eqnarray*} Q &=& \prod\left\{ 4-y^2 : y\in R, \jacobi{4-y^2}q=1 \right\}\\
&=&  \prod\left\{ (2-y)(2+y) : y \in R, \jacobi{2-y}q=\jacobi{2+y}q \right\} \\
&=& \prod \left\{ 2-z : z \in {{\mathbb F}}_q \setminus \{0,2,-2\}, \jacobi{2-z}q=\jacobi{2+z}q \right\} \\
&=& \prod \left\{ c : c \in {{\mathbb F}}_q\setminus\{2,0,4\},\jacobi cq = \jacobi{4-c}q \right\} \\
&=& (1/2) \prod \left\{ c : c \in {{\mathbb F}}_q^\x,\ \jacobi cq = \jacobi{4-c}q \right\} \\
&=& (1/2) Q N,
\end{eqnarray*}
where $Q$ is the product over $c$ that are squares and $N$ is the product over $c$ that are nonsquares.
So $Q=(1/2)QN$, and $N=2$. Interestingly, this does not solve for $Q$.  It is shown
in \cite{wilson-like} that $Q=-\jacobi{-1}q/4$.

\subsection{A generalization.}
For $j,\ell\in{{\mathbb F}}_q$ such that $j+\ell\ne 0$ and for $\varep_1,\varep_2\in\{1,-1\}$, let
$${{\cal T}}_{j,\ell}^{\varep_1,\varep_2} = \left\{ a \in {{\mathbb F}}_q^\x : \text{$\jacobi{j-a}q=\varep_1$ and 
$\jacobi{\ell+a}q = \varep_2$} \right\}.$$
In the sequel to this article, \cite{wilson-like}, we compute closed formulas for 
$\prod{{\cal T}}_{j,\ell}^{\varep_1,\varep_2}$
for all $j,\ell,\varep_1,\varep_2$.  In particular, our results when $\ell=0$ are the following. First, as noted
in this article, we have $\prod {{\cal T}}_{4,0}^{--}=2$. By \cite[Section~3]{wilson-like},
$$\prod {{\cal T}}_{4,0}^{++} =  -\varep/4,\qquad \prod{{\cal T}}_{4,0}^{+-} = \varep/2,\qquad \prod{{\cal T}}_{4,0}^{-+}=1,$$
where as usual $\varep=\jacobi{-1}q$.
By \cite[Section~5]{wilson-like}, if $\lambda \in {{\mathbb F}}_q^\x$ and $\nu = \jacobi{\lambda}q$, then
$$\prod{{\cal T}}_{4\lambda,0}^{\varep_1,\varep_2} = \lambda^{m-\gamma} \prod{{\cal T}}_{4,0}^{\nu\varep_1,\nu\varep_2},$$
where $m=(q-\varep)/4$ and
$$\gamma=\begin{cases} 1  &\text{if $\nu=\varep\varep_1=\varep_2$ or $-\varep=\nu\varep_1=1$}\\ 0 & \text{otherwise.} \end{cases}$$
If we set $A=4\lambda$ and note that $4^m=2^{(q-\varep)/2} = \jacobi2q 2^{(1-\varep)/2}$, then the above formula
may also be written as
$$\prod {{\cal T}}_{A,0}^{\varep_1,\varep_2} = \jacobi 2q A^{m-\gamma} 4^\gamma 2^{(\varep-1)/2} 
\prod{{\cal T}}_{4,0}^{\nu\varep_1,\nu\varep_2}.$$
Let $\mu \in \{1,-1\}$ and suppose $\varep_1=\varep_2=\mu$. Then $\gamma=1$ iff $\nu=\mu$, so 
$4^\gamma \prod{{\cal T}}_{4,0}^{\nu\mu,\nu\mu}=-\varep$ if $\nu=\mu$, or $2 $ if $\nu=-\mu$. Thus,
\begin{eqnarray}
\prod {{\cal T}}_{A,0}^{\mu,\mu} &=& \jacobi 2q A^{m-\gamma} 4^\gamma 2^{(\varep-1)/2} 
\prod{{\cal T}}_{4,0}^{\nu\mu,\nu\mu} \label{TA0} \nonumber \\
&=& \begin{cases} -\varep\jacobi{2}q A^{m-1} 2^{(\varep-1)/2} & \text{if $\mu=\nu$} \\
\jacobi{2}q A^m 2^{(\varep+1)/2 }  & \text{if $\mu=-\nu$.}  \end{cases}
\end{eqnarray}

\subsection{Bradley Brock.}
Bradley Brock found a ``one-line proof'' for the formula (\ref{TA0}) in the special case where $\mu=\varep\nu$.
In that case, $\nu\mu=\varep$, and (\ref{TA0}) becomes:
\begin{eqnarray*} \prod{{\cal T}}_{A,0}^{\varep\nu,\varep\nu} 
&=& \begin{cases} -\jacobi{2}q A^{m-1} & \text{if $\varep=1$} \\
\jacobi{2}q A^m & \text{if $\varep=-1$} \end{cases}  \\
&=& - \jacobi{-2}q A^{m-(\varep+1)/2}.
\end{eqnarray*}

Brock notes that $b \in {{\cal T}}_{A,0}^{\varep\nu,\varep\nu} $ iff $ A^2/b \in {{\cal T}}_{A,0}^{\varep\nu,\varep\nu}$. This can be seen
as follows. We are assuming $\jacobi b q = \jacobi{A-b}q = \mu = \varep\nu$. Then $\jacobi{A^2/b}q=\mu$.
Since $A-A^2/b =-A(A-b)/b$, $\jacobi{A-A^2/b}q=\varep\nu\mu\mu=\varep\nu=\mu$.   This proves the claim.
Each pair $b, A^2/b$ multiplies together to produce $A^2$, unless $b=A^2/b$.
Now $b=A^2/b$ iff $b= \pm A$. Here $b=A$ is impossible because $\jacobi{A-b}q=\mu$ and $\jacobi{A-A}q=0$. On the other hand, $b=-A$ could hold iff 
$-A \in {{\cal T}}_{A,0}^{\varep\nu,\varep\nu}$ iff
$\jacobi{-A}q=\jacobi{2A}q=\varep\nu$ iff $\varep\nu=\jacobi2q\nu$ iff $\jacobi2q=\varep$ iff $\jacobi{-2}q=1$.
Let $t = |{{\cal T}}_{A,0}^{\varep\nu,\varep\nu}|$. By multiplying together all pairs $b,A^2/b$ in ${{\cal T}}_{A,0}^{\varep\nu,\varep\nu}$
with $-A$ left over iff $\jacobi{-2}q=1$, we obtain that 
\begin{eqnarray*}
\prod {{\cal T}}_{A,0}^{\varep\nu,\varep\nu} &=& \begin{cases} (A^2)^{t/2} & \text{if $\jacobi{-2}q=-1$} \\
(A^2)^{(t-1)/2}(-A) & \text{if $\jacobi{-2}q=1$}  \end{cases} \\
&=& -\jacobi{-2}q A^t.
\end{eqnarray*}

Finally, one observes that $t=(q-5)/4$ if $\varep=1$, and  $t=(q+1)/4$ if $\varep=-1$.  This could be derived from
Theorem~\ref{thm:AijDescription} by noting
that $b\in{{\cal T}}_{A,0}^{\varep\nu,\varep\nu}$ iff $c \in {{\cal A}}_2^{+,\varep}$, where $c=4b/A-2$.
Brock proves the formula for $t$ in a different way. Let ${{\cal C}}$ be the conic $x^2+y^2=-A^2$.
As a projective curve of genus~0, it is well known that $|{{\cal C}}({{\mathbb F}}_q)|=q+1$. Brock notes that $(x,y)\mapsto -x^2/A$ is a 4-to-1 map from 
${{\cal C}}\setminus S$ onto ${{\cal T}}_{A,0}^{\nu\varep,\nu\varep}$,
where $S$ consists of the points where $x$ or $y$ is $0$ or $\infty$. If $\varep=1$ then $-1$ is a square,
so there are two points at $\infty$, two points with $x=0$, and two points with $y=0$. Thus, $|S|=6$ and $t=(q+1-6)/4=(q-5)/4
=m-1$.
If $\varep=-1$, then $-1$ is a nonsquare, so $S=\emptyset$ and $t=(q+1)/4=m$. In either case, $t=m-(\varep+1)/2$.

\subsection{John Dillon.}
We conclude with a ``one-line proof'' by John Dillon of the formula~(\ref{sqrtc}). Let $q=2^n$, and let ${{\cal T}}_j=
\{a\in{{\mathbb F}}_q^\x: \Tr(1/a) = j \}$. Let $T_j(x) = \prod\{(x-a) : a \in {{\cal T}}_j \}$. We are to show that $T_0(c)+T_1(c)=c^{1/2}$
for all $c\in{{\mathbb F}}_q$.  It suffices to show that $T_0(x)+T_1(x)=x^{q/2}$. Define
$$S_0(x)=\Tr(x) = x + x^2 + x^4 + \cdots x^{q/2},\qquad S_1(x) = S_0(x)+1.$$
Let $S_0^*(x)=S_0(x)/x$.
Note that $S_0^*(x)=0$ iff $x\in{{\mathbb F}}_q^\x$ and $\Tr(x)=0$, and $S_1(x)=0$ iff $x\in{{\mathbb F}}_q^\x$ and Tr$(x)=1$.  Thus,
$T_0(x)=\widetilde{S_0^*}(x)$ and $T_1(x)=\widetilde{S_1}(x)$, where $\widetilde f$ denotes the reverse of~$f$: 
$$\widetilde f(x) = x^{{{\rm deg}}(f)}f(1/x).$$ 
We have
\begin{eqnarray*}
T_0(x) + T_1(x) &=& x^{(q/2)-1} S_0^*(1/x) + x^{q/2} S_1(1/x) \\
&=& x^{(q/2)-1} S_0^*(1/x) + x^{q/2} (1 + S_0(1/x) ) \\
&=& x^{(q/2)-1} S_0^*(1/x) + x^{q/2} (1 + (1/x) S_0^*(1/x) ) \\
&=& x^{q/2}.
\end{eqnarray*}


\section{Acknowledgments}
The author thanks John Dillon for reviewing this article and providing valuable comments. 



