Not really blogging

A. Makelov

Monthly Archives: June 2012

Illuminatus!

“[it’s] like having your brains smashed out by a slice of lemon, wrapped ’round a large gold brick.”

Douglas Adams on …?

A SLICE OF LEMON?! Why not apple. A large gold brick? Why not a large golden… apple. OK, I admit it, he was apparently talking about the Pan-Galactic Gargle Blaster. But he could have as easily been talking about (can you hear the drums?)

Hell yeah. That’s right. The Illuminatus! trilogy. This book is totally crazy, crazy, crazy, crazy, crazy in so many ways and on so many levels (and probably even more than that, actually). It contains a shamelessly huge number of references to art/history/whatnot, and the funniest uses of self-reference I’ve ever encountered. It holds a very special place in my library, and also it’s a lot of fun, that’s why I chose it as the first (and hopefully not last) book to be discussed in my blog.

This book is an easy read: right from its first line, “It was the year when they finally immanentized the Eschaton.”, it will push you forward (and maybe pull you back when you finish it? Another inside joke from Math55…) through its dynamic plot, and you’ll be flying over the words, the sometimes absurdly long and complex sentences, the sudden shifts in time and place (and mindset), the infinite loads of irony, the puns, the Goddess(es), the talking porpoises, the playful mood, the underwater… whatever, laughing all the way. And – yay! It’s another sunny and exciting day of your life. You look up at the clear blue sky (no matter if it is clear and blue), infinitely more curious and infinitely more confused than you were when you started reading it. And that is always good. ‘What the hell was that?’, you might be asking yourself. What is left is this subtle feeling of a joke, resting somewhere under the worries of your mind – a small joke? a huge joke? maybe the world is a joke? maybe it was on you? – and it makes you smile mysteriously at everything and everyone you see that day. It makes you feel – or, more accurately, makes you remember that you are – liberated. And indeed, having your brains smashed out by a slice of the Apple of Discord never felt so good.

“Is”, “is.” “is” — the idiocy of the word haunts me. If it were abolished, human thought might begin to make sense. I don’t know what anything “is”; I only know how it seems to me at this moment”
― Robert Anton Wilson

This book is a hard read: you won’t know where you ARE, who the fnord characters ARE, whether what the two paranoid authors ARE scribbling about IS happening for real or not (whatever that means), what exactly IS happening, and all this IS making you mad, IS this some kind of crazy joke, why AM I even reading this?! Why all the weird conspiracy crap?! And fnord what IS the whole point of the story?!! It doesn’t make any sense whatsoever. I shouldn’t have bought fnord that! I’d better leave it back on the shelf…

You see what might trigger the bad trip. So, simply put: just keep an open mind, and let the book come in.

“The problem with quotes on the Internet is that you can’t always be sure of their authenticity.”

Abraham Lincoln

All Hail Eris! Or not. Whatever you like.

And as coincidence is a major theme of ‘Illuminatus!’, there was a curious coincidence involved in me ordering the book. I had known about it for several years, however I had some money to spend on books, so I ordered this together with one other book that had caught my eye more recenly: Gödel, Escher, Bach: An Eternal Golden Braid. That’s a weird combination, I thought. Several months later, I found this about ‘Illuminatus!’:

In more recent years, it was complimented in the bibliography to the New Hackers Dictionary as a book that can help readers “understand the hacker mindset.” The Dictionary described it as:

An incredible berserko-surrealist rollercoaster of world-girdling conspiracies, intelligent dolphins, the fall of Atlantis, who really killed JFK, sex, drugs, rock’n’roll, and the Cosmic Giggle Factor. […] The perfect right-brain companion to Hofstadter‘s Gödel, Escher, Bach.

here, and this about ‘Gödel, Escher, Bach‘:

This book reads like an intellectual Grand Tour of hacker preoccupations. Music, mathematical logic, programming, speculations on the nature of intelligence, biology, and Zen are woven into a brilliant tapestry themed on the concept of encoded self-reference. The perfect left-brain companion to “Illuminatus”.

here. Well, I was just stupefied at how well the Cosmic Coincidence Control Center are doing their job, what can I say.

Dr John Lilly refers to “the crew that never rests” as Cosmic Coincidence Control Center and warns that they pay special attention to those who pay attention to them.

About possible criticism: Yes, I’m aware of all the conspiracy theories mentioned (and developed) in ‘Illuminatus!’ and the ‘Cosmic Trigger’ series. To put it firmly: I don’t care if any of them are true or not. When I read a book, I just read a book and that’s it. I agree that in some parts of ‘Cosmic Trigger’, Wilson might appear a little assertive of such stuff, and I always hate it when someone’s like, ‘OK, see? That’s how it is, that’s the conspiracy, they’re not giving you the truth – but I am!’, but his overall approach is agnostic in nature. And in ‘Illuminatus!’ I didn’t feel any signs of someone being assertive about anything. As I said, it left me even more confused and curious. So if you fell that the book is bad because it’s trying to convince you in some weird New World Order thing, the problem might actually be in your television set.

As to the point of the book (I’ve been successfully procrastinating bringing this scary word up), as far as there is one, well, I can’t tell you what it is. It’s simply because I don’t know. I haven’t seen it. I wasn’t able (for good or for bad) to just finish the last page and say, “Hey, I finally see what all this was about. So cool.” And as author Robert A. Wilson used to read Joyce’s Ulysses each year and find something new in it, I might do the same with ‘Illuminatus!’ (and maybe blog about it? haha!). So, nice job, Mr. Wilson! You should be glad, wherever you are. However, what I feel the point is, right now in this day and in this state of mind, recollecting about the experience I had while reading it a year or so ago, can be roughly summarized as:


Advertisements

Google Summer of Code 2012: Week 5

Hi everyone,

here’s a brief summary of what I’ve been doing for the fifth week of my GSoC.

  • Firstly, I finally had my first pull request merged; it’s all my fault I didn’t complain about it on the mailing list earlier : ) I had to fix a bunch of things on it (stuff like documentation using sphinx and some improvements in code quality, mainly docstrings), and now I’m really happy to have my first major contribution to sympy merged with the master branch. Thanks to everyone who helped in reviewing it – Stefan, Mario, Tom, Matthew, and of course my mentor David.
  • Secondly, my next pull request, mainly containing work from weeks 2 and 5. After some moderate rebasing over the fixes from my first pull request, it is available here. Apart from implementations of what I did in week 2, it addresses the issue of testing randomized algorithms ( which is still being discussed here ), and splits the generators for the named groups (symmetric, dihedral,…) in a separate file (which is probably going to contain more and more constructors for some well-known groups as time goes by). The PR looks longer than it is ( : ) read: any help in the review process will be appreciated), mainly because some 250 lines were copied to a new file in order to accommodate the named groups module. I hope that this time I did a better job at splitting the different parts of the PR into several commits.
  • Finally, I started work on algorithms for backtrack searches in groups. These include stuff like printing all group elements (sort of boring, but you have to start somewhere), searching for subgroups of elements satisfying a given property, finding normalizers and centralizers,  intersection of subgroups,… In general, backtrack searches tend to be slow since all the elements in the group have to be visited, but there are ways of skipping large numbers of them. Also, for some problems in computational group theory, backtrack searches are the best we have today. They are described in [1], 4.6., and I’m currently following the exposition offered there. After two days of debugging, I finally got the function PRINTELEMENTS described in 4.6.1 of [1] to work; it turned out that the current implementation of the Schreier-Sims algorithm sets the field _coset_repr of an object of class PermutationGroup in sympy.combinatorics.perm_groups.py in a way that was unexpected to me. This little digression might help anyone else trying to understand the perm_groups file better. So for example consider the following:

In [297]: S = SymmetricGroup(4)

In [298]: S.schreier_sims()

In [299]: S._coset_repr
Out[299]:
[[[0, 1, 2, 3], [1, 2, 3, 0], [2, 3, 0, 1], [3, 0, 1, 2]],
[[0, 1, 2, 3], [0, 2, 1, 3], [0, 3, 1, 2]],
[[0, 1, 2, 3], [0, 1, 3, 2]]]
 
 In [300]: S._base
Out[300]: [0, 1, 2]

From this and similar examples I concluded that the i-th component of _coset_repr is a transversal of the i-th basic orbit of the group S and tried to use this in PRINTELEMENTS. However, consired the following example:


In [302]: G = PermutationGroup([Permutation([[0, 1, 2, 3], [4], [5]]), Permutation([[1, 3], [0], [2], [4], [5]]), Permutation([[0], [1], [2], [3], [4, 5]])])

In [303]: G.schreier_sims()

In [304]: G._base
 Out[304]: [0, 1, 4]

In [305]: G._coset_repr
 Out[305]:
 [[[0, 1, 2, 3, 4, 5],
 [1, 2, 3, 0, 4, 5],
 [2, 3, 0, 1, 4, 5],
 [3, 0, 1, 2, 4, 5]],
 [[0, 1, 2, 3, 4, 5], [0, 3, 2, 1, 4, 5]],
 [[0, 1, 2, 3, 4, 5]],
 [[0, 1, 2, 3, 4, 5]],
 [[0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 5, 4]]]

Here, the first two components of _coset_repr are as I expected, but the 3rd and 4th are something I didn’t expect to be there (I expected to get the 5th component instead of the 3rd, and no more components). Hence at present the behaviour of _coset_repr is not too clear to me. The current solution is to use the randomized version of the Schreier-Sims algorithm to get a base and a strong generating set. Another option would be to use the generators from the attribute _stabilizers_gens, but I haven’t tried that yet. Anyway, PRINTELEMENTS works now (edit: there are many other algorithms present for printing all the elements of a group, but this one is significant for the implementation of backtrack searches), and the order in which the elements of the group are visited (lexicographically with respect to the image of the base, in an ordering of \Omega = \{0, 1,\ldots, n-1\} in which base points come first) is used in most of the following backtrack searches, so a large part of this algorithm will be reused in subsequent algorithms ( I hope : ) ). My description of the situation assumed some knowledge of the theory behind the Schreier-Sims algorithm, so if something is not quite clear feel free to ask in the comments!

That’s it for now. Next week, I’ll continue with backtrack searches, and hopefully will implement the subgroup intersection routine (it seems formidable right now)… and put some more effort into getting the second pull request merged – I’ve got a lot to catch up with in terms of getting my code in sympy : ) .

[1] Derek F. Holt, Bettina Eick, Bettina, Eamonn A. O’Brien, “Handbook of computational group theory”, Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2005. ISBN 1-58488-372-3

Google Summer of Code 2012: Week 4

Hi everyone,

Here’s a brief summary of what I’ve been doing for the 4-th week of my GSoC.

This week, like the previous one, was not intense in terms of coding. Here’s what I have up and running, basically what I was talking about last week:

  • A working implementation of the randomized Schreier-Sims algorithm. This still needs to be integrated with the deterministic version of the algorithm, using the fields  _base, _coset_repr, _coset_repr_n, stabilizers_gens so that a result from the randomized algorithm can be verified deterministically. Also, it’s been suggested that we have a function that determines the base and transversal elements for the basic orbits by a given generating set that is known to be strong. This won’t be hard to implement, and will be helpful for the Butler-Portugal algorithm for tensor canonicalization – see this pull request for more information if you are interested! For more on bases and strong generating sets, see [1], pp.101-119
  • A function \text{DirectProduct(*groups)} that constructs the direct product of several groups. For more than two groups, \text{DirectProduct}(G_1,\ldots, G_n) is several times faster than calling G_1*\ldots * G_n (benchmarked it), thus it makes sense to have such a function. This is later used in constructing an arbitrary abelian group by its cycle decomposition.
  • A function for calculating the degree of transitivity of a permutation group. The idea is very brute-force: we look at the orbit of a k+1-tuple (0, 1, \ldots, k) for k = 0, 1, \ldots, n-1 and check if it spans all possible k+1-tuples. This is really bad since the number of tuples is growing like n^{k+1}, hence the complexity is O(n^{k+1}r) where k is the degree of transitivity, r is the number of generators. It seems that some sort of randomization that checks only several randomly chosen tuples for membership in the orbit will decrease the complexity, but to make sure we still need to do all the checks if the random tuples pass, which is again O(n^{k+1}r). Some bound on the probability will be good to know here.

The main focus this week was on several discussions about future changes in the permutation groups module, and on making some more effort to get my code so far merged 🙂 :

  • In this post to the mailing list, it was suggested to implement an algorithm for intersecting subgroups of a given group so that it can be used in the tensor canonicalization algorithm (again, see here). This is done in [1] but seems fairly complicated and opens the subject of backtrack searches in permutation groups; I’ll try to figure it out and implement it this coming week.
  • In this post to the mailing list, we discussed ways of testing randomized algorithms (and there are a lot of them involved in computational group theory), and an agreement was reached that some sort of manual setting of the randomized output (via an additional argument) is a sensible approach.
  • In this post to the mailing list, we discussed some changes in interface in the permutations module. Even though not everybody agrees with what I last suggested, I’ll carry these changes out and see how things unfold (i.e., whether people are happy)
  • Finally, my work from week 1 is, I hope, ready to be merged, now that I’ve made the changes suggested in the discussion of the pull request . I (finally) got familiar with the sphinx system and building the docs for sympy, and with all the conventions for writing docstrings (and convinced myself that I’ve been writing them the wrong way, I’ll fix all the docstrings in the module in the future). By the way, I installed the sphinx system in a virtualenv at the suggestion of S. Krastanov, and found the following guide really helpful in the process. When the week1 branch gets merged, a pull request with the week2 code will follow shortly, and then with the rest of the code so far…
  • And in this discussion, there were some more changes suggested, for example David proposed isolating the named groups (Symmetric, Dihedral, …) in a separate module, which I’m going to do in one of the next pull requests.

So, that’s it for now. Next week I’ll focus on getting some more of my code merged and backtrack searches.

[1] Holt, D., Eick, B., O’Brien, E. “Handbook of computational group theory”

Google Summer of Code 2012: Week 3

Hi all,

there wasn’t much coding done on my project this week; I’ve been going over the different versions of the Schreier-Sims algorithm as described in [1]; there is currently an implementation with using Jerrum’s filter as an optimization (see this), and I’ve almost implemented the faster randomized version described in [1]. It remains to see how to integrate both so that the output of the randomized version can be verified, and how to use the deterministic implementation in order to do variations of the Schreier-Sims algorithm, for example when the order of the group is known in advance, or when a base is known. Also, it might be appropriate to switch between storing transversals explicitly (requires a lot of memory, but increases speed) and using schreier vectors insted (much less memory, slower access to transversal elements) depending on the degree of the permutation group.

Apart from that, there’s been work on:

  • Finding the degree of transitivity for a permutation group: using the function orbit as acting on tuples of points, but the algorithm is sort of brute-force and becomes large for groups of large degree or large degree of transitivity.
  • Constructing abelian groups as permutation groups, by their decomposition as a direct sum of cyclic groups of given orders (per the classification of finite abelian groups), i.e. A = \text{AbelianGroup}([3,4,5]) is the group isomorphic to C_3 \oplus C_4 \oplus C_5

My code from the first two weeks is not yet merged, so next week I’ll focus on getting my pull requests reviewed, and will probably do a combined pull request next week including the code from this week. The discussion I started on the mailing list received some attention and it is now a bit clearer what changes to the interface are going to be desirable. Also, it seems that a wider array of available groups to work with will be helpful for testing purposes (i.e., groups of large degree with a small base and other interesting types of groups).

[1] Holt, D., Eick, B., O’Brien, E. “Handbook of computational group theory”

Google Summer of Code 2012: Week 2

Hi everyone,

Here is a brief summary of what I’ve been doing for the second week of my GSoC.

The first main direction was randomization: an implementation of the product replacement algorithm using an optimization suggested by Leedham-Green, as described in [1]. After an initialization that takes ~ 50 group operations (a number suggested by [1] to be large enough for practical purposes), group elements the properties of which are satisfyingly random for most CGT algorithms can be produced at the cost of one group operation (in the context of permutation groups, by a ‘group operation’ we mean the multiplication of two permutations of size the degree of the permutation group). Thus the time complexity here is O(n).

The product replacement algorithm allowed the implementation of a simple (yet backed up by some nontrivial results in number theory and group theory) and fast Monte Carlo algorithm for testing whether a given permutation group is the symmetric or the alternating group (once we know this, it is straightforward to decide which one it is by checking the parity of all the generators). This is suggested in [1] as a first step in analyzing a large permutation group. It should be noted that the algorithm is actually one-sided Monte Carlo (as defined in [2]): a wrong answer is guaranteed to be wrong, whereas a right answer may be wrong with some predefined probability. The complexity here is O(n log(n)).

The second direction was computing minimal blocks by Atkinson’s algorithm. A function taking several points S from {0, 1, …, n-1} for a transitive permutation group G of degree n, and returning the maximal block system of G (meaning the one with the smallest block size) such that the points in S are contained in the same block, was implemented. The time complexity is just above O(|S|n) ([1]). Atkinson’s algorithm itself makes use of the union-find algorithm (of course, with path compression and union by rank) to manage an equivalence relation on the set {0, 1, …, n-1}.

As a consequence of this, primitivity testing in O(n^2) time is possible (we just check for blocks containing {0, 1}, {0, 2},…, {0, n-1}). There are three optimizations to this suggested in [1] that were implemented:

  • Compute the stabilizer Stab of 0 and look at {0, rep} for orbit representatives of the action of Stab on {0, …,  n-1}
  • Stop the merging process once an equivalence class becomes larger than n/p where p is the smallest prime dividing n (as block sizes must divide n)
  • Instead of computing the stabilizer deterministically, take a subgroup generated by several random elements from Stab, by a slight modification of product replacement for G.

Still, the algorithm runs for O(n^2) time and will perform badly if Stab is small. There are primitivity testing algorithms that run in almost linear time (one is suggested in [2]), but it is claimed in [1] that the use of Atkinson’s algorithm performs well for permutation groups with degrees in the millions (which is good for our purposes) — so the question of performance here needs some further investigation.

There were some other minor changes made:

  • The group constructors for Sym and Alt now don’t calculate the order of the group right away, but only when the order is called for ( factorial(1000000) used to take almost all the time for initializing SymmetricGroup(1000000)).
  • The function orbit() can now compute the union of the orbits for several points, or the orbit of an ordered tuple of elements of {0, 1,…, n-1}. It would be desirable to be able to do this for unordered tuples as well – but the effectiveness of this might become very low since sets are not hashable in python. Perhaps there is some way to get around this.

Several changes in design were proposed in the pull request for week1 that deserve consideration (and discussion).

[1] Derek F. Holt, Bettina Eick, Bettina, Eamonn A. O’Brien, “Handbook of computational group theory”, Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2005. ISBN 1-58488-372-3

[2] Permutation Group Algorithms, Ákos Seress, Cambridge University Press

mathbabe

Exploring and venting about quantitative issues

Rational Altruist

Adventures of a would-be do-gooder.

Gowers's Weblog

Mathematics related discussions

What's new

Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao

Stefan's Blog (archive, for news see blog.krastanov.org)

Most of the blog moved to blog.krastanov.org