Weak hypergraph regularity and applications to geometric Ramsey theory
By Neil Lyall and Ákos Magyar
Abstract
Let $\Delta =\Delta _1\times \ldots \times \Delta _d\subseteq \mathbb{R}^n$, where $\mathbb{R}^n=\mathbb{R}^{n_1}\times \cdots \times \mathbb{R}^{n_d}$ with each $\Delta _i\subseteq \mathbb{R}^{n_i}$ a non-degenerate simplex of $n_i$ points. We prove that any set $S\subseteq \mathbb{R}^n$, with $n=n_1+\cdots +n_d$ of positive upper Banach density necessarily contains an isometric copy of all sufficiently large dilates of the configuration $\Delta$. In particular any such set $S\subseteq \mathbb{R}^{2d}$ contains a $d$-dimensional cube of side length $\lambda$, for all $\lambda \geq \lambda _0(S)$. We also prove analogous results with the underlying space being the integer lattice. The proof is based on a weak hypergraph regularity lemma and an associated counting lemma developed in the context of Euclidean spaces and the integer lattice.
1. Introduction
1.1. Existing results I: Distances and simplices in subsets of $\mathbb{R}^n$
Recall that the upper Banach density of a measurable set $S\subseteq \mathbb{R}^n$ is defined by
where $|\cdot |$ denotes Lebesgue measure on $\mathbb{R}^n$ and $Q(N)$ denotes the cube $[-N/2,N/2]^n$.
A result of Furstenberg, Katznelson, and Weiss Reference 6 states that if $S\subseteq \mathbb{R}^2$ has positive upper Banach density, then its distance set $\{|x-x'|\,:\, x,x'\in S\}$ contains all sufficiently large numbers. Note that the distance set of any set of positive Lebesgue measure in $\mathbb{R}^n$ automatically contains all sufficiently small numbers (by the Lebesgue density theorem) and that it is easy to construct a set of positive upper density which does not contain a fixed distance by placing small balls centered on an appropriate square grid.
This result was later reproved using Fourier analytic techniques by Bourgain in Reference 1 where he established the following more general result for all configurations of $n$ points in $\mathbb{R}^n$ whose affine span is $n-1$ dimensional, namely for all non-degenerate simplices.
Recall that a finite point configuration $\Delta '$ is said to be an isometric copy of $\lambda \Delta$ if there exists a bijection $\phi :\Delta \to \Delta '$ such that $|\phi (v)-\phi (w)|=\lambda \,|v-w|$ for all $v,w\in \Delta$, i.e. if $\Delta '$ is obtained from $\lambda \Delta$ (the dilation of $\Delta$ by a factor $\lambda$) via a rotation and translation.
Bourgain deduced Theorem B as an immediate consequence of the following stronger quantitative result for measurable subsets of the unit cube of positive measure. In Proposition C, and throughout this article, we shall refer to a decreasing sequence $\{\lambda _j\}_{j=1}^J$ as lacunary if $\lambda _{j+1}\leq \lambda _j/2$ for all $1\leq j<J$.
In Reference 12 the authors provided a short direct proof of Theorem B without using Proposition C. It is based on the observation that uniformly distributed sets $S\subseteq \mathbb{R}^d$ contain the expected “number” of isometric copies of dilates $\lambda \Delta$ and that all sets of positive upper density become uniformly distributed at sufficiently large scales. However, for the purposes of this paper it will be important to recall Bourgain’s indirect approach.
To see that Proposition C implies Theorem B notice that if Theorem B were not to hold for some set $S\subseteq \mathbb{R}^n$ of upper Banach density $\delta ^*(S)>\delta >0$, then there must exist a lacunary sequence $\lambda _1\geq \cdots \geq \lambda _J\geq 1$, with $J$ the constant in Proposition C, such that $S$ does not contain an isometric copy of $\lambda _j \Delta$ for any $1\leq j\leq J$. Taking a sufficiently large cube $Q$ with side length $N\geq \lambda _1$ and $\,|S\cap Q|\geq \delta |Q|$ and scaling back $Q\to [0,1]^n$ contradicts Proposition C.
We further note that by taking $\lambda _j=2^{-j}$ in Proposition C we obtain the following “Falconer-type” result for subsets of $[0,1]^n$ of positive Lebesgue measure.
Bourgain further demonstrated in Reference 1 that no result along the lines of Theorem B can hold for configurations that contain any three points in arithmetic progression along a line, specifically showing that for any $n\geq 1$ there are sets of positive upper Banach density in $\mathbb{R}^n$ which do not contain an isometric copy of configurations of the form $\{0, y, 2y\}$ with $|y|=\lambda$ for all sufficiently large $\lambda$. This should be contrasted with the following remarkable result of Tamar Ziegler.
Bourgain’s example was later generalized by Graham Reference 9 to establish that the condition that $\varepsilon >0$ in Theorem E is necessary and cannot be strengthened to $\varepsilon =0$ for any given non-spherical configuration $\mathcal{F}$ in $\mathbb{R}^n$ for any $n\geq 1$, that is for any finite configuration of points that cannot be inscribed in some sphere. We note that the sets constructed by Bourgain and Graham have the property that for any $\varepsilon >0$ their $\varepsilon$-neighborhoods will contain arbitrarily large cubes and hence trivially satisfy Theorem E with $\lambda _0=0$.
It is natural to ask if any spherical configuration $\mathcal{F}$, beyond the known example of simplices, has the property that every positive upper Banach density subset of $\mathbb{R}^n$, for some sufficiently large $n$, contains an isometric copy of $\lambda \mathcal{F}$ for all sufficiently large $\lambda$, and even to conjecture that this ought to hold for all spherical configurations. The first breakthrough in this direction came in Reference 12 when the authors established this for configurations of four points forming a $2$-dimensional rectangle in $\mathbb{R}^4$ and more generally for any configuration that is the direct product of two non-degenerate simplices in $\mathbb{R}^n$ for suitably large $n$.
The purpose of this article is to present a strengthening of the results in Reference 12 and to extend them to cover configurations with a higher dimensional product structure in both the Euclidean and discrete settings.
1.2. New results I: Rectangles and products of simplices in subsets of $\mathbb{R}^n$
The first main result of this article is the following
The multi-dimensional extension of Szemerédi’s theorem on arithmetic progressions in sets of positive density due to Furstenberg and Katznelson Reference 5 implies, and is equivalent to the fact, that there are isometric copies of $\lambda \mathcal{R}$ in $S$ for arbitrarily large $\lambda$, with sides parallel to the coordinate axis. Theorem 1.1 states that there is an isometric copy of $\lambda \mathcal{R}$ in $S$ for every sufficiently large $\lambda$, but only with sides parallel to given 2-dimensional coordinate subspaces which provides an extra degree of freedom for each side vector of the rectangle $\mathcal{R}$.
A weaker version of Theorem 1.1, with $\mathbb{R}^{2d}$ replaced with $\mathbb{R}^{5d}$, was later established by Durcik and Kovač in Reference 4 using an adaptation of arguments of the second author with Cook and Pramanik in Reference 3. This approach also makes direct use of the full strength of the multi-dimensional Szemerédi theorem and as such leads to quantitatively weaker results.
Our arguments work for more general patterns where $d$-dimensional rectangles are replaced with direct products of non-degenerate simplices.
Quantitative Remark. A careful analysis of our proof reveals that the constant $c(\delta ,\Delta )$ can be taken greater than $W_d(C'_\Delta \delta ^{-3n_1\cdots n_d})^{-1}$ where $W_k(m)$ is a tower of exponentials defined by $W_1(m)=\exp (m)$ and $W_{k+1}(m)=\exp (W_k(m))$ for $k\geq 1$.
1.3. Existing results II: Distances and simplices in subsets of $\mathbb{Z}^n$
The problem of counting isometric copies of a given non-degenerate simplex in $\mathbb{Z}^n$ (with one vertex fixed) has been extensively studied via its equivalent formulation as the number of ways a quadratic form can be represented as a sum of squares of linear forms, see Reference 11 and Reference 19. This was exploited by the second author in Reference 16 and Reference 17 to establish analogous results to those described in Section 1.1 for subsets of the integer lattice $\mathbb{Z}^n$ of positive upper density.
Recall that the upper Banach density of a set $S\subseteq \mathbb{Z}^n$ is analogously defined by
where $|\cdot |$ now denotes counting measure on $\mathbb{Z}^n$ and $Q(N)$ the discrete cube $[-N/2,N/2]^n\cap \mathbb{Z}^n$.
In light of the fact that any pairs of distinct points $\{x_1,x_2\}$ in $\mathbb{Z}^n$ have the property that the square of the distance between them $|x_2-x_1|^2$ is always a positive integer we introduce the convenient notation
Note that the fact that $S\subseteq \mathbb{Z}^n$ could fall entirely into a fixed congruence class of some integer $1\leq q\leq \delta ^{-1/n}$ ensures that the $q_0$ that appears in Theorems A$^\prime$ and B$^\prime$ must be divisible by the least common multiple of all integers $1\leq q\leq \delta ^{-1/n}$. Indeed if $S=(q\mathbb{Z})^n$ with $1\leq q\leq \delta ^{-1/n}$ then $S$ has upper Banach density at least $\delta$, however the distance between any two points $x,y\in S$ is of the form $|x-y|=q\lambda$ for some $\lambda \in \sqrt {\mathbb{N}}$.
However, in both Theorems A$^\prime$ and Part (i) of Theorem B$^\prime$, one can take $q_0=1$ if the sets $S$ are assumed to be suitably uniformly distributed on congruence classes of small modulus. This leads via an easy density increment strategy to short new proofs, see Reference 14 for Theorem A$^\prime$ and Section 8 for Part (i) of Theorem B$^\prime$.
The original argument in Reference 17 deduced Theorem B$^\prime$ from the following discrete analogue of Proposition C.
To see that Proposition C$^\prime$implies Theorem B$^\prime$ notice that if Part (i) of Theorem B$^\prime$ were not to hold for some set $S\subseteq \mathbb{Z}^{2n+3}$ of upper Banach density $\delta ^*(S)>\delta >0$ with $q_0$ from Proposition C$^\prime$, then there must exist a lacunary sequence $\lambda _1\geq \cdots \geq \lambda _J\geq 1$ in $q_0\sqrt {\mathbb{N}}$, with $J$ the constant from Proposition C$^\prime$, such that $S$ does not contain an isometric copy of $\lambda _j\Delta$ for any $1\leq j\leq J$. Since we can find a sufficiently large cube $Q$ with integer side length $N$ that is divisible by $q_0$ and greater than $\lambda _1$ such that $\,|S\cap Q|\geq \delta |Q|$, this contradicts Proposition C$^\prime$. Part (ii) of Theorem B$^\prime$ follows from Proposition C$^\prime$ by taking $\lambda _j=2^{J-j}q_0$.
1.4. New results II: Rectangles and products of simplices in subsets of $\mathbb{Z}^n$
We will also establish the following discrete analogues of Theorem 1.1 and 1.2.
Our arguments again work for more general patterns where $d$-dimensional rectangles are replaced with direct products of non-degenerate simplices.
Quantitative Remark. A careful analysis of our proof reveals that the constant $q_0(\delta ,\Delta )$ (and consequently also $N(\delta ,\Delta )$) can be taken less than $W_d(C'_\Delta \delta ^{-13n_1\cdots n_d})$ where $W_k(m)$ is a tower of exponentials defined by $W_1(m)=\exp (m)$ and $W_{k+1}(m)=\exp (W_k(m))$ for $k\geq 1$.
1.5. Notations and outline
We will consider the parameters $d$,$n_1$, …, $n_d$ fixed and will not indicate the dependence on them. Thus we will write $f=O(g)$ if $|f|\leq C(n_1$, …, $n_d) g$. If the implicit constants in our estimates depend on additional parameters $\varepsilon$,$\delta$,$K$, …then we will write $f=O_{\varepsilon ,\delta ,K,\dots } (g)$. We will use the notation $f\ll g$ to indicate that $|f|\leq c\,g$ for some constant $c>0$ sufficiently small for our purposes.
Given an $\varepsilon >0$ and a (finite or infinite) sequence $L_0\geq L_1\geq \cdots >0$, we will say that the sequence is $\varepsilon$-admissible if $L_j/L_{j+1}\in \mathbb{N}$ and $L_{j+1}\ll \varepsilon ^2 L_j$ for all $j\geq 1$. Moreover, if $q\in \mathbb{N}$ is given and $L_j\in \mathbb{N}$ for all $1\leq j\leq J$, then we will call the sequence $L_0\geq L_1\geq \cdots \geq L_J$$(\varepsilon ,q)$-admissible if in addition $L_J/q\in \mathbb{N}$. Such sequences of scales will often appear in our statements both in the continuous and the discrete case.
Our proofs are based on a weak hypergraph regularity lemma and an associated counting lemma developed in the context of Euclidean spaces and the integer lattice. In Section 2 we introduce our approach in the model case of finite fields and prove an analogue of Theorem 1.1 in this setting. In Section 3 we review Theorem 1.2 for a single simplex and ultimately establish the base case of our general inductive approach to Theorem 1.2. In Section 4 we address Theorem 1.2 for the direct product of two simplices, this provides a new proof (and strengthening) of the main result of Reference 12 and serves as a gentle preparation for the more complicated general case which we present in the Section 5. The proof of Theorem 1.4 is outlined in Sections 6 and 7, while a short direct proof of Part (i) of Theorem B$^\prime$ is presented in Section 8.
2. Model case: Vector spaces over finite fields
In this section we will illustrate our general method by giving a complete proof of Theorem 1.1 in the model setting of $\mathbb{F}_q^n$ where $\mathbb{F}_q$ denotes the finite field of $q$ elements. We do this as the notation and arguments are more transparent in this setting yet many of the main ideas are still present.
We say that two vectors $u,v\in \mathbb{F}_q^n$ are orthogonal, if $x\cdot y=0$, where “$\cdot$” stands for the usual dot product. A rectangle in $\mathbb{F}_q^n$ is then a set $\mathcal{R}=\{x_1,y_1\}\times \cdots \times \{x_n,y_n\}$ with side vectors $y_i-x_i$ being pairwise orthogonal.
The finite field analogue of Theorem 1.1 is the following
Write $\mathbb{F}_q^{2d}=V_1\times \ldots \times V_d$ with $V_j\simeq \mathbb{F}_q^2$ pairwise orthogonal coordinate subspaces. For any $\underline{t}\coloneq (t_1$, …, $t_d)\in \mathbb{F}_q^*$ and $S\subseteq \mathbb{F}_q^{2d}$ we define
for each $t\in \mathbb{F}_q^*$. Note that the function $\sigma _t$ may be viewed as the discrete analogue of the normalized surface area measure on the sphere of radius $\sqrt {t}$. It is well-known, see Reference 10, that
Note that if $\mathcal{N}_{\underline{t}}(1_S)>0$, then this implies that $S$ contains a rectangle of the form $\{x_{11},x_{12}\}\times \cdots \times \{x_{d1},x_{d2}\}$ with $x_{j1},x_{j2}\in V_j$ and $|x_{j2}-x_{j1}|^2=t_j$ for $1\leq j\leq d$.
Our approach to Proposition 2.1 in fact establishes the following quantitatively stronger result.
A crucial observation in the proof of Proposition 2.2 is that the averages $\mathcal{N}_{\underline{t}}(1_S)$ can be compared to ones which can be easily estimated from below. We define, for any $S\subseteq \mathbb{F}_q^{2d}$, the (unrestricted) count
The validity of Equation 2.2 will follow immediately from the $d=k$ case of Proposition 2.3. However, before we can state this counting lemma we need to introduce some further notation from the theory of hypergraphs, notation that we shall ultimately make use of throughout the paper.
2.2. Hypergraph notation and a counting lemma
In order to streamline our notation we will make use the language of hypergraphs. For $J\coloneq \{1$, …, $d\}$ and $1\leq k\leq d$, we let $\mathcal{H}_{d,k}=\{e\subseteq J;\ |e|=k\}$ denote the full $k$-regular hypergraph on the vertex set $J$. For $K\coloneq \{jl;\ j\in J,\, l\in \{1,2\}\}$ we define the projection $\pi :K\to J$ as $\pi (jl)\coloneq j$ and use this in turn to define the hypergraph bundle
Let $V\coloneq \mathbb{F}_q^{2d}$ and $V=V_1\times \ldots \times V_d$ with $V_j\simeq \mathbb{F}_q^2$ pairwise orthogonal coordinate subspaces. For a given $\underline{x}=(x_{11}$,$x_{12}$, …, $x_{d1}$,$x_{d2})\in V^2$ with $x_{j1},\,x_{j2}\in V_j$ and a given edge $e=\{1l_1$, …, $dl_d\}$, we write
Now for any $1\leq k\leq d$ and any edge $e'\in \mathcal{H}_{d,k}$, i.e. $e'\subseteq \{1$, …, $d\}$,$|e'|=k$, we let $V_{e'}\coloneq \prod _{j\in e'} V_j$. For every $\underline{x}\in V^2$ and $e\in \mathcal{H}_{d,k}^{\underline{2}}$, we define $\underline{x}_e\coloneq \pi _e(\underline{x})$ where $\pi _e: V^2\to V_{\pi (e)}$ is the natural projection map.
Our key counting lemma, Proposition 2.3, which we will establish by induction on $1\leq k\leq d$ below, is then the statement that given a family of functions $f_e:V_{\pi (e)}\to [-1,1],\,e\in \mathcal{H}_{d,k}^{\underline{2}}$, the averages (generalizing those discussed above) which are defined by
If we apply this proposition with $d=k$ and $f_e=1_S$ for all $e\in \mathcal{H}_{d,d}^{\underline{2}}$, then Theorem 2.1 clearly follows given the lower bound Equation 2.1.
by the properties of the function $\hat{\sigma }$ given above.
To see how this implies Proposition 2.3 for $k=1$ we note that since $\mathcal{H}^{\underline{2}}_{d,1}=\{jl:\ 1\leq j\leq d,\,1\leq l\leq 2\}$ it follows that
The induction step has two main ingredients, the first is an estimate of the type which is often referred to as a generalized von-Neumann inequality, namely
The corresponding inequality for the multi-linear expression $\mathcal{M} (f_e;\ e\in \mathcal{H}_{d,k}^{\underline{2}})$, namely the fact that
is well-known and is referred to as the Gowers-Cauchy-Schwarz inequality Reference 8.
The second and main ingredient is an approximate decomposition of a graph to simpler ones, and is essentially the so-called weak (hypergraph) regularity lemma of Frieze and Kannan Reference 7. We choose to state this from a somewhat more abstract/probabilistic point of view, a perspective that will be particularly helpful when we consider our general results in the continuous and discrete settings.
We will first introduce this in the case $d=2$. A bipartite graph with (finite) vertex sets $V_1$,$V_2$ is a set $S\subseteq V_1\times V_2$ and a function $f:V_1\times V_2\to \mathbb{R}$ may be viewed as weighted bipartite graph with weights $f(x_1,x_2)$ on the edges $(x_1,x_2)$. If $\mathcal{P}_1$ and $\mathcal{P}_2$ are partitions of $V_1$ and $V_2$ respectively then $\mathcal{P}=\mathcal{P}_1\times \mathcal{P}_2$ is a partition $V_1\times V_2$ and we let $\mathbb{E}(f|\mathcal{P})$ denote the function that is constant and equal to $\mathbb{E}_{x\in A} f(x)$ on each atom $A=A_1\times A_2$ of $\mathcal{P}$. The weak regularity lemma states that for any $\varepsilon >0$ and for any weighted graph $f:V_1\times V_2\to [-1,1]$ there exist partitions $\mathcal{P}_i$ of $V_i$ with $|\mathcal{P}_i|\leq 2^{O(\varepsilon ^{-2})}$ for $i=1,2$, so that
for all $U_1\subseteq V_1$ and $U_2\subseteq V_2$. Informally this means that the graph $f$ can be approximated with precision $\varepsilon$ with the “low complexity” graph $\mathbb{E}(f,\mathcal{P})$. If we consider the $\sigma$-algebras$\mathcal{B}_i$ generated by the partitions $\mathcal{P}_i$ and the $\sigma$-algebra$\mathcal{B}=\mathcal{B}_1\vee \mathcal{B}_2$ generated by $\mathcal{P}_1\times \mathcal{P}_2$ then we have $\mathbb{E}(f|\mathcal{B})$, the so-called conditional expectation function of $f$. Moreover it is easy to see, using Cauchy-Schwarz, that estimate Equation 2.9 follows from
With this more probabilistic point of view the weak regularity lemma says that the function $f$ can be approximated with precision $\varepsilon$ by a low complexity function $\mathbb{E}(f|\mathcal{B}_1\bigvee \mathcal{B}_2)$, corresponding to $\sigma$-algebras$\mathcal{B}_i$ on $V_i$ generated by $O(\varepsilon ^{-2})$ sets. This formulation is also referred to as a Koopman von Neumann type decomposition, see Corollary 6.3 in Reference 23.
We will need a natural extension to $k$-regular hypergraphs. See Reference 8Reference 22, and also Reference 2 for extension to sparse hypergraphs. Given an edge $e'\in \mathcal{H}_{d,k}$ of $k$ elements we define its boundary $\partial e'\coloneq \{\mathfrak{f}'\in \mathcal{H}_{d,k-1};\ \mathfrak{f}'\subseteq e'\}$. For each $\mathfrak{f}'=e'\backslash \{j\}\in \partial e'$ let $\mathcal{B}_\mathfrak{f}'$ be a $\sigma$-algebra on $V_{\mathfrak{f}'}\coloneq \prod _{j\in \mathfrak{f}'} V_j$ and $\bar{\mathcal{B}}_{\mathfrak{f}'}\coloneq \{U\times V_j;\ U\in \mathcal{B}_{\mathfrak{f}'}\}$ denote its pull-back over the space $V_{e'}$. The $\sigma$-algebra$\,\mathcal{B}=\bigvee _{\mathfrak{f}'\in \partial e'} \mathcal{B}_{\mathfrak{f}'}$ is the smallest $\sigma$-algebra on $\partial e'$ containing $\bar{\mathcal{B}}_{\mathfrak{f}'}$ for all $\mathfrak{f}'\in \partial e'$. Note that the atoms of $\mathcal{B}$ are of the form $A=\bigcap _{\mathfrak{f}'\in \partial e'} A_{\mathfrak{f}'}$ where $A_{\mathfrak{f}'}$ is an atom of $\bar{\mathcal{B}}_{\mathfrak{f}'}$. We say that the complexity of a $\sigma$-algebra$\mathcal{B}_{\mathfrak{f}'}$ is at most $m$, and write $\operatorname {complex}(\mathcal{B}_{\mathfrak{f}'})\leq m$, if it is generated by $m$ sets.
The proof of Lemmas 2.1 and 2.2 are presented in Section 2.4. We close this subsection by demonstrating how these lemmas can be combined to establish Proposition 2.3.
3. The base case of an inductive strategy to establish Theorem 1.2
In this section we will ultimately establish the base case of our more general inductive argument. We however start by giving a quick review of the proof of Theorem 1.2 when $d=1$ (which contains both Theorem B and Corollary D as stated in Section 1.1), namely the case of a single simplex. This was originally addressed in Reference 1 and revisited in Reference 12 and Reference 13.
3.1. A single simplex in $\mathbb{R}^n$
Let $Q\subseteq \mathbb{R}^n$ be a fixed cube and let $l(Q)$ denotes its side length.
Let $\Delta ^0=\{v_1=0$,$v_2$, …, $v_n\}\subseteq \mathbb{R}^n$ be a fixed non-degenerate simplex and define $t_{kl}\coloneq v_k\cdot v_l$ for $2\leq k,l\leq n$ where “$\cdot$” is the dot product on $\mathbb{R}^n$. Given $\lambda >0$, a simplex $\Delta =\{x_1=0$,$x_2$, …, $x_n\}\subseteq \mathbb{R}^n$ is isometric to $\lambda \Delta ^0$ if and only if $x_k\cdot x_l=\lambda ^2 t_{kl}$ for all $2\leq k,l\leq n$. Thus the configuration space $S_{\lambda \Delta ^0}$ of isometric copies of $\lambda \Delta ^0$ is a non-singular real variety given by the above equations. Let $\sigma _{\lambda \Delta ^0}$ be natural normalized surface area measure on $S_{\lambda \Delta ^0}$, described in Reference 1, Reference 12, and Reference 13. It is clear that the variable $x_1$ can be replaced by any of the variables $x_i$ by redefining the constants $t_{kl}$.
For any family of functions $f_1$, …, $f_n:Q\to [-1,1]$ and $0<\lambda \ll l(Q)$ we define the multi-linear expression
We note that all of our functions are 1-bounded and both integrals, in fact all integrals in this paper are normalized. Recall that we are using the normalized integral notation $\fint _A f\coloneq \frac{1}{|A|}\int _A f$. Since the normalized measure $\sigma _{\lambda \Delta ^0}$ is supported on $S_{\lambda \Delta _0}$ we will not indicate the support of the variables $(x_2$, …, $x_n)$ explicitly.
Note also that if $S\subseteq Q$ is a measurable set and $\mathcal{N}^1_{\lambda \Delta ^0,Q}(1_S$, …, $1_S)>0$ then $S$ must contain an isometric copy of $\lambda \Delta ^0$. Proposition 3.1 (with $Q=[0,1]^n$) is a quantitatively stronger version of Proposition C that appeared in Section 1.1 and hence immediately establishes Theorem 1.2 for $d=1$.
Our approach to establishing Proposition 3.1 is to compare the above expressions to simpler ones for which it is easy to obtain lower bounds. Given a scale $0<\lambda \ll l(Q)$ we define the multi-linear expression
where $Q(\lambda )=[-\frac{\lambda }{2},\frac{\lambda }{2}]^n$ and $t+Q(\lambda )$ is the shift of the cube $Q(\lambda )$ by the vector $t$. Note that if $S\subseteq Q$ is a set of measure $|S|\geq \delta |Q|$ for some $\delta >0$, then for a given $\varepsilon >0$, Hölder implies
for all scales $0<\lambda \ll \varepsilon \, l(Q)$.
Recall that for any $\varepsilon >0$ we call a sequence $L_1\geq \cdots \geq L_J$$\varepsilon$-admissible if $L_j/L_{j+1}\in \mathbb{N}$ and $L_{j+1}\ll \varepsilon ^2 L_j$ for all $1\leq j<J$. Note that given any lacunary sequence $l(Q)\geq \lambda _1\geq \cdots \geq \lambda _{J'}$ with $J'\gg ( \log \varepsilon ^{-1})\,J$, one can always finds an $\varepsilon$-admissible sequence of scales $l(Q)\geq L_1\geq \cdots \geq L_{J}$ such that for each $1\leq j<J$ the interval $[L_{j+1}, L_j]$ contains at least two consecutive elements from the original lacunary sequence.
In light of this observation, and the one above regarding a lower bound for $\mathcal{M}^1_{\lambda ,Q}(1_S$, …, $1_S)$, our proof of Proposition 3.1 reduces to establishing the following “counting lemma”.
There are two main ingredients in the proof of Proposition 3.2, this will be typical to all of our arguments. The first ingredient is a result which establishes that the multi-linear forms $\mathcal{N}^1_{\lambda \Delta ^0,Q}(f_1$, …, $f_n)$ are controlled by an appropriate norm which measures the uniformity of distribution of functions $f:Q\to [-1,1]$ with respect to particular scales $L$. This is analogous to estimates in additive combinatorics Reference 8 which are often referred to as generalized von-Neumann inequalities.
The result below was proved in Reference 12 for $Q=[0,1]^n$, however a simple scaling of the variables $x_i$ transfers the result to an arbitrary cube $Q$.
The corresponding inequality for the multi-linear expression $\mathcal{M}^1_{\lambda ,Q}(f_1$, …, $f_n)$, namely the fact that
The second key ingredient, proved in Reference 13 and generalized in Lemma 3.3, is a Koopman-von Neumann type decomposition of functions where the underlying $\sigma$-algebras are generated by cubes of a fixed length. To recall it, let $Q\subseteq \mathbb{R}^n$ be a cube, $L>0$ be scale that divides $l(Q)$,$Q(L)=[-\frac{L}{2},\frac{L}{2}]^n$, and $\mathcal{G}_{L,Q}$ denote the collection of cubes $t+Q(L)$ partitioning the cube $Q$ and $\Gamma _{L,Q}$ denote the grids corresponding to the centers of the cubes. By a slightly abuse of notation we also write $\mathcal{G}_{L,Q}$ for the $\sigma$-algebra generated by the grid. Recall that the conditional expectation function $\mathbb{E}(f|\mathcal{G}_{L,Q})$ is constant and equal to $\fint _A f$ on each cube $A\in \mathcal{G}_{L,Q}$.
3.2. The base case of a general inductive strategy
In this section, as preparation to handle the case of products of simplices, we prove a parametric version of Proposition 3.2, namely Proposition 3.3, which will serve as the base case for later inductive arguments.
Let $Q=Q_1\times \cdots \times Q_d$ with $Q_i\subseteq \mathbb{R}^{n_i}$ be cubes of equal side length $l(Q)$. Let $L$ be a scale dividing $l(Q)$ and for each $\underline{t}=(t_1$, …, $t_d)\in \Gamma _{L,Q}$ let $Q_{\underline{t}}(L)=\underline{t}+Q(L)$ and $Q_{t_i}(L)=t_i+Q_i(L)$. Note that $Q_{\underline{t}}(L)=Q_{t_1}(L)\times \dots \times Q_{t_d}(L)$. Here $Q(L)=[-\frac{L}{2},\frac{L}{2}]^n$ and $Q_i(L)=[-\frac{L}{2},\frac{L}{2}]^{n_i}$ for each $1\leq i\leq d$.
Let $\Delta _i^0=\{v^i_1$, …, $v^i_{n_i}\}\subseteq \mathbb{R}^{n_i}$ be a non-degenerate simplex for each $1\leq i\leq d$.
The proof of Proposition 3.3 will follow from Lemma 3.1 and the following generalization of Lemma 3.2 in which we simultaneously consider a family of functions supported on the subcubes in a partition of an original cube $Q$.
We conclude this section with a sketch of the proof of Lemma 3.3. These arguments are standard, see for example the proof of Lemma 3.2 given in Reference 12.
4. Product of two simplices in $\mathbb{R}^n$
Although not strictly necessary, we discuss in this section the special case $d=2$ of Theorem 1.2. This already gives an improvement of the main results of Reference 12, but more importantly serves as a gentle preparation for the more complicated general case, presented in the Section 5, which involve both a plethora of different scales and the hypergraph bundle notation introduced in Section 2.2.
Let $Q=Q_1\times Q_2$ with $Q_1\subseteq \mathbb{R}^{n_1}$ and $Q_2\subseteq \mathbb{R}^{n_2}$ be cubes of equal side length $l(Q)$ and $\Delta ^0=\Delta ^0_1\times \Delta ^0_2$ with $\Delta ^0_1=\{v_{11}$, …, $v_{1n_1}\}\subseteq \mathbb{R}^{n_1}$ and $\Delta ^0_2=\{v_{11}$, …, $v_{2n_2}\}\subseteq \mathbb{R}^{n_2}$ two non-degenerate simplices.
In order to “count” configurations of the form $\Delta =\Delta _1\times \Delta _2\subseteq \mathbb{R}^{n_1+n_2}$ with $\Delta _1$ and $\Delta _2$ isometric copies of $\lambda \Delta ^0_1$ and $\lambda \Delta ^0_2$ respectively for some $0<\lambda \ll l(Q)$ in a set $S\subseteq Q$ we introduce the multi-linear expression
for any family of functions $f_{kl}:Q_1\times Q_2\to [-1,1]$ with $1\leq k\leq n_1$ and $1\leq l\leq n_2$.
Indeed, if $f_{kl}=1_S$ for all $1\leq k\leq n_1$ and $1\leq l\leq n_2$ then the above expression is 0 unless there exists a configuration $\Delta \subseteq S$ of the form $\Delta _1\times \Delta _2$ with $\Delta _1$ and $\Delta _2$ isometric copies of $\lambda \Delta ^0_1$ and $\lambda \Delta ^0_2$ respectively.
The short argument presented in Section 1.1 demonstrating how both Theorem B and Corollary D follow from Proposition B, and hence from Proposition 3.1, applies equally well to each of our main theorems. This reduces our main theorems to analogous quantitative results involving an arbitrary lacunary sequence of scales. In the case $d=2$ of Theorem 1.2 this stronger quantitative result takes the following form:
Our approach to establishing Proposition 4.1 is again to compare the above expressions to simpler ones for which it is easy to obtain lower bounds. For any $0<\lambda \ll l(Q)$ and family of functions $f_{kl}:Q_1\times Q_2\to [-1,1]$ with $1\leq k\leq n_1$ and $1\leq l\leq n_2$ we consider
where $\underline{t}=(t_1,t_2)\in Q_1\times Q_2$,$\underline{x}_i=(x_{i1}$, …, $x_{in_i})$ and $Q_i(\lambda )=[-\frac{\lambda }{2},\frac{\lambda }{2}]^{n_i}$ for $i=1,2$.
Note that if $S\subseteq Q$ is a set of measure $|S|\geq \delta |Q|$ for some $\delta >0$, then careful applications of Hölder’s inequality give
for all scales $0<\lambda \ll \varepsilon \, l(Q)$.
In light of the observation above, and the discussion preceding Proposition 3.2, we see that Proposition 4.1, and hence Theorem 1.2 when $d=2$, will follow as a consequence of the following
There are again two main ingredients in the proof of Proposition 4.2. The first establishes that the our multi-linear forms $\mathcal{N}^2_{\lambda \Delta ^0,Q}(\{f_{kl}\})$ are controlled by an appropriate box-type norm attached to a scale $L$.
Let $Q=Q_1\times Q_2$ be a cube. For any scale $0<L\ll l(Q)$ and function $f:Q\to \mathbb{R}$ we define its local box norm at scale $L$ to be
for any cube $\widetilde{Q}\subseteq Q$ of the form $\widetilde{Q}=\widetilde{Q}_1\times \widetilde{Q}_2$ with $\widetilde{Q}_j\subseteq Q_j$ for $j=1,2$.
The result above was essentially proved in Reference 12 for the multi-linear forms $\mathcal{N}^2_{\lambda \Delta ^0,Q}$ when $Q=[0,1]^{n_1+n_2}$, however a simple scaling argument transfers the result to an arbitrary cube $Q$. For completeness we include its short proof in Section 4.2.
The second and main ingredient is an analogue of a weak form of Szemerédi’s regularity lemma due to Frieze and Kannan Reference 7. The more probabilistic formulation, we will use below, can be found for example in Reference 21, Reference 22, and Reference 23, and is also sometimes referred to as a Koopman-von Neumann type decomposition.
For any cube $Q\subseteq \mathbb{R}^n$ and scale $L>0$ that divides $l(Q)$ we will let $Q(L)=[-\frac{L}{2},\frac{L}{2}]^{n}$ and $\mathcal{G}_{L,Q}$ denote the collection of cubes $Q_{\underline{t}}(L)=\underline{t}+Q(L)$ partitioning the cube $Q$ and let $\Gamma _{L,Q}$ denote grid corresponding to the centers of these cubes. We will say that a finite $\sigma$-algebra$\mathcal{B}$ on $Q$ is of scale$L$ if it contains $\mathcal{G}_{L,Q}$ and for simplicity of notation will write $\mathcal{B}_{\underline{t}}$ for $\mathcal{B}|_{Q_{\underline{t}}(L)}$.
Recall that if we have two $\sigma$-algebras$\mathcal{B}_1$ on a cube $Q_1$ and $\mathcal{B}_2$ on $Q_2$ then by $\mathcal{B}_1\vee \mathcal{B}_2$ we mean the $\sigma$-algebra on $Q=Q_1\times Q_2$ generated by the sets $B_1\times B_2$ with $B_1\in \mathcal{B}_1$ and $B_2\in \mathcal{B}_2$. Recall also that we say the complexity of a $\sigma$-algebra$\mathcal{B}$ is at most $m$, and write $\operatorname {complex}(\mathcal{B})\leq m$, if it is generated by $m$ sets.
Comparing the above statement to Lemma 2.2 for $d=2$, i.e to the weak regularity lemma, note that the $\sigma$-algebra$\mathcal{B}$ of scale $L_j$ has a direct product structure only locally, inside each cube $Q_{\underline{t}}(L_j)$. Moreover this product structure varies with $\underline{t}\in \Gamma _{L_j,Q}$, however the “local complexity” remains uniformly bounded.
Assuming for now the validity of Lemmas 4.1 and 4.2 we prove Proposition 4.2. We will make crucial use of Proposition 3.3, namely our parametric counting lemma on $\mathbb{R}^n$ for simplices.
After these preparations we will now consider the general case of Theorem 1.2. Let $Q=Q_1\times \cdots \times Q_d\subseteq \mathbb{R}^n$ with $Q_i\subseteq \mathbb{R}^{n_i}$ cubes of equal side length $l(Q)$ and $\Delta ^0=\Delta _1^0\times \cdots \times \Delta _d^0$ with each $\Delta _i\subseteq \mathbb{R}^{n_i}$ a non-degenerate simplex of $n_i$ points for $1\leq i\leq d$.
We will use a generalized version of the hypergraph terminology introduced in Section 2. In particular, for a vertex set $I=\{1$,$2$, …, $d\}$ and set $K=\{il;\ 1\leq i\leq d,\,1\leq l\leq n_i\}$ we will let $\pi :K\to I$ denote the projection defined by $\pi (il)\coloneq i$. As before we will let $\mathcal{H}_{d,k}\coloneq \{e\subseteq I;\ |e|=k\}$ denote the complete $k$-regular hypergraph with vertex set $I$, and for the multi-index $\underline{n}=(n_1$, …, $n_d)$ define the hypergraph bundle
noting that $|\pi ^{-1}(i)|=n_i$ for all $i\in I$.
In order to parameterize the vertices of direct products of simplices, i.e. sets of the form $\Delta =\Delta _1\times \cdots \times \Delta _d$ with $\Delta _i\subseteq Q_i$, we consider points $\underline{x}=(\underline{x}_1$, …, $\underline{x}_d)$ with $\underline{x}_i=(x_{i1}$, …, $x_{in_i})\in Q_i^{n_i}$ for each $i\in I$. Now for any $1\leq k\leq d$ and any edge $e'\in \mathcal{H}_{d,k}$ we will write $Q_{e'}\coloneq \prod _{i\in e'} Q_i$, and for every $\underline{x}\in Q_1^{n_1}\times \cdots \times Q_d^{n_d}$ and $e\in \mathcal{H}_{d,k}^{\underline{n}}$ we define $\underline{x}_e\coloneq \pi _e(\underline{x})$, where $\pi _e:Q_1^{n_1}\times \cdots \times Q_d^{n_d}\to Q_{\pi (e)}$ is the natural projection map. Writing $\Delta _i=\{x_{i1}$, …, $x_{in_i}\}$ we have that $\Delta _1\times \cdots \times \Delta _d=\{\underline{x}_e:\ e\in \mathcal{H}_{d,d}^{\underline{n}}\}$ since every edge $\underline{x}_e$ is of the form $(x_{1l_1}$, …, $x_{dl_d})$. We can therefore identify points $\underline{x}$ with configurations of the form $\Delta _1\times \cdots \times \Delta _d$.
For any $0<\lambda \ll l(Q)$ the measures $d\sigma _{\lambda \Delta _i^0}$, introduced in Section 3.1, are supported on points $(y_2$, …, $y_{n_i})$ for which the simplex $\Delta _i=\{0$,$y_2$, …, $y_{n_i}\}$ is isometric to $\lambda \Delta _i^0$. For simplicity of notation we will write
Note that the support of the measure $d\sigma ^\lambda _i$ is the set of points $\underline{x}_i$ so that the simplex $\Delta _i\coloneq \{x_{i1}$, …, $x_{in_i}\}$ is isometric to $\lambda \Delta _i^0$ and $x_{i1}\in Q_i$, moreover the measure is normalized. Thus if $S\subseteq Q$ is a set then the density of configurations $\Delta$ in $S$ of the form $\Delta =\Delta _1\times \ldots \times \Delta _d$ with each $\Delta _i\subseteq Q_i$ an isometric copy of $\lambda \Delta _i^0$ is given by the expression
for any cube $\widetilde{Q}\subseteq Q$ of the form $\widetilde{Q}=\widetilde{Q}_1\times \cdots \times \widetilde{Q}_d$ with $\widetilde{Q}_i\subseteq Q_i$ for $1\leq i\leq d$. Note that if $S\subseteq Q$ is a set of measure $|S|\geq \delta |Q|$ for some $\delta >0$, then careful applications of Hölder’s inequality give
for all scales $0<\lambda \ll \varepsilon \, l(Q)$.
In light of the discussion above, and that preceding Proposition 3.2, we see that Proposition 5.1, and hence Theorem 1.2 in general, will follow as a consequence of the following
The validity of Proposition 5.2 will follow immediately from the $d=k$ case of Proposition 5.3.
5.1. Reduction of Proposition 5.2 to a more general “local” counting lemma
For any given $1\leq k\leq d$ and collection of functions $f_e: Q_{\pi (e)}\to [-1,1]$ with $e\in \mathcal{H}_{d,k}^{\underline{n}}$ we define the following multi-linear expressions
for any cube $\widetilde{Q}\subseteq Q$ of the form $\widetilde{Q}=\widetilde{Q}_1\times \cdots \times \widetilde{Q}_d$ with $\widetilde{Q}_i\subseteq Q_i$ for $1\leq i\leq d$.
Our strategy to proving Proposition 5.2 is the same as illustrated in the finite field settings, that is we would like to compare averages $\mathcal{N}_{\lambda \Delta ^0,Q}(f_e;e\in \mathcal{H}_{d,k}^{\underline{n}})$ to those of $\mathcal{M}^d_{\lambda ,Q}(f_e\,;\,e\in \mathcal{H}_{d,k}^{\underline{n}})$, at certain scales $\lambda \in [L_{j+1}, L_j]$, inductively for $1\leq k\leq d$. However in the Euclidean case, an extra complication emerges due to the fact the (hypergraph) regularity lemma, the analogue of Lemma 2.2, does not produce $\sigma$-algebras$\mathcal{B}_{\mathfrak{f}}$, for $\mathfrak{f}\in \mathcal{H}_{d,k-1}^{\underline{n}}$, on the cubes $Q_{\mathfrak{f}}$. In a similar manner to the case for $d=2$ discussed in the previous section, we will only obtain $\sigma$-algebras “local” on cubes $Q_{\underline{t}_{\mathfrak{f}}}(L_0)$ at some scale $L_0>0$. This will have the effect that the functions $f_e$ will be replaced by a family of functions $f_{e,\underline{t}}$, where $\underline{t}$ runs through a grid $\Gamma _{L_0,Q}$.
To be more precise, let $L>0$ be a scale dividing the side-length $l(Q)$. For $\underline{t}\in \Gamma _{L,Q}$ and $e'\in \mathcal{H}_{d,k}$ we will use $\underline{t}_{e'}$ to denote the projection of $\underline{t}$ onto $Q_{e'}$ and $Q_{\underline{t}_{e'}}(L)\coloneq \underline{t}_{e'}+ Q_{e'}(L)$ to denote the projection of the cube $Q_{\underline{t}}(L)$ centered at $\underline{t}$ onto $Q_{e'}$. It is then easy to see that for any $\varepsilon >0$ we have
provided $0<\lambda \ll \varepsilon L$ where $f_{e,\underline{t}}$ denotes the restriction of a function $f_e$ to the cube $Q_{\underline{t}}(L)$.
At this point the proof of Proposition 5.2 reduces to showing that the expressions in Equation 5.9 and Equation 5.10 only differ by $O(\varepsilon )$ at some scales $\lambda \in [L_{j+1},L_j]$, given an $\varepsilon$-admissible sequence $L_0\geq L_1\geq \cdots \geq L_J$, for any collection of bounded functions $f_{e,\underline{t}}$,$e\in \mathcal{H}_{d,k}^{\underline{n}}$,$\underline{t}\in \Gamma _{L_0,Q}$. Indeed, our crucial result will be the following
We will prove Proposition 5.3 by induction on $1\leq k\leq d$. For $k=1$ this is basically Proposition 3.3.
Indeed, in this case for a given $\underline{t}=(t_1$, …, $t_d)\in \Gamma _{L_0,Q}$ and edge $e\in \mathcal{H}_{d,1}^{\underline{n}}=\{il\,:\,1\leq i\leq d,\, 1\leq l\leq n_i\}$ we have that $f_{e,\underline{t}}^m(\underline{x}_e)=f_{il,\underline{t}}^m(x_{il})$ with $x_{il}\in Q_{t_i}(L_0)$ and hence both
By Proposition 3.3 there exists an $1\leq j< J_1=O(M\varepsilon ^{-4})$ and an exceptional set $T_\varepsilon \subseteq \Gamma _{L_0,Q}$ of size $|T_\varepsilon |\leq \varepsilon |\Gamma _{L_0,Q}|$, such that uniformly for $\underline{t}\notin T_\varepsilon$ and for $1\leq i\leq d$, one has
as the all factors are trivially bounded by 1 in magnitude. This implies Equation 5.11 for $k=1$.
For the induction step we again need two main ingredients. The first establishes that the our multi-linear forms $\mathcal{N}^d_{\lambda \Delta ^0,Q}(f_e;\,e\in \mathcal{H}_{d,k}^{\underline{n}})$ are controlled by an appropriate box-type norm attached to a scale $L$.
Let $Q=Q_1\times \cdots \times Q_d$ and $1\leq k\leq d$. For any scale $0<L\ll l(Q)$ and function $f:Q_{e'}\to [-1,1]$ with $e'\in \mathcal{H}_{d,k}$ we define its local box norm at scale $L$ by
for any cube $\widetilde{Q}$ of the form $\widetilde{Q}=\widetilde{Q}_1\times \cdots \times \widetilde{Q}_k$.
The crucial ingredient is the following analogue of the weak hypergraph regularity lemma.
Lemma 5.2 is the parametric and simultaneous version of the extension of Lemma 4.2 to the product of $d$ simplices. The difference is that in the general case one has to deal with a parametric family of functions $f_{e,\underline{t}}^m$ as $\underline{t}$ is running through a grid $\Gamma _{L_0,Q}$. The essential new content of Lemma 5.2 is that one can develop $\sigma$-algebras$\mathcal{B}_{e',\underline{t}}$ on the cubes $Q_{\underline{t}}(L_0)$ with respect to the family of functions $f_{e,\underline{t}}^m$ such that the local structure described above and Equation 5.16 hold simultaneously for almost all $\underline{t}\in \Gamma _{L_0,Q}$.
6. The base case of an inductive strategy to establish Theorem 1.4
In this section we will ultimately establish the base case of our more general inductive argument. We will however start by giving a (new) proof of Theorem B$^\prime$, namely the case $d=1$ of Theorem 1.4.
6.1. A single simplex in $\mathbb{Z}^n$
Let $\Delta ^0=\{v_1=0$,$v_2$, …, $v_{n_1}\}$ be a fixed non-degenerate simplex of $n_1$ points in $\mathbb{Z}^n$ with $n=2n_1+3$ and define $t_{kl}\coloneq v_k\cdot v_l$ for $2\leq k,l\leq n_1$. Recall, see Reference 17, that a simplex $\Delta =\{m_1=0$, …, $m_{n_1}\}\subseteq \mathbb{Z}^n$ is isometric to $\lambda \Delta ^0$ if and only if $m_k\cdot m_l =\lambda ^2 t_{kl}$ for all $2\leq k,l\leq n_1$.
For any positive integer $q$ and $\lambda \in q\sqrt {\mathbb{N}}$ we define $S_{\lambda \Delta ^0,q}(m_2$, …, $m_{n_1}):\mathbb{Z}^{n(n_1-1)}\to \{0,1\}$ be the function whose value is 1 if $m_k\cdot m_l=\lambda ^2 t_{kl}$ with both $m_k$ and $m_l$ in $(q\mathbb{Z})^n$ for all $2\leq k,l\leq n_1$ and is equal to 0 otherwise. It is a well-known fact in number theory, see Reference 11 or Reference 17, that for $n\geq 2n_1+1$ we have that
for some absolute constant $\tau >0$ and some constant $\rho (\Delta ^0)>0$, the so-called singular series, which can be interpreted as the product of the densities of the solutions of the above system of equations among the $p$-adics and among the reals. Thus if we define
where $Q(q,\lambda )\coloneq [-\frac{\lambda }{2},\frac{\lambda }{2}]^n\cap (q\mathbb{Z})^n$. Note that if $S\subseteq Q$ and $\mathcal{N}^1_{\lambda \Delta ^0,q,Q}(1_S$, …, $1_S)>0$ then $S$ must contain an isometric copy of $\lambda \Delta ^0$, while if $|S|\geq \delta |Q|$ for some $\delta >0$ then as before Hölder implies that
for all scales $\lambda \in q\sqrt {\mathbb{N}}$ with $0<\lambda \ll \varepsilon \, l(Q)$.
Recall that for any $0<\varepsilon \ll 1$ and positive integer $q$ we call a sequence $L_1\geq \cdots \geq L_J$$(\varepsilon ,q)$-admissible if $L_j/L_{j+1}\in \mathbb{N}$ and $L_{j+1}\ll \varepsilon ^2 L_j$ for all $1\leq j<J$ and $L_J/q\in \mathbb{N}$. Note that if $\lambda _1\geq \cdots \geq \lambda _{J'}\geq 1$ is any lacunary sequence in $q\sqrt {\mathbb{N}}$ with $J'\gg ( \log \varepsilon ^{-1})\,J+\log q$, one can always finds an $(\varepsilon ,q)$-admissible sequence of scales $L_1\geq \cdots \geq L_{J}$ with the property that for each $1\leq j<J$ the interval $[L_{j+1}, L_j]$ contains at least two consecutive elements from the original lacunary sequence.
In light of these observations we see that the following “counting lemma” ultimately establishes a quantitatively stronger version of Proposition B$^\prime$ that appeared in Section 1.3 and hence immediately establishes Theorem 1.4 for $d=1$.
As in the continuous setting the proof of Proposition 6.1 has two main ingredients, namely Lemmas 6.1 and 6.2. In these lemmas, and for the remainder Sections 6 and 7, we will continue to use the notation
For any cube $Q\subseteq \mathbb{Z}^n$ of side length $l(Q)$ and $q,L\in \mathbb{N}$ satisfying $q\ll L$ with $L$ dividing $l(Q)$, we shall now partition $Q$ into cubic grids $Q_{t}(q,L)=t+((q\mathbb{Z})^n \cap Q(L))$, with $Q(L)=[-\frac{L}{2},\frac{L}{2}]^n$ as usual. These grids form the atoms of a $\sigma$-algebra$\mathcal{G}_{q,L,Q}$. Note that if $q|q'$ and $L'|L$ then $\mathcal{G}_{q,L,Q}\subseteq \mathcal{G}_{q',L',Q}$.
The reduction of Proposition 6.1 to these two lemmas is essentially identical to the analogous argument in the continuous setting as presented at the end of Section 3.1, we choose to omit the details.
6.2. The base case of our general inductive strategy
Let $Q=Q_1\times \ldots \times Q_d$ with $Q_i\subseteq \mathbb{Z}^{2n_i+3}$ be cubes of equal side length $l(Q)$ and $\Delta _i^0\subseteq \mathbb{Z}^{2n_i+3}$ be a non-degenerate simplex of $n_i$ points for $1\leq i\leq d$.
We note that for any $q_0\in \mathbb{N}$ and scale $L_0$ dividing $l(Q)$ if $\underline{t}=(t_1$, …, $t_d)\in \Gamma _{q_0,L_0,Q}$, then the corresponding grids $Q_{\underline{t}}(q_0,L_0)$ in the partition of $Q$ take the form $Q_{\underline{t}}(q_0,L_0)=Q_{t_1}(q_0,L_0)\times \dots \times Q_{t_d}(q_0,L_0)$.
As in the continuous setting we will ultimately need a parametric version of Proposition 6.1, namely Proposition 6.2.
This proposition follows, as the analogous result did in the continuous setting, from Lemma 6.1 and the following parametric version of Lemma 6.2.
Lemma 6.3 is of course the discrete analogue of Lemma 3.2. Since the proofs of Proposition 6.2 and Lemma 6.3 are almost identical to the arguments presented in Section 3.2 we choose to omit these details.
After the preparations in Section 6 we can proceed very similarly as in Section 5 to prove our main result in the discrete case, namely Theorem 1.4. The main difference will be that given $0<\varepsilon \ll 1$ and $1\leq k\leq d$, we construct a positive integer $q_k(\varepsilon )$ and assume that all our sequences of scales will be $(\varepsilon ,q_k(\varepsilon ))$-admissible. The cubes $Q_{\underline{t}}(L)$ will be naturally now be replaced by the grids $Q_{\underline{t}}(q,L)$ of the form that already appear in Section 6 where we always assume $q|L$.
Let $\Delta ^0=\Delta _1^0\times \ldots \times \Delta _d^0$ with each $\Delta _i^0\subseteq \mathbb{Z}^{2n_i+3}$ a non-degenerate simplex of $n_i$ points for $1\leq i\leq d$ and $Q=Q_1\times \ldots \times Q_d\subseteq \mathbb{Z}^n$ with $Q_i\subseteq \mathbb{Z}^{2n_i+3}$ cubes of equal side length $l(Q)$ (taken much larger than the diameter of $\Delta ^0$). We will use the same parameterizations in terms of hypergraph bundles $\mathcal{H}_{d,k}^{\underline{n}}$ and corresponding notations as in Section 5 to count the configurations $\Delta =\Delta _1\times \ldots \times \Delta _d\subseteq Q$ with each $\Delta _i\subseteq Q_i$ an isometric copy of $\lambda \Delta _i^0$ for some $\lambda \in \sqrt {\mathbb{N}}$.
Given any positive integer $q$ and $\lambda \in q\sqrt {\mathbb{N}}$ we will make use of the notation
with $\sigma _{\lambda \Delta ^0_i,q}$ as defined in the previous section and $\underline{x}_i=(x_{i1}$, …, $x_{in_i})\in Q_i^{n_i}$.
Note that if $S\subseteq Q$ then the density of configurations $\Delta$ in $S$, of the form $\Delta =\Delta _1\times \ldots \times \Delta _d$ with each $\Delta _i\subseteq Q_i$ an isometric copy of $\lambda \Delta _i^0$ for some $\lambda \in q\sqrt {\mathbb{N}}$ is given by the expression
More generally, for any given $1\leq k\leq d$ and a family of functions $f_e: Q_{\pi (e)}\to [-1,1]$ with $e\in \mathcal{H}_{d,k}^{\underline{n}}$ we define the multi-linear expression
for any cube $\widetilde{Q}\subseteq Q$ of the form $\widetilde{Q}=\widetilde{Q}_1\times \cdots \times \widetilde{Q}_d$ with $\widetilde{Q}_i\subseteq Q_i$ for $1\leq i\leq d$.
We note that it is easy to show, as in the continuous, that if $S\subseteq Q$ with $|S|\geq \delta |Q|$ for some $\delta >0$ then
for all scales $\lambda \in q\sqrt {\mathbb{N}}$ with $0<\lambda \ll \varepsilon \, l(Q)$. In light of this observation and the discussion preceding Proposition 6.1 the proof of Theorem 1.4 reduces, as it did in the continuous setting, to the following
Quantitative Remark. A careful analysis of our proof reveals that there exist choices of $J_d(\varepsilon )$ and $q_d(\varepsilon )$ which are less than $W_d(\log (C_\Delta \varepsilon ^{-3}))$ and $W_d(C_\Delta \varepsilon ^{-13})$ respectively where $W_k(m)$ is again the tower-exponential function defined by $W_1(m)=\exp (m)$ and $W_{k+1}(m)=\exp (W_k(m))$ for $k\geq 1$.
The proof of Proposition 7.1 follows along the same lines as the analogous result in the continuous setting. As before we will compare the averages $\mathcal{N}^d_{\lambda \Delta ^0,q,Q}(f_e;e\in \mathcal{H}_{d,k}^{\underline{n}})$ to those of $\mathcal{M}^d_{\lambda ,q,Q}(f_e;e\in \mathcal{H}_{d,k}^{\underline{n}})$, at certain scales $q$ and $\lambda \in q\sqrt {\mathbb{N}}$ with with $L_{j+1}\leq \lambda \leq L_j$, inductively for $1\leq k\leq d$. As the arguments closely follow those given in Section 5 we will be brief and emphasize mainly just the additional features.
7.1. Reduction of Proposition 7.1 to a more general “local” counting lemma
For any given $1\leq k\leq d$ and a family of functions $f_e: Q_{\pi (e)}\to [-1,1]$ with $e\in \mathcal{H}_{d,k}^{\underline{n}}$ it is easy to see that for any $\varepsilon >0$, scale $L_0>0$ dividing the side-length $l(Q)$, and $q_0|q$ we have
provided $0<\lambda \ll \varepsilon L_0$ where $f_{e,\underline{t}}$ denotes the restriction of a function $f_e$ to the cube $Q_{\underline{t}}(q_0,L_0)$.
Thus the proof of Proposition 7.1 reduces to showing that the expressions in Equation 7.8 and Equation 7.9 only differ by $O(\varepsilon )$ for all scales $\lambda \in q\sqrt {\mathbb{N}}$ with $L_{j+1}\leq \lambda \leq L_j$, given an $(\varepsilon ,q)$-admissible sequence $L_0\geq L_1\geq \cdots \geq L_J$, for any collection of bounded functions $f_{e,\underline{t}}$,$e\in \mathcal{H}_{d,k}^{\underline{n}}$,$\underline{t}\in \Gamma _{q_0,L_0,Q}$. Indeed, our crucial result will be the following
Note that if $k=d$,$L_0=l(Q)$,$q_0=M=1$, then $|\Gamma _{q_0,L_0,Q}|=1$, and moreover if $f_{e,\underline{t}}=1_S$ for all $e\in \mathcal{H}_{d,k}^{\underline{n}}$ for a set $S\subseteq Q$, then Proposition 7.2 reduces to precisely Proposition 7.1. In fact, Proposition 7.2 is a parametric, multi-linear and simultaneous extension of Proposition 7.1 which we need in the induction step, i.e. when going from level $k-1$ to level $k$.
We will prove Proposition 7.2 by induction on $1\leq k\leq d$.
For $k=1$ this is basically Proposition 6.2, exactly as it was in the base case of the proof of Proposition 5.3.
For the induction step we will again need two main ingredients. The first establishes that the our multi-linear forms $\mathcal{N}^d_{\lambda \Delta ^0,q,Q}(f_e;e\in \mathcal{H}_{d,k}^{\underline{n}})$ are controlled by a box-type norm attached to scales $q'$ and $L$.
Let $Q=Q_1\times \ldots \times Q_d$ with $Q_i\subseteq \mathbb{Z}^{2n_i+3}$ be cubes of equal side length $l(Q)$ and $1\leq k\leq d$. For any scale $0<L\ll l(Q)$ and function $f:Q_{e'}\to [-1,1]$ with $e'\in \mathcal{H}_{d,k}$ we define its local box norm at scales $q'$ and $L$ by
for any cube $\widetilde{Q}$ of the form $\widetilde{Q}=\widetilde{Q}_1\times \cdots \times \widetilde{Q}_k$. We note that Equation 7.4 and Equation 7.5 are special cases of Equation 7.11 and Equation 7.12 with $k=d$,$\underline{n}=(2$, …, $2)$, and $f_e=f$ for all $e\in \mathcal{H}_{d,d}^{\underline{n}}$.
The proof of inequalities Equation 7.13 and Equation 7.14 follow exactly as in the continuous case, see Lemma 5.1, using Lemma 6.1 in place of Lemma 3.1. We omit the details.
The crucial ingredient is again a parametric weak hypergraph regularity lemma, i.e. Lemma 5.2 adapted to the discrete settings. The proof is essentially the same as in the continuous case, with exception that the $\mdlgwhtsquare _{L_j}$-norms are replaced by $\mdlgwhtsquare _{q_j,L_j}$-norms where $q_j=q_0 q^j$ is a given sequence of positive integers and $L_0\geq L_1\geq \cdots \geq L_{J}$ is an $(\varepsilon ,q_J)$-admissible sequence of scales. To state it we say that a $\sigma$-algebra$\mathcal{B}$ on a cube $Q$ is of scale$(q,L)$ if it is refinement of the grid $\mathcal{G}_{q,L,Q}$, i.e. if its atoms partition each cube $Q_{\underline{t}}(q,L)$ of the grid. We will always assume that $q|L$ and $L|l(Q)$. Recall also that we say the complexity of a $\sigma$-algebra$\mathcal{B}$ is at most $m$, and write $\operatorname {complex}(\mathcal{B})\leq m$, if it is generated by $m$ sets.
The proof of Lemma 7.2 follows exactly as the corresponding proof of Lemma 5.2 in the continuous setting, so we will omit the details. We will however provide some details of how one deduces Proposition 7.2, from Lemmas 7.1 and 7.2. The arguments are again very similar to those in the continuous setting, however one needs to make a careful choice of the integers $q_k(\varepsilon )$, appearing in the statement of the Proposition.
8. Appendix: A short direct proof of part (i) of Theorem B$^\prime$
We conclude by providing a short direct proof of Part (i) of Theorem B$^\prime$, namely the following
with $C>0$ a (sufficiently) large absolute constant. Following Reference 14 we further define $S\subseteq \mathbb{Z}^n$ to be $\varepsilon$-uniformly distributed (modulo $q_\varepsilon$) if its relative upper Banach density on any residue class modulo $q_\varepsilon$ never exceeds $(1+\varepsilon ^2)$ times its density on $\mathbb{Z}^n$, namely if
for all $s\in \{1$, …, $q_\varepsilon \}^d$. It turns out that this notion is closely related to the $U^1_{q,L}(Q)$-norm introduced in Section 6. Recall that for any cube $Q\subseteq \mathbb{Z}^n$ and function $f:Q\to [-1,1]$ we define
with $\chi _{q,L}$ denoting the normalized characteristic function of the cubes $Q(q,L)\coloneq [-\frac{L}{2},\frac{L}{2}]^n\cap (q \mathbb{Z})^n$. Note that the $U^1_{q,L}(Q)$-norm measures the mean square oscillation of a function with respect to cubic grids of size $L$ and gap $q$.
The following observation from Reference 14 (specifically Lemmas 1 and 2) is key to our short proof of Theorem 8.1.
Let $\Delta ^0=\{v_1=0$,$v_2$, …, $v_{k}\}$ be a fixed non-degenerate simplex of $k$ points in $\mathbb{Z}^n$ with $n=2k+3$ and define $t_{ij}\coloneq v_i\cdot v_j$ for $2\leq i,j\leq k$. We now define a function which counts isometric copies of $\lambda \Delta ^0$.
Recall, see Reference 17, that a simplex $\Delta =\{m_1=0$, …, $m_{k}\}\subseteq \mathbb{Z}^n$ is isometric to $\lambda \Delta ^0$ if and only if $m_i\cdot m_j =\lambda ^2 t_{ij}$ for all $2\leq i,j\leq k$. For any $\lambda \in \sqrt {\mathbb{N}}$ we define $S_{\lambda \Delta ^0}(m_2$, …, $m_{k}):\mathbb{Z}^{n(k-1)}\to \{0,1\}$ be the function whose value is 1 if $m_i\cdot m_j=\lambda ^2 t_{ij}$ for all $2\leq i,j\leq k$ and is equal to 0 otherwise. It is a well-known fact in number theory, see Reference 11 or Reference 17, that for $n\geq 2k+1$ we have that
for some absolute constant $\tau >0$ and constant $\rho (\Delta ^0)>0$, the so-called singular series, which can be interpreted as the product of the densities of the solutions of the above system of equations among the $p$-adics and among the reals. Thus if we define
It is clear that if $f_1=\cdots =f_k=1_S$ restricted to $Q$, then the above expression is a normalized count of the isometric copies of $\lambda \Delta ^0$ in $S\cap Q$. Thus, Theorem 8.1 will follow from Lemma 8.1 and the following special case (with $q=1$) of Lemma 6.1.
This compares with the purely number theoretic fact that the number of simplices $\Delta =\{v_1=0$,$v_2$, …, $v_k\}\subseteq \mathbb{Z}^n$ isometric to $\lambda \Delta ^0$ is asymptotic to $\rho (\Delta ^0)\,\lambda ^{(n-k)(k-1)}$. Thus, under the same conditions as in Lemma 8.2, we have
J. Bourgain, A Szemerédi type theorem for sets of positive density in ${\mathbf{R}}^k$, Israel J. Math. 54 (1986), no. 3, 307–316, DOI 10.1007/BF02764959. MR853455, Show rawAMSref\bib{Bourg87}{article}{
author={Bourgain, J.},
title={A Szemer\'{e}di type theorem for sets of positive density in ${\mathbf {R}}^k$},
journal={Israel J. Math.},
volume={54},
date={1986},
number={3},
pages={307--316},
issn={0021-2172},
review={\MR {853455}},
doi={10.1007/BF02764959},
}
Reference [2]
David Conlon, Jacob Fox, and Yufei Zhao, A relative Szemerédi theorem, Geom. Funct. Anal. 25 (2015), no. 3, 733–762, DOI 10.1007/s00039-015-0324-9. MR3361771, Show rawAMSref\bib{CFZ}{article}{
author={Conlon, David},
author={Fox, Jacob},
author={Zhao, Yufei},
title={A relative Szemer\'{e}di theorem},
journal={Geom. Funct. Anal.},
volume={25},
date={2015},
number={3},
pages={733--762},
issn={1016-443X},
review={\MR {3361771}},
doi={10.1007/s00039-015-0324-9},
}
Reference [3]
Brian Cook, Ákos Magyar, and Malabika Pramanik, A Roth-type theorem for dense subsets of $\mathbb{R}^d$, Bull. Lond. Math. Soc. 49 (2017), no. 4, 676–689, DOI 10.1112/blms.12043. MR3725488, Show rawAMSref\bib{CMP}{article}{
author={Cook, Brian},
author={Magyar, \'{A}kos},
author={Pramanik, Malabika},
title={A Roth-type theorem for dense subsets of $\mathbb {R}^d$},
journal={Bull. Lond. Math. Soc.},
volume={49},
date={2017},
number={4},
pages={676--689},
issn={0024-6093},
review={\MR {3725488}},
doi={10.1112/blms.12043},
}
Reference [4]
Polona Durcik and Vjekoslav Kovač, Boxes, extended boxes and sets of positive upper density in the Euclidean space, Math. Proc. Cambridge Philos. Soc. 171 (2021), no. 3, 481–501, DOI 10.1017/S0305004120000316. MR4324955, Show rawAMSref\bib{DK}{article}{
author={Durcik, Polona},
author={Kova\v {c}, Vjekoslav},
title={Boxes, extended boxes and sets of positive upper density in the Euclidean space},
journal={Math. Proc. Cambridge Philos. Soc.},
volume={171},
date={2021},
number={3},
pages={481--501},
issn={0305-0041},
review={\MR {4324955}},
doi={10.1017/S0305004120000316},
}
Reference [5]
H. Furstenberg and Y. Katznelson, An ergodic Szemerédi theorem for commuting transformations, J. Analyse Math. 34 (1978), 275–291 (1979), DOI 10.1007/BF02790016. MR531279, Show rawAMSref\bib{FK78}{article}{
author={Furstenberg, H.},
author={Katznelson, Y.},
title={An ergodic Szemer\'{e}di theorem for commuting transformations},
journal={J. Analyse Math.},
volume={34},
date={1978},
pages={275--291 (1979)},
issn={0021-7670},
review={\MR {531279}},
doi={10.1007/BF02790016},
}
Reference [6]
Hillel Furstenberg, Yitzchak Katznelson, and Benjamin Weiss, Ergodic theory and configurations in sets of positive density, Mathematics of Ramsey theory, Algorithms Combin., vol. 5, Springer, Berlin, 1990, pp. 184–198, DOI 10.1007/978-3-642-72905-8_13. MR1083601, Show rawAMSref\bib{FKW86}{article}{
author={Furstenberg, Hillel},
author={Katznelson, Yitzchak},
author={Weiss, Benjamin},
title={Ergodic theory and configurations in sets of positive density},
conference={ title={Mathematics of Ramsey theory}, },
book={ series={Algorithms Combin.}, volume={5}, publisher={Springer, Berlin}, },
date={1990},
pages={184--198},
review={\MR {1083601}},
doi={10.1007/978-3-642-72905-8\_13},
}
Reference [7]
Alan Frieze and Ravi Kannan, The regularity lemma and approximation schemes for dense problems, 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, pp. 12–20, DOI 10.1109/SFCS.1996.548459. MR1450598, Show rawAMSref\bib{FK96}{article}{
author={Frieze, Alan},
author={Kannan, Ravi},
title={The regularity lemma and approximation schemes for dense problems},
conference={ title={37th Annual Symposium on Foundations of Computer Science}, address={Burlington, VT}, date={1996}, },
book={ publisher={IEEE Comput. Soc. Press, Los Alamitos, CA}, },
date={1996},
pages={12--20},
review={\MR {1450598}},
doi={10.1109/SFCS.1996.548459},
}
Reference [8]
W. T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, Ann. of Math. (2) 166 (2007), no. 3, 897–946, DOI 10.4007/annals.2007.166.897. MR2373376, Show rawAMSref\bib{Gow06}{article}{
author={Gowers, W. T.},
title={Hypergraph regularity and the multidimensional Szemer\'{e}di theorem},
journal={Ann. of Math. (2)},
volume={166},
date={2007},
number={3},
pages={897--946},
issn={0003-486X},
review={\MR {2373376}},
doi={10.4007/annals.2007.166.897},
}
Reference [9]
R. L. Graham, Recent trends in Euclidean Ramsey theory, Discrete Math. 136 (1994), no. 1-3, 119–127, DOI 10.1016/0012-365X(94)00110-5. Trends in discrete mathematics. MR1313284, Show rawAMSref\bib{Graham90}{article}{
author={Graham, R. L.},
title={Recent trends in Euclidean Ramsey theory},
note={Trends in discrete mathematics},
journal={Discrete Math.},
volume={136},
date={1994},
number={1-3},
pages={119--127},
issn={0012-365X},
review={\MR {1313284}},
doi={10.1016/0012-365X(94)00110-5},
}
Reference [10]
A. Iosevich and M. Rudnev, Erdős distance problem in vector spaces over finite fields, Trans. Amer. Math. Soc. 359 (2007), no. 12, 6127–6142, DOI 10.1090/S0002-9947-07-04265-1. MR2336319, Show rawAMSref\bib{IR07}{article}{
author={Iosevich, A.},
author={Rudnev, M.},
title={Erd\H {o}s distance problem in vector spaces over finite fields},
journal={Trans. Amer. Math. Soc.},
volume={359},
date={2007},
number={12},
pages={6127--6142},
issn={0002-9947},
review={\MR {2336319}},
doi={10.1090/S0002-9947-07-04265-1},
}
Reference [11]
Y. Kitaoka, Lectures on Siegel modular forms and representation by quadratic forms, Tata Institute of Fundamental Research Lectures on Mathematics and Physics, vol. 77, Published for the Tata Institute of Fundamental Research, Bombay; by Springer-Verlag, Berlin, 1986, DOI 10.1007/978-3-662-00779-2. MR843330, Show rawAMSref\bib{Kitaoka}{book}{
author={Kitaoka, Y.},
title={Lectures on Siegel modular forms and representation by quadratic forms},
series={Tata Institute of Fundamental Research Lectures on Mathematics and Physics},
volume={77},
publisher={Published for the Tata Institute of Fundamental Research, Bombay; by Springer-Verlag, Berlin},
date={1986},
pages={vi+227},
isbn={3-540-16472-3},
review={\MR {843330}},
doi={10.1007/978-3-662-00779-2},
}
Reference [12]
Neil Lyall and Ákos Magyar, Product of simplices and sets of positive upper density in $\mathbb{R}^d$, Math. Proc. Cambridge Philos. Soc. 165 (2018), no. 1, 25–51, DOI 10.1017/S0305004117000184. MR3811544, Show rawAMSref\bib{LM17}{article}{
author={Lyall, Neil},
author={Magyar, \'{A}kos},
title={Product of simplices and sets of positive upper density in $\mathbb {R}^d$},
journal={Math. Proc. Cambridge Philos. Soc.},
volume={165},
date={2018},
number={1},
pages={25--51},
issn={0305-0041},
review={\MR {3811544}},
doi={10.1017/S0305004117000184},
}
Reference [13]
Neil Lyall and Ákos Magyar, Distance graphs and sets of positive upper density in $\mathbb{R}^d$, Anal. PDE 13 (2020), no. 3, 685–700, DOI 10.2140/apde.2020.13.685. MR4085119, Show rawAMSref\bib{LM18}{article}{
author={Lyall, Neil},
author={Magyar, \'{A}kos},
title={Distance graphs and sets of positive upper density in $\mathbb {R}^d$},
journal={Anal. PDE},
volume={13},
date={2020},
number={3},
pages={685--700},
issn={2157-5045},
review={\MR {4085119}},
doi={10.2140/apde.2020.13.685},
}
Reference [14]
Neil Lyall and Ákos Magyar, Distances and trees in dense subsets of $\mathbb{Z}^d$, Israel J. Math. 240 (2020), no. 2, 769–790, DOI 10.1007/s11856-020-2079-8. MR4193150, Show rawAMSref\bib{LM19}{article}{
author={Lyall, Neil},
author={Magyar, \'{A}kos},
title={Distances and trees in dense subsets of $\mathbb {Z}^d$},
journal={Israel J. Math.},
volume={240},
date={2020},
number={2},
pages={769--790},
issn={0021-2172},
review={\MR {4193150}},
doi={10.1007/s11856-020-2079-8},
}
[15]
Neil Lyall, Ákos Magyar, and Hans Parshall, Spherical configurations over finite fields, Amer. J. Math. 142 (2020), no. 2, 373–404, DOI 10.1353/ajm.2020.0010. MR4084158, Show rawAMSref\bib{LMP}{article}{
author={Lyall, Neil},
author={Magyar, \'{A}kos},
author={Parshall, Hans},
title={Spherical configurations over finite fields},
journal={Amer. J. Math.},
volume={142},
date={2020},
number={2},
pages={373--404},
issn={0002-9327},
review={\MR {4084158}},
doi={10.1353/ajm.2020.0010},
}
Reference [16]
Ákos Magyar, On distance sets of large sets of integer points, Israel J. Math. 164 (2008), 251–263, DOI 10.1007/s11856-008-0028-z. MR2391148, Show rawAMSref\bib{Magy08}{article}{
author={Magyar, \'{A}kos},
title={On distance sets of large sets of integer points},
journal={Israel J. Math.},
volume={164},
date={2008},
pages={251--263},
issn={0021-2172},
review={\MR {2391148}},
doi={10.1007/s11856-008-0028-z},
}
Reference [17]
Ákos Magyar, $k$-point configurations in sets of positive density of $\mathbb{Z}^n$, Duke Math. J. 146 (2009), no. 1, 1–34, DOI 10.1215/00127094-2008-060. MR2475398, Show rawAMSref\bib{Magy09}{article}{
author={Magyar, \'{A}kos},
title={$k$-point configurations in sets of positive density of $\mathbb {Z}^n$},
journal={Duke Math. J.},
volume={146},
date={2009},
number={1},
pages={1--34},
issn={0012-7094},
review={\MR {2475398}},
doi={10.1215/00127094-2008-060},
}
[18]
Hans Parshall, Simplices over finite fields, Proc. Amer. Math. Soc. 145 (2017), no. 6, 2323–2334, DOI 10.1090/proc/13493. MR3626492, Show rawAMSref\bib{Hans17}{article}{
author={Parshall, Hans},
title={Simplices over finite fields},
journal={Proc. Amer. Math. Soc.},
volume={145},
date={2017},
number={6},
pages={2323--2334},
issn={0002-9939},
review={\MR {3626492}},
doi={10.1090/proc/13493},
}
Reference [19]
Carl Ludwig Siegel, On the theory of indefinite quadratic forms, Ann. of Math. (2) 45 (1944), 577–622, DOI 10.2307/1969191. MR10574, Show rawAMSref\bib{Siegel}{article}{
author={Siegel, Carl Ludwig},
title={On the theory of indefinite quadratic forms},
journal={Ann. of Math. (2)},
volume={45},
date={1944},
pages={577--622},
issn={0003-486X},
review={\MR {10574}},
doi={10.2307/1969191},
}
Reference [20]
E. Szemerédi, On sets of integers containing no $k$ elements in arithmetic progression, Acta Arith. 27 (1975), 199–245, DOI 10.4064/aa-27-1-199-245. MR369312, Show rawAMSref\bib{Szem75}{article}{
author={Szemer\'{e}di, E.},
title={On sets of integers containing no $k$ elements in arithmetic progression},
journal={Acta Arith.},
volume={27},
date={1975},
pages={199--245},
issn={0065-1036},
review={\MR {369312}},
doi={10.4064/aa-27-1-199-245},
}
Terence Tao, A variant of the hypergraph removal lemma, J. Combin. Theory Ser. A 113 (2006), no. 7, 1257–1280, DOI 10.1016/j.jcta.2005.11.006. MR2259060, Show rawAMSref\bib{Tao06}{article}{
author={Tao, Terence},
title={A variant of the hypergraph removal lemma},
journal={J. Combin. Theory Ser. A},
volume={113},
date={2006},
number={7},
pages={1257--1280},
issn={0097-3165},
review={\MR {2259060}},
doi={10.1016/j.jcta.2005.11.006},
}
Reference [23]
Terence Tao, The ergodic and combinatorial approaches to Szemerédi’s theorem, Additive combinatorics, CRM Proc. Lecture Notes, vol. 43, Amer. Math. Soc., Providence, RI, 2007, pp. 145–193, DOI 10.1090/crmp/043/08. MR2359471, Show rawAMSref\bib{TaoMontreal}{article}{
author={Tao, Terence},
title={The ergodic and combinatorial approaches to Szemer\'{e}di's theorem},
conference={ title={Additive combinatorics}, },
book={ series={CRM Proc. Lecture Notes}, volume={43}, publisher={Amer. Math. Soc., Providence, RI}, },
date={2007},
pages={145--193},
review={\MR {2359471}},
doi={10.1090/crmp/043/08},
}
[24]
Terence Tao and Van Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006, DOI 10.1017/CBO9780511755149. MR2289012, Show rawAMSref\bib{TV}{book}{
author={Tao, Terence},
author={Vu, Van},
title={Additive combinatorics},
series={Cambridge Studies in Advanced Mathematics},
volume={105},
publisher={Cambridge University Press, Cambridge},
date={2006},
pages={xviii+512},
isbn={978-0-521-85386-6},
isbn={0-521-85386-9},
review={\MR {2289012}},
doi={10.1017/CBO9780511755149},
}
Reference [25]
Tamar Ziegler, Nilfactors of $\mathbb{R}^m$-actions and configurations in sets of positive upper density in $\mathbb{R}^m$, J. Anal. Math. 99 (2006), 249–266, DOI 10.1007/BF02789447. MR2279552, Show rawAMSref\bib{Ziegler06}{article}{
author={Ziegler, Tamar},
title={Nilfactors of $\mathbb {R}^m$-actions and configurations in sets of positive upper density in $\mathbb {R}^m$},
journal={J. Anal. Math.},
volume={99},
date={2006},
pages={249--266},
issn={0021-7670},
review={\MR {2279552}},
doi={10.1007/BF02789447},
}
Show rawAMSref\bib{4396041}{article}{
author={Lyall, Neil},
author={Magyar, \'Akos},
title={Weak hypergraph regularity and applications to geometric Ramsey theory},
journal={Trans. Amer. Math. Soc. Ser. B},
volume={9},
number={5},
date={2022},
pages={160-207},
issn={2330-0000},
review={4396041},
doi={10.1090/btran/61},
}
Settings
Change font size
Resize article panel
Enable equation enrichment
(Not available in this browser)
Note. To explore an equation, focus it (e.g., by clicking on it) and use the arrow keys to navigate its structure. Screenreader users should be advised that enabling speech synthesis will lead to duplicate aural rendering.