binary.tex

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{unicode}
\usepackage{math}
\usepackage[margin=25mm]{geometry}
\usepackage{color}
\usepackage[all]{xypic}
\DeclareUnicodeCharacter{26A0}{{\color{red}\ensuremath{\lower .25ex\hbox{\Large
$\triangle$\hskip -1.25ex}!\;\,}}}


\def\transpose#1{{\vphantom{#1}}^{\mathrm{t}}\!#1}
\def\mat#1{\begin{pmatrix}#1\end{pmatrix}}
\def\F{\mathbb{F}}
\def\appli#1#2#3#4{\begin{array}{rcl}#1&\longrightarrow&#2\\
  #3&\longmapsto&#4\end{array}}
\def\operp{\mathrel{\vbox{\offinterlineskip\ialign{\hfil##\hfil\cr
  $\scriptstyle\perp$\cr\noalign{\kern .3ex}$\scriptstyle\bigoplus$\cr}}}}
\DeclareMathOperator\GL{GL}
\DeclareMathOperator\Quad{Quad}
\DeclareMathOperator\Bil{Bil}
% \DeclareMathOperator\Sym{Sym}
\DeclareMathOperator\Alt{Alt}
\def\kR{_{(k,R)}}


% \def\chk#1{#1^{\scriptscriptstyle\vee}}
\usepackage{graphicx}
\def\chk#1{#1^{\smash{\scalebox{.7}[1.4]{\rotatebox{90}{\guilsinglleft}}}}}
\let\fr\mathfrak

\long\def\note#1{{\color{magenta}{\textbf{Note:} #1}}}

\begin{document}
\title{Solving IP1S in characteristic two: the fully irregular case}

A pencil is \emph{fully irregular} if its regular part is zero,
\emph{i.e.} if it is isomorphic to a direct sum of Kronecker modules.

\section{The equations for IP1S}

Let~$k$ be a finite field with characteristic~$2$. Except where
indicated, all tensor products shall be taken over~$k$.

\subsection{Kronecker modules as homogeneous polynomials}


For~$d ≥ 0$, we write~$H_d$ for the $d+1$-dimensional space of
homogeneous polynomials in~$k[x:y]$ of degree~$d$. For any~$h ∈ H_m$, the
multiplication by~$m$ defines linear maps~$H_d → H_{d+1}$, which we again
write~$h$; all these maps
commute with each other. We write~$\chk{H_d}$ for the dual vector space
of~$H_d$, and~$\chk{h}: \chk{H_{d+1}} → \chk{H_{d}}$ for the transposed
maps of~$h$. We also write~$\chev{φ, f}$ for the canonical bilinear
map~$H_d ⊗ \chk{H_d} → k$; we note that, for~$f ∈ H_{d-m}$ and~$φ ∈
\chk{H_d}$, we always have the relation~$\chev{φ, fh} = \chev{\chk{h} φ, f}$.

The \emph{Kronecker module} of degree~$d ≥ 0$ over~$k$ is the
$2d+1$-dimensional space~$K_d = H_{d-1} ⊕ \chk{H_d}$, equipped with the
symmetric bilinear pencil~$(b_{t})$ defined for~$f, f' ∈ H_{d-1}$ and~$φ,
φ' ∈ \chk{H_{d}}$ by
\begin{equation}
b_t (f, f') \;=\; b_t (φ, φ') \;=\; 0; \qquad
b_t (f, φ) \;=\; \chev {φ, (ty-x) f}.
\end{equation}
This means that $b_{0} (f, φ) = \chev {φ, xf} = \chev {\chk{x} φ,  f}$,
and $b_{∞} (f, φ) = \chev{φ, yf} = \chev{\chk{y} φ, f}$. Since $f ∈
H_{d-1}$ and~$φ ∈ \chk{H_{d}}$, we have~$xf ∈ H_{d}$ and~$\chk{x} φ ∈
\chk{H_{d-1}}$, so these pairings are well-defined.

% For~$d ≥ -1$, we write~$P_d$ for the
% $d+1$-dimensional space of polynomials in~$k[x]$ of degree~$≤ d$,
% and~$P_d^∨$ for its dual. Let~$ι_d: P_{d-1} → P_{d}$ be the natural
% injection map and~$x_d: P_{d-1} → P_{d}$ be the multiplication by~$x$.
% The various maps~$ι_d$ and~$x_d$, when composable, commute with each
% other, and we shall simply write them as~$ι$ and~$x$. They define
% transposed maps~$\chk{ι}$ and~$\chk{x}: P_{

% The \emph{Kronecker module} of degree~$d$
% over~$k$ is then the space~$K_d = P_{d-1} ⊕ \chk{P_d}$, equipped with the
% symmetric bilinear pencil~$(b_{t})$ defined for~$f, f' ∈ P_{d-1}$ and~$φ, φ' ∈
% \chk{P_{d}}$ by
% \begin{equation}
% b_t (f, f') \;=\; b_t (φ, φ') \;=\; 0, \qquad
% b_t (f, φ') \;=\; \chev{φ, (x - t) ι_d f}.
% \end{equation}

\subsection{Kronecker modules with coefficients}

A \emph{coefficient space} is a bilinear space~$E$ isomorphic to~$k^n$,
together with its standard scalar product~$u, v ↦ u · v$. For any linear
maps~$α: V → E$, $β: W → E$, we write~$α · β$ for the corresponding
bilinear form on~$V × W$.

\note{En première lecture, on pourra ignorer ces espaces de coefficients,
c'est-à-dire supposer que tous les coefficients~$α$, $β$ sont scalaires.}

The bilinear module~$K_d^{n}$ is isomorphic to~$E ⊗ K_d$. For~$u ∈ E ⊗
H_m$ written as~$u = ∑ u_i ⊗ x^i$ with~$u_i ∈ k^n$ and~$x^i ∈ H_m$, we
define, for~$f ∈ H_d$ and~$φ ∈ \chk{H_d}$,
\begin{equation}
u f \;=\; ∑ u_i ⊗ (x^i f) \;∈ E ⊗ H_{d+m}, \quad
\chk{u} φ \;=\; ∑ u_i ⊗ (\chk{(x^i)} φ) \;∈ E ⊗ \chk{H_{d-m}}.
\end{equation}
Likewise, for any~$h ∈ \Hom(E, E') ⊗ H_m$, write~$h = ∑ h_i ⊗ x^i$
with~$h_i ∈ \Hom (E, E')$. For any~$u ⊗ f ∈ E ⊗ H_d$, we define~$h(u ⊗
f) ∈ E' ⊗ H_{d+m}$ by~$h(u ⊗ f) = ∑ h_i(u) ⊗ (x^i f)$. An element
of~$\Hom (E ⊗ H_d, E' ⊗ H_{d+m})$ defined in this way is called
\emph{principal}. In the same way, we define principal elements of~$\Hom
(E ⊗ \chk{H_{d+m}}, E' ⊗ \chk{H_{d}})$.

Let~$r ≤ s$ be two integers and~$E, E'$ be two coefficient spaces. We say
that a bilinear form~$B$ on~$(E ⊗ H_r) × (E' ⊗ \chk{H_s})$ is
\emph{principal} if it is of the form~$B(f, φ) = \chev {φ, hf} = \chev
{\chk{h} φ, f}$ for some~$h ∈ \Hom (E, E') ⊗ H_{s-r}$.

\begin{lem}\label{lem:principal}
Let~$r ≤ s$ be two integers and~$E, E'$ be two coefficient spaces.
\begin{enumerate}
\item A bilinear form~$B$ on~$(E ⊗ H_r) × (E' ⊗ \chk{H_s})$ is principal
if, and only if, for any polynomial~$z$, $B(zf, φ) = B(f, \chk{z} φ)$.
\item Let~$α: E ⊗ H_r → E' ⊗ H_s$ and~$β: E' ⊗ \chk{H_s} → E ⊗ \chk{H_r}$ be
two linear maps. If $1 · α + β · 1$~is principal, then both~$α$ and~$β$
are principal.
\end{enumerate}
\end{lem}

\subsection{The automorphisms of a direct sum of Kronecker modules}

Any totally irregular pencil of quadrics is isomorphic to a space of the
form~$⨁ E_d ⊗ K_d$, where~$E_d = k^{n_d}$, and $(n_d)$~is some finite
sequence of integers.

\begin{prop}\label{prop:aut-Ed-Kd}
The automorphisms of~$⨁ E_d ⊗ K_d$ are exactly the maps of the form
\[ u ⊗ f ↦ ∑_{d' ≥ d} α_{d',d} (u) f + ∑_{d'} \chk{f} γ_{d',d} (u), \quad
u ⊗ φ ↦  ∑_{d' ≤ d} \chk{β_{d',d} (u)} φ, \]
where~$α_{d',d} ∈ \Hom (E_d, E_{d'}) ⊗ H_{d'-d}$, $β_{d',d} ∈ \Hom (E_d,
E_{d'} ⊗ H_{d-d'})$ and~$γ_{d',d} ∈ \Hom (E_{d}, E_{d'}) ⊗
\chk{H_{d+d'-1}}$ satisfy the following relations: let~$A, B, C$ be the
matrices~$(α_{d',d})$, $(β_{d',d})$, and~$(γ_{d',d})$; then
$\transpose{B} · A = 1$, and $\transpose{C} · A$~is antisymmetric.
\end{prop}


% \begin{prop}\label{prop:aut-Ed-Kd}
% The group of automorphisms of~$⨁ E_d ⊗ K_d$ is generated by the following
% elements:
% \begin{enumerate}
% \item elements of the form~
% \begin{equation}
% u ⊗ f ↦ ∑_{d' ≥ d} α_{d, d'} (u) f, \quad
% u ⊗ φ ↦ ∑_{d' ≤ d} \chk{β_{d, d'} (u)} φ,
% \end{equation}
% where~$α_{d, d'}: E_{d} → E_{d'} ⊗ H_{d'-d}$ and~$β_{d,d'}: E_{d} → E_{d'} ⊗ H_{d-d'}$ are linear maps satisfying
% the relations, for~$d ≤ d'$
% \begin{equation}
% ∑_{i=d}^{d'} α_{d,i} · β_{d',i} =
% \begin{cases} 1 & \text{if $d = d'$,}\\0 & \text{else.}\end{cases}
% \end{equation}

% \item elements of the form~$u ⊗ φ ↦ u ⊗ φ$, $u ⊗ f ↦ ∑_{d'} γ_{d,d'} (u)
% f$, where~$γ_{d,d'}: E_d → E_{d'} ⊗ \chk{\P_{d+d'}}$ is a linear map, such
% that~$γ_{d,d'} = \transpose{γ_{d', d}}$.
% \item elements of the form
% \begin{equation}
% u ⊗ φ ↦ u ⊗ φ, u ⊗ f ↦ u ⊗ f + ∑_{d'} \chk{f} γ_{d,d'} (u),
% \end{equation}
% where~$γ_{d,d'}: E_{d} → E_{d'} ⊗ \chk{H_{d+d'-1}}$ is such
% that~$\transpose{γ_{d,d'}} = γ_{d',d}$.
% \end{enumerate}
% \end{prop}

In the above theorem, we understand the elements~$u ⊗ f$ and~$u ⊗ φ$ to
belong to the spaces~$E_d ⊗ H_{d-1}$ and~$E_d ⊗ \chk{H_d}$. For~$d > d'$,
the space~$H_{d' - d}$ is zero, and therefore~$α_{d,d'} = β_{d',d} = 0$.

The relation~$\transpose{A} · B = 1$ means that, for all~$d, d'$, $∑_i
\transpose{α_{i,d}} · β_{i,d'} ∈ \chk{E_d} ⊗ \chk{E_{d'}} ⊗ H_{d'-d}$ is the standard
scalar product of~$E_d$ if $d = d'$ and~$0$ else; this product is to be
interpreted as the collection of the corresponding terms of all degrees
in~$(x:y)$, and the scalar product is taken in~$E_i$. Therefore, the
elements~$α_{i,j}$ uniquely determine all of the~$β_{i,j}$. Likewise, the
relation~$\transpose{A} · C + \transpose{C} · A = 0$ means that $∑_i
\transpose{α_{i,d}} · γ_{i,d'} + \transpose{γ_{i,d}} · α_{i,d'} = 0 ∈ E_d
⊗ E_{d'} ⊗ H_{d+d'-1}$, where scalar products are taken in~$E_i$.


\begin{proof}[(Sketch of) Proof of Prop.~\ref{prop:aut-Ed-Kd}]
Let~$F$ be an automorphism of~$V = ⨁ E_d ⊗ K_d$. The space~$V$ is
filtered by the degrees of its kernel vectors: for all~$d$, the
sub-space~$⨁ E_{d'} ⊗ \chk{H_{d'}}$ for~$d' ≤ d$ is exactly the linear span
of all kernel vectors of degree~$≤ d$. Therefore, $F$~is upper triangular
on these spaces, so that we may write, for~$u ∈ E_d$, $φ ∈ \chk{H_{d}}$
and~$f ∈ H_{d-1}$:
\begin{equation}
F(u ⊗ f) = ∑_{d'} α_{d',d} (u ⊗ f) + ∑_{d'} γ_{d',d} (u ⊗ f), \quad
F(u ⊗ φ) = ∑_{d' ≤ d} β_{d',d} (u ⊗ φ),
\end{equation}
where~$α_{d',d}: E_d ⊗ H_{d-1} → E_{d'} ⊗ H_{d'-1}$, $γ_{d',d}: E_d ⊗
H_{d-1} → E_{d'} ⊗ \chk{H_{d'}}$ and~$β_{d',d}: E_d ⊗ \chk{H_{d}} → E_d ⊗
\chk{H_{d'}}$. Moreover, for all~$d$, since $β_{d,d}(u ⊗ φ)$~preserves the
kernel of~$b$, it is principal, i.e. of the form~$β_{d,d,0} (u) ⊗ φ$
where $β_{d,d,0}: E_d → E_d$~is a linear map.

The relation~$b(F (u ⊗ f), F(v ⊗ φ)) = b(u ⊗ f, v ⊗ φ)$ implies that the
matrix~$A$ of all endomorphisms~$α$ is the inverse transpose of the
matrix~$B$ of the endomorphisms~$β$; since $B$~is upper triangular,
$A$~is lower triangular. We may then use Lemma~\ref{lem:principal} to
prove that all the~$α_{d',d}$ and~$β_{d',d}$ are principal, by induction
on~$d-d'$.
% Write~$β · α$ for the bilinear product of~$β(v ⊗ φ)$ and~$α(u ⊗ f)$, so
% that we have for all~$r, s$ the relation $∑_{i ≤ s} β_{s,i} · α_{r,i}
% = 1$ if $r = s$ and $0$~else.
% We now prove by induction on~$d$ the following statement: $β_{s,s} ·
% α_{s,s} = 1$ and, for all~$r > s$, we have~$α_{r,s} = 0$. For~$s = 0$,
% the previous relation becomes~$β_{0,0} α_{r,0} = 1$ if~$r = 0$ and
% $0$~else. The case~$r = 0$ proves that~$β_{0,0}$~is invertible and
% therefore that all~$α_{r,0}$ for~$r ≥ 1$ are zero. The induction step
% works in the same way: the relation for~$s$ is now~$∑

Finally, the relation on the coefficients~$γ_{d',d}$ comes directly from
the relation $b(F (u ⊗f), F(u' ⊗ f')) = 0$.
\end{proof}

\subsection{Action on the diagonal coefficients}

Let~$(V, b) = ⨁ E_d ⊗ K_d$ be a totally irregular bilinear pencil and
let~$q$ be a quadratic pencil on~$V$ whose polar form is~$b$. Since $b$~is
isotropic on~$⨁ E_d ⊗ H_{d-1}$ and on~$⨁ E_d ⊗ \chk{H_d}$, for any
element~$z = ∑ u_i ⊗ f_i + ∑ v_j ⊗ φ_j ∈ V$, we have
\begin{equation}
q(z) = ∑_i q(u_i ⊗ f_i) + ∑_j q(v_j ⊗ φ_j) +
  ∑_{i,j} b(u_i ⊗ f_i, v_j ⊗ φ_j).
\end{equation}
Let~$σ$ be the absolute Frobenius defined by~$σ(x)=x^2$. We note that the
restriction of~$q$ to one of the spaces~$E_d ⊗ H_{d-1}$ or~$E_d ⊗
\chk{H_{d}}$ is a $σ$-linear form. The quadratic form~$q$ is determined by the
restrictions of~$σ^{-1} ∘ q$ to these spaces, which are linear forms.
For~$u ∈ E_d$, $f ∈ H_{d-1}$ and~$φ ∈ \chk{H_d}$, we write $λ_d(u ⊗ f) =
σ^{-1} ∘ q\: (u ⊗ f)$ and~$μ_d (u ⊗ φ) = σ^{-1} ∘ q\: (u ⊗ φ)$.
% which we write~$λ_d ∈ E_d ⊗
% \chk{H_{d-1}}$ and~$μ_d ∈ E_d ⊗ H_d$ (using the scalar product to
% identify~$E_d$ with its dual).

Let~$F$ be an automorphism of~$b$, and define its coefficients
$α_{d,d'}$, $β_{d,d'}$ and~$γ_{d,d'}$ as in Prop.\ref{prop:aut-Ed-Kd}
above.

The action of~$F$ on the quadratic pencil~$q$ is given as follows:
\begin{align*}
q ∘ F\;(u ⊗ f) &= ∑_i q(α_{i,d} (u) f) + 
  ∑_i q(\chk{f} γ_{i,d} (u)) + ∑_i b(γ_{i,d} (u), α_{i,d} (u) f^2);\\
q ∘ F\;(u ⊗ φ) &= ∑_i q(β_{i,d} (u) φ).
\end{align*}
Define as above~$λ_d$, $μ_d$ as the diagonal parts of~$q$. Also
let~$γ'_{d,d'} = ∑_i \transpose{α_{i,d}} γ_{i,d'} ∈ \Hom (E_d, E_{d'}) ⊗
\chk{H_{d+d'-1}}$, so that the anti-symmetry condition on the
coefficients~$γ$ becomes $\transpose{γ'_{d,d'}} = γ_{d',d}$.
Write~$γ'_{d,d',j} = ∑_{i,r} \transpose{α_{i,d,r}} · γ_{i,d',r+j}$ for
the coefficients of~$γ'$, as a linear map on~$H_{d+d'-1}$.

The diagonal coefficients~$λ'_d$, $μ'_d$ of~$q' = q ∘ F$ are given by
\begin{align*}
λ'_d &= ∑_i λ_i ∘ α_{i,d} + ∑_i μ_i ∘ γ_{i,d}
  + ∑_{i,j} σ^{-1} (γ'_{d,d,2j+1} - t γ'_{d,d,2j}) ξ_{j,d-j},\\
μ'_d &= ∑_i μ_i ∘ β_{i,d}.
\end{align*}


\begin{prop}\label{prop:ip1s-semilinear}
The $n$-dimensional IP1S problem for totally irregular pencils over a
field of characteristic two is equivalent to linears equation of
dimension~$O(n^2)$ and one semi-linear equation of
the form
\begin{equation*}
X = A σ(X) + B,
\end{equation*}
where $A$~is a square matrix and $X, B$~are column matrices of
dimension~$O(n^2)$.
\end{prop}

\section{Solving Frobenius equations}

% Part~1 shows how to bring the IP1S problem to an equation of the form
% \begin{equation}\label{eq:semi-linear}
% X = A σ(X) + B,
% \end{equation}
As the matrix~$A$ of Proposition~\ref{prop:ip1s-semilinear} seems to be
quite general, we give a generic method for this family of
\emph{Frobenius equations}. In the IP1S problem, the base field~$k$ has
characteristic~two; we present here the general case for any base field.

Let~$k[φ]$ be the non-commutative ring of polynomials in~$φ$, with the
relations~$φ c = σ(c) φ$ for all~$c ∈ k$. This ring is Euclidean.
More precisely, the (left-side) Euclidean algorithm works: given two
elements~$a, b ∈ k[φ]$, there exist elements~$u, v$ such that~$u a + v b =
d$ where $d$~is the gcd of~$a$ and~$b$.

Moreover, the only two-sided ideals of~$k[φ]$ are those generated by the
powers of~$φ$.

From these two remarks and [Jacobson, Th.~19] we get the following.
\begin{thm}
Let~$φ: k^n → k^n$ be a semi-linear endomorphism. There exists a basis
of~$k^n$ in which the matrix of~$φ$ is the direct sum of cyclic matrices,
at most one of which is not nilpotent.
\end{thm}

Assume now that $A$~is cyclic and let~$R = k[a]/f(a)$ be the $k$-algebra
generated by~$a$; the equation~\eqref{eq:semi-linear} may then be written
as
\begin{equation}\label{eq:semi-linear-pol}
x = a σ(x) + b,
\end{equation}
where~$a$, $b$ and~$x$ belong to the finite algebra~$k[a]$, and $σ$~is
the absolute Frobenius automorphism. To the primary factorization~$f = ∏
f_i$ of~$f$, there corresponds a factorization~$R = ∏ R_i$ where $R_i$~is
a local algebra. Using Chinese remainders, we may therefore assume that
$R$~is a local algebra and~$f = f_0^d$, where $f_0$~is irreducible.

We first see to the case where~$d = 1$, \emph{i.e.} $R$~is an extension
of the field~$k$. Write~$k_0 = \F_p$ be the field fixed by the
Frobenius~$σ$ and let~$N_0 = N_{R/k_0}$ and~$\Tr_0 = \Tr_{R/k_0}$ be the
norm and trace operators. The equation~\eqref{eq:semi-linear-pol} implies
that
\begin{equation}
x = b' + N_0(a) x, \quad\text{where $b' = b + a σ(b) + … + a σ(a) …
σ^{n-2}(a) σ^{n-1}(b)$.}
\end{equation}
If $N_0(a) ≠ 1$, then this gives as a unique solution~$x =
b'/(1-N_0(a))$. If, on the contrary, $N_0(a) = 1$, then by
Hilbert's theorem~90~[Lang, VI.6.1], there exists~$u ∈ R^{×}$ such
that~$a = σ(u)/u$; then~$x' = ux$ satisfies the equation~$x' = σ(x') +
ub$. This last equation, using the additive form of Hilbert's theorem~90
[Lang, VI.6.3], has a solution if, and only if, $\Tr_0 (ub) = 0$. We
note that both forms of Hilbert's theorem are algorithmic.

In the general case where~$d ≥ 1$, let~$\fr m$ be the maximal ideal
of~$R$. We may use the preceding paragraph to compute a solution~$x_0$ of
the equation modulo~$\fr m$. Moreover, we notice that~$f(x) = x -  a σ(x)
- b$ is a polynomial and that~$f'(x) = 1$; therefore, this polynomial is
separated, and we may use Hensel's lemma to lift the approximate
solution~$x_0$ to a full solution.

\section{An intrinsic version of regular pencils}

This is an attempt to give a more intrinsic presentation of §2
of the IP2S document
\texttt{isomorphism\_polynomials}.

\subsection{Bilinear pencils}

Let~$b_{λ} = b_{∞} (λ - c)$ be a regular (principal) bilinear pencil
on~$V$. Using primary factorization, we assume that the characteristic
polynomial~$f$ of~$c$ is primary, \emph{i.e.} of the form~$f = p^d$
with~$p$ irreducible. We define the local algebras~$R_n = k[c]/p(c)^n$
and the extension field~$K = R_1 = k[c]/p(c)$. For each~$n$, $R_n$~is
isomorphic to~$K[π]/π^n$.

\note{pour prouver l'isomorphisme, il suffit de construire un
morphisme~$K → R_n$, càd de résoudre l'équation~$p(x) = 0$ dans~$R_n$.
Puisque $c$~est une solution approchée, et $p$~étant séparable, le lemme
de Hensel prouve qu'il existe une solution exacte.}


The form~$b_{∞}$ is $k$-bilinear on~$V$, and commutes with~$R_n$ in the
following sense: for all~$a ∈ R_n$, we have~$b_{∞} (x, ay) = b_{∞} (ax,
y)$. In particular, it commutes with~$K$. Moreover, morphisms in the IP1S
sense correspond to $R$-linear maps. We therefore define the category of
$(k, R)$-bilinear modules to be the category whose objects are
$R$-modules of finite type equipped with bilinear forms commuting
with~$R$, and whose maps are $R$-linear maps.

% We write~$\Bil_R (M)$, $\Sym_R (M)$ and $\Quad_R (M)$ for the $R$-modules
% of bilinear, symmetric and quadratic forms, and $\Bil\kR (M)$, $\Sym\kR
% (M)$ and $\Quad\kR (M)$ for the $k$-vector spaces of forms commuting
% with~$R$. We say that a quadratic form commutes with~$R$ if its polar
% form does.


\begin{prop}\label{prop:trace-form}
Let~$K/k$ be a separable field extension, and~$V$ be a finite-dimensional
vector space over~$K$.

For any $k$-bilinear form~$b: V ⊗ V → k$ commuting with~$K$, there
exists a unique $K$-bilinear form~$b_K: V ⊗ V → K$ such that~$b =
\Tr_{K/k} \,∘ \,b_K$.
\end{prop}


\begin{proof}
We first recall the (classical) proof of the result when~$V = K$. In this
case, let~$z$ be a primitive element of~$K$ and write $d = [K:k]$.
Since~$K/k$ is
separable, the trace form is non-degenerate~\cite[VI~5.2]{lang} and there
exists a unique element~$c ∈ K$ such that $\Tr (c z^i) = b(1, z^i)$ for
all~$i=0, …, d-1$. We immediately see that, for all~$x, y ∈ k$, $\Tr (c x
y) = b(x, y)$.

The general case now follows directly from taking coordinates in~$K$: all
coordinates of a bilinear form are themselves bilinear forms.
% We now prove the general case. Let~$n = \dim_K V$ and write the matrix
% of~$b$ as~$(b_{i,j})$, where $b_{i,j}: K ⊗ K → k$ is $k$-bilinear. Since
% $b_{i,j}$ again satisfies the hypotheses of the proposition, there exists
% a unique~$c_{i,j} ∈ K$ such that~$b_{i,j} (x,y) = \Tr_{K/k} (c_{i,j} x
% y)$. The bilinear form~$b_K$ is then the form with matrix~$(c_{i,j})$.
\end{proof}

\note{Noter que la
construction de Gilles pour la matrice~$T$ telle que $T M = \transpose{M}
T$ revient à peu près à la construction de la forme trace~$x,y ↦
\Tr_{K/k} (xy)$, et est donc aussi contenue dans ce résultat.}

\note{il n'est peut-être pas nécessaire que $p$~soit irréductible, mais
seulement séparable, de même que pour Hensel ci-dessus. On pourrait donc
vraisemblablement travailler directement avec les diviseurs
élémentaires ; mais je suis plus à l'aise avec des corps finis que des
algèbres séparables...}

For any integer~$m$, we define~$R_m$ as the local $k$-algebra $R_m =
k[π]/π^m$, and the $k$-linear form~$τ_m$ on~$R_m$ as the coefficient
of~$π^{d-1}$. We write~$τ$ instead of~$τ_m$ where there is no ambiguity.
We note that~$τ(xy)$, as a $k$-bilinear form on~$R_m$, is non-degenerate.
Actually, multiplication by~$π^{d-1}$ defines a (non-canonical)
$R$-linear isomorphism between~$R$ and its dual (as a $k$-vector
space)~$R^{∨}$.

\begin{prop}\label{prop:trace-local}
Let~$R = R_m$ and $M, N$ be $R$-modules of finite length. For any
$k$-bilinear form~$b: M ⊗ N → k$ commuting with~$R$, there exists a
unique $R$-bilinear form~$b_R: M ⊗ N → R$ such that~$b = τ ∘ b_R$.
% Let~$R$ be the local algebra~$R = k[π]/π^d$ and define the $k$-linear
% form~$τ_d$ on~$R$ as the coefficient of~$π^{d-1}$. For any finite free
% $R$-modules~$V, W$ and $k$-bilinear form~$b: V ⊗ W → k$ commuting
% with~$R$, there exists a unique $R$-bilinear form~$b_R: V ⊗ W →
% R$ such that~$b = τ_d ∘ b_R$.
\end{prop}

Note that we do not demand that $M$, $N$ be \emph{free} as $R$-modules.
Moreover, the unicity of~$b_R$ shows that both forms~$b$ and~$b_R$ are
simultaneously symmetric or antisymmetric. However, when $k$~is a field
of characteristic two, it may happen, as we shall see in~§2, that $b$~is
alternating whereas $b_R$~is not.

\begin{proof}[\protect{Proof of Prop.~\ref{prop:trace-local}}]
By the structure theorem of modules over a principal ring, we may
write~$M = ⊕ R_{m_i}$ for some finite sequence of integers~$m_i$. If the
result holds for modules~$(M', N)$ and~$(M'', N)$ then it also holds
for~$(M' ⊕ M'', N)$. Therefore, using induction on the length of both
modules, we only need to prove the case where~$M = R_m$ and~$N = R_n$
where~$m ≥ n$. In this case, since $b$~commutes with~$k[π]$, we see that
for~$x = ∑ x_i π^i$, $y = ∑ y_i π^i$:
\begin{equation}
b(x,y) \;=\; ∑_{i,j} x_i y_j\: b(1, π^{i+j})
  \;=\; ∑_{i+j+r = m-1} x_i y_j\: b(1, π^{m-1-r}).
\end{equation}
Let~$c = ∑ b(1, π^{i}) π^{m-1-i}$. Since $b(1, π^{r}) = 0$ for all~$r ≥
n$, $c$~belongs to the ideal~$π^{m-n} R_m = \Hom_R (R_n, R_m)$, so that
the product~$c\,y$ is well-defined in~$R_m$. The bilinear form~$b_R$ is
finally the form defined by~$b_R(x,y) = c\:xy$.
\end{proof}

Assembling the Propositions~\ref{prop:trace-form}
and~\ref{prop:trace-local}, we see that for any local pencil~$(b_{∞},
b_0)$, writing~$R = k[c]$ where $c$~is the characteristic endomorphism
of~$b$, there exists a unique $R$-bilinear form~$b_R$
on~$V$ such that~$b_{∞} = \Tr_{K/k} ∘ τ_d ∘ b_R$.
Local pencils are thus equivalent to $R$-bilinear forms on~$V$.
Moreover, a morphism of pencils~$s: b → b'$ is a
$k$-linear map such that~$\transpose{s} ∘ b_{∞} ∘ s = b'_{∞}$
and~$s^{-1} ∘ c ∘ s = c'$, or in other words a $R$-linear congruence
between the $R$-bilinear forms~$b_R$ and~$b'_R$. Therefore, solving the
local IP1S problem amounts to computing a congruence matrix
between two~$R$-bilinear forms on a $R$-module of finite length.

\note{C'est à peu près ce que dit (22) du preprint IP2S.}


\begin{prop}\label{prop:diag-bigblock}
Let~$M$ be a $R$-module of finite length and $b$~be a $R$-bilinear form
on~$M$. If the $k$-bilinear form~$τ ∘ b$ is regular, then there exists an
orthogonal decomposition~$M = \operp M_d$, where $M_d$~is a finite free
module over~$R_d = R / π^d$ and $b$~is regular, as a
$R_d$-bilinear form, on each module~$M_d$.
\end{prop}


\begin{proof}
We reason by induction on the length of~$R$. By the structure theorem for
modules over the principal ring~$R$, there exists a decomposition~$M = F
⊕ N$ where $F$~is free over~$R = k[π]/π^m$ and~$π^{m-1} N = 0$. In
particular, $N$~is a $R'$-module, where~$R' = R / π^{m-1}$; we define~$τ'
= τ_{m-1}: R' → k$ and note that~$τ'(a) = τ(π a)$ for all~$a ∈ R'$.

We first show that the restriction of~$b$ to~$F$ is regular. Let~$x ∈ F$
such that~$R x$ is a direct factor: this means that~$π^{m-1} x ≠ 0$.
Since $τ ∘ b$~is regular, there exists~$y ∈ M$ such that~$τ(b(π^{m-1} x,
y)) = 1$. This implies that~$b(x, y) ≡ 1 \pmod{π}$. Let~$y = y' + y''$
where~$y' ∈ F$ and~$y'' ∈ M/F$: since~$π^{m-1} y'' = 0$, we have~$π^{m-1}
b(x, y'') = 0$ and therefore~$b(x, y'') ∈ π R$. Therefore, $a = b(x, y')
≡ b(x, y) ≡ 1 \pmod{π}$. In particular, $a ∈ R^{×}$, so that~$b(x, a^{-1}
y') = 1$, which shows that $b$~is regular on~$F$.

Let now~$y ∈ N$. Since $b$~is regular on~$F$, there exists a unique~$f(y)
∈ F$ such that, for all~$x ∈ F$, $b(x, y) = b(x, f(y))$. This implies
that the map~$N → M, y ↦ y - f(y)$ is orthogonal to~$F$, and therefore
defines a $b$-orthogonal decomposition~$M = F ⊕ N$. Finally,
since~$π^{m-1} y = 0$, the map~$b$ has its values in~$π R$, which means
that there exists a $R'$-bilinear form~$b'$ on~$N$ such that~$b = π b'$;
since $τ ∘ b$~is regular, its orthogonal summand $τ' ∘ b'$~is regular,
and we may apply the induction hypothesis to the $R'$-bilinear form~$b'$
on~$N$.
\end{proof}

We shall generally call $b$ \emph{regular} if $τ ∘ b$~is regular as a
$k$-bilinear form. If $M$~is free then this does not conflict with the
standard definition of $R$-regularity.

Note that, if we do not assume $b$~to be regular, then there does not
necessarily exist a decomposition equivalent to that of
Prop.~\ref{prop:diag-bigblock}. For example, the $R_2$-bilinear form
over~$M = R_1 ⊕ R_2$ defined by~$b(x_1 ⊕ x_2, y_1 ⊕ y_2) = (π x_1) y_2 -
x_1 (π y_2)$ is not diagonalizable.


\begin{prop}\label{prop:bilinear-odd}
Assume that $2 ≠ 0$ in~$k$; let~$R = k[π]/π^m$ and let~$M$ be a free
$R$-module.
\begin{enumerate}
\item Any regular $R$-bilinear form~$b$ on~$M$ is diagonalizable.
\item Assume that $k$~is finite. Then any regular $R$-bilinear form~$b$
on~$M$ is equivalent to one of the diagonal forms~$(1, …, 1)$ or~$(1, …,
d)$, where $d ∈ k^{×}$~is not a square.
\end{enumerate}
\end{prop}


\subsection{Quadratic pencils in characteristic two}

If~$2 ≠ 0$ in~$k$, then quadratic pencils are the same as bilinear
pencils. Therefore, we shall only concern ourselves here with the case
where $k$~has characteristic two. We say that a quadratic form
\emph{commutes} with~$R$ if its polar form commutes in the above sense.

\begin{prop} \label{prop:trace-quad}
Let~$K$ be a finite separable extension of~$k$ and~$V$ be a $K$-vector
space. For any $k$-quadratic form~$q: V ⊗ V → k$ commuting with~$K$,
there exists a unique $K$-quadratic form~$q_K: V ⊗ V → K$ such that~$q =
\Tr_{K/k} \, ∘ \, q_K$.
\end{prop}

\note{À peu près la prop. 5 du papier Asiacrypt.}

\begin{proof}
Let~$b$ be the polar form of~$q$. By~\ref{prop:trace-form},
there exists~$b_K ∈ K$
such that~$b(x,y) = \Tr_{K/k} (b_K xy)$; in particular, since $b$~is
alternating, for all~$x$ we have~$\Tr_{K/k} (b_K x^2) = 0$ and
therefore~$b_K = 0$. Therefore, $q$~is a semi-linear form; since the
trace map is non-degenerate, there exists~$q_K$ such that~$q(x) =
\Tr_{K/k} (q_K x^2)$.

As in the bilinear case, the $n$-dimensional case directly follows by
taking coordinates. Here all diagonal entries correspond to quadratic
forms, and all others to bilinear forms; all of these commute with~$K$.
\end{proof}

We again define~$R = R_n = k[π]/π^n$. We recall that the Frobenius
morphism on~$R$ is defined by~$σ(x π^i) = x^2 π^i$; we also define the
Verschiebung morphism by~$V(x π^i) = x π^{2i}$, and note that both
maps~$σ$ and~$V$ are ring morphisms and that their composition, in any
order, is the squaring map. Moreover, we have the decomposition~$R = V(R)
⊕ π V(R)$.

\begin{lem}\label{lem:gamma-polar}
Let~$γ: R → R$ be the application defined, for~$x = V(y) + π V(z)$,
by~$γ(x) = π V(yz)$. Then, for all~$u, x ∈ R$, we have
\begin{enumerate}
\item $γ(ux) = γ(u) x^2 + u^2 γ(x)$;
\item $γ(u+x) = γ(u) + γ(x) + ux + V(α)$ for some~$α ∈ R$.
\end{enumerate}
\end{lem}


\begin{proof}
(i)~Write~$x = V(y) + π V(z)$ and~$u = V(v) + π V(w)$. Noticing
that~$σ(x) = y^2 + π z^2$, we then have
\begin{equation}\label{eq:gamma-prod}
\begin{split}
γ(ux) &= π V\pa{(vy + π wz)(wy+vz)}\\
 &= π V\pa{vw (y^2 + π z^2)} + π V \pa{(v^2+πw^2) yz}\\
 &= γ(u) V(σx) \;+\; V(σu) γ(x) \quad = γ(u) x^2 + u^2 γ(x).
\end{split}
\end{equation}

(ii) follows from
$γ(u+x) - γ(u) - γ(x) = π V(vz + wy) = ux - V(vy+πwz)$.
\end{proof}

We recall that $τ(xy)$~is a non-degenerate $k$-bilinear form
on~$R$, and we write~$R^{τ}$ for the $τ$-orthogonal of~$V(R)$: this is
the space of~$x$ such that, for all~$y ∈ R$, $τ(xV(y)) = 0$ (or
equivalently, $τ(x y^2) = 0$); this space is linearly spanned by
the~$π^{n-2i}$ for~$0 ≤ i ≤ n/2$. We call the elements of~$R^{τ}$
\emph{$τ$-alternating}, for reasons made obvious by the following
proposition.


\begin{prop}\label{prop:trace-alt}
Let~$M = ⨁ R_{n_i}$ be a $R_m$-module of finite length.
\begin{enumerate}
\item Let~$b$ be the $R$-bilinear form defined by~$b((x_i), (y_i)) = ∑
b_{i,j} x_i y_j$. Then $τ ∘ b$~is alternating if, and only if, $b_{i,j} +
b_{j,i} = 0$ and if the diagonal coefficients $b_{i,i}$ are
$τ$-alternating.
\item Let~$q$ be a $k$-quadratic form on~$M$ commuting with~$R$, $b$~its
polar form, and $b_R$ be the unique $R$-quadratic form such that~$b = τ ∘
b_R$, and~$b_{i,j}$ the coefficients of~$b_R$; then there exists a
$σ$-linear form~$a: M → R$ such that, for all~$x = (x_i) ∈ M$,
\begin{equation}
q(x) \;=\; τ\pa{a(x) + ∑_{i} b_{i,i} γ(x_i) + ∑_{i < j} b_{i,j} x_i x_j}.
\end{equation}
\end{enumerate}
\end{prop}

\begin{proof}
(i) follows from a simple computation. To prove~(ii), we see by
Lemma~\ref{lem:gamma-polar} that for all~$c ∈ R^{τ}$, $τ(c γ(x))$~is a
quadratic form on~$R$ with polar~$τ(c\, xy)$. It follows by linearity
that~$q' = τ(∑ b_{i,i} γ(x_i) + ∑ b_{i,j} x_i x_j)$ is a $k$-quadratic
form on~$M$, which has the same polar as~$q$, so that
the difference~$q - q'$ is a $σ$-linear form.
\end{proof}

% Let~$\Alt_R (M)$ be the $R$-module of alternating bilinear forms and
% $\Alt\kR (M)$ be the $k$-vector space of forms commuting with~$R$. We
% obtain the following commuting diagram, where all lines and columns are
% exact:
% \begin{equation} \xymatrix{
% \Hom_R^{σ} (M, R) \ar[r]\ar@{=}[d] & \Quad_R (M)\ar[r]\ar[d] &
%   \Alt_R (M)\ar[d] \\
% \Hom_k^{σ} (M, k) \ar[r]& \Quad\kR (M) \ar[d]\ar[r] &
%   \Alt\kR (M) \ar[d] \\
%  & \Hom_R^{σ} (M, R^{τ}) \ar@{=}[r] &\Hom_R^{σ} (M, R^{τ}) \\
% }
% \end{equation}
% Here~$\Hom^{σ}$ is the set of $σ$-linear maps.

We now give a standard form for the bilinear form~$b_R$. We note that
this is a symmetric bilinear form, and that its diagonal coefficients are
alternating; if the length~$m$ of~$R$ is even, this means that they are
squares in~$R$, whereas if $m$~is odd, then the diagonal coefficients
belong to~$π V(R)$.


\begin{prop}\label{prop:eqv-norm}
Let~$R = k[π]/π^r$ and let~$M$ be a free $R$-module. For any bilinear
form~$b$ on~$M$, define the \emph{norm} of~$b$ as the ideal~$\fr n b$ of~$R$
generated by the elements~$b(x, x)$ for~$x ∈ M$.

Then two non-degenerate, $τ$-alternating forms are equivalent if and only
if they have the same norm.
\end{prop}

% Let~$R = R_m$ and let~$M$ be a free $R$-module and $b$~be a
% $τ$-alternating, non-degenerate bilinear form on~$M$. Let~$\fr a$ be the
% ideal of~$R$ generated by the values~$b(x, x)$ for~$x ∈ M$.
% \begin{enumerate}
% \item If $\fr a = R$ then $b$~is isomorphic to the bilinear form with
% identity matrix.
% \item Else, for any generator~$a$ of~$\fr a$, $b$~is isomorphic to the
% orthogonal direct sum
% \[ \mat{a & 1\\1&0} ⟂ \mat{0 & 1\\1&0} ⟂ … ⟂ \mat {0 & 1\\ 1 & 0}. \]
% \end{enumerate}
% Furthermore, the first case may occur only if $R$~has even length.
% \end{prop}

\begin{proof}
We show that the bilinear form~$b$ is equivalent to either the form with
identity matrix, if $\fr n b = R$; or the orthogonal direct sum
\[ \mat{a & 1\\1&0} ⟂ \mat{0 & 1\\1&0} ⟂ … ⟂ \mat {0 & 1\\ 1 & 0}, \]
where $a$~is a generator of~$\fr n b$, if $\fr n b ⊂ π R$.

We write~$[u]$ for the diagonal form with coefficient~$u$ and~$H_{v, w}$ for
the form with matrix~$\mat{v&1\\1&w}$. We also write~$H = H_{0,0}$.

By~\cite[§2]{milnor2}, the $k$-bilinear form~$b_k = b ⊗_R k$ has a
decomposition~$b_k ≃ [d_1] ⟂ … ⟂ [d_r] ⟂ H^s$, where all~$d_i$ are
non-zero since $b$~is non-degenerate. We distinguish two cases.

\subparagraph{Case 1: $\fr n b = R$.}
Then the list of~$d_i$ in the above
decomposition is not empty. Moreover, since the field $k$~is perfect, all
elements~$d_i$ are squares in~$k$, so that up to a coordinate change we
may assume that~$d_i = 1$. Finally, we note that the
matrix~$\mat{1&1&0\\1&0&-1\\1&1&-1}$ is an isomorphism between the
forms~$[1] ⟂ [1] ⟂ [-1]$ and~$[1] ⟂ H$, so that if $r ≥ 1$ we may cancel
all the direct factors~$H$ and in this case $b_k$~is isomorphic to the
bilinear form with identity matrix.

By~\cite[Corollary 3.4]{baeza}, the diagonalization of~$b_k$ lifts to a
diagonalization $b ≃ [a_1] ⟂ … ⟂ [a_r]$ over~$R$. Since $b$~is
$τ$-alternating, all coefficients~$a_i$ are $τ$-alternating. If the
length of~$R$ is odd, then the set of $τ$-alternating elements of~$R$
is~$π V(R)$, which contradicts the regularity of~$b$. Therefore, the
length of~$R$ is even, which means that $a_i ∈ V(R)$ and they are
therefore squares in~$R$. From this we deduce that $b$~is isomorphic to
the identity bilinear form.

\subparagraph{Case 2: $\fr n b ⊂ π R$.}
This means that the form~$b_k$ is alternating, so that~$b_k ≃ H^s$.
By~\cite[Corollary 3.4]{baeza}, this decomposition again lifts to a
decomposition $b ≃ H_{u_1, v_1} ⟂ … ⟂ H_{u_s, v_s}$, where all
coefficients~$u_i, v_i$ are $τ$-alternating.

Let $b = H_{u,v}$ be $τ$-alternating and regular; up to a swap of~$u, v$, we
may write it as~$H_{u, u a^2}$ for some~$a ∈ R$. Since $b$~is
regular, $1 + a u ∈ R^{×}$. Therefore, the coordinate
change $P = \mat{1+a u & a/(1+a u) \\ u & 1/(1+a u)}$ transforms the
bilinear form~$b$ to~$H_{u, 0}$.

Finally, we note that the bilinear form~$b = H_{u, 0} ⟂ H_{u a^2 u, 0}$ is
isomorphic to~$H_{v, 0} ⟂ H_{0,0}$ via the coordinate change
% \begin{equation}
$\mat{1 & 0 & a & 0\\0&1&0&0\\0&0&1&0\\au & a & 0 & 1}$.
% \end{equation}
\end{proof}


The \emph{hyperbolic plane} is the module $R^2$, equipped with the
$k$-quadratic form~$q(x) = x_1 x_2$; this form commutes with~$R$. The
corresponding $τ$-alternating bilinear form~$b_R$ has the
matrix~$\mat{0&1\\1&0}$. A quadratic module is \emph{hyperbolic} if it is
isomorphic to the orthogonal sum of copies of the hyperbolic plane.

\begin{prop}
Any free regular $(k, R)$-quadratic module is isomorphic
to the orthogonal direct sum of a hyperbolic space and of a quadratic form
of dimension at most four.
\end{prop}

\begin{proof}
Let~$M = R^m$ and $q$~be a regular quadratic form on~$M$, commuting
with~$R$. Let~$b$ be the polar of~$q$. By Prop.~\ref{prop:eqv-norm}, we
know that $b_R$~is isomorphic to some form
\begin{equation}
\mat{a & 1\\1 & 0} ⟂ \mat{0 & 1\\1 & 0}^{⊗m-2}, a ∈ R^{τ}, \quad\text{or}\quad
\mat{1} ⟂ \mat{0&1\\1&0}^{⊗m-1}.
\end{equation}
For simplicity, we assume the first case; the proof in the second case is
the same.
\end{proof}


\begin{prop}
Any free regular $(k, R)$-quadratic pencil is isomorphic to the
orthogonal direct sum of a hyperbolic pencil and of a quadratic pencil of
dimension at most six.
\end{prop}


\begin{proof}
\note{Pareil...}
\end{proof}


% \begin{lem}\label{lem:exp-binary}
% Let~$E(x)$ be the formal series
% \begin{equation}
% E(x) = ∑_{i ≥ 0} x^{2^{i}-1} \quad ∈ ℤ[[x]].
% \end{equation}
% Then we have the equality in~$\F_2[[x,y]]$:
% \begin{equation}
% \frac{E(x+y)}{E(x)}{E(y)} \;=\; 1 + ∑_{i ≥ 0} ∑_{j=1}^{2^i-1} x^j
% y^{2^i-j}.
% \end{equation}
% \end{lem}
% 
% 
% \begin{lem}
% For any integer~$m$, we have a group isomorphism
% \begin{equation*}
% R_{2m}^{×} / (R_{2m}^{×})^2 \quad ≃ \quad k^m.
% \end{equation*}
% \end{lem}
% 
% \begin{proof}
% For any~$i ≤ n-1$, let~$f_i: k → R_{2m}^{×}$ be the map defined
% by~$f_i(x) = E(π^{2i+1} x)$, where $E$~is the map defined in
% Lemma~\ref{lem:exp-binary}. We then see that $f_i(x+y)/f_i(x) f_i(y)$~is
% a square in~$R_{2m}^{×}$. Since the $m$~maps $f_0, …, f_{m-1}$ are
% obviously linearly independent, they define the required isomorphism.
% \end{proof}
% 

Since the bilinear form~$τ$ is non-degenerate, the linear map~$V: R → R$
has an adjoint~$θ$, defined by $θ(π^{n-1-2i}) = π^{n-1-i}$: for all~$x,
y$, we have~$τ(x\, V(y)) = τ(θ(x)\,y)$. A direct computation proves the
following result.

\note{L'application~$θ$ est la même que celle d'Asiacrypt ; la définition
ici comme adjoint du Verschiebung est un peu plus naturelle. Cependant,
la forme canonique n'est pas la même (du tout) que pour Asiacrypt, et
plus facile à manipuler.
}

Let~$q$ be a $k$-quadratic form on~$M$ commuting to~$R$, and write~$q$ as
in Prop.~\ref{prop:trace-alt}; then there exists elements~$a_i ∈ R$ such
that $a((x_i)) = τ(∑ a_i σ(x_i))$. Let~$u: M' → M$ be a $R$-linear map,
and define the $k$-quadratic form~$q' = q ∘ u$ on~$M'$ and the
corresponding elements~$a'_i ∈ R$ and $R$-bilinear form~$b'_R$. Then a
direct computation shows that, writing~$(u_{i,j})$ for the matrix of~$u$,
\begin{equation}\label{eq:theta}
b'_R = b_R ∘ u, \quad
a'_i = ∑_r a_r σ(u_{r,i}) + θ \pa{
  ∑_r b_{r,r} γ(u_{r,i}) + ∑_{r<s} b_{r,s} u_{r,i} u_{s,i} }.
\end{equation}

\note{ Il y a une erreur dans le Lemme~2 d'Asiacrypt ; considérer par
exemple la forme bilinéaire~$b(x,y) = τ(xy)$ sur~$R_{2m}$, qui est
non-dégénérée et qui n'a pourtant pas de lagrangien stable par
multiplication par~$π$ (les seuls sous-espaces stables étant les idéaux,
soit les~$π^i R$...). Le mieux qu'on puisse faire est de considérer le
morphisme~$V: R_{2m} → R_{2m}$, qui se factorise en fait en~$V: R_{2m} →
R_m → R_{2m}$, et écrire~$R_{2m} = V(R_m) ⊕ π V(R_m)$, ou encore~$R_{2m}
= R_{m}[π_{2m}]/(π_{2m}^2 - π_m)$. Un lagrangien de~$b$ est alors par
exemple~$V(R_m)$, qui n'est pas stable par multiplication par~$π_{2m}$...
Dans la preuve, l'erreur est dans l'écriture de~$K[π] x ⊕ K[π] y$, alors
que ici $x = y$, donc le signe~$⊕$ est faux.

Mais de toute façon la construction donnée ici est plus simple, donc ce
n'est pas trop grave :-)}

The data of a quadratic pencil on~$M$ with characteristic
endomorphism~$π$ is then equivalent to the data of the two quadratic
forms~$b_{∞}$, given by the bilinear form~$b_R$ and a $σ$-linear
form~$a$, and $b_{0}$, given by~$π b_R$ and a $σ$-linear form~$c$.



% For any~$x ∈ R$ written as~$x = V(y) + π V(z)$, we define~$δ(x) =
% σ^{-1} (yz)$. Then for all~$u = V(v) + π V(w)$, we have
% \begin{equation}
% ux \;=\; V(vy \:+\: π\,wz) \:+\: π V(wy \:+\: vz)
% \end{equation}
% so that
% \begin{equation}\label{eq:delta-deriv}
% \begin{split}
% δ(ux) &= σ^{-1} \pa{wv (y^2 + π z^2) \:+\: (v^2 + π w^2) yz}\\
%  &= σ^{-1} (vw · σ(x)) \:+\: σ^{-1} (σu · yz)\\
%  &= δ(u) x + u δ(x).
% \end{split}
% \end{equation}
% 
% \begin{prop}\label{prop:quad-local}
% Let~$q$ be a quadratic form on~$R$, commuting with~$R$.
% Then there exists elements~$a, c ∈ R$, satisfying~$c^2 = 0$, such that
% \begin{equation*}\label{eq:q-sigma-1}
% q(σ^{-1}x) = τ (a x \:+\: c\, δ(x)).
% \end{equation*}
% \end{prop}
% 
% \begin{proof}[Proof of Prop.~\ref{prop:quad-local}]
% Let~$b$ be the polar form of~$q$. By Prop.~\ref{prop:trace-local}, there
% exists~$r ∈ R$ such that~$b(x,y) = τ (rxy)$. Moreover, since $b$~is
% alternating, $r$~is orthogonal to all squares in~$R$: for all~$x ∈ R$ we
% have~$τ(rx^2) = 0$ and therefore, for all~$i$, $τ(π^{2i} r) = 0$.
% 
% Define~$a = ∑_i π^{n-i-1} q(π^i)$. We then see that $q(x) = τ(a σ(x)) +
% τ( r ∑_{i < j} x_i x_j)$. Write~$x = V(y) + π V(z)$; then in the last
% sum, only the terms of odd degree in~$π$ are not orthogonal to~$r$, and
% their sum is exactly~$π V(yz)$.
% 
% Let~$θ: R → R$ be the adjoint map to~$V$, defined by~$τ(x\, θ(y)) =
% τ(V(x)\, y)$ for all~$x, y$. Then $τ( πr\, V(yz)) = τ(θ(πr)\, yz)$.
% Let~$c = θ(π r)$; since~$θ(π^{n-2i-1}) = π^{n-i-1}$, we have $v_R(c) ≥
% n/2$, so that $c^2 = 0$ in~$R$. Since~$δ(σ(x)) = yz$, we can now write
% $q(x) = τ(a σ(x) + c δ(σx))$, from which the proposition follows by
% applying~$σ^{-1}$.
% \end{proof}
% 
% Write~$q = [a, c]$ for the quadratic form defined by
% Proposition~\ref{prop:quad-local}. We deduce from \eqref{eq:delta-deriv}
% that, for all~$u ∈ R$, the form~$q(ux)$ is given by
% \begin{equation}\label{eq:q-transform}
% [a, c] ∘ u = [a\,u \:+\: c\, δ(u),\; c\,u].
% \end{equation}

% Solving the cyclic case of IP1S in characteristic two is therefore
% equivalent to solving the above equation in~$u ∈ R$. This is possible in
% polynomial time since $δ$~is contracting.




% We saw in~§2.1 that any regular bilinear pencil on~$V$ is the orthogonal
% sum of pencil of the form $b_{λ} = t a (λ - c)$, where $t$~is any
% prescribed scalar product on~$V$, $a$~is a self-adjoint map relatively
% to~$t$, and $c$~is the characteristic endomorphism of~$b$.
% 
% Using the primary factorization of~$c$, we may assume that its minimal
% polynomial is primary, \emph{i.e.} of the form~$p^d$ where $p$~is
% irreducible. In this case, there exists a finite sequence of
% integers~$n_i$ such that~$V$, as a $k[c]$-module, is isomorphic to~$⨁
% k^{n_i} ⊗_{k} k[c]/p(c)^{i}$. Write~$R_n = k[c]/p(c)^n$ and~$K = R_1 =
% k[c]/p(c)$; then $K$~is a finite extension field of~$k$. Consider the equation~$p(y) = 0$ for~$y ∈ R_n =
% k[c]/p(c)^n$; since $p(c)$~generates the maximal ideal~$\fr m$ of~$R_n$,
% $c$~is an approximate solution of the equation, and since $p$~is
% irreducible, the equation is separated. Therefore, by Hensel's lemma,
% there exists a unique solution~$y ∈ R_n$ of~$p(y) = 0$ such that~$y ≡ c
% \pmod{\fr m}$. This defines a $k$-algebra morphism~$K → R_n$, and we see
% that this is an isomorphism between~$R_n$ and the local
% $K$-algebra~$K[π]/π^n$ sending~$p(c)$ to~$π$.
% 
% \note{Je viens de prouver, en d'autres termes, quelque chose qui est déjà
% dans le papier : on peut, au lieu d'utiliser la forme normale de
% Frobenius, utiliser celle où les blocs sur-diagonaux sont la matrice
% identité (ce qui est avant 2.14). Au passage, calculer le commutant
% de~$c$ devient trivial : c'est le commutant de~$c$, et il suffit donc de
% demander que tout le monde soit $k[c]$-linéaire...}
% 
% \note{Pas besoin du lemme de Hensel pour prouver le résultat qui
% précède : en effet, $(K[π]/π^n, c)$ et~$(V, c)$ sont deux $k$-espaces
% vectoriels équipés d'un endomorphisme cyclique de même polynôme
% caractéristique, et donc forcément isomorphes. Hensel sert à donner une
% version effective.}
% 
% Let~$τ$ be the $k$-linear form on~$R_n$ defined in the following way:
% for~$u = ∑ u_i π^i ∈ R_n$, with~$u_i ∈ K$, let~$τ(u) = \Tr_{K/k}
% (u_{n-1})$. Since $p$~is separable, the trace bilinear form~$u, v ↦
% \Tr_{K/k} (uv)$ is non-degenerate on~$K$. Hence the bilinear form~$t$
% defined by~$t(u,v) = τ(uv)$ is non-degenerate on~$R_n$. Moreover, the
% linear map~$c$, corresponding to multiplication by~$c$, is obviously
% self-adjoint for this bilinear form.
% 
% \note{Le paragraphe qui précède est une façon différente et peut-être un
% peu plus courte de construire la matrice $T$ de Gilles ; ce n'est
% d'ailleurs pas la même matrice (on a en fait~$T(u, v) = t(u, h v)$ pour
% un certain~$h ∈ K^{×}$). Pour prouver que $t$~est non-dégénéré : soit~$u
% = u_r π^r + u_{r+1} π^{r+1} + …$ avec~$r ≤ d-1$; puisque $\Tr$~est
% non-dégenéré, il existe~$v ∈ K$ tel que~$\Tr (v u_r) = 1$, et on vérifie
% alors que~$t(u, v π^{d-r-1}) = 1$.}
% 
% 
% \begin{prop}
% Let~$b$ be a bilinear pencil. Assume that $b$~is local, \emph{i.e.} that
% its characteristic polynomial is~$p(c)^d$ where $p$~is irreducible. Then
% there exists a finite sequence of integers~$(n_i)$ such that $(V, b)$~is
% isomorphic, as a $k$-bilinear pencil, to
% \begin{equation}
% (⨁ E_i ⊗_{K} R_i, \quad ⨁ t_i a_i (λ - c)),
% \end{equation}
% where $E_i$~is the space~$K^{n_i}$ equipped with its canonical scalar
% product, $t_i$~is the trace scalar product on~$R_i$ defined above, and
% $a_i$~is an invertible self-adjoint $k[c]$-linear endomorphism of~$E_i
% ⊗_{K} R_i$.
% \end{prop}
% 



\section{Old version of §1}

We write~$K_d$ for the Kronecker module of dimension~$2d+1$: its basis
is~$(e_0, …, e_d, f_1, …, f_d)$, with the bilinear pencil~$b_{λ}$ defined
by~$-b_{∞} (e_j, f_{j+1}) = b_{0} (e_j, f_j) = 1$ and~$0$ else. We shall
write~$e_{d,i}$ and~$f_{d,i}$ when needed to prevent ambiguity. We also
write~$K_d^+$ for the space generated by the vectors~$e_i$ and~$K_d^-$
for that generated by the~$f_i$.

Let~$k^n$ be the $n$-dimensional vector space, equipped with its
canonical scalar product and its canonical basis~$(ε_1, …, ε_n)$. Given a
sequence of integers~$(n_d)$, we write~$E_d = k^{n_d}$. The
bilinear module~$K_d^{n_d}$ is isomorphic to~$E_d ⊗ K_d$, with the basis~$ε_i ⊗
e_j, ε_i ⊗ f_j$. We order this basis in the following way: $ε_1 ⊗ e_0, …,
ε_{n_d} ⊗ e_0, …, ε_{n_d} ⊗ e_d, ε_1 ⊗ f_1, …, ε_{n_d} ⊗ f_1, …, ε_{n_d} ⊗ f_d$.

\begin{prop}
Let~$V = ⨁ K_d^{n_d} = ⨁ E_d ⊗ K_d$ be a module with a totally irregular
bilinear pencil. Each automorphism of~$V$ is the product, in
this order, of the following maps:
\begin{enumerate}
\item an endomorphism of the form
\[\begin{array}{rcl}
u ⊗ e_{d,i} & \longmapsto & \displaystyle ∑_{m ≥ 0} ∑_{j=0}^{m}
  α_{d,m,j} (u) e_{d-m,i-j},\\
u ⊗ f_{d,i} & \longmapsto & \displaystyle ∑_{m ≥ 0} ∑_{j=0}^{m}
  β_{d,m,j} (u) f_{d+m,i+j},
\end{array}\]
where~$α_{m,j}: E_{d} → E_{d-m}$ and~$β_{m,j}: E_{d} →
E_{d+m}$ are $k$-linear maps such that, when writing~$α_{d,m} = ∑ x^j
α_{d,m,j}$ and~$β_{d,m} = ∑ y^j β_{d,m,j}$, we have the relation
\begin{equation}
∑_{i+j=m} \transpose{α_{d+m,i}} β_{d,j} = \begin{cases}
1 & \text{if $m = 0$,}\\0 & \text{if $m ≥ 1$.}
\end{cases}
\end{equation}
\item the map defined by
\[\begin{array}{rcl}
u ⊗ e_{d,i} & \longmapsto & u ⊗ e_{d,i},\\
u ⊗ f_{d,i} & \longmapsto & u ⊗ f_{d,i} + \displaystyle
  ∑_{(d',i')} γ_{d,d',i+i'}(u) ⊗ e_{d',i'}\\
\end{array}\]
where $γ_{d,d',i}: E_d → E_{d'}$, for~$i=1,…, d+d'$, is a linear
map such that~$\transpose{γ_{d,d',i}} = γ_{d',d,i}$.
\end{enumerate}
\end{prop}

% \begin{prop}\label{prop:Aut-Kdn}
% The isometries of~$K_d^n → K_d^n$ have the matrix form
% \[ \mat{A&&&&&\\ &⋱&&&(C_{i+j})&\\&&A&&&\\
%   &&&\transpose{A^{-1}}&&\\&0&&&⋱&\\&&&&&\transpose{A^{-1}}}, \]
% where $A$~is an invertible matrix of size~$n × n$, and the
% matrices~$(C_{i})$, for~$i = 1, …, 2d$, are such that $A^{-1} C_{i}$~is
% symmetric.
% \end{prop}
% 
% \begin{proof}
% Let~$K_d[λ] = K_d ⊗_{k} k[λ]$. We recall that the kernel of~$b_{λ} =
% b_{0} + λ b_{∞}$ in~$K_d[λ]$ is the line generated by~$e(λ) = ∑ λ^j e_j$.
% 
% Let~$u: K_d^n → K_d^n$ be an isometry; it extends as an isometry of~$E ⊗
% K_d[λ]$. For all~$v ∈ k^n$, the vector~$u(v
% ⊗ e(λ)$ belongs to the kernel of~$b_{λ})$ and is therefore of the
% form~$α(v) ⊗ e(λ)$, where $α: E → E$~is a linear map. Since $u$~is an
% automorphism, the map~$α$ is invertible.
% 
% There exist linear maps~$β_{i,j}, γ_{i,j}: E → E$ such that~$u(v ⊗ f_i) =
% ∑ β_{i,j} (v) ⊗ f_j + ∑ γ_{i,j} (v) ⊗ e_j$. The relations for~$b_{λ}
% (u(v ⊗ e_i), u(v' ⊗ f_j))$ write down as
% \begin{equation}
% α(v) · β_{i,j} (v') = \text{$1$ if $r = i$, $0$ else;}
% \end{equation}
% since $α$~is regular, this means that $β_{i,i} = α' = \transpose{α}^{-1}$
% and all other~$β_{i,j}$ are zero. The relations~$b_{λ} (u(v ⊗ f_i), u(v' ⊗
% f_j)) = 0$ write down as
% \begin{equation}
% γ_{i,j}(v) · α'(v') + α'(v) · γ_{j,i} (v') = 0; \quad
% γ_{i,j-1} (v) · α'(v') + α'(v) · γ_{j,i-1} (v') = 0.
% \end{equation}
% Letting~$C_{i,j}$ be the matrix of~$γ_{i,j}$ and~$C'_{i,j} = A^{-1}
% C_{i,j}$, these relations become
% \begin{equation}
% C'_{i,j} + \transpose{C'_{j,i}} = 0, \quad
% C'_{i,j-1} + \transpose{C'_{j,i-1}} = 0.
% \end{equation}
% From these we deduce that $C'_{i,j} = C'_{i+1,j-1}$ and $C'_{i,j} +
% \transpose{C'_{i,j}} = 0$.
% \end{proof}



We write~$Δ$ for the canonical isomorphism from diagonal matrices to
column vectors, and $∇ = Δ^{-1}$. We easily check that, for any column
vector~$X$ and square matrix~$A$, we have~$Δ(A ∇(X) \transpose{A}) = σ(A)
X$, where $σ$~is the absolute Frobenius.

Let~$q$ be a quadratic pencil, with polar form
isomorphic to~$K_d^n$; then, using the above basis of~$E ⊗ K_d$, there
exist coumn vectors~$D_0, …, D_d, E_1, …, E_d$ such that $b$~has a matrix
of the form
\[ B(D_0,…, E_d) =
  \mat{∇(D_0)&&&&-λ&&\\&∇(D_1)&&&1&⋱&\\&&⋱&&&⋱&-λ\\&&&∇(D_d)&&&1\\
  &&&&∇(E_1)&&\\&0&&&&⋱&\\&&&&&&∇(E_d)}.
\]
\begin{prop}\label{prop:aut-Kdn-diag}
Let~$b$ be a quadratic pencil with matrix~$B(D_0,…, E_d)$ and~$u$ be an
isometry of~$K_d^n$, with matrix given by~$A, C_i$ as in
Prop.~\ref{prop:Aut-Kdn}. Then $b ∘ u$ has matrix $B(D'_0, …, E'_d)$,
where
\begin{eqnarray*}
D'_i &=& \transpose{σ(A)} · D_i),\\
E'_i &=& σ(A)^{-1} · E_i + ∑_j σ(\transpose{C_{i+j}}) · D_j
  - λ Δ(A^{-1}·C_{2i-1}) + Δ(A^{-1}·C_{2i}).
\end{eqnarray*}
\end{prop}

Write~$X = σ(A^{-1})$ and the symmetric matrix~$A^{-1} C_{i}$ as~$∇(Y_i)
+ Z_i + σ^{-1}(Z_i)$, where $Z_i$~is alternate.
Given two quadratic pencils with polar forms isomorphic to~$K_d^n$ and
diagonal coefficients~$D_0, …, E_d$ and~$D'_0, …, E'_d$, the IP1S problem
then reduces to the equations
\begin{equation}\begin{split}
D_i &= \transpose{X} D'_i,\\
E'_i &= X E_i + ∑ D'_j × σ(Y_{i+j}) - λ Y_{2i-1} + Y_{2i}
  + ∑ Z_{i+j} · D'_j,
\end{split}\end{equation}
where $×$~is the coefficient-wise product of the two column
vectors~$D'_j$ and~$σ(Y_{i+j})$.


\begin{thebibliography}{m}
\bibitem{lang} S. Lang, \emph{Algebra}.
\bibitem{jacobson} N. Jacobson, \emph{The Theory of Rings}
\bibitem{baeza} R. Baeza, \emph{Quadratic Forms over Semilocal Rings}
\bibitem{milnor2} J. Milnor, \emph{Symmetric inner products in
characteristic~2}.
\end{thebibliography}
\end{document}