# Decomposition

The functions `Decomposition` and `NewformDecomposition` express a space of modular symbols as a direct sum of Hecke-stable subspaces.

In the intrinsics below, the `Proof` parameter affects the internal characteristic polynomial computations. If `Proof` is set to `false` and this causes a characteristic polynomial computation to fail, then the sum of the dimensions of the spaces returned by `Decomposition` will be less than the dimension of `M`. Thus setting `Proof` equal to `false` is usually safe.

## `Decomposition(M, bound : parameters): ModSym, RngIntElt -> SeqEnum`

```magma
Proof: BoolElt                    Default: true
```

The decomposition of the space of modular symbols $M$ with respect to the Hecke operators $T_p$ with $p$ coprime to the level of $M$ and $p \le$ `bound`. If `bound` is too small, the constituents of the decomposition are not guaranteed to be “irreducible”, in the sense that they can not be decomposed further into kernels and images of Hecke operators $T_p$ with $p$ prime to the level of $M$. When `Decomposition` is called, the result is cached, so each successive call results in a possibly more refined decomposition.

Important Note: In some cases `NewformDecomposition` is significantly faster than `Decomposition`.

## `NewformDecomposition(M : parameters): ModSym -> SeqEnum`

```magma
Proof: BoolElt                    Default: true
```

Unsorted decomposition of the space of modular symbols $M$ into factors corresponding to the Galois conjugacy classes of newforms of level some divisor of the level of $M$. We require that `IsCuspidal(M)` is `true`.

## `AssociatedNewSpace(M): ModSym -> ModSym`

The space of modular symbols corresponding to the Galois-conjugacy class of newforms associated to the space of modular symbols $M$. The level of the newforms is allowed to be a proper divisor of the level of $M$. The space $M$ must have been created using `NewformDecomposition`.

## `SortDecomposition(D): [ModSym] -> SeqEnum`

Sort the sequence $D$ of spaces of modular symbols with respect to the `lt` comparison operator.

## `IsIrreducible(M): ModSym -> BoolElt`

Returns `true` if and only if `Decomposition(M)` has cardinality $1$.

## `M1 lt M2: ModSym, ModSym -> BoolElt`

The ordering on spaces of modular symbols is determined as follows:

**(1)**
This rule applies only if `NewformDecomposition` was used to construct both of $M_1$ and $M_2$: If `Level(AssociatedNewSpace(M1))` is not equal to that of $M2$ then the $M_i$ with larger associated level is first.

**(2)**
The smaller dimension is first.

**(3)**
The following applies when the weight is $2$ and the character is trivial: Order by $W_q$ eigenvalues, starting with the *smallest* $p\mid N$, with the eigenvalue $+1$ being less than the eigenvalue $-1$.

**(4)**
Order by ${\operatorname{abs}}({\rm trace}(a_p))$, with $p$ not dividing the level, and with positive trace being smaller in the event that the two absolute values are equal.

Rule (3) is included so that our ordering extends the one used in (most of!) [[Cremona, 1997](../../references.md#cite-cremona-algs)].

## `Example: Decomposition (ex-25e8b4)`

First, we compute the decomposition of the space of modular symbols of weight $2$ and level $37$.

```magma
> M := ModularSymbols(37,2); M;
Full modular symbols space for Gamma_0(37) of weight 2 and dimension 5
over Rational Field
> D := Decomposition(M,2); D;
[
     Modular symbols space for Gamma_0(37) of weight 2 and dimension 1
     over Rational Field,
     Modular symbols space for Gamma_0(37) of weight 2 and dimension 2
     over Rational Field,
     Modular symbols space for Gamma_0(37) of weight 2 and dimension 2
     over Rational Field
]
> IsIrreducible(D[2]);
true
> C := CuspidalSubspace(M); C;
Modular symbols space for Gamma_0(37) of weight 2 and dimension 4 over
Rational Field
> N := NewformDecomposition(C); N;
[
     Modular symbols space for Gamma_0(37) of weight 2 and dimension 2
     over Rational Field,
     Modular symbols space for Gamma_0(37) of weight 2 and dimension 2
     over Rational Field
]

```

Next, we use `NewformDecomposition` to decompose a space having plentiful old subspaces.

```magma
> M := ModularSymbols(90,2); M;
Full modular symbols space for Gamma_0(90) of weight 2 and dimension
37 over Rational Field
> D := Decomposition(M,11); D;
[
     Modular symbols space for Gamma_0(90) of weight 2 and dimension 11
     over Rational Field,
     Modular symbols space for Gamma_0(90) of weight 2 and dimension 4
     over Rational Field,
     Modular symbols space for Gamma_0(90) of weight 2 and dimension 2
     over Rational Field,
     Modular symbols space for Gamma_0(90) of weight 2 and dimension 2
     over Rational Field,
     Modular symbols space for Gamma_0(90) of weight 2 and dimension 4
     over Rational Field,
     Modular symbols space for Gamma_0(90) of weight 2 and dimension 8
     over Rational Field,
     Modular symbols space for Gamma_0(90) of weight 2 and dimension 6
     over Rational Field
]
> C := CuspidalSubspace(M); C;
Modular symbols space for Gamma_0(90) of weight 2 and dimension 22
over Rational Field
> N := NewformDecomposition(C); N;
[
     Modular symbols space for Gamma_0(90) of weight 2 and dimension 2
     over Rational Field,
     Modular symbols space for Gamma_0(90) of weight 2 and dimension 2
     over Rational Field,
     Modular symbols space for Gamma_0(90) of weight 2 and dimension 2
     over Rational Field,
     Modular symbols space for Gamma_0(90) of weight 2 and dimension 4
     over Rational Field,
     Modular symbols space for Gamma_0(90) of weight 2 and dimension 4
     over Rational Field,
     Modular symbols space for Gamma_0(90) of weight 2 and dimension 8
     over Rational Field
]

```

The above decomposition uses all of the Hecke operator; it suggests that the decomposition `D` is not as fine as possible. Indeed, `D[7]` breaks up further:

```magma
> Decomposition(D[7],11);
[
    Modular symbols space for Gamma_0(90) of weight 2 and dimension 6
    over Rational Field
]
> Decomposition(D[7],19);
[
     Modular symbols space for Gamma_0(90) of weight 2 and dimension 4
     over Rational Field,
     Modular symbols space for Gamma_0(90) of weight 2 and dimension 2
     over Rational Field
]

```

The function `AssociatedNewSpace` allows us to see where each of these subspace comes from. By definition they each arise by taking images under the degeneracy maps from a single Galois-conjugacy class of newforms of *some* level dividing $90$.

```magma
> [Level(AssociatedNewSpace(A)) : A in N];
[ 90, 90, 90, 45, 30, 15 ]
> A := N[4];
> qEigenform(AssociatedNewSpace(A),7);
q + q^2 - q^4 - q^5 + O(q^7)
> qExpansionBasis(A,7);
[
    q - 2*q^4 - q^5 + O(q^7),
    q^2 + q^4 + O(q^7)
]

```