Orioles 1, Red Sox 0

Was this it?  The game of the year, the game we’ll remember?  Gausman v. Porcello, both starters going 8 innings.  Gausman didn’t allow a run, Porcello just one, a home run to Mark Trumbo (of course, Trumbo).  Adam Jones got all of a Porcello pitch in the 3rd that looked to clear the Green Monster with yards to spare, but a brutal inbound wind knocked it out of the sky like a snipe.  Gausman hit 96 on his 109th pitch.  Jonathan Schoop backhanded a tough chance that took a weird hop and rolled partway up his wrist, and still managed to somehow flip the ball into his hand, like David Bowie in Labyrinth, and get the runner at first.  Schoop has the sweetest little “I made the play” smile in baseball, I think.  Manny Machado tagged up from first on a very deep fly by Chris Davis; Mookie Betts’s astonishingly throw got to second base with Machado no more than 2/3 of the way there.  He almost seemed to laugh at how out he was.  Zach Britton (of course, Britton) came in for the bottom of the 9th.  Battled with David Ortiz for 8 pitches, finally getting him to ground out to Chris Davis, who raced Ortiz, slow man versus slower man, to the bag.  Slow man won.  With two outs, Britton faced Hanley Ramirez, who swung three times, each time at a pitch farther removed from his person.  Orioles 1, Red Sox 0.  Nothing but must-win series from here onwards.


Overfriendly balloon

A Mylar balloon I bought weeks ago for Dr. Mrs. Q’s birthday has been holding its helium astonishingly well, but has now lost enough that its density is almost exactly that of air.  It doesn’t hug the ceiling or the floor, but slowly traverses the room, carried by air currents too weak for me to feel, I guess.  And here’s the thing:  as I sit here working, it keeps — well — visiting me.  It’s kind of creepy, when it slowly floats into my peripheral vision and then taps me once or twice.  Hey.  Balloon here.  OK, moving on.  See you later.




Luke Pebody on sharp bounds for tri-colored sum-free sets

Quick update on this post, where I listed three variations on the problem of finding large subsets of an abelian group A with no three terms in arithmetic progression.  The quantities I called G_2(F_q^n) and G_3(F_q^n) in that post are both bounded above by M(F_q^n), the number of monomials of total degree at most (q-1)n/3 and degree at most q-1 in each variable.  There’s already been a lot of motion in the few weeks since I wrote that post!  A result of Kleinberg, Sawin, and Speyer shows that G_2(F_q^n) is bounded between c_q^n and c_q^{n-epsilon} for some constant c_q, which they explicitly describe but which is kind of hard to compute.  But it’s kind of a win-win.  Either c_q^n is less than M(F_q^n), in which case, great, improvement over the results of CLP/EG, or not, in which case, great, the bounds on tri-colored sum-free sets in CLP/EG are tight up to subexponential factors!  And now Luke Pebody has posted a preprint showing that the latter is the case.

To sum up:  the quantities G_2(F_q^n) and G_3(F_q^n) which I alluded to in the original post are now bounded above by M(F_q^n) and below by M(F_q^n)^{1-epsilon}.  Wonderful!

This only heightens the interest in the original problem of estimating G_1(F_q^n), the size of the largest subset of F_q^n containing no three-term arithmetic progession.  Is the bound M(F_q^n) essentially sharp?  Or is G_1(F_q^n) much smaller?

Tagged , , ,

Roasted balsamic brussels sprouts

Note to self:  this recipe is good.



Arithmetic progression joke

Why was 7.333… disgusted by 7.666….?

Continue reading

Tagged , ,

The Wisconsin Supreme Court gets home rule wrong and right

The Supreme Court made a decision in the Milwaukee police officer residency requirement case I wrote about, peevishly and at length, earlier this year.  Chief Justice Michael Gableman is still claiming the home rule amendment says something it doesn’t say; whether he’s confused or cynical I can’t say.

the home rule amendment gives cities and villages the ability “to determine their local affairs and government, subject only to this constitution and to such enactments of the legislature of statewide concern as with uniformity shall affect every city or every village.”  In other words, a city or village may, under its home rule authority, create a law that deals with its local affairs, but the Legislature has the power to statutorily override the city’s or village’s law if the state statute touches upon a matter of statewide concern or if the state statute uniformly affects every city or village. See Madison
Teachers, 358 Wis. 2d 1, ¶101.

“In other words,” phooey.  The amendment says a state enactment has to be of statewide concern and uniform in its effect.  Gableman turns the “and” into an “or,” giving the state much greater leeway to bend cities to its will.  The citation, by the way, is to his own opinion in the Act 10 case, where he’s wrong for the same reason.

But here’s the good news.  Rebecca Bradley, the newest justice, wrote a blistering concurrence (scroll to paragraph 52 of the opinion) which gets the amendment right.  She agrees with the majority that the state has constitutional authority to block Milwaukee’s residency requirement.  But the majority’s means of reaching that conclusion is wrong.  Bradley explains: by the home rule amendment’s plain text and by what its drafters said at the time of its composition, it is and, not or; for a state law to override a city law, it has to involve a matter of statewide concern and apply uniformly to all muncipalities.  Here’s Daniel Hoan, mayor of Milwaukee, and one of the main authors of the home rule amendment:

We submit that this wording is not ambiguous as other constitutional Home Rule amendments may be. It does not say——subject to state laws, subject to state laws of state-wide concern, or subject to laws uniformly affecting cities, but it does say——subject only to such state laws as are therein defined, and these laws must meet two tests: First——do they involve a subject of statewide concern, and second——do they with uniformity affect every city or village?

Bradley concedes that decades of Supreme Court precedent interpret the amendment wrongly.  So screw the precedent, she writes!  OK, she doesn’t actually write that.  But words to that effect.

I know I crap on Scalia-style originalism a lot, partly because I think it’s often a put-on.  But this is the real thing.




Tagged , , , ,

I got a message for you

“I got a message for you, if I could only remember.  I got a message for you, but you’re gonna have to come and get it.”  Kardyhm Kelly gave me a tape of Zopilote Machine in 1995 and I played nothing but for a month.  “Sinaloan Milk Snake Song” especially.  Nobody but the Mountain Goats ever made do-it-yourself music like this, nobody else ever made it seem so believable that the things it occurred to you to say or sing while you were playing your guitar in your bedroom at home might actually be pop songs.   The breakdown at the end of this!

“I’ve got a heavy coat, it’s filled with rocks and sand, and if I lose it I’ll be coming back one day (I got a message for you).”  I spent a lot of 1993 thinking about the chord progression in the verse of this song.  How does it sound so straight-ahead but also so weird?  Also the “la la la”s (“Sinaloan Milk Snake Song” has these too.)

“Roll me in the greenery, point me at the scenery.  Exploit me in the deanery.  I got a message for you.”

The first of these I ever heard.  Douglas Wolk used to send mixtapes to Elizabeth Wilmer at Math Olympiad training.  This was on one of them.  1987 probably. I hadn’t even started listening to WHFS yet, I had no idea who Robyn Hitchcock was.  It was on those tapes I first heard the Ramones, Marshall Crenshaw, the Mentors (OK, we were in high school, cut us some slack.)

(Update:  Douglas denies ever putting the Mentors on a mixtape, and now that I really think about it, I believe Eric Wepsic was to blame for bringing the Mentors into my life.)

Why is this line so potent?  Why is the message never explicitly presented?  It’s enough — it’s better — that the message only be alluded to, never spoken, never delivered.

Tagged , ,

“On l-torsion in class groups of number fields” (with L. Pierce, M.M. Wood)

New paper up with Lillian Pierce and Melanie Matchett Wood!

Here’s the deal.  We know a number field K of discriminant D_K has class group of size bounded above by roughly D_K^{1/2}.  On the other hand, if we fix a prime l, the l-torsion in the class group ought to be a lot smaller.  Conjectures of Cohen-Lenstra type predict that the average size of the l-torsion in the class group of D_K, as K ranges over a “reasonable family” of algebraic number fields, should be constant.  Very seldom do we actually know anything like this; we just have sporadic special cases, like the Davenport-Heilbronn theorem, which tells us that the 3-torsion in the class group of a random quadratic field is indeed constant on average.

But even though we don’t know what’s true on average, why shouldn’t we go ahead and speculate on what’s true universally?  It’s too much to ask that Cl(K)[l] literally be bounded as K varies (at least if you believe even the most modest version of Cohen-Lenstra, which predicts that any value of dim Cl(D_K)[l] appears for a positive proportion of quadratic fields K) but people do think it’s small:

Conjecture:  |Cl(K)[l]| < D_K^ε.

Even beating the trivial bound

|Cl(K)[l]| < |Cl(K)| < D_K^{1/2 + ε}

is not easy.  Lillian was the first to do it for 3-torsion in quadratic fields.  Later, Helfgott-Venkatesh and Venkatesh and I sharpened those bounds.  I hear from Frank Thorne that he, Bhargava, Shankar, Tsimerman and Zhao have a nontrivial bound on 2-torsion for the class group of number fields of any degree.

In the new paper with Pierce and Wood, we prove nontrivial bounds for the average size of the l-torsion in the class group of K, where l is any integer, and K is a random number field of degree at most 5.  These bounds match the conditional bounds Akshay and I get on GRH.  The point, briefly, is this.  To make our argument work, Akshay and I needed GRH in order to guarantee the existence of a lot of small rational primes which split in K.  (In a few cases, like 3-torsion of quadratic fields, we used a “Scholz reflection trick” to get around this necessity.)  At the time, there was no way to guarantee small split primes unconditionally, even on average.  But thanks to the developments of the last decade, we now know a lot more about how to count number fields of small degree, even if we want to do something delicate like keep track of local conditions.  So, for instance, not only can one count quartic fields of discriminant < X, we can count fields which have specified decomposition at any specified finite set of rational primes.  This turns out to be enough — as long as you are super-careful with error terms! — to  allow us to show, unconditionally, that most number fields of discriminant < D have enough small split primes to make the bound on l-torsion go.  Hopefully, the care we took here to get counts with explicit error terms for number fields subject to local conditions will be useful for other applications too.


Tagged , , , , ,


Back from family vacation in Greece.  Tiny notes/memories:

  • I have a heuristic that Americans fly the national flag much more than Europeans do, but in Greece, the Greek flag is all over the place.
  • Greeks really like, or Greeks think people in hotels and restaurants really like, soft-rock covers of hits from the 80s.  Maybe both!  We heard this mix CD everywhere.

    If you don’t feel like an hour and a half of this, at least treat yourself to James Farelli’s inexplicably fascinating acoustic take on “Owner of a Lonely Heart.”

  • The city of Akrotiri in the Aegean islands, a thousand years older than classical Greece, was buried under 200 feet of ash by the massive eruption of Santorini. They’ve only just started to dig it out. There are wall frescoes whose paint is still colorful and fresh. But these wall frescoes aren’t on the walls anymore; they fell during the earthquake preceding the eruption and lie in fragments on the floors. Our guide told us that they don’t try to reconstruct these using computers; archeologists put the pieces together by hand. I was perplexed by this: why don’t they digitize the images and try to find matches? It seemed to me like exactly the sort of thing we now know how to do. But no: it turns out this is a problem CS people are already thinking about, and it’s hard. Putting together pottery turns out to be a computationally much easier problem. Why? Because pots are surfaces of revolution and so their geometry is much more constrained!
  • The 2-star Michelin molecular gastronomy restaurant Funky Gourmet, run by a member of the El Bulli disapora, is just as great as advertised. But how can you run a molecular gastronomy restaurant in Athens and not call it Grecian Formula…?

Variations on three-term arithmetic progressions

Here are three functions.  Let N be an integer, and consider:

  •  G_1(N), the size of the largest subset S of 1..N containing no 3-term arithmetic progression;
  •  G_2(N), the largest M such that there exist subsets S,T of 1..N with |S| = |T| = M such that the equation s_i + t_i = s_j + t_k has no solutions with (j,k) not equal to (i,i).  (This is what’s called  a tri-colored sum-free set.)
  • G_3(N), the largest M such that the following is true: given subsets S,T of 1..N, there always exist subsets S’ of S and T’ of T with |S’| + |T’| = M and S'+T \cup S+T' = S+T.

You can see that G_1(N) <= G_2(N) <= G_3(N).  Why?  Because if S has no 3-term arithmetic progression, we can take S = T and s_i = t_i, and get a tri-colored sum-free set.  Now suppose you have a tri-colored sum-free set (S,T) of size M; if S’ and T’ are subsets of S and T respectively, and S'+T \cup S+T' = S+T, then for every pair (s_i,t_i), you must have either s_i in S’ or t_i in T’; thus |S’| + |T’| is at least M.

When the interval 1..N is replaced by the group F_q^n, the Croot-Lev-Pach-Ellenberg-Gijswijt argument shows that G_1(F_q^n) is bounded above by the number of monomials of degree at most (q-1)n/3; call this quantity M(F_q^n).  In fact, G_3(F_q^n) is bounded above by M(F_q^n), too (see the note linked from this post) and the argument is only a  modest extension of the proof for G_1.  For all we know, G_1(F_q^n) might be much smaller, but Kleinberg has recently shown that G_2(F_2^n) (whence also G_3(F_2^n)) is equal to M(F_2^n) up to subexponential factors, and work in progress by Kleinberg and Speyer has shown this for several more q and seems likely to show that the bound is tight in general.  On the other hand, I have no idea whether to think G_1(F_q^n) is actually equal to M(F_q^n); i.e. is the bound proven by me and Dion sharp?

The behavior of G_1(N) is, of course, very much studied; we know by Behrend (recently sharpened by Elkin) that G_1(N) is at least N/exp(c sqrt(log N)).  Roth proved that G_1(N) = o(N), and the best bounds, due to Tom Sanders, show that G_1(N) is O(N(log log N)^5 / log N).  (Update:  Oops, no!  Thomas Bloom has an upper bound even a little better than Sanders, change that 5 to a 4.)

What about G_2(N) and G_3(N)?  I’m not sure how much people have thought about these problems.  But if, for instance, you could show (for example, by explicit constructions) that G_3(N) was closer to Sanders than to Behrend/Elkin, it would close off certain strategies for pushing the bound on G_1(N) downward. (Update:  Jacob Fox tells me that you can get an upper bound for G_2(N) of order N/2^{clog* N} from his graph removal paper, applied to the multicolored case.)

Do we think that G_2(N) and G_3(N) are basically equal, as is now known to be the case for F_q^n?

Tagged , , , ,
%d bloggers like this: