Archive for March, 2009

Computing Gröbner bases in Haskell

I wrote a small package to compute Gröbner bases in Haskell with the Buchberger algorithm (with applications to variable elimination). Performance is quite bad compared to specialised software like Macaulay, but it seems to work ! I put a Cabal package here. Maybe I’ll add several functions afterwards.

A testcase :
import Data.Polynomial
import Data.Ring
import Algebra.GroebnerBasis
import Algebra.Elimination
type R = Polynom QQ VarXYZ
[x,y,z,t,u,v] = map returnp [X,Y,Z,T,U,V] :: [R]
-- projection from a point on the intersection of quadrics
main = do
print $ step_eliminate [T] $ MakeIdeal
[x^2 - 3*y*z + z*t + 2*x*t,
z^2 + 5*y^2 + z*x - 2*t*z]

The output should be :

20 March 2009 at 7:47 pm Leave a comment

Schemes in algebraic geometry 3 : glued schemes and sheaves

André Weil was among the first ones to point out the importance of having a local description of varieties, especially projective spaces, which can always locally be described as an affine space with completion by a hyperplane at infinity, and projective varieties, which similarly look like varieties in affine space. The use of sheaves in local description of spaces was magnified by Cartan and Serre, in the context of complex analytic spaces, and generalised to the algebraic setting by Serre in Faisceaux algébriques cohérents.

The projective space is the simplest example of an algebro-geometric object which cannot be described by the prime spectrum or the functor of points of a ring. For example, there is no obvious ring whose ideals describe varieties in projective space, which come from homogeneous equations. We would like to give a correct definition of gluing affine lines (with coordinates z and 1/z) to define the projective line \mathbb P^1 as the gluing of \mathbb A^1 with \mathbb A^1 \to \mathbb P^1 given by z \mapsto 1/z. For functors of points, the latest article by Alain Connes and Caterina Consani, gives a definition. For prime spectra, one has to be aware that gluing only topological spaces do not give meaningful information on algebraic properties. This is illustrated by the case of differentiable manifolds, which are not the same as topological manifolds: gluing differentiable manifolds has to induce a correspondance between differentiable functions (this is equivalent to the requirement that gluing maps between charts be differentiable).

17 March 2009 at 12:35 am Leave a comment

Why can we have a Fast Fourier Transform ?

The Fourier transform was introduced by Fourier as a tool to solve heat equations, but is now used in its discrete version throughout the computing world more than trillions of times each second. It is probably more, I was assuming an average computer does billions of Discrete Cosine Transforms per day for Web browsing (JPEG images and Youtube) and music listening, but how huge is the contribution of millions of people watching MPEG-2 compressed television programs on satellite or terrestrial digital broadcasting?

It is thus important to know that the Fourier transform (which is always the Fast Fourier Transform) is really fast (especially when it is dozens, hundreds of times faster than the natural algorithm). I am not yet sure about the fast versions of variants of the discrete transform (cosine transforms and its friends), but I guess they can be derived from the classical case.

What is it ?

The classical Fourier transform takes a T-periodic function f and computes for each integer n the integral

f_n = \frac 1 {\sqrt T} \int_0^T f(t) \exp(-ni\omega t) dt

where \omega = 2\pi/T. It separates f into components having period T/n, and has the property that the energy E(f) = \frac 1 T \int |f(t)|^2 dt is the sum \sum |f_k|^2.

The discrete Fourier transform takes a discrete function given by x = (x_0, x_1, \dots, x_{n-1}) and computes the discrete analogue

y_p = \sum_{q = 0}^{n-1} x_q \exp(-2i\pi \frac{pq}{n})


12 March 2009 at 3:23 pm 3 comments

Schemes in algebraic geometry 2 : prime spectra and generic points

I just explained how the affine plane could be described by the ring \mathbb Z[x,y]. A point M of the affine plane whose coordinate ring is R is a morphism \mathbb Z[x,y] \to R defined by the assignment P \mapsto P(a,b) \in R, where (a,b) are the coordinates of M. In the case of points corresponding to morphisms \mathbb Z[x,y] \to \mathbb Z, there is a natural way of recovering the point from the ring morphism by looking at his equations, which are elements of the kernel of the morphism. If M satisfies the equations x=a and y=b, then M has the form (a,b). This motivates the abstract definition of point of the affine plane as a morphism \mathbb Z[x,y] \to R to some ring.

Conversely, the set of equations of M defines a canonically associated point p_M, which is the morphism \mathbb Z[x,y] \to \mathbb Z[x,y]/I, where I is the ideal generated by the equations. But this morphism has no reason to totally recover M if it wasn’t a point with integral coordinates. For example, the point (2,3) is a special point, satisfying a lot of equations, which characterize it. But (\log 2, \pi) do not satisfy any polynomial equations with integral coefficients, so the set of its equations is empty, and cannot be used to recover it. Moreover, the point (e, \log 3) does not satisfy equations either: their algebraic properties are exactly the same. These points are called generic.

The prime spectrum of a ring is a convenient way of describing equivalence classes of points of a given ring.
Definition. The prime spectrum of A = \mathbb Z[x,y] is the set of points p_I: A \to A/I for prime ideals I. If M: A \to R is any point of the affine plane with coordinates in an integral domain R, then Mis canonically associated to some p_M := p_I, where I is the kernel of the map A \to R.

10 March 2009 at 10:07 pm 2 comments

Schemes in algebraic geometry I : the affine plane

I think most people blogging around algebraic geometry eventually write about schemes, (as in Rigorous trivialities or algebraic stacks (in the Secret Blogging Seminar), which are traditionnally seen as the main reason (not) to study algebraic geometry today. My turn now. I recommend Igor Dolgacev’s lectures which is one of my favorite ways of speaking of schemes.

Interesting mathematics come up when algebraic varieties (things defined by several polynomial equations) are no longer defined as mere sets (sets of tuples of numbers satisfying the equation) but mope complex mathematical objects. Differential geometry, for example, gives the structure of a complex manifold to algebraic varieties in \mathbb C^n, which is still an efficient way of proving theorems. However, during the 20th century, a lot of mathematicians tried to develop a new structure which would avoid the use of analysis to concentrate on the algebraic aspects (I don’t know exaclty who, but expect Hilbert, Zariski, Chevalley, Grothendieck to have played a role). Grothendieck approach using category theory and functors of points is now widely used and is a very impressive way of tying together intuition, commutative algebra, and geometry.

There are many ways of reverse engineering Grothendieck’s definition of a scheme (see EGA1 if you want to know how this is related to Chevalley’s definition of a scheme). The first thing to say is probably what properties and notions are needed for schemes:

8 March 2009 at 12:49 pm 2 comments

Monads in mathematics 4 : the bar and cobar constructions

The use of monads and comonads in homological algebra is as old as the theory: Godement’s standard construction refers to the use of monads in cohomology theory, and is said to be the first study of a general method for constructing acyclic resolutions. Later the theory was explored in greater depth by Eilenberg, Moore, Barr, Beck. The term bar resolution is now most commonly used to describe the process. Monads derived from operads were also studied by Lawvere, Mitchell, Bénabou, under the name of algebraic theories, with aim towards topoi and logic.

Bar resolutions (see J. Baez website and the LNM Seminar on Triples and Categorical Homology Theory) are a way to canonically (i.e. functorially) describe an arbitrary algebra over a monad using only free algebras. It is a particular case of definition with generators and relations which is often the only way to describe infinite mathematical objects with finite expressions (computer algebra systems usually deal with finitely generated objects, and use generators and relations to describe their elements), but bar resolutions somehow are the universal way of doing this.

Most cohomology theories fit in the framework of bar constructions, though in various apparently unrelated ways. However, a visible common denominator of most constructions is the use of simplicial methods. This makes them of some use in homotopical algebra: bar resolutions are used to define canonical cofibrant resolutions of objects, which explains their uses in definition of derived functors.

4 March 2009 at 10:39 pm Leave a comment

Monads in mathematics 3 : monads from adjunctions

The adjunction property between two functors, T: C_1 \to C_2 and U: C_2 \to C_1, says that there is a natural bijection between morphisms \mathrm{Hom}_1(A, UB) (in the first category) and \mathrm{Hom}_2(TA, B) (in the second category). Here natural means that these bijection is compatible with composition with morphisms B \to B', UB \to UB' or A' \to A and TA' \to TA.

Adjunctions are naturally created by the use of monads or operads. For example, the functor V_k: \mathrm{Set} \to \mathrm{Vect}_k mapping a set X to the free vector space V_k(X) = k^{(X)} with basis X, has a adjoint, U: \mathrm{Vect}_k \to \mathrm{Set}, mapping a vector space to the set of its elements. The meaning of the adjunction is that a morphism V_k(X) \to W is equivalent to the choice X \to W of images of basis vectors where W is considered as as set. Similar adjunctions exist for other free objects (free algebras, free groups, free modules).

2 March 2009 at 12:13 am 1 comment