Galois representations associated to modular forms
Theorem (Deligne). Let $f = \sum a_nq^n\in S_k(\Gamma_1(N))$ be a newform. Put $K_f = \mathbf{Q}(a_1, a_2, \ldots)$ and let $\lambda\mid l$ be a prime of $K_f$. Then there exists a continuous representation \[\rho\colon \operatorname{Gal}(\overline{\QQ}/\QQ)\to \operatorname{GL}_2(\mathbf{F}_\lambda)\] that is unramified outside $Nl$ such that for all primes $p\nmid N l$ we have \[\operatorname{Tr}(\rho(\operatorname{Frob}_p)) \equiv a_p\bmod \lambda.\]
Our favourite cusp form:
\[\Delta = q\prod_{n\geq 1}\left(1-q^n\right)^{24} = \sum_{n\geq 1}\tau(n)q^n = q - 24q^2 + 252q^3 - 1472q^4 + 4830q^5 + \cdots \in S_{12}(\operatorname{SL}_2(\mathbf{Z})).\]
{{{id=34| S = CuspForms(1, 12) /// }}} {{{id=104| S /// }}} {{{id=176| S.newforms() /// }}} {{{id=102| Delta = S.newforms()[0] /// }}} {{{id=103| Delta.q_expansion(11) /// }}} {{{id=109| /// }}}
In this case we have for each prime number $l$ a continuous representation \[\rho_l\colon\operatorname{Gal}(\overline{\QQ}/\QQ)\to \operatorname{GL}_2(\mathbf{F}_l)\] such that for each prime $p\not=l$ we have \[\operatorname{Tr}(\rho(\operatorname{Frob}_p)) \equiv \tau(p) \bmod l.\]
Theorem. For $l\not\in\{2,3,5,7,23,691\}$ the image of $\rho_l$ contains $\operatorname{SL}_2(\mathbf{F}_l)$.
Example. We have $\tau(p)\equiv 1 + p^{11}\bmod 691$. Thus \[
\rho_{691} \sim \left(\begin{array}{cc} 1 & 0 \\ 0 & \chi_l^{11} \end{array} \right)
\quad\mbox{where }\chi_l\colon \operatorname{Gal}(\overline{\QQ}/\QQ)\rightarrow
\operatorname{Gal}(\mathbf{Q}(\zeta_l)/\mathbf{Q})\stackrel{\sim}{\rightarrow} \mathbf{F}_l^\times\colon \operatorname{Frob}_p\mapsto p.\]
Computational aspects of modular forms and Galois representations
Theorem (Couveignes, Edixhoven, R. de Jong, Merkl). There exists a deterministic algorithm that on input a prime number $l$ computes $\rho_l$ in time polynomial in $l$.
Corollary. There exists a deterministic algorithm that on input two prime numbers $p\not=l$ computes $\tau(p)\bmod l$ in time polynomial in $\log p$ and $l$.
Corollary. There exists a deterministic algorithm that on input a prime number $p$ computes $\tau(p)$ in time polynomial in $\log p$.
What does 'computing $\rho_l$' mean?
There is a number field $K_l$ such that $\rho_l$ factors through $\operatorname{Gal}(K_l/\mathbf{Q})$:\[\rho_l\colon\operatorname{Gal}(\overline{\QQ}/\QQ) ↠ \operatorname{Gal}(K_l/\mathbf{Q}) ↣ \operatorname{GL}_2(\mathbf{F}_l).\]
Computing $\rho_l$ essentially means: computing a polynomial $P_l\in\mathbf{Q}[x]$ with splitting field $K_l$.
Modular Jacobians
Theorem. For $l\not\in\{2, 3, 5, 7, 691\}$ there is a $2$-dimensional $\mathbf{F}_l$-linear subspace $V_l$ of $J_1(l)(\overline{\mathbf{Q}})[l]$ such that $\rho_l$ is given by the action of $\operatorname{Gal}(\overline{\mathbf{Q}}/\mathbf{Q})$ on $V_l$.
Here, $J_1(l)$ is the Jacobian of the modular curve $X_1(l)$. Choosing a suitable function $h\in\mathbf{Q}(J_1(l))$ one can define \[P_l(x) := \prod_{P\in V_l-\{0\}}(x-h(P)).\]
{{{id=15| mgr = ModularGaloisRepresentation(Delta, 13); mgr /// }}} {{{id=16| J = mgr.jacobian(); J /// }}} {{{id=108| /// }}}To compute $P_l$, use numerical approximations!
The Abel-Jacobi isomorphism
Let $f_1, \ldots, f_g$ be a basis of $S_2(\Gamma_1(l))$ and let $\Lambda\subset\mathbf{C}^g$ be the corresponding period lattice, i.e. \[\Lambda = \left\{\int_\gamma (f_1,\ldots, f_g)\frac{dq}{q}\colon\, \gamma \text{ closed path on }X_1(l)\right\}.\]
{{{id=70| J.period_lattice(prec=100) /// }}} {{{id=115| /// }}}We have an isomorphism \[\operatorname{AJ}\colon J_1(l)(\mathbf{C})\stackrel{\sim}{\rightarrow}\mathbf{C}^g/\Lambda\] defined by \[Q_1 + \cdots + Q_g - gQ \mapsto \sum_i \int_Q^{Q_i}(f_1,\ldots,f_g)\frac{dq}{q}.\]
The computation proceeds in a few steps:
In explicit computations we use the projective representation \[\tilde\rho_l\colon\operatorname{Gal}(\overline{\mathbf{Q}}/\mathbf{Q})\to\operatorname{PGL}(\mathbf{F}_l),\] with corresponding polynomial \[\tilde{P}_l(x) := \prod_{L\in\mathbf{P}(V_l)}\Big(x\,-\!\!\!\!\sum_{P\in L-\{0\}}h(P)\Big)\in\mathbf{Q}[x].\] Compare degrees: \[\deg(P_l) = l^2 - 1\quad\text{and}\quad\deg(\tilde{P}_l) = l+1.\]
{{{id=23| pol = mgr.smaller_polynomial(); pol /// }}}Theorem (Khare, Wintenberger, Kisin). All irreducible odd continuous 2-dimensional representations of $\operatorname{Gal}(\overline{\mathbf{Q}}/\mathbf{Q})$ are modular (Serre's conjecture).
{{{id=24| G = QQ['x'](pol).galois_group(); G # Requires optional packages kash and database_gap /// }}} {{{id=26| G.is_isomorphic(PGL(2, 13)) /// }}} {{{id=27| K = NumberField(pol, name='a') /// }}} {{{id=29| OK = K.maximal_order() /// }}} {{{id=30| OK.discriminant().factor() /// }}} {{{id=134| /// }}} {{{id=94| /// }}}Computing in $J_1(l)_{\mathbf{F}_{p^r}}$ (in progress, with Peter Bruin)
Use Khuri-Makdisi's algorithm for computing in Jacobians of curves: Peter has just explained how this works. Compute $P_l$ (or $\tilde{P}_l$) by computing it modulo many small primes $p$.
{{{id=80| tau_rep = TauRepresentation(11); tau_rep # Apply trac 11685 and 11684 first /// }}} {{{id=97| p = 23; tau_rep_p = tau_rep.local_representation(23); tau_rep_p /// }}} {{{id=84| J = tau_rep_p.jacobian_base_ext(); J /// }}} {{{id=86| P = J.random_element() /// }}} {{{id=136| P /// }}} {{{id=141| P in J /// }}} {{{id=142| P == 0 /// }}} {{{id=144| J.order() /// }}} {{{id=143| 12100 * P == 0 /// }}} {{{id=139| X = J.curve(); X /// }}} {{{id=147| X.degree() /// }}} {{{id=140| D = P.normalised_divisor() /// }}} {{{id=148| D.basis_matrix() /// }}} {{{id=150| V = X.sections(1) /// }}} {{{id=155| psi = BundledCurveRationalFunction(X, 1, V[0], V[1]) /// }}} {{{id=157| pol = tau_rep_p.polynomial(psi) /// }}} {{{id=175| pol /// }}}This polynomial corresponds to the action of $\rho(\operatorname{Frob}_p)$ on $V_l\approx \mathbf{F}_l^2$. Its irreducible factors correspond to the cycles. We also have \[\operatorname{charpol}(\rho(\operatorname{Frob}_p)) = x^2 - \tau(p) x + p^{11}.\]
{{{id=158| pol.factor() /// }}} {{{id=161| mat = Matrix(GF(11), [[tau(p), p^11],[-1, 0]]); mat /// }}} {{{id=162| mat.multiplicative_order() /// }}} {{{id=180| /// }}}