3.0

Release Tour

Sage 3.0 was released on April 21st, 2008 (changelog), 277 tickets (PRs) merged, 48 contributors. For the official, comprehensive release notes, see the HISTORY.txt file that comes with the release.

Random Numbers

Sage has a new random number framwork (by Carl Witty) with a global random number state, so that results using pseudo-random numbers can be reproducible. Randomized doctests are now actually tested, instead of having their results ignored. Use set_random_seed(n) to set a new random number seed, and initial_seed() to find the most recently set seed (or the seed set at Sage startup, if no new seed has been set). For much more information on the new random number framework, type sage.misc.randstate?.

GCC 4.3 Support

Sage 3.0 has full GCC 4.3 support, which means that every included package was fixed to compile with GCC 4.3 and the changes were pushed upstream.

New Default Binaries

• RedHat Enterprise Linux 5/Itanium
• Ubuntu 6.06 Long Term Support
• Arch Linux

Boolean Polynomials

The PolyBoRi library was updated to version 0.3.1 leading to greater stability and better performance. The interface to PolyBoRi was also improved and the documentation updated. Also the conversion to/from PolyBoRi, Singular and Magma was greatly improved.

Example Usage:

sage: sr = mq.SR(1,1,1,4,gf2=True) # create a small scale AES system
sage: F,s = sr.polynomial_system()
sage: P = F.ring() # polynomial ring
sage: B = BooleanPolynomialRing(P.ngens(),P.variable_names(),order='lex') # quotient ring
sage: IB = Ideal([B(f) for f in F]) # create ideal
sage: IM = IB._magma_() # convert to Magma
sage: IS = IB._singular_() # convert to Singular
sage: gb = IS.groebner() 
sage: P.change_ring(order='lex') == B.cover_ring()
True

Modular Abelian Varieties

Sage now has support for computing with modular abelian varieties, including computing endomorphism rings, intersections, kernels of morphisms, etc., with complete documentation.

sage: J = J0(389)
sage: D = J.decomposition()
sage: D
[
Simple abelian subvariety 389a(1,389) of dimension 1 of J0(389),
Simple abelian subvariety 389b(1,389) of dimension 2 of J0(389),
Simple abelian subvariety 389c(1,389) of dimension 3 of J0(389),
Simple abelian subvariety 389d(1,389) of dimension 6 of J0(389),
Simple abelian subvariety 389e(1,389) of dimension 20 of J0(389)
]
sage: G, _ = D[4].intersection(D[0] + D[1] + D[2] + D[3])
sage: G
Finite subgroup with invariants [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 40, 40] over QQ of Simple abelian subvariety 389e(1,389) of dimension 20 of J0(389)

Increased Doctest Coverage

We dramatically increased our automated testing and example suite so that 51.5 % of functions have autotested examples. There are now nearly 60,000 lines of input examples. In February our testing was in the 30% range. This was a huge amount of work by many many Sage developers, and it has the practical impact that when you type foo? it is nearly twice as likely that you'll see a helpful example.

$ cd devel/sage/sage
$ ../../../sage -coverage .
...
Overall weighted coverage score:  51.5%
Total number of functions:  19514

R Pexpect Interface

There is now a new interface to R that uses a pseudotty; this is a completely different alternative to rpy, which makes it possible for the web-based Sage notebook to work as an R GUI, and also makes it so any R command can be used from Sage 100% exactly as in R. It is still clunky and has numerous issues, but it is fairly usable, documented, and has a test suite.

Crystals

FIXME

Laurent Polynomials

FIXME

Full Changelog: 2.11...3.0

2.11

Release Tour

Sage 2.11 was released on March 30, 2008. For the official, comprehensive release notes, see the HISTORY.txt file that comes with the release. For the latest changes see sage-2.11.txt.

ATLAS

Michael Abshoff and Burcin Erocal upgraded ATLAS to the 3.8.1 release. In addition tuning info for 32 bit Prescott CPUs as well as Powerbook G4s under Linux was added.

zn_poly

David Harvey's zn_poly library is now a standard package for Sage. zn_poly is a new C library for polynomial arithmetic in $(Z/nZ)[x]$ where $3 \le n \le ULONG_MAX$ (i.e. any machine-word-sized modulus). The main benefit is speed. Three examples on sage.math, from my current development code (this code is not yet in the spkg):

• Multiplying length $200$ polynomials over $Z/nZ$ where n has 10 bits:
  * NTL (zz_pX): 113 µs
  * Magma: 44 µs
  * zn_poly: 13 µs
• Multiplying length $10^6$ polynomials over $Z/nZ$ where n has 40 bits and is odd:
  * NTL (zz_pX): 9.1s
  * Magma: 8.3s
  * zn_poly: 2.06s
• Reciprocal of a length $10^6$ power series over $Z/nZ$ where n has 40 bits and is odd:
  * NTL (zz_pX): 25.4s
  * Magma: ludicrously slow, maybe I'm doing something wrong
  * zn_poly: 3.62s
  The library is used so far only to compute the zeta function for hyperelliptic curves.

small roots method for polynomials mod N (N composite)

Coppersmith's method for finding small roots of univariate polynomials modulo $N$ where $N$ is composite was implemented. An application of this method is to consider RSA. We are using 512-bit RSA with public exponent $e=3$ to encrypt a 56-bit DES key. Because it would be easy to attack this setting if no padding was used we pad the key $K$ with 1s to get a large number.

sage: Nbits, Kbits = 512, 56
sage: e = 3

We choose two primes of size 256-bit each.

sage: p = 2^256 + 2^8 + 2^5 + 2^3 + 1
sage: q = 2^256 + 2^8 + 2^5 + 2^3 + 2^2 + 1
sage: N = p*q
sage: ZmodN = Zmod( N )

We choose a random key

sage: K = ZZ.random_element(0, 2^Kbits)

and pad it with $512-56=456$ $1$s

sage: Kdigits = K.digits()
sage: M = [0]*Kbits + [1]*(Nbits-Kbits)
sage: for i in range(len(Kdigits)): M[i] = Kdigits[i]
sage: M = ZZ(M, 2)

Now we encrypt the resulting message:

sage: C = ZmodN(M)^e

To recover $K$ we consider the following polynomial modulo $N$:

sage: P.<x> = PolynomialRing(ZmodN)
sage: f = (2^Nbits - 2^Kbits + x)^e - C

and recover its small roots:

sage: Kbar = f.small_roots()[0]
sage: K == Kbar
True

Generic Multivariate Polynomial Arithmetic

Joel Mohler improved the efficiency of the generic multivariate polynomial arithmetic in Sage. Before his patch was applied:

sage: R.<x,y,z,a,b>=ZZ[]
sage: f=prod([2*g^2-4*g+8 for g in R.gens()])
sage: %time _=f*f
CPU times: user 2.23 s, sys: 0.00 s, total: 2.23 s
Wall time: 2.24

and after:

sage: R.<x,y,z,a,b>=ZZ[]
sage: f=prod([2*g^2-4*g+8 for g in R.gens()])
sage: %time _=f*f
CPU times: user 0.22 s, sys: 0.00 s, total: 0.22 s
Wall time: 0.22

k-Schur Functions and Non-symmetric Macdonald Polynomials

$k$-Schur functions $s_\lambda^{(k)}$ are a relatively new family of symmetric functions which play a role in $\mathbb{Z}[h_1, \ldots, h_k]$ as the Schur functions $s_\lambda$ do in $\Lambda$. The $k$-Schur functions, amongst other things, provide a natural basis for the quantum cohomology of the Grassmannian. The $k$-Schur functions can be used like any other symmetric functions and are created with kSchurFunctions.

sage: ks3 = kSchurFunctions(QQ,3); ks3
k-Schur Functions at level 3 over Univariate Polynomial Ring in t over Rational Field
sage: s(ks3([3,2,1]))
s[3, 2, 1] + t*s[4, 1, 1] + t*s[4, 2] + t^2*s[5, 1]

Non-symmetric Macdonald polynomials in type A can now be accessed in Sage. The polynomials are computed from the main theorem in "A Combinatorial Formula for the Non-symmetric Macdonald Polynomials" by Haglund, Haiman, and Loehr. ( http://arxiv.org/abs/math.CO/0601693 )

sage: from sage.combinat.sf.ns_macdonald import E
sage: E([0,1,0])
((-t + 1)/(-q*t^2 + 1))*x0 + x1
sage: E([1,1,0])
x0*x1

Improved capabilities for solving matrix equations

William Stein implemented code so that one can now solve matrix equations $AX = B$ and $XA=B$ whenever a solution exists. In particular, solving linear equations now works even if $A$ is singular or nonsquare.

sage: A = matrix(QQ,2,3, [1,2,3,2,4,6]); v = vector([-1/2,-1])
sage: x = A \ v; x
(-1/2, 0, 0)
sage: A*x == v
True

Generators for congruence subgroups

Robert Miller implemented an algorithm for very quickly computing generators for congruence subgroups $\Gamma_0(N)$, $\Gamma_1(N)$, and $\Gamma_H(N)$.

sage: Gamma0(11).generators()
[[1 1]
[0 1],
 [-1  0]
[ 0 -1],
...
 [10 -1]
[11 -1],
 [-10   1]
[-11   1]]
sage: time G = Gamma0(389).generators()
CPU times: user 0.03 s, sys: 0.01 s, total: 0.04 s
Wall time: 0.04
sage: time G = Gamma0(997).generators()
CPU times: user 0.14 s, sys: 0.00 s, total: 0.14 s
Wall time: 0.14
sage: time G = Gamma0(2008).generators()
CPU times: user 0.82 s, sys: 0.00 s, total: 0.82 s
Wall time: 0.82
sage: len(G)
3051  

gfan-0.3 upgrade, improved interface

@interact
def gfan_browse(p1 = input_box('x^3+y^2',type = str, label='polynomial 1: '), p2 = input_box('y^3+z^2',type = str, label='polynomial 2: '), p3 = input_box('z^3+x^2',type = str, label='polynomial 3: ')):
    R.<x,y,z> = PolynomialRing(QQ,3)
    i1 = ideal(R(p1),R(p2),R(p3))
    gf1 = i1.groebner_fan()
    testr = gf1.render()
    html('Groebner fan of the ideal generated by: ' + str(p1) + ', ' + str(p2) + ', ' + str(p3))
    show(testr, axes = False, figsize=[8,8*(3^(.5))/2])

Bugfixes/Upgrades (incomplete)

• misc:
  * #2148 PolyBoRi monomial orders are wrong
  * #2437 Update eclib.spkg to eclib-20080304
  * #2468 inverting a non-invertible matrix over RDF returns weird results
  * #2517 ignore bad values in plot
  * #2545 FractionFieldElement lacks derivative method
  * #2566 fix all known bugs in graph_isom and binary_code
  * #2571 problem with copy() on sage.rings.integer_mod.IntegerMod_gmp
  * #2574 problem with Abelian groups and trivial elements
  * #2576 preserve docstrings of decorated methods in multi_polynomial_ideal.py
  * #2579 Inconsistency in integer quotient
  * #2581 extend solve_right to all cases; implement solve_left
  * #2582 fix bug in PermutationGroupElement
  * #2585 padic bugfix - check=False in constructor
  * #2587 subgroup of a permutation group is so slow it's silly
  * #2588 documentation and tests for sage.schemes.hyperelliptic_curves.jacobian_morphism
  * #2593 Sage chokes on utf-8 in .sage files
  * #2594 MPolynomial_polydict floordiv wrong arithmetic fixed
  * #2602 plot_vector_field docs are unnecessarily complicated (and use the slow lambda functions!)
  * #2584 printing bug with list_function()

Full Changelog: 2.10.3...2.11

2.10.3

Release Tour

Sage 2.10.3 was released on 11 Mar 2008. For the official, comprehensive release notes, see the HISTORY.txt file that comes with the release.For the latest changes seesage-2.10.3.txt. Among many other things that were done, we have the following cool new features. Of course, this list is incomplete; see the release notes for more details.

Michael Abshoff was the release managers for this Sage release.

Interactive Functions

Sage now has a first version of its "interact" command. Calling @interact before defining a function will construct controls to graphically control the input variables of the function, making it dramatically easier to create interactive functionality that is easy to use. See http://wiki.sagemath.org/interact for details and examples or just type "interact?" in Sage.

Graph theory

Many of the results of Sage Days 7: Combinatorics are included in this release, including Schnyder's algorithm for producing straight-line drawings of planar graphs in linear time (Jonathan Bober and Emily Kirkman), and a new compiled backend for the base graph structures (Robert Miller). This backend will be switched into graphs proper in sage-2.10.4, and the basic functions, such as add edge and has edge, will be sped up by at least 20 times in many cases, and often much more. In addition most of graph.py was refactored and cleaned up, in preparation for the switch.

Plotting

• The plot_vector_field function now takes 2-variable functions, allowing for much more complex vector fields.

sage: plot_vector_field((lambda x,y: x+y, lambda x,y: x^2*y^3), (x,-2,2), (y,-2,2))

Linear Algebra

• Matrices now have a jordan_form method which computes the Jordan canonical form.

sage: a = matrix(ZZ,4,[1, 0, 0, 0, 0, 1, 0, 0, 1, -1, 1, 0, 1, -1, 1, 2]); a
[ 1  0  0  0]
[ 0  1  0  0]
[ 1 -1  1  0]
[ 1 -1  1  2]
sage: a.jordan_form()
[2|0 0|0]
[-+---+-]
[0|1 1|0]
[0|0 1|0]
[-+---+-]
[0|0 0|1]

Unified derivative syntax

The derivative function now accepts the same argument format across many different data types, including symbolic objects, polynomials, power series, and Laurent series. For example:

sage: var("x y")
(x, y)
sage: f = sin(x^3 * y^2)
sage: f.derivative(x, y, 2)   # differentiate with respect to x, and then twice with respect to y
-30*x^5*y^2*sin(x^3*y^2) - 12*x^8*y^4*cos(x^3*y^2) + 6*x^2*cos(x^3*y^2)

sage: R.<t> = PowerSeriesRing(ZZ)
sage: S.<u> = PowerSeriesRing(R)
sage: f = t^3 * u^2
sage: f.derivative(u, t, 2)
12*t*u

Full Changelog: 2.10.2...2.10.3

2.10.2

Full Changelog: 2.10.1...2.10.2

2.10.1

Release Tour

Sage 2.10.1 was released on 2 Feb 2008. For the official, comprehensive release notes, see the HISTORY.txt file that comes with the release.

Michael Abshoff were the release managers for this Sage release.

For the latest changes see sage-2.10.1.txt. In addition to many bug fixes, integration of new packages, and speedups, we have the following cool new features. This list is incomplete; see the release notes for more details.

• Typeset output easily accessible in the notebook: There is now a checkbox at the top of each worksheet which enables or disables typeset output in the worksheet. When the box is checked, new output is typeset. When the box is unchecked, new output is returned in its usual form.
• Graph isomorphism works for graphs containing multiple edges: The graph isomorphism testing has been extended to handle graphs with multiple edges.
• Vertex objects: Arbitrary objects can now be associated with the vertices of a graph.
• Tremendous speedups in evaluating functions: If a function is being used for plotting, an extremely fast version of the function is automatically used.
• Plotting vectors now has several different options, including automatically plotting arrows if the vector is 2 or 3 dimensional and plotting a step function of the components for higher dimensions.
• Showing lists of graphics: Now calling show() on a list will automatically tile the graphics in a customizable array. Defaults for graphics plotted in a list can also be provided. Try doing show(graphs(4)), for example, which nicely plots all undirected graphs on 4 vertices.
• Unifying 2d and 3d graphics: You can mix 2d and 3d graphics together and the system handles the combination intelligently.

Full Changelog: 2.9.2...2.10.1

2.10.4

Release Tour

Sage 2.10.4 was released on March 17, 2008. For the official, comprehensive release notes, see the HISTORY.txt file that comes with the release. For the latest changes seesage-2.10.4.txt.

Robert Miller and Michael Abshoff were the release managers for this Sage release.

Memory leaks exposed by modular symbols

Michael Abshoff, Martin Albrecht, Burcin Erocal, Willem Jan Palenstijn, Clement Pernet, William Stein: memory leaks exposed by modular symbols functionality. This ticket is a composite of numerous other memleak fixes merged over a 7 month period. Modular forms are an excellent way to expose memory leaks in pretty much every algebraic component of Sage and all known issues there are now finally fixed.

SQLAlchemy and DSage

We merged SetupTools and SQLAlchemy into Sage as standard packages. SQLAlchemy is now used as in DSage replacing hand written code with much more efficient classes from SQLAlchemy. SetupTools is required to install SQLAlchemy, but is also useful for a number of experimental spkgs like Mayavi2, TVTK and other packages from the Enthought Tool Suite. Yi Qiang improved DSage making it more robust and finally adding the doumentation to the standard Sage manual.

Graph theory: chromatic polynomial

An algorithm originally written in C by Gordon Royle has been adapted by Robert Miller to replace the old slow method. This algorithm uses a cut and merge algorithm to recursively compute the chromatic polynomial, and is written in Cython.

Documentation

Many doctest patches written during Doc Day 2 were merged. In addition many people kept up the good work after Doc Day 2 was over and have been submitting patches to increase coverage. We did exceed the target for the release by 0.6% reaching 47.6%.

Symmetric function updates

Mike Hansen, reviewed by Franco Saliola: Sage 2.10.4 adds support for Macdonald polynomials, LLT polynomials, and Jack polynomials as well as a whole class of user-defined symmetric functions which can characterized by orthogonality and triangularity conditions. Support for working with ribbon tableaux was also added as part of these updates. In addtition, many doctests were added and subtle bugs fixed.

Notebook Updates

Tom Boothby and William Stein, reviewed by each other and Timothy Clemans.

Fixed a bunch of bugs, new and old:

• Smarter update polling (#185): rather than always poll every 1/2 second, we start at 1/4 second intervals, and gradually slow down to 5 second intervals after about 30 seconds.
• Emptying the trash works (#432)
• Saving cells without evaluating (#1590): When a cell loses focus, and it's been changed, the changes are sent to the server so that work isn't lost.
• Removed the last few absolute URLs so the public notebook will be useable by people behind crazy firewalls. (#1879)
• Updating worksheet title changes the window title (#1974): it should be noted, William Stein was born in 1974.
• Speed up security certificate generation in linux (#1976)
• Fixed evaluate link (#2332)
• Interact bug in drop down menus fixed (#2530)

Parallel Doctesting

Gary Furnish reviewed by Michael Abshoff:

"sage -tp" has been introduced as an experimental multithreaded doctester. The first parameter is the number of threads, and the second parameter is the folder to doctest. Thus "sage -tp 4 devel/sage/sage" tests everything with four threads running. Additional options like "-long" or valgrind options like "-memcheck" do work. The code base is still young and needs more testing. The eventual goal will be to replace the current doctesting infrastructure with this code base.

SBox Class

A new S-box class was introduced to Sage to support (algebraic) exploration of this fundamental cryptographic primitive.

• We create a new 3-bit S-box

sage: S = mq.SBox(7,6,0,4,2,5,1,3); S
(7, 6, 0, 4, 2, 5, 1, 3)

• and check its properties with respect to differential

sage: S.difference_distribution_matrix()

[8 0 0 0 0 0 0 0]
[0 2 2 0 2 0 0 2]
[0 0 2 2 0 0 2 2]
[0 2 0 2 2 0 2 0]
[0 2 0 2 0 2 0 2]
[0 0 2 2 2 2 0 0]
[0 2 2 0 0 2 2 0]
[0 0 0 0 2 2 2 2]

sage: S.maximal_difference_probability()
0.25

• and linear cryptanalysis:

sage: S.linear_approximation_matrix()

[ 4  0  0  0  0  0  0  0]
[ 0  0  0  0  2  2  2 -2]
[ 0  0 -2 -2 -2  2  0  0]
[ 0  0 -2  2  0  0 -2 -2]
[ 0  2  0  2 -2  0  2  0]
[ 0 -2  0  2  0  2  0  2]
[ 0 -2 -2  0  0 -2  2  0]
[ 0 -2  2  0 -2  0  0 -2]

sage: S.maximal_linear_bias_relative()
0.25

• We can express this S-box as a univariate polynomial over $GF(2^3)$

sage: S.interpolation_polynomial()
x^6 + a*x^5 + (a + 1)*x^4 + (a^2 + a + 1)*x^3 + (a^2 + 1)*x^2 + (a + 1)*x + a^2 + a + 1

• or as a set of polynomials over $GF(2)$.

sage: S.polynomials(degree=2)

[x0*x2 + x1 + y1 + 1,
 x0*x1 + x1 + x2 + y0 + y1 + y2 + 1,
 x0*y1 + x0 + x2 + y0 + y2,
 x0*y0 + x0*y2 + x1 + x2 + y0 + y1 + y2 + 1,
 x1*x2 + x0 + x1 + x2 + y2 + 1,
 x0*y0 + x1*y0 + x0 + x2 + y1 + y2,
 x0*y0 + x1*y1 + x1 + y1 + 1,
 x1*y2 + x1 + x2 + y0 + y1 + y2 + 1,
 x0*y0 + x2*y0 + x1 + x2 + y1 + 1,
 x2*y1 + x0 + y1 + y2,
 x2*y2 + x1 + y1 + 1,
 y0*y1 + x0 + x2 + y0 + y1 + y2,
 y0*y2 + x1 + x2 + y0 + y1 + 1,
 y1*y2 + x2 + y0]

Full Changelog: 2.10.3...2.10.4