I ran across this problem in a reddit side-bar job-ad, and was intrigued by the task (description paraphrased to decrease googleability):

Write a function

uint64_t bitsquares(uint64_t a, uint64_t b);

such that it return the number of integers in [a,b] that have a square number of bits set to 1. Your function should run in less than O(b-a).

I think I see how to do it in something like logarithmic time. Here’s how:

First off, we notice that we can list all the squares between 0 and 64: these are 0, 1, 9, 16, 25, 36, 49, and 64. The function I will propose will run through a binary tree of depth 64, shortcutting through branches whenever it can. In fact; changing implementation language completely, I wonder if I cannot even write it comprehensively in Haskell.

So, today I saw this in my Twitter feed:

«Phil Harvey wants us to partition {1,…,16} into two sets of equal size so each subset has the same sum, sum of squares and sum of cubes.» — posted by @MathsJam and retweeted @haggismaths.

Sounds implausible was my first though. My second thought was that there aren’t actually ALL that many of those: we can actually test this.

So, here’s a short collection of python lines to _do_ that testing.

import itertools
allIdx = range(1,17)
sets = itertools.combinations(allIdx,8)
setpairs = [(list(s), [i for i in allIdx if i not in s]) for s in sets]
def f((s1,s2)): return (sum(s1)-sum(s2), sum(map(lambda n: n**2, s1))-sum(map(lambda n: n**2, s2)), sum(map(lambda n: n**3, s1))-sum(map(lambda n: n**3, s2)))

goodsets = [ss for ss in setpairs if f(ss) == (0,0,0)]

And back comes one single response (actually, two, because the comparison is symmetric).

This is a typed up copy of my lecture notes from the combinatorics seminar at KTH, 2010-09-01. This is not a perfect copy of what was said at the seminar, rather a starting point from which the talk grew.

In some points, I’ve tried to fill in the most sketchy and un-articulated points with some simile of what I ended up actually saying.

Combinatorial species started out as a theory to deal with enumerative combinatorics, by providing a toolset & calculus for formal power series. (see Bergeron-Labelle-Leroux and Joyal)

As it turns out, not only is species useful for manipulating generating functions, btu it provides this with a categorical approach that may be transplanted into other areas.

For the benefit of the entire audience, I shall introduce some definitions.

Definition: A category C is a collection of objects and arrows with each arrow assigned a source and target object, such that

Category theory, with an origin in algebra and topology, has found use in recent decades for computer science and logic applications. Possibly most clearly, this is seen in the design of the programming language Haskell – where the categorical paradigm suffuses the language design, and gives rise to several of the language constructs, most prominently the Monad.

In this course, we will teach category theory from first principles with an eye towards its applications to and correspondences with Haskell and the theory of functional programming. We expect students to previously or currently be taking CS242 and to have some level of mathematical maturity. We also expect students to have had contact with linear algebra and discrete mathematics in order to follow the motivating examples behind the theory expounded.

Wednesdays at 4.15.

Online notes will appear successively on the Haskell wiki on http://haskell.org/haskellwiki/User:Michiexile/MATH198

Dear blogosphere,

come this fall, I shall be teaching. My first lecture course, ever.

The subject shall be on introducing Category Theory from the bottom up, in a manner digestible for Computer Science Undergraduates who have seen Haskell and been left wanting more from that contact.

And thus comes my question to you all: what would you like to see in such a course? Is there any advice you want to give me on how to make the course awesome?

The obvious bits are obvious. I shall have to discuss categories, functors, (co)products, (co)limits, monads, monoids, adjoints, natural transformations, the Curry-Howard isomorphism, the Hom-Tensor adjunction, categorical interpretation of data types. And all of it with explicit reference to how all these things influence Haskell, as well as plenty of mathematical examples.

But what ideas can you give me to make this greater than I’d make it on my own?

I started fiddling around with R again, and ended up playing with a zipcode database.

So, first I downloaded the zipcode database at Mapping Hacks, and unpacked the zipfile in my working directory.

Then, I loaded the data into R

So, now I have an R frame containing a lot of US cities, their geographical coordinates, and their zip codes. So we can start playing with the plot command! After rooting around a bit, I ended up settling on the smallest footprint plot dot I could make R produce, by setting the option pch=20 in the plot options. Hence, I ended up with a command basically like this:

This post is to give you all a very swift and breakneck introduction to Gröbner bases; not trying to be a nice and soft introduction, but much more leading up to announcing the latest research output from me.

Recall how you would run the Gaussian algorithm on a matrix. You’d take the leftmost upmost non-zero entry, divide its row by its value, and then use that row to eliminate anything in the corresponding column.

Once we have the matrix on echelon form, we can then do lots of things with it. Importantly, we can use substitution using the leading terms to do equation system solving.

The starting point for the theory of Gr̦bner bases was that the same method could be used Рwith some modification Рto produce something from a bunch of polynomials that ends up being as useful as a row-reduced echelon form.

Or actually, I haven’t quite yet.

But, out of a whim, I downloaded J and started to play with it while reading this set of neat notes on Functional Programming and J.

And … well … my reaction so far is kinda “Buh!? What the *** just happened there?”

The first example I ran across, tried to read, and finally managed to is the following:

This snippet is supposed to tell us how many 0s are trailing 100!. To get at this, we first need to figure out what, exactly, is done here. First observation is that 100! is the product of all integers from 1 to 100. The second is that the number of 0s trailing this is the same as the lower of the orders of 2 and 5, respectively, dividing 100!. Which, in turn is the lower of the numbers of 2s and 5s occurring in the totality of all prime decompositions of all the integers from 1 to 100.

This is extremely early playing around. It touches on things I’m going to be working with in Stanford, but at this point, I’m not even up on toy level.

We’ll start by generating a dataset. Essentially, I’ll take the trefolium, sample points on the curve, and then perturb each point ever so slightly.

As a result, we get a dataset that looks like this:

So, let’s pick a sample from the dataset. What I’d really want to do now would be to do the witness complex construction, but I haven’t figured enough out about how R ticks to do quite that. So we’ll pick a sample and then build the 1-skeleton of the Rips-Vietoris complex using Euclidean distance between points. This means, we’ll draw a graph on the dataset with an edge between two sample points whenever they are within ε from each other.

First off, I’d ask your pardon for the lull in postings – this spring has been insane. It has been very much fun – traveling the world, talking about my research and meeting people I only knew electronically – and also very intense.

To break the lull, I thought I’d try to pick up what I did last summer: parallel computing on clusters. It’s been a bit of blog chatter about SAGE and how SAGE suddenly has transformed from a Really Good Idea to something that starts to corner out most other systems in usability and flexibility.

Matlab? SciPy bundled with SAGE and the Python integration seems to be at least as good, if not better.
Maple? Mathematica? Maxima? Singular? GAP? SAGE interfaces with all those that it doesn’t emulate.

I saw the Cerebrate solve the first Scripting Games challenge: Pairing off. And immediately thought “I can do that in Haskell too”.

So, here it is.

import Data.List

cards = [(1,7),(0,5),(3,7),(2,7),(2,13)]

countpairs [] = 0
countpairs [a] = 0
countpairs (a:as) = length . filter (((snd a)==) . snd) $ as

pairingOff = sum . map countpairs . tails

And that’s that. Alas, the actual competition only takes Perl, VBScript and PowerShell, so I won’t be submitting this.

Brent Yorgey wrote a post on using category theory to formalize patch theory. In the middle of it, he talks about the need to commute a patch to the end of a patch series, in order to apply a patch undoing it. He suggests a necessary condition to do this is that, given patches P and Q, we need to be able to find patches Q’ and P’ such that PQ=Q’P', and preferably such that Q’ and P’ capture some of the info in P and Q.

However, as such, this is not enough to solve the issue. For one thing, we can set Q’=P and P’=Q, and things are the way he asks for.

Now, I wonder whether we can solve this by using PROPs (or possibly di-operads or something like that). Let’s represent a document as a list of some sort of tokens. We’ll set the set of all lists of length , and we’ll set to denote operations that take a list of length n and returns a list of length m.

Last week, the news hit the blogosphere that Google had released a beta API for generating graphs using a reasonably easy and transparent GET parametrisation.

Inspired by this, and inspired by my early playing around with Ruby on Rails, I decided to whack together a Rails plugin that takes care of building the Google Charts IMG tag using what I hope is reasonably easy to use syntax.

I have a test-site using random data up for playing around with it.

The test-site as such runs on Ruby on Rails. The controller does some parsing and setting up of relevant arrays, and primarily generates random data for plotting.

The view has the following source code:

So, there is this one big and neat framework called Rails, building on top of this one neat new programming language called Ruby.

And one of the things that makes Rails so Damn Neat is that if you only set things up the right way around, it guesses almost everything you need it to guess for you.

One of the ways it does this is by pluralization. Basically, the model Foo has a model defined in app/model/foo.rb and it accesses the database table foos.

So, when talking a good friend through the basics, we created the table persons and generated the model Person. And promptly got an error from the framework.

It turns out that the pluralization of person is people. I wonder what else irregularities they built into the system. If I have a model called Index, does Rails expect it to read from the database table indexes or from indices?

dynkin:~/magma> magma
Magma V2.14-D250907   Wed Sep 26 2007 13:19:51 on dynkin   [Seed = 1]
Type ? for help.  Type -D to quit.

Loading startup file "/home/mik/.magmarc"

> Attach("homotopy.m");
> Attach("assoc.m");
> Aoo := ConstructAooRecord(DihedralGroup(4),10);
> S := CohomologyRingQuotient(Aoo`R);
> CalculateHighProduct(Aoo,[x,y,x,y]);
z
> exit;
Total time: 203.039 seconds, Total memory usage: 146.18MB

And this is one major reason for the lack of updates recently.

Trying to make the time until my flight leaves tomorrow go by, I played around a bit with the proof assistant Coq. And after wrestling a LOT with the assistant, I ended up being able to prove some pretty basic group theory results.

And this is how it goes:

This sets the stage. It defines a group as a group object in Set, but without the diagonal map. It produces a minimal definition – the left identity and inverse follow from the right ones, which we shall prove immediately.

One thing that has been bugging me for quite some time with AucTeX (which I love, in general) has been that I wasn’t able to reset the bloody hot key for math mode input.

The original setting maps to Shift-key left of backspace-space, since it’s an accent key which I occasionally use for .. y’know .. accenting letters, and thus don’t want immediate output from. And M-x set-variable LaTeX-math-abbrev-prefix didn’t do anything close to what I expected.

Today, I, on a whim, go and search the auctex mailing list archives for this. And lo and behold! One of the first messages tells me that I need to do M-x customize-variable LaTeX-math-abbrev-prefix. So I do, and it has my changes already, but not committed, so after committing the changes I try it out and it just works!

This should speed up usage of Emacs for me a bit.

IMPORTANT: Note that the implementation herein is severely flawed. Do not use this.

One subject I spent a lot of time thinking about this spring was taking tensor products of A_∞-algebras. This turns out to actually already being solved – having a very combinatorial and pretty neat solution.

Recall that we can describe ways to associate operations and homotopy of associators by a sequence of polyhedra K_n, n=2,3,.., called the associahedra. An A_∞-algebra can be defined as being a map from the cellular chains on the Associahedra to n-ary endomorphisms of a graded vector space.

If this was incomprehensible to you, no matter for this post. The essence is that by figuring out how to deal with these polyhedra, we can figure out how to deal with A_∞-algebras.

Conway’s Look-and-say sequence

Syntaxfree writes over at his blog about a silly little toy he wrote, using the PFP library, to generate random text.

Now, his text is unreadable. I mean, it’s even unpronounceable. Why? Because he’s looking at bigram distributions of letter.

Great, I thought, I’ll do him one better. Random text using bigram distributions on words must surely be a LOT better than random text using bigram distributions on letters. At least the words come out readable, and they may even come out in a decent order.

So I sat down with his code, and hacked, tweaked, and monadized it to this

Inspired by other bloggers on Planet Haskell, I thought I’d just sit down and write a retrospection post, reviewing the past year – primarily from angles such as mathematics, computers and my generic life situation.

It divides neatly into two different sections: the months as a commercial programmer and the months as PhD student and academic careerist.

The year began still working for Teleca Systems, and with security consulting for Stockholm-based firms and frequent trips back home.

Then as the year went on and my PhD applications grew more and more, I started getting results. I got invited to Bonn for an interview with the Homology and Homotopy graduate school program – which was in the end turned down because I was more of a homological algebraist than a topologist. And the week after that, I was invited to Jena for an interview for a position doing PhD work on computational homological algebra. The interview went well, the potential advisor was nice (and a once-roleplaying gamer to sweeten the deal more) and I got the position just a few days later.

In a recent post, pozorvlak reminded me of one of the reason it is important to have a good, obvious, and quick-to-write programming language around.

He, as I, is a mathematician, spending his time thinking, finding patterns, and trying to formulate (more or less) absolute proof that his patterns hold all the time, alternatively ways to demonstrate that they may not be universal.

In the post linked above, he starts by a neat little exercise, gets interested, and goes out to look at more examples. These show a very clear pattern, and after following this pattern quite some way out, he finally believes the pattern enough to start searching for a proof: which he also finds.

This term, I’m listening to a lecture course on Computational Group Theory. As a good exercise, I plan to implement everything we talk about as Haskell functions as well.

The first lecture was mainly an introduction to the area, ending with a very naïve algorithm to generate a permutation group from a set of generators. Next week will bring less naïve algorithms with not quite as horrible complexity.

Before the algorithm can be brought, we’d want some undergrowth: we’d want to be able to work with permutations at all. So, we’ll start with the basic group theory and permutation implementations. A lot of this is stolen or rewritten from this permutation group code.

Our code will make use of two libraries, so if you collate code snippets while reading this, you’ll want to use

If you don’t want to bother with that, the code is available here.

As we left off the last installment, we were just about capable to open up a window, and draw some basic things in it by giving coordinate lists to the command renderPrimitive. The programs we built suffered under a couple of very infringing and ugly restraints when we wrote them – for one, they weren’t really very modularized. The code would have been much clearer had we farmed out important subtasks on other modules. For another, we never even considered the fact that some manipulations would not necessarily be good to do on the entire picture.

Some modules

To deal with the first problem, let’s break apart our program a little bit, forming several more or less independent code files linked together to form a whole.

First off, HelloWorld.hs – containing a very generic program skeleton. We will use our module Bindings to setup everything else we might need, and tie them to the callbacks.

Since the content rate of haskell-related posts is going up, the feed of this blog will get added to Planet Haskell. Hi, Planet!

After having failed following the googled tutorial in HOpenGL programming, I thought I’d write down the steps I actually can get to work in a tutorial-like fashion. It may be a good idea to read this in parallell to the tutorial linked, since Panitz actually brings a lot of good explanations, even though his syntax isn’t up to speed with the latest HOpenGL at all points.

Hello World

First of all, we’ll want to load the OpenGL libraries, throw up a window, and generally get to grips with what needs to be done to get a program running at all.

This code throws up a window, with a given title. Nothing more happens, though. This is the skeleton that we’ll be building on to. Save it to HelloWorld.hs and compile it by running

ghc -package GLUT HelloWorld.hs -o HelloWorld


The weekly reports have been dead for a while. Reason? The blog has been dead for a while.

Hardware woes

The old computer running this website had some problem all of a sudden about 3 weeks ago. These problems appeared as a complete lockdown of the system – no response to anything. So my brother – with me on the other side of a telephone, tried to reboot the box; but couldn’t get it back up online again. He was headed out to a LARP anyway within hours – and so couldn’t really do much more about it.

Right.

End result? I joined forces with a good friend of mine; we split hardware costs for a slick new box – an Asus barebone box with a 64bit processor and a gig of RAM. It received the harddrive and network interface from the old box, and was with that good to go – only .. processor architecture changed; and so for optimal performance, it’d be a nice idea to actually use a new system install that took advantage of the extra available bitwidth.

I just received in the mail a bunch of prints. Of my article “Computation of Poincaré-Betti series for monomial rings”, produced from my Master’s thesis for the “School and workshop on computational algebra for algebraic geometry and statistics” in Torino 2004. It is now being published in the Rendiconti di Istituto Matematico di Universita di Trieste, on pages 85-94 of Vol. XXXVII (2005).

Damn, it feels good. Reviewed and everything. If you’re curious, my manuscript can be found at http://math.su.se/~mik/torino.pdf or at the arXiv as math.AC/0502348.

Todays webbrowsing led me to John Baez finds in mathematical physics for week 226, which led me to snoop around John Baez homepage, which in turn led me to stumble across the Geometry of Computation school and conference in Marseilles right now.

This, in turn, leads to several different themes for me to discuss.

Cryptographic hashes

In the weeks finds, John Baez comes up to speed with the cryptographic community on the broken state of SHA-1 and MD-5. Now, this is a drama that has been developing with quite some speed during the last 1-1½ years. It all began heating up seriously early 2005 when Wang, Yin and Yu presented a paper detailing a serious attack against SHA-1. Since then, more and more tangible evidence for the inadvisability of MD-5 and upcoming problems with SHA-1 have arrived – such as several example objects with different contents and identical MD-5 hashes: postscript documents (Letter of Recommendation and Access right granting), X.509 certificates et.c.

Breaking news! Just in from /.

According to this article, there is a Cincinnati-based company that just had two of its employees implant glass-encapsulated RFIDtags in their biceps as a part of the access control system to their datacenter.

And we’re one step closer to the artificial linking of identity verification to body parts.

I see two aspects to discuss here. One is of the inherent security problems with the solution, and the other is about the sci-fi feel and possible problems and antagonists.

So let’s start with the second aspect. I can remember a lesson in eight grade, discussing in our social sciences class, where I suggested use of passive radio transmitters to implant small chips in people that would work as a central for identification and verification. The implanted chip would be used as ID card, as credit card et.c. et.c. and you wouldn’t have to juggle cards at all any longer. I was quite taken by the vision I had – until my baptist pastor of a teacher started quoting relevations on me, claiming that such an implant would be a perfect example of how the Mark of the Beast would manifest.

Stumbling across the blog Epsilon-Delta with a brilliant article series on mathematics as key to effective programming. This in itself merits a closer look at the blog; which in turn merits it a place in my blogroll. Go and read it you too!