From around the web…

Workout notes Slept in; had time for a 3 mile “run” (28:27), 3 mile walk (38:25), followed by weights. The track was a bit of a zoo, with three weight lifters walking abreast, and people who think that the track is a good place to stand and talk (never mind the thousands of square feet available in the building). I know, no biggie, but sometimes I think that Shalini is right (check out the title of this post). But there are other times where I must have been the guilty party!

Injury: felt ok, though my left lower hamstring barked a bit during the weight session (after squats). It feels good now; not sure if it was the one naproxen or the hiking boots with the lifted heel.

Trail running: trail runners (and hikers) can relate to this Frazz cartoon.

Larger

Source (where one can buy autographed copies).

Math notes: I’ll keep mum until I submit the two papers I am almost done with. Recursivity shares some cool work that he did with a graduate student. The set up goes something like this: Let U denote all the possible sequences of 0’s and 1’s and let S be some set of finite sequences of 0’s and 1’s. Let S* denote that subset of U that one can obtain by taking all possible infinite concatenations of S. For example, if S = {0, 1}, then S* is all of U. If S = {0, 10} then S* consists of all sequences that don’t have adjacent 1’s.

If we let C(S*) denote the compliment of S* in U, the question studied is: when is C(S*) a finite set, and what sort of cardinality does it have?

[...]
Now, are there any examples where S* is co-finite? Yes. One example is S = {1, 00, 01,10, 000, 01010}. It shouldn’t be too hard to convince yourself that every string except 0 and 010 can be written as concatenation of strings in this set. So in this case S* is co-finite.

Finally, we need an analogue of the largest integer not representable. That’s not hard — it’s just the length of the longest string not in S*. In the previous example, where S = {1, 00, 01,10, 000, 01010}, the answer would be 3, since 010 is the longest string omitted from S*. Let’s call this the Frobenius number of the set of strings S.

Now it’s not too hard to show that if the longest string in S is of length n, and S* is co-finite, then the Frobenius number is bounded by a function which is exponential in n. For example, over an alphabet of two letters, you can show that the Frobenius number is < (2/3)*(4n – 1). (In case the exponent doesn’t show up well in your browser, that’s 4 to the n power, minus 1, times two-thirds.)

I figured out this generalization a while ago, and the upper bound a year or so ago. But I could not find any example where the Frobenius number was anywhere near as big as that upper bound. Indeed, for a long time, the worst-case example I knew was when you took S to be the set of all strings of length n, together with all the strings of length n+1. In this case, the Frobenius number is easily shown to be n2 – n – 1.

I gave the problem to my Ph. D. student Zhi Xu, who only started a few months ago. We tried many different possibilities, but eventually we figured out that you should try sets S that contain almost all strings of some lengths, omitting only a few. And recently he made a big breakthrough: he was able to construct examples where the Frobenius number is exponentially large in n, the length of the longest string. Here’s one of his examples: take S to be over a binary alphabet, that is, over {0,1}, and let it contain all the strings of length 3, all the strings of length 5, except that you remove the strings {00001, 01010, 10011}. Then S* is co-finite, and the length of the longest string not in S* is 25. For example, 0000101001100000001010011 can’t be gotten by concatenating the strings of S. [...]

Read the article to see a cool motivation for the problem and where it fits into other areas of mathematics.

Social: why I am, in general, opposed to blanket “zero tolerance” policies.

The laws with the best intentions often have idiotic consequences.