Correlation with a 1-set implies correlation with a subspace

Introduction

The aim of this article is to present a proof of a result that forms part of an attempt to model a proof of DHJ(3) on the proof by Ajtai and Szemerédi of the corners theorem. If [math]\mathcal{B}[/math] is a subset of [math][3]^n[/math] then let us call it a 1-set if there exists a collection [math]\mathcal{U}[/math] of subsets of [math][n][/math] such that [math]\mathcal{B}=\{(U,V,W):U\in\mathcal{U}\}.[/math] Note that we have also used the phrase 1-set in a different sense: if [math]x\in[3]^n[/math] then the 1-set of x is the set of all i such that [math]x_i=1.[/math] Thus, a 1-set is a collection [math]\mathcal{B}[/math] of sequences such that whether or not x belongs to [math]\mathcal{B}[/math] depends only on the 1-set of x. If you understood that last sentence, then you should have no difficulty coping with the fact that the phrase "1-set" has two meanings, one a function applied to sequences and the other a property of sets of sequences.

The result to be proved here is that if [math]\mathcal{A}[/math] is a subset of [math][3]^n[/math] of density [math]\delta[/math] and [math]\mathcal{B}[/math] is a 1-set of density [math]\beta\gt0[/math] such that [math]|\mathcal{A}\cap\mathcal{B}|\geq(\delta+\eta)|\mathcal{B}|,[/math] then there is an m-dimensional combinatorial subspace S of [math][3]^n[/math] such that [math]|\mathcal{A}\cap S|\geq(\delta+\eta/2)|S|.[/math] In loose terms, correlation with a 1-set implies correlation with a subspace. Of course, there is some dependence of m on [math]\delta,\eta,\beta[/math] and n: ultimately what we care about is that for fixed [math]\delta,\eta [/math] and [math]\beta[/math] m should tend to infinity with n.

Motivation

The reason for being interested in this problem is that it is the natural analogue of the first step of Ajtai and Szemerédi in their proof of the corners theorem. See the article about their proof, and in particular the section entitled "Where next?" for more details about why this is.

The proof

Since this article was started, the intended proof has changed somewhat. It can now be found as (an easy consequence of) Step 2 on this page.