Petridis’s explorations of Plunnecke

As Tim Gowers trumpeted in this blog entry, Giorgis Petridis has been tinkering with the additive number theory applications of Plunnecke’s Inequality (please excuse my lack of umlaut, since I suspect I’m going to be repeating that name a lot and don’t want to hunt down the HTML tags). Petridis is giving a four-part talk at CUNY this weekend, and since I’ll be missing parts one and two, I’ve been rummaging through his recent papers on the arXiv, in the hopes that I can have some idea what’s going on on Thursday.

Plunnecke’s Inequality concerns a particular type of graph, called a Plunnecke graph or occasionally a commutative graph. Plunnecke graphs are directed graphs with vertices in a sequence of tiers (V₀, V₁, V₂,…), such that each edge goes from one tier to the next tier, and any pattern of edges

“factors” into a separated pattern of edges

where the v_i‘s are distinct. The relevance of this type of graph to additive number theory is as follows: if A and B are subsets of an additive group, and one sets the V_h to be the sumset A+hB, and the edges from elements in any tier to elements in the next tier that arise from adding an element of B, one ends up with a Plunnecke graph (due to the commutativity of the elements).

Plunnecke’s Inequality involves the magnification ratio from V₀ to V_h: Look at a set X in V₀, and take the number of vertices in V_h on paths from X, divided by the number of vertices in X. The magnification ratio D_h is the ratio which is smallest over all choices for X. The big inequality states that D_h^1/h decreases as h increases. This leads to many of the most standard inequalities to control sumset size, such as the following, due to Imre Ruzsa:

If , then

This is all old news, but the point is that Plunnecke’s Inequality is proven as a pure graph theory problem, using an application of Menger’s Theorem. Petridis’s surprising discovery was that one can prove Ruzsa’s inequality without the detour into graph theory, via an induction proof. Maybe it doesn’t seem surprising that one doesn’t have to use graphs to prove a problem which is not inherently about graphs, but the source of the surprise is that for about twenty years, nobody happened upon the non-detour proof. I won’t take the time to summarize the argument, because Gowers (Petridis’s graduate advisor) already did a fine job doing so in his aforementioned blog entry. Suffice it to say that it utilizes the extra traction one achieves by assuming you have already chosen the right X in the magnification ratio description above.

I haven’t read all three of Petridis’s papers in their entirety (yet). The one I found most interesting is graph-theory-based and presents a new proof of Plunnecke’s Inequality that does not require Menger’s Theorem. I’m not sure whether the arguments arose from translating the induction argument into the graph setting, or were simply inspired by the revelation that Menger was not needed in the additive setting and thus might not be required to prove Plunnecke; either way, the paper gives easy-to-follow proofs, and it explores the sharpness of Plunnecke’s Inequality by identifying what happens when the magnification ratios constitute a geometric sequence.

The argument summarized in Gowers’ entry appears in a more general setting in this paper, which looks at product-sets in a non-abelian setting. The results for product-sets are obviously weaker than in the sumset case, but the first theorem introduced is strong enough to make up most of the improved proof of Ruzsa’s result. The third paper is a bit more daunting, but I intend to give it a look on the plane Thursday morning. Hopefully this reading will give me enough background to follow at least part of what Giorgis has to say after I arrive at CUNY this weekend.