\section{Introduction}
\label{sec:introduction}
It has been of great interest in recent years the study of irreducible
polynomials which can be written as composition of degree two polynomials (see
for example
\citep{bib:ahmadi2009note,
bib:ahmadi2012stable,
ferraguti2016sets,
bib:gomez2010estimate,
bib:gomez2017complexity,
bib:heathbrownmicheli,
jones2007iterated,
jones2008density,
bib:jones2012iterative,
bib:jones2012settled,
bib:ostafe2010length}).
Such polynomials are also used in other contexts, see for example Rafe Jones' construction
of irreducible polynomials reducible modulo every prime
\cite{bib:jones2012iterative} or the proof of \cite[Conjecture
1.2]{bib:andrade2013special} in \cite{bib:ferraguti2016existence}. In this
paper we explain how the theory of this class of polynomials completely fits in
a general context which allows the use of powerful machinery coming from the
 theory of finite automata (in characteristic different from $2$).
In fact, we show that some irreducibility questions over finite fields can be
translated into automata theoretical ones (see
Definition~\ref{def:automaton_nonsquare} and Theorem~\ref{thm:irred_regular}).
As a side result, we also obtain that the set of irreducible polynomials which
can be written as the composition of degree two polynomials is naturally endowed
with a regular structure given by Theorem~\ref{thm:disjoint}.

Let $\mathbb{F}_q$ be a finite field of odd characteristic and let $\mathcal{S} \subset \mathbb{F}_q[x]$ be a set of monic degree two polynomials.
In this paper, we consider the set $\mathcal{S}$ to be an alphabet, and a word $f_1
\cdots f_k \in \mathcal{S}^*$ corresponds to the composition $f_1 \circ \cdots \circ
f_k \in \mathbb{F}_q[x]$.
The empty word naturally corresponds to $x$.
Let $\mathcal{I} \subset \mathcal{S}^*$ be the language of words whose corresponding
compositions are irreducible.
Our goal is to show that $\mathcal{I}$ is a regular language by  providing an automaton that accepts it.
The entire theory lifts to local fields under the assumption that the set $\mathcal{S}$ is finite and none of its elements has discriminant in the maximal ideal of the local field.

\section{Distinguished sets and freedom}
We include in this section some elementary facts concerning the freedom of the monoid generated by a finite set of irreducible degree two polynomials. These results will be needed in Section~\ref{sec:automaton_irreducible}.
Each polynomial $f \in \mathcal{S}$ can be uniquely written as $f = (x - a_f)^2 - b_f$
for some $a_f,b_f\in \mathbb{F}_q$.
We define $D_\mathcal{S} = \{b_f : f \in \mathcal{S}\}$ to be the \emph{distinguished set} of
$\mathcal{S}$.

We denote by $\mathcal{S}^*$ the set of words over the alphabet $\mathcal{S}$, so $\mathcal{S}^*$ is
the free monoid generated by the symbols in $\mathcal{S}$. Let $C_{\mathcal{S}}\subseteq \mathbb{F}_q[x]$ be the
compositional monoid generated by $\mathcal{S}$, that is the smallest subset of
$\mathbb{F}_q[x]$ containing $\mathcal{S}$ and $x$ which is closed by composition.

We will denote by $\pi$ the natural surjective morphism of monoids $\mathcal{S}^*\longrightarrow C_{\mathcal{S}}$ which maps a word $f_1f_2\ldots f_k\in\mathcal{S}^*$ to the composition $f_1\circ f_2\circ\ldots\circ f_k\in\mathbb{F}_q[x]$.
Notice that, for an element $f\in \mathcal{S}$ we will denote by $f^{(n)}$ the $n$-fold composition of $f$ with itself.

For $b\in D_\mathcal{S}$, we define $A_b$ as the subset of all $a$ in $\mathbb{F}_q$ such that
there exists $f\in \mathcal{S}$ with $f=(x-a)^2-b$.
For any of the $A_b$, we define the difference set
\[A_b-A_b=\{a-a': a,a'\in A_b\}.\]
We can define a relation $\sim$ on $\mathcal{S}^*$ by setting $u\sim w$ if there exists $\ell\in \bigcup_{b\in D_\mathcal{S}} \left(A_b-A_b\right)$ for which
$\pi(u)+\ell=\pi(w)$. This relation is symmetric and reflexive but not transitive, unless  $\bigcup_{b\in D_\mathcal{S}} \left(A_b-A_{b}\right)$ is an additive subgroup of $\mathbb{F}_q$.

In this section we provide a computable condition to establish whether $C_\mathcal{S}$
is a free monoid, which will be needed later on.
\begin{proposition}\label{thm:relation}
Let $u,v$ be words of $\mathcal{S}^*$ of equal length $n \ge 1$. Let $u',v'$ be the $(n-1)$-suffixes of $u$ and $v$ respectively. Then
\begin{enumerate}
\item[(i)] $\pi(u)=\pi(v)$ implies  $u'\sim v'$
\item[(ii)] $u\sim v$ if and only if  $\pi(fu)=\pi(gv)$ for some $f,g\in \mathcal{S}$.
\end{enumerate}
\end{proposition}
\begin{proof}
Let us first prove (i). Suppose $\pi(u)=\pi(v)$ and let us write
\[\pi(u)=(h_1-a)^2-b=(h_2-a')^2-b'=\pi(v)\]
for $h_1 = \pi(u')$, $h_2 = \pi(v')$.
Then we have $(h_1-a-h_2+a')(h_1+h_2-a-a')=b-b'$. Since $h_1+h_2-a-a'$ has positive degree, this forces $b=b'$ and $h_1-a-h_2+a'=0$. Now it is clear that $a,a'\in A_b$, which implies $a'-a\in A_b-A_b$, and then $u'\sim v'$.

Let us now prove (ii). If $u\sim v$, by definition we have $\pi(u)-a=\pi(v)-a'$
for $a-a'\in A_b-A_b$ for some $b$. Now, by squaring and subtracting $b$ on both
sides of the equality we get $f(\pi(u))=g(\pi(v))$ for some $f,g\in \mathcal{S}$, and
hence $\pi(fu) = \pi(gv)$.
Vice versa, if there exists $f,g\in \mathcal{S}$ such that $\pi(f u)=\pi(g v)$, then (i)
applies.
\end{proof}

\begin{lemma}\label{thm:relation_max_min}
	Let $u,v$ be words of $\mathcal{S}^*$ of equal length $n \ge 1$.
	If $\abs{D_{\mathcal{S}}}=\abs{\mathcal{S}}$ or $\abs{D_\mathcal{S}}=1$, then we have that
	$u \sim v$ if and only if $\pi(u) = \pi(v)$.
\end{lemma}
\begin{proof}
One direction is trivial: If $\pi(u)=\pi(v)$ then $u\sim v$.
For the other direction, we look at the two cases separately.

In the case $\abs{D_{\mathcal{S}}}=\abs{\mathcal{S}}$, it follows from $u \sim v$ that $\pi(u) -
\pi(v) = c \in A_b - A_b$ for some $b \in D_\mathcal{S}$.
However, $A_b$ consists of only one element, so $c = 0$.

For the case $\abs{D_{\mathcal{S}}}=1$, assume that $u \sim v$, so $\pi(u)=\pi(v) + c$
for some $c\in \mathbb{F}_q$.
Let $u',v'$ be the $(n-1)$-suffixes of $u$ and $v$.
Then, since $\abs{D_\mathcal{S}}=1$, we have that $(\pi(u')-a_1)^2-(\pi(v')-a_2)^2=c$
for some $a_1,a_2\in\mathbb{F}_q$.
As $c$ is constant, this forces $(\pi(u')-a_1)-(\pi(v')-a_2)=0$, which in turn
forces $c=0$ and hence $\pi(u) = \pi(v)$.
\end{proof}

The following proposition shows that the freedom of the monoid is ensured whenever $D_\mathcal{S}$ is either maximal or minimal.

\begin{proposition}\label{thm:freedom_max_min}
If $\abs{D_{\mathcal{S}}}=\abs{\mathcal{S}}$ or $\abs{D_\mathcal{S}}=1$, then $C_{\mathcal{S}}\cong \mathcal{S}^*$.
\end{proposition}
\begin{proof}
Clearly, a polynomial of degree two in $C_{\mathcal{S}}$ cannot have two distinct writings in terms of compositions.
Let $F$ be a polynomial in $C_\mathcal{S}$ of minimal degree with two different writings,
i.e.\@ such that $F=\pi(fu)=\pi(gv)$ for $f,g\in \mathcal{S}$ and $u, v\in \mathcal{S}^*$ of
positive length.
From $\pi(fu)=\pi(gv)$ one deduces by Proposition~\ref{thm:relation} that $u\sim v$.
Lemma~\ref{thm:relation_max_min} now gives $\pi(u)=\pi(v)$, which implies  $u=v$
by the minimality of $F$.
\end{proof}

\begin{corollary}\label{thm:freedom2}
If $\abs{\mathcal{S}}=2$ then $C_{\mathcal{S}}\cong \mathcal{S}^*$.
\end{corollary}
\begin{proof}
Immediate by observing that $\abs{D_\mathcal{S}}=1$ or $\abs{D_\mathcal{S}}=\abs{\mathcal{S}}=2$.
\end{proof}

\section{An automaton for irreducible compositions}
\label{sec:automaton_irreducible}

\subsection{Capelli's Lemma}
\label{sec:capellis_lemma}

In this subsection we describe the basic tools needed to establish the main result. We start with a well known result by Capelli, which gives a necessary and sufficient criterion to control the irreducibility of the composition of two polynomials.
\begin{lemma}[Capelli's Lemma]\label{thm:capelli}
	Let $K$ be a field and $f,g \in K[x]$ polynomials.
	Let $\beta \in \overline{K}$ be a root of $g$.
	Then, $g \circ f$ is irreducible over $K$ if and only if $g$ is irreducible
	over $K$ and $f - \beta$ is irreducible over $K(\beta)$.
\end{lemma}

We now use Capelli's Lemma to produce a simple ancillary result which will help us in what follows.

\begin{lemma}\label{thm:irred_short}
	Let $g \in \mathbb{F}_q[x]$ be monic and irreducible of even degree, and let $f = (x -
	a_f)^2 - b_f \in \mathbb{F}_q[x]$.
	Then, $g \circ f$ is irreducible if and only if $g(-b_f)$ is not a square in
	$\mathbb{F}_q$.
\end{lemma}
\begin{proof}
	Let $d = \deg(g)$, and let $\beta \in \mathbb{F}_{q^d}$ be a root of $g$.
	According to Lemma~\ref{thm:capelli}, $g \circ f$ is irreducible over $\mathbb{F}_q$
	if and only if $f - \beta$ is irreducible over $\mathbb{F}_{q^d}$.
	Writing $f-\beta = (x - a_f)^2 - (b_f + \beta)$, this is equivalent to $b_f + \beta$
	not being a square in $\mathbb{F}_{q^d}$.
	Let $N\colon \mathbb{F}_{q^d} \to \mathbb{F}_q$ be the norm map.
	If $\beta_1, \ldots, \beta_d$ are the roots of $g$, we have
	\begin{equation*}
		N(b_f + \beta) = \prod_{i=1}^{d}(b_f + \beta_i) = (-1)^d \prod_{i=1}^{d}
		((-b_f) - \beta_i) = g(-b_f),
	\end{equation*}
	since $d$ is even.
	Now we can conclude,
	since $b_f + \beta$ is a nonsquare in $\mathbb{F}_{q^d}$ if and
	only if $N(b_f + \beta) = g(-b_f)$ is a nonsquare in $\mathbb{F}_q$.
\end{proof}

We are now ready to state one of the basic ingredients of the proof of the main theorem, which will allow us to ``push'' irreducibility questions for compositions of degree two polynomials on a finite level.

\begin{proposition}\label{thm:irred_long}
	Let $f_1, \ldots, f_k \in \mathbb{F}_q[x]$ be monic polynomials of degree two.
	Write $f_i = (x - a_i)^2 - b_i$ for all $i$.
	Then, $f_1 \circ \cdots \circ f_k$ is irreducible if and only if all of the
	following are nonsquares in $\mathbb{F}_q$:
	\begin{itemize}
		\item $b_1$
		\item $f_1(-b_2)$
		\item[] $\vdots$
		\item $(f_1 \circ \cdots \circ f_{k-1})(-b_k)$.
	\end{itemize}
\end{proposition}
\begin{proof}
	Clearly, $f_1$ is irreducible if and only if $b_1$ is a nonsquare.
	The rest follows by inductive application of Lemma~\ref{thm:irred_short}.
\end{proof}

\subsection{Brief interlude on Automata Theory}

In this subsection we recall the basic results needed in the next section.
For the definition of \emph{deterministic finite automaton} (DFA),
and \emph{nondeterministic finite automaton} (NFA) we refer for example to
\cite[Chapter~2]{bib:hopcroftintroduction}.
Since all the automata in the paper will have a finite set of states, we will often omit the word finite.

Let $\Sigma$ be a set of symbols (an \emph{alphabet}) and $\Sigma^*$ be the set
of words over $\Sigma$, that is the free monoid generated by it.
Let us recall that a subset $\mathcal{L}$ of $\mathcal{S}^*$ is called a \emph{language}. Let $\cdot$ be
the usual binary operation in $\Sigma^*$ (i.e. concatenation of words) and ${}^*$ be the unary operation on languages defined by $\mathcal{L}\mapsto \mathcal{L}^*$ where $\mathcal{L}^*$ is the smallest submonoid of $\Sigma^*$ containing $\mathcal{L}$ (in the context of languages, this operation is often called \emph{Kleene star}).

 A language is said to be
\emph{regular} if it is finite or can be expressed recursively starting from
finite sets using the operations $\cup,\cdot,{}^*$ (see \cite{bib:hopcroftintroduction} for more details).  The following fact is
well known.

\begin{theorem}
A language is regular if and only if it is accepted by a DFA.
\end{theorem}

We will need the following fundamental results from the theory of Automata.

\begin{theorem}
If a language $\mathcal{L}$ is accepted by a DFA or an NFA, then it is regular.
\end{theorem}
Roughly, the theorem above states that the accepted languages of NFAs
do not generalize the notion of regular language.

We will also be using the notion of a \emph{partial deterministic finite
automaton}, which is the same as a DFA, except the transition function is
actually a partial function.
If, when reading a word, a required transition is not defined, the word is
rejected.
Clearly, a partial DFA is a special case of an NFA, so languages accepted by
partial DFAs are also regular.

\subsection{Putting all together: building the automaton}
We first define a finite deterministic automaton $\mathcal{N}=\mathcal{N}(\mathcal{S})$ using the data contained in $\mathcal{S}$.

\begin{definition}\label{def:automaton_nonsquare}
The states of the automaton $\mathcal{N}(\mathcal{S})$ are given by the following:
	\begin{itemize}
		\item A special start state $\mathfrak{I}$.
			It is accepting.
		\item For each $a \in \mathbb{F}_q$, we have a distinguished state
			$\dist{a}$.
			It is accepting if $-a$ is a nonsquare.
		\item For each $a \in \mathbb{F}_q$, we have a state $\reg{a}$.
			It is accepting if $a$ is a nonsquare.
	\end{itemize}
	The transitions are as follows:
	\begin{itemize}
		\item For each $f \in \mathcal{S}$, we have a transition
			$\mathfrak{I} \xrightarrow{f} \dist{-b_f}$.
		\item For each $f \in \mathcal{S}$ and each $a \in \mathbb{F}_q$, we have a transition
			$\dist{a} \xrightarrow{f} \reg{f(a)}$.
		\item For each $f \in \mathcal{S}$ and each $a \in \mathbb{F}_q$, we have a transition
			$\reg{a} \xrightarrow{f} \reg{f(a)}$.
	\end{itemize}
\end{definition}

\begin{remark}
	The reason we distinguish between the states $\reg{a}$ and $\dist{a}$ is that
	they may be accepting at different times:
	$\reg{a}$ accepts if $a$ is nonsquare, $\dist{a}$ if $-a$ is nonsquare.
	In the case that $-1$ is a square in $\mathbb{F}_q$, the two are equivalent and we
	can identify the two types of states.
\end{remark}

\begin{theorem}\label{thm:irred_regular}
	The language $\mathcal{I}$ of irreducible compositions is regular.
\end{theorem}
\begin{proof}
	Let $\mathcal{L}$ be the regular language over the alphabet $\mathcal{S}$ that is accepted
	by the automaton $\mathcal{N}$ reading from \emph{right to left}.
	It is easy to see that a single letter $f$ is in $\mathcal{L}$ if and only if $b_f$
	is nonsquare.
	Furthermore, a word $f_1 \cdots f_k$, $k \ge 2$, is in $\mathcal{L}$ if and only if
	$(f_1 \circ \ldots \circ f_{k-1})(-b_{f_k})$ is nonsquare.
	By Proposition~\ref{thm:irred_long}, it follows that the word $f_1 \cdots
	f_k$ corresponds to an irreducible polynomial if and only if each prefix $f_1
	\cdots f_l$, $l \le k$, lies in $\mathcal{L}$.
	In other words, $\mathcal{I}$ is the language of all words whose every prefix is in
	$\mathcal{L}$.

	We want to prove that $\mathcal{I}$ is regular. To do so, let us first construct a
	non-deterministic automaton $\mathcal U$ from $\mathcal{N}$ by reversing all the
	arrows of $\mathcal{N}$ and setting the start state of $\mathcal{N}$ as final state of
	$\mathcal U$ and the final states of $\mathcal{N}$ as start states of $\mathcal U$.
	Observe that the accepted language of $\mathcal U$ is again the language
	$\mathcal{L}$, this time reading from left to right as usual. Now we use subset construction (see
	e.g.~\cite[Section~2.3.5]{bib:hopcroftintroduction}) to generate a new
	deterministic automaton $\mathcal V$ having the same accepted language as
	$\mathcal U$.
	Finally, we remove all non-accepting states from $\mathcal V$ to obtain the
	partial automaton $\mathcal{M}$.
	It is easily seen that $\mathcal{M}$ accepts exactly those words whose every prefix
	is accepted by $\mathcal V$, which as explained above is $\mathcal{I}$.
\end{proof}

\begin{remark}\label{rem:prefixclosed}
Notice that the language accepted by the final automaton $\mathcal M$ is prefix closed.
\end{remark}

We now provide an example to see the theorem in action.

\begin{example}\label{ex:1}
	As a simple example, consider the case $q = 5$ and $\mathcal{S} = \{f, g\}$ with
	$f = x^2 - 2$ and $g = (x-1)^2 - 3$.

	We first construct the interim automaton $\mathcal{N}$ using the method described in
	Definition~\ref{def:automaton_nonsquare}.
	Since $p \equiv 1 \mod 4$, we can identify the nodes $\dist{a}$ and $\reg{a}$.
	Note that we have removed the node $\reg{0}$ since it is not reachable from
	$\mathfrak{I}$.
	The result is seen in Figure~\ref{fig:ex1_Ansq}.

	\begin{figure}[h]
		\centering
		\begin{tikzpicture}[auto]
			\node (I) at (0,0) [draw] {$\mathfrak{I}$};

			\node (a2) at ( 1,-1) [draw] {$\reg{2}$};
			\node (a3) at (-1,-1) [draw] {$\reg{3}$};
			\node (a1) at (-1,-2.5) [] {$\reg{1}$};
			\node (a4) at ( 1,-2.5) [] {$\reg{4}$};

			\draw [->] (I) to node [swap] {$f$} (a3);
			\draw [->] (I) to node [] {$g$} (a2);

			\draw [->] ([yshift=-2]a3.east) to node [swap] {$f$} ([yshift=-2]a2.west);
			\draw [->] (a3) to node [swap] {$g$} (a1);

			\draw [->] (a2) to [loop right] node {$f$} (a2);
			\draw [->] ([yshift=2]a2.west) to node [swap] {$g$} ([yshift=2]a3.east);

			\draw [->] ([yshift=-2]a1.east) to node [swap] {$f$} ([yshift=-2]a4.west);
			\draw [->] (a1) to node [swap,xshift=-1,yshift=4] {$g$} (a2);

			\draw [->] (a4) to [loop right] node {$f$} (a4);
			\draw [->] ([yshift=2]a4.west) to node [swap] {$g$} ([yshift=2]a1.east);
		\end{tikzpicture}
		\caption{The interim automaton $\mathcal{N}$ for Example~\ref{ex:1}, coming from
		Definition~\ref{def:automaton_nonsquare}. Boxed states are accepting.}
		\label{fig:ex1_Ansq}
	\end{figure}

	After performing the transformation described in the proof of
	Theorem~\ref{thm:irred_regular} and cutting out all unreachable states, we end
	up with the simple partial automaton $\mathcal{M}$ in Figure~\ref{fig:ex1_Airr}.
	This shows that the irreducible compositions of $f$ and $g$ are precisely
	those of the form $f^{(n)}$, $f^{(n)} \circ g$, $f^{(n)} \circ g^{(2)}$ and $f^{(n)} \circ g^{(2)} \circ f$ for $n \ge 0$.

	\begin{figure}[h]
		\centering
		\begin{tikzpicture}[auto]
			\node (S) at (0,0) [draw,circle] {$S$};

			\node (1) at ( 1.5, 0) [draw,circle] {$1$};
			\node (2) at ( 3.0, 0) [draw,circle] {$2$};
			\node (3) at ( 4.5, 0) [draw,circle] {$3$};

			\draw [->] (S) to [loop below] node {$f$} (S);
			\draw [->] (S) to node {$g$} (1);
			\draw [->] (1) to node {$g$} (2);
			\draw [->] (2) to node {$f$} (3);

		\end{tikzpicture}
		\caption{The automaton $\mathcal{M}$ accepting $\mathcal{I}$ for Example~\ref{ex:1}. All states are accepting.}
		\label{fig:ex1_Airr}
	\end{figure}
\end{example}

Using the machinery we developed in the rest of the paper, we describe an
infinite set of primes of $\mathbb{F}_q[x]$ having a finite regular structure.

\begin{theorem}\label{thm:disjoint}
Let $\mathbb{F}_q$ be a finite field of characteristic different from $2$.
The set of irreducible polynomials having coefficients in $\mathbb{F}_q$ which can be
written as a nonempty composition of degree $2$ polynomials can be partitioned
into a finite disjoint union $\bigsqcup_{a\in \mathbb{F}_q} \mathcal{L}_a$ in such a way that
each $\mathcal{L}_a$ is in natural bijection with the words of a regular language $\mathcal{L}$,
which is independent of $a$. In particular, the set of such irreducible
polynomials has a finite regular expression in terms of the elementary
operations $\cup, \cdot, {}^*$.
\end{theorem}
\begin{proof}
Let $D$ be the set of irreducible polynomials in $\mathbb{F}_q[x]$ that can be written
as nonempty composition of degree $2$ polynomials. Let $\mathcal{S}=\{x^2-b\}_{b\in \mathbb{F}_q}$. By
Proposition~\ref{thm:freedom_max_min}, $C_\mathcal{S}$ is isomorphic to $\mathcal{S}^*$, so it is naturally
embedded in $\mathbb{F}_q[x]$. Apply now Theorem~\ref{thm:irred_regular} to obtain  the
regular language of irreducible polynomials $\mathcal{I}$ generated by $\mathcal{S}$, and let
$\mathcal{L} = \mathcal{I} \setminus \{x\}$.
Let $\psi_a\colon \mathcal{L}\longrightarrow \mathbb{F}_q[x]$ be the shift map defined by
$f(x)\mapsto f(x+a)$.
Let $\mathcal{L}_a=\psi_a(\mathcal{L})$.
It is easy to observe that for any polynomial $f\in D$, there exists $a\in
\mathbb{F}_q$ such that $f(x-a)$ can be written as an element of $C_\mathcal{S}$.
This shows that
\[D=\bigcup_{a\in \mathbb{F}_q} \mathcal{L}_a.\]
It remains to show that $\mathcal{L}_a\cap \mathcal{L}_b=\emptyset$ if $a\neq b$, the final
result will follow immediately. We argue by induction on the length of the words
in $\mathcal{L}$ (i.e.\@ the degree of the polynomials). Let $a,b\in \mathbb{F}_q$ with $a\neq b$
such that there exist two words $v,w\in \mathcal{L}$ of minimal length $\ell$ such that
$\psi_a(v)=\psi_b(w)$. If $\ell=1$, this is clearly impossible, so let us assume
$\ell>1$. We can write $f(v'(x+a))=g(w'(x+b))$ for some $f,g\in \mathcal{S}$ and $v',w'$
suffixes of $v$ and $w$ respectively. Therefore, for some $k,j\in \mathbb{F}_q$ we have
\[v'(x+a)^2-w'(x+b)^2=(v'(x+a)-w'(x+b))(v'(x+a)+w'(x+b))=k-j.\]
Since $v',w'$ are monic and the characteristic of $\mathbb{F}_q$ is different from $2$,
then the degree of the polynomial $(v'(x+a)+w'(x+b))$ is greater than or equal
to $2$. This forces both $k=j$ and $(v'(x+a)-w'(x+b))=0$, which contradicts the
minimality of $\ell$.
\end{proof}

\begin{example}\label{ex:2}
	For an example demonstrating Theorem~\ref{thm:disjoint}, take $q = 3$ and
	$\mathcal{S} = \{f, g, h\}$ with $f = x^2$, $g = x^2 - 1$, $h = x^2 - 2$.
	From Proposition~\ref{thm:freedom_max_min}, $C_\mathcal{S}$ is free and isomorphic to
	$\mathcal{S}^*$.
	Applying the construction, we get the automaton shown in
	Figure~\ref{fig:ex2_Airr}.
	We see that the irreducible polynomials in $C_\mathcal{S}$ are exactly $x$, $h$,
	$h\circ g\circ f^{(n)}$ for $n \ge 0$, and $h^{(2)}\circ k$ for $k \in C_\mathcal{S}$ arbitrary (possibly the identity).
	Applying Theorem~\ref{thm:disjoint}, it follows that the set of irreducible polynomials in $\mathbb{F}_3[x]$ that can be written as a nonempty composition of
	degree $2$ polynomials is precisely
	\[\bigcup_{a\in \mathbb{F}_3} \left(\{h(x+a)\} \cup \{h\circ g \circ f^{(n)}(x+a) : n \ge 0\} \cup \{h^{(2)}\circ k(x+a) : k \in C_\mathcal{S}\}\right).\]

	\begin{figure}[h]
		\centering
		\begin{tikzpicture}[auto]
			\node (S) at (0,0) [draw,circle] {$S$};

			\node (1) at ( 1.5, 0) [draw,circle] {$1$};
			\node (2) at ( 3.0, 0) [draw,circle] {$2$};
			\node (3) at ( 1.5, -1.5) [draw,circle] {$3$};

			\draw [->] (S) to node {$h$} (1);
			\draw [->] (2) to [loop right] node {$f$} (2);
			\draw [->] (1) to node {$g$} (2);
			\draw [->] (1) to node {$h$} (3);
			\draw [->] (3) to [loop left] node {$f$} (3);
			\draw [->] (3) to [loop below] node {$g$} (3);
			\draw [->] (3) to [loop right] node {$h$} (3);

		\end{tikzpicture}
		\caption{The automaton $\mathcal{M}$ accepting $\mathcal{I}$ for Example~\ref{ex:2}. All states are accepting.}
		\label{fig:ex2_Airr}
	\end{figure}
\end{example}

Let us now describe two implications of our result in the case in which $q$ is small compared with $n$. Recall that the \emph{iterated logarithm} of a positive real number $x$, denoted by $\log^*x$, is the number of times the logarithm function must be iteratively applied before the result is less than or equal to $1$.
\begin{corollary}
For fixed $q$, we can list all monic irreducible polynomials of degree $2^n$ which are compositions of degree $2$ polynomials with complexity $O(q^n  2^n  n  8^{\log^*(2^n)})$, where the implied constant depends only on $q$.
\end{corollary}
\begin{proof}
First, we choose $\mathcal{S}=\{x^2-a: \;a\in \mathbb F_q\}$ and write down the automaton $\mathcal M$ given by Theorem \ref{thm:irred_regular}. The complexity of this step is $O(1)$, where the implied constant clearly depends only on $q$.
Since the distinguished set is maximal, we can identify the polynomials $C_\mathcal{S}$ and the words in $\mathcal{S}^*$.
Now the construction is recursive: let $\mathcal{L}_0(m)$ be the set of words of $\mathcal{S}^*$ of length $m$ (so polynomials of degree $2^m$). For any word $g\in \mathcal{L}_0(m)$ and any $f\in \mathcal{S}$, check if the word $gf$ is accepted by the automaton $\mathcal M$: if it is, $gf$ is an element in $\mathcal{L}_0(m+1)$. This check takes constant time for fixed $q$ if for each element of $\mathcal{L}_0(m)$ we also store the state in which the automaton ends after reading it.
As we observed in Remark~\ref{rem:prefixclosed}, the language accepted by $\mathcal M$ is prefix closed, so  all the elements of $\mathcal{L}_0(m+1)$ can be constructed in this way. Then, constructing $\mathcal{L}_0(m+1)$ from $\mathcal{L}_0(m)$ costs at most $O(q^{m+1})$.

It is elementary now to observe that $\mathcal{L}_0(1)$ can be easily constructed by selecting the irreducible degree $2$ polynomials (again $O(1)$ operations) and therefore that $\mathcal{L}_0(n)$ can be constructed in time at most $O(q^n)$.
Using the proof of Theorem~\ref{thm:disjoint} directly, we know that the set $D(n)$ of all irreducible polynomials of degree $2^n$ which are compositions of degree $2$ polynomials can be written as
\[D(n)=\bigsqcup_{a\in \mathbb{F}_q} \mathcal{L}_a(n),\]
where $\mathcal{L}_a(n)=\{g(x+a): \; g\in \mathcal{L}_0(n)\}$.

In order to represent the elements of $D(n)$ by coefficients, we now need to evaluate the elements of $\mathcal{L}_0(n)$.
For a single such element, if we evaluate it from inside out, this means squaring polynomials of degree $d = 1, 2, \ldots, 2^{n-1}$ and subtracting a constant each time.
According to~\citep{bib:harvey2017faster}, such a squaring can be done in time $O(d \log(d) 8^{\log^*(d)})$, the total time for each element hence being $O(2^n n 8^{\log^*(2^n)})$.
\end{proof}

\begin{remark}
The reader should notice that this is much quicker than listing such polynomials by using an irreducibility test. This would have in fact complexity $O(q^n  2^n  n  8^{\log^*(2^n)}  I(2^n))$, where $I(2^n)$ is the cost of the chosen irreducibility test for a polynomial of degree $2^n$.  Again, the implied constant depends on the time of constructing the automaton, which just depends on the parameter $q$.
\end{remark}

Another interesting fact is that (again for fixed $q$) we have an efficient deterministic algorithm to test irreducibility for polynomials which are a composition of degree two polynomials.

\begin{corollary}\label{cor:irred_test_decomp}
	Let $f$ be a polynomial of degree $2^n$ which is known to be a composition of
	monic degree two polynomials.
	Then $f$ can be tested for irreducibility in time $O(2^nn^2 8^{\log^*(2^n)})$,  where the implied
	constant depends only on $q$.
\end{corollary}
\begin{proof}
	We need to write $f$ in the form $f = g_1 \circ g_2 \circ \cdots \circ g_n
	\circ \ell$, where $g_i = x^2 - a_i$ and $\ell = x - b$, with $a_i$ and $b$ in
	$\mathbb{F}_q$.

	For this, suppose we have $F = G \circ H$ with $G = x^2 - a$, where $a \in
	\mathbb{F}_q$, and $H$ is a polynomial of degree $d \ge 1$.
	Assume $F$ is known, and we seek $G$ and $H$.
	We apply the algorithm \texttt{Univariate decomposition}
	from~\cite[Section~2]{bib:von1990functional} with $r = 2$.
	This gives us the unique $\tilde{G}$ of degree $2$ and $\tilde{H}$ of degree
	$d$ with $\tilde{H}(0) = 0$ such that $F = \tilde{G} \circ \tilde{H}$.
	Clearly, setting $c = H(0)$, we have $\tilde{H} = H - c$ and $\tilde{G} = G(x
	+ c) = x^2 + 2cx + c^2 - a$.
	From this, it is easy to recover $c$, $a$, $G$ and $H$.
	The algorithm \texttt{Univariate decomposition} takes time $O(d \log(d)^2
	8^{\log^*(d)})$, again using the multiplication algorithm
	from~\citep{bib:harvey2017faster}.

	Applying this repeatedly to the $f$ from the theorem will find the
	decomposition $f = g_1 \circ g_2 \circ \cdots \circ g_n \circ \ell$ in $O(2^n
	n^2 8^{\log^*(2^n)})$ time, which can then be checked for irreducibility with
	the automaton in time $O(n)$. Again, for fixed $q$, constructing the automaton has constant complexity, independently of the degree of the polynomial we are testing.
\end{proof}

\begin{remark}
For fixed $q$, testing irreducibility for a polynomial of degree $2^n$ using for example Rabin's test \cite{bib:rabintest} with fast polynomial operations costs $O(n4^{n})$.
\end{remark}

\begin{remark}
As we already mentioned, the whole point is that our algorithm is very efficient
in the regime of small fixed $q$ and large $n$.
Let us nonetheless have a quick look at the complexity with regards to $q$.
If we follow the algorithm as described in
Corollary~\ref{cor:irred_test_decomp} directly, the complexity appears to be
exponential in $q$.
In particular, we can expect the subset construction step  to take
exponential time and space.

Fortunately, it is not in fact necessary to construct the entire automaton to
execute the above algorithm.
Instead, we can solely construct the interim automaton $\mathcal N$ from
Theorem~\ref{thm:irred_regular}.
This takes $O(q^2)$ field operations, and has to be done only once for each $q$.
Then, given the decomposition of the polynomial into $f_1 \circ \cdots\circ f_n$ we can run a word $f_1 \cdots f_n$ through $\mathcal N$ directly as
follows:
define $S_0$ as the set of accepting states of $\mathcal N$.
Then, for $i$ from $1$ to $n$, let $S_i$ be the set of all states $t$ such that
there is a $s \in S_{i-1}$ and a transition $t \xrightarrow{f_i} s$ in $\mathcal
N$.
If at some point $S_i$ does not contain the initial state $\mathfrak{I}$, we reject the
word.
Otherwise, we accept.

This method mirrors the reversal and subset construction from
Theorem~\ref{thm:irred_regular}, except that only the parts that are actually
used are computed.
The complexity of this algorithm is easy to determine:
when computing $S_i$ from $S_{i-1}$, we can iterate over all states $t$ of the
automaton and check whether the unique outgoing transition labelled $f_i$ ends
in $S_{i-1}$.
Hence, each step takes only $O(q)$ field operations, for a total cost of $O(q^2
+ nq)$.
Since for small $q$ the quantity $2^n	n^2 8^{\log^*(2^n)}$ dominates $q^2+nq$, the
complexity in terms of $\mathbb F_q$-operations remains unchanged.
\end{remark}

\section{Irreducible compositions over local fields}

In this final section, we will show how the results of the previous sections can be lifted, under some additional hypothesis, to polynomials over local fields. Let $K$ be a non-archimedean local field with finite residue field $\mathbb{F}_q$ of odd characteristic. Let $\mathcal{O}_K$ be its ring of integers and $\varpi$ be a uniformizer.  We will denote by $\widetilde{\cdot}$ the reduction map $\mathcal{O}_K[x]\to \mathbb{F}_q[x]$. Let us start by recalling the following lemma, which we state in a weaker form, sufficient for our purposes.
\begin{lemma}\label{rafe_lemma}
Let $L$ be any field and let $f,g\in L[x]$ be monic polynomials with $f=(x-a_f)^2-b_f$ for some $a_f,b_f\in L$. Then we have:
\[\disc(g\circ f)=\pm \disc(g)^{2}\cdot 4^{\deg g}\cdot g(-b_f).\]
\end{lemma}
\begin{proof}
 See \cite[Lemma 2.6]{bib:jones}.
\end{proof}

\begin{theorem}\label{local_thm}
 Let $f_1,\ldots,f_k\in \mathcal{O}_K[x]$ be monic polynomials of degree 2 such that $\varpi \nmid \disc(f_1)$. Then $f_1\circ\cdots\circ f_k$ is irreducible in $K[x]$ if and only if $\widetilde{f_1}\circ\cdots\circ \widetilde{f_k}$ is irreducible in $\mathbb{F}_q[x]$.
\end{theorem}
 \begin{proof}

   One direction is obvious, so let us assume that $f_1\circ\cdots\circ f_k$ is irreducible. For every $i=1,\ldots,k$, let $f_i=(x-a_i)^2-b_i$ for some $a_i,b_i\in \mathcal{O}_K$. By Proposition~\ref{thm:irred_long}, we need to show that the following elements are not squares:
   \begin{itemize}
		\item $c_1\coloneqq\widetilde{b_1}$
		\item $c_2\coloneqq\widetilde{f_1}(\widetilde{-b_2})$
		\item[] $\vdots$
		\item $c_k\coloneqq(\widetilde{f_1} \circ \cdots \circ \widetilde{f_{k-1}})(\widetilde{-b_k})$.
	\end{itemize}
    First, suppose that $c_t=0$ for some $t\in \{1,\ldots,k\}$. This implies that $\widetilde{f_1}$ has a root, and since by hypothesis the discriminant of $\widetilde{f_1}$ is non-zero, by Hensel's lemma we can lift such a root to a root of $f_1$. But then $f_1\circ\cdots\circ f_k$ is clearly reducible, which is a contradiction. Thus we can assume that $c_i\neq 0$ for all $i\in\{1,\ldots,k\}$. Now let $t\in \{1,\ldots,k\}$ be such that $c_t$ is a non-zero square. By Proposition~\ref{thm:irred_long}, this implies that $\widetilde{f_1}\circ\cdots\circ \widetilde{f_t}$ is reducible. On the other hand, applying Lemma~\ref{rafe_lemma} recursively and using the definition of the $c_i$'s we get that:
	\[\disc(\widetilde{f_1}\circ\cdots\circ \widetilde{f_t})=u \cdot\prod_{i=1}^{t}c_i^{2^{t-i}}\neq 0,\]
    where $u$ is an appropriate power of 2 (up to sign). This proves that $\varpi \nmid \disc(f_1\circ\cdots\circ f_t)$ and since $f_1\circ\cdots\circ f_t$ is irreducible by hypothesis, it defines an unramified extension of $K$. It follows that $\widetilde{f_1}\circ\cdots\circ \widetilde{f_t}$ is irreducible (see for example~\cite[Chapter~7]{bib:cassels}), giving a contradiction.
 \end{proof}
 It is clear that the hypothesis that $\varpi\nmid \disc(f_1)$ is necessary for the claim to hold, since for example $x^2-\varpi$ is irreducible in $K[x]$, while its reduction is reducible in $\mathbb{F}_q[x]$.

 Given a finite set $\mathcal{S}\subseteq \mathcal{O}_K[x]$ of monic polynomials of degree two with unitary discriminant, Theorem \ref{local_thm} shows that irreducible compositions of the elements of $\mathcal{S}$ correspond bijectively to irreducible compositions of the elements of $\widetilde{\mathcal{S}}\subseteq \mathbb{F}_q[x]$. Therefore, if we consider $\mathcal{S}$ as an alphabet and $\mathcal{I}$ is the language of irreducible compositions of the elements of $\mathcal{S}$, we deduce immediately the following corollary.
 \begin{corollary}
  The language $\mathcal{I}$ is regular.
 \end{corollary}
 \begin{proof}
  It is enough to apply Theorem~\ref{thm:irred_regular} to the language of irreducible compositions of the elements of $\widetilde{\mathcal{S}}$.
 \end{proof}
 The above corollary essentially states that the theory we developed in the rest of the paper lifts entirely to local fields, at least in the case in which the elements in $\mathcal{S}$ have unitary discriminant.
It would be interesting to understand what happens when this condition is not satisfied.
\section{Further research}
One of the natural questions arising from the results in the present paper is whether Theorem~\ref{thm:disjoint} can be generalised to higher degree polynomials. In fact any lift of such results to polynomials of degree three or more would be of great interest, in particular because the necessary and sufficient criterion by Boston and Jones~\citep{bib:jones2012settled} (and the subsequent results on the subject such as~\citep{bib:ahmadi2009note,bib:ahmadi2012stable,ferraguti2016sets,bib:gomez2010estimate,bib:heathbrownmicheli}) only exists in degree two.
In the context of local fields, another interesting issue arising from Theorem \ref{local_thm} of this paper is the following: how can one include singular polynomials in the generating set $\mathcal{S}$? In fact, the condition on the discriminant seems to be essential.
Another question arising from these results is whether it is possible to explicitly compute the generating function of the language of irreducible compositions just in terms of the coefficient of the generating polynomials. It is indeed possible to compute such a function just in terms of the obtained automata, but this would drop most of the available information. In particular, it seems that the key ingredient to address this issue is to understand the structure of the finite submonoid of maps from $\mathbb{F}_q$ to $\mathbb{F}_q$ which can be written as composition of degree two polynomials.
More generally, many of the questions and constructions which were related just to the compositions of a single polynomial, now seem to naturally arise in this more general context, were the rigidity of finite automata theory provides assistance.

\section{Acknowledgements}

The first author was supported by Swiss National Science Foundation grant number 168459. The Second Author is thankful to Swiss National Science Foundation grant number 161757 and 171248.

The authors are thankful to the anonymous referee for his suggestions, which greatly improved the content and the readability of the paper. We are expecially thankful for suggesting a reference which boiled down the complexity in Corollary \ref{cor:irred_test_decomp} from $O(4^n)$ to $O(2^n	n^2 8^{\log^*(2^n)})$.

\bibliographystyle{plain}


\section{Parametrizations}

In this section, we first recall how a Euclidean hypersurface of constant
rank can be locally parametrized by the use of the Gauss parametrization.
Then, we  discuss a class of envelopes of hyperplanes depending on parameters
as well how they can be  described in terms of the Gauss parametrization.

\subsection{The Gauss parametrization}

Let $f\colon M^n\to\mathbb{R}^{n+1}$ be an isometric immersion of constant rank
$k$ for $1\leq k\leq n-1$.  By that we mean that its second fundamental
form $A$ has constant rank $k$ or, equivalently, that the relative nullity
subspaces, i.e., the kernels of its second form  $\Delta(x)=\mbox{ker } A(x)$,
satisfy $\dim\Delta(x)=n-k$  at any $x\in M^n$.
In this situation, it is a standard fact that the tangent distribution
$x\in M^n\mapsto\Delta(x)$ is integrable and that its totally geodesic
leaves are mapped by $f$ into open subsets of affine subspaces of $\mathbb{R}^{n+1}$

A hypersurface of constant rank can be locally parametrized in terms of
the image of its Gauss map $N$ and its support function $\gamma=\<f,N\>$.
This parametrization is known as the  \emph{Gauss parametrization}
and was described in \cite{dg} but it was already used by Sbrana
in \cite{sb1} and \cite{sb2} long before.
\vspace{1ex}

Let  $(g,\gamma)$ be a pair formed by an isometric immersion
$g\colon L^k\to\mathbb{S}^n$ into the unit sphere and a function
$\gamma\in C^\infty(L)$. Denote by $\bar\pi\colon\Lambda\to L^k$ the normal
bundle of $g$ and set $h=i\circ g$ where $i\colon\mathbb{S}^n\to\mathbb{R}^{n+1}$
is the standard inclusion. It was shown in \cite{dg} that the map
$\psi\colon \Lambda\to\mathbb{R}^{n+1}$ given by
$$
\psi(x,w)=\gamma(x)h(x)+h_*\mbox{grad\,}\gamma(x)+i_*w
$$
parametrizes (at regular points) a hypersurface of constant rank $k$ such
that the fibers of $\Lambda$ are identified with the leaves of the
relative nullity foliation of $\psi$.

Conversely, any  hypersurface $f\colon M^n\to\mathbb{R}^{n+1}$ of constant  rank $k$ can be
locally parametrized as above.   In fact, let  $U\subset M^n$ be
an open saturated subset  of leaves of relative nullity
and let $\pi\colon U\to L^{n-k}$ denote the projection onto the quotient space.
The Gauss map $N$ of $f$  induces an immersion $g\colon L^{n-k}\to\mathbb{S}^n$
given by $g\circ\pi = N$. Moreover, since the support function
$\<f,N\>$ is  constant along the relative nullity leaves, hence it induces
a function $\gamma\in C^\infty(L)$. Now the Gauss parametrization allows
to recover $f$ by means of the pair $(g,\gamma)$.
\vspace{1,5ex}

The next statement presents some basic properties of the
Gauss parametrization.

\begin{proposition}{\hspace*{-1ex}}{\bf .  }\label{gp} The following assertions hold:
\begin{itemize}
\item[(i)] The map $\psi\colon \Lambda\to\mathbb{R}^{n+1}$ is regular at $(x,w)$
if and only if  the self adjoint operator
$$
P_w(x)=\gamma(x)I+\emph{Hess}\,\gamma(x)-A_w
$$
on $T_xL$ is nonsingular. Here $A_w$ is the shape operator of $g$
with respect to $w$.
\item[(ii)]  The map $\psi$ when restricted to the open subset $V$ of regular
points is an immersed hypersurface having the map $N\colon\Lambda\to\mathbb{S}^n$
given by $N(x,w)=g(x)$ as a Gauss map of rank $k$.
\item[(iii)] If $(x,w)\in V$ there is $j(x,w)\colon T_xL\to T_{(x,w)}\Lambda$
so that $j\colon T_xL\to\Delta^\perp(x,w)\subset T_{(x,v)}\Lambda$ is
an isometry such that
\begin{equation} \label{eq}
h_*=\psi_*\circ j,\;\;\;P_w^{-1}=\bar\pi_*\circ j\;\;\mbox{and}\;\;
A\circ  j=-j\circ P_w^{-1}
\end{equation}
where $A$ is the shape operator of $\psi$ at $(x,w)$ with respect to $N$.
\end{itemize}
\end{proposition}

\noindent\emph{Proof: } See \cite{dg}.\qed

\subsection{Envelopes of hyperplanes}

Let $P_u\colon\mathbb{R}^n\to\mathbb{R}^{n+1}$, $n\geq 2$, denote a smooth $k$-parameter
family of affine hyperplanes parametrized by $u=(u_1,\ldots,u_k)$ on an
open subset $U\subset\mathbb{R}^k$ with $1\leq k\leq n-1$.
\vspace{1ex}

We say that a hypersurface  $f\colon M^n\to\mathbb{R}^{n+1}$ is the
\emph{envelope of hyperplanes} of $(P_u)_{u\in U}$  if there exists
a smooth totally geodesic foliation of $M^n$ by leaves
$(L_u)_{u\in U}$ of dimension  $n-k$ parametrized by an embedding
$h\colon U\to M^n$ transversal to the foliation and embeddings
$j_u\colon L_u\to P_u(\mathbb{R}^n)$ as  open subset of $(n-k)$-dimensional
affine subspaces of $\mathbb{R}^{n+1}$ such that $j_u=f\vert_{L_u}$ and
$P_u(\mathbb{R}^n)=f_*T_{h(u)}M$ for any $u\in U$.
\vspace{1ex}

Clearly, the leaves of $(L_u)_{u\in U}$ are contained in the relative nullity
of $f$. Also notice that any hypersurface $f\colon M^n\to\mathbb{R}^{n+1}$ with constant
index of  relative nullity $\nu=n-k$ is the envelope of the $k$-parameter family of
tangent hyperplanes.
\vspace{1ex}

A $k$-parameter family of affine hyperplanes $(P_u)_{u\in U}$ can be given
in terms of a smooth family  of equations of the form
$$
G(u)=\varphi_1x_1+\cdots +\varphi_{n+1}x_{n+1}-\varphi_0=0
$$
where $\varphi_j\in C^\infty(U)$, $0\leq j\leq n+1$, and
$x=(x_1,\ldots,x_{n+1})$ are coordinates in $\mathbb{R}^{n+1}$ with respect
to a canonical base.

Assume that the map
$\varphi=(\varphi_1,\ldots,\varphi_{n+1})\colon U\to\mathbb{R}^{n+1}$
is an immersion and without loss of generality that
$0\not\in\varphi(U)$.  Let $g\colon U\to\mathbb{S}^n\subset\mathbb{R}^{n+1}$
and $\gamma\in C^\infty(U)$ be given by
$$
g=\frac{1}{\phi}(\varphi_1,\ldots,\varphi_{n+1})\;\;\mbox{and}
\;\;\gamma=\frac{\varphi_0}{\phi}
$$
where $\phi^2=\sum_{j=1}^{n+1}\varphi_j^2$.

Being $g$ is an immersion, the pair $(g,\gamma)$  gives a
hypersurface $f\colon M^n\to\mathbb{R}^{n+1}$ by means of the Gauss
parametrization. Clearly $f$ is the envelope of $(P_u)_{u\in U}$
and the leaves $(L_u)_{u\in U}$ of the envelope coincide with the
relative nullity foliation of $f$.  Moreover,  the envelope of
$(P_u)_{u\in U}$ can be locally given as the solution of the
system of equations
$$
(R)\begin{cases}
G(u)=0\\
G_{u_j}(u)=0,\;\;j=1,\ldots,k.
\end{cases}
$$

We have shown the following fact.

\begin{proposition}{\hspace*{-1ex}}{\bf .  } Any hypersurface $f\colon M^n\to\mathbb{R}^{n+1}$
of constant rank $k$ can be locally  given as the envelope
of a smooth family of affine hyperplanes
$$
G(u)=\varphi_1x_1+\cdots +\varphi_{n+1}x_{n+1}-\varphi_0=0
$$
where $(\varphi_1,\ldots,\varphi_{n+1})\colon U\to\mathbb{R}^{n+1}$
is an immersion of an open subset $U$ of $\mathbb{R}^k$.
Then $f$ is locally the solution of the  system of equations $(R)$.
\end{proposition}

\section{A class of surfaces}

A surface $g\colon L^2\to\mathbb{S}^n$ in the unit sphere is called
\emph{hyperbolic} (respectively, \emph{elliptic}) if there exists a
tensor $J$ on $L^2$ satisfying $J^2=I$ and $J\neq I$
(respectively, $J^2=-I$) and such that the second fundamental form
$\alpha_g\colon TL\times TL\to N_gL$ of $g$ satisfies
\begin{equation} \label{eq:aJ}
\alpha_g(JX,Y)=\alpha_g(X,JY)
\end{equation}
for all vector fields $X,Y\in\mathfrak{X}(L)$.
Local coordinates $(u,v)$ on $L^2$  are called
\emph{real-conjugate} for $g$ if the condition
$$
\alpha_g(\partial_u,\partial_v)=0
$$
holds where $\partial_u=\partial/\partial u$ and $\partial_v=\partial/\partial v$.
They are called \emph{complex-conjugate} if the condition
$\alpha_g(\partial,\bar\partial)=0$
holds where  $\partial=\partial_z=(1/2)(\partial_u-i\partial_v)$, that is, if we have that
$$
\alpha_g(\partial_u,\partial_u) + \alpha_g(\partial_v,\partial_v)=0.
$$

A simple argument (see \cite{dft}) gives the following result.

\begin{proposition}{\hspace*{-1ex}}{\bf .  }\label{coordinates}
Let $g\colon L^2\to\mathbb{S}^n$ be a hyperbolic (respectively, elliptic) surface.
Then  there exists locally a real-conjugate (respectively, complex-conjugate)
system of coordinates on $L^2$ for $g$. Conversely, if there exists real-conjugate
(respectively, complex-conjugate) coordinates on $L^2$, then
$g$ is a hyperbolic (respectively, elliptic) surface.
\end{proposition}

Let $g\colon L^2\to\mathbb{S}^n$ be a simply-connected surface that carries a
real-conjugate system of coordinates $(u,v)$. Equivalently, the isometric
immersion $h=i\circ g\colon L^2\to\mathbb{R}^{n+1}$ satisfies
\begin{equation} \label{eq:guv}
h_{uv}-\gg h_u-\Gamma^2  h_v + Fh=0
\end{equation}
where $\gg,\Gamma^2 $ are the Christoffel symbols given by
$$
\nabla_{\partial_u}\partial_v=\gg\partial_u+\Gamma^2 \partial_v
$$
and $F=\<\partial_u,\partial_v\>$.

We are interested in surfaces for which, in addition, the following system of
differential equations admits solution:
\begin{equation} \label{eq:siti}
d\mu+2\mu\o=0\;\;\;\mbox{where}\;\;\; \o=\Gamma^2  du+\gg dv.
\end{equation}
This is the case if and only if the integrability condition
\begin{equation} \label{integcon}
\gg_u=\Gamma^2 _v
\end{equation}
is satisfied.

\begin{proposition}{\hspace*{-1ex}}{\bf .  } Let $g\colon L^2\to\mathbb{S}^n$ be a hyperbolic surface
with real conjugate coordinates $(u,v)$ such that the induced metric satisfies
condition (\ref{integcon}).  Then there is a positive function
$\mu\in C^\infty(L)$ such that $\varphi$ is a solution of (\ref{eq:guv})
if and only if $\psi=\sqrt{\mu}\varphi$ is a solution of
$$
\psi_{uv}+M\psi=0
$$
where  $M\in C^\infty(L)$ is given by
\begin{equation} \label{Mm}
M=F-\frac{\mu_{uv}}{2\mu}+\frac{\mu_u\mu_v}{4\mu^2}\cdot
\end{equation}
In particular, the immersion
$k=\sqrt{\mu}\,h\colon L^2\to\mathbb{R}^{n+1}$ satisfies
\begin{equation} \label{form}
k_{uv}+Mk=0.
\end{equation}
Conversely, let $k\colon L^2\to\mathbb{R}^{n+1}$ be an isometric immersion
that for a system of coordinates  $(u,v)$ satisfies (\ref{form})
where  $M\in C^\infty(L)$. Then $(u,v)$ are real conjugate coordinates
for the immersion $g=(1/\|k\|)\,k\colon L^2\to\mathbb{S}^n$ and
condition (\ref{integcon}) is satisfied for the induced metric.
\end{proposition}

\noindent\emph{Proof: } If $g$ satisfies the integrability condition, then
$$
\gg=-\frac{\mu_v}{2\mu},\;\;\;\Gamma^2 =-\frac{\mu_u}{2\mu}
$$
where $\mu=c\,e^{-2\int\o}$ for any $c\in\mathbb{R}_+$. Hence (\ref{eq:guv})
becomes
\begin{equation} \label{eq:guv2}
h_{uv}+\frac{\mu_v}{2\mu}h_u+\frac{\mu_u}{2\mu}h_v+Fh=0.
\end{equation}
It follows easily that $k=\sqrt{\mu}\,h$ takes the form (\ref{form})
where $M$ is given by (\ref{Mm}).
The converse is a straightforward computation.\vspace{1,5ex}\qed

Let $g\colon L^2\to\mathbb{S}^n$ be a simply-connected surface endowed
with  complex-conjugate coordinates $(z,\bar{z})$.
Equivalently, the isometric immersion $h=i\circ g\colon L^2\to\mathbb{R}^{n+1}$
satisfies
\begin{equation} \label{eq:guz}
h_{z\bar z}-\Gamma h_z-\bar\Gamma h_{\bar z}+Fh=0
\end{equation}
where the Christoffel symbols, obtained using the $\mathbb{C}$-linear extensions
of the metric of $L^2$ and the corresponding connection, are given by
$$
\nabla_{\partial}\bar\partial=\Gamma\partial+\bar \Gamma\bar\partial
$$
and $F=\<\partial,\bar\partial\>$.

We are interested in surfaces for which, in addition, the following
system of differential equations for $\mu$ real admits solutions:
\begin{equation}  \label{eq:comp}
\mu_{\bar{z}}+2\mu\Gamma=0.
\end{equation}
This is the case if and only if the integrability condition
\begin{equation} \label{integcon2}
\Gamma_z=\bar{\Gamma}_{\bar z},
\end{equation}
that is, $\Gamma_z\;\mbox{is real}$, is satisfied.

\begin{proposition}{\hspace*{-1ex}}{\bf .  } Let $g\colon L^2\to\mathbb{S}^n$ be an elliptic surface
with complex  conjugate coordinates $(z,\bar{z})$  such that the induced
metric satisfies condition (\ref{integcon2}).
Then, there is a positive solution  $\mu\in C^\infty(L)$
of (\ref{eq:comp}) such that $\varphi$ is a solution of (\ref{eq:guz})
if and only if $\psi=\sqrt{\mu}\varphi$ is a solution of
$$
\psi_{z\bar z}+M\psi=0
$$
where  $M\in C^\infty(L)$ is given by
\begin{equation} \label{Mm2}
M=F-\frac{\mu_{z\bar z}}{2\mu}+\frac{\mu_z\mu_{\bar z}}{4\mu^2}\cdot
\end{equation}
In particular, the immersion
$k=\sqrt{\mu}\,h\colon L^2\to\mathbb{R}^{n+1}$ satisfies
\begin{equation} \label{form2}
k_{z\bar z}+Mk=0.
\end{equation}

Conversely, let $k\colon L^2\to\mathbb{R}^{n+1}$ be an isometric immersion that
 for a system of coordinates  $(z,\bar{z})$ satisfies (\ref{form2})
where  $M\in C^\infty(L)$. Then $(z,\bar{z})$ are complex conjugate
coordinates for the immersion $g=(1/\|k\|)k\colon L^2\to\mathbb{S}^n$  and
condition  (\ref{integcon2}) is satisfied for the induced metric.
\end{proposition}

\noindent\emph{Proof: } We have $\mu=c\,e^{-2\int\o}$ for any $c\in\mathbb{R}_+$ where
$\o=\Gamma d\bar{z}$. Then (\ref{eq:guz}) takes the form
$$
h_{z\bar z}+\frac{\mu_z}{2\mu}h_z+\frac{\mu_{\bar z}}{2\mu}h_{\bar z}+Fh=0.
$$
It follows easily that $k=\sqrt{\mu}\,h$ is as in  (\ref{form2}) where
$M$ is given by (\ref{Mm2}).
The converse is a straightforward computation.\qed

\section{The main result}

After introducing the necessary terminology and definitions, we  present
the main result of the paper in terms of the Gauss parametrization, as
is the case in the paper by Sbrana.  The proof of the alternative version
of the theorem in terms  of envelopes of hyperplanes given in the introduction
can easily be obtained from this version using results from the preceding
sections.
\vspace{1,5ex}

By a \emph{variation} $F$ of an isometric immersion $f\colon M^n\to\mathbb{R}^{n+1}$
we mean a smooth map $F\colon (-\epsilon, \epsilon)\times M^n\to\mathbb{R}^{n+1}$
such that $f_t=F(t,\cdot)$ is an immersion for each $t\in I=(-\epsilon,
\epsilon)$ and  $f=f_0$.
The variational vector field of $F$ is the section ${\cal T}\in\Gamma(f^*(T\mathbb{R}^{n+1}))$
of the Riemannian vector bundle $f^*(T\mathbb{R}^{n+1})$ defined as
$$
{\cal T}(x)=F_*\partial/\partial t|_{t=0}(x).
$$

A variation $F$ of a given isometric immersion
$f\colon M^n\to\mathbb{R}^{n+1}$ is called an \emph{isometric bending} if
$f_t$ is an isometric immersion for any $t\in I$.
The variational vector field of an isometric bending satisfies
$$
\<\tilde\nabla_X{\cal T},f_*Y\>+\<f_*X,\tilde\nabla_Y{\cal T}\>=0
$$
for any $X,Y\in\mathfrak{X}(M)$. Equivalently, it satisfies that
$$
\<\tilde\nabla_X{\cal T},f_*X\>=0
$$
for any $X\in\mathfrak{X}(M)$.
\vspace{1ex}

An isometric bending $F$ is called \emph{trivial} if it is produced by a smooth
one-parameter family of isometries of $\mathbb{R}^{n+1}$, that is, if there
exist a smooth family ${\cal C}\colon I\to O(n+1)$ of orthogonal transformations
of $\mathbb{R}^{n+1}$ and a smooth map $v\colon I\to \mathbb{R}^{n+1}$ such that
$$
F(t,x)={\cal C}(t)f(x)+v(t).
$$
For a trivial isometric bending the variational vector field is of the form
$$
{\cal T}(x)={\cal D}f(x)+w
$$
where ${\cal D}={\cal C}'(0)$ is a skew-symmetric linear endomorphism of $\mathbb{R}^{n+1}$
and $w=v'(0)$ a vector in  $\mathbb{R}^{n+1}$.
Conversely, given a skew-symmetric linear endomorphism ${\cal D}$ of $\mathbb{R}^{n+1}$
and a vector $w\in\mathbb{R}^{n+1}$, the map
$$
F(t,x)=e^{t{\cal D}}f(x)+tw
$$
defines a  trivial isometric bending that has ${\cal T}={\cal D}f+w$ as variational
vector field.
\vspace{1ex}

By an \emph{infinitesimal bending} ${\cal T}$ of an isometric immersion
$f\colon M^n\to\mathbb{R}^{n+1}$ we mean an element of $\Gamma(f^*(T\mathbb{R}^{n+1}))$
that satisfies
\begin{equation} \label{iif0}
\<\tilde\nabla_X{\cal T},f_*Y\>+\<f_*X,\tilde\nabla_Y{\cal T}\>=0
\end{equation}
for any $X,Y\in\mathfrak{X}(M)$.
An infinitesimal bending is said to be \emph{trivial} if
$$
{\cal T}(x)={\cal D}f(x)+w
$$
where ${\cal D}$ is a skew-symmetric linear
endomorphism of $\mathbb{R}^{n+1}$ and $w\in\mathbb{R}^{n+1}$.
\vspace{1ex}

An isometric immersion $f\colon M^n\to\mathbb{R}^{n+1}$ is called \emph{infinitesimally
bendable} if it admits a nontrivial infinitesimal bending.  Otherwise,
it is said that $f$ is \emph{infinitesimally rigid}.
\vspace{1ex}

Multiplying a given infinitesimal bending by a real constant and adding a trivial
infinitesimal bending yields a new infinitesimal bending. In the sequel,
we identify two infinitesimal bendings ${\cal T}_1$ and ${\cal T}_2$ if
${\cal T}_2={\cal T}_0 + c\,{\cal T}_1$ where ${\cal T}_0$ is a trivial infinitesimal bending and
$0\neq c\in\mathbb{R}$.
\vspace{1ex}

We have already observed  that hypersurfaces of rank at least three at any point
are infinitesimally rigid.  Therefore, the interesting case to be considered is
the one of constant rank two.  We see next that even in this special case
hypersurfaces are ``generically" infinitesimally rigid.
\vspace{1ex}

We call the pair $(g,\gamma)$ a \emph{special hyperbolic pair}
(respectively, \emph{special elliptic pair}) if  $g\colon L^2\to\mathbb{S}^n$
is a hyperbolic (respectively, elliptic) surface so that system (\ref{eq:siti})
(respectively, system (\ref{eq:comp})) has solution and $\gamma\in C^\infty(L)$
satisfies (\ref{eq:guv}) (respectively,  (\ref{eq:guz})).

\begin{theorem}{\hspace*{-1ex}}{\bf .  }\label{main} Let $f\colon M^n\to\mathbb{R}^{n+1}$, $n\geq 3$, be an
infinitesimally bendable hypersurface of constant rank two that is neither
surface-like nor ruled on any open subset of $M^n$. Then, there is
an open and dense subset of $M^n$ such that along any connected
component $f$ is parametrized in terms of the Gauss parametrization
by a special hyperbolic or a special elliptic pair.

Conversely, any hypersurface parametrized in terms of the Gauss
parametrization by a special hyperbolic or special elliptic pair
admits locally a  unique infinitesimal bending.
\end{theorem}

The case of ruled hypersurfaces that has been excluded from consideration
in the above result is rather simple and will be treated separately in
Section $5$.

\section{Existence and uniqueness}

 We study the system of differential equations of  an infinitesimal
bending of a Euclidean hypersurface and discuss its integrability
conditions. This yields a kind of fundamental theorem for
infinitesimal bendings that is,  basically, contained in Sbrana's
paper  \cite{sb1}.  In fact, the case of arbitrary codimension
was later taken on by Schouten \cite{sc} but presented in a rather difficult
terminology.  We point out that in this section some  long but straightforward
computations are only indicated.
\vspace{1,5ex}

Given a hypersurface $f\colon M^n\to\mathbb{R}^{n+1}$, $n\geq 3$, in the sequel
we associate to any infinitesimal bending ${\cal T}$ of $f$ the variation
$F\colon \mathbb{R}\times M^n\to\mathbb{R}^{n+1}$ with variational vector field
${\cal T}$ given by
$$
F(t,x)=f(x)+t{\cal T}(x).
$$
It is usually said that  $f_t=F(t,\cdot)$ is isometric to $f$ up to first
order for if
\begin{equation} \label{var}
\|f_{t*}X\|^2=\|f_*X\|^2+t^2\|\tilde\nabla_X{\cal T}\|^2
\end{equation}
for all $X\in\mathfrak{X}(M)$.

Let $g_t$ be the metric on $M^n$ induce by $f_t$. Then,
$$
\partial/\partial t\vert_{t=0}\,g_t(X,Y)=0
$$
for all $X,Y\in\mathfrak{X}(M)$.  Consequently, we have that the  associated
one-parameter family of Levi-Civita connections and the corresponding
family of curvature tensors satisfy
$$
\partial/\partial t\vert_{t=0}\,f_*\nabla^t_XY=0
$$
and
\begin{equation} \label{curvature}
\partial/\partial t\vert_{t=0}\,\<R^t(X,Y)Z,W\>=0
\end{equation}
for all $X,Y,Z,W\in\mathfrak{X}(M)$.
\vspace{1ex}

 Let $N(t)$ denote a Gauss map of $f_t$ and $A(t)$ the second fundamental
form of $f_t$ with respect to $N(t)$ so that the map $t\in\mathbb{R}\mapsto N(t)$
is smooth.  Then  $N=N(0)$ is the Gauss map and $A=A(0)$ is the second
fundamental form of $f$. Moreover, let us define
$L\in\Gamma(\mbox{End}(TM,f^*(T\mathbb{R}^{n+1}))$ by
$$
LX=\tilde\nabla_X{\cal T}={\cal T}_*X.
$$
Then (\ref{iif0}) can be written as
\begin{equation} \label{iif}
\<LX,f_*Y\>+\<f_*X,LY\>=0
\end{equation}
for all $X,Y\in\mathfrak{X}(M)$.

\begin{lemma}{\hspace*{-1ex}}{\bf .  } We have that
${\cal Y}=\partial/\partial t\vert_{t=0}\, N(t)\in\Gamma(f^*(T\mathbb{R}^{n+1}))$ satisfies
\begin{equation} \label{4}
\<{\cal Y},N\>=0
\end{equation}
and
\begin{equation} \label{3}
\<{\cal Y},f_*X\>+\<LX,N\>=0
\end{equation}
for all $X\in\mathfrak{X}(M)$.
\end{lemma}

\noindent\emph{Proof: } The derivative with respect to $t$ at $t=0$ of $\<N(t),N(t)\>=1$
gives (\ref{4}) whereas  of $\<N(t),f_{t*}X\>=0$ yields (\ref{3}).\qed

\begin{lemma}{\hspace*{-1ex}}{\bf .  }
We have that $B=\partial/\partial t\vert_{t=0}\, A(t)\in\Gamma(\mbox{End}(TM))$
is symmetric and satisfies
\begin{equation} \label{1}
(\tilde\nabla_XL)Y=\<BX,Y\>N+\<AX,Y\>{\cal Y}
\end{equation}
and
\begin{equation} \label{2}
{\cal Y}_*X=-f_*BX-LAX
\end{equation}
for all $X,Y\in\mathfrak{X}(M)$.
\end{lemma}

\noindent\emph{Proof: } The derivative with respect to $t$ at $t=0$ of the Gauss formula
$$
\tilde\nabla_Xf_{t*}Y=f_{t*}\nabla^t_XY + g_t(A(t)X,Y)N(t)
$$
 easily gives (\ref{1}).
As for the Weingarten formula
$$
\tilde\nabla_XN(t)=-f_{t*}(A(t)X)
$$
we have that its derivative at $t=0$ yields (\ref{2}).
\vspace{1,5ex}\qed

If ${\cal T}={\cal D}f+w$ is a trivial infinitesimal bending then
$L={\cal D}\circ f_*$.  It follows that
${\cal Y}={\cal D}N$  and that $B=0$ since
$$
\<BX,Y\>=\<(\tilde\nabla_XL)Y,N\>=\<(\tilde\nabla_X{\cal D})Y,N\>=0
$$
for all $X,Y\in\mathfrak{X}(M)$.

\begin{proposition}{\hspace*{-1ex}}{\bf .  }  The tensor $B$ is a symmetric Codazzi
tensor, i.e.,
\begin{equation} \label{6}
\left(\nabla_XB\right)Y-\left(\nabla_YB\right)X=0
\end{equation}
such that
\begin{equation} \label{5}
BX\wedge AY-BY\wedge AX=0
\end{equation}
for all $X,Y\in\mathfrak{X}(M)$.
\end{proposition}

\noindent\emph{Proof: }  The derivative at $t=0$ of the Codazzi equation
$$
\left(\nabla^t_XA(t)\right)Y=\left(\nabla^t_YA(t)\right)X
$$
gives (\ref{6}).
To obtain (\ref{5}) we compute the derivative at $t=0$ of the
Gauss equation
$$
R^t(X,Y)Z=g(t)(A(t)Y,Z)A(t)X-g(t)(A(t)X,Z)A(t)Y
$$
and use (\ref{curvature}).\vspace{1,5ex}\qed

The next result is to be expected bearing in mind the nature of the Gauss
and Codazzi equations as the integrability conditions for the system of
differential equations associated to an isometric immersion as a hypersurface.

\begin{lemma}{\hspace*{-1ex}}{\bf .  }\label{sys} Equations (\ref{6}) and (\ref{5}) are the
integrability conditions of the system of  differential equations
(\ref{1}) and (\ref{2}) for $L$ and ${\cal Y}$, that is,
$$
(S)\begin{cases}
{\cal Y}_*X=-LAX-f_*BX\\
(\tilde\nabla_XL)Y=\<BX,Y\>N+\<AX,Y\>{\cal Y}.
\end{cases}
$$
\end{lemma}

\noindent\emph{Proof: } For the first equation, we have to show that
\begin{equation} \label{condi1}
\tilde\nabla_X{\cal Y}_*Y-\tilde\nabla_Y{\cal Y}_*X-\tilde\nabla_{[X,Y]}{\cal Y}=0
\end{equation}
for all $X,Y\in\mathfrak{X}(M)$. One has that
$$
\tilde\nabla_X{\cal Y}_*Y=-(\tilde\nabla_XL)AY-L(\nabla_XA)Y-LA\nabla_XY-f_*\nabla_XBY-\<AX,BY\>N.
$$
Then (\ref{condi1}) is equivalent to
$$
(\tilde\nabla_XL)AY-(\tilde\nabla_YL)AX+f_*((\nabla_XB)Y-(\nabla_YB)X)
+(\<AX,BY\>-\<AY,BX\>)N=0.
$$
Replacing the first two terms by the use of the second equation in $(S)$
it is easily seen that (\ref{condi1}) follows from (\ref{6}).

It is easy to see that the integrability condition for the second
equation is
\begin{equation} \label{condi2}
(\tilde\nabla_X\tilde\nabla_YL-\tilde\nabla_Y\tilde\nabla_XL-\tilde\nabla_{[X,Y]}L)Z=-LR(X,Y)Z
\end{equation}
for all $X,Y,Z,W\in\mathfrak{X}(M)$.
A straightforward computation using (\ref{1}) gives
\begin{eqnarray*}
(\tilde\nabla_X\tilde\nabla_YL)Z\!\!\!&=&\!\!\!\<(\nabla_XB)Y,Z\>N+\<B\nabla_XY,Z\>N
-\<BY,Z\>f_*AX+\<(\nabla_XA)Y,Z\>{\cal Y}\\
\!\!\!&&\!\!\!+\; \<A\nabla_XY,Z\>{\cal Y}
-\<AY,Z\>LAX-\<AY,Z\>f_*BX.
\end{eqnarray*}
That $A$ is a Codazzi tensor together with (\ref{6}) yields
\begin{eqnarray*}
(\tilde\nabla_X\tilde\nabla_YL-\tilde\nabla_Y\tilde\nabla_XL-\tilde\nabla_{[X,Y]}L)Z
\!\!\!&=&\!\!\!-\<BY,Z\>f_*AX-\<AY,Z\>(LAX+f_*BX)\\
\!\!\!&&\!\!\!+\,\<BX,Z\>f_*AY-\<AX,Z\>(LAY+f_*BX).
\end{eqnarray*}
On the other hand,  we have
$$
LR(X,Y)Z=\<AY,Z\>LAX-\<AX,Z\>LAY,
$$
and (\ref{condi2}) follows using (\ref{5}).\vspace{1,5ex}\qed

Next we consider the case of hypersurfaces of constant rank two.

\begin{corollary}\label{kerB}{\hspace*{-1ex}}{\bf .  } If $f\colon M^n\to\mathbb{R}^{n+1}$, $n\geq 3$,
is an infinitesimally bendable hypersurface of constant rank two,
then $\Delta\subset\ker B$.
\end{corollary}

\noindent\emph{Proof: }  This follows easily from (\ref{5}).

\begin{theorem}{\hspace*{-1ex}}{\bf .  }\label{mains}  Let $f\colon M^n\to\mathbb{R}^{n+1}$, $n\geq 3$, be a
simply-connected  hypersurface of constant rank two.
Then, the set of all symmetric Codazzi tensors
$B\in\Gamma(\mbox{End}(TM))$  such that $\Delta\subset\ker B$ and
$$
BX\wedge AY-BY\wedge AX=0
$$
for all $X,Y\in\mathfrak{X}(M)$ is in one-to-one correspondence with
the set of all infinitesimal bendings of $f$ so that $B=0$ corresponds
to the trivial one.
\end{theorem}

\noindent\emph{Proof: } Given  $B\in\Gamma(\mbox{End}(TM))$ as in the statement,
we first prove that there exists a solution ${\cal Y}$  and $L$ of system
$(S)$ such that (\ref{iif}), (\ref{4}) and (\ref{3}) are satisfied.
In particular, this gives the existence of an infinitesimal bending
${\cal T}$ such that $L={\cal T}_*$. To see this, observe that by (\ref{1}) the
one-form $\o=\<L,v\>$ is closed for any $v\in\mathbb{R}^{n+1}$.

Given a solution  ${\cal Y}$ and $L$ of $(S)$, we define a smooth function by
$$
\tau=\<{\cal Y},N\>,
$$
a smooth one-form by
$$
\theta(X)=\<{\cal Y},f_*X\>+\<LX,N\>
$$
and a smooth symmetric bilinear tensor by
$$
\beta(X,Y)=\<LX,f_*Y\>+\<LY,f_*X\>.
$$
A straightforward calculation gives that
\begin{equation} \label{tau}
d\tau=-\theta\circ A,
\end{equation}
\begin{equation} \label{theta}
(\nabla_X\theta)Y=-\beta(AX,Y)+2\tau\<AX,Y\>
\end{equation}
and
\begin{equation} \label{M}
(\nabla_Z\beta)(X,Y)=\<AX,Y\>\theta(Z)+\<AX,Z\>\theta(Y)
\end{equation}
for all $X,Y,Z\in\mathfrak{X}(M)$.

We claim that the system of differential equations formed by (\ref{tau}),
(\ref{theta}) and (\ref{M}) is completely integrable.  The integrability
condition for the first equation is easy to verify. For the second equation,
we have to see that
\begin{equation} \label{cal1}
(\nabla_X\nabla_Y\theta-\nabla_Y\nabla_X\theta-\nabla_{[X,Y]}\theta)Z
=-\theta(R(X,Y)Z)
\end{equation}
holds. Using (\ref{tau}) and (\ref{theta}) we obtain
$$
(\nabla_X\nabla_Y\theta)Z=-(\nabla_X\beta)(AY,Z)
-\beta(\nabla_XAY,Z)-2\theta(AX)\<AY,Z\>
+2\tau\<\nabla_XAY,Z\>.
$$
Hence
\begin{align*}
 (\nabla_X\nabla_Y\theta-\nabla_Y\nabla_X\theta-\nabla_{[X,Y]}\theta)Z
=&-(\nabla_X\beta)(AY,Z)+(\nabla_Y\beta)(AX,Z)\\
&\,-2\theta(AX)\<AY,Z\>+2\theta(AY)\<AX,Z\>.
\end{align*}
Using (\ref{M}) we obtain that
$$
(\nabla_X\nabla_Y\theta-\nabla_Y\nabla_X\theta-\nabla_{[X,Y]}\theta)Z
=-\theta(AX)\<AY,Z\>+\theta(AY)\<AX,Z\>.
$$
On the other hand, we have from the Gauss equation that
$$
\theta(R(X,Y)Z)=\<AY,Z\>\theta(AX)-\<AX,Z\>\theta(AY),
$$
and (\ref{cal1}) follows.

Finally, the integrability condition for the last equation, namely, that
\begin{equation} \label{cal2}
\!\!(\nabla_X\nabla_Y\beta-\nabla_Y\nabla_X\beta-\nabla_{[X,Y]}\beta)(Z,W)
=-\beta(R(X,Y)Z,W)-\beta(R(X,Y)W,Z)
\end{equation}
can be verified by a similar computation, and this
proves the claim.

Start with a solution $L^*$ and ${\cal Y}^*$ of system $(S)$ with
corresponding tensors $\theta^*$,  $\beta^*$ and function $\tau^*$.
Fix a point $p_0\in M^n$ and let $L_0$ and ${\cal Y}_0$ be a solution of the
integrable system
$$
(S_0)\begin{cases}
{\cal Y}_*X=-LAX\\
(\tilde\nabla_XL)Y=\<AX,Y\>{\cal Y}
\end{cases}
$$
with  initial conditions $\theta_0(p_0)=\theta^*(p_0)$,
$\beta_0(p_0)=\beta^*(p_0)$ and $\tau_0(p_0)=\tau^*(p_0)$.
Then $L=L^*-L_0$ and
${\cal Y}={\cal Y}^*-{\cal Y}_0$ are a solution of $(S)$ such that
$\theta=\theta^*-\theta_0$,  $\beta=\beta^*-\beta_0$ and
$\tau=\tau^*-\tau_0$. Clearly $\theta(p_0)=\beta(p_0)=\tau(p_0)=0$.
Since $\theta, \beta$ and $\tau$ solve the homogeneous integrable system
(\ref{tau}), (\ref{theta}) and (\ref{M}), hence $\theta=\beta=\tau=0$.

Given any two pairs  $L_j,{\cal Y}_j$, obtained as above, let ${\cal T}_j$, $1\leq j\leq 2$,
be the associated infinitesimal bendings.
It remains to show that ${\cal T}={\cal T}_1-{\cal T}_2$ is a trivial infinitesimal bending.

We have that the pair $L=L_1-L_2$, ${\cal Y}={\cal Y}_1-{\cal Y}_2$ satisfies $(S_0)$
as well as  (\ref{iif}), (\ref{4}) and (\ref{3}). Fix $p_0\in M^n$ and
define  a skew-symmetric linear endomorphism ${\cal C}$ of $\mathbb{R}^{n+1}$ by
$$
{\cal C}f_*(p_0)X=L(p_0)X\;\;\mbox{and}\;\;{\cal C}N(p_0)={\cal Y}(p_0)
$$
and a vector $v\in\mathbb{R}^{n+1}$ by $v={\cal T}(p_0)-{\cal C}f(p_0)$.
Consider the  trivial infinitesimal bending $\tilde{{\cal T}}={\cal C}f+v$ and
$\tilde{{\cal Y}}={\cal C}N$.  Then, the pair $\tilde{L}$ and $\tilde{{\cal Y}}$ satisfies
$(S_0)$. Thus, also the pair $L^*=L-\tilde{L}$, ${\cal Y}^*={\cal Y}-\tilde{{\cal Y}}$
solves system $(S_0)$. Moreover, ${\cal T}^*(p_0)=0$, ${\cal Y}^*(p_0)=0$ and
$L^*(p_0)=L(p_0)-\tilde{L}(p_0)=0$.
Thus ${\cal T}^*=0$ and hence ${\cal T}=\tilde{{\cal T}}$.\qed

\section{The proof of Theorem \ref{main}}

In the sequel, let $f\colon M^n\to\mathbb{R}^{n+1}$, $n\geq 3$, be a
hypersurface of constant  rank two. Recall that the \emph{splitting tensor}
$C\colon\Gamma(\Delta)\to\Gamma(\mbox{End}(\Delta^\perp))$
is defined by
$$
C_TX=-(\nabla_XT)_{\Delta^\perp}
$$
for any $T\in\Gamma(\Delta)$ and $X\in\mathfrak{X}(M)$.
 From the Codazzi equation, it follows that
\begin{equation} \label{codazzi}
\nabla_TA=AC_T=C_T^tA
\end{equation}
for any $T\in\Gamma(\Delta)$.

\begin{proposition}{\hspace*{-1ex}}{\bf .  }  Assume that the splitting tensor at any point
satisfies $C_T\in\mbox{span}\{I\}$ for any $T\in\Delta$, where $I$ denotes the
identity section of $\mbox{End}(\Delta^\perp)$. Then $f$ is surface-like.
\end{proposition}

\noindent\emph{Proof: } See Lemma $6$ in \cite{dft}.\vspace{1,5ex}\qed

Assume further that $f$ is infinitesimally bendable.
Locally and because of the rank assumption,  there is an orthonormal
tangent frame spanning $\Delta^\perp$ such that
\begin{equation} \label{matrix}
A\vert_{\Delta^\perp}=\begin{bmatrix}
\lambda_1&0\\
0&\lambda_2
\end{bmatrix}.
\end{equation}

\begin{lemma}{\hspace*{-1ex}}{\bf .  } If $B\neq 0$ at any point of $M^n$, then
\begin{equation} \label{matrix2}
B\vert_{\Delta^\perp}=\begin{bmatrix}
\lambda\lambda_1&b\\
b&-\lambda\lambda_2
\end{bmatrix}.
\end{equation}
\end{lemma}

\noindent\emph{Proof: } By Corollary \ref{kerB} we have that $\Delta\subset\ker B$.
Now (\ref{matrix2}) follows easily from (\ref{5}).\qed

\begin{lemma}{\hspace*{-1ex}}{\bf .  }\label{conditions} We have that
$D=(A\vert_{\Delta^\perp})^{-1}B\vert_{\Delta^\perp}\in\Gamma(\mbox{End}(\Delta^\perp))$
satisfies:
\begin{itemize}
\item[(i)] $[D,C_T]=0$ for all $T\in\Delta$,
\item[(ii)] $\nabla_TD=0$ for all $T\in\Delta$,
\item[(iii)] $\mbox{tr\,} D=0$,
\item[(iv)] $T(\det D)=0$ for all $T\in\Delta$.
\end{itemize}
\end{lemma}

\noindent\emph{Proof: } We denote $A=A\vert_{\Delta^\perp}$ and $B=B\vert_{\Delta^\perp}$.
From (\ref{codazzi}) we obtain $\nabla_TB=BC_T.$
Hence
$$
BC_T=C_T^tB.
$$
We have using  (\ref{codazzi}) that
$$
ADC_T=BC_T=C_T^tB=C_T^tAD=AC_TD,
$$
and $(i)$ follows. We have
\begin{eqnarray*}
A\nabla_TD\!\!\!&=&\!\!\!\nabla_T(AD)-(\nabla_TA)D=\nabla_TB-(\nabla_TA)D
=BC_T-AC_TD\\
\!\!\!&=&\!\!\!BC_T-C_T^tAD=BC_T-C_T^tB=0,
\end{eqnarray*}
and this yields $(ii)$. We obtain from (\ref{matrix}) and (\ref{matrix2}) that
$$
D=\begin{bmatrix}
\lambda&b/\lambda_1\\
b/\lambda_2&-\lambda
\end{bmatrix},
$$
which gives $(iii)$. Now part $(iv)$ follows
from  $(ii)$ and $(iii)$.\qed

\begin{proposition}{\hspace*{-1ex}}{\bf .  }\label{ruled} Assume that $f\colon M^n\to\mathbb{R}^{n+1}$, $n\geq 3$,
is not surface-like on any open subset of $M^n$. Then $f$ is ruled
along any open subset where $D\neq 0$ satisfies $\det D=0$.
\end{proposition}

\noindent\emph{Proof: } By Lemma \ref{conditions} there is an orthogonal frame $X,Y$
of $\Delta^\perp$ with $Y$ of unit length such that $DY=0$ and $DX=Y$.
We claim that $f$ is ruled by the integral leaves of
the distribution
$\Delta\oplus\mbox{span}\{Y\}$. To see this, we have to show that
$$
(i)\; \<AY,Y\>=0,\;(ii)\;\nabla_TY=0,\;
(iii)\;\<\nabla_YT,X\>=0\;\;\mbox{and}\;\;(iv)\;\<\nabla_YY,X\>=0
$$
for all $T\in\Delta$. We have
$$
\<AY,Y\>=\<ADX,Y\>=\<BX,Y\>=\<BY,X\>=\<ADY,X\>=0.
$$
Condition $(ii)$ follows easily using $\nabla_TD=0$.
Since  $[D,C_T]=0$, we obtain
$$
\<\nabla_YT,X\>=-\<C_TY,X\>=-\<C_TDX,X\>=-\<DC_TX,X\>=0.
$$
We have that
$$
BY=ADY=0\;\;\mbox{and}\;\;BX=ADX=AY=\lambda X,\;\;\lambda\neq 0,
$$
and condition $(iv)$ follows easily using (\ref{6}).
\vspace{1,5ex}\qed

In the sequel, we consider the case $\det D\neq 0$. By the above, this
is always the case under the assumptions of Theorem \ref{main}.
\vspace{1ex}

By part $(iii)$ of Lemma \ref{conditions} the eigenvalues of $D$ are
the solutions of  $t^2+\det D=0$. Therefore, on each connected component
of an open subset of $ M^n$ either $\det D<0$ and thus $D$ has two
smooth real eigenvalues $\{\mu,-\mu\}$ or $\det D>0$ and thus $D$ has a
pair of smooth complex eigenvalues $\{i\mu,-i\mu\}$. Then
$J\in\Gamma(\mbox{End}(\Delta^\perp))$ defined by
\begin{equation} \label{jota}
D=\mu J
\end{equation}
satisfies $J^2=I$ in the first case and $J^2=-I$ in the second case.

\begin{lemma}{\hspace*{-1ex}}{\bf .  }\label{para}  The eigenspaces of $D$ are parallel and the
eigenvalues constant along the leaves of $\Delta$.
\end{lemma}

\noindent\emph{Proof: } Follows from parts $(ii)$ and $(iv)$ of Lemma \ref{conditions}.
\vspace{1,5ex}\qed

A hypersurface $f\colon M^n\to\mathbb{R}^{n+1}$ of rank two is said to be
\emph{hyperbolic} (respectively, \emph{elliptic}) if there exists
$J\in\Gamma(\mbox{End}(\Delta^\perp))$ satisfying the following conditions:
\begin{itemize}
\item[(i)]  $J^2=I$ and $J\neq I$ (respectively, $J^2=-I$).
\item[(ii)] $\nabla_TJ=0$ for all $T\in\Gamma(\Delta)$.
\item[(iii)] $C_T\in\mbox{span}\{I,J\}$ for all $T\in\Gamma(\Delta)$.
\end{itemize}

\begin{proposition}\label{hypel}
{\hspace*{-1ex}}{\bf .  } Assume that $f\colon M^n\to\mathbb{R}^{n+1}$ is neither surface-like
nor ruled on any open subset $\tilde{M}^n$ of $M^n$. Then, there is an
open and dense subset $\tilde M^n$ of $M^n$ such that the restriction of
$f$ to any connected component of $\tilde{M}^n$ is either hyperbolic or
elliptic.
\end{proposition}

\noindent\emph{Proof: } Let  $J\in\Gamma(\mbox{End}(\Delta^\perp))$ be defined by (\ref{jota}).
The subspace $S$ of all elements in $\mbox{End}(\Delta^\perp)$ that
commute  with $D$, i.e., that commute with $J$, is $S=\mbox{span}\{I,J\}$.
Thus condition $(iii)$ in the above definition follows from part
$(i)$ of Lemma \ref{conditions}.\vspace{1,5ex}\qed

Given a submersion $\pi\colon M\to L$ between differentiable manifolds,
then  $X\in \mathfrak{X}(M)$ is said  to be \emph{projectable} if it is
$\pi$-related to some  $\bar X\in \mathfrak{X}(L)$, that is, if there
exists $\bar X\in \mathfrak{X}(L)$ such that $\pi_*X=\bar X\circ \pi$.
\vspace{1,5ex}

In the sequel, we denote by $\pi\colon M^n\to L^2$ the submersion onto the
(local) quotient space of leaves of $\Delta$, namely, onto $L^2=M^n/\Delta$.
A tensor $D\in\mbox{End}(\Delta^\perp)$  is said to be  \emph{projectable} with
respect to $\pi$ if it is the horizontal lift of some tensor $\bar D$ on $L$.
Clearly, $D$ is projectable with respect to  $\pi$ if and only if for all
$\bar{x}\in L$,  $x,y\in \pi^{-1}(\bar{x})$,
$v\in\Delta^\perp(x)$ and $w\in \Delta^\perp(y)$ with  $\pi_*v=\pi_*w$,
we have  that $\pi_*Dv=\pi_*Dw$.

\begin{lemma}\label{prop*}{\hspace*{-1ex}}{\bf .  }
Let $f\colon M^n\to\mathbb{R}^{n+1}$ be a  hypersurface of rank two parametrized
by a pair $(g,\gamma)$ in terms of the  Gauss parametrization.
If $f$ is  hyperbolic (respectively, elliptic) with respect to
$J\in\Gamma(\mbox{End}(\Delta^\perp))$ and $D=\mu J$ satisfies  $(i)$--$(iv)$
in Lemma~\ref{conditions}, then $J$ and $D$ are the horizontal lifts of
tensors $\bar{J}$ and $\bar D=\bar\mu\bar{J}$ on $L^2$ such that
$\mu=\bar{\mu}\circ\pi$, $\bar{J}^2=\bar I$
(respectively, $\bar{J}^2=-\bar I$), the pair  $(g,\gamma)$ is hyperbolic
(respectively, elliptic)  with respect to  $\bar{J}$ and $\bar D$ satisfies:
\begin{itemize}
\item[(a)] $\mbox{tr\,}\bar{D}=0$,
\item[(b)] $\left(\nabla'_{\bar{X}}\bar{D}\right)\bar{Y}
-\left(\nabla'_{\bar{Y}}\bar{D}\right){\bar{X}}=0$
for all $\bar{X},\bar{Y}\in \mathfrak{X}(L)$
\end{itemize}
where
$\nabla'$ is the  Levi-Civita connection  of the metric induced by $g$.

Conversely, if the pair $(g,\gamma)$ is hyperbolic  (respectively,
elliptic) with respect to a tensor $\bar{J}$ on $L^2$ satisfying
${\bar J}^2=\bar I$ (respectively, ${\bar J}^2=-\bar I$), then the
hypersurface  $f$ is hyperbolic (respectively, elliptic) with  respect
to the horizontal lift $J$ of $\bar J$. In addition, the horizontal lift
$D=\mu J$ of a tensor $\bar{D}=\bar{\mu}\bar{J}$, $\mu=\bar{\mu}\circ\pi$,
satisfying $(a)$ and $(b)$ also fulfills the properties $(i)$--$(iv)$ in
Lemma \ref{conditions}.
\end{lemma}

\noindent\emph{Proof: } We have from parts $(i)$ and $(ii)$ of Lemma \ref{conditions}
and  Corollary $13$ in \cite{dft2} that the tensor $D$ is projectable.
Then part $(iii)$ of Lemma \ref{conditions} gives
$\mbox{tr\,}\bar{D}=\mbox{tr\,} D=0$.

From part $(iv)$ of Lemma \ref{conditions} we have that that $\det D$
is projectable and from Lemma~\ref{para} that also $J$ is projectable.
We have from the Gauss parametrization that
$$
f_*AX=-N_*X=-h_*\pi_*X
$$
where  $h=i\circ g$. Hence,
\begin{equation} \label{first}
f_*ADX=h_*\pi_*DX=-h_*\bar{D}\pi_*X
\end{equation}
for any $X\in\mathfrak{X}(M)$. In particular,
\begin{equation} \label{bra}
f_*AD[X,Y]=-h_*\bar{D}\pi_*[X,Y]=-h_*\bar{D}[\pi_*X,\pi_*Y]
\end{equation}
for any $X,Y\in\mathfrak{X}(M)$. Moreover,
\begin{eqnarray}\label{net}
f_*\nabla_XADY\!\!\!&=&\!\!\!\tilde\nabla_Xf_*ADY-\<AX,ADY\>N\nonumber\\
\!\!\!&=&\!\!\!-\tilde\nabla_{\pi_*X}h_*\bar{D}\pi_*Y
-\<h_*\pi_*X,h_*\bar{D}\pi_*Y\>h\circ\pi\nonumber\\
\!\!\!&=&\!\!\!-h_*\nabla'_{\pi_*X}\bar{D}\pi_*Y-\alpha_h(\pi_*X,\bar{D}\pi_*Y)
-\<\pi_*X,\bar{D}\pi_*Y\>h\circ\pi\nonumber\\
\!\!\!&=&\!\!\!-h_*\nabla'_{\pi_*X}\bar{D}\pi_*Y-\alpha_g(\pi_*X,\bar{D}\pi_*Y).
\end{eqnarray}
 From (\ref{6}) and the above, we have that
$$
0=f_*(\nabla_XB)Y-f_*(\nabla_YB)X=f_*\nabla_XADY-f_*\nabla_YADX-f_*AD[X,Y].
$$
We conclude that part $(b)$ holds as well as
$$
\alpha_g(\pi_*X,\bar{D}\pi_*Y)=\alpha_g(\bar{D}\pi_*X,\pi_*Y).
$$
Since $\bar D\in\mbox{span}\{I,\bar J\}$ but $\bar D\not\in\mbox{span}\{I\}$, the preceding
equation is equivalent to
\begin{equation} \label{equiv}
\alpha_g(\pi_*X,\bar{J}\pi_*Y)=\alpha_g(\bar{J}\pi_*X,\pi_*Y)
\end{equation}
and thus $g$ is hyperbolic (respectively, elliptic) with respect to  $\bar J$.

To deal with the function $\gamma$ we first show that condition (\ref{eq:aJ})
is equivalent to
$$
(\mbox{Hess\,} h^v+h^v I)J=J^t(\mbox{Hess\,} h^v+h^v I)
$$
where $\mbox{Hess\,} h^v$ is the endomorphism  of $TL$ associated to the Hessian
and $h^v=\<h,v\>$ for any $v\in\mathbb{R}^{n+1}$.
We have that the Hessian of $h^v$ satisfies
$$
\mbox{Hess\,} h^v(X,Y)=\<\alpha_h(X,Y),v\>=\<i_*\alpha_g(X,Y)-\<X,Y\>h,v\>
$$
for all $X,Y\in\mathfrak{X}(L)$. Thus
$$
\<i_*\alpha_g(JX,Y)-i_*\alpha_g(X,JY),v\>
=\<((\mbox{Hess\,} {h^v}+h^v I)J-J^t(\mbox{Hess\,} {h^v}+h^v I))X,Y\>
$$
for all $X,Y\in\mathfrak{X}(L)$.

It remains to prove that
\begin{equation} \label{prenda}
\left(\mbox{Hess\,}\gamma+\gamma I\right)\bar{J}
=\bar{J}^t\left(\mbox{Hess\,}\gamma+\gamma I\right).
\end{equation}
By the Gauss parametrization, there exists a diffeomorphism
$\theta\colon U\subset\Lambda\to M^n$ from an open neighborhood of the
zero section of $\Lambda$ such that $\pi\circ\theta=\bar\pi$ and
$$
f\circ\theta(x,w)=\gamma(x)h(x)+h_*\nabla\gamma(x)+w
$$
for any $(x,w)\in\Lambda$.
Let $j\colon T_xL\to T_{(x,w)}\Lambda$ be the linear isometry in
Proposition \ref{gp}. Then,  for any $\bar{X},\bar{Y}\in T_xL$ we obtain
using (\ref{eq}) and (\ref{first})   that
\begin{eqnarray}\label{addpw}
-\< AD\theta_* j\bar{X},\theta_*j\bar{Y}\>\!\!\!&=&\!\!\!
-\< f_ *AD\theta_* j\bar{X},f_* \theta_*j\bar{Y}\>\nonumber\\
\!\!\!&=&\!\!\!\<h_*\bar{D}\pi_* \theta_* j\bar{X},h_*\bar{Y}\>\nonumber\\
\!\!\!&=&\!\!\!\<\bar{D}\bar\pi_*j\bar{X},\bar{Y}\>'\nonumber\\
\!\!\!&=&\!\!\!\<\bar{D}P_w^{-1}\bar{X},\bar{Y}\>'.
\end{eqnarray}
It follows that $\bar{D}P_w^{-1}=P_w^{-1}\bar{D}^t$, or equivalently, that
$P_w\bar{D}=\bar{D}^tP_w$. And because $\bar D\in\mbox{span}\{I,\bar J\}$, this
is equivalent to $P_w\bar{J}=\bar{J}^tP_w$.
Moreover, using that $A_w\bar{J}=\bar{J}^{t}A_w$ as follows from
(\ref{equiv}), we conclude that  (\ref{prenda}) is satisfied.\qed

\begin{lemma}\label{propr}{\hspace*{-1ex}}{\bf .  }
The following assertions on a surface  $g\colon L^2\to\mathbb{S}^n$ are equivalent:
\begin{itemize}
\item[(i)] The surface $g$ is hyperbolic (respectively, elliptic) with respect
to a tensor $\bar{J}$ on $L^2$ satisfying ${\bar J}^2=I$ (respectively,
${\bar J}^2=-I$), and there is $\bar{D}=\bar{\mu}\bar{J}$,
$\bar\mu>0$, such that
\begin{itemize}
\item[(a)] $\mbox{tr\,}\bar{D}=0$,
\item[(b)] $\left(\nabla'_{\bar{X}}\bar{D}\right)\bar{Y}
-\left(\nabla'_{\bar{Y}}\bar{D}\right){\bar{X}}=0$
for all $\bar{X},\bar{Y}\in \mathfrak{X}(L).$
\end{itemize}
\item[(ii)] There exist real-conjugate (respectively, complex-conjugate)
coordinates on $L^2$ such that system  (\ref{eq:siti})
(respectively, (\ref{eq:comp})) has solution.
\end{itemize}
\end{lemma}

\noindent\emph{Proof: }  We make use of Proposition \ref{coordinates}. In the case of
real coordinates $(u,v)$ and since we have $\bar{D}\partial u=\bar\mu\partial u$,
$\bar{D}\partial v=-\bar\mu\partial v$, we easily see that
$$
\left(\nabla'_{\partial u}\bar{D}\right)\partial v
-\left(\nabla'_{\partial v}\bar{D}\right)\partial u=0
$$
is equivalent to the system (\ref{eq:siti}). The case of complex coordinates
is similar.\vspace{1,5ex}\qed

\noindent\emph{Proof of Theorem \ref{main}:} By Proposition \ref{hypel},
on each connected component of an  open and dense subset of $M^n$ the hypersurface $f$
is either hyperbolic or elliptic with respect to  $J\in\Gamma(\mbox{End}(\Delta^\perp))$.
It follows from Lemma \ref{conditions} that there exists $D\in\Gamma(\mbox{End}(\Delta^\perp))$
satisfying the properties  $(i)$--$(iv)$.

Let $f$ be parameterized by a pair $(g,\gamma)$ in terms of the Gauss
parametrization.
By Lemma \ref{prop*} if $f$ is  hyperbolic (respectively, elliptic)
with respect to $J$, then $J$ and $D$ can be projected to  tensors $\bar{J}$ and
$\bar D\in\mbox{span}\{I,\bar{J}\}$ on $L^2$, with   $\bar{J}^2=I$ (respectively,
$\bar{J}^2=-I$).
Moreover,  the pair $(g,\gamma)$ is  hyperbolic (respectively, elliptic)
with respect to  $\bar{J}$ and $\bar D$ satisfies $(a)$ and $(b)$ in
Lemma~\ref{prop*}. Now the proof of the direct statement follows from
Lemma \ref{propr}.

Conversely, let $f\colon M^n\to\mathbb{R}^{n+1}$ be a simply-connected
hypersurface parameterized  in terms of the Gauss parametrization
by a special hyperbolic or special elliptic pair $(g,\gamma)$.
By Lemma~\ref{propr},  there exists $\bar{D}=\bar{\mu}\bar{J}$ satisfying
equations $(a)$ and $(b)$.
By Lemma~\ref{prop*} the hypersurface  $f$ is hyperbolic or elliptic
with respect to the horizontal lift $J$ of $\bar J$, and the horizontal
lift $D=\mu J$ of  $\bar{D}=\bar{\mu}\bar{J}$ satisfies $(i)$--$(iv)$ in
Lemma \ref{conditions}.

To conclude from Theorem \ref{mains} that $f$ admits a unique nontrivial
infinitesimal bending it remains to show that $B\in\Gamma(\mbox{End}(TM))$
defined by $B\vert_{\Delta^\perp}=A\vert_{\Delta^\perp}D$ and $\Delta\subset\ker B$
is symmetric and satisfies equations (\ref{6}) and (\ref{5}). In fact,
that $B$ is symmetric follows easily from (\ref{addpw}).

Part $(b)$ of Lemma \ref{prop*} together with (\ref{bra}) and (\ref{net})
imply that
$$
f_*((\nabla_XB)Y-(\nabla_YB)X)=f_*\nabla_XADY-f_*\nabla_YADX-f_*AD[X,Y]=0
$$
for any $X,Y\in\Gamma(\Delta^\perp)$.
Since  $D$ is projectable, we can use Corollary $13$ in \cite{dft2} and
deduce that
$$
\nabla_TD=[D,C_T]
$$
for any $T\in\Delta$. Using (\ref{codazzi}) we obtain
$$
(\nabla_TB)X=(\nabla_TAD)X=(\nabla_TA)DX+A[D,C_T]X=ADC_TX
$$
for any $T\in\Delta$ and $X\in\Delta^\perp$. It follows that
$$
(\nabla_XB)T-(\nabla_TB)X=0
$$
for any $T\in\Delta$ and $X\in\Delta^\perp$. Since
$$
(\nabla_SB)T-(\nabla_TB)S=B[S,T]=0
$$
for any $S,T\in\Delta$, we have shown that (\ref{bra}) holds.
Since (\ref{net}) is equivalent to $\mbox{tr\,} D=0$, the proof follows.\qed

\section{The ruled case}

In this section, we discuss the infinitesimal bendings of ruled
hypersurfaces that have not been considered yet.
\vspace{1ex}

Let $f\colon M^n\to\mathbb{R}^{n+1}$, $n\geq 3$, be a ruled hypersurface without
flat points which is not surface-like on any open subset of $M^n$. Then $f$
has rank two and there exists locally an orthonormal frame $X,Y$ of
$\Delta^\perp$ such that the second fundamental form is the form
$$
A\vert_{\Delta^\perp}=\begin{bmatrix}
\lambda&\mu\\
\mu&0
\end{bmatrix}.
$$
Note that if $M^n$ is simply-connected then the set of all isometric
immersions of $M^n$ into $\mathbb{R}^{n+1}$ consists of ruled immersions with
the same rulings; see \cite{dft}. Moreover, this set
can be parametrized by the set of all smooth functions in an interval.
In fact, the second fundamental form of any other immersion must
be of the form
$$
A\vert_{\Delta^\perp}=\begin{bmatrix}
\lambda + \theta&\mu\\
\mu&0
\end{bmatrix}
$$
where $\theta\in C^\infty(M)$ is determined by choosing a smooth function
along an integral curve of $X$ and extending it to $M^n$ by requiring that
\begin{equation} \label{codazzi2}
Y(\theta)=\<\nabla_XX,Y\>\theta\;\;\mbox{and}\;\;T(\theta)
=\<\nabla_XX,T\>\theta
\end{equation}
for any $T\in\Delta$.

\begin{proposition}{\hspace*{-1ex}}{\bf .  }
 Let $f\colon M^n\to\mathbb{R}^{n+1}$, $n\geq 3$, be a simply-connected ruled
hypersurface of constant rank two that is not surface-like on any open
subset of $M^n$.  Then, any infinitesimal bending is the variational
vector field of an isometric bending.
\end{proposition}

\noindent\emph{Proof: } Since $M^n$ is simply-connected, there is a global orthonormal
frame $\{X,Y\}$ of $\Delta^\perp$ as above. By Lemma \ref{conditions} and
Proposition \ref{ruled}, the Codazzi tensor $B$ on $M^n$ is given by
$B|_{\Delta^\perp}=A|_{\Delta^\perp}D$ and $\Delta\subset\ker B$, where
$D=\theta J$ and  $J\in\Gamma(End(\Delta^\perp))$ is such that  $JX=Y$ and
$JY=0$. Moreover, $\theta\in C^{\infty}(M)$ is arbitrarily prescribed along
an integral curve of $X$ and  required to satisfy (\ref{codazzi2}).
Therefore, the one-parameter family of Codazzi tensors $A(t)=A+tB$, $t\in\mathbb{R}$,
gives rise to an isometric bending of $f$ having the infinitesimal bending
determined by $B$ as its variational vector field.