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

Topological complexity is a numerical homotopy invariant, introduced by Farber in the course of his topological study of the robot motion planning problem \cite{Far03, Far06}. For any space $X$, the number ${\sf TC}(X)$ is defined to be the sectional category of the free path fibration on $X$, and as such gives a quantitative measure of the complexity of navigation in $X$. Computation of ${\sf TC}(X)$ for a given space $X$ can be delicate, but is often achievable by combining cohomological lower bounds (in terms of the zero-divisors cup-length \cite[Theorem 7]{Far03}) with upper bounds coming from obstruction theory or the specific geometry of the space at hand.

A class of spaces for which the computation of topological complexity presents a unique challenge are the Eilenberg--Mac Lane spaces $K(\pi,1)$, for $\pi$ a torsion-free discrete group. A description of ${\sf TC}(\pi)\coloneqq {\sf TC}(K(\pi,1))$ in terms of algebraic properties of the group $\pi$ (as requested by Farber in \cite{Far06}) seems to be out of reach at present. In certain cases one can often compute the exact value of ${\sf TC}(\pi)$ using the bounds mentioned above. There are standard bounds ${\sf cd}(\pi)\leq {\sf TC}(\pi)\leq 2\, {\sf cd}(\pi)$ in terms of the cohomological dimension of $\pi$. There are also sharper bounds in terms of cohomological dimensions of certain subgroups or quotient groups of $\pi\times \pi$ (see \cite[Theorem 1.1]{GLO} and \cite[Proposition 3.7]{G}, reproduced as Theorems \ref{thm:lowerbound} and \ref{thm:upperbound} below) which can be of use when the cohomological or obstruction-theoretic bounds are either insufficient, or computationally infeasible.

In this paper we investigate the topological complexity of certain subgroups of Artin's braid groups. Recall that the full braid group $B_n$, the pure braid group $P_n$ and the symmetric group $\mathfrak{S}_n$ fit into an extension
\[
\xymatrix{
1 \ar[r] & P_n \ar[r] & B_n \ar[r]^-{\pi} & \mathfrak{S}_n \ar[r] & 1}
\]
where the projection $\pi$ sends a braid to the associated permutation of its endpoints (definitions will be given in Section \ref{Braidgroups} below). Given any subgroup $G\le \mathfrak{S}_n$, its pre-image $B_n^G\coloneqq\pi^{-1}(G)$ is a subgroup of $B_n$ containing $P_n$. The cohomological dimension of $B_n^G$ is $n-1$, and so by the standard bounds mentioned above we have $n-1\le {\sf TC}(B_n^G)\le 2n-2$. We will prove the following.

\begin{thm}\label{thm:introupper}
Suppose that $G\leq \mathfrak{S}_n$ satisfies either of the following conditions:
\begin{itemize}
\item $G\leq\mathfrak{S}_{n-k}\times \mathfrak{S}_k$ where $(n,k)=(n-1,k)=(n-1,k-1)=1$, or
\item $G\leq \mathfrak{S}_{n-2}\times \{1\}^2$.
\end{itemize}
Then we have
\[
{\sf TC}(B_n^G)\leq 2n-3.
\]
\end{thm}

\begin{thm}\label{thm:introlower}
Let $G\le \mathfrak{S}_{n-k}\times \mathfrak{S}_k$ for $k\ge2$. Then \[{\sf TC}(B_n^G)\ge 2n-k-1.\]

Furthermore, if $G\le \mathfrak{S}_{n-1}\times \{1\}$, then \[{\sf TC}(B_n^G)\ge 2n-3.\]
\end{thm}

\begin{cor}\label{exact}
If $G\leq \mathfrak{S}_{n-2}\times \{1\}^2$, then
\[
{\sf TC}(B_n^G)=2n-3.
\]
\end{cor}

These results extend the computation of the topological complexity of pure braid groups (due to Farber and Yuzvinsky \cite{FY}) to various \emph{mixed} or \emph{coloured braid groups}. Our methods are somewhat different (in particular we use \cite[Theorem 1.1]{GLO} instead of zero-divisors cup-length).

The above results generalise to the setting of higher topological complexity. The generalised results are formally very similar and thus we do not give them in the introduction. They are discussed in Section \ref{highertc}. We should mention that the results for higher topological complexity extend the computation of the higher topological complexity of pure braid groups due to Gonz\'alez and Grant \cite{GG}. Again, our methods are somewhat different to theirs, which are in turn similar to the ones used by Farber and Yuzvinsky in \cite{FY}.

Configuration spaces of points in the plane give models for Eilenberg--Mac Lane spaces of braid groups, including those considered in this paper (see \lemref{lem:keypione} below). Therefore, our results have implications for motion planning of $n$ agents moving in a planar region avoiding collisions, where the agents are partitioned into equivalence classes according to their function.

Several of the results in this paper were inspired by corresponding results in \cite{CGJ}; we thank the authors of that paper for their correspondence and in particular for providing an algebraic proof of \lemref{lem:centre}. We also thank Jes\'us Gonz\'alez for suggesting that we generalise our results to higher topological complexity.

\section{Topological complexity of aspherical spaces

For any space $X$, let $p_X:X^I\to X\times X$ denote the free path fibration on $X$, with projection $p_X(\gamma) = (\gamma(0),\gamma(1))$. Recall that the \emph{topological complexity} of $X$, denoted ${\sf TC}(X)$, is defined to be the minimal $k$ such that $X\times X$ admits a cover by $k+1$ open sets $U_0,U_1,\ldots , U_k$, on each of which there exists a local section of $p_X$ (that is, a continuous map $s_i:U_i\to X^I$ such that $p_X\circ s_i = \mathrm{incl}_i:U_i\hookrightarrow X\times X$). Note that here we use the reduced version of ${\sf TC}(X)$, which is one less than the number of open sets in the cover.

Let $\pi$ be a discrete group. It is well-known that there exists a connected CW-complex $K(\pi,1)$ with
\[\pi_i(K(\pi,1))=\left\{\begin{array}{ll} \pi & (i=1) \\ 0 & (i\ge2). \end{array}\right.\]
Such a space is called an \emph{Eilenberg--Mac Lane space} for the group $\pi$. Furthermore, $K(\pi,1)$ is unique up to homotopy. This makes the following definition sensible.

\begin{defn}
The topological complexity of a discrete group $\pi$ is given by
\[{\sf TC}(\pi)\coloneqq{\sf TC}(K(\pi,1)).\]
\end{defn}

In the survey article \cite{Far06} Farber poses the problem of describing ${\sf TC}(\pi)$ solely in terms of algebraic properties of the group $\pi$. Very little is known about this problem in general. We remark that the corresponding question about $\mathsf{cat}(\pi):=\mathsf{cat}(K(\pi,1))$ has been completely answered: By work of Eilenberg--Ganea \cite{EG} and Stallings \cite{Sta} and Swan \cite{Swa}, we have $\mathsf{cat}(\pi)={\sf cd}(\pi)$, where ${\sf cd}$ denotes the cohomological dimension. In cases where the exact value of ${\sf TC}(\pi)$ is known, it often agrees with the standard cohomological lower bound in terms of the zero-divisors cup-length. However, one can also give potentially sharper lower bounds for ${\sf TC}(\pi)$ which take into account the subgroup structure of $\pi$.

\begin{thm}[{Grant--Lupton--Oprea \cite[Theorem 1.1]{GLO}}]\label{thm:lowerbound}
Let $\pi$ be a discrete group, and let $A$ and $B$ be subgroups of $\pi$. Suppose that $gAg^{-1} \cap B = \{1\}$
for every $g \in \pi$. Then \[{\sf TC}(\pi)\ge {\sf cd}(A \times B).\]
\end{thm}

This result has been applied in \cite{GLO} to calculate the topological complexity of Higman's group. In Section \ref{Lower bounds} of the current paper we will use it to give lower bounds for the topological complexity of mixed braid groups.

In fact, the upper bounds used in this paper are also group-theoretic in nature.

\begin{thm}[{Grant \cite[Proposition 3.7]{G}}]\label{thm:upperbound}
Let $\pi$ be a torsion-free discrete group, with centre $\mathcal{Z}(\pi)\le \pi$. Identify $\mathcal{Z}(\pi)$ with its image under the diagonal homomorphism $d:\pi\to \pi\times \pi$. Then \[{\sf TC}(\pi)\le {\sf cd}\left(\frac{\pi\times\pi}{\mathcal{Z}(\pi)}\right).\]
\end{thm}

This result was applied in \cite{G} to give upper bounds for the topological complexity of finitely generated torsion-free nilpotent groups. In Section \ref{Upper bounds} below we will apply it to various subgroups of the full braid group.

\section{Braid groups and their subgroups}\label{Braidgroups

\begin{defn}
A \emph{braid on $n$ strands} is an isotopy class of embeddings of the disjoint union of $n$ intervals in $\mathbb{R}^3$. The embeddings start at a set of $n$ distinct points in the plane $z=0$ and end at the corresponding set of points in the plane $z=1$, and are monotonically increasing in the direction of the $z$-axis. The isotopies are fixed on the boundary. Note that the start and end points of the individual strands are not required to correspond.

The \emph{full braid group} $B_n$ for $n\ge2$ is the group of braids with $n$ strands, where the group operation is given by concatenating braids.
\end{defn}

The group $B_n$ was first studied by Artin \cite{Art}, who showed (among other things) that it is generated by the braids $\sigma_i$ for $i=1,\ldots ,n-1$ which pass the $i$th strand over the $(i+1)$st strand. There is a canonical epimorphism
\[\pi\colon B_n\to\mathfrak{S}_n\]
which sends the generator $\sigma_i$ to the transposition $(i\;i+1)$ in the symmetric group $\mathfrak{S}_n$. Thus a braid $\gamma\in B_n$ gets sent to the associated permutation $\pi(\gamma)\in \mathfrak{S}_n$ of its endpoints.

The kernel $P_n\coloneqq\pi^{-1}(\{1\})$ of this projection is the \emph{pure braid group} and its elements are called \emph{pure braids}. More generally, given a subgroup $G\leq \mathfrak{S}_n$, we denote its pre-image by $B_n^G\coloneqq\pi^{-1}(G)$. Such a subgroup of $B_n$ may be called a \emph{$G$-braid group}, and its elements \emph{$G$-braids}. These are the groups whose topological complexity we are interested in computing.

\begin{ex}\label{ex:mixed}
Given an integer $1\le k\le n-1$, let $G=\mathfrak{S}_{n-k}\times \mathfrak{S}_k\leq \mathfrak{S}_n$ be the group of permutations which preserve the partition of $n$ objects into the first $n-k$ objects and the last $k$ objects. We denote the subgroup $B_n^{\mathfrak{S}_{n-k}\times \mathfrak{S}_k}$ by $B_{n-k,k}$, and refer to it as a \emph{mixed braid group}. One could imagine using two colours to distinguish the first $n-k$ braids from the last $k$ braids (hence groups of this form also are often called \emph{coloured braid groups}).
\end{ex}

In proving algebraic facts about braid groups and their subgroups, it is often easiest to argue topologically using configuration space models for their $K(\pi,1)$'s. Let
$$\mathbb{C}_m:=\mathbb{C}\setminus\{0,1,\ldots , m-1\}$$
denote the complex plane with $m$ punctures. Recall that the \emph{configuration space} of $n$ points on the plane with $m$ punctures is given by
\[F(\mathbb{C}_m,n)\coloneqq\{(x_1,\ldots,x_n)\in(\mathbb{C}_m)^n\,|\,x_i\ne x_j\text{ for }i\ne j\}.\]

\begin{lem}[Fadell--Neuwirth \cite{FN}]\label{lem:fadellneuwirth}
For each $m\ge0$ and $n\ge2$, projection onto the first coordinate gives a locally trivial fibration sequence
\begin{equation}\label{Fadell-Neuwirth}
F(\mathbb{C}_{m+1},n-1)\to F(\mathbb{C}_m,n)\to\mathbb{C}_m.
\end{equation}
Furthermore, this fibration admits a section.
\end{lem}

\begin{lem}\label{lem:keypione}
Any subgroup $G\leq \mathfrak{S}_n$ of the symmetric group acts freely on $F(\mathbb{C},n)$ by permuting the coordinates. The quotient space $F(\mathbb{C},n)/G$ under this action is an Eilenberg--Mac Lane space $K(B_n^G,1)$.
\end{lem}

\begin{proof}
It is easily seen from the definitions that $B_n^G$ is the fundamental group of $F(\mathbb{C},n)/G$.

It is also well known that $F(\mathbb{C},n)$ is aspherical. This follows from the Fadell-Neuwirth fibrations (\ref{Fadell-Neuwirth}) and induction. Explicitly, note that $F(\mathbb{C}_{n-1},1) = \mathbb{C}_{n-1}$ is homotopic to a wedge of circles and therefore aspherical, and that for $1\le k\le n-1$ we have that $F(\mathbb{C}_{n-k-1},k+1)$ fibres over an aspherical space $\mathbb{C}_{n-k-1}$ with fibre $F(\mathbb{C}_{n-k},k)$.

The spaces $F(\mathbb{C},n)/G$ are therefore aspherical, because they have $F(\mathbb{C},n)$ as a covering space.
\end{proof}

Recall that a duality group is a group whose (co)homology satisfies a generalization of Poincar\'e duality \cite{BE}. In more detail, we call a group $\pi$ a \emph{duality group of dimension $n$} if there exists a $\mathbb{Z}\pi$-module $C$ and an element $e\in H_n(\pi;C)$ such that the cap product homomorphism
\[e\cap-\colon H^k(\pi;A)\overset{\cong}{\to}H_{n-k}(\pi;C\otimes A)\]
is an isomorphism for all $k\in \mathbb{Z}$ and all $\mathbb{Z}\pi$-modules $A$. It follows that ${\sf cd}(\pi)=n$.

For instance, the fundamental group of a closed aspherical $n$-manifold is a duality group of dimension $n$.

\begin{thm}[Bieri--Eckmann \cite{BE}]\label{thm:duality}
\begin{enumerate}
\item If a torsion-free group $\pi$ has a finite index subgroup $S$ which is a duality group of dimension $n$, then $\pi$ is also a duality group of dimension $n$.
\item If $K$ and $Q$ are duality groups of dimensions $m$ and $n$ respectively which fit into an extension of groups
\[
\xymatrix{
1 \ar[r] & K \ar[r] & \pi \ar[r] & Q\ar[r] & 1,
}
\]
then $\pi$ is a duality group of dimension $m+n$.
\item Non-trivial free groups are duality groups of dimension $1$.
\end{enumerate}
\end{thm}

The following lemma tells us that the groups we are interested in are indeed duality groups.

\begin{lem}\label{lem:dualitygroups}
For every $G\le\mathfrak{S}_n$, the group $B_n^G$ is a duality group of dimension $n-1$.

Furthermore, $\tilde P_{n-2}\coloneqq\pi_1(F(\mathbb{C}_2,n-2))$ is a duality group of dimension $n-2$.
\end{lem}
\begin{proof}
The fact that $P_n=\pi_1 (F(\mathbb{C},n))$ is a duality group of dimension $n-1$ follows from the same chain of Fadell--Neuwirth fibrations used in the proof of \lemref{lem:keypione}. Indeed, by Lemma \ref{lem:fadellneuwirth} we have for each $1\le k\le n-1$ a split short exact sequence of fundamental groups
 \[\xymatrix{
 1  \ar[r] & \pi_1 (F(\mathbb{C}_{n-k},k))  \ar[r] & \pi_1 (F(\mathbb{C}_{n-k-1},k+1))  \ar[r] & \pi_1 (\mathbb{C}_{n-k-1})  \ar[r] &  1.}
 \]
  Our inductive hypothesis is that $\pi_1 (F(\mathbb{C}_{n-k},k))$ is a duality group of dimension $k$. The induction step follows from Theorem \ref{thm:duality} (2), with the base case $k=1$ given by Theorem \ref{thm:duality} (3).

Observe that in the course of the induction (two steps before the end) we have shown that $\tilde P_{n-2}\coloneqq\pi_1(F(\mathbb{C}_2,n-2))$ is a duality group of dimension $n-2$.

Finally, let $G\le\mathfrak{S}_n$. The group $B_n^G$ is torsion-free because it has a finite-dimensional $K(\pi,1)$. Now the claim follows from \thmref{thm:duality} (1) because $B_n^G$ contains the duality group $P_n$ as a finite index subgroup.
\end{proof}

In order to apply Theorem \ref{thm:upperbound} to the groups $B_n^G$, we need to identify their centres. Note that $P_n\leq B_n^G\leq B_n$. It is well known that $\mathcal{Z}(P_n)$ and $\mathcal{Z}(B_n)$ are infinite cyclic, and are equal for $n\geq 3$.

\begin{lem}\label{lem:centre}
For any subgroup $G\leq \mathfrak{S}_n$, the centre $\mathcal{Z}(B_n^G)$ is infinite cyclic. Furthermore, when $n\ge3$ we have
\[
\mathcal{Z}(P_n)=\mathcal{Z}(B_n^G)=\mathcal{Z}(B_n),
\]
and all of these groups are generated by the full twist
\[\Delta^2=((\sigma_1\ldots\sigma_{n-1})(\sigma_1\ldots\sigma_{n-2})\ldots(\sigma_1\sigma_2)\sigma_1)^2=(\sigma_1\ldots\sigma_{n-1})^n.\]
\end{lem}
\begin{proof}
The case $n=2$ is clear since all the groups will be isomorphic to $\mathbb{Z}$. For the rest of the proof assume $n\ge3$.

It is a standard result that the full twist $\Delta^2$ generates $\mathcal{Z}(P_n)=\mathcal{Z}(B_n)$ (for a proof see for instance \cite[Theorem 1.24]{KT}). Since $\Delta^2$ commutes with everything (and in particular with braids in $B_n^G$) we therefore have $\mathcal{Z}(P_n)\leq \mathcal{Z}(B_n^G)$. It just remains to be shown that $\mathcal{Z}(B_n^G)\leq P_n$, since then it follows easily that $\mathcal{Z}(B_n^G)\leq \mathcal{Z}(P_n)$. In fact, a seemingly stronger statement is true: If a braid $\gamma\in B_n$ commutes with every pure braid, then $\gamma$ is itself a pure braid.

To see this note that it is possible to assign to each pure braid an \emph{ordered} link by closing off the braid, that is, by connecting together both ends of each strand in the braid. This is illustrated in the following picture.

\begin{center}
\begin{tikzpicture}[scale=0.5]
\braid[number of strands=3,thick,style strands={1}{red},style strands={2}{green},style strands={3}{blue}] a_1a_2^{-1}a_2^{-1}a_1a_2a_2;
\braid[number of strands=3,thick,style strands={1}{red},style strands={2}{green},style strands={3}{blue},xshift=-8cm] a_1a_2^{-1}a_2^{-1}a_1a_2a_2;
\draw[thick,red,rounded corners](1,0)--(1,0.5)--(0,0.5)--(0,-7)--(1,-7)--(1,-6.5);
\draw[thick,green,rounded corners](2,0)--(2,1)--(-0.5,1)--(-0.5,-7.5)--(2,-7.5)--(2,-6.5);
\draw[thick,blue,rounded corners](3,0)--(3,1.5)--(-1,1.5)--(-1,-8)--(3,-8)--(3,-6.5);
\end{tikzpicture}
\captionof{figure}{A pure braid and its closure.}
\end{center}

Note that conjugating a pure braid by a braid $\gamma\in B_n$ before closing it off will result in the same link, but with the ordering of its components permuted by $\pi(\gamma)$. Suppose that $\gamma\in B_n$ commutes with every braid in $P_n$. Then conjugation by $\gamma$ is the identity on $P_n$, and the permutation $\pi(\gamma)$ acts trivially on the set of isotopy classes of ordered links of $n$ components. It follows that $\pi(\gamma)=1$, so $\gamma$ is a pure braid.
\end{proof}

\section{Upper bounds}\label{Upper bounds

Using the algebraic results of the previous section, we can now establish our main upper bound.

\begin{thm}\label{thm:torsionbound}
Suppose that $G\le \mathfrak{S}_n$ is such that $B_n^G/\mathcal{Z}(B_n^G)$ is torsion-free. Then
\[{\sf TC}(B_n^G)\le 2n-3.\]
\end{thm}

\begin{proof}
Consider the group extension
\begin{equation*}
\xymatrix{ 1 \ar[r] &  \mathcal{Z}(B_n^G) \ar[r]^-{d} &  B_n^G\times B_n^G \ar[r] & (B_n^G\times B_n^G)/\mathcal{Z}(B_n^G) \ar[r] & 1,}
\end{equation*}
where $d$ denotes the diagonal embedding. By Theorem \ref{thm:upperbound}, it will suffice to prove that the quotient group $(B_n^G\times B_n^G)/\mathcal{Z}(B_n^G)$ has cohomological dimension $2n-3$. It follows from the assumptions that this quotient is torsion-free, and by Lemma \ref{lem:centre} it contains $(P_n\times P_n)/\mathcal{Z}(P_n)$ as a subgroup of finite index. Thus we are reduced (by Theorem \ref{thm:duality}(1)) to showing that $(P_n\times P_n)/\mathcal{Z}(P_n)$ is a duality group of dimension $2n-3$.

Using the operations of addition and multiplication in $\mathbb{C}$, it is easily shown that the first two Fadell--Neuwirth fibrations used in the proofs of Lemmas \ref{lem:keypione} and \ref{lem:dualitygroups} are in fact trivial, so that we have a splitting up to homeomorphism
\[F(\mathbb{C},n)\approx F(\mathbb{C}_2,n-2)\times\mathbb{C}_1\times\mathbb{C}.\]
On fundamental groups this gives a splitting $P_n\cong\tilde{P}_{n-2}\times\mathbb{Z}$, under which the centre $\mathcal{Z}(P_n)$ corresponds to $\{1\}\times\mathbb{Z}$. We therefore find that
\[
(P_n\times P_n)/\mathcal{Z}(P_n) \cong (\tilde{P}_{n-2}\times\mathbb{Z}\times \tilde{P}_{n-2}\times\mathbb{Z})/\mathcal{Z}(P_n) \cong \tilde{P}_{n-2}\times \tilde{P}_{n-2}\times \mathbb{Z}.
\]
Since the group $\tilde{P}_{n-2}$ was shown in \lemref{lem:dualitygroups} to be a duality group of dimension $n-2$, the result now follows from Theorem \ref{thm:duality}(2).
\end{proof}

We now give examples of subgroups $G\leq \mathfrak{S}_n$ for which the assumption of the theorem holds. We continue to denote the mixed braid group $B_n^{\mathfrak{S}_{n-k}\times \mathfrak{S}_k}$ from Example \ref{ex:mixed} by $B_{n-k,k}$.

\begin{prop}\label{prop:torsionfree}
The mixed braid group modulo its centre $B_{n-k,k}/\mathcal{Z}(B_{n-k,k})$ is torsion-free if and only if $(n,k)=(n-1,k)=(n-1,k-1)=1$.
\end{prop}
\begin{proof}

The centre $\mathcal{Z}(B_{n-k,k})$ is infinite cyclic generated by the full twist $\Delta^2=(\sigma_1\ldots\sigma_{n-1})^n$, by \lemref{lem:centre}. Thus torsion elements in $B_{n-k,k}/\mathcal{Z}(B_{n-k,k})$ will be represented by braids $\alpha\in B_{n-k,k}$ such that $\alpha^m=\Delta^l$, for some powers $m,l\in\mathbb{Z}$, but $\alpha$ is not a power of $\Delta^2$ itself.

Viewing the braid group $B_n$ as the fundamental group of the configuration space $F(\mathbb{C},n)/\mathfrak{S}_n$, the full twist corresponds to a rotation of the point configuration by $2\pi$. Section~2.2 from \cite{GM} tells us that all torsion elements are represented by rotations up to conjugation. To be precise, there exist $m,l\in\mathbb{Z}$ such that $\alpha^m=\Delta^l$ if and only if there exist $\beta\in B_n$ and $p\in\mathbb{Z}$ such that either $\alpha=\beta\delta^p\beta^{-1}$ or $\alpha=\beta\epsilon^p\beta^{-1}$. Here the elements $\delta$ and $\epsilon$ can be expressed in terms of the standard generators as
\[\delta=\sigma_1\ldots\sigma_{n-1}\text{ and }\epsilon=\sigma_1(\sigma_1\ldots\sigma_{n-1}),\] and correspond to minimal rotations in $F(\mathbb{C},n)/\mathfrak{S}_n$, where in the case of $\epsilon$ one of the points in the configuration is a fixed point of the rotation.

Recall that $\pi$ denotes the canonical projection $\pi\colon B_n\to\mathfrak{S}_n$.

Observe that $\pi(\delta)$ is an $n$-cycle and $\pi(\epsilon)$ is an $(n-1)$-cycle times a 1-cycle. Therefore $\pi(\delta)^p$ is a product of $d$ $n/d$-cycles, where $d=(p,n)$ is the greatest common divisor of $p$ and $n$, which could be 1. Similarly $\pi(\epsilon)^q$ is a product of $d$ $(n-1)/d$-cycles and a 1-cycle, where $d=(q,n-1)$.

Recall that elements in the symmetric group are conjugate if and only if they have the same cycle structure. Therefore, $\pi(\delta)^p$ is conjugate to an element in $\mathfrak{S}_{n-k}\times\mathfrak{S}_k$ if and only if $n/(p,n)$ divides $k$. Similarly, $\pi(\epsilon)^q$ is conjugate to an element in $\mathfrak{S}_{n-k}\times\mathfrak{S}_k$ if and only if $(n-1)/(q,n-1)$ divides $k$ or $k-1$.

One implication in the theorem now follows from combining the above observations. If $B_{n-k,k}/\mathcal{Z}(B_{n-k,k})$ had torsion there would exist an element $\alpha\in B_{n-k,k}$ which is conjugate to $\delta^p$ or $\epsilon^q$. Therefore, there would exist an element $\pi(\alpha)\in\mathfrak{S}_{n-k}\times\mathfrak{S}_k$ conjugate to $\pi(\delta)^p$ or $\pi(\epsilon)^q$. This implies that either $(n,k)\ne1$ or $(n-1,k)\ne1$ or $(n-1,k-1)\ne1$.

The converse implication follows from a similar argument. Assume that for instance $(n,k)\ne1$. Then there exists an element $\alpha\in\mathfrak{S}_{n-k}\times\mathfrak{S}_k$ conjugate to $\pi(\delta)^p$:
\[\alpha=\beta\pi(\delta)^p\beta^{-1}.\]

Taking a lift $\sigma_\beta$ of $\beta$ yields an element $\sigma_\beta\delta^p\sigma_\beta^{-1}$ of $B_{n-k,k}$.
\end{proof}

\begin{cor}\label{cor:torsion1}
If $G\le \mathfrak{S}_{n-k}\times \mathfrak{S}_k$ with $(n,k)=(n-1,k)=(n-1,k-1)=1$, then the group $B_n^G/\mathcal{Z}(B_n^G)$ is torsion-free.
\end{cor}
\begin{proof}
If $G\le \mathfrak{S}_{n-k}\times \mathfrak{S}_k$, then $B_n^G$ is a subgroup of $B_{n-k,k}$ but by \lemref{lem:centre}, the centre of both groups is the same. Therefore, if $B_{n-k,k}/\mathcal{Z}(B_{n-k,k})$ is torsion-free then so is $B_n^G/\mathcal{Z}(B_n^G)$.
\end{proof}

\begin{prop}\label{prop:torsion2}
If $G=H\times\{1\}^2\le\mathfrak{S}_n$ where $H\le \mathfrak{S}_{n-2}$, then the group $B_n^G/\mathcal{Z}(B_n^G)$ is torsion-free.
\end{prop}

\begin{proof}
In the proof of \thmref{thm:torsionbound} it was observed that there is a homeomorphism $F(\mathbb{C},n)\approx F(\mathbb{C}_2,n-2)\times\mathbb{C}_1\times\mathbb{C}$. This splitting is compatible with the action of $G=H\times\{1\}^2$ (as is clear from writing out explicit formulae, or see Lemma 3.1 and Theorem 3.3 of \cite{CGJ} for a proof). Therefore we have a homeomorphism $$F(\mathbb{C},n)/G\approx (F(\mathbb{C}_2,n-2)/H)\times \mathbb{C}_1\times \mathbb{C},$$ which on fundamental groups gives the splitting $B_n^G\cong \tilde{B}_{n-2}^H\times \mathbb{Z}$, where $\tilde{B}_{n-2}^H\coloneqq\pi_1(F(\mathbb{C}_2,n-2)/H)$. Under this splitting the centre $\mathcal{Z}(B_n^G)=\mathbb{Z}$ corresponds to $\{1\}\times\mathbb{Z}$, and therefore we have $B_n^G/\mathcal{Z}(B_n^G)\cong \tilde{B}_{n-2}^H$.

Finally we observe that $\tilde{B}_{n-2}^H$ is torsion-free because it has the finite-dimensional space $F(\mathbb{C}_2,n-2)/H$ as its $K(\pi,1)$.
\end{proof}

Putting together \corref{cor:torsion1}, \propref{prop:torsion2} and \thmref{thm:torsionbound} yields:

\begin{thm}\label{thm:upperresult}
Let $G\le \mathfrak{S}_{n-2}\times\{1\}^2\le \mathfrak{S}_n$ or $G\le \mathfrak{S}_{n-k}\times \mathfrak{S}_k$ with $(n,k)=(n-1,k)=(n-1,k-1)=1$. Then \[{\sf TC}(B_n^G)\le 2n-3.\]
\end{thm}

\begin{rem}
In the case $G\leq \mathfrak{S}_{n-2}\times\{1\}^2$, the upper bound ${\sf TC}(B_n^G)\le 2n-3$ can be deduced from the fact that there is a splitting
\[
B_n^G \cong \left(B_n^G/\mathcal{Z}(B_n^G)\right)\times \mathcal{Z}(B_n^G),
\]
together with the product formula for topological complexity \cite[Theorem 11]{Far03}. We do not know if the upper bound ${\sf TC}(B_n^G)\le 2n-3$ for $G\leq\mathfrak{S}_{n-k}\times \mathfrak{S}_k$ can be obtained in this way. For instance, we do not know if the centre of the mixed braid group $B_{5,3}$ splits off as a direct factor.
\end{rem}

\section{Lower bounds}\label{Lower bounds

We now give lower bounds for ${\sf TC}(B_n^G)$ in certain cases, using Theorem \ref{thm:lowerbound}. Our arguments generalise the argument given in \cite[Proposition 3.3]{GLO} for pure braids.

\begin{thm}\label{lower1}
Let $G\le \mathfrak{S}_{n-k}\times \mathfrak{S}_k$ for $k\ge2$. Then \[{\sf TC}(B_n^G)\ge 2n-k-1.\]

Furthermore, if $G\le \mathfrak{S}_{n-1}\times \mathfrak{S}_1$, then \[{\sf TC}(B_n^G)\ge 2n-3.\]
\end{thm}
\begin{proof}

Suppose $G\le \mathfrak{S}_{n-k}\times \mathfrak{S}_k$ for $k\ge2$. To apply \thmref{thm:lowerbound}, we need to give two subgroups of $B_n^G$ which contain no non-trivial conjugates. The following subgroups satisfy this assumption:

\begin{enumerate}
\item Think of $P_{n-k+1}$ for $k\ge 2$ as a subgroup of $P_n$ by adding $k-1$ strands which do not interact with any other strand.
\item Denote by $A_n$ the subgroup of $P_n$ generated by braids of the form \[\alpha_j=\sigma_{j}\sigma_{j+1}\ldots \sigma_{n-1}\sigma_n\sigma_n\sigma_{n-1}\ldots \sigma_{j+1}\sigma_{j},\]
for $1\le j\le n-1$. In words, the generator $\alpha_j$ takes the $j$th strand over the last $n-j$ strands and back under them until it gets back to its original position, see the braid diagrams below. Looking at the braid diagrams it becomes evident that the generators commute, and therefore $A_n\cong\mathbb{Z}^{n-1}$.
\end{enumerate}

Since $P_n\leq B_n^G$, these are indeed both subgroups of $B_n^G$. It remains to show that $P_{n-k+1}\cap \gamma A_n\gamma^{-1}=\{1\}$ for all $\gamma\in B_n^G$.

Recall that closing off a pure braid yields an ordered link, and that conjugating a pure braid in $P_n$ by an element of $B_n^G$ before closing it off will result in an isotopic link up to permutation of its components by an element of $G$. In light of the above, it suffices to show that the links coming from closing off nontrivial elements of $P_{n-k+1}$ can not be obtained by permuting with an element in $G$ the components of the link coming from closing off an element of $A_n$.

 For this we note that if we close a non-trivial braid in $A_n$, the last two components of the link will be linked either with some other component or with each other. This can be seen for the generators $\alpha_i$ by taking a look at the following braid diagrams.

\vspace{.3cm}
\begin{minipage}{.48\linewidth}
\begin{center}
\begin{tikzpicture}[xscale=0.7,yscale=1.25]
\braid[number of strands=4,thick,style strands={3}{red}] 1 a_3a_3 1;
\end{tikzpicture}
\captionof{figure}{The braid $\alpha_{3}\in A_4$. }
\end{center}
\end{minipage}%
\begin{minipage}{.48\linewidth}
\begin{center}
\begin{tikzpicture}[scale=0.7]
\braid[number of strands=4,thick,style strands={2}{red}] a_2a_3a_3a_2;
\end{tikzpicture}
\captionof{figure}{The braid $\alpha_{2}\in A_4$. }
\end{center}
\end{minipage}
\vspace{.3cm}

Because the generators $\alpha_i$ of $A_n$ commute with each other, every element $\sigma \in A_n$ can be written uniquely in the form
\[\sigma=\alpha_{1}^{m_{1}}\alpha_{2}^{m_{2}}\cdots\alpha_{n-1}^{m_{n-1}}\qquad(m_i\in \mathbb{Z}).\]
The exponent $m_i$ determines the linking number of the $i$th strand with all subsequent strands, from the $(i+1)$st up to the $n$th. Therefore the last two components of the link which results from closing off $\sigma$ are unlinked from the first $n-2$ and from each other if and only if all the $m_i=0$, i.e. if and only if $\sigma$ is trivial. In particular, closing off a non-trivial element of $A_n$ will yield a link where at least two of the last $k$ components are linked with something else.

On the other hand, closing braids in $P_{n-k+1}\subset P_{n}$ yields links in which at most one of the last $k$ components is linked with another component. Therefore, a link coming from a non-trivial element in $A_n$ cannot be obtained from a link coming from a braid in $P_{n-k+1}$ by permuting the components by an element of $G$. This is because, by assumption, an element of $G$ does not permute any of the last $k$ components with any of the first $n-k$.

Finally, \thmref{thm:lowerbound} yields

\[{\sf TC}(B_n^G)\ge {\sf cd}(P_{n-k+1})+{\sf cd}(A_n)=(n-k)+(n-1)=2n-k-1.\]

The proof for $G\le \mathfrak{S}_{n-1}\times \mathfrak{S}_1$ is analogous but has to be stated separately. Here we may take the subgroups $P_{n-1}$ and $A_n$, and just use the linking number with the last strand.
\end{proof}

Note that the lower bound goes down by one at each step for $k\ge2$ but it is the same for $B_{n-1,1}$ and $B_{n-2,2}$.

\begin{cor}\label{cor:lower2}
Let $G\le \mathfrak{S}_{n-2}\times\{1\}^2\le \mathfrak{S}_n$. Then \[{\sf TC}(B_n^G)\ge 2n-3.\]
\end{cor}

Note that in \corref{cor:lower2} the lower bound coincides with the upper bound from \thmref{thm:upperresult} and thus gives a complete answer in that case.

\begin{rem}\label{rem:zerodivisors}
The optimal lower bound ${\sf TC}(P_n)\geq 2n-3$ can be obtained fairly easily using zero-divisors cup-length \cite{FY}, because the rational cohomology algebra $H^*(P_n;\mathbb{Q})$ is well understood.

One could ask whether the lower bounds for ${\sf TC}(B_n^G)$ given above can be obtained similarly using rational cohomology. An application of the Cartan--Leray spectral sequence would give an algebra isomorphism
\[
H^*(B_n^G;\mathbb{Q})\cong H^*(P_n;\mathbb{Q})^G.
\]
In the cases we are interested in, however, the calculation of this ring of invariants appears not so straightforward, and does not seem to have been carried out in the literature. In the low dimensional cases in which we were able to compute the zero-divisors cup-length, it was less effective than our lower bound. One could try to replace $\mathbb{Q}$ with some other coefficient ring, but then calculations become even more involved.

For the full braid group $B_n$, both the zero-divisors cup-length and the methods given in this paper appear to be insufficient.
\end{rem}

\section{Higher topological complexity}\label{highertc}

The concept of higher topological complexity was introduced by Rudyak in \cite{Rud}. See also the subsequent paper \cite{BGRT} by Basabe, Gonz\'alez, Rudyak and Tamaki.

Recall that in Section 2 the topological complexity of a space $X$ was defined using the free path fibration $p_X:X^I\to X\times X$, with projection $p_X(\gamma) = (\gamma(0),\gamma(1))$. For any natural number $m\ge2$, the \emph{$m$th topological complexity} of $X$, denoted ${\sf TC}_m(X)$, can similarly be defined with help of the fibration $$p^m_X:X^I\to X^m$$ with projection $$p^m_X(\gamma) = (\gamma(0),\gamma(1/(m-1)),\ldots,\gamma((m-2)/(m-1)),\gamma(1)).$$Concretely, it is the minimal $k$ such that $X^m$ admits a cover by $k+1$ open sets $U_0,U_1,\ldots , U_k$, on each of which there exists a local section of the fibration $p^m_X$. Of course, the case $m=2$ corresponds to the original topological complexity.

The results for the topological complexity of mixed braid groups in the last two sections rely on \cite[Theorem 1.1]{GLO} and  \cite[Proposition 3.7]{G} (denoted \thmref{thm:lowerbound} and \thmref{thm:upperbound} in this paper). Those theorems can be generalised in a straightforward way to the following statements about higher topological complexity.

\begin{thm}\label{thm:higherlowerbound}
Let $\pi$ be a discrete group, and let $A$ and $B$ be subgroups of $\pi$. Suppose that $gAg^{-1} \cap B = \{1\}$
for every $g \in \pi$. Then \[{\sf TC}_m(\pi)\ge {\sf cd}(A \times B \times \pi^{m-2}).\]
\end{thm}

\begin{thm}\label{thm:higherupperbound}
Let $\pi$ be a torsion-free discrete group, with centre $\mathcal{Z}(\pi)\le \pi$. Identify $\mathcal{Z}(\pi)$ with its image under the diagonal homomorphism $d_m:\pi\to \pi^m$. Then \[{\sf TC}_m(\pi)\le {\sf cd}\left(\frac{\pi^m}{\mathcal{Z}(\pi)}\right).\]
\end{thm}

Using this, the proofs in the earlier sections generalise to yield the following results.

\begin{thm}\label{thm:higherupperresult}
Suppose that $G\leq \mathfrak{S}_n$ satisfies either of the following conditions:
\begin{itemize}
\item $G\leq\mathfrak{S}_{n-k}\times \mathfrak{S}_k$ where $(n,k)=(n-1,k)=(n-1,k-1)=1$, or
\item $G\leq \mathfrak{S}_{n-2}\times \{1\}^2$.
\end{itemize}
Then we have
\[
{\sf TC}_m(B_n^G)\leq m(n-1)-1.
\]
\end{thm}

\begin{thm}\label{thm:higherlowerresult}
Let $G\le \mathfrak{S}_{n-k}\times \mathfrak{S}_k$ for $k\ge2$. Then \[{\sf TC}_m(B_n^G)\ge m(n-1)-k+1.\]

Furthermore, if $G\le \mathfrak{S}_{n-1}\times \{1\}$, then \[{\sf TC}(B_n^G)\ge m(n-1)-1.\]
\end{thm}

As before, in some cases the upper and lower bounds coincide to give an equality.

\begin{cor}
If $G\leq \mathfrak{S}_{n-2}\times \{1\}^2$, then
\[
{\sf TC}(B_n^G)=m(n-1)-1.
\]
\end{cor}

redpajama_set_name: RedPajamaArXiv


text:
\section{Introduction}

Omitting the linear and constant terms, a quadratic function $Q$ from ${\mathbb F}_{p^n}$ to ${\mathbb F}_p$, for a prime $p$,
can be expressed in trace form as
\begin{equation}
\label{quadra}
Q(x) = {\rm Tr_n}\left(\sum_{i=0}^{\lfloor{n}/2\rfloor}a_ix^{p^i+1}\right)\ , \quad a_i\in{\mathbb F}_{p^n} \ ,
\end{equation}
where ${\rm Tr}_n$ denotes the absolute trace from ${\mathbb F}_{p^n}$ to ${\mathbb F}_p$.
When $n$ is odd, this representation is unique. For even $n$ the coefficient $a_{n/2}$ is taken modulo
the additive subgroup $G = \{x\in{\mathbb F}_{p^n}\;:\;{\rm Tr}^n_{n/2}(x) = 0\}$ of ${\mathbb F}_{p^n}$, where ${\rm Tr}^n_{n/2}$
denotes the relative trace from ${\mathbb F}_{p^n}$ to ${\mathbb F}_{p^{n/2}}$. Furthermore, if $p=2$, then $a_0 = 0$,
hence $i$ in  the summation in $(\ref{quadra})$ ranges over
$1 \leq i \leq \lfloor{n}/2\rfloor$, since $a_0x^2$ is a linear term.

The {\it Walsh transform} $\widehat{f}$ of a function $f:{\mathbb F}_{p^n}\rightarrow {\mathbb F}_p$ is the function from ${\mathbb F}_{p^n}$ into
the set of complex numbers defined as
\[ \widehat{f}(b) = \sum_{x \in \mathbb F_{p^n}}\epsilon_p^{f(x)-{\rm Tr_n}(bx)} \ , \]
where $\epsilon_p = e^{2\pi i/p}$ is a complex $p$-th root of unity.

Quadratic functions belong to the class of {\it plateaued functions}, for which for every $b \in {\mathbb F}_{p^n}$, the
Walsh transform $\widehat{f}(b)$ vanishes or has absolute value $p^{(n+s)/2}$ for some fixed integer $0\le s \le n$.
Accordingly we call $f$ {\it $s$-plateaued}.
Note that if $p=2$, then $\epsilon_p = -1$, and $\widehat{f}(b)$ is an integer. Hence for any $s$-plateaued function
from ${\mathbb F}_{2^n}$ to ${\mathbb F}_2$, $n$ and $s$ must be of the same parity. Recall that a $0$-plateaued function from
${\mathbb F}_{p^n}$ to ${\mathbb F}_p$ is called {\it bent}. Clearly a Boolean bent function can exist only when $n$ is even. When $p$ is odd, a $1$-plateaued function is called {\it semi-bent}.
A Boolean function $f$ is called semi-bent, if $f$ is $1$ or $2$-plateaued, depending on the parity of $n$.

The {\it nonlinearity} $N_f$ of a function $f:{\mathbb F}_{p^n}\rightarrow{\mathbb F}_p$ is defined to be the smallest Hamming distance of $f$
to any affine function, i.e.
\[ N_f = \min_{u\in{\mathbb F}_{p^n},v\in{\mathbb F}_p}|\{x\in{\mathbb F}_{p^n}\;:\;f(x) \ne {\rm Tr_n}(ux)+v\}| \ . \]
The nonlinearity of a Boolean function $f$ can be expressed in terms of the Walsh transform as
\begin{equation}
\label{Nf}
N_f = 2^{n-1} - \frac{1}{2}\max_{b\in{\mathbb F}_{2^n}}|\widehat{f}(b)| \ .
\end{equation}
By Parseval's identity we have $\sum_{b\in{\mathbb F}_{2^n}}\left|\widehat{f}(b)\right|^2=2^{2n}$ for any Boolean function $f$.
As a consequence, Boolean bent functions are the Boolean functions attaining the highest possible nonlinearity.
Since high nonlinearity is crucial for cryptographic applications, Boolean bent functions are of particular interest.

Recall that the $r$th order Reed-Muller code $R(r,n)$ of length $2^n$ is defined as
\[ R(r,n)=\{(f(\alpha_{1}),f(\alpha_{2}),\cdots,f(\alpha_{2^{n}}))\;
|\; f\in P_{r}\} \ , \]
where $P_{r}$ is the set of all polynomials from ${\mathbb F}_{2^n}$ to ${\mathbb F}_2$ (or from ${\mathbb F}_2^n$ to ${\mathbb F}_2$)
of algebraic degree at most $r$, and $\alpha_{1},\alpha_{2},\ldots,\alpha_{2^n}$ are the elements of
${\mathbb F}_{2^n}$ (or ${\mathbb F}_2^n$) in some fixed order.
The set of quadratic Boolean functions together with the constant and affine functions form the second order
Reed-Muller codes.

In this work we focus on the subclasses of the set of quadratic functions given in Equation $(\ref{quadra})$, obtained by
restricting the coefficients to the prime subfield. Namely, for $p=2$ we consider $ \mathcal{C}_1$ and the larger class
$\mathcal{C}_2$ defined as
\[ \mathcal{C}_1 = \left\{Q(x) = {\rm Tr_n}\left(\sum_{i=1}^{\lfloor (n-1)/2\rfloor}a_ix^{2^i+1}\right)\;:\; a_i \in{\mathbb F}_2 ,\; 1\le i\le \left\lfloor \dfrac{n-1}{2}\right\rfloor \right\} , \; \text{and} \]
\begin{align*}
& \mathcal{C}_2 = \left\{Q(x) = {\rm Tr_n}\left(\sum_{i=1}^{(n/2)-1}a_ix^{2^i+1}\right) + {\rm Tr_{n/2}}(a_{n/2}x^{2^{n/2}+1})\right. : \\
& \qquad \qquad \qquad  \qquad \qquad \qquad \qquad \qquad \qquad \qquad
a_{n/2},a_i \in{\mathbb F}_2,\; 1\le i\le n/2 \Bigg\} \ .
\end{align*}
Note that $ \mathcal{C}_1$ is defined for arbitrary $n$, while $\mathcal{C}_2$ is defined for even $n$ only.
These two classes of Boolean functions have attracted significant attention in the last decade,
 see the articles \cite{caw,cpt,f2,hf,kgs,kkos,mt,mrt,yg}.
For $p>2$ we put
\[ \mathcal{D} =\left\{Q(x) = {\rm Tr_n}\left(\sum_{i=0}^{\lfloor n/2\rfloor}a_ix^{p^i+1}\right)\;:\; a_i \in{\mathbb F}_p\right\}\ . \]
The class $\mathcal{D}$ has also been studied previously, see \cite{caw,kgs,lhz,mt,mrt}.

The study of the Walsh spectrum of quadratic functions in $\mathcal{C}_1$ and $\mathcal{D}$
has been initiated in \cite{kgs}, where the authors determine all $n$ for which all such quadratic functions are semi-bent.
This result was extended in \cite{cpt} for $\mathcal{C}_1$. In the articles \cite{hf,yg} bent functions in $\mathcal{C}_2$ are constructed.

Enumeration of functions in $\mathcal{C}_1$, $\mathcal{C}_2$ and $\mathcal{D}$ for particular values of $s$ has been a challenging problem.
In \cite{yg} the number of bent functions in $\mathcal{C}_2$ was obtained for some special classes of $n$. Counting
results on Boolean quadratic functions in $\mathcal{C}_1$ with a large value of $s$
have been obtained in the paper \cite{f2}. Far reaching enumeration results for the sets $\mathcal{C}_1$ and $\mathcal{D}$
have been obtained in \cite{caw,mt,mrt} by the use of
methods originally employed in the analysis of the linear
complexity of periodic sequences, see \cite{fno}.

Let us denote the number of $s$-plateaued quadratic functions in $\mathcal{C}_1$ and $\mathcal{D}$ by $\mathcal{N}_n(s)$
and $\mathcal{N}_n^{(p)}(s)$, respectively.
In \cite{mt}, the number $\mathcal{N}_n(s)$
has been determined for $n = 2^m$, $m\ge 1$, and all possible values of $s$.
In \cite{mrt}, $\mathcal{N}_n(s)$ and $\mathcal{N}_n^{(p)}(s)$ are described by the use of
{\it generating polynomials} $\mathcal{G}_n(z)$ and $\mathcal{G}_n^{(p)}(z)$, defined by
\[ \mathcal{G}_n(z) = \sum_{t=0}^n\mathcal{N}_n(n-t)z^t\quad\mbox{and}\quad\mathcal{G}_n^{(p)}(z) = \sum_{t=0}^n\mathcal{N}_n^{(p)}(n-t)z^t \ .\]
In the cases of odd $n$ and $n = 2m$ for an odd $m$, the polynomial $\mathcal{G}_n(z)$ is
determined as a product of polynomials, see \cite{mrt}.
Similarly $\mathcal{G}_n^{(p)}(z)$ is obtained for $n$ with $\gcd(n,p) = 1$
in \cite{cm,mrt}. In particular, explicit formulas for the number of bent functions in $\mathcal{D}$ and of semi-bent functions
in $\mathcal{C}_1$ are given for such $n$. For a result on the number of semi-bent functions in $\mathcal{C}_2$ we may refer to the recent article \cite{kkos}.
The average behaviour of the Walsh transform of functions in $\mathcal{C}_1$ and $\mathcal{D}$ is analysed in \cite{caw}.
We remark that unlike $\mathcal{C}_2$, the set $\mathcal{C}_1$ does not contain bent functions.

In this work we present the solution of the enumeration problem in all remaining cases, i.e., we extend the above results to functions in $\mathcal{C}_1$, $\mathcal{C}_2$, $\mathcal{D}$ {\it for arbitrary $n$ and all possible $s$}, by determining,
\begin{itemize}
\item[(i)] the generating polynomial $\mathcal{G}_n(z)$ for any (even) number $n$,
\item[(ii)] the generating polynomial $\mathcal{H}_n(z) = \sum_{t=0}^n\mathcal{M}_n(n-t)z^t$ concerning the number $\mathcal{M}_n(s)$
of $s$-plateaued functions in $\mathcal{C}_2$, for any even number $n$, and
\item[(ii)] the generating polynomial $\mathcal{G}_n^{(p)}(z)$ for any number $n$, $\gcd(n,p) > 1$.
\end{itemize}
We therefore completely describe the distribution of the parameter $s$ in the set $\mathcal{C}_2$, and in the sets $\mathcal{C}_1$ and $\mathcal{D}$
in all remaining cases. This also yields the distribution of the nonlinearity in $\mathcal{C}_1$ and $\mathcal{C}_2$ in full generality.
In particular, one can obtain the number of bent functions in the sets $\mathcal{C}_2$ and $\mathcal{D}$,
or the number of semi-bent functions in $\mathcal{C}_1$, $\mathcal{C}_2$ and $\mathcal{D}$ for arbitrary integers $n$.

\begin{remark}
\label{rot.symm} The classes $\mathcal{C}_1, \mathcal{C}_2$ and $\mathcal{D}$ have additional properties that we explain below.
A Boolean function $f$, defined over ${\mathbb F}_{2^n}$ is {\it idempotent} if it satisfies $f(x^2) = f(x)$ for all $x\in{\mathbb F}_{2^n}$.
The set of idempotent quadratic functions coincides with $\mathcal{C}_1$ when $n$ is odd, and it coincides with $\mathcal{C}_2$
when $n$ is even.  For an odd prime $p$, one can similarly define a {\it $p$-potent} function as
a function $f$ from ${\mathbb F}_{p^n}$ to ${\mathbb F}_p$ that satisfies $f(x^p) = f(x)$ for all $x\in{\mathbb F}_{p^n}$. As one would expect,
the set of $p$-potent quadratic functions coincides with $\mathcal{D}$.
It is observed in \cite{cgl} that there is a nonlinearity preserving one-to-one correspondence between the set of idempotent quadratic functions
from ${\mathbb F}_{2^n}$ to ${\mathbb F}_2$ and the set of {\it rotation symmetric} quadratic functions from ${\mathbb F}_2^n$ to ${\mathbb F}_2$.
(Note that only even $n$ is considered in \cite{cgl}, but the same applies to the case of odd $n$.)
Following the arguments of \cite{cgl}, one can show that this property extends to any prime $p \geq 2$ and hence
there is a one-to-one correspondence between the set
$\mathcal{D}$ and the set of rotation symmetric quadratic functions from ${\mathbb F}_p^n$ to ${\mathbb F}_p$, which preserves the parameter $s$.
Hence many results on
idempotent and $p$-potent quadratic functions also yield results on rotation symmetric quadratic functions, which add to the interest in the classes $\mathcal{C}_1$,
$\mathcal{C}_2$ and $\mathcal{D}$.
\end{remark}
Having obtained the distribution of $s$ in $\mathcal{C}_1$,
$\mathcal{C}_2$, $\mathcal{D}$, we are able to give the distribution of the nonlinearity of rotation symmetric quadratic functions from ${\mathbb F}_2^n$ to ${\mathbb F}_2$, and the
distribution of the co-dimension of rotation symmetric quadratic functions from ${\mathbb F}_p^n$ to ${\mathbb F}_p$, for odd $p$.
We also analyse the subcodes of the second order Reed-Muller code obtained from $\mathcal{C}_1$ and $\mathcal{C}_2$, and
present the weight distribution for both subcodes of $R(2,n)$.

\section{Preliminaries}
\label{prel}

In this section we summarize basic tools that we use to obtain our results.
We essentially follow the notation of \cite{mt,mrt}.
For technical reasons we include the $0$-function, for which all coefficients $a_i$ are zero, in all sets
$\mathcal{C}_1$, $\mathcal{C}_2$ and $\mathcal{D}$. Being constant, the zero function is $n$-plateaued.

Let $Q(x)$ be in $\mathcal{C}_1$, i.e. $ Q(x)= {\rm Tr_n}(\sum_{i=1}^{\lfloor(n-1)/2\rfloor}a_ix^{2^i+1})$, $a_i \in{\mathbb F}_2$.
We associate to $Q$, the polynomial
\[ A(x) = \sum_{i=1}^{\lfloor(n-1)/2\rfloor}(a_ix^i+a_ix^{n-i}) \]
of degree at most $n-1$. For even $n$ we consider $Q(x) \in \mathcal{C}_2$, i.e. $Q(x) = {\rm Tr_n}(\sum_{i=1}^{(n/2)-1}a_ix^{2^i+1}) + {\rm Tr_{n/2}}(a_{n/2}x^{2^{n/2}+1})$,
$a_i \in{\mathbb F}_2$, and the associated polynomial
\[ A(x) = \sum_{i=1}^{(n/2)-1}(a_ix^i+a_ix^{n-i}) + a_{n/2}x^{n/2} \]
of degree at most $n-1$. \\
When $p$ is odd and $n$ is arbitrary we consider $Q(x) \in \mathcal{D}$, i.e. the quadratic function of the form $ Q(x)= {\rm Tr_n}(\sum_{i=0}^{\lfloor n/2\rfloor}a_ix^{p^i+1})$, $a_i \in{\mathbb F}_p$, and the associated polynomial
\[ A(x) = \sum_{i=0}^{\lfloor n/2\rfloor}(a_ix^i+a_ix^{n-i}) \]
of degree at most $n$.
With the standard Welch squaring method of the Walsh transform, one can easily see that in all three cases, the quadratic function $Q$
is $s$-plateaued if and only if
\[ s = \deg\big(\gcd(x^n-1,A(x))\big) \ , \]
see also \cite{hk,kgs,lhz,yg}.
We observe that $A(x) = x^dh(x)$, where $d$ is a non-negative integer and $h$ is a self-reciprocal polynomial of degree $n-2d$. Note that $d$ is a positive integer in the case $p=2$.
When $Q(x)\in \mathcal{C}_1$ or $Q(x)\in \mathcal{C}_2$, and hence $Q$ is a Boolean function, the polynomial $\gcd(x^n+1,A(x))$ is also self-reciprocal, and $A(x)$
can be written as
\[ A(x) = x^df(x)g(x) \ , \]
where $f$ is a self-reciprocal divisor of $x^n+1$ of degree $s$, and $g$ is a self-reciprocal polynomial with degree smaller than
$n-s$, satisfying $\gcd(g,(x^n+1)/f) = 1$. \\
When $p$ is odd, then $x^n-1 = (x-1)\psi(x)$, where $\psi(x) = 1+x+\cdots+x^{n-1}\in{\mathbb F}_p[x]$ is self-reciprocal.
Hence $\gcd(x^n-1,A(x)) = (x-1)^\epsilon f(x)$, $\epsilon\in\{0,1\}$, for a self-reciprocal divisor $f$ of $x^n-1$. Thus $A(x)$
can be written as
\[ A(x) = x^d(x-1)^\epsilon f(x)g(x) \ , \]
where $g$ satisfies $\gcd(g,(x^n-1)/((x-1)^\epsilon f)) = 1$. \\
Obviously the factorization of $x^n+1$ and $\psi(x)$ into self-reciprocal factors plays an important role. In accordance
with \cite{mt,mrt}, for a prime power $q$, we call a self-reciprocal polynomial $f\in{\mathbb F}_q[x]$ {\it prime self-reciprocal} if
\begin{itemize}
\item[(i)] $f$ is irreducible over ${\mathbb F}_q$, or
\item[(ii)] $f=ugg^*$, where $g$ is irreducible over ${\mathbb F}_q$, the polynomial $g^*\ne g$ is the reciprocal
of $g$ and $u\in{\mathbb F}_q^*$ is a constant.
\end{itemize}
To analyse the factorization of $x^n+1$ and $(x^n-1)/(x-1)$ into prime self-reciprocal polynomials, we recall the canonical
factorization of $x^n-1$ into irreducible polynomials. Since $x^n-1 = (x^m-1)^{p^v}$ if $n = mp^v$,
$\gcd(m,p) = 1$, we can assume that $n$ and $p$ are relatively prime.
Let $\alpha$ be a primitive $n$th root of unity in an extension field of ${\mathbb F}_p$, and let
$C_j = \{jp^k \bmod n\;:\; k\in{\mathbb N}\}$ be the {\it cyclotomic coset} of $j$ modulo $n$ (relative to powers of $p$).
Then $x^n-1 \in{\mathbb F}_p[x]$ can be factorized into irreducible polynomials as
\[ x^n-1 = \prod_{t=1}^hf_t(x)\quad\mbox{with}\quad f_t(x) = \prod_{i\in C_{j_t}}(x-\alpha^i), \]
where $C_{j_1},\ldots,C_{j_h}$ are the distinct cyclotomic cosets modulo $n$. \\
It is observed in \cite{mt,mrt} that, when $p$ is odd, an irreducible factor $f_t(x) = \prod_{i\in C_{j_t}}(x-\alpha^i)$ of $x^n-1$,
different from $x-1$, is self-reciprocal if and only if $C_{j_t}$ contains with $i$, its additive
inverse $-i$ modulo $n$. Otherwise there exists a cyclotomic coset $C_{-j_t}$, which consists of the additive inverses
of the elements of $C_{j_t}$, and the polynomial $f_t^*(x) = \prod_{i\in C_{-j_t}}(x-\alpha^i)$, which is the reciprocal of
$f_t$. In this case $f_tf_t^*$ is a prime self-reciprocal divisor of $x^n-1$. \\
Most of our results are expressed in terms of the degrees of the prime self-reciprocal
factors of $x^n-1$. We remark that by Lemma 2 in \cite{mt}, the cardinalities of the
cyclotomic cosets modulo $n$, and the degrees of the prime self-reciprocal divisors of $x^n-1$ can be obtained directly
from the factorization of $n$.

As explained above our aim is to determine the
generating polynomials $\mathcal{G}_n(z)$ and $\mathcal{H}_n(z)$ for even $n$, and $\mathcal{G}_n^{(p)}(z)$ for $n = p^vm$, $v>0$.
This enables us to solve the problem of enumerating
 quadratic functions in the sets $\mathcal{C}_1$, $\mathcal{C}_2$ and $\mathcal{D}$ with prescribed $s$.
We adapt the number theoretical approach used in \cite[Section V]{mrt}, by which the generating
polynomial $\mathcal{G}_n(z)$ is obtained to yield the number of $s$-plateaued quadratic functions in $\mathcal{C}_1$ for the
two cases; odd $n$ and $n=2m$, where $m$ is odd. We start by giving some definitions and lemmas.

For a (self-reciprocal) polynomial $f\in \mathbb{F}_{p}[x]$ we define
\begin{align*}
& C(f):=\lbrace g\in \mathbb{F}_{p}[x]\; |\; g \text{ is self-reciprocal},\;\deg(g)\;\text{is even, and }\mathrm{deg}(g) <\mathrm{deg}(f)  \rbrace \ ,\\
& K(f):= \lbrace g\in C(f) \; |\; \mathrm{gcd}(g(x),f(x))=1 \rbrace  \ ,\;\;\text{and}\\
& \phi_{p}(f):=|K(f)| \ .
\end{align*}
Let $f$ be a monic self-reciprocal polynomial in $\mathbb{F}_{p}[x]$ with even degree. Let $f=r_{1}^{e_{1}}\cdots r_{k}^{e_{k}}$
be the factorization of $f$ into distinct monic self-reciprocal polynomials all of {\it even degree}, i.e. either
$r_1 = (x+1)^2$ and $r_j$, $2\le j\le k$, are prime self-reciprocal polynomials, or $r_j$ is prime self-reciprocal
for all $1\le j\le k$. Then we define the (following variant of the M\"obius) function $\mu_p$ as
\begin{align*}
\mu_{p}(f):=\left\lbrace \begin{array}{ll}
(-1)^{k}& \text{ if } e_{1}=\cdots=e_{k}=1 ,  \\
0& \text{ otherwise.}
\end{array} \right.
\end{align*}
As for the classical M\"obius function on the set of positive integers, we have
\[ \sum_{d|f}\mu_p(d) = \left\{\begin{array}{ll}
1 & \quad\mbox{if}\; f=1,\\
0 & \quad\mbox{otherwise,}
\end{array}\right. \]
where the summation is over all monic self-reciprocal divisors $d$ of $f$ of even degree.
\begin{remark}
Compare $\mu_p$ with the "M\"obius function" used in \cite{mrt}, which is
defined on the set of all self-reciprocal polynomials.
Here considering the M\"obius function on the set of self-reciprocal polynomials of {\it even degree}, where the set of
the prime elements is the union of $\{(x+1)^2\}$ and the set of prime self-reciprocal polynomials of even degree, proved to be
advantageous and has facilitated obtaining $\mathcal{G}_n(z)$, $\mathcal{H}_n(z)$ and $\mathcal{G}_n^{(p)}(z)$
in full generality.
\end{remark}
The next lemma is Lemma 8 in \cite{mrt}, except that the condition on a self-reciprocal polynomial "not to be divisible by $x+1$"
is replaced by the condition that it is of "even degree". The proof is similar to the one in \cite{mrt}
with this slight modification and hence
we omit it.
\begin{lemma}\cite[Lemma 8]{mrt}
\label{13-8}
Let $f\in \mathbb{F}_{p}[x]$ be a monic self-reciprocal polynomial whose degree is a positive even integer. Then
\begin{align*}
\sum_{d|f}\phi_{p}(d)=p^{\frac{\mathrm{deg}(f)}{2}}-1 \ ,
\end{align*}
where the sum runs over all monic self-reciprocal divisors $d$ of $f$ of even degree.
\end{lemma}
The next lemma is again similar to Lemma 9 in \cite{mrt}, except that polynomials involved are of even degree. We give the proof for the convenience of the reader.
\begin{lemma}\cite[Lemma 9]{mrt}
\label{13-9}
Let $f,f_1,f_2\in \mathbb{F}_{p}[x]$ be monic self-reciprocal polynomials whose degrees are positive even integers.
\begin{itemize}
\item [(i)] We have
\begin{align*}
\phi_{p}(f)=\sum_{d|f}\mu_{p}(d)p^{\frac{\mathrm{deg}(f)-\mathrm{deg}(d)}{2}} \ ,
\end{align*}
where the sum runs over all monic self-reciprocal divisors $d$ of $f$ of even degree.
\item [(ii)] If $\mathrm{gcd}(f_1,f_2)=1$, then
\begin{align*}
\phi_{p}(f)=\phi_{p}(f_1)\phi_{p}(f_2) \ .
\end{align*}
\end{itemize}
\end{lemma}
{\it Proof.}
Taking the summation over all monic self-reciprocal divisors $d$ of $f$ of even degree, by Lemma \ref{13-8} we get
\begin{align*}
& \sum_{d|f}\mu_p(d)\left(p^{\frac{\deg(f)-\deg(d)}{2}}-1\right) =
\sum_{d|f}\mu_p\left(\frac{f}{d}\right)\left(p^{\frac{\deg(d)}{2}}-1\right)  \\
& =\sum_{d|f}\mu_p\left(\frac{f}{d}\right)\sum_{d_1|d}\phi_p(d_1) =
\sum_{d_1|f}\phi_p(d_1)\sum_{g|\frac{f}{d_1}}\mu_p(g) = \phi_p(f)\ ,
\end{align*}
where in the last step we use the fact that the inner sum is $1$ for $d_1 = f$ and $0$ otherwise. With
\begin{eqnarray*}
\phi_p(f) & = & \sum_{d|f}\mu_p(d)\left(p^{\frac{\deg(f)-\deg(d)}{2}}-1\right) \\
& = & \sum_{d|f}\mu_p(d)p^{\frac{\deg(f)-\deg(d)}{2}} - \sum_{d|f}\mu_p(d) =
\sum_{d|f}\mu_p(d)p^{\frac{\deg(f)-\deg(d)}{2}},
\end{eqnarray*}
we finish the proof for (i). \\
If $\gcd(f_1,f_2) = 1$, then $\mu_p(f_1f_2) = \mu_p(f_1)\mu_p(f_2)$.
Taking the summation over all monic self-reciprocal divisors $d_i$ of $f_i$
with $\deg(d_i)$ is even, $i=1,2$, we then have
\begin{align*}
\phi_p(f_1)\phi_p(f_2)& = \sum_{d_1|f_1}\mu_p(d_1)p^{\frac{\deg(f_1)-\deg(d_1)}{2}}
\sum_{d_2|f_2}\mu_p(d_2)p^{\frac{\deg(f_2)-\deg(d_2)}{2}}  \\
& = \sum_{d_1|f_1\atop d_2|f_2}\mu_p(d_1d_2)p^{\frac{\deg(f_1f_2)-\deg(d_1d_2)}{2}} =
\sum_{d|f}\mu_p(d)p^{\frac{\deg(f)-\deg(d)}{2}}\ ,
\end{align*}
which shows (ii). \hfill$\Box$\\[.5em]
For an integer $t$, we define $\mathcal{N}_{n}(f;t)$ by
\begin{align}
\label{Nft}
\mathcal{N}_{n}(f;t)=\left\lbrace \begin{array}{ll}
1 & \text{ if } t=0 \\
\sum_{d|f, \mathrm{deg}(d)=t} \phi_{p}(d)& \text{ if $t>0$ is even}  \\
0 & \text{ otherwise,}
\end{array}  \right.
\end{align}
where the above sum runs over all monic self-reciprocal divisors $d$ of $f$ of degree $t$. Then we define the generating
function $\mathcal{G}_n(f;z)$ for the distribution of the values $\mathcal{N}_{n}(f;t)$ by
\begin{align*}
\mathcal{G}_n(f;z)=\sum \mathcal{N}_{n}(f;t)z^{t} \ .
\end{align*}
We note that $\mathcal{G}_n(f;z)$ is a polynomial by definition of $\mathcal{N}_{n}(f;t)$.

The next lemma and its proof resembles Lemma 10 in \cite{mrt} for $p=2$.
\begin{lemma}\cite[Lemma 10]{mrt}
\label{Gmulti}
Let $f=f_1f_2$ for two self-reciprocal polynomials $f_1,f_2$ of even degree. If $\mathrm{gcd}(f_1,f_2)=1$, then
\begin{align*}
\mathcal{G}_n(f;z)=\mathcal{G}_n(f_1;z)\mathcal{G}_n(f_2;z)\ .
\end{align*}
\end{lemma}
{\it Proof.}
We have to show that for each $t\ge0$,
\[ \mathcal{N}_n(f;t) =\sum_{0\le t_1\le t}\mathcal{N}_n(f_1;t_1)\mathcal{N}_n(f_2;t-t_1) \ .\]
For $t=0$, $t>\deg(f)$ and $t$ odd this is trivial. Assume that $1\le t\le \deg(f)$ is even.
Taking into account that $\phi_p(1) = 0$, by Lemma \ref{13-9}(ii), and the definition of $\mathcal{N}_n(f;t)$ we obtain
\begin{eqnarray*}
& & \sum_{0\le t_1\le t}\mathcal{N}_n(f_1;t_1)\mathcal{N}_n(f_2;t-t_1) =
\mathcal{N}_n(f_1;0)\mathcal{N}_n(f_2;t) + \mathcal{N}_n(f_1;t)\mathcal{N}_n(f_2;0) \\
& &  + \sum_{1< t_1< t-1\atop\text{even}}\sum_{d_1|f_1\atop\deg(d_1)=t_1}\phi_p(d_1)\sum_{d_2|f_2\atop\deg(d_2) = t-t_1}\phi_p(d_2) \\
& = & \mathcal{N}_n(f_2;t) + \mathcal{N}_n(f_1;t) +
\sum_{1< t_1< t-1\atop\text{even}}\sum_{d_1|f_1;\deg(d_1) = t_1\atop d_2|f_2;\deg(d_2) = t-t_1}\phi_p(d_1d_2) \\
& = & \mathcal{N}_n(f_2;t) + \mathcal{N}_n(f_1;t) +
\sum_{d|f\atop \deg(d) = t}\phi_p(d) - \sum_{d_1|f_1\atop \deg(d_1) = t}\phi_p(d_1) -
\sum_{d_2|f_2\atop \deg(d_2) = t}\phi_p(d_2) \\
& = & \mathcal{N}_n(f;t).
\end{eqnarray*}
\hfill$\Box$
\begin{lemma}
\label{simpleG}
Let $r$ be a prime self-reciprocal polynomial of even degree. Then
\[ \mathcal{G}_{n}(r^k;z) = 1+\sum_{j=1}^{k}(p^{\frac{\mathrm{deg}(r^{j})}{2}}-p^{\frac{\mathrm{deg}(r^{j})-\mathrm{deg}(r)}{2}})z^{j\mathrm{deg}(r)}. \]
For an even integer $k$ we have
\[ \mathcal{G}_{n}((x+1)^{k};z) = \mathcal{G}_{n}((x-1)^{k};z) = 1+\sum_{j=1}^{\frac{k}{2}}p^{j-1}(p-1)z^{2j}. \]
\end{lemma}
{\it Proof.}
If $r$ is a prime self-reciprocal polynomial of even degree, then
\begin{eqnarray*}
 \mathcal{G}_{n}(r^{k};z)   &=&   \sum_{t:\text{ even}}\mathcal{N}_{n}(r^{k};t)z^{t}
 = 1+\sum_{t:\text{ even},\; t>0}\left(\sum_{d|r^{k}; \; \mathrm{deg}(d)=t}\phi_p(d)\right)z^{t}\\
   &=&1+ \sum_{j= 1}^{k}\phi_p(r^{j})z^{j\mathrm{deg}(r)}=
 1+  \sum_{j= 1}^{k}\left(\sum_{d|r^{j}}\mu_{p}(d)p^{\frac{\mathrm{deg}(r^{j})-\mathrm{deg}(d)}{2}}\right)z^{j\mathrm{deg}(r)} \\
   &=& 1+\sum_{j=
   1}^{k}\left(p^{\frac{\mathrm{deg}(r^{j})}{2}}-p^{\frac{\mathrm{deg}(r^{j})-\mathrm{deg}(r)}{2}}\right)z^{j\mathrm{deg}(r)}.
\end{eqnarray*}
The expression for $\mathcal{G}_{n}(((x-1)^2)^{k/2};z)$ follows as a special case, and $\mathcal{G}_{n}(((x+1)^2)^{k/2};z)$
is determined in the same way since the sum in $(\ref{Nft})$ is over self-reciprocal polynomials $d$ of even degree dividing $f$, and
$\mathcal{N}(f;t) = 0$ for odd $t$.
\hfill$\Box$

\section{Distribution of the nonlinearity in $\mathcal{C}_1$ and $\mathcal{C}_2$}
\label{secB}

Our aim in this section is to determine both $\mathcal{G}_n(z)$ and $\mathcal{H}_n(z)$
for all (even) integers $n$. By Remark \ref{rot.symm}, this does not only enable us to completely describe the distribution of the nonlinearity
for the set of idempotent quadratic Boolean functions, but also
for the set of rotation symmetric quadratic Boolean functions.

We first express our counting functions $\mathcal{N}_{n}(s)$ and $\mathcal{M}_{n}(s)$ in terms of $\mathcal{N}(f;t)$.
\begin{proposition}
\label{N+M}
Let $n$ be even and let $\mathcal{N}_{n}(s)$ and $\mathcal{M}_{n}(s)$ be the number of $s$-plateaued quadratic functions in $\mathcal{C}_1$
and $\mathcal{C}_2$, respectively. Then
\begin{equation*}
\mathcal{N}_{n}(s)=\mathcal{N}_{n}\left(\frac{x^{n}+1}{(x+1)^{2}};n-s\right)\quad\mbox{and}\quad
\mathcal{M}_{n}(s)=\mathcal{N}_{n}(x^{n}+1;n-s) \ .
\end{equation*}
\end{proposition}
{\it Proof.} The statement is clear when $n-s$ is zero or odd. Suppose $n-s > 0$ is even.
First we consider quadratic functions $Q \in \mathcal{C}_1$. For the corresponding associate polynomial $A(x)$
we have
$\mathrm{gcd}(A(x),x^{n}+1)=(x+1)^{2}f_{1}(x)$ for some self-reciprocal divisor $f_{1}$ of $(x^n+1)/(x^2+1)$
of degree $s-2$, i.e.
\begin{equation*}
    A(x)=x^c(x+1)^{2}f_{1}(x)g(x)
\end{equation*}
for an integer $c\ge 1$ and a self-reciprocal polynomial $g$ of even degree less than
$n-s$, which is relatively prime to
$d(x)=\frac{x^{n}+1}{(x+1)^{2}f_{1}(x)}$. In other words, $g$ is any of the $\phi_2(d)$
polynomials in $K(d)$.
To determine the number $\mathcal{N}_n(s)$ we consider all
divisors $(x+1)^2f_1(x)$ of $x^n+1$ of degree $s$, or equivalently, all divisors $d(x)$ of $(x^n+1)/(x^2+1)$
of degree $n-s$. Hence we obtain $\mathcal{N}_n(s)$ as
\begin{equation*}
\mathcal{N}_n(s) = \sum_{d|\frac{x^{n}+1}{(x+1)^{2}} \text{ and
}\mathrm{deg}(d)=n-s}\phi_{2}(d) \ .
\end{equation*}
If $Q\in\mathcal{C}_2$, then the associated polynomial $A(x)$ satisfies
$\mathrm{gcd}(A(x),x^{n}+1)=f_{1}(x)$, where $f_{1}$ is a self-reciprocal polynomial of degree $s$, i.e.
\begin{equation*}
A(x)=x^cf_{1}(x)g(x)
\end{equation*}
for an integer $c\ge 1$ and a self-reciprocal polynomial $g$ of even degree less than
$n-s$ with
$\mathrm{gcd}\left(g,(x^{n}+1)/f_{1}(x)\right)=1$. Therefore $g\in K(d)$.
As a consequence, the number of $s$-plateaued quadratic functions in $\mathcal{C}_2$ is
\begin{equation*}
\mathcal{M}_n(s) = \sum_{d|(x^{n}+1) \text{ and
}\mathrm{deg}(d)=n-s}\phi_{2}(d) \ ,
\end{equation*}
which finishes the proof. \hfill$\Box$ \\[.5em]
The following is the main theorem of this section.
\begin{theorem}
\label{G}
Let $n = 2^vm$, $m$ odd, $v>0$, and let $x^n+1 = (x+1)^{2^v}r_1^{2^v}\cdots r_k^{2^v}$, where $r_1,\ldots,r_k$ are prime self-reciprocal
polynomials of even degree. We set
\begin{align*}
G_i(z):=1+\sum_{j=1}^{2^v}\left(2^{\frac{j\deg(r_i)}{2}}-2^{\frac{(j-1)\deg(r_i)}{2}}\right)z^{j\deg(r_i)} \ .
\end{align*}
Then the generating polynomial $\mathcal{G}_n(z) = \sum_{t=0}^n\mathcal{N}_n(n-t)z^t$
is given by
\[ \mathcal{G}_n(z) = \left(1+\sum_{j=1}^{2^{v-1}-1}2^{j-1}z^{2j}\right)\prod_{i=1}^k G_i(z)
\ , \]
and the generating polynomial $\mathcal{H}_n(z) = \sum_{t=0}^n\mathcal{M}_n(n-t)z^t$ is given by
\[ \mathcal{H}_n(z) = \left(1+\sum_{j=1}^{2^{v-1}}2^{j-1}z^{2j}\right)\prod_{i=1}^k G_i(z) \ . \]
\end{theorem}
{\it Proof.}
By Proposition \ref{N+M} and Lemma \ref{Gmulti} we have
\[ \mathcal{G}_n(z) = \mathcal{G}_{n}(\frac{x^n+1}{x^2+1};z)=
\mathcal{G}_{n}((x+1)^{2(2^{v-1}-1)};z)\prod_{i=1}^{k}\mathcal{G}_{n}(r_{i}^{2^{v}};z)\ , \]
and
\[ \mathcal{H}_n(z) = \mathcal{G}_{n}(x^n+1;z)=
\mathcal{G}_{n}((x+1)^{2(2^{v-1})};z)\prod_{i=1}^{k}\mathcal{G}_{n}(r_{i}^{2^{v}};z)\ . \]
For a prime self-reciprocal polynomial $r$ of even degree, Lemma \ref{simpleG} for $p=2$ gives
\begin{align*}
& \mathcal{G}_{n}(r^{2^{v}};z) =
1+ \sum_{j=1}^{2^{v}}(2^{\frac{j\mathrm{deg}(r)}{2}}-2^{\frac{(j-1)\mathrm{deg}(r)}{2}})z^{j\mathrm{deg}(r)},\:\mbox{and} \\
& \mathcal{G}_{n}((x+1)^{2e};z) = 1+\sum_{j=1}^e2^{j-1}z^{2j}.
\end{align*}
Combining those formulas yields the assertion. \hfill$\Box$
\begin{remark}
Putting $v=1$ and $m > 1$
in Theorem \ref{G}, one obtains
$\mathcal{G}_n(z)$ in
Theorem 5(ii) of \cite{mrt}. Note that the Theorem 5(ii) in \cite{mrt} contains an
additional factor $2$, since a quadratic function there may also have
a linear term. Similarly the expression for $\mathcal{G}_n(z)$ with $m=1$ gives Theorem 6 in \cite{mt}.
\end{remark}
As a corollary of Theorem \ref{G} we obtain the number $\mathcal{M}_{n}(0)$ of bent functions in the set $\mathcal{C}_2$ as the coefficient of $z^n$
in $\mathcal{H}_n(z)$ for arbitrary (even) integers $n$. This complements the results of \cite{hf,yg}, where $\mathcal{M}_{n}(0)$ has
been presented for the special cases $n = 2^vp^r$, where $p$ is a prime such that the order of $2$ modulo $p$ is $p-1$ or
$(p-1)/2$.
\begin{corollary}
Let $n = 2^vm$, $m$ odd, $v>0$, and let $x^n+1 = (x+1)^{2^v}r_1^{2^v}\ldots r_k^{2^v}$, where $r_1,\cdots,r_k$ are prime self-reciprocal
polynomials of even degree. Then the number of bent functions in $\mathcal{C}_2$ is
\[ \mathcal{M}_n(0) = 2^{2^{v-1}}\prod_{i=1}^k
\left(2^{\frac{2^v\deg(r_i)}{2}}-2^{\frac{(2^v-1)\deg(r_i)}{2}}\right)\ , \]
which is also the number of rotation symmetric quadratic bent functions in $n$ variables.
\end{corollary}
Similarly one may obtain $\mathcal{M}_n(s)$ and $\mathcal{N}_n(s)$ for other small values of $s$.
The number of semi-bent function in $\mathcal{C}_1$ for even $n$, and in $\mathcal{C}_2$ is presented in the next corollary.
Note that the number of semi-bent functions in $\mathcal{C}_1$ when $n$ is odd is given in \cite[Corollary 7]{mrt}.
\begin{corollary}
Let $n = 2^vm$, $m$ odd, $v>0$, and let $x^n+1 = (x+1)^{2^v}r_1^{2^v}\ldots r_k^{2^v}$, where $r_1,\cdots,r_k$ are prime self-reciprocal
polynomials of even degree.
The number of semi-bent functions in $\mathcal{C}_1$ is
\[ \mathcal{N}_n(2) = 2^{2^{v-1}-2}\prod_{i=1}^k\left(2^{\frac{2^v\deg(r_i)}{2}}-2^{\frac{(2^v-1)\deg(r_i)}{2}}\right). \]
The number of semi-bent functions in $\mathcal{C}_2$ is
\begin{itemize}
\item[-] $\mathcal{M}_n(2) = \mathcal{N}_n(2)$ if $3$ does not divide $n$,
\item[-] $\mathcal{M}_n(2) = \mathcal{N}_n(2) + 2^{2^{v-1}-1}2^{2^v-2}\prod_{r_i\ne x^2+x+1}^k\left(2^{\frac{2^v\deg(r_i)}{2}}-2^{\frac{(2^v-1)\deg(r_i)}{2}}\right)$ if $3$ divides $n$.
\end{itemize}
\end{corollary}
{\it Proof.}
The corollary follows from Theorem \ref{G} with the observation that $x^2+x+1$ divides $x^n-1$ if and only if $3$ divides $n$.
\hfill$\Box$
\begin{remark}
In \cite[Theorem 12]{kkos}, for $n\equiv 0 \bmod 3$ an expression for the number $\mathcal{K}$ of semi-bent functions in $\mathcal{C}_2\setminus C_1$
is given, which involves a M\"obius function on the set of monic self-reciprocal polynomials. Our formula
\[ \mathcal{K} = 2^{2^{v-1}-1}2^{2^v-2}\prod_{r_i\ne x^2+x+1}^k\left(2^{\frac{2^v\deg(r_i)}{2}}-2^{\frac{(2^v-1)\deg(r_i)}{2}}\right) \]
is more explicit.
\end{remark}
\begin{remark}
To completely describe the nonlinearity distribution in $\mathcal{C}_1$
and $\mathcal{C}_2$ it is inevitable to consider the generating polynomials. Otherwise, in order to determine $\mathcal{N}_n(s)$ or $\mathcal{M}_n(s)$ for a specific $s$,
one would first have to find {\it all} possible ways of expressing $s$ as a sum of degrees of polynomials in the
prime self-reciprocal factorization of $x^n+1$, which for general $n$ is illusive.
\end{remark}

\section{Weight distribution of subcodes of second order Reed-Muller codes}
\label{secRM}

Let $\mathcal{Q}$ be a set of quadratic functions, which do not contain linear or constant terms. Assume that $\mathcal{Q}$
is closed under addition. Denote the set
of affine functions from ${\mathbb F}_{2^n}$ to ${\mathbb F}_2$ by $\mathcal{A} = \{{\rm Tr_n}(bx)+c\; :\; b\in{\mathbb F}_{2^n},\; c\in{\mathbb F}_2\}$. Then the set
\[ \mathcal{Q} \oplus \mathcal{A} = \{Q(x)+l(x)\;:\; Q\in\mathcal{Q},\; l\in\mathcal{A}\} \]
gives rise to a linear subcode $\bar{R}_\mathcal{Q}$ of the second order Reed-Muller code $R(2,n)$, which
contains the first order Reed-Muller code $R(1,n)$ as a subcode. Clearly, we can write $\mathcal{Q} \oplus \mathcal{A}$
as the union $\mathcal{Q} \oplus \mathcal{A} = \cup_{Q\in\mathcal{Q}} Q+\mathcal{A}$ of (disjoint) cosets of $\mathcal{A}$.
To obtain the weight distribution of the code $\bar{R}_\mathcal{Q}$, it is sufficient to know the weight distribution for
each of these cosets.

It can be seen easily that the weight of the codeword $c_Q$ of a (quadratic) function $Q$
can be expressed in terms of the Walsh transform as
\[ wt(c_Q)=2^{n-1}-\frac{1}{2}\widehat{Q}(0) \ .\]
For a quadratic function $Q$
we define $Q_{b,c}(x) = Q(x) + {\rm Tr_n}(bx+c)$.
Using $\widehat{Q_{b,c}}(0)=(-1)^{{\rm Tr_n}(c)}\widehat{Q}(b)$ one can show that the weight distribution of the coset $Q+\mathcal{A}$
for an $s$-plateaued quadratic function $Q$ is as follows. There are
\begin{itemize}
\item[-] $2^{n-s}$ codewords of weight $2^{n-1}+2^{\frac{n+s}{2}-1}$,
\item[-] $2^{n-s}$ codewords of weight $2^{n-1}-2^{\frac{n+s}{2}-1}$, and
\item[-] $2^{n+1}-2^{n-s+1}$ codewords of weight $2^{n-1}$.
\end{itemize}
Hence, if one knows the number of $s$-plateaued quadratic functions in $\mathcal{Q}$ for every $s$, one can determine
the weight distribution of $\bar{R}_\mathcal{Q}$. \\
If $\mathcal{Q}$ is the set of all quadratic functions, then $\bar{R}_\mathcal{Q} = R(2,n)$.
The weight distribution of $R(2,n)$ is completely described in \cite{sb} by explicit, quite involved formulas.
Here we focus on the subcodes of $R(2,n)$, obtained from the sets $\mathcal{C}_1$ and $\mathcal{C}_2$, in other words from
the set of idempotent quadratic functions.
Putting $k=n-s$ (which is even), the observations above imply that the only weights that can occur are
$2^{n-1}$ and $2^{n-1}\pm 2^{n-1-\frac{k}{2}}$, $0\le k \le n$. Moreover, codewords of the weights $2^{n-1}+2^{n-1-\frac{k}{2}}$
and $2^{n-1}-2^{n-1-\frac{k}{2}}$ appear the same number of times. Hence to describe the weight distribution of the codes
$\bar{R}_\mathcal{C}$ we
may consider the polynomial $\mathcal{W}_\mathcal{C}(z) = \sum_{k=0}^nA^{\mathcal{C}}_kz^k$, where $A^{\mathcal{C}}_k$ is the
number of codewords in $\bar{R}_\mathcal{C}$ of weight $2^{n-1}\pm 2^{n-1-\frac{k}{2}}$. Again by the above observations,
$A^{\mathcal{C}_1}_k = \mathcal{N}_n(n-k)2^k$ and $A^{\mathcal{C}_2}_k = \mathcal{M}_n(n-k)2^k$. Consequently,
\begin{eqnarray}
\label{W=}
\nonumber
\mathcal{W}_{\mathcal{C}_1}(z) & = & \sum_{k=0}^nA^{\mathcal{C}_1}_kz^k = \sum_{k=0}^n\mathcal{N}_n(n-k)2^kz^k = \mathcal{G}_n(2z)\ , \\
\mathcal{W}_{\mathcal{C}_2}(z) & = & \sum_{k=0}^nA^{\mathcal{C}_2}_kz^k = \sum_{k=0}^n\mathcal{M}_n(n-k)2^kz^k = \mathcal{H}_n(2z)\ .
\end{eqnarray}
For the number $A^{\mathcal{C}_1}$ of codewords in $\bar{R}_{\mathcal{C}_1}$ of weight $2^{n-1}$ we have
\begin{eqnarray*}
A^{\mathcal{C}_1} & = & \sum_{k=0}^{n}{\mathcal{N}_{n}(n-k)(2^{n+1}-2^{k+1})}
=2^{n+1}\sum_{k=0}^{n}{\mathcal{N}_{n}(n-k)}-2\sum_{k=0}^{n}{\mathcal{N}_{n}(n-k)2^{k}} \\
& = & 2^{n+1}\mathcal{G}_{n}(1)-2\mathcal{G}_{n}(2) \ .
\end{eqnarray*}
Similarly, $A^{\mathcal{C}_2} = 2^{n+1}\mathcal{H}_{n}(1)-2\mathcal{H}_{n}(2)$. \\
The following theorem describes the weight distribution of the codes $\bar{R}_\mathcal{C}$.
\begin{theorem}
Let $n = 2^tm$, $m$ odd, and let $x^n+1 = (x+1)^{2^t}r_1^{2^t}\cdots r_l^{2^t}$ for prime self-reciprocal polynomials
$r_1,\ldots,r_l$ of even degree. Then for even $n$
\[ \mathcal{W}_{\mathcal{C}_2}(z) = \sum_{k=0}^nA^{\mathcal{C}_2}_kz^k =
\left(1+\sum_{j=1}^{2^{t-1}}2^{3j-1}z^{2j}\right)\prod_{i=1}^l W_i(z)
 \ , \]
where
\begin{align*}
W_i(z)=1+\sum_{j=1}^{2^t}\left(2^{\frac{3j\deg(r_i)}{2}}-2^{\frac{(3j-1)\deg(r_i)}{2}}\right)z^{j\deg(r_i)} \ ,
\end{align*}
and
\begin{eqnarray*}
A^{\mathcal{C}_2} & = & 2^{n+1+2^{t-1}}\prod_{i=1}^l\left(1+\sum_{j=1}^{2^t}\left(2^{\frac{j\deg(r_i)}{2}}-2^{\frac{(j-1)\deg(r_i)}{2}}\right)\right) \\
& & - \frac{2^{3(2^{t-1}+1)}+6}{7}\prod_{i=1}^l\left(1+\sum_{j=1}^{2^t}\left(
2^{\frac{3j\deg(r_i)}{2}}-2^{\frac{(3j-1)\deg(r_i)}{2}}\right)\right)\ .
\end{eqnarray*}
When $t=0$, i.e., $n$ is odd, we have
\begin{equation}
\label{WB}
\mathcal{W}_{\mathcal{C}_1}(z) = \sum_{k=0}^nA^{\mathcal{C}_1}_kz^k = \prod_{i=1}^{l}\left[1+(2^{3\mathrm{deg}(r_{i})/2}-2^{\mathrm{deg}(r_{i})})z^{\mathrm{deg}(r_{i})}\right]\ ,\;\mbox{and}
\end{equation}
\[ A^{\mathcal{C}_1} = 2^{\frac{3n+1}{2}} - 2\prod_{i=1}^{l}\left(1+(2^{3\mathrm{deg}(r_{i})/2}-2^{\mathrm{deg}(r_{i})})\right)\ . \]
\end{theorem}
{\it Proof.} By using $(\ref{W=})$, the formulas for $\mathcal{W}_{\mathcal{C}_1}(z)$ and $\mathcal{W}_{\mathcal{C}_2}(z)$ follow from
the generating function
$\mathcal{G}_n(z) = \prod_{i=1}^{l}\left[1+(2^{\mathrm{deg}(r_{i})/2}-1)z^{\mathrm{deg}(r_{i})}\right]$ when $n$ is odd
(see Theorem 5(i) in \cite{mrt}) and Theorem \ref{G}. The formulas for $A^{\mathcal{C}_1}$ and $A^{\mathcal{C}_2}$ are obtained by
expanding $2^{n+1}\mathcal{G}_{n}(1)-2\mathcal{G}_{n}(2)$ and $2^{n+1}\mathcal{H}_{n}(1)-2\mathcal{H}_{n}(2)$.
\hfill$\Box$
\begin{remark}
When $n$ is odd, the code $\bar{R}_{\mathcal{C}_1}$ has $2^{(3n+1)/2}$ codewords, i.e. $\dim(\bar{R}_{\mathcal{C}_1}) = (3n+1)/2$.
Observing that the coefficient of $z^{k}$ in $(\ref{WB})$ is not zero if and only if
$k=\sum_{r_{i}\in\{r_{1},\ldots, r_{l}\}}\mathrm{deg}(r_{i})$,
for $r=\mathrm{min}\{\deg(r_{i})\}_{i=1}^{l}$ we conclude that $\bar{R}_{\mathcal{C}_1}$ is a $[2^{n},(3n+1)/2,2^{n-1}-2^{n-1-\frac{r}{2}} ]$ code.
.
\end{remark}

\section{Enumeration of $s$-plateaued quadratic functions for odd characteristic}

In this section we apply our method to quadratic functions in $\mathcal{D}$.
Recall that results on $\mathcal{D}$ translate to results on the set of rotation
symmetric functions from ${\mathbb F}_p^n$ to ${\mathbb F}_p$.
As we will see, determining the generating function in odd characteristic is considerably more involved.
We can restrict ourselves to the case $\gcd(n,p) > 1$ since the case $\gcd(n,p) = 1$ is dealt with in
\cite{mrt} with a different method which employs discrete Fourier transform. We emphasize that the method of \cite{mrt}
is not applicable to the case $\gcd(n,p) > 1$.

Recall that
to $Q(x) = \mathrm{Tr}_n \left(\sum_{i=0}^{\lfloor n/2\rfloor}a_{i}x^{p^{i}+1} \right) \in \mathcal{D}$, the associate is
\begin{equation*}
    A(x) = \sum_{i=0}^{\lfloor n/2\rfloor}(a_ix^i+a_ix^{n-i}) \ ,
\end{equation*}
which is a polynomial of degree at most $n$.
We treat the cases of odd and even $n$ separately.

\subsection*{The case of odd $n$}

In this case the factorization of $x^n-1$ into prime self-reciprocal divisors is given by
\begin{equation*}
x^n-1=(x-1)^{p^{v}}r_{1}^{p^{v}}\cdots r_{k}^{p^{v}} \ .
\end{equation*}
Firstly we note that $x^n-1$ is not divisible by $x+1$ as $n$ is an odd
integer, and hence each $r_{i}$, $1\le i\le k$, is a prime self-reciprocal polynomial of even degree.
Write $A(x)$ as
\begin{equation*}
    A(x) = \sum_{i=0}^{\lfloor
    n/2\rfloor}(a_ix^i+a_ix^{n-i})=x^{c}h(x) \ ,
\end{equation*}
where $h(x)$ is a self-reciprocal polynomial of degree $n-2c$. Since
$n$ is odd, also the degree of $h$ is odd, and hence $x+1$ is a factor of $A(x)$.
In fact, $x+1$ must appear as an odd power in the factorization of $A(x)$. In particular,
\begin{equation*}
    A(x) =x^{c}(x+1)\varrho(x)
\end{equation*}
for a self-reciprocal polynomial $\varrho(x)$ of even degree $n-2c-1$.
As a consequence,
\begin{equation*}
\mathrm{gcd}( A(x),x^n-1)=\mathrm{gcd}( \varrho(x),x^n-1)=
(x-1)^{\epsilon}f_{1}(x) \ ,
\end{equation*}
for a self-reciprocal polynomial $f_{1}$ of even degree, and some $\epsilon\in \{0,1\}$. That is,
\begin{equation*}
\varrho(x)=(x-1)^{\epsilon}f_{1}(x)g_{1}(x) \; \text{with} \;
\mathrm{gcd}\left(\frac{x^n-1}{(x-1)^{\epsilon}f_{1}(x)},g_{1}(x)\right)=1 \ .
\end{equation*}

We will frequently use the following observation, which immediately follows from the definition of $\phi_p$.
\begin{proposition}\label{d}
For a self-reciprocal polynomial $d$ of even degree we have
\begin{equation*}
\phi_{p}((x\pm 1)d)=\phi_{p}((x\pm 1)^2 d) \ .
\end{equation*}
\end{proposition}

We now represent the counting function $\mathcal{N}^{(p)}_{n}(s)$ in
terms of the function $\mathcal{N}_{n}(f;t)$ in $(\ref{Nft})$.
The arguments are more complicated than in the even characteristic case, for instance,
here the distinction between odd and even $n$ is required.
As we see in the proposition below, for odd $n$ we also need to consider odd and
even $s$ separately. In the next subsection,
where $n$ is even, we have to treat four cases.
\begin{proposition}\label{s-n-odd} Let $n$ be an odd integer such that the $p$-adic valuation of $n$ is $v_{p}(n)=v$.
The number $\mathcal{N}^{(p)}_{n}(s)$ of quadratic $s$-plateaued functions in $\mathcal{D}$ is given by
{ \footnotesize \begin{equation*}
\mathcal{N}^{(p)}_{n}(s)=\left\{\begin{array}{ll}
                        \mathcal{N}_{n}(\frac{x^n-1}{(x-1)^{p^{v}}};n-s)    & \text{ if $s$ is odd,} \\
                        \mathcal{N}_{n}((x-1)(x^n-1);n-s+1) - \mathcal{N}_{n}(\frac{x^n-1}{(x-1)^{p^v}};n-s+1)     & \text{ if $s$ is even.}
                          \end{array}
 \right.
\end{equation*}}
\end{proposition}
\begin{proof}
Suppose that $\mathrm{gcd}( A(x),x^n-1)=(x-1)f_{1}(x) $, i.e.
  $\epsilon=1$. This holds if only if $s$ is odd. In this case, $\mathrm{deg}(g_{1})$ is odd and $g_{1}(x)$ is
  divisible by $(x-1)$ since $\varrho(x)$ is a self-reciprocal polynomial of
  even degree, i.e. $g_{1}(x)=(x-1)g(x)$ for some self-reciprocal polynomial $g$ of even degree. Furthermore we know that
  $\mathrm{gcd}(\frac{x^n-1}{(x-1)f_{1}(x)},g_{1}(x))=1$, and
  therefore $x-1$ is not a factor of $\frac{x^n-1}{(x-1)f_{1}(x)}$.
Consequently, $(x-1)^{p^{v}-1}$ must divide $f_{1}(x)$. Hence $h(x)$ can be expressed as
  \begin{equation*}
 h(x)=(x+1)(x-1)^{p^v+1}f(x)g(x) \; \;\text{with} \;\;
\mathrm{gcd}\left(\frac{x^n-1}{(x-1)^{p^v}f(x)},g(x)\right)=1 \ ,
  \end{equation*}
where $g$ is a self-reciprocal polynomial of even degree smaller than $n-s$, and hence $g\in K\left( \frac{x^n-1}{(x-1)^{p^v}f(x)} \right)$.
Furthermore, each divisor $d$ of $\frac{x^n-1}{(x-1)^{p^v}}$ of degree $n-s$ uniquely determines $f(x)$. As a result, there exist
\begin{equation*}
\sum_{d|\frac{x^n-1}{(x-1)^{p^{v}}};\;
\mathrm{deg}(d)=n-s}\phi_p(d)=\mathcal{N}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}};n-s\right)
\end{equation*}
$s$-plateaued quadratic functions in $\mathcal{D}$ if $s$ is odd.
\vspace{.2cm}
Now we consider the case of even $s$, i.e. $\epsilon=0$ and $\mathrm{gcd}( A(x),x^n-1)=f(x)$, where the multiplicity of $x-1$ in $f$ is even.
As a result, $\frac{x^n-1}{f(x)}$ is divisible by $x-1$, which implies that $g(x)$ is not divisible by $x-1$. In this case,
  \begin{equation*}
h(x)=(x+1)f(x)g(x) \;\; \;\text{with} \;\;\;
\mathrm{gcd}\left(\frac{x^n-1}{f(x)},g(x)\right)=1 \ ,
\end{equation*}
i.e. $g\in K\left(\frac{x^n-1}{f(x)} \right)=K\left((x-1)\frac{x^n-1}{f(x)} \right)$ by Proposition \ref{d}. Furthermore for any self-reciprocal
divisor $d$ of $x^n-1$ of degree $n-s-1$, the factor $(x-1)d$ uniquely determines $f$. Hence there are
\begin{align*}
&\sum_{(x-1)d|x^n-1;\;
\mathrm{deg}(d)=n-s-1}\phi_p((x-1)d)\\
&= \sum_{(x-1)^2d|(x-1)(x^n-1);\;
\mathrm{deg}(d)=n-s-1}\phi_p((x-1)^{2}d)
\end{align*}
$s$-plateaued functions in $\mathcal{D}$ in the case of even $s$, where $d$ runs over all monic self-reciprocal divisors of $x^n-1$.
In order to determine the last sum, we separate the set
\begin{equation*}
S = \{d\;:\; d\;\text{is monic, self-reciprocal,}~ d|(x-1)(x^n-1), ~\deg(d) = n-s+1\}
\end{equation*}
into two disjoint subsets.
The set $\mathcal{S}_{1}$ consists of elements of $S$ which are divisible by $x-1$, and $\mathcal{S}_{2}$ is the complement, i.e.
\begin{align*}
\mathcal{S}_{1} &=\{d\;:\; d = (x-1)^2k \in S, ~k ~\text{is self-reciprocal,}~ \deg(k)=n-s-1 \}, \\
\mathcal{S}_{2} &=\left\{d\;:\; d\in S,~ d|\frac{x^n-1}{(x-1)^{p^v}} \right\}.
\end{align*}
Then
\[ \sum_{d\in S_1}\phi_p(d) = \sum_{d\in S}\phi_p(d) - \sum_{d\in S_2}\phi_p(d) \ , \]
or equivalently
\begin{align*}
&\sum_{(x-1)^{2}d|(x-1)(x^n-1);\;
\mathrm{deg}(d)=n-s-1}\phi_p((x-1)^{2}d)\\
&=\sum_{d|(x-1)(x^n-1);\;
\mathrm{deg}(d)=n-s+1}\phi_p(d)-\sum_{d|\frac{x^n-1}{(x-1)^{p^v}};\;
\mathrm{deg}(d)=n-s+1}\phi_p(d)\\
&=\mathcal{N}_{n}((x-1)(x^n-1);n-s+1) - \mathcal{N}_{n}(\frac{x^n-1}{(x-1)^{p^v}};n-s+1) \ .
\end{align*}
\end{proof}

\begin{remark} Note that from the proof of Proposition \ref{s-n-odd}, we see that $s\geq p^{v}$ if $s$ is odd.
\end{remark}

\begin{theorem}\label{pro:n-odd} Let $n$ be an odd integer and let $x^n-1=(x-1)^{p^{v}}r_{1}^{p^{v}}\cdots r_{k}^{p^{v}}$ be the factorization of
$x^n-1$ into distinct prime self-reciprocal polynomials.
Then
$\mathcal{G}^{(p)}_{n}=\sum_{t=0}^{n}\mathcal{N}^{(p)}_{n}(n-t)z^{t}$ is given by
\begin{align*}
\mathcal{G}^{(p)}_{n}(z)=
\left( 1+\sum_{j= 1}^{\frac{p^{v}+1}{2}}p^{j-1}(p-1)z^{2j-1} \right)\prod_{i=1}^{k}G_i(z)\ ,
\end{align*}
where
\begin{align*}
G_i(z)= 1+\sum_{j=
   1}^{p^{v}}(p^{\frac{\mathrm{deg}(r_i^{j})}{2}}-p^{\frac{\mathrm{deg}(r_i^{j})-\mathrm{deg}(r_i)}{2}})z^{j\mathrm{deg}(r_i)} \ .
\end{align*}
\end{theorem}
\begin{proof}
We can express the generating function as
{\footnotesize \begin{eqnarray*}
 \mathcal{G}^{(p)}_{n}(z)  &=&  \sum_{t:\text{ even}}\mathcal{N}^{(p)}_{n}(n-t)z^{t}+\sum_{t: \text{ odd}}\mathcal{N}^{(p)}_{n}(n-t)z^{t}\\
   &=&  \sum_{t:\text{ even}} \mathcal{N}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}};t\right)z^{t}+\sum_{t: \text{ odd}}\left( \mathcal{N}_{n}((x-1)(x^n-1);t+1) -
   \mathcal{N}_{n}\left(\frac{x^n-1}{(x-1)^{p^v}};t+1\right)\right) z^{t} \\
     &=&  \sum_{t:\text{ even}} \mathcal{N}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}};t\right)z^{t}+\frac{1}{z}\sum_{t: \text{ odd}}\left( \mathcal{N}_{n}((x-1)(x^n-1);t+1) - \mathcal{N}_{n}\left(\frac{x^n-1}{(x-1)^{p^v}};t+1\right)\right) z^{t+1} \\
   &=&  \sum_{t:\text{ even}} \mathcal{N}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}};t\right)z^{t}
   +\frac{1}{z}\left[\sum_{t:\text{ even}}\left( \mathcal{N}_{n}((x-1)(x^n-1);t) -
   \mathcal{N}_{n}\left(\frac{x^n-1}{(x-1)^{p^v}};t\right)\right) z^{t}\right]\\
   &=&\mathcal{G}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}};z\right)+
   \frac{1}{z}\left[\mathcal{G}_{n}((x-1)(x^n-1);z) - \mathcal{G}_{n}\left(\frac{x^n-1}{(x-1)^{p^v}};z \right)\right]\\
   &=& \prod_{i=1}^{k}\mathcal{G}_{n}(r_{i}^{p^{v}};z)\left(1-\frac{1}{z}+ \frac{1}{z}\mathcal{G}_{n}((x-1)^{p^{v}+1};z)\right).
\end{eqnarray*}}
Note that in the fourth equality
we added and subtracted $\mathcal{N}_{n}((x-1)(x^n-1);0)=\mathcal{N}_{n}\left(\frac{x^n-1}{(x-1)^{p^v}};0\right)=1$.
In the last equality we used Lemma \ref{Gmulti}. We then obtain the claimed formula by Lemma \ref{simpleG}.
\end{proof}

\subsection*{The case of even $n$}

In this case the factorization of $x^n-1$ is given by
\begin{equation*}
x^n-1=(x-1)^{p^{v}}(x+1)^{p^{v}}r_{1}^{p^{v}}\cdots r_{k}^{p^{v}} \
,
\end{equation*}
for some distinct prime self-reciprocal polynomials $r_i$, $1\le i\le k$, of even
degree. Now
\begin{equation*}
    A(x) = \sum_{i=0}^{\
    n/2}(a_ix^i+a_ix^{n-i})=x^{c}h(x) \ ,
\end{equation*}
where $h(x)$ is self-reciprocal, and of even degree $n-2c$.
For the $\gcd(A(x),x^n-1)$ we have
\begin{equation}
\label{epsde}
\mathrm{gcd}( A(x),x^n-1)=\mathrm{gcd}(h(x),x^n-1)=
(x-1)^{\epsilon}(x+1)^{\delta}f_{1}(x) \ ,
\end{equation}
for a self-reciprocal polynomial $f_{1}$ of even degree, and elements $\epsilon, \delta \in \{0,1\}$.
Consequently,
\begin{equation*}
h(x)=(x-1)^{\epsilon}(x+1)^{\delta}f_{1}(x)g_1(x), \; \text{with} \;
\mathrm{gcd}\left(\frac{x^n-1}{(x-1)^{\epsilon}(x+1)^{\delta}f_{1}(x)},g_1(x)\right)=1
\ .
\end{equation*}
We now have to distinguish four cases depending on the values of $\epsilon$ and $\delta$ in $(\ref{epsde})$.
\begin{itemize}
  \item [(i)] Let $\epsilon=\delta=1$, i.e., $\mathrm{gcd}( A(x),x^n-1)=\mathrm{gcd}(h(x),x^n-1)=
(x-1)(x+1)f_{1}(x)$. In this case, $s$ is even and the
self-reciprocal polynomial $h$ of even degree is given by
\begin{align*}
&  h(x)=(x-1)(x+1)f_{1}(x)(x-1)(x+1)g(x) \\
&\quad \quad \quad \quad\quad \quad\text{with } \mathrm{gcd}\left((x-1)(x+1)g(x),\frac{x^n-1}{(x-1)(x+1)f_{1}}\right)=1 \ ,
\end{align*}
where $g(x)$ is a self-reciprocal polynomial of degree $\leq n-s-2$.
As a result, $f_{1}(x)=(x-1)^{p^{v}-1}(x+1)^{p^{v}-1}f(x)$ for a
self-reciprocal polynomial $f$ of even degree (which of course is a product of some $r_{i}$'s).
As a consequence,
\begin{equation*}
h(x)=(x-1)^{p^{v}+1}(x+1)^{p^{v}+1}f(x)g(x) \ ,
\end{equation*}
for some self-reciprocal polynomial $g$. Note that $\mathrm{deg}(g)$ is an even integer smaller than $n-s$ and
$\mathrm{gcd}\left(g,\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}f(x)}\right)=1$.
Recalling that $\mathrm{deg}\left(\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}f(x)}\right)=n-s$,
we see that $g\in K\left(\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}f(x)}\right)$.
Furthermore each divisor $d$ of $\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}}$ of degree $n-s$ uniquely
determines $f$, and hence there exist
\begin{align*}
\sum_{d|\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};\;
\mathrm{deg}(d)=n-s}\phi_p(d)
\end{align*}
such polynomials $h$.
\item [(ii)] Let $\epsilon=1$ and $\delta=0$, i.e., $\mathrm{gcd}( A(x),x^n-1)=\mathrm{gcd}(h(x),x^n-1)=
(x-1)f_{1}(x)$. In this case, $s$ is odd and the self-reciprocal polynomial $h$ of even degree is given by
\begin{equation*}
    h(x)=(x-1)f_{1}(x)(x-1)g(x)\;\; \text{with} \;\;
    \mathrm{gcd}\left((x-1)g(x),\frac{x^n-1}{(x-1)f_{1}}\right)=1 \ ,
\end{equation*}
for some self-reciprocal polynomial $g$,where $deg(g)$ is even, and smaller than $n-s$. Consequently,
$f_{1}(x)=(x-1)^{p^{v}-1}f(x)$ for some self-reciprocal polynomial $f$ of even degree, and therefore
\begin{equation*}
h(x)=(x-1)^{p^{v}+1}f(x)g(x) \ ,
\end{equation*}
where $\mathrm{gcd}\left(g,\frac{x^n-1}{(x-1)^{p^{v}}f(x)}\right)=1$.
Since $\frac{x^n-1}{(x-1)f_{1}}$ contains the factor $x+1$, the polynomial $g$ is not divisible by $x+1$.
In particular, $g \in K((x+1)d)$, where $d=\frac{x^n-1}{(x-1)^{p^{v}}(x+1)f(x)}$ is a
self-reciprocal polynomial of even degree $n-s-1$. As above,
each self-reciprocal divisor $d$ of $\frac{x^n-1}{(x-1)^{p^{v}}(x+1)}$ of degree
$n-s-1$ uniquely determines $f$. Consequently there exist
\begin{align*}
\sum_{d|\frac{x^n-1}{(x-1)^{p^{v}}(x+1)};\;
\mathrm{deg}(d)=n-s-1}\phi_p((x+1)d)
\end{align*}
such polynomials $h$.

\item [(iii)] The case $\epsilon=0$ and $\delta=1$ is very similar. With the same argument as in (ii) we get
\begin{equation}
\label{hiii}
    h(x)=(x+1)f_{1}(x)(x+1)g(x)\;\; \text{with} \;\;
    \mathrm{gcd}\left((x+1)g(x),\frac{x^n-1}{(x+1)f_{1}}\right)=1 \ ,
\end{equation}
for some self-reciprocal polynomial $g$, where $deg(g)$ is even, smaller than $n-s$, and
\begin{align*}
\sum_{d|\frac{x^n-1}{(x+1)^{p^{v}}(x-1)};\;
\mathrm{deg}(d)=n-s-1}\phi_p((x-1)d)
\end{align*}
is the number of polynomials $h$ of the form $(\ref{hiii})$.
\item [(iv)] Let $\epsilon=\delta=0$, i.e., $\mathrm{gcd}( A(x),x^n-1)=\mathrm{gcd}(h(x),x^n-1)=
f(x)$ for some self-reciprocal polynomial $f$ of even degree. In this case
we see that the self-reciprocal polynomial $h$ is given by
\begin{equation*}
    h(x)=f(x)g(x)\; \text{with} \;
    \mathrm{gcd}\left(g(x),\frac{x^n-1}{f(x)}\right)=1 \ ,
\end{equation*}
where $g(x)$ is a self-reciprocal polynomial of degree $\leq n-s$.
Note that $\frac{x^n-1}{f(x)}$ is divisible by both $x-1$ and $x+1$, so $g(x)$ is
not divisible by neither. Therefore
\begin{equation}
\label{hiiii}
    h(x)=f(x)g(x)\; \text{with} \;
    \mathrm{gcd}\left(g(x),(x-1)(x+1)\frac{x^n-1}{f(x)}\right)=1 \ ,
\end{equation}
where $g(x)$ is a self-reciprocal polynomial of degree smaller than $n-s+2$.
As for each self-reciprocal divisor $d$ of $x^n-1$ of degree $n-s$, $f$ is uniquely determined, we can again express
the number of polynomials $h$ of the form $(\ref{hiiii})$ in terms of $\phi_p$ as
\begin{align*}
\sum_{(x-1)(x+1)d|(x-1)(x+1)(x^n-1);\;
\mathrm{deg}(d)=n-s}\phi_p((x-1)(x+1)d).
\end{align*}
\end{itemize}

\begin{remark}
From the above observations we conclude that again $s\geq p^{v}$ if $s$ is odd.
\end{remark}

\begin{theorem}
\label{pro:n-even}
Let $n$ be an even integer and let $x^n-1=(x-1)^{p^{v}}(x+1)^{p^{v}}r_{1}^{p^{v}}\cdots r_{k}^{p^{v}}$ be the factorization of $x^n-1$
into distinct prime self-reciprocal polynomials.
Then the generating function $\mathcal{G}^{(p)}_{n}$ is given by
\begin{align*}
\mathcal{G}^{(p)}_{n}(z)=
\left( 1+\sum_{j= 1}^{\frac{p^{v}+1}{2}}p^{j-1}(p-1)z^{2j-1} \right)^2\prod_{i=1}^{k}G_i(z) \ ,
\end{align*}
where
\begin{align*}
G_i(z)=  1+\sum_{j=
   1}^{p^{v}}(p^{\frac{\mathrm{deg}(r_i^{j})}{2}}-p^{\frac{\mathrm{deg}(r_i^{j})-\mathrm{deg}(r_i)}{2}})z^{j\mathrm{deg}(r_i)} \ .
\end{align*}
\end{theorem}

\begin{proof}
First let $s$ be odd, which applies in the cases (ii) and (iii) above. The discussion of these cases imply for
$\mathcal{N}^{(p)}_{n}(s)$ that
{\scriptsize \begin{eqnarray}
\label{I+II}
   \mathcal{N}^{(p)}_{n}(s) &=& \sum_{d|\frac{x^n-1}{(x-1)^{p^{v}}(x+1)};\;
\mathrm{deg}(d)=n-s-1}\phi_p((x+1)d)+\sum_{d|\frac{x^n-1}{(x+1)^{p^{v}}(x-1)};\;
\mathrm{deg}(d)=n-s-1}\phi_p((x-1)d)\nonumber\\
 &=& \sum_{d|\frac{x^n-1}{(x-1)^{p^{v}}(x+1)};\;
\mathrm{deg}(d)=n-s-1}\phi_p((x+1)^{2}d)+\sum_{d|\frac{x^n-1}{(x+1)^{p^{v}}(x-1)};\;
\mathrm{deg}(d)=n-s-1}\phi_p((x-1)^{2}d) \ . \nonumber\\
& &
\end{eqnarray}}
To determine the sum $(\ref{I+II})$ we separate the set
\begin{equation*}
S=\left \{h\;:\; h\;\text{is monic, self-reciprocal,}~ h|\frac{x^n-1}{(x-1)^{p^v}},~
\deg(h) = n-s+1\right\}
\end{equation*}
into the two disjoint subsets
\begin{eqnarray*}
  S_{1} &=&\{h\;:\; h\in S \; \text{and} \; \mathrm{gcd}(h, x+1)=1\},\;\mbox{and}  \\
    S_{2} &=&\{h\;:\; h\in S \; \text{and} \; (x+1)|h\}.
\end{eqnarray*}
Note that being self-reciprocal and of even degree, the polynomials $h$ in the set $S_2$
are divisible by $(x+1)^{2}$. Then for the first sum in $(\ref{I+II})$ we obtain
\begin{eqnarray*}
& & \sum_{d|\frac{x^n-1}{(x-1)^{p^{v}}(x+1)};\;
\mathrm{deg}(d)=n-s-1}\phi_p((x+1)^{2}d)=  \sum_{h\in
S_{2}}\phi_p(h)\\
& &=\sum_{h|\frac{(x+1)(x^n-1)}{(x-1)^{p^{v}}};\;
  \mathrm{deg}(h)=n-s+1}\phi_p(h)-\sum_{h\in S_{1}}\phi_p(h)\\
   & &=\sum_{h|\frac{(x+1)(x^n-1)}{(x-1)^{p^{v}}};\;
  \mathrm{deg}(h)=n-s+1}\phi_p(h)-\sum_{h|\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};\;
  \mathrm{deg}(h)=n-s+1}\phi_p(h)\\
  & &={\mathcal{N}}_{n}\left(\frac{(x+1)(x^n-1)}{(x-1)^{p^{v}}};n-s+1\right)-{\mathcal{N}}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};n-s+1\right).
\end{eqnarray*}
In a similar way, for the second sum in $(\ref{I+II})$ we get
\begin{align*}
&\sum_{d|\frac{x^n-1}{(x+1)^{p^{v}}(x-1)};\;
\mathrm{deg}(d)=n-s-1}\phi_p((x-1)^{2}d) \\
& {\mathcal{N}}_{n}\left(\frac{(x-1)(x^n-1)}{(x+1)^{p^{v}}};n-s+1\right)-{\mathcal{N}}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};n-s+1\right).
\end{align*}
Combining, we obtain
\begin{eqnarray*}
  \mathcal{N}^{(p)}_{n}(s) &=&{\mathcal{N}}_{n}\left(\frac{(x+1)(x^n-1)}{(x-1)^{p^{v}}};n-s+1\right)
  +{\mathcal{N}}_{n}\left(\frac{(x-1)(x^n-1)}{(x+1)^{p^{v}}};n-s+1\right)\\
   &&-2{\mathcal{N}}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};n-s+1\right)
   \
\end{eqnarray*}
for an odd integer $s$.
\vspace{.2cm}
Now we consider the case of even $s$, which corresponds to (i) and (iv). By the above observations,
\begin{eqnarray*}
  \mathcal{N}^{(p)}_{n}(s) &=& \sum_{d|\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};\;
\mathrm{deg}(d)=n-s}\phi_p(d)\\&&+\sum_{(x-1)(x+1)d|(x-1)(x+1)(x^n-1);\;
\mathrm{deg}(d)=n-s}\phi_p((x-1)(x+1)d) \\
   &=&\mathcal{N}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};n-s\right)\\&&+\sum_{(x-1)(x+1)d|(x-1)(x+1)(x^n-1);\;
\mathrm{deg}(d)=n-s}\phi_p((x-1)(x+1)d).
\end{eqnarray*}
\vspace{.5cm}
We set $T:=\sum_{(x-1)(x+1)d|(x-1)(x+1)(x^n-1);\;\mathrm{deg}(d)=n-s}\phi_p((x-1)(x+1)d)$ and in order to determine $T$ we consider the set
\[ S = \{h(x)\;:\;h(x)\,\text{is self-reciprocal, }~ h|(x-1)(x+1)(x^{n}-1),~ \deg(h) = n-s+2\} \]
and its subsets
\begin{align*}
&S_{1} = \{h(x)\;:\; h\in S, \; \mathrm{gcd}(h, x-1)=1\}, \\
& S_{2} =\{h(x)\;:\; h\in S, \; \mathrm{gcd}(h, x+1)=1\}, \\
&S_{3} =\{h(x)\;:\; h\in S, \; \mathrm{gcd}(h, x^{2}-1)=1\}.
\end{align*}
Note that since $h$ is a self-reciprocal polynomial of even degree, $h$ is divisible by $(x\mp 1)^2$ if it is divisible by $x\mp 1$. As a consequence,
\begin{align*}
T=\sum_{h|(x-1)(x+1)(x^n-1);\;
\mathrm{deg}(h)=n-s+2}\phi_p(h)-\sum_{h\in S_{1} }\phi_p(h)-\sum_{h\in S_{2} }\phi_p(h)+\sum_{h\in S_{3} }\phi_p(h).
\end{align*}
We also note that for $h$ in the set $S$, $h\in S_{1} $ if and only if $h|(x+1)\frac{x^n-1}{(x-1)^{p^{v}}}$, $h\in S_{2} $ if and only if
$h|(x-1)\frac{x^n-1}{(x+1)^{p^{v}}}$ and  $h\in S_{3}$ if and only if $h|\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}}$. Therefore we can express
the sum $T$ as
\begin{align*}
T=\sum_{h|(x-1)(x+1)(x^n-1);\;
\mathrm{deg}(h)=n-s+2}\phi_p(h)-\sum_{h|(x+1)\frac{x^n-1}{(x-1)^{p^{v}}};\;
\mathrm{deg}(h)=n-s+2}\phi_p(h)\\
-\sum_{h|(x-1)\frac{x^n-1}{(x+1)^{p^{v}}};\;
\mathrm{deg}(h)=n-s+2 }\phi_p(h)
+\sum_{h|\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};\;
\mathrm{deg}(h)=n-s+2  }\phi_p(h).
\end{align*}
Hence, for an even integer $s$
{ \scriptsize \begin{eqnarray*}
  \mathcal{N}^{(p)}_{n}(s) &=& \mathcal{N}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};n-s\right)+\mathcal{N}_{n}\left((x-1)(x+1)(x^{n}-1);n-s+2\right) \\
 &&- \mathcal{N}_{n}\left(\frac{(x+1)(x^{n}-1)}{(x-1)^{p^{v}}};
  n-s+2\right) - \mathcal{N}_{n}\left(\frac{(x-1)(x^{n}-1)}{(x+1)^{p^{v}}}; n-s+2\right)\\ && + \mathcal{N}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};n-s+2\right).
\end{eqnarray*}}
\vspace{.3cm}

From the above equalities
we get
{\scriptsize \begin{align*}
\mathcal{G}_n^{(p)}(z) &= \sum_{t=0}^{n} \mathcal{N}^{(p)}_{n}(n-t)z^{t}=\sum_{t: \text{ odd}} \mathcal{N}^{(p)}_{n}(n-t)z^{t}+\sum_{t: \text{ even}} \mathcal{N}^{(p)}_{n}(n-t)z^{t} \\
&=\sum_{t: \text{ odd}}\left[\mathcal{N}_{n}\left(\frac{(x+1)(x^n-1)}{(x-1)^{p^{v}}};t+1\right)
  +\mathcal{N}_{n}\left(\frac{(x-1)(x^n-1)}{(x+1)^{p^{v}}};t+1\right)-2\mathcal{N}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};t+1\right)\right]z^{t}\\
  &+\sum_{t: \text{ even}}\left[  \mathcal{N}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};t\right)+\mathcal{N}_{n}\left((x-1)(x+1)(x^{n}-1);t+2\right)- \mathcal{N}_{n}\left(\frac{(x+1)(x^{n}-1)}{(x-1)^{p^{v}}};
  t+2\right)  \right.\\
  & \left. - \mathcal{N}_{n}\left(\frac{(x-1)(x^{n}-1)}{(x+1)^{p^{v}}}; t+2\right)
  +\mathcal{N}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};t+2\right)\right]z^t

     \end{align*}
  \begin{align*}
  &=\frac{1}{z}\sum_{t: \text{ odd}}\left[\mathcal{N}_{n}\left(\frac{(x+1)(x^n-1)}{(x-1)^{p^{v}}};t+1\right)
  +\mathcal{N}_{n}\left(\frac{(x-1)(x^n-1)}{(x+1)^{p^{v}}};t+1\right)-2\mathcal{N}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};t+1\right)\right]z^{t+1}\\
  &+\sum_{t: \text{ even}} \mathcal{N}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};t\right)z^t
  +\frac{1}{z^{2}}\sum_{t: \text{ even}}\Big[ \mathcal{N}_{n}\left((x-1)(x+1)(x^{n}-1);t+2\right) \\
  & - \mathcal{N}_{n}\left(\frac{(x+1)(x^{n}-1)}{(x-1)^{p^{v}}};
  t+2\right)- \mathcal{N}_{n}\left(\frac{(x-1)(x^{n}-1)}{(x+1)^{p^{v}}}; t+2\right)
  +\mathcal{N}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};t+2\right)\Big]z^{t+2}

   \end{align*}
  \begin{align*}
  &=\frac{1}{z}\sum_{t: \text{ even}}\left[\mathcal{N}_{n}\left(\frac{(x+1)(x^n-1)}{(x-1)^{p^{v}}};t\right)
  +\mathcal{N}_{n}\left(\frac{(x-1)(x^n-1)}{(x+1)^{p^{v}}};t\right)-2\mathcal{N}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};t\right)\right]z^{t}\\
  &+\sum_{t: \text{ even}} \mathcal{N}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};t\right)z^t
  +\frac{1}{z^{2}}\sum_{t: \text{ even}}\left[ \mathcal{N}_{n}\left((x-1)(x+1)(x^{n}-1);t\right)  \right.\\
  & \left. - \mathcal{N}_{n}\left(\frac{(x+1)(x^{n}-1)}{(x-1)^{p^{v}}};
  t\right)- \mathcal{N}_{n}\left(\frac{(x-1)(x^{n}-1)}{(x+1)^{p^{v}}}; t\right)
  +\mathcal{N}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};t\right)\right]z^{t}

    \end{align*}
  \begin{align*}
    &=\frac{1}{z}\left[\mathcal{G}_{n}\left(\frac{(x+1)(x^n-1)}{(x-1)^{p^{v}}};z\right)
  +\mathcal{G}_{n}\left(\frac{(x-1)(x^n-1)}{(x+1)^{p^{v}}};z\right)-2\mathcal{G}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};z\right)\right]\\
  &+ \mathcal{G}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};z\right)
  +\frac{1}{z^{2}}\Big[ \mathcal{G}_{n}\left((x-1)(x+1)(x^{n}-1);z\right) \\
  & - \mathcal{G}_{n}\left(\frac{(x+1)(x^{n}-1)}{(x-1)^{p^{v}}};
  z\right)- \mathcal{G}_{n}\left(\frac{(x-1)(x^{n}-1)}{(x+1)^{p^{v}}}; z\right)
  +\mathcal{G}_{n}\left(\frac{x^n-1}{(x-1)^{p^{v}}(x+1)^{p^{v}}};z\right)\Big]

    \end{align*}
  \begin{align*}
 & =\prod_{i=1}^{k}\mathcal{G}_{n}(r_{i}^{p^{v}};z)\left( \frac{1}{z}\mathcal{G}_{n}((x+1)^{p^{v}+1};z)+\frac{1}{z}\mathcal{G}_{n}((x-1)^{p^{v}+1};z)-\frac{2}{z}+1\right.\\
 &\left.+\frac{1}{z^{2}}\mathcal{G}_{n}((x-1)^{p^{v}+1}(x+1)^{p^{v}+1};z)- \frac{1}{z^{2}}\mathcal{G}_{n}((x+1)^{p^{v}+1};z) -\frac{1}{z^{2}}\mathcal{G}_{n}((x-1)^{p^{v}+1};z)+\frac{1}{z^{2}}\right).
\end{align*}}
By Lemma \ref{simpleG} we get
\begin{align*}
& \mathcal{G}^{(p)}_{n}(z)=\prod_{i=1}^{k}\mathcal{G}_{n}(r_{i}^{p^{v}};z)\left( \frac{2}{z}\mathcal{G}_{n}((x-1)^{p^{v}+1};z)-\frac{2}{z}+1+\frac{1}{z^{2}}\mathcal{G}_{n}((x-1)^{p^{v}+1};z)^2\right.\\
 &\left.-\frac{2}{z^{2}}\mathcal{G}_{n}((x-1)^{p^{v}+1};z)+\frac{1}{z^{2}}\right).
\end{align*}
Putting
\begin{align*}
&G_{i}:=\mathcal{G}_{n}(r_{i}^{p^{v}};z)\ , \;\; \text{and} \;\;A:=\sum_{j= 1}^{\frac{p^{v}+1}{2}}p^{j-1}(p-1)z^{2j} =\mathcal{G}_{n}((x-1)^{p^{v}+1};z)-1
\end{align*}
this yields
\begin{align*}
&\mathcal{G}^{(p)}_{n}(z)&=&\prod_{i=1}^{k} G_{i} \left[\frac{2}{z} (1+A)-\frac{2}{z} +1+\frac{1}{z^{2}}(1+A)^2 -\frac{2}{z^{2}}(1+A)+\frac{1}{z^{2}}\right]\\
&&=&\left(1+\frac{A}{z}\right)^2 \prod_{i=1}^{k} G_{i}.
\end{align*}
Simplifying and using Lemma \ref{simpleG} we get the desired result.
\end{proof}

As an immediate corollary of Theorems \ref{pro:n-odd} and \ref{pro:n-even} we obtain the number of bent functions in the
set $\mathcal{D}$. Note that the case of $\gcd(n,p)=1$ is covered in \cite[Corollary 7]{mrt}.
\begin{corollary}
Let the factorization of $x^n-1$ into distinct prime self-reciprocal polynomials be
$x^n-1=(x-1)^{p^{v}}r_{1}^{p^{v}}\cdots r_{k}^{p^{v}}$ when $n$ is odd, and
$x^n-1=(x-1)^{p^{v}}(x+1)^{p^{v}}r_{1}^{p^{v}}\cdots r_{k}^{p^{v}}$ when $n$ is even.
Then the number of bent functions in $\mathcal{D}$ is
\[ \mathcal{N}_n(0) = (p-1)p^{\frac{p^v-1}{2}}\prod_{i=1}^k\left(p^{\frac{p^v\deg(r_i)}{2}}-p^{\frac{(p^v-1)\deg(r_i)}{2}}\right)\ , \]
if $n$ is odd, and
\[ \mathcal{N}_n(0) =
((p-1)p^{\frac{p^v-1}{2}})^2\prod_{i=1}^k\left(p^{\frac{p^v\deg(r_i)}{2}}-p^{\frac{(p^v-1)\deg(r_i)}{2}}\right)\ , \]
if $n$ is even.
\end{corollary}