Archive for May, 2005

Math::Symbolic Modules

Tuesday, May 31st, 2005

For some reason, I ran across Steffen Mueller’s website again (I’ve been there in the distant past when I was obsessed with Perl), and saw his list of Perl modules. It looks like we share some interests: programming, physics, math. I was particularly impressed by the Math::Symbolic series of modules that he’s written; it has almost as many features as some of the crappy ‘CASes’ out there, except for integration. And from reading the POD on the site, it seems like integration of at least rational functions shouldn’t be too hard with the tree structure he’s using. I wonder why he hasn’t implemented it? Too bad there is nothing like Math::Symbolic for Python. While I’m at it, too bad there’s nothing like CPAN for Python, or PPM repositories.

An Intro to Typography

Tuesday, May 31st, 2005

I’m reading a practical introduction to typography at the FreeType website. It covers all the basics of font terminology needed to use FreeType, along with simple algorithms for rendering text. I used to be into typography, so I’m familiar with some of the concepts, but it also has some interesting information that I never came across before. For instance, most word processors base their layout on the resolution of the printer you’re using, so if you go from one printer to another, the layout of the document may change drastically— this is why a Word document can increase in size when you write it one place and print it another. That’s something I never really considered before, even though I have noticed it, and occasionally been annoyed. Adobe Acrobat is of course immune to this problem, because it computes its font metrics separately.

On further consideration, it looks like I’m going to have to write the layout algorithms for the notebook interface myself: I can’t think of a noncompromising way to enhance any text widgets so they can handle math properly, and simply embedding special widgets won’t work.

Compiling Python Extensions w/ Mingw32

Monday, May 30th, 2005

It is an unpleasant fact that there is no Python binding for FreeType 2— the one I had discovered is apparently very outdated, and not being worked on. Since I thought I’d at least look into the possibility of binding it myself; looking at the code for that one, it doesn’t look like too daunting a task: tedious, but not requiring any tricks. So I figured, if I concentrate on just the portions of the API I need, I should be able to handle this.

First, I had to get a copy of Mingw32; luckily for me, it turns out that comes bundled in the Enthought Python distribution, so I was saved the hassle of a 49Mb download over a dial-up connection. This morning I spent about 2 hours searching on the Internet and wrestling at the command line trying to figure out how to compile C extensions for Python. That was an unpleasant reminder of why I dislike C programming so much, especially under Windows: all the switches, and linking, and worrying about library types and versions; and despite all the care in the world and careful adherence to instructions, nothing ever works right. Nontrivial C programming has always been like black magic to me. And after all that, I discover that what I needed to do was very simple:

  • Open up python, and run
    [python]
    from scipy_distutils.mingw32ccompiler import *
    build_import_library()
    [/python]
  • Make my extension’s dll by calling gcc hello.c -IC:\Python23\include -Lc:\python23\libs -lpython23 -shared -o hello.dll

And that’s it. I don’t know what distutils is, but it seems to be the standard for installing extensions, so maybe it’s worth looking into more. Also, once I build the library with the function call, it remains in the library directory, so I need do the first step only once.

Now I need to figure out SWIG, and the Freetype API.

Mathematical Typesetting and Google meta-tags

Sunday, May 29th, 2005

All fired up since rediscovering FreeType, I started looking for resources on mathematical typesetting, just for fun— all I’m doing doesn’t seem to require any rareified knowledge, just basic sup-/sub-/over-/under-scripts and accents, maybe a few more details— but it turns out the only one I could find that is even nearly that specific is ‘Digital Typography’ by Donald E. Knuth (who I recently saw in a Google result described as the Leonard Euler of CS… I kid you not!), which from reading the table of contents is not that focused on mathematical typesetting issues. There seems to be one chapter on it specifically, then the others are general typesetting issues. I found an interesting bibliography on typesetting/OCR and related issues: http://www.math.utah.edu:8080/pub/tex/bib/font.bib.

More immediately useful, I now have choices of font sets to work with: the AMS distributes the CM fonts in Type 1 format, and Elsevier supposedly offers a comprehensive set of math fonts (esstix?), but I haven’t been able to log into the ftp site. Then, in the future, I’m looking forward to the release of the Stix Fonts; those seem like they’ll be ultra-comprehensive.

On an unrelated note, the thought has often struck me that it is easier– on your hands for one; less cut and paste, or direct typing— and arguably more natural to give keywords to Google search by, and maybe a little guiding details (e.g.: it’s the 2nd result; it’s on the 4th page, etc.) than trying to track URLs. In fact, since there’s more of a context to that way of linking, it might provide more info than a direct link. There should be a semi-formalism for this (i.e. standardized enough so a person, but not necessarily a program, knows what you mean), like google{math typesetting bibliography}{2 down}{3rd page}, or something. Of course, this isn’t a good course to take if you want your link to last long. Hmmm, to think of it, this could be the basis of a neat WP-plugin: one that displays the google{} string, and use it as a link to the google results (linking to the correct page number if that is specified); maybe you could even code up some javascript that could parse some of this info out of a google search result url, and turn it into a google{} string— for even more leverage, a plugin for your browser that automatically makes such tags for each link you click on in a search result, and automatically stores them for later retrieval. If you’re anything like me, your average Internet session consists of a lot of visits to Google, to the point where you could track what you were doing and where you went very well from a list of such meta-tags. And of course, you could have similar yahoo{} and msn{} meta-tags.

Python and Pixel perfect placement

Sunday, May 29th, 2005

I’ve been tinkering around with the basics of a notebook interface for CASes. I’ve been using Tkinter up to now, which is turning out to be the easiest GUI kit I’ve ever messed around with— unfortunately, Tkinter doesn’t seem to support the level of control I need over font information: to manage all the weird convolutions (no pun intended) that mathematical expressions can involve, I’m having to rewrite a text widget from scratch. At least, I haven’t attempted to ‘merely modify’ the text widget, because I think that would be a harder task (and perhaps impossible; certainly more ambitious than I want to be), using any GUI kit. So I’ve been hopping around from Python GUI kit to kit: wxPython, wax, PythonCard, PyGTK, Tkinter, Jython/Swing. The situation was equally hopeless: due to the cross-platform requirements of all of these, the font control is lacking. For instance, there is no reliable way to load a font file with a particular name, as far as I could see; it seems like a lot of the finer levels of font selection can only be managed through the font selection dialogs offered, which is inappropriate for this situation. Also, there didn’t seem to be very good, or reliable ways of gauging the bounding box of a piece of text. These are basically the two features I need most.

I finally remembered today, that the FreeType library does these things and more, and is cross-platform. By using the FreeType library, I could treat individual glyphs of the font as images, and construct all mathematical expressions as images, using logic separate from the main text widget, so I could use rich text widgets, which handle images and text, for input purposes. That would save a lot of trouble— to be honest, given my laziness, would stop the project from halting in its tracks—, because I wouldn’t have to worry about the annoying details of managing line wrapping, justification, etc, or even image placement (assuming the kit used has a rich enough text editor widget). All I have to implement is the logic which makes the images seem responsive as text to user input, handles high-lighting, cursor display, etc. Two problems remain: finding a Python binding for FreeType— it seems there is one, ft2, but I have not tried it out to see if I can work with it— and making a choice of toolkits to use. Tkinter seems like the best choice in terms of standardization, but I’m going to look at wxPython and PyGTK to see if either of those might make my image interaction tasks easier; I’m mostly concerned about cursor positioning and resizing and high-lighting control. Of course, there is also the not insignificant problem of the actual placement of the glyphs; mostly, I’m worried about figuring out how to place the glyphs that form extensible characters, like an integral sign. But I’ll cross that Rubicon once I get to it.

Implicit Equation Grapher

Saturday, May 28th, 2005

For a while now, I’ve been thinking about plotting implicit equations in the back of my head. Mathematica’s method still eludes me—all you do is specify the equation, and the range of x,y values to consider—; the only way I can think of involves finding at least one solution to the equation, and then following the gradient of the function in a way that keeps the value as close to 0 as possible. Besides the obvious drawback of requiring a seed, this technique also diverges from the actual curve, because after the first value, all the points considered to be on the curve are actually not. So it is possible, if you have a convoluted enough expression, that what you end up with looks nothing like the actual curve.

To pass the time today while at a graduation ceremony, I took along a book with me, and I was surprised to see that it had almost the exact same technique I was thinking of for graphing implicit equations, except being on paper, it was more detailed. Supposedly this was gleaned from a research paper; therefore at least some other people who have considered this problem have run into the same dead-end.

Amusingly— considering that using this technique requires having a closed form expression for the gradient—, this was an exercise at the end of the chapter:

Develop a menu-driven, interactive graphics program to draw planar curves that are specified implicitly. Use the method developed in Section 2.3.2. Provide several examples of implicit functions to be drawn.

Interpreting that liberally, that requires the program to parse and calculate derivatives for arbitrary expressions. Of course, you could always take the easy way out and just hardcode in the examples.

Bombelli father of complex arithmetic?

Thursday, May 26th, 2005

I have often wondered what caused complex arithmetic to be defined the way it is. The definition of the addition seems obvious, but why is it that
 (a, b)(c,d) = (ac-bd, bc+ad)? The answer according to Tristan Needham in his book Visual Complex Analysis:

Apparently, the mathematician Bombelli realized that the solution to the general cubic equation x^3 = 3px+2q given in Cardano’s Ars Magna:

 \displaystyle x = \sqrt[3]{q + \sqrt{q^2 - p^3}} + \sqrt[3]{q - \sqrt{q^2 - p^3}}

gives complex solutions if p^3 > q^2. For the example x^3 = 15x + 4, the solution is  x = \sqrt[3]{2 + 11i} + \sqrt[3]{2 - 11i}. In general, when x is complex, that implies the equation x^3 = 3px + 2q has no solution, but by graphing the line and the cubic, you can see that there is a solution in this case: x=4.

From here, Bombelli had his “wild idea”: what if he worked backwards to determine what  x = \sqrt[3]{2 + 11i} + \sqrt[3]{2 - 11i} was? First, he needed to determine what \sqrt[3]{2 \pm 11i} is; he did so by assuming \sqrt[3]{2 \pm 11i} = 2 \pm ni (Why? I don’t know; it doesn’t seem obvious— maybe he tried different numbers besides 2, and this was one that worked). From here, he assumed the standard laws of complex arithmetic, to solve the equation (2 \pm ni)^3 = 2 \pm 11i, yielding x=4 as expected.

This was the first example of complex arithmetic at work. More specifically, before Bombelli considered this instance in which complex arithmetic was needed to solve a cubic equation (consider the graph of x^3 and a line; there is always an intersection, so there is always a real solution), complex numbers were encountered only in the solution to quadratic equations. There, they could be ignored, since the presence of a complex number indicates that the given line and the parabola x^2 do not intersect.

Math books worth the bother

Thursday, May 26th, 2005

Here is a hopefully-to-be-seldom–updated (since I’ve only read parts of the books on this list, and intend to finish all of them at some point) list of math books that I think are very original, very thorough, or in general, worth the bother of attempting to read. Which is a rare thing indeed.

Beyond Undergraduate Mathematics

Thursday, May 26th, 2005

This is the working draft of an article I’m writing for kuro5hin.org, and hence subject to change; it’s been way too long since a good technical article was written there, and that’s part of why I loved the site so much. I’m attempting to recruit help from the UH math club members in the form of donations of sections on the parts of mathematics whose existence I am only aware of, e.g. number theory.

Excerpt (for the listing on the k5 section page)

Mathematics is a beautiful art in all its varied forms. Unfortunately, most of us do not get to see any further into this wonderful world than calculus. One of the factors sustaining the development of mathematics is the continuous development of unexpected applications in the physical sciences. In this article, I will give an overview of some of the mathematical sciences with direct physical applications, and hopefully a sense of their beauty as well as some of their guiding principles: less is more, generalization as a means to an end.

Algebra and Analysis: the twin pillars of mathematics

Most of the mathematical sciences can be categorized as either algebraic or analytic. The algebraic sciences are those that concern themselves with the results arising from the structure of certain spaces. For instance, linear algebra is the study of results arising from the structure of vector spaces. That is, we take a collection of objects that have operations defined on them— in the case of linear algebra, addition and multiplication by scalars— and pull out all the meaning we can find, in all the generality we can manage. The beauty of algebra is that the results apply to any system with the given structure, so a lot of results translate to very different spaces. For instance, if you have any inner-product space ( a vector space with an inner-product defined on it: a generalization of a dot product, which makes it possible to define angles between the vectors, and hence geometricize the space), then you know that there is an orthonormal basis for that space. Since the space of continuous functions is a vector space, this tells us that we can find a set of continuous functions such that every other continuous function is expressible as a sum of these functions. In addition to linear
algebra, algebra gives us concepts like rings and fields, useful generalizations of number systems. The modern approach to algebra is to specify a space in terms of what axioms it must satisfy, and then develop every
result as a logical conclusion of those axioms. The trick and the art to this is anticipating or deducing what combinations of axioms are useful.

Because of its abstracted nature, algebra’s roots reach deep into nearly every advanced mathematical discipline, and it even has some direct practical applications. Especially interesting in the latter camp is the Risch algorithm, which determines whether an indefinite integral is expressible in terms of elementary functions and if so returns the primitive; it relies heavily on algebraic tools: differential fields, extensions fields, etc. Algebra is intrinsically interesting because of the beauty of its abstract deductions ( somewhat similar to how a programming language specification is beautiful because you can see the depth of thinking put into it, and the precision with which it is worded), but its proliferation of definitions and axioms can seem
sterile unless you simultaneously see applications of them, or follow the historical development of those concepts so you can see the motivations behind them. The only interesting tidbit I have left on algebra— in fact, the reason why I came to have any interest in algebra at all— is the fact that it is the backbone of every CAS (Computer Algebra System, like Mathematica, Maple, Axiom, etc.), especially in the form of the Risch algorithm and the techniques used to solve systems of equations. It is interesting to note that Axiom is constructed to mirror the structures studied in algebra; by maintaining this high-level information, it makes it possible to write algorithms (for calculating GCDS, etc.) that will work for any such space without modification.

Analytic sciences are those that concern themselves specifically with a particular type of algebraic structure: complete fields. More intuitively, analytic sciences study spaces in which sequences can be said to converge, or equivalently every set has a least upper and greatest lower bound; such spaces are also known as Archimedean fields. The most common, and most used complete fields are simply the real numbers and the complex numbers. The rationals are an example of a space which does not have the Archimedean property: if you let S = {x in Q | x^2 <= 2}, then clearly S does not have a least upper bound, because you can find a rational number arbitrarily close to sqrt{2}.

It is from the Archimedean property that we get all the goodies that make analysis such a useful, powerful, and intuitive tool: continuity, the intermediate value theorem, the fundamental theorem of calculus... all of these follow from the Archimedean property. Informally, I think of analysis as dealing with smooth spaces, and as such, I find it much more compatible with physical intuition than algebra, in general.

Analysis is typically divided into Real and Complex Analysis: real analysis deals exclusively with analysis on the real number line, while complex analysis deals with analysis in the complex plane. Of course, all the results of real analysis are results in complex analysis, but not vice versa. I've not studied enough of complex analysis to see why the distinction is made: why there are real analysists, and complex analysists. Maybe one reason for the distinction lies in the fact that the complex plane is a unique mathematical entity: it is the algebraic completion of the real numbers. Simply speaking, every polynomial with real (or for that matter, complex) coefficients has a root in the complex plane. In fact, this is the historical justification for the introduction of
imaginary numbers: they made possible the formal solution of polynomials. This makes the complex plane a natural and powerful domain for the study of polynomials. As another possible reason for the distinction, perhaps a stronger one, is there is a phenomenon encountered in the complex plane that has no analog on the real line: analyticity. Analyticity is a strange property that differentiable functions possess in the complex plane: while it is possible to have a differentiable real function whose derivative is not differentiable (e.g. the integral of the absolute value function), if a function is differentiable in the complex plane, automagically derivatives of all orders exist for that function. Furthermore, in some neighborhood of the function, the function is identical with its Taylor series; this is profound because it is possible to construct a real function that is differentiable of all orders at a given point, yet in no neighborhood of that point is the function equal to its Taylor series. Analyticity, also known as holomorphicity, is a powerful and useful tool both in mathematics and engineering and physics. One more strange property of holomorphic functions: they are as delicate as
soap bubbles. If you perturb the function at a single point, it loses it's analyticity; therefore an analytic function can be defined solely by it's values on a sequence with a limit point lieing in the domain of definition of
the function. Hadamard, a famous mathematician, once said "The shortest path between two truths in the real domain passes through the complex domain"; this has held true in my brief experience: for instance, instead of the cumbersome trigonometric Fourier series, most modern expositions deal almost exclusively with complex exponential Fourier series which are a lot more palatable (more on Fourier series later). Complex analysis provides a powerful toolkit for handling a whole array of physically motivated problems: consider the use of the complex exponential (of course, a holomorphic function; in fact, an entire function, one that is holomorphic on the entire complex plane, a rare beauty) in phasors and the solution to differential
equations in physics.

Of course, there are branches of mathematics that don't fall neatly into the realms of algebra or analysis: while calculus is clearly in the analysis camp, the study of differentiable manifolds (very important!, more later) demands knowledge of both, and (classical) number theory is not usually regarded as an algebraic
theory. Really, in modern math, algebra and analysis are very comfortable bedmates.