Hi Sage-Devel, This email will focus entirely on functionality present in Magma that is not available in Sage. We will almost entirely ignore questions of efficiency for this email.
We follow the magma "Handbook" Version 2.15 from December 2008. http://magma.maths.usyd.edu.au/magma/htmlhelp/MAGMA.htm For each section of that handbook we list areas where Magma is functionally ahead of Sage in a significant way. We're not getting bogged down in details, but explaining in rough strokes the main functional areas where Magma has capabilities that Sage doesn't. If as you read the below you have any extra knowledge about a particular area, please respond to this email (or email me offlist). If you're interested in helping with one of the projects, but aren't listed below, please respond too (or mail me offlist). Thanks! I. The Magma Language Sage can't interpret programs written in the Magma language yet. Fortunately, Python is fairly close to Magma as a language. "There's a nice lexical analyzer/parser package in python called PLY (which is GPL'ed), that might be nice to include in Sage, if, in the future, people might be motivated to write translators from other languages to SAGE. A lot of the difficulty in getting automated translation from Magma, is a kind of dynamic type inference -- it goes in the compiler literature under the name of "partial execution". It's an ambitious project but doable." -- Victor Miller Project: Write a parser that could run any Magma program, assuming the functionality it requires is available in the Sage library. Robert Bradshaw, lead developer of the Cython compiler, has expressed to me a strong interest in writing such a parser once he finishes his Ph.D., if funding were available. II. Sets, Sequences, and Mappings I think Sage has everything that Magma has here, and more. III. Basic Rings and Linear Algebra * Sage still doesn't implement automatic coercions between finite fields of characteristic p. Recent work of Lenstra, de Smit, etc., on this problem suggests a good theoretical framework in which to design a good algorithm. PROJECT: Implement automatic coercions between finite fields. * Multivariate polynomial rings have an optimized F4 in Magma, but not in Sage. PROJECT: Implement an optimized F4. (Yes, everybody and their dog has tried and failed, but Allan Steel did it back in 2002, so somebody else can.) * Fast Groebner basis over Z and Z/nZ. This will be in Sage 4.1, since the Singular team made that a major priority. IV. Lattices and Quadratic Forms * Sage has no database of lattices PROJECT: Create a database of lattices. * There is no Lattice data type in Sage, though most functionality for lattices in Magma is also available in Sage, e.g., in the quadratic froms and free modules code. There has been much talk about creating a lattice type for Sage and organizing the lattice functionality around it. PROJECT: Create a Lattice class in Sage. V. Global Arithmetic Fields * Computing Galois groups of number fields of arbitrary degree PROJECT: Implement this new Galois groups algorithm. Is it published? * Class field theory -- Sage doesn't do anything in particular (e.g., compute ray class groups and ray class fields), though PARI does, so this is likely mainly a matter of exposing more functionality from PARI. PROJECT: Expose Pari's class field theory functionality. * Algebraic function fields -- Sage can do almost nothing (even robust computation of Riemann-Roch spaces isn't there). I don't think Sage even has optimized arithmetic in any algebraic function fields. Florian Hess did a Ph.D. (in German) on the algorithms for function fields. PROJECT: Implement Hess's algorithm(s). * Class field theory for algebraic function fields. Since Sage doesn't have algebraic function fields, it also doesn't have class field theory for them. PROJECT: Implement class field field for function fields. * Artin representations -- there is a small (?) package in Magma for computing with representations of Gal(Qbar/Q) into GL_n(C) with finite image. Sage doesn't have a nice object like this. PROJECT: Create a similar class in Sage. Make sure to hook into Dokchitser's L-functions code, plotting code, etc. VI. Local Arithmetic Fields * Factorization over extension of p-adic fields isn't in Sage yet. PROJECT: Implement Round 4 (David Roe is currently working on this.) * Sage doesn't do Newton polygons. PROJECT: Implement Newton Polygons (David Roe has mostly done this, but not included it in Sage yet) * Sage doesn't do arbitrary p-adic extensions, though it supports some extensions (this will come once the previous two are done) * Galois theory and ramification groups for p-adic extensions (needs the previous features) * Local class field theory (built upon the previous features: this is a ways out). * Magma's linear algebra over p-adics is better than in Sage. PROJECT: Design and implement good algorithms for linear algebra over p-adics (subtle and interesting research area). * Galois rings PROJECT: Implement Galois rings over p-adic fields. Probably not too hard. * Lazy multivariate power series with possibly fractional exponents PROJECT: Implement them. We've tried to design these before, but got tangled up in details, so following the Magma interface and definitions closely is probably a good idea. VII. Modules * Sage has nothing for modules over Dedekind domains (except over ZZ): this is an extremely important building block for certain algorithms (e.g., arithmetic in quaternion algebras over number fields), so needs to get implemented. I recently wrote code for general modules over ZZ, but it isn't in Sage yet. PROJECT: Finish modules over ZZ, optimize PROJECT: Extend modules over ZZ to modules over a PID PROJECT: Implement modules over Dedekind domains (via pseudobasis). VIII. Finite Groups; Finitely-Presented Groups * I'm not enough of a group theorist to appreciate differences between what Sage provides via GAP and Magma. They seem pretty similar to me for group theory. Sage exposes much of GAP's functionality for groups. PROJECT: Rewrite the C kernel of GAP so that Sage can directly manipulate GAP objects at the C level, thus completely avoiding pexpect. Basically this might mean re-implementing the GAP interpreter in C/Cython. PROJECT: Implement in Cython native group theory functionality. X. Coxeter Groups; Lie Groups * I have the impression that our Coxeter code is extremely good, and is under active development (e.g., by Dan Bump). * I'm not sure about the situation for Lie groups. XII. Algebras * Generic algebras -- we have them, but they are slow and not used much. Little of interest is supported. PROJECT: Create a fast optimized Cython implementation of free algebras and their quotients. Basically, rewrite sage/algebras/free*. Make sure that all functionality in Magma for these is also present in Sage. * Ideal theory of quaternion algebras over *number fields*. This is extremely high on my todo list. We have very fast basic arithmetic, but need ideal theory over Dedekind domains, etc. PROJECT: Implement quaternion algebras over over number fields, following the algorithms and strategy John Voight used for Magma. * Quantum groups, Lie algebras, Universal enveloping algebras -- pretty sure we don't have this in Sage. XIII. Representation Theory * Characters of finite groups; GAP has this, of course, but I don't think Sage nicely wraps it. PROJECT: Wrap more of GAP's functionality, in particular characters of finite groups. XIV. Commutative Algebra * Modules over multivariate rings. This is a big Gap in functionality in Sage; presumably Singular can help fill it in? PROJECT: If Singular can do this well, wrap it. If not, consider Macaulay 2 which certainly can. * Differential rings: I think we have nothing in Sage. PROJECT: Add support for differential rings. Again, Singular or Macaulay2? * Invariant theory: I think we have nothing in Sage. PROJECT: Add support for invariant theory. Maybe this in GAP + Singular as a package. XV. Algebraic Geometry * General algebraic curves are far more well developed in Magma. PROJECT: Finish improving doctest coverage of algebraic curves in Sage. Fill in all the generic missing functionality. (Alex Ghitza has been working on this.) * Resolution of singularities of algebraic curves -- we don't have this (?). PROJECT: Implement this or wrap functionality from Singular (?). * Algebraic surfaces -- sage has nothing special PROJECT: Implement same algorithms as from Magma for algebraic surfaces. XVI. Arithmetic Geometry * Rational curves and conics -- sage doesn't have any special code for them. PROJECT: These are mostly "easy", but with a couple of important algorithms, which I think are already in Sage (as part of C libraries, e.g., Stoll's code). * Elliptic curves -- Sage doesn't have 3-descent, 4-descent, 8-descent; Heegner points are not as well developed yet. Sage doesn't have its own 2-descent. PROJECT: Implemt 2-descent, 3-descent, 4-descent, and 8-descent in Sage. (Robert Miller just implemented most of 2-descent and the results are amazing.) PROJECT: Implement a package for computing with and doing research on Heegner and higher Heegner points. Include functionality related to Gross-Zagier L-functions. (Robert Bradshaw is doing this as part of his Ph.D. thesis.) * Sage doesn't have all pairings for elliptic curves over finite fields, e.g., some subset of Weil, Tate, EtaT, Etaq, Ate, ReducedAte, Ateq is missing. PROJECT: Fill in missing pairings. * Elliptic curves over function fields -- we don't have anything at all. PROJECT: Implement package for elliptic curves over function fields and Drinfeld modular curves. (Sal Butt whose Ph.D. was on elliptic curves over function fields with Fernando R-Villegas, will be my postdoc for the next few years.) * Models of genus one curves -- Sage has nothing useful here, which is very annoying. PROJECT: Implement all the standard models (as defined by what Magma supports), and transitions between them. * Hyperelliptic curves -- Sage has nothing really for jacobian over number fields, effective Chabauty. Sage also doesn't implement the analytic Jacobians package from Magma. PROJECT: Make the group law on hyperelliptic Jacobians very fast. PROJECT: Implement effective Chabuaty. PROJECT: Implement 2-descent on Jacobians of Hyperelliptic curves over QQ. XVII. Modular Arithmetic Geometry (?) * Arithmetic fuchsian groups and Shimura curves -- John Voights code; Sage doesn't have this at all. PROJECT: Implement a package for computing with Shimura curves in Sage. XVIII. Geometry * Weight 1 modular forms PROJECT: Implement standard algorithm(s) for computing weight 1 modular forms. See Tate's algorithm from Springer Lecture Notes 1585 and an algorithm of Kevin Buzzard. * Hilbert modular forms -- requires quaternion algebras over real fields. PROJECT: Implement computation of Hilbert modular forms following Lassina Dembele's papers. This has to wait for quaternion algebras over number fields. XIX. Combinatorics * Finite planes and incidence geometry -- I think Sage doesn't have them. (?) PROJECT: Add support to Sage for finite planes and incidence geomtry. XX. Coding Theory * Algebraic-Geometric codes -- I'm sure we're missing a lot PROJECT: Implement standard range of AG codes. Requires more algebraic curve functionality, some of which isn't available in the open source world. * Quantum codes XXI.Cryptography Strangely, Sage seems to have much more crypto functionality than Magma. We have way way more. The word encryption doesn't appear in any nontrivial way in the Magma reference manual. XXII. Optimization We have a lot more in Sage... --- OTHER REMARKS: I good systematic and verifiable approach to this project would be to make the goal to port every single example in the Magma Handbook to Sage. -- William Stein Associate Professor of Mathematics University of Washington http://wstein.org --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
