## Utah v. Strieff

The Supreme Court held today in Utah v. Strieff that if you stop someone illegally, then run a search on their drivers license and find they have unpaid traffic tickets, giving cause for arrest, and you then arrest them, search them, and find drugs, the drugs are admissible evidence despite arising by means of an illegal stop.  I read through the decision, following the cites and deciding whether I believed the argument.  I don’t.  But I should have saved my time and read Sotomayor’s dissent, which makes the case very clearly and in my view persuasively.

What everybody agrees on:

• Evidence need not be excluded just because it would not have been obtained but for an illegal stop.  If the officer had stopped Strieff without reasonable cause, and in the course of their conversation, someone wandered by, pointed at Strieff, and said “that’s the guy who robbed me yesterday!” it would be OK to use the accusation as evidence even though it wouldn’t have happened had Strieff not been detained.  “But for” is necessary for exclusion, but not sufficient.
• The criterion is, rather, supposed to be “whether, granting establishment of the primary illegality, the evidence to which instant objection is made has been come at by exploitation of that illegality or instead by means sufficiently distinguishable to be purged of the primary taint.”

The majority’s theory is that the information obtained by the offer about the arrest warrant was a “means sufficiently distinguishable.”  Sotomayor disagrees, and so do I.  Running Strieff’s name through the database wasn’t a separate interaction that just happened, by chance, to take place in the spacio-temporal neighborhood of the illegal stop:  it was an attempt to execute the purpose of the illegal stop, and has to be seen as a continuation of that stop.

What’s especially annoying is the majority’s use of cites that don’t support its case.  They say the facts in Segura v. United States are “similar” to those in Strieff.  They are not.  In fact (as the majority concedes) the decision to admit the evidence in Segura was reached under a totally different theory, because in that case, unlike this one, the evidence used at trial would have been obtained whether or not the illegal search had taken place; i.e. even the weaker “but for” standard wasn’t met.  Then they say the request for the warrant in the course of the illegal stop was a “negligibly burdensome precaution for officer safety,” citing Rodriguez v. United States.  In that case, it was remarked that it was legitimate, for the cause of traffic safety, to check for outstanding traffic warrants against a driver stopped for a traffic violation.  So far so good.  But the decision in that case goes on to say that making the driver submit to a dog sniff of his car is not permissible.  “Lacking the same close connection to roadway safety as the ordinary inquiries, a dog sniff is not fairly characterized as part of the officer’s traffic mission.”

The majority’s theory is that the officer checked Strieff for outstanding warrants because public safety required it.  Sotomayor’s theory is that the officer checked Strieff for outstanding warrants because he had no cause to search Strieff, and wanted some.  Which do you find more plausible?

What’s interesting is that the case that best supports the majority’s theory is one they don’t even directly cite: Johnson v. Louisiana.  In that case, Johnson was arrested without a warrant for a robbery, brought to the courthouse, and put in a lineup, where he was identified by a witness as perpetrator of a different robbery.  The court held that Johnson’s ID in the lineup was admissible even though it resulted from an illegal arrest, because the lineup was ordered separately by the judge after Johnson had been brought in:  this “intervening action” was held to be sufficient separation between the illegal arrest and the evidence obtained.  What I can’t tell from the decision is:  was it just by chance that the victim of the other robbery happened to be present at the lineup for the original robbery?  Or was it common practice to arrest people on a hunch and then put them in a bunch of different lineups to see if anyone IDed them as the perpetrator of a crime?  If it’s the former, I can sort of understand the Court’s reasoning.  If the latter, no way.

## Wall words

When I was a kid I had an anthology of Cyril Kornbluth stories and one detail in the introduction made a big impression on me:  Kornbluth had lots of random notes among his papers, ideas, words, and phrases, and the editor of the anthology found it kind of poignant to look at these and wonder what stories they would have been.  Especially — and this phrase has stuck with me all these years — “ghosts in a Martian department store.”

Anyway:  while cleaning up the basement, I came across a pile of Post-its, which were on my wall when I was a creative writing grad student at Johns Hopkins in 1994.  Each of these, I guess, was something I meant to use for something.  I have no memory of what any of these mean.  But here they are.  Maybe you can use them.  None of them is as good as “ghosts in a Martian department store.”

• “every third person in the world”
• assapanic
• “Bald men, a lot of them — yeah, that might work!”
• Rick Ziggurat
• The First Church of Christ Plaintiff
• Community Reaction to a Horrifying Event – Arndt
• out of the fishy-smelling steam
• reckless use of a highway
• THE UNDERTAKER’S BIRTHDAY (Did the stripper shoot the corpse?)
• The grandfatherly crook gives a motivational lecture to fifth-graders
• “you slug in a ditch!”
• Solomon “Duck-Duck” Goos
• A first line:  “Here’s something you might not know.”
• “luz” — “an unidentified bone…”
• The hobo community, waiting /expecting (esperar) for rich couples to pick them up.
• The apocalypse counselor “If the sun went supernova, we wouldn’t know for eight minutes.”
• “Of course, there is some element of risk involved in building a house out of oily rags.”
• steeped in regret
• Chief Louis Anemone NYPD (red)
• “This guy’s been shot.”  “No kidding — you think he’ll make it?”
• HIDALGO – hijo de algo
• fetus/treatise
• abacinate
• “Victory without a whimper…the only sound:  excellence.”
• “The ghost of Knute Rockne is living and he is smiling.”
• “That’s a big number, but it’s a heck of a lot better than infinity.”
Tagged , ,

## Creeping and boiling

Then the cannon-ball smashed through the window-sill, the opened glass panes shattering into fragments with a crash.  The ball itself rolled on until the stone wall stopped it with a heavy thud, then it burst into pieces, and a creeping gray smoke came boiling out.

I have a lot of issues with this passage.

First of all, it seems like the cannonball smashed through the window, not the windowsill.  As for the panes — if the cannonball smashed through them, doesn’t that mean they were closed, not open?  How would they shatter if not into fragments?  I object, too, to the “with a [sound effect]” construction being used in two consecutive sentences, especially given that the chosen sound effect (“crash,” “thud”) is the most obvious choice in both cases.  The second sentence has too many different actions carried out by too many different objects (the ball, the wall, then the ball again, then the smoke.)  The smoke — is it creeping or boiling?  By my lights it can’t be both.

The lines are from Naomi Novik’s Uprooted, a fantasy novel which despite this paragraph has a lot of good things about it. and which won this year’s Nebula Award.

Two idiosyncratic reactions:

• Agnieszka’s magic is set up as being the inheritance of Baba Jaga, a kind of intuitive, sing-songy, kitcheny kind of magic, explicitly opposed to the formal, rule-governed spell-casting of Sarkan, the broody sorcery dude who kidnaps, then mentors, then eventually falls in love with her.  This works well in the story, but I’m not on board with the suggestion that formal, rule-governed manipulation is a masculine activity that needs a feminine complement in order to achieve its full power.  Math has an improvisational, intuitive aspect, to be sure; but that aspect, like the formal aspect, belongs to men and women equally.
• Weird feature of this book:  its setting is a magical version of Poland, and Agnieszka is explicitly presented as being “rooted” in the village, the hearth, the homeland; this is, in part the source of her power.  Sarkan, by contrast, is explicitly “rootless” — without a connection of his own to the land, he has to feed on the young women of the village, one after another, cutting their connection to the village and leaving them sort of ruined, suited only for big-city life.  So my mind naturally wanders to the question of “what group of people were thought of in rural Eastern Europe as rootless cosmopolitans who hide out behind walls looking at books all day and who corrupt our women and we just have to accept it because they have access to mysterious secret powers?”  Now maybe I’m overthinking this, but I do have to point out that after I noticed this I looked up Novik on Wikipedia, and her mother is Polish and her father is Jewish.  Make of it what you will.

Tagged ,

## How Not To Be Wrong update

Big month for How Not To Be Wrong, by the way!  Bill Gates picked the book as one of his five summer reads, and wrote a really nice review on his blog.  It turns out Bill Gates is basically the nerdy Oprah!  Sales spiked at his signal.  (Interesting fact:  the week after his post was the first week ever that we sold more e-books than physical ones.)  Penguin printed a bunch more copies and since then the book has been selling at a level it hasn’t hit since it first came out.  This week, more than a year after publication, the paperback enters the New York Times best seller list at #8.  That’s crazy!

In other news:  the book has now been published in Brazil, Italy, Japan, China, Taiwan, and Korea.  Editions planned for France, Spain, Hungary, Finland, Russia, Czech Republic, Ukraine, Portugal, and Turkey.

## Very Aomby

This song, by Damily, is amazing:

This is tsapiky, a currently dominant style in popular music of southern Madagascar.  There isn’t much tsapiky on Spotify, but what there is is pretty good.  (None of it equals “Very Aomby,” though.)

Tagged , , ,

## Sumsets and sumsets of subsets

Say that ten times fast!
Now that you’re done, here’s an interesting fact.  I have been turning over this argument of Croot-Lev-Pach and mine and Gijswijt’s for a couple of weeks now, trying to understand what it’s really doing that leads to control of subsets of F_q^n without arithmetic progressions.

It turns out that there’s a nice refinement of what we prove, which somehow feels like it’s using more of the full strength of the Croot-Lev-Pach lemma.  The critical input is an old result of Roy Meshulam on linear spaces of low-rank matrices.

So here’s a statement.  Write M(q,n) for the CLP/EG upper bound on subsets of F_q^n with no three-term AP.

Then Theorem:  every subset S of F_q^n contains a subset S’ of size at most M(q,n) such that S’+S = S+S.

(Exercise:   Show that this immediately implies the bound on subsets with no three-term AP.)

I find this result very funny, so much so that I didn’t believe it at first, but I think the proof is right..!  Well, see for yourself, here it is.

Two natural questions:  is the bound on S’ sharp?  And is there any analogue of this phenomenon for the integers?

Update:  Of course right after I post this I realize that maybe this can be said more simply, without the invocation of Meshulam’s result (though I really like that result!)  Namely:  it’s equivalent to say that if |S| > M(q,n), you can remove ONE element from S and get an S’ with S’+S = S+S.  Why is this so?  Well, suppose not.  Choose some s_1.  We know it can’t be removed, so there must be some s_1 + s’_1 which is not expressible as a sum in S+T any other way.  The same applies to s_2, s_3, and so on.  So you end up with a set U of “unique sums” s_i + s’_i.  Now you can apply the CLP/EG argument directly to this situation; let P be a polyomial vanishing off U, this makes the matrix P(s+t) on S have a single 1 in each row and each column, and this is just as good as diagonal from the point of view of the argument in EG, so you can conclude just as there that |S| <= M(q,n).  Does that make sense?  This is the same spirit in which the polynomial method is used by Blasiak-Church-Cohn-Grochow-Umans to control multicolored sum-free sets, and the multicolored sum-free set of size (2^(4/3))^n constructed by Alon, Shpilka, and Umans also gives a lower bound for the problem under discussion here.

I still like the one-step argument in the linked .pdf better!  But I have to concede that you can prove this fact without doing any fancy linear algebra.

Update to Update (Jun 9):  Actually, I’m not so sure this argument above actually proves the theorem in the linked note.  So maybe you do need to (get to!) use this Meshulam paper after all!  What do you guys think?

Update:  The bound is sharp, at least over F_2!  I just saw this paper of Robert Kleinberg, which constructs a multicolored sum-free set in F_2^n of size just under M(2,n)!  That is, he gives you subsets S and T, both of size just under M(2,n), such that S’+T union S+T’ can’t be all of S+T if S’ and T’ are smaller than (1/2)S and (1/2)T, if I worked this out right.

The construction, which is actually based on one from 2014 by Fu and Kleinberg, actually uses a large subset of a cyclic group Z/MZ, where M is about M(2,n), and turns this into a multicolored sum-free set in (F_2)^n of (about) the same size.  So the difference between the upper bound and the lower bound in the (F_2)^n case is now roughly the same as the difference between the (trivial) upper bound and the lower bound in the case of no-three-term-AP sets in the interval.  Naturally you start to wonder:  a) Does the Fu-Kleinberg construction really have to do with characteristic 2 or is it general?  (I haven’t read it yet.)  b) Can similar ideas be used to construct large 3-AP-free subsets of (F_q)^n?  (Surely this has already been tried?) c) Is there a way to marry Meshulam’s Fourier-analytic argument with the polynomial method to get upper bounds on order (1/n)M(q,n)?  I wouldn’t have thought this worthwhile until I saw this Kleinberg paper, which makes me think maybe it’s not impossible to imagine we’re getting closer to the actual truth.

## Bounds for cap sets

Briefly:  it seems to me that the idea of the Croot-Lev-Pach paper I posted about yesterday can indeed be used to give a new bound on the size of subsets of F_3^n with no three-term arithmetic progression! Such a set has size at most (2.756)^n. (There’s actually a closed form for the constant, I think, but I haven’t written it down yet.)

Here’s the preprint. It’s very short. I’ll post this to the arXiv in a day or two, assuming I (or you) don’t find anything wrong with it, so comment if you have comments! Note: I’ve removed the link, since the official version of this result is now the joint paper by me and Gijswijt, and the old version shouldn’t be cited.

Update:  Busy few days of administrative stuff and travel, sorry for not having updated the preprint yet, will try to finish it today.  One note, already observed below in the comments:  you get a similar bound for subsets of (F_q)^n free of solutions to (ax+by+cz=0) for any (a,b,c) with a+b+c=0; the cap set case is q=3, (a,b,c) = (1,1,1).

Update 2:  Dion Gijswijt and I will be submitting this result as a joint paper, which will amalgamate the presentations of our essentially identical arguments.  Dion carried out his work independently of mine at around the same time, and the idea should be credited to both of us.  Our joint paper is available on the arXiv.

## Croot-Lev-Pach on AP-free sets in (Z/4Z)^n

As you know I love the affine cap problem:  how big can a subset of (Z/3Z)^n be that contains no three elements summing to 0 — or, in other words, that contains no 3-term arithmetic progression?  The best upper bounds, due to Bateman and Katz, are on order 3^n / n^(1+epsilon).  And I think it’s fair to say that all progress on this problem, since Meshulam’s initial results, have come from Fourier-analytic arguments.

So I’m charmed by this paper of Ernie Croot, Vsevolod Lev, and Peter Pach which proves a much stronger result for A = (Z/4Z)^n:  a subset with no 3-term arithmetic progression has size at most c^n for c strictly less than 4.  Better still (for an algebraic geometer) the argument has no harmonic analysis at all, but proceeds via the polynomial method!

This is surprising for two reasons.  First, it’s hard to make the polynomial method work well for rings, like Z/4Z, that aren’t fields; extending our knowledge about additive combinatorics to such settings is a long-standing interest of mine.  Second, the polynomial method over finite fields usually works in the “fixed dimension large field” regime; problems like affine cap, where the base ring is fixed and the dimension are growing, have so far been mostly untouched.

As for the first issue, here’s the deal.  This looks like a problem over Z/4Z but is really a problem over F_2, because the condition for being a 3-term AP

a – 2b + c = 0

has a 2 in it.  In other words:  the two outer terms have to lie in the same coset of 2A, and the middle term is only determined up to 2A.

So CLP recast the problem as follows.  Let S be a large subset of A with no 3-term AP.   Let V be 2A, which is an n-dimensional vector space over F_2.  For each v in V, there’s a coset of V consisting of the solutions to 2a = v, and we can let S_v be the intersection of S with this coset.

We want to make this a problem about V, not about A.  So write T_v for a translate of S_v by some element of the coset, so T_v now sits in V.  Which element?  Doesn’t matter!

We can now write the “no 3-term AP” condition strictly in terms of these subsets of V.  Write (T_v – T_v)^* for the set of differences between distinct elements of T_v.  Write U for the set of v in V such that T_v is nonempty.  Then the union over all v in U of

(T_v – T_v)^* + v

is disjoint from U.

I leave it as an exercise to check the equivalence.

Now we have a combinatorial question about vector spaces over F_2; we want to show that, under the condition above, the sum of |T_v| over all v in U can’t be too large.

This is where the polynomial method comes in!  CLP show that (over any field, not just F_2), a polynomial of low degree vanishing on (T_v – T_v)^* has to vanish at 0 as well; this is Lemma 1 in their paper.  So write down a polynomial P vanishing on V – U; by dimension considerations we can choose one which doesn’t vanish on all of V.  (This uses the fact that the squarefree monomials of degree up to d are linearly independent functions on F_2^n.)  If U is big, we can choose P to have lowish degree.

Since P vanishes on V-U, P has to vanish on (T_v – T_v)^* + v for all v.  Since P has low degree, it has to vanish on v too, for all v.  But then P vanishes everywhere, contrary to our assumption.

The magic of the paper is in Lemma 1, in my view, which is where you really see the polynomial method applied in this unusual fixed-field-large-dimension regime.  Let me say a vague word about how it works.  (The actual proof is less than a page, by the way, so I’m not hiding much!)  Let P be your polynomial and d its degee.  You send your vector space into a subvariety of a much larger vector space W via degree-d Veronese embedding F_d. In fact you do this twice, writing

V x V -> W x W.

Now if P is your polynomial of degree-d, you can think of P(v_1 – v_2) as a bilinear form <,> on W x W.  Suppose S is a subset of V such that P(s_1 – s_2) vanishes for all distinct s_1, s_2 in S.   That means

<F_d(s_1), F_d(s_2)> = 0

for all distinct s_1, s_2 in S.  On the other hand,

<F_d(s_1), F_d(s_1)>

doesn’t depend on s_1; it just takes the value P(0).  So if P(0) is not equal to 0, you have |S| vectors of nonzero norm which are mutually orthogonal under this bilinear form, and so there can be at most dim W of these, and that’s the bound on |S| you need.

This is very slick and I hope the idea is more generally applicable!

## Songs: Ramrao Parsatwar, EEK, Dick Diver

A couple of songs I want to remember I like.

“Jaltarang” is an old record by Ramrao Parsatwar.  The jaltarang is a percussion instrument consisting of bowls partially filled with water.  This comes to me via radiooooo, which I heartily recommend.

Something about this instrumental reminds me of EEK’s amazing “Trinity,” — I don’t know what to say about this one except it comes from Egypt and  it sounds kind of like video game music but from a video game too fun to humanly play.

But as you know I mostly listen to square Anglophone guitar-based indie so here’s a gem in that vein, “Waste the Alphabet,” by Dick Diver, like the EEK track a 2015 release.  Vocals a little like John Vanderslice, bass that sounds like Athens, GA in 1982, sort of New Zealandy guitar (this is actually from Australia.)  Hits all my spots.

## Bourgain, Gamburd, Sarnak on Markoff triples

Such a great colloquium last week by Peter Sarnak, this year’s Hilldale Lecturer, on his paper with Bourgain and Gamburd.  My only complaint is that he promised to talk about the mapping class group and then barely did!  So I thought I’d jot down what their work has to do with mapping class groups and spaces of branched covers.

Let E be a genus 1 Riemann surface — that is, a torus — and O a point of E.  Then pi_1(E-O) is just a free group on two generators, whose commutator is (the conjugacy class of) a little loop around the puncture.  If G is a group, a G-cover of E branched only at O is thus a map from pi_1(E-O) to G, which is to say a pair (a,b) of elements of G.  Well, such a pair considered up to conjugacy, since we didn’t specify a basepoint for our pi_1.  And actually, we might as well just think about the surjective maps, which is to say the connected G-covers.

Let’s focus on the case G = SL_2(Z).  And more specifically on those maps where the puncture class is sent to a matrix of trace -2.  Here’s an example:  we can take

$a_0 = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 2 \end{array} \right]$

$b_0 = \left[ \begin{array}{cc} 2 & 1 \\ 1 & 1 \end{array} \right]$

You can check that in this case the puncture class has trace -2; that is, it is the negative of a unipotent matrix.  Actually, I gotta be honest, these matrices don’t generate SL_2(Z); they generate a finite-index subgroup H of SL_2(Z), its commutator.

Write S for the set of all conjugacy classes of pairs (a,b) of matrices which generate H and have commutator with trace -2.  It turns out that this set is the set of integral points of an affine surface called the Markoff surface:  namely, if we take x = Tr(a)/3, y = Tr(b)/3, and z = Tr(ab)/3, then the three traces obey the relation

$x^2 + y^2 + z^2 = 3xyz$

and indeed every solution to this equation corresponds to an element of S.

So the integral points on the Markoff surface are acted on by an infinite discrete group.  Which if you just look at the equation seems like kind of a ridiculous miracle.  But in the setting of H-covers is very natural.  Because there’s a natural group acting on S: namely, the mapping class group Γ of type (1,1).  This group’s whole purpose in life is to act on the fundamental group of a once-punctured torus!  (For readers unfamiliar with mapping class groups, I highly recommend Benson Farb and Dan Margalit’s wonderful textbook.)   So you start with a surjection from pi_1(E-O) to H, you compose with the action of  Γ, and you get a new homomorphism.  The action of  Γ on pi_1(E-O) is only outer, but that’s OK, because we’re only keeping track of conjugacy classes of homomorphisms from pi_1(E-O) to H.

So Γ acts on S; and now the lovely theorem is that this action is transitive.

I don’t want to make this mapping class group business sound more abstract than it is.  Γ isn’t a mystery group; it acts on H_1(E-O), a free abelian group of rank 2, which gives a map from Γ to SL_2(Z), which turns out to be an isomorphism.  What’s more, the action of Γ on pairs (a,b) is completely explicit; the standard unipotent generators of SL_2(Z) map to the moves

(a,b) -> (ab,b)

(a,b) -> (a,ab)

(Sanity check:  each of these transformations preserves the conjugacy class of the commutator of a and b.)

Sarnak, being a number theorist, is interested in strong approximation: are the integral solutions of the Markoff equation dense in the adelic solutions?   In particular, if I have a solution to the Markoff equation over F_p — which is to say, a pair (a,b) in SL_2(F_p) with the right commutator — can I lift it to a solution over Z?

Suppose I have a pair (a,b) which lifts to a pair (a,b).  We know (a,b) = g(a_0,b_0) for some g in Γ.  Thus (a,b) = g(a_0,b_0).  In other words, if strong approximation is true, Γ acts transitively on the set S_p of Markoff solutions mod p.  And this is precisely what Bourgain, Gamburd, and Sarnak conjecture.  (In fact, they conjecture more:  that the Cayley-Schreier graph of this action is an expander, which is kind of a quantitative version of an action being transitive.)  One reason to believe this:  if we replace F_p with C, we replace S with the SL_2(C) character variety of pi_1(E-O), and Goldman showed long ago that the action of mapping class groups on complex character varieties of fundamental groups was ergodic; it mixes everything around very nicely.

Again, I emphasize that this is on its face a question of pure combinatorial group theory.  You want to know if you can get from any pair of elements in SL_2(F_p) with negative-unipotent commutator to any other via the two moves above.  You can set this up on your computer and check that it holds for lots and lots of p (they did.)  But it’s not clear how to prove this transitivity for all p!

They’re not quite there yet.  But what they can prove is that the action of Γ on S_p has a very big orbit, and has no very small orbits.

Now that G is the finite group SL_2(F_p), we’re in my favorite situation, that of Hurwitz spaces.  The mapping class group Γ is best seen as the fundamental group of the moduli stack M_{1,1} of elliptic curves.  So an action of Γ on the finite set S_p is just a cover H_p of M_{1,1}.  It is nothing but the Hurwitz space parametrizing maps (f: X -> E) where E is an elliptic curve and f an SL_2(F_p)-cover branched only at the origin.  What Bourgain, Gamburd, and Sarnak conjecture is that H_p is connected.

If you like, this is a moduli space of curves with nonabelian level structure as in deJong and Pikaart.  Or, if you prefer (and if H_p is actually connected) it is a noncongruence modular curve corresponding to the stabilizer of an element of S_p in Γ = SL_2(Z).  This stabilizer is in general going to be a noncongruence subgroup, except it is a congruence subgroup in the more general sense of Thurston.

This seems like an interesting family of algebraic curves!  What, if anything, can we say about it?