# The linear time encoding scheme fails to encode

Yotam Dikstein, Irit Dinur and Shiri Sivan Institute for Advanced Study, USA.
email<EMAIL_ADDRESS>Institute of Science, ISRAEL. email:
<EMAIL_ADDRESS>Supported by ERC grant 772839, and ISF grant
2073/21.Weizmann Institute of Science, ISRAEL. email<EMAIL_ADDRESS>
###### Abstract

We point out an error in the paper “Linear Time Encoding of LDPC Codes” (by
Jin Lu and José M. F. Moura, IEEE Trans). The paper claims to present a linear
time encoding algorithm for every LDPC code. We present a family of
counterexamples, and point out where the analysis fails. The algorithm in the
aforementioned paper fails to encode our counterexample, let alone in linear
time.

##  1 Introduction

A Low Density Parity Check (LDPC) code is defined as the null-space of a low
density $m{\times}n$ ($m<n$) matrix over $\mathbb{F}_{2}$. In this context, a
matrix is called low density if each row has $O(1)$ ones. Gallager was the
first to study random ensembles of such codes [2] and proved that they can be
decoded in linear time by a simple message-passing algorithm. Sipser and
Spielman [5] showed that this works whenever the parity-check graph is a good
enough expander.

Although decoding is optimal (linear time), the straightforward encoding
procedure is quadratic, because the generator matrix of these codes is dense.
Are there more efficient algorithms? There are several specific families of
codes for which the encoding complexity has been analyzed. For example:

  * •

Spielman [6] constructs a family of linear time encodable and decodable codes.

  * •

Richardson et al. [4] present a number of encoding schemes (distinguished by
their preprocessing algorithms) and analyze their expected performance on
various LDPC distributions. They find that certain distributions can be
encoded in expected linear time using these algorithms. However, Di et al. [1]
show that these distributions have expected sub-linear distance.

As previously mentioned, Richardson et al. [4] introduce multiple
preprocessing algorithms. These algorithms, notably Algorithms C and D,
exhibit similarities to those proposed by Lu et al. [3]. Both papers aim to
triangularize the input LDPC matrix, or bring it as close as possible to
triangular form, through greedy row and column permutations. The primary
distinction between the algorithms suggested by [3] and [4] lies in the fact
that the former allows a restricted number of row additions along with row and
column permutations, while the latter does not. [4] calculate an expected
quadratic encoding complexity for certain LDPC distributions, whereas [3]
claim that their algorithm assures linear time encoding for all LDPC codes.

Excluding Lu and Moura [3], there have been no claims of a sub-quadratic
encoding algorithm for general LDPC codes. In this note we address the
algorithm presented in [3] and show that it contains a critical flaw.
Specifically, their algorithm is indeed linear-time, but fails to encode the
code given by the input LDPC matrix.

######  Theorem 1.1.

There exists a family of LDPC codes given by matrices $M_{n}$ on which the
algorithm presented in [3] fails to encode the code.

In particular, the algorithm of [3] fails on the $9\times 18$ matrix $M_{18}$
depicted in the following figure, as we illustrate in Section 6.

Figure 1: $M_{18}$. All blank spaces are zeros.

##  2 Definitions

######  Definition 2.1 (Kronecker product).

If $A$ is an $m\times n$ matrix and $B$ is a $p\times q$ matrix, then the
Kronecker product $A\otimes B$ is the $pm\times qn$ block matrix:

A linear code $\mathcal{C}$ specified by a parity check matrix
$M\in\\{0,1\\}^{m\times n}$, is the linear subspace

$\mathcal{C}=\left\\{x\in\\{0,1\\}^{n}\left|\;\vphantom{x\in\\{0,1\\}^{n}Mx=0}\right.Mx=0\right\\}.$

This space is also referred to as the kernel of $M$, denoted as $Ker(M)$. We
like to view $M$ also as the adjacency matrix of a bipartite graph with left
nodes $[n]$ called variables and right nodes $[m]$ called constraints such
that $M(i,j)=1$ iff the $i$-th variable is connected to the $j$th constraint.

Lu and Moura mainly use the graph representation, while we prefer the matrix
view. In Section 2.1 we will present the algorithms from [3] in both
languages. We will freely alternate between the terms variable and column,
constraint and row.

Given a matrix $M\in\\{0,1\\}^{m\times n}$, a set of row indices $C\subset[m]$
and column indices $V\subset[n]$ we use the notation $M(C,V)$ to denote the
sub-matrix of $M$ induced by these sets. This corresponds to the subgraph of
the Tanner graph induced by vertices $V\subset[n]$ and $C\subset[m]$.

We will use the following definition of an (algebraic) circuit over
$\mathbb{F}_{2}$.

######  Definition 2.2 (Circuit).

A circuit $\Phi=(V,E)$ is a directed acyclic graph such that every vertex has
in-degree at most $2$ (i.e. fan-in $2$). The input of the circuit,
$I(\Phi)\subseteq V$ are all vertices with in-degree $0$. The output of the
circuit $O(\Phi)$ are all vertices with out-degree $0$. The size of the
circuit $|\Phi|=|V|$.

Vertices of a circuit are sometimes called gates. We note that while formally,
the fan-in in this model is $2$. The results in this paper remain the same by
relaxing the fan-in bound to any constant $d$ instead.

Let $\Phi$ be circuit with input vertices $I=\\{{v_{1},v_{2},\dots,v_{k}}\\}$
and output vertices $O=\\{{u_{1},u_{2},\dots,u_{m}}\\}$. A circuit naturally
calculates a linear function $T:\mathbb{F}_{2}^{k}\to\mathbb{F}_{2}^{m}$ as
follows. Given $(x_{1},x_{2},\dots,x_{n})\in\mathbb{F}_{2}^{n}$ every input
vertex $v_{i}$ is labeled with $x_{i}$. Then the label of every other vertex
is set to be the sum of the labels of its incoming neighbors (mod $2$). The
fact that $\Phi$ is acyclic ensures that such a labeling is possible. Finally,
the value of
$T(x_{1},x_{2},\dots,x_{k})=(\ell(u_{1}),\ell(u_{2}),\dots,\ell(u_{m}))$ where
$\ell(u_{j})$ is the labeling of $u_{j}$.

######  Definition 2.3 (Linear time encodable codes).

An infinite family of matrices $\\{{M_{n}\in\\{0,1\\}^{m_{n}\times n}}\\}_{n}$
is _linear time encodable_ if there exists a constant $c>0$ and circuits
$\\{{\Phi_{n}}\\}_{n}$ of size at most $cn$ such that $\Phi_{n}$ calculates a
linear isomorphism $T_{n}:\mathbb{F}_{2}^{k_{n}}\to Ker(M_{n})$.

Lu and Moura [3] first present a construction of linear sized circuits and
characterize the codes that are encodable by this construction. These codes
are those whose code graph does not contain certain subgraphs called Encoding
Stopping Sets (ESS) or Pseudo Encoding Stopping Sets (PESS). Graphs without
such subgraphs are called Pseudo-Trees. We beleive this part of their paper is
correct, see [3, Corollary 1] which refers to connected graphs but this easily
generalizes to unions of such.

Then [3] introduces an algorithm that takes as input an LDPC matrix $M$ and
outputs a linear sized circuit $\Phi$ that is supposed encode $M$. They do so
by decomposing the matrix $M$ into submatrices that are encodable via their
initial construction (or a slight modification of it). We will show that this
decomposition fails. Doing so requires a few more definitions.

######  Definition 2.4 ((Pseudo) Encoding Stopping Set).

Let $V\subseteq[n]$ and $C\subseteq[m]$ be subsets of the columns and rows of
a matrix $M$. An Encoding Stopping Set (ESS) is a submatrix $M(C,V)$ such
that:

  1. 1.

For all $c\in C$,
$\left\\{v\left|\;\vphantom{vM(c,v)=1}\right.M(c,v)=1\right\\}\subseteq V$.
That is, all variables participating in this constraint are in $V$.

  2. 2.

For all $v\in V$ the Hamming weight of the $v$-th column is at least $2$ in
$M(C,V)$. That is, every variable in $v\in V$ participates in at least two
constraints in $C$.

  3. 3.

The set of rows corresponding to $C$ is linearly independent (in other words,
$M(C,[n])$ has rank $|C|$ over $\mathbb{F}_{2}$).

If items $1,2$ hold but item 3 does not, we call the submatrix a Pseudo
Encoding Stopping Set (or PESS).

######  Definition 2.5 (Pseudo-Tree).

A matrix is a Pseudo-Tree if it does not contain an ESS or a PESS.

Lu and Moura also require that the Pseudo-Tree is connected (as a graph), but
this requirement is not necessary for our purposes. Additionally, they define
Pseudo-Trees in different terms, but they show the equivalence to our
definition (see [3, Corollary 1]).

As mentioned, Pseudo-Trees are linear-time encodable via a greedy algorithm,
see [3, Lemma 1]. Lu and Moura observe that if an ESS is “almost” a Pseudo-
Tree, then it is linear-time encodable. By “almost” we mean that there is a
constant number of constraints whose removal yields a Pseudo-Tree. Thus, they
also give the following definition.

######  Definition 2.6 (k-fold-constraint (Pseudo) Encoding Stopping Set).

Let $M(C,V)$ be an (P)ESS. We say that $M(C,V)$ is a k-fold-constraint
Encoding Stopping Set if the following two conditions hold.

  1. 1.

There exists k constraints $c_{1},...,c_{k}\in C$ s.t.
$M(C\setminus\\{{c_{1},...,c_{k}}\\},V)$ does not contain any PESS or ESS.

  2. 2.

For any $k-1$ constraints $c_{1},...,c_{k-1}$,
$M(C\setminus\\{{c_{1},...,c_{k-1}}\\},V)$ contains a PESS or ESS.

Lu and Moura provide a linear time encoding algorithm for any $1$\- or
$2$-fold constraint (P)ESS [3, Algorithm 4].

###  2.1 Lu and Moura’s algorithms

We now present the two main algorithms used in Lu and Moura’s paper. We will
present a graph version as well as a matrix version for these algorithms. The
Algorithm (P)ESS-FINDER finds a PESS or a 1 or 2-fold-constraint ESS in a
given bipartite graph (see [3, Algorithm 5] for Lu and Moura’s version). The
second algorithm, DECOMPOSE utilizes the algorithm (P)ESS-FINDER to decompose
the given graph into linear-time encodable components (see [3, Algorithm 6]).

We give a more streamlined description of their algorithms. In particular, we
added the algorithm STRIP as a sub-procedure of (P)ESS-FINDER for easier
reference, and we omit the analysis from the description of the algorithms.

Algorithm (P)ESS-FINDER [3, Algorithm 5], Find a 1 or 2-fold-constraint
(P)ESS- graph language

Input: A Tanner graph $G=(V\cup C,E)$ with maximal variable degree 3.

  1. 1.

Initialize $H=(V_{H}\cup C_{H},E_{H})\leftarrow G$, $S\leftarrow\emptyset$.

  2. 2.

While $H\neq\emptyset$:

    1. (a)

Choose a lightest constraint $c\in C_{H}$. Add $c$ and its neighbours to $S$
and remove them from $H$.

    2. (b)

If $c$ doesn’t have any neighbours in $H$ and STRIP$(S)\neq\emptyset$ then
output STRIP$(S)$.

  3. 3.

Return $S$.

Algorithm STRIP Remove degree one variables

Input: Graph $S$.

  1. 1.

While there exists a degree $1$ bit node $x\in V_{S}$:

    1. (a)

Remove $x$ and its neighbours from $S$.

  2. 2.

Return $S$.

Algorithm (P)ESS-FINDER [3, Algorithm 5], Find a 1 or 2-fold-constraint
(P)ESS- matrix language

Input: An LDPC matrix $M\in\\{{0,1}\\}^{m\times n}$ with maximal column weight
3.

  1. 1.

Initialize $H\leftarrow{M},C\leftarrow\emptyset,V\leftarrow\emptyset$.

  2. 2.

While $C\neq[m]$ and $V\neq[n]$:

    1. (a)

Choose a lightest row $c$. Let $V_{c}$ be the indices of the corresponding
variables. Add $c$ to $C$ and $V_{c}$ to $V$ and zero the columns $V_{c}$ in
$H$.

    2. (b)

If $V_{c}=\emptyset$, and $STRIP(M(C,V))\neq\emptyset$ then output
$STRIP(M(C,V))$.

  3. 3.

Return $M(C,V)$.

The $STRIP$ procedure used in the matricial version of (P)ESS-FINDER is
equivalent to the one defined for graphs, namely we remove from $V$ any column
of weight one (and the corresponding row from $C$) and repeat.

Algorithm DECOMPOSE [3, Algorithm 6], Decompose a PC to ESS’s, PESS’s and
encodable components

Input: An LDPC matrix $M(C,V)$.

  1. 1.

Initialize $i\leftarrow 1$, $Components\leftarrow\emptyset$,
$M(C_{1},V_{1})\leftarrow\;\ref{alg: ess finder- graph}(M(C,V))$.

  2. 2.

While $M(C_{i},V_{i})\neq M(C,V)$:

    1. (a)

If $M(C_{i},V_{i})$ is a PESS:

      1. i.

Find $C^{\prime}\subseteq C_{i}$, such that $\sum_{c\in
C^{\prime}}c|_{V_{i}}=0\text{ (modulo 2)}$.

      2. ii.

Choose a constraint $c\in C^{\prime}$ and remove it from $C_{i}$.

      3. iii.

If $i>1$:

        1. A.

Remove $M(C_{i-1},V_{i-1})$ from $Components$.

        2. B.

Add the constraint $c^{*}=\sum_{c\in C^{\prime}}c\big{|}_{V_{i-1}}$ to
$C_{i-1}$.

        3. C.

Add $\ref{alg:decomposition}(M(C_{i-1},V_{i-1}))$ to $Components$.

    2. (b)

Add $M(C_{i},V_{i})$ to $Components$.

    3. (c)

$C\leftarrow C\setminus C_{i}$.

    4. (d)

$V\leftarrow V\setminus V_{i}$.

    5. (e)

$i\leftarrow i+1$.

    6. (f)

$M(C_{i},V_{i})\leftarrow\ref{alg:ess-finder}(M(C,V))$.

  3. 3.

Add $M(C,V)$ to $Components$.

  4. 4.

Output $Components$.

For the graph version of Algorithm DECOMPOSE we use the notation
$G(\tilde{U})$, to denote the subgraph of $G=(U,E)$ induced by
$\tilde{U}\subseteq U$.

Algorithm DECOMPOSE [3, Algorithm 6], Decompose a graph to ESS’s, PESS’s and
encodable components

Input: A Tanner graph $G=(V\cup C,E)$.

  1. 1.

Initialize $i\leftarrow 1$, $Components\leftarrow\emptyset$,
$G_{1}=G(V_{1}\cup C_{1})\leftarrow Algorithm\;\ref{alg: ess finder-
graph}(G)$.

  2. 2.

While $G_{i}\neq G(V\cup C)$:

    1. (a)

If $G_{i}$ is a PESS:

      1. i.

Find $C^{\prime}\subseteq C_{i}$, such that $\sum_{c\in
C^{\prime}}c|_{V_{i}}=0\text{ (modulo 2)}$.

      2. ii.

Choose a constraint variable $c\in C^{\prime}$ and remove it from $C_{i}$.

      3. iii.

If $i>1$:

        1. A.

Remove $G_{i-1}$ from $Components$.

        2. B.

Add the vertex $c^{*}=\sum_{c\in C^{\prime}}c\big{|}_{V_{i-1}}$ to $C_{i-1}$.

        3. C.

Add $\ref{alg:decomposition-graphs}(G_{i-1})$ to $Components$.

    2. (b)

Add $G_{i}$ to $Components$.

    3. (c)

$C\leftarrow C\setminus C_{i}$.

    4. (d)

$V\leftarrow V\setminus V_{i}$.

    5. (e)

$i\leftarrow i+1$.

    6. (f)

$G_{i}\leftarrow\ref{alg: ess finder- graph}(G(V\cup C))$

  3. 3.

Add $G$ to $Components$.

  4. 4.

Output $Components$.

##  3 The flaw in the paper

Before pointing to the error in [3] we provide an outline of their intended
encoding strategy.

  * •

Input: An LDPC matrix $M$ with kernel dimension $k$. It is assumed that each
column in $M$ has weight at most $3$, by adding variables, if needed.

  * •

Output: A linear-sized circuit $\Phi$ that implements $w\mapsto Gw$ for all
$w\in\\{0,1\\}^{k}$, for some matrix $G$ such that $ImG=KerM$.

The paper’s approach for constructing $\Phi$ from $M$ is based on a
decomposition algorithm, DECOMPOSE (see [3, Algorithm 6]) which generates a
list of “components” which are pseudo-trees and 1/2-fold-constraint Encoding
Stopping Sets using DECOMPOSE.

As mentioned earlier, [3] observe that each component, being a pseudo-tree or
a 1/2-fold-constraint ESS, admits linear time encoding via the label-and-
decide or label-and-decide-recompute algorithm in [3, Algorithms 2,3,4]. This
algorithm shows how to partition the bits into message bits and output bits so
that one can propagate the values from message bits to output bits, using the
constraints, in linear time.

The decompose algorithm outputs components together with an implicit labeling
of their input and output bits. Every component corresponds to a matrix in the
output of Algorithm DECOMPOSE. However, these can be described as a collection
of circuits and connections between them, as portrayed in Figure 2. More
precisely, the components can be described as a collection of circuits
$\Phi_{1},\Phi_{2},\dots,\Phi_{i}$ that can be composed into a circuit $\Phi$
that encodes the code, such that in this decomposition some of the input bits
of every $\Phi_{i}$ are connected to some of the output bits of
$\\{{\Phi_{j}:1\leq j<i}\\}$. Every circuit $\Phi_{i}$ is supposed to encode a
pseudo-tree or a $1$\- or $2$-fold (P)ESS, thus the matrices that are
outputted in Algorithm DECOMPOSE should be pseudo-trees or a $1$\- or $2$-fold
(P)ESSs.

Figure 2: The circuit $\Phi$.

### The Flaw

Unfortunately, it is not true that DECOMPOSE returns $1$\- or $2$-fold-
constraint (P)ESS’s and pseudo-Trees. In Step 2(a)ii, parallel to the third
line of the decomposition algorithm in [3, Algorithm 6], the authors claim
that if (P)ESS-FINDER outputs a PESS, then removing one constraint transforms
it to a Pseudo-Tree. In other words, [3] falsely assume that the only linear
dependency is the sum of all constraints and thus the removal of any single
constraint resolves the linear dependency. However, there could be multiple
linear dependencies on this same set of variables. The algorithm fails to take
these into consideration, thereby resulting in a code that has too many
codewords.

The main issue is that the constraints that we failed to add at step 2iiiB are
never taken into consideration, thereby resulting in a code that has too many
codewords.

In the next section we provide an example where DECOMPOSE encounters a PESS
which has a linear number of constraints that are ignored.

The first component output by the algorithm thus has a Kernel that is much
larger and contains many non-codewords.

##  4 A Counter Example

######  Theorem 4.1.

There exists a sequence of matrices $M_{n}\in\\{0,1\\}^{m\times n}$ with a
sequence of sub matrices $A_{n}$ that satisfy:

  1. 1.

There exists a valid set of choices for (P)ESS-FINDER such that $\ref{alg:ess-
finder}(M_{n})$ outputs $A_{n}$.

  2. 2.

$dim(Ker(M_{n}))\leq n/2+2$.

  3. 3.

$dim(Ker(A_{n}))\geq n/2+\Omega(n)$.

Let us assume that the encoding scheme suggested by [3] works. This implies
that the message bits of the code are a union of the message bits of the
components output by DECOMPOSE. That is, denoting by $k_{i}$ the number of new
input bits that enter the $i$-th component,

$dim(Ker(M))=\sum_{i\in[r]}k_{i}$ (1)

As the following corollary shows, this is not always true.

######  Corollary 4.2.

There exists a sequence of matrices $M_{n}\in\\{0,1\\}^{m\times n}$ and a
valid set of choices for $\ref{alg:decomposition}(M_{n})$ s.t.
$\sum_{i\in[r]}k_{i}>dim(Ker(M_{n}))$.

###### Proof of Corollary 4.2, assuming Theorem 4.1.

Assume towards contradiction that DECOMPOSE is correct on any input matrix
$M$.

We assume that DECOMPOSE and (P)ESS-FINDER goes through the constraints in
order. By inspection, we can see that the first component output is $A_{n}$
which is an ESS. After removing it from $M_{n}$, the algorithm continues to
decompose the remainder graph. In the next step, due to the structure of
$M_{n}$, the algorithm will find a PESS, and therefore add a a constraint to
$A_{n}$ resulting in $A^{\prime}_{n}$, and run DECOMPOSE on $A^{\prime}_{n}$.

The output of this step is a list of components
$M^{\prime}_{1},\ldots,M^{\prime}_{t}$, such that, assuming that DECOMPOSE is
correct and (1) holds,
$\sum_{j=1}^{t}k_{j}=\dim(KerA^{\prime}_{n})\geq\dim(Ker(A_{n}))-1$.

However, by item 2 of Theorem 4.1 $n/2+2\geq dim(Ker(M_{n}))$, while item 3 of
Theorem 4.1 assures that $dim(Ker(A_{n}))\geq n/2+\Omega(n)$. Combining the
above and invoking (1) once more,

$n/2+2\geq dim(Ker(M_{n}))\geq dim(Ker(A^{\prime}_{n}))\geq
dim(Ker(A_{n}))-1\geq n/2+\Omega(n),$

and this leads to a contradiction to the correctness of DECOMPOSE.

∎

The proof of Theorem 4.1 will follow from the description of the
counterexample, along with some necessary properties. Our counter-example has
column weight 3 and row weight 6. There are $n$ columns and $m$ rows
($m=n/2$), where $n=11N+7$ for any odd integer $N$. The counter-example
$M_{n}\in\\{0,1\\}^{m\times n}$ is

$M_{n}=\left[\begin{array}[]{c|c}A_{n}&0\\\ \hline\cr
B_{n}&I_{\frac{N+1}{2}}\otimes\mathbf{1}_{3\times 2}\\\ \end{array}\right]$

where $\otimes$ stands for the Kronecker product, see Definition 2.1, and we
now detail the matrices $A_{n},B_{n}$.

#### The matrix $A_{n}$.

We will now describe $A_{n}\in\\{0,1\\}^{(4N+2)\times(10N+6)}$. Towards this
we shall decompose $A_{n}=S_{n}+D_{n}$ ($S$ stands for “stairs” and $D$ for
“diagonals”) and describe these two components separately. $S_{n}$ is the
matrix described by blocks in Figure 3, where:

  1. 1.

$\forall d\in[4]$, $T_{d}=I_{N}\otimes\mathbbm{1}_{d}$ where
$\mathbbm{1}_{d}=(1,1...,1)$ $d$-times.

  2. 2.

The first row of $S_{n}$ is all zero except for six 1’s at columns 1 to 6
$(1,1,1,1,1,1,0,0,...)$.

#### The matrix $D_{n}$.

The matrix $D_{n}\in\\{0,1\\}^{(4N+2)\times(10N+6)}$ is described by blocks in
Figure 4. The first column has a single 1 at the second entry, then there’s a
square block of height and width $4N+1$, with $1$’s on its main diagonal and
on the lower sub-diagonal. Afterwards come three identity matrices of
dimensions $3N+1,2N+1$ and $N+1$. The last column has a single 1 at the last
entry (which could be thought of as an identity matrix of dimension $1$). All
other entries of $D_{n}$ are $0$.

Figure 3: $S_{n}$. Recall that $T_{d}=I_{N}\otimes\mathbbm{1}_{d}$. Figure 4:
$D_{n}$. Recall that $A_{n}=S_{n}+D_{n}$.

We show a formula for $A_{n}$.

######  Claim 4.3.

$A_{n}(i,j)=1$ in the following cases:

$\begin{cases}j\in[6]&i=1\\\
j\in\\{{i-1,i}\\}\cup\\{{4i-1,...,4i+2}\\}&i\in[2,N+1]\\\
j\in\\{{i-1,i}\\}\cup\\{{i+3N+1}\\}\cup\\{{3i+N+1,...,3i+N+3}\\}&i\in[N+2,2N+1]\\\
j\in\\{{i-1,i}\\}\cup\\{{i+3N+1}\\}\cup\\{{i+5N+2}\\}\cup\\{{2i+3N+3,2i+3N+4}\\}&i\in[2N+2,3N+1]\\\
j\in\\{{i-1,i}\\}\cup\\{{i+3N+1}\\}\cup\\{{i+5N+2}\\}\cup\\{{i+6N+3}\\}\cup\\{{i+6N+5}\\}&i\in[3N+2,4N+1]\\\
j\in\\{{i-1,i}\\}\cup\\{{i+3N+1}\\}\cup\\{{i+5N+2}\\}\cup\\{{i+6N+3}\\}\cup\\{{10N+6}\\}&i=4N+2\\\
\end{cases}.$ (2)

###### Proof of Claim 4.3.

Observe that $T_{d}(i,j)=1$ if $i=\lceil\frac{j}{d}\rceil$, i.e.
$j\in\\{{(i-1)d+1,...,id}\\}$. The $T_{d}$ matrix in $S_{n}$ begins with a
column offset of $6+N\sum_{k=d+1}^{4}k$, and a row offset of $1+(4-d)N$. For
example, $T_{4}$ is shifted by six columns and one row, and therefore, in the
rows corresponding to $T_{4}$, $S_{n}(i,j)=1$ iff
$j-6\in\\{(i-1-1)4+1,...,(i-1)4\\}$. By calculating the shifts on
$T_{3},T_{2}$ and $T_{1}$ and rearranging we get the algebraic definition of
$S_{n}$:

$S_{n}(i,j)=1\iff\begin{cases}j\in[6]&i=1\\\
j\in\\{{4i-1,...,4i+2}\\}&i\in[2,N+1]\\\
j\in\\{{3i+N+1,...,3i+N+3}\\}&i\in[N+2,2N+1]\\\
j=\\{{2i+3N+3,2i+3N+4}\\}&i\in[2N+2,3N+1]\\\
j=i+6N+3&i\in[3N+2,4N+1]\end{cases}.$ (3)

The matrix $D_{n}$ consists of six diagonals (considering the bottom right
entry as a length 1 diagonal).

  * •

The first diagonal consists of the entries $(i,j)$ satisfying $j=i-1$.

  * •

The second diagonal has entries $(i,j)$ where $j=i$ and $i\geq 2$.

  * •

The third diagonal starts at the $(N+2,4N+3)$-entry and includes all indices
$(N+2+t,4N+3+t)$ (for $t\in\\{0,...3N\\}$). In other words, it contains all
$(i,j)$ s.t. $j=4N+3+t=i+3N+1$ (and $i\in\\{N+2,...,4N+2\\}$).

  * •

The other diagonals are similarly calculated from Figure 4.

Putting together these six diagonals with the formula for $S_{n}$ yields the
full formula for $A_{n}$ (Equation 2). ∎

We denote by $j_{t}$ the leading entry index of the $t$-th row in $S_{n}$. One
may verify the following formula:

$j_{t}=d_{t}t+\frac{(5-d_{t})(4-d_{t})}{2}N+7-2d_{t}$ (4)

for $d_{t}=5-\lceil\frac{t-1}{N}\rceil$ (i.e. $d_{t}$ is the step ”width” of
row $t$, and row $t$ belongs to the rows corresponding to $T_{d_{t}}$ in
$S_{n}$).

#### The matrix $B_{n}$.

The matrix $B_{n}\in\\{0,1\\}^{\frac{3}{2}(N+1)\times(10N+6)}$ is depicted in
Figure 5. Note that the first identity matrix in $B_{n}$ is placed on the
second row, while the rest of the identity matrices begin at the first row.

It is easy to observe that $B_{n}(i,j)=1$ in the following cases:

$\begin{cases}j\in\\{{1,\frac{1}{2}(11N+5),7N+4,\frac{1}{2}(17N+11)}\\}&i=1\\\
j\in\\{{4N+i,\frac{1}{2}(11N+3)+i,7N+3+i,\frac{1}{2}(17N+9)+i}\\}&i\in[2,\frac{3}{2}(N+1)]\end{cases}.$
(5)

Figure 5: $B_{n}$

The bottom right block of $M_{n}$ was defined as
$I_{\frac{N+1}{2}}\otimes\mathbf{1}_{3\times 2}$ but could actually be any
$\frac{3}{2}(N+1)\times(N+1)$ matrix as long as it has row regularity 2 and
column regularity 3. $M_{18}$ is small enough to sketch (see Figure 1).

Before analyzing the counterexample we only need to confirm that all columns
of $M_{n}$ have weight $3$, and that all rows have weight $6$ as claimed.

######  Claim 4.4.

Every row in $M_{n}$ has weight $6$, and every column weight $3$.

###### Proof of Claim 4.4.

Clearly every row in $A_{n}$ has 6 ones (this can be verifies by looking at
Equation 2). Every row in $B_{n}$ has 4 ones (as indicated in Equation 5), and
the selection of the bottom right matrix is made to ensure that the weight of
these rows is completed to 6.

Let us verify that every column has $3$ ones. The $N+1$ rightmost columns
(corresponding to the bottom left block) clearly have $3$ ones, so we only
need to show that the columns of $\begin{bmatrix}A_{n}\\\ B_{n}\end{bmatrix}$
each have $3$ ones. The diagonal $i$ starts at column 2 and continues to
column $4N+2$, the diagonal $i+3N+1$ starts at columns $4N+3$ and ends a
column before the diagonal $i+5N+2$ starts. Together with the diagonal
$i+6N+3$ and entry $A_{n}(4N+2,10N+6)$ the columns 2 to 10N+6 have another
”layer” of $1$’s. The diagonal $i-1$ ”covers” columns 1 to 4N+1, so in total,
using Claim 4.3, columns $[2,4N+1]$ have weight 3, while columns
${1}\cup[4N+2,10N+6]$ have weight 2. The weight of these columns is completed
to 3 by the columns of $B_{n}$, which can be easily verified by its
definition. ∎

We move on to prove Theorem 4.1.

###  4.1 Proof of theorem 4.1

For the reader’s convenience we restate the theorem.

######  Theorem 4.1 (Restated).

There exists a sequence of matrices $M_{n}\in\\{0,1\\}^{m\times n}$ that
satisfies:

  1. 1.

There exists a valid set of choices for (P)ESS-FINDER such that $\ref{alg:ess-
finder}(M_{n})$ outputs $A_{n}$.

  2. 2.

$dim(Ker(M_{n}))\leq n/2+2$.

  3. 3.

$dim(Ker(A_{n}))\geq n/2+\Omega(n)$.

###### Proof.

  1. 1.

For item 1 we use the following lemma (see proof).

######  Lemma 4.5.

For $t=1,2,...,4N+1$, choosing row $t$ at iteration $t$ is a valid choice for
Algorithm (P)ESS-FINDER($M_{n}$).

Assuming (P)ESS-FINDER makes these choices, then after iteration $4N+1$ all
the columns with 1’s in those rows are zeroed out, yielding the matrix

$\tilde{M}_{n}=\left[\begin{array}[]{c|c}0_{(4N+2)\times(10N+6)}&0_{(4N+2)\times(N+1)}\\\
\hline\cr\\\
0_{\frac{3}{2}(N+1)\times(10N+6)}&I_{\frac{N+1}{2}}\otimes\mathbf{1}_{3\times
2}\\\ \end{array}\right]$

So at iteration $4N+2$, row $4N+2$ (the last row of $A_{n}$) will certainly be
chosen since it would have weight 0, while all rows $>4N+2$ (rows
corresponding to $B_{n}$) will have weight 2. According to step 2b of
Algorithm (P)ESS-FINDER this leads to the call $STRIP(A_{n})$ which returns
$A_{n}$ since all columns of $A_{n}$ have weight of at least 2. Hence,
Algorithm (P)ESS-FINDER halts and outputs $A_{n}$.

  2. 2.

The removal of rows $1$ and $4N+3$ from $M_{n}$ (corresponding to the first
row of $A_{n}=D_{n}+S_{n}$ and the first row of $B_{n}$) yields an ($m-2$)-row
matrix that has a “staircase form”, so $Rank(M_{n})\geq m-2$. This can be seen
by looking at $D_{n}$ (Figure 4) and at $B_{n}$ (Figure 5). The first diagonal
in $D_{n}$ continues into $B_{n}$’s first identity matrix. We conclude that
$dim(Ker(M_{n}))=n-Rank(M_{n})\leq n-(m-2)=n/2+2$.

  3. 3.

$A_{n}$ has $10N+6$ columns and $4N+2$ rows, therefore

$dim(Ker(A_{n}))=10N+6-Rank(A_{n})\geq
6N+4\overset{(n=11N+7)}{=}n/2+\Omega(n)\gg n/2$

∎

###### Proof of Lemma 4.5.

Let us introduce the following notation. For any $i\in[m],j\in[n]$,

$wt(i,j):=\sum_{k=j}^{n}M_{n}(i,k)$

This is the Hamming weight of row $i$ restricted to entries $j,\ldots,n$.

Recall that $j_{t}$ is the leading entry index of the $t$-th row in $S_{n}$.
For example, in Figure 6 we highlight the entry $S_{n}(3,j_{3})$.

Figure 6: $S_{n}(3,j_{3})$ highlighted

Assume by induction that rows $1,..,t-1$ were chosen in iterations $1,..,t-1$
of Algorithm (P)ESS-FINDER($M_{n}$) for some $t\in\\{2,...,4N+1\\}$. Then
columns $\\{{1,...,j_{t}-1}\\}$ were zeroed-out in those iterations since for
every $t$, the submatrix $M_{n}(\\{{1,...,t-1}\\},\\{{1,...,j_{t}-1}\\})$ has
at least one non-zero entry at every column. This can be seen by recalling
that the top left block of $M_{n}$ is $A_{n}=D_{n}+S_{n}$ and by noting that
every column in $S_{n}(\\{{1,...,t-1}\\},\\{{1,...,j_{t}-1}\\})$ has at least
one non-zero entry (for illustration look at Figure 6). Moreover, the
submatrix $M_{n}(\\{{1,...,t-1}\\},\\{{j_{t},...,n}\\})$ is the zero matrix,
so no other columns were zeroed out in previous steps. To verify this claim,
observe that by Claim 4.3, the last non-zero entry for every row
$i\in\\{1,...,4N+1\\}$ comes from $S_{n}$, and that
$S_{n}(\\{1,...,t-1\\},\\{j_{t},...,n\\})$ is the zero matrix (see again
Figure 6 for illustration).

To complete the proof we need to show that for all $i>t$,

$wt(t,j_{t})\leq wt(i,j_{t}),$ (6)

meaning that row $t$ is a valid choice for the algorithm at iteration
$t\in[4N+1]$.

If $t=4N+2$ then $wt(t,j_{t})=0$ so (6) clearly holds, so assume that
$t<4N+2$. We prove (6) by analyzing separately the rows $i\leq 4N+2$
(corresponding to $A_{n}$) and the rows $i>4N+2$ (corresponding to $B_{n}$).

We begin with $i\leq 4N+2$. Recall that $d_{t}$ is the number of ones in a row
in a the block $T_{d}$ in $D_{n}$, such that $t$ is in that block. If $t$ is
the last row of a block $T_{d}$, i.e. $t\in\\{{N+1,2N+1,3N+1,4N+1}\\}$, then
$wt(t,j_{t})=d_{t}=wt(i,j_{t})$ for every row $i\in(t,4N+2]$. Let us
demonstrate this by example. The row $t=N+1$ has non-zeros only coming from
$S_{n}$ (and not $D_{n}$). These are four non-zeros coming from $T_{4}$ so
$wt(t,j_{t})=4$. Rows $i\in[N+2,2N+1]$ have ones from both $S_{n}$ and
$D_{n}$. In $S_{n}$, they get three $1$’s from $T_{3}$. An additional $1$
comes from the second identity component in $D_{n}$. The remaining cases are
similar and easy to verify.

For $t\notin\\{{N+1,2N+1,3N+1,4N+1}\\}$, let $t^{\prime}$ denote the last row
in the block of $t$, namely, $d_{t^{\prime}}=d_{t}$ and for every
$i>t^{\prime}$, $d_{i}<d_{t}$. For all $i\in(t,t^{\prime}]$, $wt(i,j_{t})\geq
d_{t}=wt(t,j_{t})$. For all $i\in(t^{\prime},4N+2]$, $wt(i,j_{t})\geq d_{t}$
since $wt(i,j_{t})\geq wt(i,j_{t^{\prime}})=d_{t}$, thus proving the first
item.

Thus far we showed that at iterations $t\in[4N+1]$, row $t$ was not heavier
than any of the rows $i\in(t,4N+2]$ (the rows below $t$ in $A_{n}$). Now we
prove that the first row in $B_{n}$ is the lightest among all rows of $B_{n}$,
that is, $wt(4N+3,j_{t})\leq wt(i,j_{t})$ for any $i\geq 4N+3$. we denote by
$i^{\prime}=i-4N-2$ the index of row $i$ relative to $B_{n}$. The value
$wt(4N+3,j)$ decreases at columns
$j\in\\{{1,\frac{1}{2}(11N+3)+1,7N+4,\frac{1}{2}(17N+9)+1}\\}$ while the value
$wt(i,j)$, decreases at
$j\in\\{{4N+i^{\prime},\frac{1}{2}(11N+3)+i^{\prime},7N+3+i^{\prime},\frac{1}{2}(17N+9)+i^{\prime}}\\}$
for all $i>4N+3$. Thus concluding that $wt(4N+3,j_{t})\leq wt(i,j_{t})$ for
all $i>4N+3$ and all $t$.

At last we show that at iterations $t\in[4N+1]$, row $t$ of $A_{n}$ is no
heavier than the first row of $B_{n}$ (i.e. $wt(t,j_{t})\leq wt(4N+3,j_{t})$).
This is also a case analysis:

  * •

At row $t=1$, $wt(1,1)=wt(4N+3,1)=6$.

  * •

For $t\in[2,N+1]$, we prove that $wt(4N+3,j_{t})\geq 4=wt(t,j_{t})$:

The rows $t\in[2,N+1]$ correspond to the block $T_{4}$ in $S_{n}$, therefore
$wt(t,j_{t})=4$. By the definition of $S_{n}$ (Equation 3), when
$t\in[2,N+1]$, then $j_{t}=4t-1$, i.e. $j_{t}\in[7,4N+3]$. By the definition
of $B_{n}$ (Equation 5), the first row has weight of at least 2 for all $j\leq
7N+4$. Adding weight 2 from the block
$I_{\frac{N+1}{2}}\otimes\mathbf{1}_{3\times 2}$ we get that $wt(4N+3,j)\geq
4$ for all $j\in[7,4N+3]$.

  * •

Similarly we can show that in rows $t\in[N+2,2N+1]$, $wt(4N+3,j_{t})\geq
3=wt(t,j_{t})$. These rows correspond to the block $T_{3}$ in $S_{n}$,
therefore $wt(t,j_{t})=3$ and $j_{t}\in[4N+7,7N+4]$, while for all
$j\leq\frac{1}{2}(17N+11)$, $wt(4N+3,j)\geq 3$.

  * •

In rows $t\in[2N+2,4N+1]$, $wt(4N+3,j_{t})\geq 2\geq wt(t,j_{t})$. For all
columns corresponding to $A_{n}$ ($j\in[10N+6]$), $wt(4N+3,j)\geq 2$ since the
first row of the block $I_{\frac{N+1}{2}}\otimes\mathbf{1}_{3\times 2}$
contributes 2 to the weight of row $4N+3$. Rows $t\in[2N+2,4N+1]$ correspond
to the blocks $T_{2}$ and $T_{1}$ in $S_{n}$ and therefore
$wt(t,j_{t})\in\\{1,2\\}$.

∎

##  5 The typical case

We would like to emphasize that although our example may seem like a carefully
constructed counterexample, it seems that a random low density matrix will
fail as well. In [4] the authors analyze the expected behavior of similar
algorithms on random matrices, and conclude that none of them yield sub-
quadratic encoding complexity. The nature of their analysis is heuristic and
therefore cannot hold as a formal proof. Nevertheless, their results are
backed with experimentation, so they are likely to have a holding in reality.
Our experiments show that a random matrix will have a first component with too
many message bits, with very high probability111The probability depends on the
row and column weight distributions. The observation applies for example to
(3,6)-regular matrices that are large enough (say $n>200$)..

##  6 Running Algorithm DECOMPOSE on $M_{18}$

As a warm up, let us run Algorithm DECOMPOSE on $M_{18}$ depicted in Figure 1.
There are many choices made by this algorithm, so we will show a sequence of
choices that result in an output of components that do not describe the code
$Ker(M_{18})$.

  1. 1.

Let $M=M_{18}$. The first time the Algorithm DECOMPOSE is called as a
subroutine, it is called on $M$ and returns $A_{18}=M([6],[16])$, the first
six rows in $M$:

    1. (a)

This is because for iterations $i=1,2,\dots,6$ of Algorithm DECOMPOSE, the
$i$-th row of $M$ is a lightest row.

    2. (b)

After selecting these rows, in the sixth iteration $V_{c}=\emptyset$ so after
running step $2(b)$, the STRIP procedure returns $A_{18}$ which Algorithm
DECOMPOSE outputs.

This matrix has full rank so it is not a PESS.

  2. 2.

The second time Algorithm DECOMPOSE is called as a subroutine, it is called on
$M(\\{{7,8,9}\\},\\{{17,18}\\})$ (the grey part of Figure 1). One observes
that $M(\\{{7,9}\\},\\{{17,18}\\})$ is a valid output in this step.

  3. 3.

$M(\\{{7,9}\\},\\{{17,18}\\})$ is a PESS, so we remove one row (say, the
$7$-th row) and recursively run Algorithm DECOMPOSE on the matrix whose rows
are those of $A_{18}$ plus the row $c_{7}+c_{9}$ (the sum of the seventh and
ninth rows of $M_{18}$). Assuming DECOMPOSE works properly, the components it
returns when called on $A_{18}$ with the new row, will have at least 9 input
bits, since there are 16 variables and 7 constraints. However, the residual
matrix $M(\\{8,9\\},\\{17,18\\})$ has rank 1, so it also has an input bit. In
total, the output components will have at least 10 input bits, while $M_{18}$
has only 9 (it has full rank). We conclude that the output components of
$\ref{alg:decomposition}(M_{18})$ do not describe the code $Ker(M_{18})$.

## References

  * [1] Changyan Di, Tom Richardson, and Rüdiger Urbanke.  Weight distribution of low-density parity-check codes.  Information Theory, IEEE Transactions on, 52:4839 – 4855, 12 2006\.
  * [2] R. Gallager.  Low-density parity-check codes.  IRE Transactions on Information Theory, 8(1):21–28, 1962.
  * [3] Jin Lu and José M. F. Moura.  Linear time encoding of LDPC codes.  IEEE Transactions on Information Theory, 56(1):233–249, 2010.
  * [4] T.J. Richardson and R.L. Urbanke.  Efficient encoding of low-density parity-check codes.  IEEE Transactions on Information Theory, 47(2):638–656, 2001.
  * [5] M. Sipser and D.A. Spielman.  Expander codes.  IEEE Transactions on Information Theory, 42(6):1710–1722, 1996\.
  * [6] D.A. Spielman.  Linear-time encodable and decodable error-correcting codes.  IEEE Transactions on Information Theory, 42(6):1723–1731, 1996\.


# The Index of $\mathbb{T}_{2}^{\operatorname{an}}$ inside $\mathbb{T}_{2}$

Noah Taylor111The author is supported in part by NSF Grant DMS-$1701703$.

(February 28, 2021)

##  1 Introduction

Let $N$ be a prime number and let $S_{2}(\Gamma_{0}(N),\mathbb{Z})$ denote the
modular forms of weight $2$ and level $\Gamma_{0}(N)$ with integer
coefficients, and for any other ring $R$, we denote
$S_{2}(\Gamma_{0}(N),R)=S_{2}(\Gamma_{0}(N),\mathbb{Z})\otimes R$. If $R$ is a
characteristic $p$ ring, we define $S_{2}(\Gamma_{0}(N),R)^{\text{Katz}}$ to
be the $R$-module of Katz forms as defined in [Kat73, Section 1.2], and define
similar notation for the spaces of weight $1$ forms. For $N\nmid n$, let
$T_{n}$ denote the $n$th Hecke operator inside
$\operatorname{End}(S_{2}(\Gamma_{0}(N),\overline{\mathbb{Z}}))$, and let
$U_{N}$ denote the $N$th Hecke operator. We let
$\mathbb{T}^{\operatorname{an}}$ denote $\mathbb{Z}[T_{3},T_{5},\ldots]$, the
algebra generated by $T_{n}$ for $(2N,n)=1$, and we denote
$\mathbb{T}^{\operatorname{an}}[T_{2},U_{N}]$ by $\mathbb{T}$. The goal of
this paper is to compute the index of $\mathbb{T}^{\operatorname{an}}$ inside
$\mathbb{T}$. Specifically, we prove the following theorem in sections 3 and
4:

######  Theorem 1.1.

The quotient $\mathbb{T}/\mathbb{T}^{\operatorname{an}}$ is purely
$2$-torsion, and

$\dim_{\mathbb{F}_{2}}\mathbb{T}/\mathbb{T}^{\operatorname{an}}=\dim_{\mathbb{F}_{2}}S_{1}(\Gamma_{0}(N),\mathbb{F}_{2})^{\operatorname{Katz}}.$

In other words, if
$c=\dim_{\mathbb{F}_{2}}S_{1}(\Gamma_{0}(N),\mathbb{F}_{2})^{\operatorname{Katz}}$
is the dimension of the weight $1$ level $\Gamma_{0}(N)$ Katz forms over
$\mathbb{F}_{2}$, then the index of $\mathbb{T}^{\operatorname{an}}$ in
$\mathbb{T}$ is equal to $2^{c}$.

The setup of the paper is as follows. In section 2, we introduce some facts
from the literature about modular forms and establish a duality theorem
between modular forms and Hecke algebras. In section 3 we prove the first half
of the theorem, that $\mathbb{T}^{\operatorname{an}}$ contains $2\mathbb{T}$
as submodules of $\mathbb{T}$, so the quotient
$\mathbb{T}/\mathbb{T}^{\operatorname{an}}$ is purely $2$-torsion. Then in
section 4 we use a theorem of Katz to relate the extra elements of
$\mathbb{T}$ to weight $1$ modular forms using the duality, and finally
establish the equality of Theorem 1.1 between dimensions. In section 5 we
conclude with some examples, and some theorems and conjectures we propose
based on the work of Cohen-Lenstra and Bhargava.

##  2 Preliminaries

###  2.1 From $\mathbb{Z}$ to $\mathbb{Z}_{2}$

We start by proving that $U_{N}\in\mathbb{T}^{\operatorname{an}}$, thereby
reducing our work to considering
$\mathbb{T}^{\operatorname{an}}\subseteq\mathbb{T}^{\operatorname{an}}[T_{2}]$.

######  Theorem 2.1.

$U_{N}\in\mathbb{T}^{\operatorname{an}}$.

###### Proof.

It is enough to check that
$U_{N}\in\mathbb{T}^{\operatorname{an}}\otimes\mathbb{Z}_{p}$ for every $p$:
if $\mathbb{T}^{\operatorname{an}}$ and
$\mathbb{T}^{\operatorname{an}}[U_{N}]$ have different ranks as
$\mathbb{Z}$-modules, then the $\mathbb{Z}_{p}$-ranks of
$\mathbb{T}^{\operatorname{an}}\otimes\mathbb{Z}_{p}$ and
$\mathbb{T}^{\operatorname{an}}[U_{N}]\otimes\mathbb{Z}_{p}=\mathbb{T}^{\operatorname{an}}\otimes\mathbb{Z}_{p}[U_{N}]$
are also different for every $p$, contradiction. On the other hand, if
$\text{rank}(\mathbb{T}^{\operatorname{an}})=\text{rank}(\mathbb{T}^{\operatorname{an}}[U_{N}])$,
then the quotient
$\mathbb{T}^{\operatorname{an}}[U_{N}]/\mathbb{T}^{\operatorname{an}}$ is
finite. If it’s nontrivial, then for any prime $p$ dividing its order, there
is a surjective map
$(\mathbb{T}^{\operatorname{an}}[U_{N}]\otimes\mathbb{Z}_{p})/(\mathbb{T}^{\operatorname{an}}\otimes\mathbb{Z}_{p})\twoheadrightarrow(\mathbb{T}^{\operatorname{an}}[U_{N}]/\mathbb{T}^{\operatorname{an}})\otimes\mathbb{Z}_{p}$
with nontrivial image. So for this $p$,
$\mathbb{T}^{\operatorname{an}}[U_{N}]\otimes\mathbb{Z}_{p}\neq\mathbb{T}^{\operatorname{an}}\otimes\mathbb{Z}_{p}$.
Therefore, we will only check whether
$\mathbb{T}^{\operatorname{an}}\otimes\mathbb{Z}_{p}$ contains $U_{N}$.
Further, as $\mathbb{T}^{\operatorname{an}}\otimes\mathbb{Z}_{p}$ is a
complete semi-local ring, it splits as a direct sum of its completions at
maximal ideals, so it’s further enough to check that $U_{N}$ is in
$\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$ for the completion
$\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$ at each maximal ideal
$\mathfrak{m}$.

In a previous paper, we proved that
$U_{N}\in\mathbb{T}^{\operatorname{an}}\otimes\mathbb{Z}_{2}=\mathbb{T}^{\operatorname{an}}_{2}$
[Tay20, Lemma 5.1], so the statement is true for all maximal ideals over $2$.
So let $\ell$ be an odd prime, $\mathfrak{m}$ be a maximal ideal of
$\mathbb{T}^{\operatorname{an}}$ over $\ell$, and $\mathfrak{a}$ be a maximal
ideal of $\mathbb{T}$ containing $\mathfrak{m}$.

Let $\mathbb{T}_{\mathfrak{a}}$ be the completion of $\mathbb{T}$ with respect
to $\mathfrak{a}$, and let $A$ be the integral closure of
$\mathbb{T}_{\mathfrak{a}}$ over $\mathbb{Z}_{\ell}$, which can be written as
$A=\displaystyle\oplus_{i}\mathcal{O}_{i}$ for $\mathcal{O}_{i}$ finite
extensions of $\mathbb{Z}_{\ell}$. The maps

$\pi_{i}:\mathbb{T}\rightarrow\mathbb{T}_{\mathfrak{a}}\rightarrow
A\rightarrow\mathcal{O}_{i}$

produce conjugacy classes of eigenforms with coefficients in
$\mathcal{O}_{i}$, with the coefficient $a_{i,j}$ of $q^{j}$ equal to
$\pi_{i}(T_{j})$ if $(j,N)=1$, or $\pi_{i}(U_{j})$ if $N|j$. These are
newforms as $N$ is prime, and there are no weight $2$ level $1$ forms. By
Eichler-Deligne-Shimura-Serre there are representations
$\rho_{i}:G_{\mathbb{Q}}\rightarrow\operatorname{GL}_{2}(\mathcal{O}_{i})$,
unramified away from $\ell N$, so that
$\operatorname{Tr}(\rho_{i}(\operatorname{Frob}_{\ell}))=a_{i,p}$ for all
primes $p\nmid\ell N$.

[DDT97, Theorem 3.1(e)] describes the shape of the local-at-$N$
representation:

$\rho_{i}|_{G_{\mathbb{Q}_{N}}}=\begin{pmatrix}\epsilon\chi&*\\\
0&\chi\end{pmatrix}$

where $\chi$ is the unramified representation taking $\operatorname{Frob}_{N}$
to $a_{i,N}$ and $\epsilon$ is the $N$-adic cyclotomic character.
Additionally, $\det\rho_{i}=\epsilon$, so $\chi^{2}$ is identically $1$ and
$a_{i,N}$ is equal to $1$ or $-1$ for each $i$. We show that $a_{i,N}$ is
equal among all $i$ over all $\mathfrak{a}$ containing $\mathfrak{m}$, so that
the image of $U_{N}$ in $\mathbb{T}_{\mathfrak{a}}$ is constantly $1$ or $-1$
over all $\mathfrak{a}$, and hence, in
$\mathbb{T}_{\mathfrak{m}}=\oplus_{\mathfrak{m}\subseteq\mathfrak{a}}\mathbb{T}_{\mathfrak{a}}$,
is inside $\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$.

By the Chebotarev density theorem, a representation is determined up to
semisimplification and conjugation by its trace on the Frobenius elements of
unramified primes. The $\rho_{i}(\operatorname{Frob}_{p})$ have trace equal to
$a_{i,p}$, which is the image of $T_{p}$ under $\pi_{i}$. Because
$\mathfrak{m}$ is contained in $\mathfrak{a}$ for all $\mathfrak{a}$, the
image of $T_{p}$ under reduction of
$\mathbb{T}^{\operatorname{an}}\bmod\mathfrak{m}$ is the same as the reduction
of $a_{i,p}\bmod\mathfrak{a}$. Therefore, the semisimplifications of the
reductions of $\rho_{i}$ over all $i$ and all $\mathfrak{a}$ are all
isomorphic. But we can deduce the value of $a_{i,N}$ from the reduction of
$\rho_{i}\bmod\mathfrak{a}$, because $\rho_{i}|_{G_{\mathbb{Q}_{N}}}$ has an
unramified quotient and a ramified subspace, and the same is true for the
reduction $\bmod\mathfrak{a}$ as $\ell\neq 2$. So the image of the Frobenius
on the unramified quotient is either $1$ or $-1$ for one (and hence every)
$\rho_{i}$, and therefore $a_{i,N}$ does not depend on $i$ or $\mathfrak{a}$,
only on $\mathfrak{m}$. So $U_{N}$ lies in
$\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$ for all $\mathfrak{m}$, and
we’re done.∎

We can now reduce from forms over $\overline{\mathbb{Z}}$ to forms over
$\overline{\mathbb{Z}}_{2}$. To do this, we first recall [Wil95, Lemma, pp.
491] which says that if $\mathbb{T}^{1}$ is the Hecke algebra over
$\mathbb{Z}$ corresponding to level $\Gamma_{1}(N)$ forms and $\mathbb{T}^{2}$
is the subalgebra of operators relatively prime to $2$, that $\mathbb{T}^{2}$
has $2$-power index in $\mathbb{T}^{1}$. As the algebras $\mathbb{T}$ and
$\mathbb{T}^{\operatorname{an}}=\mathbb{T}^{\operatorname{an}}[U_{N}]$ are
quotients of $\mathbb{T}^{1}$ and $\mathbb{T}^{2}$ of this lemma, the same is
true for $\mathbb{T}$ and $\mathbb{T}^{\operatorname{an}}$. (Alternatively,
with a similar argument to the proof of Theorem 2.1, we can check that $T_{2}$
is contained in all completions at maximal ideals of
$\mathbb{T}^{\operatorname{an}}\left[\frac{1}{2}\right]$. This is true as $2$
is unramified in, and $T_{2}$ is a trace of, the modular representations over
primes other than $2$, so Chebotarev and completeness of
$\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$ show that
$T_{2}\in\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$.) So we can calculate
the index of $\mathbb{T}^{\operatorname{an}}\otimes\mathbb{Z}_{2}$ inside
$\mathbb{T}\otimes\mathbb{Z}_{2}$, and by abuse of notation begin to call
these $\mathbb{T}^{\operatorname{an}}$ and $\mathbb{T}$ instead. We know that
$\mathbb{T}$ and $\mathbb{T}^{\operatorname{an}}$ are semi-local rings, and as
such, they can be written as a direct sum of their completions:

$\mathbb{T}=\bigoplus_{\mathfrak{a}\subset\mathbb{T}}\mathbb{T}_{\mathfrak{a}},\qquad\text{and}\qquad\mathbb{T}^{\operatorname{an}}=\bigoplus_{\mathfrak{m}\subset\mathbb{T}^{\operatorname{an}}}\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}.$

Additionally, because the $\mathbb{Z}_{2}$-ranks of $\mathbb{T}$ and
$\mathbb{T}^{\operatorname{an}}$ are equal,
$T_{2}\in\mathbb{T}\otimes\mathbb{Q}_{2}=\mathbb{T}^{\operatorname{an}}\otimes\mathbb{Q}_{2}=\mathbb{T}^{\operatorname{an}}\left[\frac{1}{2}\right]$,
and hence maps $\mathbb{T}^{\operatorname{an}}\rightarrow K$ where $K$ is a
finite extension of $\mathbb{Q}_{2}$ can be uniquely extended to maps
$\mathbb{T}\rightarrow K$. This means that modular forms are rigid in
characteristic $0$: we can determine the image of $T_{2}$ from the image of
the remaining operators, and hence from any modular representation
$\rho_{f}:G_{\mathbb{Q}}\rightarrow\operatorname{GL}_{2}(K)$ we may determine
the entire form $f$. We say that $\rho$ is ordinary if the restriction
$\rho|_{D_{2}}$ of $\rho$ to the decomposition group at $2$ is reducible, and
we say that an eigenform is ordinary if $a_{2}$ is a unit mod 2. The next
theorem describes the shape of $\rho_{f}$ at $2$:

######  Theorem 2.2 ([Wil88, Theorem 2]).

If $f$ is an ordinary $2$-adic form, then $\rho_{f}|_{D_{2}}$, the restriction
of $\rho_{f}$ to the decomposition group at a prime above $2$, is of the shape

$\rho_{f}|_{D_{2}}\sim\begin{pmatrix}\chi\lambda^{-1}&*\\\
0&\lambda\end{pmatrix}$

for $\lambda$ the unramified character
$G_{\mathbb{Q}_{2}}\rightarrow\overline{\mathbb{Z}}_{2}^{\times}$ taking
$\operatorname{Frob}_{2}$ to the unit root of $X^{2}-a_{2}X+2$, and $\chi$ is
the $2$-adic cyclotomic character.

###  2.2 A Duality Theorem

In this section, we will compute the Pontryagin dual of one of the summands in
$\mathbb{T}$ with the following lemma. Let $\mathfrak{a}$ be any maximal ideal
of $\mathbb{T}$ and let

$S_{2}(\Gamma_{0}(N),\mathbb{Z}_{2})_{\mathfrak{a}}=e\cdot
S_{2}(\Gamma_{0}(N),\mathbb{Z}_{2})$

where $e$ is the projector $\mathbb{T}\rightarrow\mathbb{T}_{\mathfrak{a}}$.

######  Lemma 2.3.

The Pontryagin dual of $\mathbb{T}_{\mathfrak{a}}$ is
$M=\displaystyle\lim_{\longrightarrow}S_{2}(\Gamma_{0}(N),\mathbb{Z}_{2})_{\mathfrak{a}}/(2^{n})$
where the transition maps are multiplication by $2$.

###### Proof.

First, we note that $\mathbb{T}_{\mathfrak{a}}$ acts on $M$ because
$\mathbb{T}_{\mathfrak{a}}$ acts compatibly on each level. If any element
$T\in\mathbb{T}_{\mathfrak{a}}$ acts trivially on $M$, then on any given
modular form in $S_{2}(\Gamma_{0}(N),\mathbb{Z}_{2})_{\mathfrak{a}}$, it acts
by arbitrarily high powers of $2$, and hence acts as $0$. Then $T$ acts
trivially on the rest of $S_{2}(\Gamma_{0}(N),\mathbb{Z}_{2})$, so $T$ is the
$0$ endomorphism. Therefore, $M$ is a faithful
$\mathbb{T}_{\mathfrak{a}}$-module.

We also know that $M[\mathfrak{a}]$, the elements of $M$ killed by all of
$\mathfrak{a}$, is a subspace of
$S_{2}(\Gamma_{0}(N),\mathbb{Z}_{2})_{\mathfrak{a}}/(2)=S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})_{\mathfrak{a}}$.
It is a vector space over $\mathbb{T}/\mathfrak{a}$, although through the
action of $\mathbb{T}$, not by multiplication on the coefficients. We explain
why it’s a $1$-dimensional $\mathbb{T}/\mathfrak{a}$-vector space. The map

$S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})\rightarrow\operatorname{Hom}(\mathbb{T},\mathbb{F}_{2}),\quad
f\mapsto\phi_{f}:T_{n}\rightarrow a_{n}$

is injective by the $q$-expansion principle. The forms killed by
$\mathfrak{a}$ must correspond to maps factoring through
$\mathbb{T}/\mathfrak{a}$, so the space of forms is at most the dimension of
$\operatorname{Hom}(\mathbb{T}/\mathfrak{a},\mathbb{F}_{2})=\dim_{\mathbb{F}_{2}}\mathbb{T}/\mathfrak{a}$.
So the dimension as a $\mathbb{T}/\mathfrak{a}$-vector space is at most $1$.

On the other hand, there is at least $1$ form in $M[\mathfrak{a}]$, because we
may take the form $T_{1}q+T_{2}q^{2}+T_{3}q^{3}+\ldots\in
S_{2}(\Gamma_{0}(N),\mathbb{T}/\mathfrak{a})$ and consider its image under the
trace map $\mathbb{T}/\mathfrak{a}\rightarrow\mathbb{F}_{2}$. This is nonzero
because the trace map is nondegenerate, and because the Hecke operators
generate $\mathbb{T}$ additively. This is in the kernel of $\mathfrak{a}$
because the trace of a form is just the sum of its conjugates, and for any
expression in $\mathfrak{a}$ in terms of the Hecke operators with coefficients
in $\mathbb{F}_{2}$, because its application to the original form is $0$ by
definition, its application to any of the form’s conjugates must also be $0$
(because the Hecke operators act $\mathbb{F}_{2}$-linearly on a form’s
coefficients and hence commute with Galois conjugation), and so too must its
application to the sum. Because the trace form has coefficients in
$\mathbb{F}_{2}$, we’ve found a nontrivial form in $M[\mathfrak{a}]$, and this
must be dimension $1$ as required.

We consider the Pontryagin dual of $M$: as $M$ is a $\mathbb{Z}_{2}$-module,
the image of any map $M\rightarrow\mathbb{Q}/\mathbb{Z}$ must land in
$\mathbb{Q}_{2}/\mathbb{Z}_{2}$. So let
$M^{\vee}=\operatorname{Hom}_{\mathbb{Z}_{2}}(M,\mathbb{Q}_{2}/\mathbb{Z}_{2})$.
We endow this with a $\mathbb{T}_{\mathfrak{a}}$-module structure by letting
$(T\phi)(f)=\phi(Tf)$. Because
$S_{2}(\Gamma_{0}(N),\mathbb{Z}_{2})_{\mathfrak{a}}\simeq\mathbb{Z}_{2}^{k}$
for some $k$ because it is torsion free,
$M\simeq(\mathbb{Q}_{2}/\mathbb{Z}_{2})^{k}$ as a $\mathbb{Z}_{2}$ module. So
if $\phi(f)=0$ for all $\phi\in M^{\vee}$, we know that $f=0$. If $T\phi=0$
for all $\phi$, then $\phi(Tf)=0$ for all $\phi$ and $f$, and so $Tf=0$ for
all $f$, and $T=0$. So $M^{\vee}$ is also a faithful
$\mathbb{T}_{\mathfrak{a}}$-module.

Further, $\mathbb{T}_{\mathfrak{a}}$ injects into $M^{\vee}$: we can rewrite

$M=\displaystyle\lim_{\longrightarrow}\frac{1}{2^{n}}S_{2}(\Gamma_{0}(N),\mathbb{Z}_{2})_{\mathfrak{a}}/S_{2}(\Gamma_{0}(N),\mathbb{Z}_{2})_{\mathfrak{a}}$

where the transition maps are inclusion. Then the
$\mathbb{T}_{\mathfrak{a}}\times M\rightarrow\mathbb{Q}_{2}/\mathbb{Z}_{2}$ as
$(T,f)\rightarrow a_{1}(Tf)$ defines the injection. By Nakayama’s lemma and
the duality of $M[\mathfrak{a}]$ and $M^{\vee}/\mathfrak{a}$, the minimal
number of generators of $M^{\vee}$ as a $\mathbb{T}_{\mathfrak{a}}$-module is
$1$. So we’ve proven that $M^{\vee}\simeq\mathbb{T}_{\mathfrak{a}}$.∎

We may use Pontryagin Duality to find that the dual to
$T_{\mathfrak{a}}/2=M^{\vee}/2$ is $M[2]$, which is exactly
$S_{2}(\Gamma_{0}(N),\mathbb{Z}_{2})_{\mathfrak{a}}/(2)=S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})_{\mathfrak{a}}$.
Thus we obtain a perfect pairing

$T_{\mathfrak{a}}/2\times
S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})_{\mathfrak{a}}\rightarrow\mathbb{F}_{2},\qquad(T,f)\rightarrow
a_{1}(Tf).$

We may sum these pairings over all $\mathfrak{a}$, because Hecke operators and
forms with incompatible maximal ideals annihilate each other. Therefore we
obtain a perfect pairing $\mathbb{T}/2\times
S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})\rightarrow\mathbb{F}_{2}$.

##  3 $2T_{2}$ is integral

In this section we prove the following lemma:

######  Lemma 3.1.

For any element $T\in\mathbb{T}$, the element $2T\in\mathbb{T}$ lies inside
$\mathbb{T}^{\operatorname{an}}$.

First we prove a lemma describing the image of the representation
corresponding to a non-Eisenstein ideal.

######  Lemma 3.2.

Suppose $\mathfrak{m}$ does not contain the Eisenstein ideal. Then there is a
representation

$\rho:G_{\mathbb{Q}}\rightarrow\operatorname{GL}_{2}(\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}).$

that is unramified outside $2N$, and which satisfies
$\operatorname{Tr}(\rho(\operatorname{Frob}_{\ell}))=T_{\ell}$ for $\ell\nmid
2N$.

###### Proof.

Let $A=\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$ and $A^{\prime}$ is its
integral closure over $\mathbb{Z}_{2}$, which can be written as the product
$\prod_{i}\mathcal{O}_{i}$ of a collection of integer rings. We know that
there exist representations
$\rho^{\prime}_{i}:G_{\mathbb{Q}}\rightarrow\prod_{i}\operatorname{GL}_{2}(\mathcal{O}_{i})$,
by Eichler-Shimura-Deligne-Serre. The image is
$\operatorname{GL}_{2}(\mathcal{O}_{i})$, because $G_{\mathbb{Q}}$ is compact,
and we may choose an invariant lattice on which it acts. These
$\rho^{\prime}_{i}$ combine to give a representation

$\rho^{\prime}=\prod_{i}\rho^{\prime}_{i}:G_{\mathbb{Q}}\rightarrow\prod_{i}\operatorname{GL}_{2}(\mathcal{O}_{i}).$

We know that the traces of the representations at $\operatorname{Frob}_{\ell}$
are the images of $T_{\ell}$ for all $\ell\nmid pN$, so the trace of
$\rho^{\prime}$ by Chebotarev Density always lands in
$\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$. We assumed $\mathfrak{m}$ did
not contain the Eisenstein ideal, so we know that each $\rho^{\prime}_{i}$,
and therefore the full $\rho^{\prime}$, is residually irreducible. By [Car94,
Theorem 2] we find that $\rho^{\prime}$ is similar to a representation

$\rho:G_{\mathbb{Q}}\rightarrow\operatorname{GL}_{2}(\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}).$

∎

To prove Lemma 3.1, we look at the three different possible cases and deduce
that the projection of $2T_{2}$ to $\mathbb{T}_{\mathfrak{a}}$ lies in
$\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$ for each
$\mathfrak{m}\subseteq\mathfrak{a}$. Further, we prove that $T_{2}^{2}$ lies
in $\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}\cdot
T_{2}+\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$, so that any
$T\in\mathbb{T}$, being an element in $\mathbb{T}^{\operatorname{an}}[T_{2}]$,
lies in $\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}\cdot
T_{2}+\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$ also, and hence is half
of an element in $\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$.

###  3.1 $\overline{\rho}$ ordinary irreducible

We first assume that the residual representation
$G_{\mathbb{Q}}\rightarrow\operatorname{GL}_{2}(\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}/\mathfrak{m})$
is irreducible but the local residual representation at $2$ is reducible. We
will show that $2T_{2}$, as an element of
$\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}[T_{2}]$, actually lies in
$\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$. This will be done by proving
it is in the ring generated over $\mathbb{Z}_{2}$ by the traces of $\rho$.
Equivalently, we will look at the traces of
$\rho\otimes_{\mathbb{Z}_{2}}\mathbb{Q}_{2}$. This breaks the representation
into a direct sum
$\bigoplus_{i}\rho^{\prime}_{i}\otimes\mathbb{Q}_{2}:G_{\mathbb{Q}}\rightarrow\prod_{i}\operatorname{GL}_{2}(E_{i})$.
Each of the $\rho^{\prime}_{i}$ themselves have the same residual
representation which is reducible when restricted to the decomposition group,
so all these representations are ordinary.

Looking at a given $\rho^{\prime}_{i}$, we may apply Theorem 2.2 to it to
obtain a shape of $\rho^{\prime}_{i}|_{D_{2}}$. In particular, the trace of an
element $\rho(g)$ is equal to $\chi(g)\lambda^{-1}(g)+\lambda(g)$ with
$\lambda$ the unramified character whose image of Frobenius is the unit root
of $X^{2}-T_{2}X+2$, and $\chi$ is the cyclotomic character. If $\alpha$
denotes the unit root of $x^{2}-a_{2,i}x+2=0$, then letting $g$ be an element
of $\operatorname{Gal}(\mathbb{Q}_{2}^{\text{ab}}/\mathbb{Q}_{2})$ which both
is a lift of Frobenius and acts trivially on the $2$-power roots of unity (so
$\chi(g)=1$), then we know $\operatorname{Tr}(g)=\alpha+\alpha^{-1}$. If we
let $h$ be a lift of Frobenius with $\chi(h)=-1$, we find that
$\operatorname{Tr}(h)=\alpha-\alpha^{-1}$. And by definition, we know
$\alpha+\frac{2}{\alpha}=a_{2,i}$, so
$2a_{2,i}=2\alpha+4\alpha^{-1}=3\operatorname{Tr}(g)-\operatorname{Tr}(h)$.

We now look at the product of representations. The elements $g$ and $h$ were
independent of the coefficient field, so we know that the element of
$\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}\otimes\mathbb{Q}_{2}$ that is
$2a_{2,i}$ in each coordinate, namely $2T_{2}\otimes 1$, is equal to
$3\operatorname{Tr}(g)-\operatorname{Tr}(h)$. So $2T_{2}$ is in the ring
generated by the traces of elements, and thus in
$\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$.

Similarly, we can prove that $T_{2}^{2}$ is in
$\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}+T_{2}\cdot\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$:
in each coordinate, we can calculate that

$a_{2,i}^{2}=\operatorname{Tr}(g)a_{2,i}+(\operatorname{Tr}(gh)-\operatorname{Tr}(g^{2})-1).$

So in $\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}[T_{2}]$, we find that
$T_{2}^{2}=\operatorname{Tr}(g)T_{2}+(\operatorname{Tr}(gh)-\operatorname{Tr}(g^{2})-1)$.
So
$T_{2}^{2}\subseteq\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}+T_{2}\cdot\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$,
and therefore so is every power of $T_{2}$. So we know that
$2\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}[T_{2}]\subseteq\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$,
and the $\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$-module quotient
$\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}[T_{2}]/\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$
is an $\mathbb{F}_{2}$ vector space. In section 4 we will calculate its
dimension.

###  3.2 $\overline{\rho}$ reducible

We now suppose $\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$ corresponds to
a reducible residual representation, so that $\mathfrak{m}$ is the Eisenstein
ideal generated by $2$ and $T_{\ell}$ for $\ell\nmid N$ (including $\ell=2$).
We claim that $T_{2}$ is already in
$\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$. This is because by [Maz77,
Proposition 17.1], the Eisenstein ideal of the full Hecke algebra is generated
by $1+\ell-T_{\ell}$ for any good prime. So by completeness, $T_{2}-3$ and
therefore $T_{2}$ can be written as a power series in $T_{\ell}-\ell-1$.

###  3.3 $\overline{\rho}$ non-ordinary

We now assume that the residual local representation at $2$ is irreducible, or
equivalently that in $\mathbb{T}_{\mathfrak{a}}$, $T_{2}$ is not a unit, where
$\mathfrak{a}$ is some ideal of $\mathbb{T}$ above $\mathfrak{m}$
corresponding to $\rho$. We claim that $T_{2}$ is already in
$\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$, so that
$\mathfrak{a}=\mathfrak{m}$ is actually unique, and the index is $1$.

######  Theorem 3.3.

If $\rho$ is non-ordinary with corresponding map
$\mathbb{T}^{\operatorname{an}}\rightarrow\mathbb{F}$ with maximal ideal
$\mathfrak{m}$, then for any $\mathfrak{a}\subseteq\mathbb{T}$ containing
$\mathfrak{m}$, $T_{2}\in\mathbb{T}_{\mathfrak{a}}$ is already contained in
the image of $\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$.

###### Proof.

The $\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$-module
$\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}[T_{2}]$ requires the same
generators as the $\mathbb{T}^{\operatorname{an}}/\mathfrak{m}$-vector space
$\mathbb{T}/\mathfrak{m}\mathbb{T}$ by Nakayama’s Lemma, so it’s enough to
prove that $\mathbb{T}/\mathfrak{m}\mathbb{T}$ is one-dimensional over
$\mathbb{T}^{\operatorname{an}}/\mathfrak{m}$. If it’s not, then all of
$\mathbb{T}^{\operatorname{an}}/\mathfrak{m}$ and $T_{2}$ are independent over
$\mathbb{F}_{2}$, so there is a homomorphism
$\phi\in\operatorname{Hom}(\mathbb{T}/\mathfrak{m}\mathbb{T},\mathbb{F}_{2})$
sending all of $\mathbb{T}^{\operatorname{an}}/\mathfrak{m}$ to $0$, and
$T_{2}$ to $1$. Recalling the perfect pairing after Lemma 2.3, we find a
nonzero modular form $g\in S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})[\mathfrak{m}]$
with all odd coefficients equal to $0$.

By part (3) of the main result of [Kat77], we know that there is some nonzero
form $f\in S_{1}(\Gamma_{0}(N),\mathbb{F}_{2})^{\operatorname{Katz}}$ with
$f^{2}=g$. (Here, we’re considering weight $1$ Katz forms, and so the weight
$2$ forms we construct may be Katz forms as well. So if necessary we enlarge
the spaces we’re considering, but it doesn’t affect the conclusion.) As forms
with coefficients in $\mathbb{F}_{2}$ commute with the Frobenius endomorphism,
$f(q^{2})$ has the same $q$-expansion as $g$. If $\mathbb{T}^{1}$ and
$\mathbb{T}^{1,\operatorname{an}}$ are the weight $1$ Hecke algebras, it is
quick to check that the corresponding Hecke actions on $q$-expansions of
$\mathbb{T}^{1,\operatorname{an}}$ are identical to those of
$\mathbb{T}^{\operatorname{an}}$. Therefore $f\in
S_{1}(\Gamma_{0}(N),\mathbb{F}_{2})^{\operatorname{Katz}}[\mathfrak{m}]$.
Further, we know that $f$ is alone in this space, by part (2) of [Kat77]: any
other form in
$S_{1}(\Gamma_{0}(N),\mathbb{F}_{2})^{\operatorname{Katz}}[\mathfrak{m}]$ has
the same odd coefficients, so the difference between it and $f$ has only even-
power coefficients, and hence must be $0$ by Katz’s theorem. So $f$ is also an
eigenform for $T_{2}$ in weight $1$, say with eigenvalue $b_{2}$.

So we’ve discovered that
$S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})^{\operatorname{Katz}}[\mathfrak{m}]$ is
at most $2$ dimensional, spanned by $Vf$ and $Af$. Here, $V$ acts as
$V\left(\sum_{n=1}^{\infty}a_{n}q^{n}\right)=\sum_{n=1}^{\infty}a_{n}q^{2n}$
on power series, so that $Vf=g$, and can either be a weight-doubling operator,
as used in [Kat77], or a level-doubling operator. Additionally, $Af$ is the
multiplication of $f$ with the Hasse invariant $A$, which preserves
$q$-expansions. We can hence calculate the action of $T_{2}$ on this space: we
know that $T_{2}$ acts in weight $2$ via $U+2V$, where
$U\left(\sum_{n=1}^{\infty}a_{n}q^{n}\right)=\sum_{n=1}^{\infty}a_{2n}q^{n}$,
and in weight $1$ as $U+\langle 2\rangle V$ with $\langle 2\rangle$ the
diamond operator, which is identically $1$ on mod 2 forms. Further, we can
compute that $UVf=Af$, as $V$ doubles each exponent and $U$ halves it.

So we find

$\displaystyle T_{2}(Vf)$ $\displaystyle=UVf=Af$ $\displaystyle T_{2}(Af)$
$\displaystyle=U(Af)=A(Uf)=A(T_{2}f-\langle 2\rangle Vf)=A(b_{2}f)-\langle
2\rangle Vf$

and the matrix for the $T_{2}$ action is $\begin{pmatrix}b_{2}&-\langle
2\rangle\\\ 1&0\end{pmatrix}$. (In these computations, the distinction between
the level-raising $V$ and the weight-raising $V$ has been blurred, because on
$q$-expansions they are equal; we view both lines as equalities of weight $2$
level $\Gamma_{0}(N)$ forms.) As $\langle 2\rangle$ is trivial, the
determinant of this matrix is $1$, so $T_{2}$ is invertible. This is
impossible because the form was non-ordinary. So there cannot be such a form
$g$, and $\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}[T_{2}]$ requires only
one generator as a $\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$-module, as
required. ∎

##  4 Dimension of $\mathbb{T}/\mathbb{T}^{\operatorname{an}}$

In this section we prove the second half of Theorem 1.1. It is enough to look
locally, so we will localize at a maximal ideal $\mathfrak{m}$ of
$\mathbb{T}^{\operatorname{an}}$. Because completion at only ordinary non-
Eisenstein ideals have $T_{2}$ not immediately in
$\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$, we assume that $\mathfrak{m}$
is such an ideal.

###  4.1 Relating $\mathbb{T}/\mathbb{T}^{\operatorname{an}}$ to $S_{2}$

We first recall the perfect pairing
$S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})\times\mathbb{T}/2\rightarrow\mathbb{F}_{2}$,
given by $(f,T)\rightarrow a_{1}(Tf)$. While proving this, we proved perfect
pairings
$S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})_{\mathfrak{a}}\times\mathbb{T}_{\mathfrak{a}}/2\rightarrow\mathbb{F}_{2}$,
and we now combine all $\mathfrak{a}$ that contain $\mathfrak{m}$, to get a
perfect pairing
$S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})_{\mathfrak{m}}\times\mathbb{T}_{\mathfrak{m}}/2\rightarrow\mathbb{F}_{2}$
where we denote $\mathbb{T}_{\mathfrak{m}}$ as the localization of
$\mathbb{T}$ at the (not necessarily maximal) ideal $\mathfrak{m}\mathbb{T}$,
and $S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})_{\mathfrak{m}}=e\cdot
S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})$ for $e$ the projection from $\mathbb{T}$
to $\mathbb{T}_{\mathfrak{m}}$. Considering the subspace of forms killed by
$A\theta$, the operator defined in [Kat77] which acts as $q\frac{d}{dq}$ on
$q$-expansions and raises the weight by $3$, it’s clear that the entirety of
$\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$ annihilates it under the
pairing, and we wish to prove that this is the full annihilator. For ease of
notation, let us write
$V=\mathbb{T}_{\mathfrak{m}}/2\mathbb{T}_{\mathfrak{m}}$,
$W=S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})_{\mathfrak{m}}$, and
$V^{\prime}=\mathbb{T}_{\mathfrak{m}}^{\operatorname{an}}/2\mathbb{T}_{\mathfrak{m}}$.

######  Lemma 4.1.

$S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})_{\mathfrak{m}}\cap\operatorname{Ker}A\theta$
and $\mathbb{T}_{\mathfrak{m}}^{\operatorname{an}}/2\mathbb{T}_{\mathfrak{m}}$
are mutual annihilators in this perfect pairing.

###### Proof.

We’ve seen that they annihilate each other. Now suppose
$f=\sum_{i=1}^{\infty}a_{i}q^{i}\in W$ is annihilated by all of $V^{\prime}$.
By the usual formula for the Hecke action on $q$-expansions, the coefficient
of $q^{1}$ in $T_{n}f$ is $a_{n}$, so $a_{n}=0$ for all odd $n$. Therefore
$f\in
S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})_{\mathfrak{m}}\cap\operatorname{Ker}A\theta$,
and we can call this space $\operatorname{Ann}(V^{\prime})$. This is enough to
show they are mutual annihilators by dimension count, but we’ll prove the
other direction as well.

The space $W/\operatorname{Ann}(V^{\prime})$ is represented by sequences of
odd-power coefficients that appear in forms in $W$. We first prove that the
map
$V^{\prime}\rightarrow\operatorname{Hom}(W/\operatorname{Ann}(V^{\prime}),\mathbb{F}_{2})$
induced by the pairing is surjective. Given a map
$\varphi\in\operatorname{Hom}(W/\operatorname{Ann}(V^{\prime}),\mathbb{F}_{2})$
whose input is sequences of odd-power coefficients, we can define a map
$\varphi^{\prime}$ in the double dual of $V^{\prime}$ taking maps

$\chi:V^{\prime}\rightarrow\mathbb{F}_{2}\text{ to
}\varphi(\chi(T_{1}),\chi(T_{3}),\chi(T_{5}),\ldots).$

This is the definition of $\varphi^{\prime}$ when
$(\chi(T_{1}),\chi(T_{3}),\ldots)$ appears as the odd-power coefficients of a
form. And then if we’ve not defined $\varphi^{\prime}$ on all of the dual of
$V^{\prime}$, we can just extend it any way we want. But because $V^{\prime}$
is finite dimensional, this $\varphi^{\prime}$ determines an element
$T_{\varphi}\in V^{\prime}$ for which

$\chi(T_{\varphi})=\varphi^{\prime}(\chi)=\varphi(\chi(T_{1}),\chi(T_{3}),\ldots).$

Then because any sequence of coefficients $(a_{1},a_{3},\ldots)$ is given by a
character $\chi_{(a_{i})}:T_{n}\rightarrow a_{n}$ (the restriction of such a
$\chi$ from $\mathbb{T}_{\mathfrak{a}}$, for example), the pairing truly does
send $T_{\varphi}$ to $\varphi$.

Now given $T$ that sends all of $\operatorname{Ann}(V^{\prime})$ to $0$, $Tf$
must only depend on the odd coefficients of $f$. But then
$\varphi:f\rightarrow a_{1}(Tf)$ is an element of
$\operatorname{Hom}(W/\operatorname{Ann}(V^{\prime}),\mathbb{F}_{2})$. So by
surjectivity there is some element $T^{\prime}$ of $V^{\prime}$ with
$a_{1}(Tf)=\varphi(f)=a_{1}(T^{\prime}f)$ for all $f\in
W/\operatorname{Ann}(V^{\prime})$. Then $a_{1}((T-T^{\prime})f)$ is $0$ for
all $f$ either in $\operatorname{Ann}(V^{\prime})$ or a lift of an element of
$W/\operatorname{Ann}(V^{\prime})$, and so in all of $W$. Because the pairing
is perfect, $T=T^{\prime}\in V^{\prime}$ as we needed.∎

Now that we know these are mutual annihilators, we obtain an isomorphism

$V/V^{\prime}\rightarrow\operatorname{Hom}(\operatorname{Ann}(V^{\prime}),\mathbb{F}_{2}),$

and taking dimensions and reinterpreting, we’ve proven that

$\dim\mathbb{T}_{\mathfrak{m}}/\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}=\dim
S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})_{\mathfrak{m}}\cap\operatorname{Ker}A\theta.$

So we have proven the following.

######  Lemma 4.2.

The index of $\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$ in
$\mathbb{T}_{\mathfrak{m}}$ equals $2$ raised to the dimension of
$S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})_{\mathfrak{m}}\cap\operatorname{Ker}A\theta.$

###  4.2 Lifting from weight $1$ to weight $2$

Now we use the main theorem of [Kat77] to find a subspace of
$S_{1}(\Gamma_{0}(N),\mathbb{F}_{2})^{\operatorname{Katz}}$ that maps under
$V$ to
$S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})_{\mathfrak{m}}\cap\operatorname{Ker}A\theta$.
As in Section 3.3, we have $\mathbb{T}^{\operatorname{an}}$-equivariance, and
so the maximal ideal $\mathfrak{m}$ has an exact analogue in
$\mathbb{T}^{1,\operatorname{an}}$ and we land in the subspace
$S_{1}(\Gamma_{0}(N),\mathbb{F}_{2})_{\mathfrak{m}}^{\operatorname{Katz}}$. We
may not obtain the whole subspace because, while $Vf$ is in the kernel of
$A\theta$ for all $f\in
S_{1}(\Gamma_{0}(N),\mathbb{F}_{2})_{\mathfrak{m}}^{\operatorname{Katz}}$, we
don’t know that it’s a form that is the reduction of a $\mathbb{Z}_{2}$ form,
which is what $\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$ parametrizes. In
this section we will prove that the space of Katz forms of weight $2$ actually
are all standard forms.

The first case is $N\equiv 3\mod 4$, which was taken care of Edixhoven:

######  Theorem 4.3 ([Edi06, Theorem 5.6]).

Let $N\geq 5$ be odd and divisible by a prime number $q\equiv-1$ modulo $4$
(hence the stabilizers of the group $\Gamma_{0}(N)/\\{1,-1\\}$ acting on the
upper half plane have odd order). Then
$S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})^{\operatorname{Katz}}$ and
$\mathbb{F}_{2}\otimes S_{2}(\Gamma_{0}(N),\mathbb{Z})$ are equal, and the
localizations at non-Eisenstein maximal ideals of the algebras of
endomorphisms of $S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})^{\operatorname{Katz}}$
and $H^{1}_{\textup{par}}(\Gamma_{0}(N),\mathbb{F}_{2})$ generated by all
$T_{n}$ ($n\geq 1$) coincide: both are equal to that of
$S_{2}(\Gamma_{0}(N),\mathbb{Z})$ tensored with $\mathbb{F}_{2}$.

So for primes $N\equiv 3\mod 4$, we’ve proven the equality in Theorem 1.1. For
the remainder of this section we therefore assume $N\equiv 1\mod 4$. Further,
up until this point we’ve only worked with $\mathbb{F}_{2}$-forms, but we
change coefficients to $\overline{\mathbb{F}}_{2}$ so that we can find
eigenforms associated to each maximal ideal. Theorem 4.3 still applies as its
proof in [Edi06] can be extended to all finite extensions of $\mathbb{F}_{2}$.

######  Theorem 4.4.

There are no Katz forms that are not the reduction of a form in
$S_{2}(\Gamma_{0}(N),\overline{\mathbb{Z}}_{2})$. That is,

$S_{2}(\Gamma_{0}(N),\overline{\mathbb{F}}_{2})^{\operatorname{Katz}}=S_{2}(\Gamma_{0}(N),\overline{\mathbb{F}}_{2}).$

###### Proof.

Let $\ell$ be an arbitrary prime that is $3\mod 4$, and we will look at
$S_{2}(\Gamma_{0}(N\ell),\overline{\mathbb{F}}_{2})^{\operatorname{Katz}}$. We
can apply Theorem 4.3 to it and conclude that this space is exactly the
characteristic $0$ forms tensored with $\overline{\mathbb{F}}_{2}$, so we may
drop the Katz superscript. Further, we know that all Katz forms of level
$\Gamma_{0}(N)$ lie in this space. So we just need to know there are no extra
level $\Gamma_{0}(N)$ forms within this space.

As $\mathbb{T}^{\operatorname{Katz}}\otimes\overline{\mathbb{F}}_{2}$ can be
broken into a direct sum of $\overline{\mathbb{F}}_{2}$-vector spaces on which
the semi-simple action of each operator is by multiplication by a constant,
$S_{2}(\Gamma_{0}(N),\overline{\mathbb{F}}_{2})^{\operatorname{Katz}}$ can be
written as a direct sum of generalized eigenspaces. If we show every
generalized eigenform in
$S_{2}(\Gamma_{0}(N),\overline{\mathbb{F}}_{2})^{\operatorname{Katz}}$ is the
reduction of a modular form from
$S_{2}(\Gamma_{0}(N),\overline{\mathbb{Z}}_{2})$, then we’re done. So suppose
$f$ is a generalized Katz eigenform for all $T_{n}$, including $T_{2}$. Let
the eigenvalue corresponding to $T_{\ell}$ equal $a_{\ell}$; we will prove
that if $f\not\in S_{2}(\Gamma_{0}(N),\overline{\mathbb{F}}_{2})$, then
$a_{\ell}=0$.

There are two maps from
$S_{2}(\Gamma_{0}(N),\overline{\mathbb{F}}_{2})^{\operatorname{Katz}}$ to
$S_{2}(\Gamma_{0}(N\ell),\overline{\mathbb{F}}_{2})$: the plain embedding with
equality on $q$-expansions, and the map $V_{\ell}$ sending $f(q)$ to
$f(q^{\ell})$. We know $T_{\ell}=U_{\ell}+\ell V_{\ell}$ on $q$-expansions, so
we find that

$U_{\ell}(T_{\ell}-a_{\ell})=U_{\ell}(U_{\ell}+\ell
V_{\ell}-a_{\ell})=U_{\ell}^{2}-a_{\ell}U_{\ell}+\ell
U_{\ell}V_{\ell}=U_{\ell}^{2}-a_{\ell}U_{\ell}+\ell$

as operators from
$S_{2}(\Gamma_{0}(N),\overline{\mathbb{F}}_{2})^{\operatorname{Katz}}$ to
$S_{2}(\Gamma_{0}(N\ell),\overline{\mathbb{F}}_{2})$. Then because $f$ is a
generalized eigenform, we find

$0=(U_{\ell}^{k}(T_{\ell}-a_{\ell})^{k})f=U_{\ell}^{k-1}(U_{\ell}^{2}-a_{\ell}U_{\ell}+\ell)(T_{\ell}-a_{\ell})^{k-1}f=\ldots=(U_{\ell}^{2}-a_{\ell}U_{\ell}+\ell)^{k}f.$

If we factor $X^{2}-a_{\ell}X+\ell$ as $(X-\alpha)(X-\beta)$ for some lift of
$a_{\ell}$, we’ve proven that $(U_{\ell}-\alpha)(U_{\ell}-\beta)$ acts
topologically nilpotently on any lift of $f$ (which exists by Theorem 4.4).
This will eventually be used to prove that one of $\alpha$ or $\beta$, and
hence both, reduce to $1$ mod the maximal ideal of
$\overline{\mathbb{Z}}_{2}$.

######  Lemma 4.5.

For any characteristic $0$ newform $g$ of level $N\ell$, $U_{\ell}-1$ acts
topologically nilpotently.

###### Proof.

The eigenform $g$ gives us a representation
$\rho:G_{\mathbb{Q}}\rightarrow\operatorname{GL}_{2}(\overline{\mathbb{Q}}_{2})$.
The shape of this representation at the decomposition group at $\ell$ is given
by [DDT97, Theorem 3.1(e)], as we recalled in the proof of Theorem 2.1, which
says that

$\rho|_{D_{\ell}}=\begin{pmatrix}\chi\varepsilon&*\\\ 0&\chi\end{pmatrix}$

where $\chi$ is the unramified representation that sends
$\operatorname{Frob}_{\ell}$ to the $U_{\ell}$-eigenvalue of $g$, and
$\varepsilon$ is the $2$-adic cyclotomic character. Because the determinant is
the $2$-adic cyclotomic character as well, we know that $\chi^{2}=1$, so the
$U_{\ell}$-eigenvalue of $g$ is $\pm 1$. So $U_{\ell}-1$ is either $0$ or
$-2$, which both act nilpotently.∎

If $\alpha-1$ and $\beta-1$ have valuation $0$, then
$(U_{\ell}-\alpha)(U_{\ell}-\beta)$ will not act nilpotently on any linear
combination of eigenforms which includes at least one newform, by Lemma 4.5.
As $(U_{\ell}-\alpha)(U_{\ell}-\beta)$ acts nilpotently on a lift of $f$, we
know that this lift is a linear combinaton of only oldforms, and hence $f$
lifts to $S_{2}(\Gamma_{0}(N),\overline{\mathbb{Z}}_{2})$. Otherwise, one of
$\alpha$ and $\beta$, and hence both, are $1$ mod the maximal ideal of
$\overline{\mathbb{Z}}_{2}$, and so $\alpha+\beta\equiv 0\equiv a_{\ell}$.

Therefore, we have proven that if $f$ is a generalized eigenform in
$S_{2}(\Gamma_{0}(N),\overline{\mathbb{F}}_{2})^{\operatorname{Katz}}$ that
has no lift to characteristic $0$, then $a_{\ell}=0$ for any prime $\ell\equiv
3\mod 4$, as our choice of $\ell$ was arbitrary. Letting $g$ be a true
eigenform in the same eigenspace as $f$, we obtain a representation
$\overline{\rho}_{g}:G_{\mathbb{Q}}\rightarrow\operatorname{GL}_{2}(\overline{\mathbb{F}}_{2})$
with $\operatorname{Tr}(\rho_{g}(\operatorname{Frob}_{p}))=a_{p}$. We showed
that $\overline{\rho}_{g}$ has trace $0$ on all $\operatorname{Frob}_{\ell}$,
so it must be the induction of a character from $G_{\mathbb{Q}(i)}$ to
$G_{\mathbb{Q}}$. But such a representation is dihedral in the terminology of
[KM19], and [KM19, Theorem 12(1)] proves that it’s impossible for a dihedral
representation on $G_{\mathbb{Q}(i)}$ to give rise to a form of level
$\Gamma_{0}(N)$. So there can be no Katz eigenforms of level $\Gamma_{0}(N)$
that don’t lift, and hence no generalized eigenforms and therefore no forms at
all.∎

From this, we conclude that all the forms $V_{2}f$, where $f$ is a weight $1$
form of level $N$, are classical forms, and so the dimension of the space
$S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})_{\mathfrak{m}}\cap\operatorname{Ker}A\theta$
is exactly the dimension
$S_{1}(\Gamma_{0}(N),\mathbb{F}_{2})^{\operatorname{Katz}}_{\mathfrak{m}}$.
And so from Lemma 4.2, taking a direct sum over all $\mathfrak{m}$, we obtain
Theorem 1.1.

##  5 Examples

In this section we use Theorem 1.1 to make nontrivial observations about the
index of $\mathbb{T}^{\operatorname{an}}$ inside $\mathbb{T}$.

###  5.1 $N\equiv 3\bmod 4$

######  Lemma 5.1.

If $N\equiv 3\bmod 4$ is prime, the anemic Hecke algebra
$\mathbb{T}^{\operatorname{an}}$ is equal to the full algebra $\mathbb{T}$ if
and only if the class group $\textup{Cl}(\mathbb{Q}(\sqrt{-N}))$ is trivial.

###### Proof.

If $K=\mathbb{Q}(\sqrt{-N})$ has class number greater than $1$, by genus
theory, since the discriminant of $K$ is $-N$ which is divisible by only a
single prime, the $2$-part of the class group of $K$ is trivial, so
$\text{Cl}(K)$ has a nontrivial mod $2$ multiplicative character which
translates to an unramified mod 2 character $\chi$ of
$\operatorname{Gal}(\overline{\mathbb{Q}}/K)$. Inducing this to
$\operatorname{Gal}(\overline{\mathbb{Q}}/\mathbb{Q})$, we get a dihedral
representation with Artin conductor equal to $N$. Wiese proves in [Wie04] that
all dihedral representations give rise to Katz modular forms, and so the space
$S_{1}(\Gamma_{0}(N),\mathbb{F}_{2})^{\operatorname{Katz}}$ is nontrivial, and
hence $\mathbb{T}^{\operatorname{an}}\subsetneq\mathbb{T}$.

This shows that if $N$ is not $3,7,11,19,43,67$ or $163$ (and is still a
$3\bmod 4$ prime), $\mathbb{T}^{\operatorname{an}}(N)\subsetneq\mathbb{T}(N)$.
On the other hand, for $N=3$ and $N=7$ there are no modular forms of weight
$2$, and for the other $N$, computer verification using the techniques of
modular symbols, such as described in [Ste07], provides the following table:
$\begin{array}[]{c|c}N&T_{2}\\\ \hline\cr 11&-2T_{1}\\\ \hline\cr 19&0\\\
\hline\cr 43&-2T_{1}-2T_{3}+T_{5}\\\ \hline\cr 67&T_{3}-T_{11}\\\ \hline\cr
163&\begin{array}[]{c}30T_{1}-16T_{3}-23T_{5}-9T_{7}+18T_{9}+3T_{11}-24T_{13}\\\
+12T_{15}+40T_{17}-16T_{19}-14T_{21}-9T_{23}+2T_{25}+32T_{27}\end{array}\\\
\hline\cr\end{array}$

These each prove that there are no Katz eigenforms of weight $1$ and level $N$
for any of these $N$, and in turn that there are no Galois representations
that could provide such forms. Of course, we knew a priori there were no
dihedral representations, as they would need to arise from the class group,
but we now know that there are no larger-image representations.∎

###  5.2 $N\equiv 1\bmod 4$

######  Question 5.2.

Is it true that for a positive proportion of prime $N\equiv 1\bmod 4$, the
anemic Hecke algebra $\mathbb{T}^{\operatorname{an}}$ is not equal to the full
algebra $\mathbb{T}$, and for a positive proportion of $N$,
$\mathbb{T}^{\operatorname{an}}$ is equal to $\mathbb{T}$?

We cannot immediately claim anything about the class group, because the Cohen-
Lenstra heuristics [CL84, C11] claim that approximately $75.446\%$ of positive
prime-discriminant quadratic extensions have trivial class group, so that
there can be no dihedral modular forms.

The strong form of Serre’s conjecture due to Edixhoven [Edi97, Conjecture 1.8]
is not known, where the strong form differs from the form proven by Khare and
Wintenberger in [KW09] in this weight $1$ case. A result of Wiese for dihedral
representations [Wie04] is known, and a converse (that the corresponding
representation $\overline{\rho}$ is unramified at $2$) has been proven [Wie14,
Corollary 1.3]. We may also use Theorem 1.1 to construct weight $1$ forms in
the case that the eigenvalues of $\operatorname{Frob}_{2}$ in the
characteristic $2$ representation are distinct, because there are two possible
values for $a_{2}$, implying that
$\mathbb{T}_{\mathfrak{m}}\neq\mathbb{T}^{\operatorname{an}}_{\mathfrak{m}}$.

We also know the subgroups of
$\operatorname{SL}_{2}(\overline{\mathbb{F}}_{2})$, by Dickson, of four types:
cyclic, upper-triangular, dihedral, and full-image (see [Suz77, Chapter 3,
Theorem 6.17]). We know a modular representation must be absolutely
irreducible: if not, say $f$ is a weight $1$ form for which
$\overline{\rho}_{f}$ is reducible. Then $Af$ is a weight $2$ form with the
same representation, along with $Vf$ in the same generalized eigenspace. But
in Section 3.2 we proved that $T_{2}$ is already contained in the Hecke
algebra corresponding to any eigenform with reducible representation, meaning
that the dimension of $S_{2}(\Gamma_{0}(N),\mathbb{F}_{2})_{\mathfrak{m}}$ is
dimension $1$, not $2$. Therefore only absolutely irreducible representations
can be modular, so only dihedral and full-image representations can exist. So
assuming the strong version of Serre’s conjecture, we know that for any weight
$1$ forms to exist at level $N$, we need either a dihedral extension of
$\mathbb{Q}$, which must arise from inducing from the class group of
$\mathbb{Q}(\sqrt{N})$, or we need an extension of $\mathbb{Q}$ unramified
outside $N$ with Galois group isomorphic to
$\operatorname{SL}_{2}(\mathbb{F}_{2^{k}})$ for some $k$.

Work has been done by Lipnowski [Lip16] to interpret Bhargava’s heuristics for
the Galois group $\operatorname{GL}_{2}(\mathbb{F}_{p})$ for $p$ a prime, in
order to count elliptic curves by their conductors through their $p$-adic
representations. Although not done in this current note, it appears tractable
to similarly analyze the groups $\operatorname{SL}_{2}(\mathbb{F}_{2^{k}})$
and obtain a heuristic, explicit or not, on how many primes $p$ have an
elsewhere-unramified extension with each of these as their Galois groups.
Because of the Cohen-Lenstra heuristics, it appears likely that infinitely
many, even a positive proportion, of primes $1\bmod 4$ have no weight $1$
forms, so $\mathbb{T}=\mathbb{T}^{\operatorname{an}}$, and a positive
proportion of primes have some weight $1$ form so
$\mathbb{T}^{\operatorname{an}}\subsetneq\mathbb{T}$.

####  5.2.1 Explicit example: $N=653$

An instructive example is that of $N=653$. Of course this is $1\bmod 4$, and
so any dihedral representation that would give a weight $1$ form would have to
come from an induction of the class group of $\mathbb{Q}(\sqrt{653})$, but the
Minkowski bound is $\frac{1}{2}\sqrt{653}\approx 12.77$, and $2,3,5$ are inert
and $7=230^{2}-653\cdot 9^{2}$ and $-11=51^{2}-653\cdot 2^{2}$ are norms of
principal ideals. So $\mathbb{Q}(\sqrt{653})$ has class number $1$. But the
Galois closure $L$ of the field $\mathbb{Q}[x]/(x^{5}+3x^{3}-6x^{2}+2x-1)$ has
Galois group $A_{5}=\operatorname{SL}_{2}(\mathbb{F}_{4})$, and is ramified
only at $653$ with ramification degree $2$ and inertial degree $2$. Therefore,
Edixhoven predicts that the tautological Galois representation gives rise to a
weight $1$ level $\Gamma_{0}(653)$ modular form. This is not a classical form,
as $\operatorname{SL}_{2}(\mathbb{F}_{4})$ does not embed into
$\operatorname{GL}_{2}(\mathbb{C})$, where all weight $1$ characteristic $0$
eigenforms must arise from.

On the other hand, $\operatorname{SL}_{2}(\mathbb{F}_{4})$ does embed into
$\operatorname{PGL}_{2}(\mathbb{C})$, and by a theorem of Tate, all projective
Galois representations lift. We can follow the proof given by Serre in [Ser77]
to obtain a lift, unramified away from $653$, and with Artin conductor
$653^{2}$. The fixed field of the kernel of this representation is a quadratic
extension of $L[x]/(x^{4}-x^{3}+82x^{2}-1102x+13537)$, which is itself the
compositum of $L$ and the quartic subfield of the $653$rd roots of unity.
Locally at $653$ it is a faithful representation of
$\operatorname{Gal}(\mathbb{Q}_{653}(\sqrt[8]{653},\sqrt{2})/\mathbb{Q}_{653})$,
a Galois group isomorphic to $\langle x,y|x^{8}=y^{2}=e,yx=x^{5}y\rangle$.

We therefore find that, as the Artin conjecture for odd representations has
been proven in [KW09], an eigenform of weight $1$ and level $653^{2}$ that
reduces to the characteristic $2$ form of level $653$ we found above. We can
additionally twist by the nontrivial character of
$\mathbb{Q}(\sqrt{653})/\mathbb{Q}$, not changing the determinant or level, to
get a second Artin representation, and hence a second modular form of the same
weight and nebentypus. These two eigenforms are congruent mod $2$, so their
average is also an integral form, and there is therefore a nilpotent element
of the weight $1$ mod $2$ Hecke algebra, in a similar sense to [CE09, Lemma
3.8]. And conjugating the $\mathbb{F}_{4}$-forms, we obtain $2$ more weight
$1$ forms of level $653$. So the index of $\mathbb{T}^{\operatorname{an}}$ in
$\mathbb{T}$ must be at least $16$.

Indeed, we can find the following four (non-eigen)forms of weight $2$ and
level $653$:

$\displaystyle f_{1}=0$ $\displaystyle q^{1}$ $\displaystyle+1$ $\displaystyle
q^{2}$ $\displaystyle+2$ $\displaystyle q^{3}$ $\displaystyle-4$
$\displaystyle q^{4}$ $\displaystyle+0$ $\displaystyle q^{5}$
$\displaystyle+2$ $\displaystyle q^{6}$ $\displaystyle+0$ $\displaystyle
q^{7}$ $\displaystyle+4$ $\displaystyle q^{8}$ $\displaystyle+0$
$\displaystyle q^{9}$ $\displaystyle+4$ $\displaystyle q^{10}$
$\displaystyle+0$ $\displaystyle q^{11}$ $\displaystyle+1$ $\displaystyle
q^{12}$ $\displaystyle-6$ $\displaystyle q^{13}$ $\displaystyle+\ldots$
$\displaystyle f_{2}=0$ $\displaystyle q^{1}$ $\displaystyle+0$ $\displaystyle
q^{2}$ $\displaystyle+2$ $\displaystyle q^{3}$ $\displaystyle-3$
$\displaystyle q^{4}$ $\displaystyle+0$ $\displaystyle q^{5}$
$\displaystyle+2$ $\displaystyle q^{6}$ $\displaystyle+2$ $\displaystyle
q^{7}$ $\displaystyle+2$ $\displaystyle q^{8}$ $\displaystyle+4$
$\displaystyle q^{9}$ $\displaystyle-3$ $\displaystyle q^{10}$
$\displaystyle+4$ $\displaystyle q^{11}$ $\displaystyle-6$ $\displaystyle
q^{12}$ $\displaystyle+0$ $\displaystyle q^{13}$ $\displaystyle+\ldots$
$\displaystyle f_{3}=0$ $\displaystyle q^{1}$ $\displaystyle+0$ $\displaystyle
q^{2}$ $\displaystyle+0$ $\displaystyle q^{3}$ $\displaystyle+4$
$\displaystyle q^{4}$ $\displaystyle+0$ $\displaystyle q^{5}$
$\displaystyle+1$ $\displaystyle q^{6}$ $\displaystyle+2$ $\displaystyle
q^{7}$ $\displaystyle+2$ $\displaystyle q^{8}$ $\displaystyle+4$
$\displaystyle q^{9}$ $\displaystyle+5$ $\displaystyle q^{10}$
$\displaystyle+2$ $\displaystyle q^{11}$ $\displaystyle+0$ $\displaystyle
q^{12}$ $\displaystyle+4$ $\displaystyle q^{13}$ $\displaystyle+\ldots$
$\displaystyle f_{4}=0$ $\displaystyle q^{1}$ $\displaystyle-2$ $\displaystyle
q^{2}$ $\displaystyle-6$ $\displaystyle q^{3}$ $\displaystyle+2$
$\displaystyle q^{4}$ $\displaystyle+0$ $\displaystyle q^{5}$
$\displaystyle+2$ $\displaystyle q^{6}$ $\displaystyle+2$ $\displaystyle
q^{7}$ $\displaystyle-5$ $\displaystyle q^{8}$ $\displaystyle+0$
$\displaystyle q^{9}$ $\displaystyle+0$ $\displaystyle q^{10}$
$\displaystyle-2$ $\displaystyle q^{11}$ $\displaystyle-6$ $\displaystyle
q^{12}$ $\displaystyle-2$ $\displaystyle q^{13}$ $\displaystyle+\ldots$

each of whose odd-power coefficients are all even, proving that none of
$T_{2},T_{4},T_{6}$ or $T_{8}$ are in $\mathbb{T}^{\operatorname{an}}$ plus
the other $3$. But a calculation up to the Sturm bound of $109$ proves that
there are no other modular forms with all odd-power coefficients and
coefficients of $q^{2},q^{4},q^{6},q^{8}$ all even but some other coefficient
is odd. Therefore $\mathbb{T}=2\mathbb{T}+\langle
T_{2},T_{4},T_{6},T_{8}\rangle$, so $\mathbb{T}/2\mathbb{T}$ is generated as
an $\mathbb{F}_{2}$-vector space by $T_{2},T_{4},T_{6},T_{8}$. By Lemma 3.1,
$\mathbb{T}/\mathbb{T}^{\operatorname{an}}$ is a quotient of
$\mathbb{T}/2\mathbb{T}$, but from the above forms $T_{2},T_{4},T_{6},T_{8}$
are independent in $\mathbb{T}/\mathbb{T}^{\operatorname{an}}$ so the index of
$\mathbb{T}^{\operatorname{an}}$ in $\mathbb{T}$ must be exactly $2^{4}=16$.

## References

  * [Car94] Henri Carayol.  Formes modulaires et représentations galoisiennes à valeurs dans un anneau local complet.  In $p$-adic monodromy and the Birch and Swinnerton-Dyer conjecture (Boston, MA, 1991), volume 165 of Contemp. Math., pages 213–237. Amer. Math. Soc., Providence, RI, 1994.
  * [CE09] Frank Calegari and Matthew Emerton.  Elliptic curves of odd modular degree.  Israel J. Math., 169:417–444, 2009.
  * [CL84] H. Cohen and H. W. Lenstra, Jr.  Heuristics on class groups of number fields.  In Number theory, Noordwijkerhout 1983 (Noordwijkerhout, 1983), volume 1068 of Lecture Notes in Math., pages 33–62. Springer, Berlin, 1984.
  * [DDT97] Henri Darmon, Fred Diamond, and Richard Taylor.  Fermat’s last theorem.  In Elliptic curves, modular forms & Fermat’s last theorem (Hong Kong, 1993), pages 2–140. Int. Press, Cambridge, MA, 1997.
  * [Edi97] Bas Edixhoven.  Serre’s conjecture.  In Modular forms and Fermat’s last theorem (Boston, MA, 1995), pages 209–242. Springer, New York, 1997.
  * [Edi06] Bas Edixhoven.  Comparison of integral structures on spaces of modular forms of weight two, and computation of spaces of forms mod 2 of weight one.  J. Inst. Math. Jussieu, 5(1):1–34, 2006.  With appendix A (in French) by Jean-François Mestre and appendix B by Gabor Wiese.
  * [Kat73] Nicholas M. Katz.  $p$-adic properties of modular schemes and modular forms.  In Modular functions of one variable, III (Proc. Internat. Summer School, Univ. Antwerp, Antwerp, 1972), pages 69–190. Lecture Notes in Mathematics, Vol. 350, 1973.
  * [Kat77] Nicholas M. Katz.  A result on modular forms in characteristic $p$.  In Modular functions of one variable, V (Proc. Second Internat. Conf., Univ. Bonn, Bonn, 1976), pages 53–61. Lecture Notes in Math., Vol. 601, 1977.
  * [KM19] Kiran Kedlaya and Anna Medvedovsky.  Mod-2 dihedral galois representations of prime conductor.  The Open Book Series, 2(1):325–342, jan 2019.
  * [KW09] Chandrashekhar Khare and Jean-Pierre Wintenberger.  Serre’s modularity conjecture. I.  Invent. Math., 178(3):485–504, 2009.
  * [Lip16] Michael Lipnowski.  On bhargava’s heuristics for $\mathbf{GL}_{2}(\mathbf{F}_{p})$-number fields and the number of elliptic curves of bounded conductor.  arXiv preprint arXiv:1610.09467, 2016.
  * [Maz77] B. Mazur.  Modular curves and the Eisenstein ideal.  Inst. Hautes Études Sci. Publ. Math., 47:33–186 (1978), 1977\.
  * [Ser77] J.-P. Serre.  Modular forms of weight one and Galois representations.  In Algebraic number fields: $L$-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975), pages 193–268, 1977.
  * [Ste07] William Stein.  Modular forms, a computational approach, volume 79 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2007.  With an appendix by Paul E. Gunnells.
  * [Suz77] Michio Suzuki.  Gun ron. Vol. 1, volume 18 of Gendai Sūgaku [Modern Mathematics].  Iwanami Shoten, Tokyo, 1977.
  * [Tay20] Noah Taylor.  On Seven Conjectures of Kedlaya and Medvedovsky.  Preprint, 2020.
  * [Wie04] Gabor Wiese.  Dihedral Galois representations and Katz modular forms.  Doc. Math., 9:123–133, 2004.
  * [Wie14] Gabor Wiese.  On Galois representations of weight one.  Doc. Math., 19:689–707, 2014.
  * [Wil88] A. Wiles.  On ordinary $\lambda$-adic representations associated to modular forms.  Inventiones mathematicae, 94(3):529–574, 1988.
  * [Wil95] Andrew Wiles.  Modular elliptic curves and Fermat’s last theorem.  Ann. of Math. (2), 141(3):443–551, 1995.