Two examples: discrete valuation rings on curves

Let’s look at the curves ${\mathcal C : y = x^2}$ and ${\mathcal D : y^2 = x^3}$. They’re pretty simple, so naturally, we’re going to use some big tools to analyze him. Today the plan is to look at these curves by studying how functions behave on them locally.

Motivating the Zariski Topology

Act I: Where polynomials take over

It is a large theme in commutative algebra that the only thing standing in the way of two rings is what polynomials in these rings look like. Think about this briefly: the only difference between ${{\mathbb Z}}$ and ${{\mathbb Z}/p{\mathbb Z}}$ is that, in the latter ring, the polynomial ${x^p-1}$ is always the zero function, while in the former it is never the zero function.

This idea motivates a lot of the definitions in ring theory, usually phrased in language like (though often not identical to) “a ring ${A}$ is said to have property ${\mathcal P}$ if the roots of polynomials with property ${\mathcal Q}$ always are in ${A}$.” Fine examples of this include:

• The definition of an integral domain: we say that ${A}$ is a domain if, for all ${a \in A}$ nonzero, the function ${ax}$ has no roots in ${A}$;
• The definition of a field: we say that ${A}$ is a field if, whenever ${a \in A}$ is nonzero, the function ${ax-1}$ has a root in ${A}$;
• The definition of being algebraically closed: we say that a field ${A}$ is algebraically closed if every polynomial in ${A[x]}$ has a root in ${A}$;
• The definition of a separable field extension: we say an extension ${L/K}$ of fields is separable if every element of ${L}$ has a separable minimal polynomial in ${K[x]}$;
• The definition of a normal field extension: we say an extension ${L/K}$ of fields is normal if ${L}$ is the splitting field of a family of polynomials in ${K[x]}$;
• The definition of an integrally closed domain: we say that an integral domain ${A}$ with field of fractions ${K}$ is integrally closed if, any root in ${K}$ of a monic polynomial in ${A[x]}$ is actually an element of ${A}$.

And so on. Roots of polynomials say an enormous amount about the rings they take their coefficients in! Hence they are more than sensible things to study — they are, in a very real sense, the only thing to study.

Act II: Where geometry arises

So we have now become interested in sets of the form

$\displaystyle \{a \in A : f(a) = 0 \text{ for all } f \in S\} \text{ where } S \subseteq A[x] \mathrm.$

A natural generalization of this is to allow polynomials in several variables, so that we start looking at sets of the form

$\displaystyle \{(a_1,...,a_n) \in A^n : f(a_1,...,a_n) = 0 \text{ for all } f \in S\} \text{ where } S \subseteq A[x_1,...,x_n] \mathrm.$

Sets of this form are called affine varieties, and they are the first step in the study of classical algebraic geometry. Rather conveniently, affine varieties happen to satisfy the axioms of closed sets for a topology: the empty set and the whole space are both affine varieties, and the collection of affine varieties is closed under arbitrary intersection and finite union. This observation defines the (classical) Zariski topology on ${A^n}$.

Act III: A formulation using ideals

Classically it was entirely common to work with ${A = {\mathbb C}}$, which has the desirable property that (since ${{\mathbb C}}$ is algebraically closed) affine varieties tend to be non-empty (they are only empty if ${S}$ contains a constant, non-zero function).

Working with algebraically closed fields one is eventually lead to Hilbert’s Nullstellensatz, which one can use to formulate a theory of varieties entirely in terms of maximal ideals in ${A[x_1,...,x_n]}$. In this formulation, one defines

$\displaystyle \mathfrak{m}\text{Spec} A[x_1,...,x_n] = \{\text{maximal ideals of } A[x_1,...,x_n]\}$

and then one creates a topology — still called the Zariski topology — on ${\mathfrak{m}\text{Spec} A[x_1,...,x_n]}$ where a set is closed if it is of the form

$\displaystyle \{\mathfrak m : \mathfrak m \supseteq I\} \text{ where } I \subseteq A[x_1,...,x_n] \text{ is any ideal.}$

When ${A}$ is algebraically closed, this topology on ${\mathfrak{m}\text{Spec}}$ is homeomorphic to the classical Zariski topology on ${A^n}$ by the map ${(a_1,...,a_n) \mapsto (x_1 - a_1,...,x_n - a_1)}$ (this is a consequence of the Nullstellensatz). Suddenly we have a formulation of the Zariski topology entirely in the language of ideals.

Act IV: Functoriality leads to ${\text{Spec}}$

There are some obvious ways to generalize the work in Act III. First, there’s no reason in particular to only look at polynomial rings like ${A[x_1,...,x_n]}$; we may as well consider arbitrary rings and look at their ${\mathfrak{m}\text{Spec}}$, which we can define and topologize in the same way.

Once we’ve done this, we have a mapping, where rings give us topological spaces. In the modern world it is natural to ask this mapping to be functorial — that is, if rings are going to give us topological spaces, we may as well ask that ring homomorphisms give us continuous maps.

Let’s set ${\mathfrak{m}\text{Spec}}$ aside for a moment and simply consider what this functor might look like. Our experience with ${\mathfrak{m}\text{Spec}}$ suggests that it is profitable to have a topological space whose points are ideals of ${A}$, so we’ll stick with this idea, trying to dial it in to something more precise.

First we need to ask ourselves: should our functor be co- or contravariant? As it happens, if we want our topological spaces to have points corresponding to ideals, then our hand is forced: we need only look at the initial and terminal objects in Ring and Top.

• The terminal object in Ring is the zero ring, which has no proper ideals. It should therefore correspond to the empty topological space, which is the initial object in Top.
• If ${k}$ is a field, then ${k}$ has only one ideal (the zero ideal), hence should be sent to a topological space with only one point (the final object in Top).

Thus the map ${k \rightarrow 0}$ needs to correspond to the map ${\{\} \rightarrow \cdot}$, which is a contravariant relationship. Thus our functor is going to be contravariant.

Luckily, there is a good, contravariant way for ring homomorphisms to move around ideals: if ${f : A \rightarrow B}$ is a ring homomorphism, and ${\mathfrak b \subseteq B}$ is an ideal, then ${f^{-1}(\mathfrak b) \subseteq A}$ is also an ideal (often called the contraction of ${\mathfrak b}$).

With this in mind we now return to ${\mathfrak{m}\text{Spec}}$. If ${f : A \rightarrow B}$ is a ring homomorphism, it is sadly the case that the contraction of a maximal ideal in ${B}$ is not likely to be a maximal ideal in ${A}$ (that is, the map ${\mathfrak b \mapsto f^{-1}(\mathfrak b)}$ is not likely to be a function ${\mathfrak{m}\text{Spec} B \rightarrow \mathfrak{m}\text{Spec} A}$). The standard example of this is to look at the inclusion map ${{\mathbb Z} \hookrightarrow {\mathbb Q}}$, noting that the unique maximal ideal of ${{\mathbb Q}}$ does not pull back to a maximal ideal in ${{\mathbb Z}}$.

It is true, however, that if ${\mathfrak b}$ is a maximal ideal, then ${f^{-1}(\mathfrak b)}$ will be a prime ideal. In fact, this is true even if ${\mathfrak b}$ is just a mere prime ideal itself (not necessarily maximal). In particular, if we allow ourselves to expand ${\mathfrak{m}\text{Spec}}$ a little, generalizing to the set

$\displaystyle \text{Spec} A = \{\mathfrak p : \mathfrak p \subseteq A \text{ a prime ideal}\}$

then contraction does induce a function ${\text{Spec} B \rightarrow \text{Spec} A}$. Furthermore, if we endow ${\text{Spec} A}$ with a topology in exactly the same way we did with ${\mathfrak{m}\text{Spec} A}$, then contraction will be continuous. We’ve thus developed a contravariant functor from Ring to Top!

Act V: Curtains, and on to schemes

And so the journey to schemes begins. I won’t define schemes here; my point was to motivate, not elucidate. I’ll just say what’s missing.

In the classical theory of varieties, one is lead to consider functions from a variety in ${A^n}$ back down to ${A}$. There’s a reasonable definition for what it means for a function to be “well behaved” enough to be worth looking at — continuity is a part of it, but obviously it wouldn’t be algebra unless there was an algebraic condition as well.

This definition, after a good deal of modernization, lends itself quite well to generalization. One defines what the class of “good functions” on ${\text{Spec} A}$ should be, in such a way that both the topology of ${\text{Spec} A}$ and the algebra of ${A}$ are incorporated, then creates a new structure on ${\text{Spec} A}$ which carries around this data. This combination — ${\text{Spec} A}$ and the extra structure that describes the “good functions” — are what we call an affine scheme. A scheme is a topological space (again with some structure that describes the “good functions”) which is locally isomorphic to affine schemes.

The handwaving above suggests why it is so time-consuming to define schemes: not only do we need to define ${\text{Spec} A}$, but we also need to introduce the extra structure for tracking the “good functions,” as well as a characterization of these functions (so that the structure can track it!)

But once one has managed through this process (experience suggests this is where most would-be algebraic geometers give up and decide to study something else), one is left with a powerful theory indeed — in no small part due to the functor from Act IV.

Continued weak support from Opal Kelly

A mentioned earlier, I have a XEM 3001 from Opal Kelly. I bought it for simplicity. Simple it is — supported, however, it is not.

Issues thus far:

• The FrontPanel software, a utility for doing quick-and-dirty PC interfacing with the device, is only supported on a handful of Fedora releases. No source means no can make run on other platforms. Until this January, they only supported Fedora 5 and 7. Absurd.
• Support is conducted via their online forum. Cute, except they rarely respond with any real info. A lot of “oh, we’ll do something about that real soon now.” Be prepared to hear back a caustic reply. The customer is always an idiot, after all.
• The RAM3001 module — an addon for the low end XEM boards to give them some memory — isn’t really supported with the XEM3001. Sure, they say it is. It’s not. They have sample code for interfacing for all other modules. They’re response? Oh, you should be able to figure out what to do based on the source for the hardware you don’t own. So, you know, familiarize yourself with some other hardware you have nothing to do with.

I’m sure that experienced engineers can get around this. Experienced I am not. They market their products to students. Bummer.

Logitech QuickCam Vision Pro for “Mac”

I’m currently playing with wavelets as a part of my journey to know something about signal processing. Edge detection is a now-classic application of wavelets, so I figured I should experiment with that a bit.

To that end, I went out looking for a webcam that works well under Linux. Based on reports that the camera works in Linux — mostly this review, I picked up the Logitech QuickCam Vision Pro for Mac. I’d like to report that the camera does, in fact, work via the UVC driver with Video 4 Linux 2. Even auto-focus works (I’ve heard that this camera implements it in hardware, though I cannot confirm this).

It turns out that OpenCV has its own V4L2 interface, and that this has been exported to the OpenCV Python bindings. I grabbed some sample code from here and it worked out-of-box. With a 1-line modification, I was applying the Python Image library’s CONTOUR filter. Here’s the result, plus blurry because of my shaky hands:

PythonWare Image library, Contours filter.

Works great, almost in real time on my desktop machine. So now the task ahead of me is to implement the same functionality, since that’s what got me started down this path to begin with.

Here are two pictures I took of the camera after removing the stand it came with. To be clear, these were (obviously!) not shot on the camera itself.

Cute size

I removed the camera's stand only to find these mounts inside. Perfect!

Opal Kelly XEM3001

Today my Opal Kelly XEM3001 arrived. I’m hoping to use it for some high-speed signal processing, which I’ll write about when I have more to show for it. For the time being, I just wanted to mention that the FrontPanel software works on my MacBook Pro more or less, though I must point out that some of the samples are trying to find wave files in c:\windows, which is a cute bug, and luckily pretty harmless (these being just sample projects, after all). The sample code showed that it was possible to upload code to the FPGA (and fast!) as well as communicate to the device via USB.

Edit. Well, it works on my Mac, but not on Ubuntu. The supporting software (which is free as in beer) is shipped binary-only, and is built for Fedora 7. I found this thread where Opal Kelly responded to a user’s support question by trying to sell him a custom build.

Of course, I’d be elated if they’d just release the source, I can’t really expect everyone to wake up to the 21st century. Still, if they insist on this silly binary-only distribution, it’d be nice if they’d support the same distribution that Xilinx supports (ie, Redhat). It’d also be nice if they could find a way to ship without dynamic linking dependencies. *sigh*

Pics:

t

Kinetic source release

I’ve received a request to release the source for Kinetic, a project I worked on in Haskell around the winter of 2006 (iirc). There are two reasons why I’ve put this off:

1. This was one of the first projects I worked on in Haskell, and the source shows that. My experience has been Haskell is often criticized based on the quality of code produced by its n00bs. This is an unreasonable thing to do (imagine judging a unicycle based on how well someone can ride it on their first go!) but I see it often none the less. I hope that this release does not lead to more of this nonsense.
2. The project had ambitious goals that I never had the time to pursue (I’m sure many hackers know that feeling…) I’m really not interested in hearing about how I didn’t deliver on that. It’s just something I was working on when I was in college, you dig?

I’ve uploaded a snapshot of my development directory here. The build process attempts to download the source to ghc-6.6 and build it locally for use in the construction of the kernel. It will also try to find (using very basic means) the object files for many non-system C routines used to support the GHC runtime.

The Makefile should be able to produce a bootable CD ISO that can be used with VMWare. The operating system includes a driver for the VMWare graphics adapter, which it will assume is what the host system provides (so it probably won’t get very far in Bochs or qemu).

Of course, when I tried building it on my current machine, the build failed in ghc-6.6. I know that I was working on replacing the GUI with a console-based shell at some point; it’s possible that the source I posted is somewhere in the middle of that, and won’t build as a result. I’ll investigate this more when I get a chance.

I’d be happy to answer any questions about the system as best as I can. Happy hacking!

GHC as the basis for an operating system

Today’s post is more of a “thinking out loud.”

A few years back I started working on an “operating system written in Haskell. The code drew on some C++ that I had already written for dealing with CPU-level data structures, together with some new Haskell code I had written for interfacing with it. I wound up leaving the project to rest soon after that, more or less because I didn’t like the way the code was turning out. I’d later look back and realize that my haskell-foo just wasn’t up to the task of writing the code in good style (I’m planning to release the source this weekend, so you’ll get a chance to see what I mean).

Recently I learned that House, a Haskell-based OS project that preceded my own, is once more in active development. This is good news for two distinct reasons:

1. It was an interesting project that accomplished much more than I managed to, and
2. If I ever find the time to work on an operating system again, there’s a project to contribute to rather than re-invent.

All of this made me wonder, though: what would it take to make GHC itself bootable? It’s already the standard compiler; more or less everything works with it. Every day Hackage grows with more software that works in it. At some point, doesn’t it make sense to just boot to GHC?

How would it be done? Perhaps in much the same way as I made Kinetic bootable: create a stripped down POSIX environment, include whatever standard libraries are needed to support the thing, and run Bochs until the kinks get worked out.

What do you think?

High speed methods in number factorization

On 24 February 2009 I’ll be giving a talk for the University of Utah GSAC Colloquium on sub-exponential algorithms for number factorization. The talk will cover Pomerance’s Quadratic Sieve, as well as other current methods. The plan is to focus on the connections between number factorization and other problems in mathematics whose connections to number theory are both non-obvious and highly useful.

This will be a survey of known methods, rather than a presentation of original work.

On keeping category theory and abstract algebra alive in Haskell

Undoubtedly, the part that has gotten the most attention is his suggestion that the Haskell community stop using mathematical names (as a default) for our common idioms. To quote:

I’m a mathematician, so perhaps my opinion on this should be taken with a grain of salt. But to be fair, I came to Haskell years before I had taken any category theory, and back before my abstract algebra was where it is today.

It’s been said elsewhere, but I think it bears repeating: we basically have two choices on this issue.

1. We use less technical names, so that we don’t scare off people who are scared of technical names.
2. We call it what it is, with the added benefit that people who are familiar with these ideas can come to the language and apply some existing intuition.

Each option picks a preferred audience, where the audience for (2) is undoubtedly in the minority. But is that necessarily a bad thing?

Haskell is a Great Language Experiment. Originating in academia, it has been built out of a vast collection of wildly strange ideas, more or less just to see how well these ideas would work out. We’re watching that experiment unfold today.

Some parts of the experiment are obvious, such as using monads to bring side effects into the type system. Others are less obvious, such as suggesting that we should think about our software in terms of category theory and abstract algebra.

So thus I suggest the following perspective: just as we have become convinced that monads are a better way of modeling side effects, so too may we be convinced that these branches of math provided a good way of thinking about programs. If we do become convinced of this, then it behooves us to stick with this nomenclature and rethink our approach to training programmers. After all, it might be the case that an army of programmers who thinks in these terms will produce better results than army that doesn’t. If so, we should adopt this practice!

Of course, this has the obvious disadvantage of disenfranchising those programmers who won’t or cannot think of their problems in these terms. That’s fine; Haskell doesn’t need to be for everybody, just as not everybody needs to love Java, or Python, or Assembly, or Ada, or whatever.

What’s best is to attract people to Haskell who can like it for what it is, because once we decide we need to change Haskell to suit the needs of the people who don’t like it, then we’re no longer talking about Haskell, but rather some strange derivative language. In principle there’s nothing wrong with that; I’m not married to Haskell — just to the ideas that make it great. After all, at some point a language will come along that takes Haskell’s ideas as a foundation and expands on them in some nontrivial way. When that happens, I’ll convert to the new language, just as I converted to Haskell. It’s not clear to me, though, that renaming everything will bring about this sort of revolution.

Besides, let’s be honest: is it really the names that are tripping people up, or is this just more “monads are like burritos?” Sure, you can look at a monoid and say “aha! if only someone had called this thing appendable, I would have understood it from the beginning.” But is that really true, or is it just an excuse for having a tough time grappling with a genuinely new idea?

Sure, I grant that it’s not very helpful to try to teach monads to people by starting with examples of adjoint functors, talking about the semantics of join, etc. It’s much more helpful to start by explaining how the idea gets used, and then get into the abstract business of it all (for the people who are so inclined). But this is a problem in how we explain the ideas, not in what we call them.

These algebraic and category theoretic foundations have inspired a lot of great ideas in the Haskell community. Renaming everything obfuscates the ideas, and will slow down future developments and unifications. In my experience (and I suspect the experience of many others), the “call it what it is” approach has made it much easier to see the big picture in my programs. Are we really ready to give up the conventions and way of thinking that got us where we are?

I’ve read a few comments about why Haskell is awesome. I even wrote an ironic blog post about it. Today I’m going to explain why I use Haskell for doing real work, entirely in terms of the tools Haskell developers use.

Edit: Immediately after posting, I found this article on Sententia cdsmith about reasons why Haskell is a good language. So between this post on tools and his post on the language, I think we’ve got our bases covered :)

Availability of quality libraries

I first really came into appreciating libraries by way of Perl’s CPAN, probably around 1999. These days I’m absolutely convinced that your language needs to have a searchable, cross-referenced, dependency-tracking library repository. For Haskell, it’s Hackage.

Hackage has many desirable qualities: Packages are written to work together rather than compete with one another. Searching for packages by name or description is performed by Google, and has all of the quality you’d expect as a result. But Hackage has another search option, which brings me to my next point…

Haskell is strongly-typed and purely-functional. Good Haskell style is all about writing tiny functions (one-liners!) and remaining abstract (code-reuse!). These qualities make the type signature of a function very telling.

Think about how many times you’ve been working with data in one format and needed a function that could convert it to something else. You’d like to avoid writing the function yourself (code-reuse!) but don’t know what it is called. How would you find it? Google around with related terms? Ask a mailing list?

The Haskell community has two search engines that trivially solve this problem: Hooge and Hayoo!. These engines can search for a function by name or by its type signature; and Hayoo! is linked into Hackage, so it is able to tell you which library contains the function you want.

Here’s a concrete example: I’ve got a list of numbers, and I want to split it up into two lists — one consisting of the evens, one consisting of the odds. This seems like a pretty specialized task, so I doubt there’s a function written for it explicitly. So let’s look for a function that takes a list, and a boolean test, and splits it into two lists — one consisting of the elements satisfying the test, and the other consisting of the elements that don’t.

That is, I need a function that takes a list of integers, and a function from integers to bools, and produces two lists of integers.

No problem: I jump over to Hoogle and search for functions of type [Int] -> (Int -> Bool) -> ([Int], [Int]). It produces a short list of results, tells me what library they are in, and even gives a brief description of what the function does. I quickly see that partition is the function I want.

Remember that Hayoo! works in conjunction with Hackage, so that I have this ability for all of the libraries in the standard repository. What other language is so centralized?

Project Management

We’ve got all the usual things — source control by darcs, unit testing by HUnit, automated testing by Quick Check, and source documentation by Haddock. We’ve also got package management by Cabal (tied into Hackage, of course).

We’ve got one other tool that is perhaps the strongest reason for the language — the Glorious Glasgow Haskell Compiler. You won’t find a more advanced compiler anywhere on earth. It produces code that is performance-competitive with C, has built in support for profiling, and features a rich interactive mode that both helps you test code and also explore types and interfaces.

Technology

For many people, the initial draw to Haskell is the advanced technology that is built into the language. Haskell was originally drafted as a “language playground,” giving researchers a place to experiment with new ideas. Over time it has adapted to keep the experiments that worked. Today it stands alone in its simultaneous support for many language features that the mainstream world probably won’t see for at least another 10 years.

This stuff isn’t just syntactic sugar, either. Haskell probably has better support for concurrency than any other language, due to a combination of its pure semantics, modern memory sharing techniques, and data-driven parallelism.

To get a sense for how wildly amazing Haskell-related technology, check out Automatic generation of free theorems — a tool that, given a function’s type signature, can write a function for you that has the correct signature! You won’t find this kind of thing anywhere else.

Community

Lastly we come to one of the most special features that Haskell offers: its unique developer community.

The Haskell community is famous for its strange blend of pure academics, working engineers, and tinkering hobbyists. The community has active mailing lists where people pour unimaginable amounts of time into giving each other detailed and useful answers. It is not at all uncommon for the discussion on the lists to lead to groundbreaking developments in Haskell development.

The community also has one of the most active language-centric IRC channels, complete with an IRC bot that evaluates Haskell code publicly, giving everyone a chance to experiment with code together in real-time.

Of course, the community does the “web 2.0” thing as well: we’ve got an active reddit, tons of active and insightful blogs, an electronic magazine, a Wikibook, and a weekly newsletter of online Haskell community happenings.

Conclusions

Haskell programmers generally feel like they’ve caught on to something very special. Every day there are new developments in the community that push the boundaries of technology, enabling people to write sophisticated programs in less time and with greater reliability. There really is a sense that we’re playing with the toys of the future, which have somehow been gifted to us today.

It’s a strange language — far enough ahead of the others that it can be tricky for beginners — but it really has quite a bit to offer. And with the availability of the supporting tools we’ve just looked at, it is beyond ready for prime time.

• Status

• RT @richinseattle: Happy to announce a 3-day advanced training on "Vuln Discovery and Triage Automation" at HITB in Singapore this fall htt… 5 days ago
• Builds step-indexed model of λ calc with mutable references in the internal language of a suitable topos (such as presheaves over ω). 6 days ago
• arxiv.org/abs/1208.3596 First steps in synthetic guarded domain theory, Birkedal, Møgelberg, Schwinghammer, Støvring. 6 days ago
• @level2three *understatement* 2 weeks ago
• @tmanning The eqn will have solutions, but the solution set won't be a curve; could still be some buggy output, but maybe not 2 weeks ago