Month: June 2013

Seven dogmas of category theory

Posted on by John

Joseph Goguen gave seven dogmas in his paper A Categorical Manifesto.

  1. To each species of mathematical structure, there corresponds a category whose objects have that structure, and whose morphisms preserve it.
  2. To any natural construction on structures of one species, yielding structures of another species, there corresponds a functor from the category of the first species to the category of the second.
  3. To each natural translation from a construction F : A -> B to a construction G: A -> B there corresponds a natural transformation F => G.
  4. A diagram D in a category C can be seen as a system of constraints, and then a limit of D represents all possible solutions of the system.
  5. To any canonical construction from one species of structure to another corresponds an adjuction between the corresponding categories.
  6. Given a species of structure, say widgets, then the result of interconnecting a system of widgets to form a super-widget corresponds to taking the colimit of the diagram of widgets in which the morphisms show how they are interconnected.
  7. Given a species of structure C, then a species of structure obtained by “decorating” or “enriching” that of C corresponds to a comma category under C (or under a functor from C).

Although category theory is all about general patterns, it can be hard to learn what the general patterns of category theory are. The list above is the best high-level description of category theory I’ve seen.

Related posts

SymPy book

Posted on by John

There’s a new book on SymPy, a Python library for symbolic math.

The book is Instant SymPy Starter by Ronan Lamy. As far as I know, this is the only book just on SymPy. It’s only about 50 pages, which is nice. It’s not a replacement for the online documentation but just a quick start guide.

The online SymPy documentation is good, but I think it would be easier to start with this book. And although I’ve been using SymPy off and on for a while, I learned a few things from the book.

How many lights can you turn on?

Posted on by John

Suppose you have a large n × n grid of lights, some turned on and some turned off. Along the side of each row is a switch that can toggle the lights in that row, turning on lights that were originally off and vice versa. There are similar switches along the top that can toggle the lights in each column. How many lights can you turn on?

The answer depends on the initial configuration. If they’re all on initially, for example, then you don’t need to do anything! But in the worst case, how well can you do?

Let aij be +1 or -1 depending on whether the light in the ith row and jth column is initially turned on or off. Let xi be +1 or -1 depending on whether the lights in the ith row are toggled, and let yj be +1 or -1 depending on whether the lights in the jth column are toggled. It is always possible to choose the values of xi and yj so that

\sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i y_j \geq \left(\sqrt{2/\pi} + o(1)\right) n^{3/2}

Here o(1) means a term that goes to zero as n increases. More on this notation here.

A light that is turned on contributes a +1 to the sum and a light that is turned off contributes a -1, so the sum tells us # lights on – # lights off. Of course # lights on + # lights off = n2, so the number of lights on is

\frac{n^2}{2} + \left(\sqrt{1/2\pi} + o(1)\right) n^{3/2}

(Note that o(1)/2 = o(1): half of an expression going to zero is still an expression going to zero.)

The proof takes about a page in The Probabilistic Method. The idea is to pick the yj randomly and then select the xi to maximize the sum. The lower bound comes from the expected value over the choices of the y‘s. Since the lower bound is the expected value, there must be some choice of y‘s that exceed or at least meet that value.

The theme of The Probabilistic Method is using probability to prove theorems that have nothing to do with probability. For example, sometimes the easiest way to prove an object with a certain property exists is to prove that the probability of selecting such an object at random is positive. As one of my professors used to say, some things are so hard to find that the best way to find them is to look randomly. Sometimes the thing you’re looking for has high probability, particularly in a limit, but your intuition is drawn to low probability exceptions.

Sum-free subset results

Posted on by John

This posts gives some results for the sum-free subset problem in the previous post.

Paul Erdős proved in 1965 that a set of n non-zero integers contains a sum-free subset of size larger than kn where k = 1/3.

The best value of k is unknown. Erdős proved k is at least 1/3. Alon and Kleitman proved that k must be less than 12/29.

Alon and Kleitman also consider the problem of sum-free subsets of an arbitrary Abelian group. They proved that set of n non-zero elements of an Abelian group must have a sum-free subset of at least 2n/7 elements. The constant 2/7 is the best value in general. But for the specific case of the integers one can do better, since 1/3 > 2/7, but the best constant for the integer case is unknown.

Source: The Probabilistic Method

Other Erdős posts

Sum-free subset challenge

Posted on by John

A set of integers is called sum-free if no element of the set is the sum of any other pair of elements in the set. For example, {1, 10, 100} is sum-free.

Let’s look at pulling out a sum-free subset of a larger set. For example, if we start with {1, 2, 3, …, 10}, then {1, 5, 10} as a sum-free subset. So is {1, 2, 4, 7}. Notice in this case 1 + 2 + 4 = 7, but that’s OK because we’re only concerned with whether an element is the sum of two other elements.

[Update: Thanks to Sjoerd Visscher for pointing out that the definition of sum-free does not require that the elements of a sum be distinct. So when I said that the set {1, 2, 4, 7} is sum-free, this was wrong because 2 + 2 = 4. The set A is sum-free if the intersection of A+A with A is empty.]

Now let A be a set of integers with n elements. How large of a sum-free subset does A contain? It could be as large as n if the set A were sum-free to begin with, so that’s an upper bound. But what is a lower bound on the size of the largest sum-free subset?

There is a theorem that gives a number k such that every set of n non-zero integers contains a sum-free subset of size at least kn. You could let k be zero, but that’s no fun. Can you find a larger value of k? I’ll tell you later what value of k the theorem has. Until then, maybe you could try to find your own value.

Suppose you want to write a program to explore this empirically. For a given set, how would you find a maximal sum-free subset? Brute force examination of all subsets would take 2n steps, so hopefully you could do better than that.

What are some sets that have relatively small maximal sum-free subsets?

Other quiz/puzzle posts