Greece

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 , , , ,

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.

Tagged , , ,

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”
  • The Admonitionist
  • 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
  • fuckadelphia
  • 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.

 

Tagged , , , , , ,

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.

 

Tagged , , , ,

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!

 

 

 

Tagged , , , ,
Follow

Get every new post delivered to your Inbox.

Join 715 other followers

%d bloggers like this: