Category Archives: offhand

The Americans can retire at 42

On the front page of my New York Times today, this capsule summary:

The French can retire at 62. Or 52. Sometimes 42. President Emmanuel Macron calls the tangle unsustainable. A million protesters disagree.

In the actual article, we learn that the retirement age of 42 applies to one group of workers; dancers in the national ballet. I find it very annoying when an article is teased with a number presented as normal when it’s actually extremely atypical. You could write the same teaser about the United States, having New York City firefighters in mind. But you would be misleading your audience even though the claim would be, I suppose, technically correct.

Khot,Minzer,Safra on approximate sections of sheaves

Subhash Khot is giving a talk at Current Developments in Math this year and his talk has the intriguing phrase “Grassmann graph” in it so I thought I’d look up what it is and what he and his collaborators prove about it, and indeed it’s interesting! I’m just going to jot down something I learned from “Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion,” by Khot, Dor Minzer, and Muli Safra, in a way that makes it sound like something algebraic geometers might be interested in, which, indeed, I think they might be!

Suppose you have a sheaf F on a space, and the space has a covering U_1, .. U_N. The sheaf axiom says that if we have a family of sections s_i of F(U_i) such that s_i and s_j agree on U_i \cap U_j for all i,j, then there is actually a global section s in F(X) which restricts to each s_i.

What if we only have an approximate section? That is: what if we have a family of s_i such that: if I select i and j uniformly at random, the probability that s_i and s_j agree on U_i \cap U_j is bounded below by some p > 0. Call such a family a “p-section.” (You should take the view that this is really a family of problems with X changing and N growing, so that when I say p > 0 the content is that p is bounded away from some 0 uniformly in X,N.)

The question is then: Is an approximate section approximately a section?

(This is meant to recall the principle from additive number theory that an approximate subgroup is approximately a subgroup, as in e.g. Freiman-Rusza.)

That is: if s_1, .. s_N from a p-section, is there some actual section s in F(X) such that, for i chosen uniformly at random,

\mathbf{Pr}(s | U_i) = s_i > p' > 0

for some p’ depending only on p?

The case which turns out to be relevant to complexity theory is the Grassmann graph, which we can describe as follows: X is a k-dimensional vector space over F_2 and the U_i are the l-dimensional vector spaces for some integer l. But we do something slightly weird (which is what makes it the Grassmann graph, not the Grassmann simplicial complex) and declare that the only nonempty intersections are those where U_i \cap U_j has dimension l-1. The sheaf is the one whose sections on U_i are the linear functions from U_i to F_2.

Speculation 1.7 in the linked paper is that an approximate section is approximately a section. This turns out not to be true! Because there are large sets of U_i whose intersection with the rest of X is smaller than you might expect. This makes sense: if X is a space which is connected but which is “almost a disjoint union of X_1 and X_2,” i.e. X_1 \cup X_2 = X and $\latex X_1 \cap X_2$ involves very few of the U_i, then by choosing a section of F(X_1) and a section of F(X_2) independently you can get an approximate section which is unlikely to be approximated by any actual global section.

But the good news is that, in the case at hand, that ends up being the only problem. Khot-Minzer-Safra classify the “approximately disconnected” chunks of X (they are collections of l-dimensional subspaces containing a fixed subspace of small dimension and contained in a fixed subspace of small codimension) and show that any approximate section of F is approximated by a section on some such chunk; this is all that is needed to prove the “2-to-2 games conjecture” in complexity theory, which is their ultimate goal.

So I found all this quite striking! Do questions about approximate global sections being approximated by global sections appear elsewhere? (The question as phrased here is already a bit weird from an algebraic geometry point of view, since it seems to require that you have or impose a probability measure on your set of open patches, but maybe that’s natural in some cases?)

Tagged , , ,

Pete Alonso was a Mallard

Pete Alonso of the New York Mets is the NL Rookie of the Year and the all-time home run king among both rookies and Mets. I’m proud to say I saw him hit a 407-foot three-run moonshot in June 2014, when he was a 19-year-old playing for the Madison Mallards in the summer-collegiate Northwoods League. Go Mallards!

Tagged

Morally problematic, even questionable

Today’s New York Times contains the phrase

is itself a morally problematic, even questionable, act.

Are there no editors anymore? What work is “even questionable” doing? Is it possible to imagine an act that was morally problematic but not morally questionable? And even if it is, is that thin distinction really what the writer of this piece about an HBO miniseries is going for? Or did they just think “is itself a morally problematic act” didn’t have enough heft, stuff another couple of non-nutritive words in there, admire the sentence’s new bulk, move on?

Boo, I say, boo.

Tagged ,

The quarter-circle game

Start at a lattice point inside the quarter-circle x^2 + y^2 < 10^6 in the positive quadrant. You and your opponent take turns: the allowable moves are to go up, right, or both at once (i.e. add (0,1), add (1,0), or add (1,1).) First person to leave the quarter-circle wins. What does it look like if you color a starting point black for “first-player loss” and yellow for “first-player win”? It looks like this:

I like the weird zones of apparent order here. Of course you can do this for any planar domain, any finite set of moves, etc. Are games like this analyzable at all?

I guess you could go a little further and compute the nimber or Grundy value associated to each starting position. You get:

What to make of this?

Here’s some hacky code, it’s simple.


M = 1000
def Crossed(a,b):
    return (a**2 + b**2 >= M*M)

def Mex(L):
    return min([i for i in range(5) if not (i in L)])


L = np.zeros((M+2,M+2))
for a in reversed(range(M+2)):
    for b in reversed(range(M+2)):
        if Crossed(a,b):
            L[a,b] = 0
        else:
            L[a,b] = Mex([L[a+1,b],L[a,b+1],L[a+1,b+1]])

plt.imshow(L,interpolation='none',origin='lower')
plt.show()

One natural question: what proportion of positions inside the quarter-circle are first-player wins? Heuristically: if you imagine the value of positions as Bernoulli variables with parameter p, the value at my current position is 0 if and only if all three of the moves available to me have value 1. So you might expect (1-p) = p^3. This has a root at about 0.68. It does look to me like the proportion of winning positions is converging, but it seems to be converging to something closer to 0.71. Why?

By the way, the game is still interesting (but I’ll bet more directly analyzable) even if the only moves are “go up one” and “go right one”! Here’s the plot of winning and losing values in that case:

Tagged ,

We are a long way from such sentiments

All of us living at a certain time on this planet together, and together experiencing all its earthly joys and sorrows, seeing the same sky, loving and hating what are, after all, the same things, each and every one of us condemned to suffer the same sentence, the same disappearance off the face of the earth, should really nurture the greatest tenderness towards each other, a feeling of the most heart-rending closeness, and should be literally screaming with terror and pain whenever we are parted by a fate which at any moment is fully capable of transforming every one of our separations, even if only meant to last ten minutes, into an eternal one. But, as you know, for most of the time, we are a long way from such sentiments, and often take leave of even those closest to us in the most thoughtless manner imaginable.

Ivan Bunin, “Long Ago,” 1921 (Sophie Lund, trans.)
Tagged , , ,

Snappy comeback

AB has curly hair, really curly hair, and strangers comment on it all the time. My stance on this is to tell her “it’s not really polite for people to randomly comment on your appearance, but it’s not impolite enough for you to be impolite back — just say thanks and move on.” Is that the right stance?

Anyway, though, today someone at the farmer’s market said “I would die to have hair like yours” and AB said, in a non-combative, sunny way, “How would that help you if you were dead?” and I was super proud.

Tagged ,

Assembled audience

I gave a talk at Williams College last year and took a little while to visit one of my favorite museums, Mass MoCA. There’s a new installation there, by Taryn Simon, called Assembled Audience. You walk in through a curtained opening and you’re in a pitch-black space. It’s very quiet. And then, slowly, applause starts to build. Bigger and bigger. About a minute of swell until the invisible crowd out there in the dark is going absolutely fucking nuts.

And I have to be honest, whatever this may say about me: I felt an incredible warmth and safety and satisfaction, standing there, being clapped for and adored by a recording of a crowd. Reader, I stayed for a second cycle.

Tagged ,

When the coffee cup shattered on the kitchen floor

As an eternal 1990s indie-pop nerd I could not but be thrilled this week when I realized I was going to Bristol

on the National Express.

Bristol, besides having lots of great mathematicians to talk to, is much lovelier than I knew. There’s lots of terrain! It seems every time you turn a corner there’s another fine vista of pastel-painted row houses and the green English hills far away. There’s a famous bridge. I walked across it, then sat on a bench at the other side doing some math, in the hopes I’d think of something really good, because I’ve always wanted to scratch some math on a British bridge, William Rowan Hamilton-style. Didn’t happen. There was a bus strike in Bristol for civil rights because the bus companies didn’t allow black or Indian drivers; the bus lines gave in to the strikers and integrated on the same day Martin Luther King, Jr. was saying “I have a dream” in Washington, DC. There’s a chain of tea shops in Bristol called Boston Tea Party. I think it’s slightly weird to have a commercial operation named after an anti-colonial uprising against your own country, but my colleagues said no one there really thinks of it that way. The University of Bristol, by the way, is sort of the Duke of the UK, in that it was founded by a limitless bequest from the biggest tobacco family in the country, the Willses. Bristol also has this clock:

Tagged , , ,

In which I almost waste four dollars at Amazon

Instructive anecdote. I needed a somewhat expensive book and the UW library didn’t have it. So I decided to buy it. Had the Amazon order queued up and ready to go, $45 with free shipping, then had a pang of guilt about the destruction of the publishing industry and decided it was worth paying a little extra to order it directly from the publisher (Routledge.)

From the publisher it was $41, with free shipping.

I think it really did used to be true that the Amazon price was basically certain to be the best price. Not anymore. Shop around!

Tagged
%d bloggers like this: