Archive for the ‘Math’ Category

Authoring MathML

No Comments »

I am not entirely satisfied with the result that WP LaTex produces. Obviously, the white background on every little piece of math is a problem. Moreover, it only supports the simplest of layouts – at least I can’t get environments like displaymath, align etc. to work properly. Therefore, I decided to look into MathML. MathML is a W3 Recommendation specification for describing mathematics intended for machine to machine communication. That means in particular that MathML may be used by webservers to send mathematical content to client browsers.

Thus, MathML should be able to achieve the same goal as the WP LaTeX plug-in. However, this alternative comes at a price, since it relies on the browser being able to render MathML. Alas, browser support for MathML is somewhat limited: Firefox supports MathML, but IE needs a plug-in. You would think, Google caring so much about spreading good karma, that Google’s Chrome browser would support MathML, but it doesn’t. Not in any shape or form. Since I like Chrome very much for its speed and ease of use, I find this very disappointing.

However, most of the math I am authoring is just for my personal reference, so I don’t have to adhere to browser support restrictions too much and I decided to move forward and try to find an editor capable of producing MathML (besides Notepad, obviously).

The W3 organisation has a list of MathML editors, of which I have tried a few.

FireMath

This is a Firefox plug-in (much like Firebug etc.) and may be the best free option at the moment. It has a nice preview region, a reasonable layout and the generated XML is easily accesible. I will evaluate this further, before I pass my judgement.

http://www.firemath.info/

MathML Editor for Flash

The MathML Editor for Flash is, as the name suggests, a Flash application for editing and rendering MathML. You can try MathML Editor for Flash out here. It is pretty rudimentary and, unless I am greatly deceived, it is nigh impossible to typeset anything but the most basic expressions. The process of building an expression is very hierarchical, and you have to somewhat plan this hierarchy in advance. If you have got lots of indexes, superscripts, accents etc., you are going to have to start over again and again. Trying to typeset

Polynomial covering spaces stuff

drove me crazy with frustration. Also, I gave up on this application when it took me more than a few minutes to find the symbol \mathbb{C} (I never found it).

http://code.google.com/p/mathmleditor/


A note on distributive and modular lattices

No Comments »

I’ve been working a little with an old friend, modal logic, this weekend. This digressed into a study of lattices and Boolean algebras, so I thought I would write up some of my observations for archival. Also, I just like to say “lattice”.

Smock

If you know anything about lattices, you will probably find this stuff trivial. If you don’t know anything about lattices, a free and much better introduction can be found in A Course in Universal Algebra.

Definition: A distributive lattice is a lattice which satisfies the distributive laws:

D1: x \land (y \lor z) \simeq (x \land y) \lor (x \land z)
D2: x \lor (y \land z) \simeq (x \lor y) \land (x \lor z)

Actually, it can be shown that a lattice satisfies D1 iff it satisfies D2.

Definition: A lattice L is said to be modular if the modular law holds:

M : x \leq y \Rightarrow x \lor (y \land z) \simeq y \land (x \lor z)

Lemma: The modular law for lattices is equivalent to the identity

 (x \land y) \lor (y \land z) \simeq y \land ((x \land y) \lor z)

Proof
Assume that the modular law holds and consider the expression y \land ((x \land y) \lor z). Since x \land y \leq y we can apply the modular law to infer that y \land ((x \land y) \lor z) \simeq (x \land y) \lor (y \land z).

Now, assume that the identity holds and that x \leq y for some x, y, z \in L. Then x = x \land y so

x \lor (y \land z) \simeq
(x \land y) \lor (y \land z) \stackrel{\dagger}{\simeq}
y \land ((x \land y) \lor z) \simeq
y \land (x \lor z),

where the identity was used in \dagger. Thus, the modular law holds.\Box

Theorem: Every distributive lattice is modular.

Proof
Assume that x \leq y for some x, y, z \in L where L is a distributive lattice. Then y = x \lor y so
 x \lor (y \land z) \simeq (x \lor y) \land (x \lor z) \simeq y \land (x \lor z)

where we have made use of D2. The desired result now follows from the lemma.


Testing WP LaTeX

No Comments »
   \xymatrix{ 0 \ar[r] & Z_{n+1} \ar[r]^i \ar[d]^0 & C_{n+1} \ar[r]^\partial \ar[d]^\partial & B_n \ar[r] \ar[d]^0 & 0 \\ 0 \ar[r] & Z_{n} \ar[r]^i & C_n \ar[r]^\partial & B_{n-1} \ar[r] & 0}

I guess the WP LaTeX server doesn’t have the xy package installed.


F# and the Euler project

2 Comments »

At JAOO 2008 I attended the presentation “Learning F# and the Functional Point of View” by Robert Pickering. It’s been quite a while since I’ve done functional programming (I think it was when we implemented a small compiler in SML at DIKU a few years back), so this was a nice opportunity to revisit the functional paradigm. Since “real men use the stack” and since functional programming and its immutable datastructures will really come into its own when we’re talking concurrent applications and the plethora-of-processors machines of the future, it is about time we start considering using functional programming in main stream applications.

All of the above lead me to pick up F# and a book (“Foundations of F#“, also by Robert) this past weekend. In order to get a real feel for the language I decided to tackle some of the problems at Project Euler while reading the book. Thus, without further ado, here’s the Euler Project’s Problem #3 and my solution using F#:

Problem 3:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

Solution using F#:

(comments below)

let doesNotContainAsFactors (p:bigint) xs =
(List.for_all (fun a -> not (p % a = 0I)) xs)

let rec nextPrime (x:bigint) primes =
    if doesNotContainAsFactors x primes then
        x, x::primes
    else
        nextPrime (x+1I) primes

(* Find largest prime factor in x*)
let largestPrimeFactor x =
    let rec innerLargestPrimeFactor (x:bigint) primesLessThanCandidate candidate =
        if candidate = x then
            x
        else
            match x % candidate with
            | 0I -> innerLargestPrimeFactor
                (x / candidate) primesLessThanCandidate candidate
            | _ ->
                match (nextPrime candidate primesLessThanCandidate) with
                (newPrime, newPrimesList) ->
                    innerLargestPrimeFactor x newPrimesList newPrime
            innerLargestPrimeFactor x [] 2I

First, we define a function

doesNotContainAsFactors : bigint -> BigInt list -> bool.

This function takes a list of integers xs (as you can see from definition they are really bigints, but for convenience I’m going to continue to refer to them as integers) and an integer p. The function returns true if no element of xs is a divisor in p. Thus, if xs contains all primes smaller than p then doesNotContainAsFactors will return true exactly when p is a prime.
The next function to consider is

nextPrime : bigint -> BigInt list -> bigint * bigint list.

This function takes an integer x and a list primes of integers. When xs contains all the primes less than x the function uses doesNotContainAsFactors to find the first prime greater than or equal to x. It returns this prime along with a list of all primes less than or equal to the newly found prime.
Next comes the main function,

largestPrimeFactor : bigint -> bigint

which is to take an integer x and return its largest prime factor. It does this by testing whether 2 divides x. If it doesn’t, nextPrime is used to find the next prime and the test is repeated. When a prime divides x we factor out the prime by repeating the test on the quotient. Since the primes we test are continually getting larger, we will eventually have factored out all but the largest prime divisor. Once multiple occurences of this largest prime divisor have been factored out, the candidate prime we are trying to divide into x will now equal x. Thus, once we recognize that this is the case, we return x.

So, what is the largest prime factor of 600851475143?. Well, we evaluate largestPrimeFactor 600851475143I and see that the answer is 6857.

I am not entirely happy with the performance of the functions above. Finding the largest prime of 600851475143 does take a couple of seconds on my laptop. I haven’t analyzed the complexity of the code above, but it sure doesn’t feel right. That might be a topic for a future post. Also, comments are welcome :-)


Math in WordPress

1 Comment »

Last night I decided to investigate whether I would be able to publish math in my WordPress blog. I wanted to be able to write mathematical formulas and diagrams in some sort of markup language and have it rendered as it would be in a book – i.e. arrows should be real arrows, not just –>, parentheses should be properly sized etc.. At the moment, the most promising solution seems to be the LaTeX for WordPress plug-in. Using this plug-in you can embed LaTeX code directly in your blog by enclosing it in a pair of double-dollar-tags. When the page is displayed, the plug-in will append the LaTeX code to a URI and request a public Mimetex service at http://l.wordpress.com/latex.php, which will in turn respond with an image stream of the rendered formula. So, if I write

0 \to \text{Ker}(h) \stackrel{i}{\hookrightarrow} H^n(C;G) \stackrel{h}{\to} \text{Hom}(H_n(C),G) \to 0

I will get this:

$$ {0 \to \text{Ker}(h) \stackrel{i}{\hookrightarrow} H^n(C;G) \stackrel{h}{\to} \text{Hom}(H_n(C),G) \to 0} $$

Pretty sweet!
My only complaint would be that the public WordPress latex service doesn’t seem to support the rendering of commutative diagrams through the xy package: if I write

\xymatrix{ 0 \ar[r] & Z_{n+1} \ar[r]^i \ar[d]^0 & C_{n+1} \ar[r]^\partial \ar[d]^\partial & B_n \ar[r] \ar[d]^0 & 0 \\ 0 \ar[r] & Z_{n} \ar[r]^i & C_n \ar[r]^\partial & B_{n-1} \ar[r] & 0}

I get

$$ \xymatrix{ 0 \ar[r] & Z_{n+1} \ar[r]^i \ar[d]^0 & C_{n+1} \ar[r]^\partial \ar[d]^\partial & B_n \ar[r] \ar[d]^0 & 0 \\ 0 \ar[r] & Z_{n} \ar[r]^i & C_n \ar[r]^\partial & B_{n-1} \ar[r] & 0}$$

while I would have expected something like

The commutative diagram as I would have liked it

(I ran this through latex on my laptop, so I think it ought to parse).

All in all, I think the end result of the Latex for WordPress plug-in is pretty cool. In general, the lack of support for commutative diagrams in the public WordPress service is a minor issue, but since I expect to be blogging a bit about algebraic topology and category theory, I may put an effort into setting up a properly configured service, If I can find the time and a suitable environment.

It is worth noting that the browser always requests images from your webserver and never sends a request directly to the Mimetex service. Thus, the first time a formula is to be rendered, the webserver requests the image from the Mimetex service, caches the result locally and only then serves up the image to the browser. Obviously, this takes quite a burden off of the shoulders of the public Mimetex service providers.