A general result about density increments

http://www.youtube.com/EgilLeofwine#1 tramadol hydrochloride,  :-PPP,

Terminology

If A and B are two subsets of a finite set X, then we say that the density of A in B is [math]\displaystyle{ |A\cap B|/|B|. }[/math]

Description of result

Let us focus on the proof of DHJ(3), though what we say is much more general. That proof has two stages, which can be described as follows.

1. Prove that if [math]\displaystyle{ \mathcal{A} }[/math] is a subset of [math]\displaystyle{ [3]^n }[/math] of density [math]\displaystyle{ \delta }[/math] then there is a dense 12-subset [math]\displaystyle{ \mathcal{B} }[/math] of a subspace S of dimension tending to infinity, such that the density of [math]\displaystyle{ \mathcal{A} }[/math] in [math]\displaystyle{ \mathcal{B} }[/math] is at least [math]\displaystyle{ \delta+c(\delta), }[/math] where [math]\displaystyle{ c(\delta)\gt 0. }[/math] (In fact, [math]\displaystyle{ c(\delta) }[/math] is proportional to [math]\displaystyle{ \delta^2. }[/math])

2. Every 12-set can be almost entirely partitioned into m-dimensional subspaces, where m tends to infinity with n. Here, m depends only on the density of the part of the 12-set that is allowed not to be partitioned.

Once we have these two stages, we are basically done, for reasons that can be appreciated even if one does not know the definition of a 12-set. The reason is that if we partition all of a 12-set apart from a subset of measure at most [math]\displaystyle{ c(\delta)/2 }[/math] into m-dimensional subspaces, then the density of [math]\displaystyle{ \mathcal{A} }[/math] in the partitioned part is at least [math]\displaystyle{ \delta+c(\delta)/2, }[/math] so by averaging [math]\displaystyle{ \mathcal{A} }[/math] has density at least [math]\displaystyle{ \delta+c(\delta)/2 }[/math] in at least one of these subspaces. That gives us a density increment on a subspace, which is exactly what we need for a density-increment strategy.

Now let us generalize 2 very slightly. Given a finite set X, we define its characteristic measure [math]\displaystyle{ \xi }[/math] to be the function that takes the value [math]\displaystyle{ 1/|X| }[/math] everywhere in X and 0 everywhere else. Given a set Y, we write [math]\displaystyle{ \xi(Y) }[/math] for [math]\displaystyle{ \sum_{y\in Y}\xi(y)=|X\cap Y|/|X|. }[/math] Let [math]\displaystyle{ \beta }[/math] be the characteristic measure of [math]\displaystyle{ \mathcal{B}, }[/math] let [math]\displaystyle{ S_1,\dots,S_N }[/math] be a collection of subspaces, and for each i let [math]\displaystyle{ \sigma_i }[/math] be the characteristic measure of [math]\displaystyle{ S_i. }[/math] We are assuming that [math]\displaystyle{ \beta(\mathcal{A})\geq\delta+c(\delta). }[/math] If we can find a convex combination [math]\displaystyle{ \sum_{i=1}^N\lambda_i\sigma_i }[/math] such that [math]\displaystyle{ \|\sum_i\lambda_i\sigma_i-\beta\|\leq c(\delta)/2, }[/math] then [math]\displaystyle{ \sum_i\lambda_i\sigma_i(\mathcal{A})\geq\delta+c(\delta)/2. }[/math] It follows that there exists i such that [math]\displaystyle{ \sigma_i(\mathcal{A})\geq\delta+c(\delta)/2, }[/math] which is what we wanted.

The main result of this page is that a converse to this generalized step 2 is true as well. Loosely, this tells us that any proof that a density increase on a 12-set implies a density increase on a subspace must also show that a 12-set can be evenly covered with subspaces, up to a small error.

The proof

Suppose that we cannot find a convex combination [math]\displaystyle{ \sum_{i=1}^N\lambda_i\sigma_i }[/math] such that [math]\displaystyle{ \|\sum_i\lambda_i\sigma_i-\beta\|\leq c(\delta)/2. }[/math] Then the Hahn-Banach theorem provides us with a function F and non-negative reals [math]\displaystyle{ \lambda+\mu=1 }[/math] such that [math]\displaystyle{ \mathbb{E}_{x\in\mathcal{B}}F(x)\gt 1, }[/math] while [math]\displaystyle{ \|F\|_\infty\leq 2\lambda/c(\delta) }[/math] and [math]\displaystyle{ \sigma_i(F)=\mathbb{E}_{x\in S_i}F(x)\leq \mu }[/math] for every i. From this it follows that [math]\displaystyle{ \lambda\gt c(\delta)/2. }[/math]

Now let [math]\displaystyle{ G(x)=\delta(1+F(x)/\|F\|_\infty). }[/math] Then G takes values in [math]\displaystyle{ [0,2\delta], }[/math] and [math]\displaystyle{ \mathbb{E}_{x\in\mathcal{B}}G(x)\gt \delta(1+c(\delta)/2\lambda). }[/math] However, for each i we have [math]\displaystyle{ \sigma_i(G)\leq\delta(1+\mu/\|F\|_\infty)\leq\delta(1+c(\delta)^2\mu/2\lambda) }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math]

Haven't quite finished this.