����;� TeX output 2001.07.23:1540������x�������=������G[��D��t�qG�cmr17�Some�B�Mo���dular�Degree�and�Congruence������Mo���dulus�B�Computations��#�􍍍�������X�Qffcmr12�William��/A.�Stein������&a�����July��/23,�2001��5V��'���N�G�cmbx12�Con��u�ten�ts��b#���'���N�cmbx12�1��8��The��Denitions��>�1���?����'2��8��The��History��%Ο2������'3��8��The��Naiv��e�Algorithms�����3�������8���X�Qcmr12�3.1��S�JA��w��ra�y�to�compute�� ��g�cmmi12�m�����!�2cmmi8�E��
A�������.���	C������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.����֚3������8��3.2��S�JA��w��ra�y�to�compute��c�����E��	6�������.���	C������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.��������.����֚3���?����'�4��8��The��Examples���3������'5��8��The��F���uture��*ʸ4���(V���'�1��D(�The�z�Denitions����'�Let��k�E��=�Q��b�S�e�an�elliptic�curv��re�that�is�an��1���@cmti12�optimal���quotient��of��J�����|{Ycmr8�0����(�N�����E��-��),��where�����'�N��M�=�}i�N�����E��/��is�5the�conductor�of��E���.��Here��J�����0����(�N�@�)�is�the�Jacobian�of�the�algebraic����'curv��re�m_�X�����0����(�N�@�)�and�a�deep�theorem�implies�that�there�is�a�surjectiv�e�morphism����'�����:�Y��X�����0����(�N�@�)��#!",�
cmsy10�!��E���.��The���condition�that��E�7��is�optimal�means�that�the�induced����'map��������$�K�cmsy8���V�:�UR�J�����0����(�N�@�)��!��E����has�(geometrically)�connected�k��rernel.�����'�Denition��1.1.��The���mo��ffdular�35de�gr�e�e��of��E����is�����ƹ��m�����E��
�ڹ=��URdeg��
(��n9�)�:�������1����*�x�������=�������8��One���reason�that�the�mo�S�dular�degree�is�w��rell�w�orth�thinking�ab�S�out�is�that�����'an���assertion�ab�S�out�ho��rw��m�����E����gro�ws�relativ�e�to��N�����E����is�equiv��X�alen�t�to�the�ABC����'Conjecture.����8��Let���f��Q�=�UR�f�����E��
�ڹ=�������&��u
cmex10�P�����a�����n���P�q��n9���2�n��	k��2��S�����2����(�����0���(�N�@�))�b�S�e�the�newform�attac��rhed�to��E���.�����'�Denition��1.2.��The���c��ffongruenc�e�35mo�dulus��of��E����is�� ���(p�c�����E��
�ڹ=�UR#�������q��������ō���S�����2����(�����0���(�N�@�)�;����Z�)����[��z�B���
�΍����Z�f��+���(�Z�f�G��)������?�������O�X��q����Z���;��"Ow��'�where���(�Z�f�G��)����2�?��:�is�the�unique��T���=��Z�[��:���:�:��ʞT�����n����N�:���:�:��r�]-mo�S�dule���complemen��rt�of��Z�f�;��in����'�S�����2����(�����0���(�N�@�)�;����Z�).�8�Equiv��X�alen��rtly��V,�����c<��c�����E��
�ڹ=���URmax���3|�f�c�UR�:��f�����P����Q����԰����9�=�����G��g�n-�(�mo�S�d���B�c�)����for�some��g�Ë�2�UR�(�Z�f�G��)�����?����k�P�g�:��(V���'�2��D(�The�z�History��b#�����8�������D_��<��M�t�1984:�8�??�������8������D_��1984:�'ֹDon��#Zagier�wrote�the�often-cited�pap�S�er��Mo��ffdular��p�ar�ametriza-����D_�tions�^of�el���liptic�curves��'�(1985),��in�whic��rh�he�ga�v�e�an�algorithm�to�compute����D_��m�����E��0�(sometimes?).�8�The��pap�S�er�incluced�������Q�u�{����^9q�A��result�of�Rib�S�et:�����^9q�Theorem��2.1�(Rib�`et).��If�35�N�����E��`��is�prime,�then������;��m�����E��
�ڹ=�UR�c�����E��-��:�������Q�u�{����^9q�It��also�said�����"��c�����E��
���j�UR�m�����E��-��:�������8������D_��1998:�-��F��Vrey���and�M�S����vuller�published�a�w��ronderful�surv�ey:�-��A��2rithmetic�Mof����D_�mo��ffdular�35curves�and�applic�ations�.�������Q�u�{����^9q�They���ask:��V�Question�E�4.4�:�Let��E�J��b�S�e�an�optimal�quotien��rt�of�an�y����^9qconductor.�8�Do�S�es���m�����E��
�ڹ=�UR�c�����E��-��?��������Q�u�{����^9q�They��=remark�that��c�����E��
p��j�C?�m�����E���Źand�giv��re�t�w�o�references�[Rib�S�et�83,����^9qIn��rv�en�tiones]��and�[Zagier�1985].������2����.�x�������=����������8������D_��1995:�BR�Cremona�oawrote�a�Math.��
Comp.�pap�S�er,���and�oacomputed��m�����E����for�����D_�ev��rery��curv�e�of�conductor���UR�N�@�,�where��N�+��is�a�few�thousand.��|�����8������D_��2001:�K}�Mark�s�W��Vatkins,��Jwho�did�a�Ph.D.�on�the�class�n��rum�b�S�er�s�problem����D_�of��Gauss,�Grcomputed��m�����E��/8�for�some�curv��res�with��N�����E���HUGE�,�using�an����D_�algorithm��he�created�from�a�form��rula�of�M.�Flac�h.��'\����'�3��D(�The�z�Naiv��u�e�Algorithms���#���'�6��N�ffcmbx12�3.1��K�cA�ffw���a�y�to�compute����g�ffcmmi12�m��(��
�b>

cmmi10�E���@��'�Use��the�(not-exact!)�8�sequence:�������q�H�����1����(�E��;����Z�)�UR�!��H�����1���(�X�����0���(�N�@�)�;����Z�)��!��H�����1���(�E��;����Z�)�:����'�The�z�comp�S�osition�map�from��H�����1����(�E��;����Z�)�Jh�!��H�����1���(�E��;����Z�)�z�is�m��rultiplication�b�y��m�����E��-��,�����'and�Y��H�����1����(�E��;����Z�)�can�b�S�e�computed�b�ecause�its�image�in��H�����1����(�X�����0���(�N�@�)�;����Z�)�Y�is�satu-����'rated,��Ras��|�E�r��is�optimal.�*'This�algorithm�is�describ�S�ed�in�detail�in�[Kohel-Stein,����'ANTS��IV],��and�amoun��rts�to�nding�\left�and�righ�t�eigen�v�ectors"�and�taking����'their��dot�pro�S�duct.��"􍍑'�3.2��K�cA�ffw���a�y�to�compute��c��(��E�����'�Compute�{��S�����2����(�����0���(�N�@�)�;����Z�)�K����Z�[[�q�n9�]]�to�precision�[�SL���
ދ����2�����(�Z�)�:������0����(�N�@�)]�=�6�using,���e.g.,����'mo�S�dular��sym��rb�ols,�then�use�a�Smith�Normal�F��Vorm�algorithm.��'\����'�4��D(�The�z�Examples��b#��'�These��examples�w��rere�computed�b�y�m�yself�and�Amo�S�d�Agashe.��Or�����8������D_��54B�:��Let��E����b�S�e�the�elliptic�curv��re��y��n9���2�2��߱�+��t�xy���+��y�Ԉ�=�fO�x����2�3��qx���x����2�2���+��x����1.�V�Then����D_��m�����E����=��h2���and��c�����E���=��h6.���In�fact,��it's�easy�to�see�that�3��j��c�����E���}�\b��ry�hand"����D_�b��ry��bwriting�do�wn�the�form��f��a�corresp�S�onding�to��54B���and�the�form��g����D_�corresp�S�onding���to��X�����0����(27)�and�noting�that��f�G��(�q�n9�)�UR���g��(�q��)�6�+��g��(�q�����2�2��.=�)�UP(�mo�S�d���B3).����D_�(Because���of�the�\Sturm�Bound",��Dit�suces�to�c��rhec�k���this�up�to��O�S��(�q��n9���2�19��	nA�).)���>��D_��Hey�z��c�����E��
���6�=�UR�m�����E��-��!!�(�In�fact,��t�c�����E���6�URj����m�����E��-��!!���When�!�w��re�rst�did�this�computation,����D_�Rib�S�et��had�already�men��rtioned�to�us�that�he�had�really�pro�v�ed�that����D_��m�����E��
���j�UR�c�����E��-��,��dnot��Rvice-v��rersa.�nW��Ve�w�ere,��dho�w�ev�er,�extremely��Rsurprised�to�nd����D_�so��quic��rkly�an�example�in�whic�h��c�����E��	��6�=�UR�m�����E��-��.������3�����x�������=����������8������D_��T-shirt�:��&My��Kt-shirt�has��243A���and��243B��on�it.�J�F��Vor��243A�,�w��re�ha�v�e�����D_��m�����E��K�=���9�׮and��c�����E���=���27.���F��Vor��243B�,�w��re�ha�v�e��m�����E��K�=���6�and��c�����E���=���54.���I����D_�designed��^the�t-shirt�man��ry�mon�ths�b�S�efore�I��[knew�that�question�4.4�had����D_�a��negativ��re�answ�er.��������8������D_��242B�:���N��6�=�UR2������11����2�2����.������M�m�����E��
�ڹ=�UR2�����4��V�6�=��c�����E���=�2�����4��j������11����D_�The��failure�is�probably�not�just�a�\small�primes"�phenomenon.����'�Moral:�8�A��little�computation�sometimes�greatly�cleans�the�air.��(V���'�5��D(�The�z�F��aGuture��b#��'�Based�1�on�computations,�CFAmo�S�d�and�I�1zconjectured�and�Rib�et�pro��rv�ed�1�the�fol-�����'lo��rwing��theorem.����'�Theorem�5.1�(Rib�`et,�7�2001).�AW�L��ffet����E�\��b�e�an�el���liptic�curve�of�c�onductor��N�@��.����'If�35�p����2�2��V�,���
msbm10�-�UR�N�t�then���ord���,
����p���j�(�m�����E��-��)�=��ord���N*����p����(�c�����E���)�.����'�New��V��Version�of�\�Question��4.4�.�8�F�or�all��N�����E��
����UR�539,�w��re�ha�v�e�������!�ord���������p�����(�c�����E��-��=m�����E���)�UR����ord���N*����p����(�N�����E��-��)������1�:����'�In��particular,�for��p�UR���5,��do�w��re�ha�v�e�������ord����o����p����̹(�c�����E��-��=m�����E���)�UR���1?����8��Is��this�true�in�general?������4����s���;�x��	�6��N�ffcmbx12�1���@cmti12�,���
msbm10�&��u
cmex10�$�K�cmsy8�#!",�
cmsy10�!�2cmmi8� ��g�cmmi12�|{Ycmr8���N�cmbx12���N�G�cmbx12���g�ffcmmi12�X�Qffcmr12�D��t�qG�cmr17�X�Qcmr12�
�b>

cmmi10�"��������