# Line free sets correlate locally with dense sets of complexity k-2

## Introduction

The aim of this page is to generalize the proof that line-free subsets of $[3]^n$ correlate locally with sets of complexity 1 to an analogous statement for line-free subsets of $[k]^n.$

Until this sentence is removed, there is no guarantee that this aim will be achieved, or even that a plausible sketch will result.

## Notation and definitions

The actual result to be proved is more precise than the result given in the title of the page. To explain it we need a certain amount of terminology. Given $j\leq k$ and a sequence $x\in[k]^n,$ let $U_j(x)$ denote the set $\{i\in[n]:x_i=j\}.$ We call this the j-set of x. More generally, if $E\subset[k],$ let $U_E(x)$ denote the sequence $(U_j(x):j\in E).$ We call this the E-sequence of x. For example, if n=10, k=4, $x=3442411123$ and $E=\{2,3\}$ then the E-sequence of x is $(\{4,9\},\{1,10\}).$ It can sometimes be nicer to avoid set-theoretic brackets and instead to say things like that the 24-sequence of x is $(49,235).$

An E-set is a set $\mathcal{A}\subset[k]^n$ such that whether or not x belongs to $\mathcal{A}$ depends only on the E-sequence of x. In other words, to define an E-set one chooses a collection $\mathcal{U}_E$ of sequences of the form $(U_i:i\in E),$ where the $U_i$ are disjoint subsets of [n], and one takes the set of all x such that $(U_i(x):i\in E)\in\mathcal{U}_E.$ More generally, an $(E_1,\dots,E_r)$-set is an intersection of $E_h$-sets as h runs from 1 to r.

Of particular interest to us will be the sequence $(E_1,\dots,E_{k-1}),$ where $E_j=[k-1]\setminus j.$ What is an $(E_1,\dots,E_{k-1})$set? It is a set where membership depends on k-1 conditions, and the jth condition on a sequence x depends just on the sets $U_i(x)$ with $i\leq k-1$ and $i\ne j.$

Since it provides a useful illustrative example, let us describe the class of sets that will arise in the proof. Suppose we have a subset $\mathcal{B}$ of $[k-1]^n.$ We can use $\mathcal{B}$ to define a set $\mathcal{A}\subset[k]^n$ as follows. A sequence x belongs to $\mathcal{A}$ if and only if whenever you change all the ks of x into js, for some j<k, you end up with a sequence in $\mathcal{B}.$

To see that this is an $(E_1,\dots,E_{k-1})$-set, it is enough to show that the set of all x such that changing ks to js is an $E_j$-set. And indeed, whether or not x belongs to that set does depend only on the sets $U_i(x)$ with $i\leq k-1$ and $i\ne j,$ since once you know those you have determined the sequence obtained from x when you rewrite the ks as js.



## Some stuff copied from the DHJ(3) case that I hope to modify

Let us assume for now that the equal-slices density of $\mathcal{A}$ in $[3]^n$ is at least $\delta$, and that the equal-slices density of $\mathcal{A} \cap [2]^n$ in $[2]^n$ is at least $\theta$. As discussed in the sections below, we can reduce to this case by passing to subspaces.

The key definitions are:

$\mathcal{U} := \{z \in [3]^n : \mathrm{changing }\ z\mathrm{'s }\ 3\mathrm{'s}\ \mathrm{to }\ 2\mathrm{'s\ puts\ it\ in }\ \mathcal{A}\}$,
$\mathcal{V} := \{z \in [3]^n : \mathrm{changing }\ z\mathrm{'s }\ 3\mathrm{'s}\ \mathrm{to }\ 1\mathrm{'s\ puts\ it\ in }\ \mathcal{A}\}$.

Note that $\mathcal{U}$ is a 1-set and $\mathcal{V}$ is a 2-set. Further, since $\mathcal{A}$ contains no combinatorial line, it must be disjoint from $\mathcal{U} \cap \mathcal{V}$. We will now see that $\mathcal{U} \cap \mathcal{V}$ is large in equal-slices measure on $[3]^n$.

To see this, let $z$ be drawn from equal-slices measure on $[3]^n$ in the manner described at the end of the article on the topic. Note that this also generates $x, y \in [2]^n$. As we saw in the article, we get that both $x, y \in \mathcal{A}$ with probability at least $\eta := \theta^2 - \frac{2}{n+2}$, using the fact that $\mathcal{A} \cap [2]^n$ has equal-slices density at least $\theta$ in $[2]^n$. But when this happens, $z \in \mathcal{U} \cap \mathcal{V}$, by definition. Hence $\mathcal{U} \cap \mathcal{V}$ has equal-slices density at least $\eta$ on $[3]^n$.

We now have that $\mathcal{A}$ avoids the set $\mathcal{U} \cap \mathcal{V}$, which has equal-slices density at least $\eta$. It is thus easy to conclude that $\mathcal{A}$ must have relative density at least

$\frac{\delta}{1 - \eta} \geq \delta(1 + \eta)$

on one of the three sets $\mathcal{U}\cap \mathcal{V}^c$, $\mathcal{U}^c\cap \mathcal{V}$, $\mathcal{U}^c \cap \mathcal{V}^c$. And each of these is a 12-set with density at least $\eta$.

We can move from this relative density-increment under equal-slices to a nearly as good one under uniform using the results in the passing between measures section ("relative density version").