Obstructions to uniformity

Suppose that we have a definition of quasirandomness for subsets of some structure. As stated in the quasirandomness article, a definition of quasirandomness is not very useful unless one has some understanding of sets that are not quasirandom. Let S be a structure (such as a complete graph, [math]\displaystyle{ [3]^n, }[/math] a finite Abelian group, or [math]\displaystyle{ [n]^2 }[/math]) and let A be a subset of S of density [math]\displaystyle{ \delta }[/math]. Let f be [math]\displaystyle{ 1-\delta }[/math] on A and [math]\displaystyle{ -\delta }[/math] on the complement of A. Then the average of f is zero. Typically, one would like to show that if A, or equivalently f, is not quasirandom then there is some "structured subset" [math]\displaystyle{ S'\subset S }[/math] such that [math]\displaystyle{ \mathbb{E}_{x\in S'}f(x)\geq c }[/math] for some positive constant c that depends on [math]\displaystyle{ \delta }[/math] only. Better still, one would like a converse: that any function that has positive expectation on a substructure must fail to be quasirandom. If we can do this, then we say that we have a complete set of obstructions to uniformity. ("Uniformity" is sometimes used as a synonym for "quasirandomness".)

More generally, we can look not for structured sets but structured functions. In this case we would like to find a set G of functions such that for every non-quasirandom function f there exists g in G such that [math]\displaystyle{ \mathbb{E}_{x\in S}f(x)g(x)\geq c, }[/math] and such that if there exists such a g then f is not quasirandom.

Examples

Graphs

If f is a non-quasirandom function defined on the edges of the complete graph [math]\displaystyle{ K_n, }[/math] then there are sets X and Y of vertices of linear size such that [math]\displaystyle{ \mathbb{E}_{(x,y)\in X\times Y}f(x,y)\geq c, }[/math] where c is a positive constant that depends on the degree of non-quasirandomness of f. Conversely, if such vertex sets exist, then f is not quasirandom.

Functions defined on [math]\displaystyle{ \mathbb{Z}_N }[/math]

If f is a non-quasirandom function defined on [math]\displaystyle{ \mathbb{Z}_N, }[/math] then there exists an integer r such that [math]\displaystyle{ \mathbb{E}_{x\in\Z_N}f(x)exp(2\pi irx/N)\geq c, }[/math] where again c is a positive constant that depends on the degree of non-quasirandomness of f. Again, the converse holds as well. Thus, in this case the trigonometric functions form a complete set of obstructions to quasirandomness.

The relevance to the density Hales-Jewett theorem

It is possible to think about obstructions to uniformity even in the absence of a precisely formulated definition of quasirandomness. For example, in the case of the density Hales-Jewett theorem, we know that we want quasirandom sets to contain roughly the expected number of combinatorial lines. Therefore, we can temporarily (and unsatisfactorily) define a quasirandom set to be one that contains roughly the expected number of combinatorial lines and try to classify "extreme examples" of sets that do not contain roughly the expected number. These extreme examples will typically be highly structured sets: for instance, the set of all sequences x such that [math]\displaystyle{ x_1=1 }[/math] is easily shown to have more combinatorial lines than a random set of density 1/3, but it is also a highly structured subset of [math]\displaystyle{ [3]^n. }[/math] If these examples appear to belong to a limited number of types, we can then hypothesize that every set with the wrong number of combinatorial lines correlates with one of these extreme examples. It is these extreme examples that one calls obstructions to uniformity.

Once we have formulated a conjecture of this type, we would hope to prove it in two stages as follows.

• Every quasirandom set contains roughly as many combinatorial lines as a random set of the same density. Therefore, a set with the wrong number of combinatorial lines is not quasirandom.

• Every non-quasirandom set is noticeably correlated with an obstruction to uniformity.

Possible candidates

The obstructions to uniformity appear to be hard to describe if one uses the uniform measure on [math]\displaystyle{ [3]^n, }[/math] even if one localizes to a few slices. However, if one uses equal-slices measure, then all known obstructions are sets of the following form. (The next couple of paragraphs are lifted from the discussion of DHJ(1,3).)

Let [math]\displaystyle{ \mathcal{U},\mathcal{V} }[/math] and [math]\displaystyle{ \mathcal{W} }[/math] be collections of subsets of [math]\displaystyle{ [n]. }[/math] Define [math]\displaystyle{ \mathcal{A}(\mathcal{U},\mathcal{V},\mathcal{W}) }[/math] to be the set of all triples [math]\displaystyle{ (U,V,W), }[/math] where [math]\displaystyle{ U,V,W }[/math] are disjoint, and [math]\displaystyle{ U\in\mathcal{U},V\in\mathcal{V},W\in\mathcal{W}. }[/math] These triples are in an obvious one-to-one correspondence with elements of [math]\displaystyle{ [3]^n. }[/math]

Call [math]\displaystyle{ \mathcal{A} }[/math] a set of complexity 1 if it is of the form [math]\displaystyle{ \mathcal{A}(\mathcal{U},\mathcal{V},\mathcal{W}) }[/math]. For instance, a slice [math]\displaystyle{ \Gamma_{a,b,c} }[/math] is of complexity 1, as is a union of slices of the form [math]\displaystyle{ \bigcup\{\Gamma_{a,b,c}:(a,b,c)\in A\times B\times C, a+b+c=n\} }[/math]

It is conceivable, though certainly not proved, that every set that does not contain roughly the expected number of combinatorial lines, given its density (where everything is with respect to equal-slices measure) correlates significantly with a set of complexity 1. In the opposite direction, sets of complexity 1 do give a large source of examples of sets with the wrong number of combinatorial lines.