A general result about density increments

From Polymath1Wiki

Jump to: navigation, search

Contents

Introduction

The purpose of this page is to prove a general result about density-increment strategies. It is not logically necessary as part of the proof of DHJ(3) or DHJ(k), but it helps to explain why certain features of the proof are as they are.

Terminology

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

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 \mathcal{A} is a subset of [3]n of density δ then there is a dense 12-subset \mathcal{B} of a subspace S of dimension tending to infinity, such that the density of \mathcal{A} in \mathcal{B} is at least δ + c(δ), where c(δ) > 0. (In fact, c(δ) is proportional to δ2.)

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 c(δ) / 2 into m-dimensional subspaces, then the density of \mathcal{A} in the partitioned part is at least δ + c(δ) / 2, so by averaging \mathcal{A} has density at least δ + c(δ) / 2 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 ξ to be the function that takes the value 1 / | X | everywhere in X and 0 everywhere else. Given a set Y, we write ξ(Y) for \sum_{y\in Y}\xi(y)=|X\cap Y|/|X|. Let β be the characteristic measure of \mathcal{B}, let S_1,\dots,S_N be a collection of subspaces, and for each i let σi be the characteristic measure of Si. We are assuming that \beta(\mathcal{A})\geq\delta+c(\delta). If we can find a convex combination \sum_{i=1}^N\lambda_i\sigma_i such that \|\sum_i\lambda_i\sigma_i-\beta\|\leq c(\delta)/2, then \sum_i\lambda_i\sigma_i(\mathcal{A})\geq\delta+c(\delta)/2. It follows that there exists i such that \sigma_i(\mathcal{A})\geq\delta+c(\delta)/2, 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 \sum_{i=1}^N\lambda_i\sigma_i such that \|\sum_i\lambda_i\sigma_i-\beta\|\leq c(\delta)/2. Then the Hahn-Banach theorem provides us with a function F and non-negative reals λ + μ = 1 such that \mathbb{E}_{x\in\mathcal{B}}F(x)>1, while \|F\|_\infty\leq 2\lambda/c(\delta) and \sigma_i(F)=\mathbb{E}_{x\in S_i}F(x)\leq \mu for every i. From this it follows that λ > c(δ) / 2.

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

Haven't quite finished this.

Retrieved from "http://michaelnielsen.org/polymath1/index.php?title=A_general_result_about_density_increments"
Personal tools