A cute combinatorial result of Santaló

There is a nice result due to Santaló that says that if a (finite) collection of axis-parallel rectangles is such that any small subcollection is aligned, then the whole collection is aligned. This is kind of surprising at first, because the condition only says that there is a line, but this line might be different for any choice of subcollection. The precise statement is as follows:

Theorem. Let $\mathcal{R}$ be a collection of rectangles with sides parallel to the axes (possibly intersecting). If for every choice of 6 rectangles of $\mathcal{R}$ there exists a line intersecting all $6$ of them, then there exists a line intersecting all rectangles of $\mathcal{R}$ at once.

To be precise, I should clarify that by line intersection it is meant intersection with the interior of the rectangle – so a line touching only the boundary is not allowed. The number 6 doesn’t have any special esoteric meaning here, to the best of my understanding – it just makes the argument work.

Freiman’s theorem and compact subsets of the real line with additive structure

In the following, I shall use ${|A|}$ to denote both the Lebesgue measure of ${A}$, when a subset of ${\mathbb{R}}$, or the cardinality of set ${A}$. This shouldn’t cause any confusion, and help highlight the parallel with the continuous case.

For the sake of completeness, we remind the reader that the Minkowski sum of two sets ${A,B}$ is defined as

$\displaystyle A+B:=\{a+b \,:\, a\in A, b\in B\}.$

I’ve been shamefully sketchy in the previous post about Christ’s work on near extremizers, and in particular I haven’t addressed properly one of the most important ideas in his work: exploiting the hidden additive structure of the inequalities. I plan to do that in this post and a following one, in which I’ll sketch his proof of the sharpened Riesz-Sobolev inequality.

In that paper, one is interested in proving that triplets of sets ${A,B,C \subset \mathbb{R}^d}$ that nearly realize equality in Riesz-Sobolev inequality

$\displaystyle \left\langle \chi_{A} \ast \chi_{B}, \chi_{C}\right\rangle \leq \left\langle \chi_{A^\ast} \ast \chi_{B^\ast}, \chi_{C^\ast}\right\rangle$

must be close to the extremizers of the inequality, which are ellipsoids (check this previous post for details and notation). In case ${d=1}$, ellipsoids are just intervals, and one wants to prove there exist intervals ${I,J,K}$ s.t. ${A \Delta I, B\Delta J, C\Delta K}$ are very small.

Christ devised a tool that can be used to prove that a set on the line must nearly coincide with an interval. It’s the following

Proposition 1 (Christ, [ChRS2]) , (continuum Freiman’s theorem) Let ${A\subset \mathbb{R}}$ be a measurable set with finite measure ${>0}$. If

$\displaystyle |A+A|< 3|A|,$

then there exists an interval ${I}$ s.t. ${A\subset I}$ [1] and

$\displaystyle |I| \leq |A+A|-|A|.$

Thus if one can exploit the near equality to spot some additive structure, one has a chance to prove the sets must nearly coincide with intervals. It turns out that there actually is additive structure concealed in the Riesz-Sobolev inequality: consider the superlevel sets

$\displaystyle S_{A,B}(t):=\{x \in \mathbb{R} \,:\, \chi_A \ast \chi_B (x) > t\};$

then one can prove that

$\displaystyle S_{A,B} (t) - S_{A,B} (t') \subset S_{A,-A}(t+t' - |B|).$

If one can control the measure of the set on the right by ${|S_{A,B} (t)|}$ for some specific value of ${t=t'}$, then Proposition 1 can be applied, and ${S_{A,B}(t)}$ will nearly coincide with an interval. Then one has to prove this fact extends to ${A,B,C}$, but that’s what the proof in [ChRS] is about and I will address it in the following post, as said.

Anyway, the result in Prop. 1, despite being stated in a continuum setting, is purely combinatoric. It follows – by a limiting argument – from a big result in additive combinatorics: Freiman’s theorem.

The aim of this post is to show how Prop. 1 follows from Freiman’s theorem, and to prove Freiman’s theorem with additive combinatorial techniques. It isn’t necessary at all in order to appreciate the results in [ChRS], but I though it was nice anyway. I haven’t stated the theorem yet though, so here it is:

Theorem 2 (Freiman’s ${3k-3}$ theorem) Let ${A\subset \mathbb{Z}}$ be finite and such that

$\displaystyle |A+A| < 3|A|-3.$

Then there exists an arithmetic progression ${P}$ s.t. ${A\subseteq P}$, whose length is ${|P|\leq |A+A|-|A|+1}$.

The proof isn’t extremely hard but neither it’s trivial. It relies on a few lemmas, and it is fully contained in section 2. Section 1 contains instead the limiting procedure mentioned above that allows to deduce Proposition 1 from Freiman’s theorem.

Remark 1 Notice that Proposition 1 is essentially a result for the near-extremizers of Brunn-Minkowski’s inequality in ${\mathbb{R}^1}$, which states that ${|A+A|\geq |A|+|A|}$. Indeed the extremizers for B-M are convex sets, which in dimension 1 means the intervals. Thus Prop 1 is saying that if ${|A+A|}$ isn’t much larger than ${2|A|}$, then ${A}$ is close to being an extremizer, i.e. an interval. One can actually prove that for two sets ${A,B}$, if one has

$\displaystyle |A+B| \leq |A|+|B|+\min(|A|,|B|)$

then ${\mathrm{diam}(A) \leq |A+B|-|B|}$. A proof can be found in [ChRS]. It is in this sense that the result in [ChBM] for Brunn-Minkowski was used to prove the result in [ChRS] for Riesz-Sobolev, which was then used for Young’s and thus for Hausdorff-Young, as mentioned in the previous post.

Fine structure of some classical affine-invariant inequalities and near-extremizers (account of a talk by Michael Christ)

I’m currently in Bonn, as mentioned in the previous post, participating to the Trimester Program organized by the Hausdorff Institute of Mathematics – although my time is almost over here. It has been a very pleasant experience: Bonn is lovely, the studio flat they got me is incredibly nice, Germany won the World Cup (nice game btw) and the talks were interesting. 2nd week has been pretty busy since there were all the main talks and some more unexpected talks in number theory which I attended. The week before that had been more relaxed instead, but I’ve followed a couple of talks then as well. Here I want to report about Christ’s talk on his work in the last few years, because I found it very interesting and because I had the opportunity to follow a second talk, which was more specific of the Hausdorff-Young inequality and helped me clarify some details I was confused about. If you get a chance, go to his talks, they’re really good.

What follows is an account of Christ’s talks – there are probably countless out there, but here’s another one. This is by no means original work, it’s very close to the talks themselves and I’m doing it only as a way to understand better. I’ll stick to Christ’s notation too. Also, I’m afraid the bibliography won’t be very complete, but I have included his papers, you can make your way to the other ones from there.

1. Four classical inequalities and their extremizers

Prof. Christ introduced four famous apparently unrelated inequalities. These are

• the Hausdorff-Young inequality: for all functions ${f \in L^p (\mathbb{R}^d)}$, with ${1\leq p \leq 2}$,

$\displaystyle \boxed{\|\widehat{f}\|_{L^{p'}}\leq \|f\|_{L^p};} \ \ \ \ \ \ \ \ \ \ \text{(H-Y)}$

• the Young inequality for convolution: if ${1+\frac{1}{q_3}=\frac{1}{q_1}+\frac{1}{q_2}}$ then

$\displaystyle \|f \ast g\|_{L^{q_3}} \leq \|f\|_{L^{q_1}}\|g\|_{L^{q_2}};$

for convenience, he put it in trilinear form

$\displaystyle \boxed{ |\left\langle f\ast g, h \right\rangle|\leq \|f\|_{L^{p_1}}\|g\|_{L^{p_2}}\|h\|_{L^{p_3}}; } \ \ \ \ \ \ \ \ \ \ \text{(Y)}$

notice the exponents satisfy ${\frac{1}{p_1}+\frac{1}{p_2}+\frac{1}{p_3}=2}$ (indeed ${q_1=p_1}$ and same for index 2, but ${p_3 = q'_3}$);

• the Brunn-Minkowski inequality: for any two measurable sets ${A,B \subset \mathbb{R}^d}$ of finite measure it is

$\displaystyle \boxed{ |A+B|^{1/d} \geq |A|^{1/d} + |B|^{1/d}; } \ \ \ \ \ \ \ \ \ \ \text{(B-M)}$

• the Riesz-Sobolev inequality: this is a rearrangement inequality, of the form

$\displaystyle \boxed{ \left\langle \chi_A \ast \chi_B, \chi_C \right\rangle \leq\left\langle \chi_{A^\ast} \ast \chi_{B^\ast}, \chi_{C^\ast} \right\rangle,} \ \ \ \ \ \ \ \ \ \ \text{(R-S)}$

where ${A,B,C}$ are measurable sets and given set ${E}$ the notation ${E^\ast}$ stands for the symmetrized set given by ball ${B(0, c_d |E|^{1/d})}$, where ${c_d}$ is a constant s.t. ${|E|=|E^\ast|}$: it’s a ball with the same volume as ${E}$.

These inequalities share a large group of symmetries, indeed they are all invariant w.r.t. the group of affine invertible transformations (which includes dilations and translations) – an uncommon feature. Moreover, for all of them the extremizers exist and have been characterized in the past. A natural question then arises

Is it true that if ${f}$ (or ${E}$, or ${\chi_E}$ where appropriate) is close to realizing the equality, then ${f}$ must also be close (in an appropriate sense) to an extremizer of the inequality?

Another way to put it is to think of these questions as relative to the stability of the extremizers, and that’s why they are referred to as fine structure of the inequalities. If proving the inequality is the first level of understanding it, answering the above question is the second level. As an example, answering the above question for (H-Y) led to a sharpened inequality. Christ’s work was motivated by the fact that nobody seemed to have addressed the question before in the literature, despite being a very natural one to ask.

Dimension of projected sets and Fourier restriction

I had a nice discussion with Tuomas after the very nice analysis seminar he gave for the harmonic analysis working group a while ago – he talked about the behaviour of Hausdorff dimension under projection operators and later we discussed the connection with Fourier restriction theory. Turns out there are points of contact but the results one gets are partial, and there are some a priori obstacles.

What follows is an account of the discussion. I will summarize his talk first.

1. Summary of the talk

1.1. Projections in ${\mathbb{R}^2}$

The problem of interest here is to determine whether there is any drop in the Hausdorff dimension of fractal sets when you project them on a lower dimensional vector space, and if so what can be said about the set of these “bad” projections. This is a very hard problem in general, so one has to start with low dimensions first. In ${\mathbb{R}^2}$ the projections are associated to the points in ${\mathbb{S}^1}$, namely for ${e\in\mathbb{S}^1}$ one has ${\pi_e (x) = (x\cdot e)e}$, and so for a given compact set ${K}$ of Hausdorff dimension ${0\leq \dim K \leq 1}$ one asks what can be said about the set of projections for which the dimension is smaller, i.e. ${\dim \pi(K) < \dim K}$. For ${s \leq \dim K}$, define the set of directions

$\displaystyle E_s (K):= \{e \in \mathbb{S}^1 \,:\, \dim \pi_e (K) < s\}.$

We refer to it as to the set of exceptional directions (of parameter ${s}$). One preliminary result is Marstrand’s theorem:

Theorem 1 (Marstrand) For any compact ${K}$ in ${\mathbb{R}^2}$ s.t. ${s<\dim K <1}$, one has

$\displaystyle |E_s (K)| = 0.$

In other words, the dimension is conserved for a.e. direction. The proof of the theorem relies on a characterization of dimension in terms of energy:

Theorem 2 (Frostman’s lemma) For ${K}$ compact in ${\mathbb{R}^d}$, it is ${s<\dim K}$ if and only if there exists a finite positive Borel measure ${\mu}$ supported in ${K}$ such that

$\displaystyle I_s(\mu):= \int_{K}{\int_{K}{\frac{d\mu(x)\,d\mu(y)}{|x-y|^s}}}<\infty.$

Ptolemaics meetings 4 & 5 & 6 ; pt I

These last ones have been quite interesting meetings, I’m happy about how the whole thing is turning out. Sadly I’m very slow at typing and working out the ideas, so I have to include three different meetings in one. Since the notes are getting incredibly long, I’ll have to split it in at least two parts.I include the pdf version of it, in case it makes it any easier to read.

ptolemaics meeting 4 & 5 & 6 pt I

Let me get finally into the time frequency of the Walsh phase plane. I won’t include many proofs as they are already well written in Hytönen’s notes (see previous post). My main interest here is the heuristic interpretation of them (disclaimer: you might think I’m bullshitting you at a certain point, but I’m probably not). Ideally, it would be very good to be able to track back the train of thoughts that went in Fefferman’s and Thiele-Lacey’s proofs.

Sorry if the pictures are shit, I haven’t learned how to draw them properly using latex yet.

1. Brush up

Recall we have Walsh series for functions ${f \in L^2(0,1)}$ defined by

$\displaystyle W_N f(x) = \sum_{n=0}^{N}{\left\langle f,w_n\right\rangle w_n(x)},$

the (Walsh-)Carleson operator here is thus

$\displaystyle \mathcal{C}f(x) = \sup_{N\in \mathbb{N}}{|W_N f(x)|},$

and in order to prove ${W_N f(x) \rightarrow f(x)}$ a.e. for ${N\rightarrow +\infty}$ one can prove that

$\displaystyle \|\mathcal{C}f\|_{L^{2,\infty}(0,1)} \lesssim \|f\|_{L^2(0,1)}.$

There’s a general remark that should be done at this point: the last inequality is equivalent to

$\displaystyle \left|\left\langle\mathcal{C}f, \chi_E\right\rangle\right| = \left|\int_{E}{\mathcal{C}f}\,dx\right| \lesssim |E|^{1/2}\|f\|_{L^2(0,1)}$

to hold on every measurable ${E}$ (of finite measure).

Ramsey numbers

Perhaps made famous by the work of Erdős, the Ramsey numbers are one very nice example of graph theory and combinatorics.

Notation here is somewhat nasty (well, it could be worse), so say that a complete graph of size ${n}$ is denoted as ${K_n}$, a totally disconnected graph as ${D_n}$ (i.e. a graph with ${n}$ vertices and ${0}$ edges), and given a graph ${G}$ the expression ${K_n \leq G }$ means ${G}$ has a subgraph with ${n}$ vertices which is isomorphic to a complete graph (same for ${D_n}$).

Definition 1 Given ${k,l\in\mathbb{N}}$, the Ramsey number ${R(k,l)}$ is the minimum number such that a graph with at least ${R(k,l)}$ vertices either contains a subgraph isomorphic to ${K_k}$ or to ${D_l}$.

In order to generalize this notion readily, it’s better to reformulate it in terms of ${2}$-colorings:

Definition 2 Given ${k,l\in\mathbb{N}}$, the Ramsey number ${R(k,l)}$ is the minimum number such that any ${2}$-coloring of ${K_{R(k,l)}}$ has a red subgraph isomorphic to ${K_k}$ or a blue subgraph isomorphic to ${K_l}$.

In this way the definition only requires notation for complete subgraphs. Notice that the definition makes the Ramsey number naturally symmetric, ${R(k,l)=R(l,k)}$, that trivially ${R(1,k)=1}$ for every ${k}$ and ${R(2,k)=k}$. Finally, notice that the number is increasing in the arguments, i.e. ${R(k,l)\leq R(k+1,l)}$.