Quasipolynomial density bounds for $K$-point configurations in $\mathbb{Z}^d$

Introduction

A basic problem in additive combinatorics is to determine which finite patterns must occur in dense subsets of integer lattices. At the qualitative level, the multidimensional Szemerédi theorem of Furstenberg and Katznelson [6] gives a general answer: for every finite set $F \subseteq\mathbb{Z}^d$, every subset of $\mathbb{Z}^d$ of positive upper Banach density contains a homothetic copy $x+qF$, with $x \in\mathbb{Z}^d$ and $q \in\mathbb{N}$. The quantitative bounds obtainable from this general theorem are, however, extremely weak; see [8, 22].

Here we study the corresponding quantitative problem for similarity classes of simplices. Let

be the vertex set of a fixed nondegenerate $(K-1)$-simplex. We say that $\Delta'=\{x_0,\ldots,x_{K-1}\}\subseteq\mathbb{Z}^d$ is a similar copy of $\Delta$ if

for some $t>0$, or equivalently if $\Delta'$ is a translated and rotated image of a dilate of $\Delta$. Every homothetic copy is similar, so the qualitative existence of such configurations follows from the preceding theorem; our concern is the quantitative dependence on the density.

Our main result is the following.

Theorem 1.1. Let $K\geq3$, and let $\Delta\subseteq\mathbb{Z}^d$ be the vertex set of a fixed nondegenerate integral $(K-1)$-simplex. If $d\geq4K+4$, then there are constants $C,c>0$, depending only on $\Delta$ and $d$, such that every set $A\subseteq[N]^d$ containing no nontrivial similar copy of $\Delta$ satisfies

In the common range $d\geq4K+4$, this improves an earlier result of the second author [17], which states that, when $d\geq2K+3$, every set $A\subseteq[N]^d$ containing no nontrivial similar copy of $\Delta$ satisfies

To the best of our knowledge, this is the only previous quantitative result formulated for similar copies of an arbitrary nondegenerate integral simplex.

By Chebyshev’s bound, theorem 1.1 immediately gives the following quantitative relative result in the prime lattice; compare this to [3, 5, 23]. Let $\mathbb{P}$ denote the set of primes.

Corollary 1.2. Let $K\geq3$, and let $\Delta\subseteq\mathbb{Z}^d$ be the vertex set of a fixed nondegenerate integral $(K-1)$-simplex. If $d\geq4K+4$, then there are constants $C,c>0$, depending only on $\Delta$ and $d$, such that every set $A\subseteq(\mathbb{P}\cap[N])^d$ containing no nontrivial similar copy of $\Delta$ satisfies

An equivalent form of our main result is that a set $A\subseteq[N]^d$ of density $\alpha$ must contain a similar copy once

Theorem 1.1 also directly implies the following quantitative result in the Euclidean setting.

Corollary 1.3. Let $K\geq3$, $d\geq4K+4$, and let $\Delta\subseteq\mathbb{Z}^d$ be as above. For every measurable $E\subseteq[0,1]^d$ with $\lvert E\rvert\geq\alpha>0$, there are $x\in\mathbb{R}^d$, $U\in O(d)$, and

such that $x+\lambda U\Delta\subseteq E$.

A short proof, based on averaging Theorem 1.1 over translates of a sufficiently fine lattice, is given in Appendix A. For comparison, a polylogarithmic bound follows from the proof of Bourgain’s simplex theorem in dimensions $d \ge K$ [1, 16]. The cut-operator method also has a direct and simpler implementation in the Euclidean setting, which should permit a lower dimension threshold; we do not pursue this direction here.

Beyond [17], quantitative results in the literature concern special configurations or indirect parametrizations by nonsingular matrix progressions. A notable example is the corners configuration, consisting of axis-parallel isosceles right triangles. Building on ideas originating in the work of Kelley and Meka [11], Jaber, Liu, Lovett, Ostuni and Sawhney [10] recently proved that every corner-free set $A \subseteq[N]^2$ satisfies

For an integral planar triangle, complex multiplication gives a parametrization of its similar copies in the form $x$, $x+T_1y$, $x+T_2y$, where $T_1$, $T_2$, and $T_1-T_2$ are nonsingular rational matrices. Thus the problem becomes a matrix-valued version of Roth’s theorem. Quaternionic constructions, and more generally integral orthogonal pairwise anticommuting Hurwitz–Radon matrices [7], similarly give four-term parametrizations of tetrahedral shapes after passage to a suitable auxiliary lattice. Prendiville’s theorem [19] then yields a density bound of the form $(\log\log N)^{-c}$ for these parametrizations.

This Hurwitz–Radon construction extends to arbitrary nondegenerate simplices, and more generally to configurations of fixed affine rank, but it has an unavoidable dimensional cost. The sharp Hurwitz–Radon theorem forces a $(K-1)$-simplex represented in this way to use matrices of order $\exp(\Omega(K))$; Geramita and Pullman [7] show that the optimal families may be chosen integral. Prendiville’s work also suggests that longer nonsingular matrix progressions should be accessible through higher-order Fourier analysis. Together with the recent quasipolynomial inverse theorem of Leng, Sah and Sawhney [15, 14], this suggests that one might hope for a density bound of the form

for each fixed nonsingular matrix progression. Such a result is not presently available: a multidimensional localized density-increment argument would still have to be developed. Even if carried out, this route would give a substantially weaker dependence on $N$ than Theorem 1.1 and, through the Hurwitz–Radon parametrization, would require an exponentially large dimension.

Outline of the proof

Setup

Let $F_0,\ldots,F_{K-1}:[N]^d\to[-1,1]$, extended by zero to $\mathbb{Z}^d$, and $L:=\binom{K}{2}$, and let $w=\mathbf{1}_{[1,2]}$. Fix $R=\lceil\sigma N\rceil$ for some sufficiently small constant $0<\sigma<1$ depending only on $\Delta$, assume $N$ is sufficiently large depending on $\Delta$ and $d$, and write $w_R(n)=R^{-2}w(n/R^2)$. We count weighted solutions to equation (1.1) for $t=n\in\mathbb{N}$, $n\asymp R^2$, via the multilinear expression

Kitaoka’s estimate [13] supplies

Here $(K-1)d$ is the number of relative variables, while $2L=2\binom{K}{2}$ is the contribution of the $\binom{K}{2}$ quadratic equations.

Suppose that $A\subset[N]^d$ has density $\alpha>0$ and contains no nontrivial similar copy of $\Delta$. Then $\Lambda_N(1_A,\ldots,1_A)=0$. Thus, writing $1_A=\alpha1_{[N]^d}+g$, the pigeonhole principle yields, for some $F_0,\ldots,F_{K-1}$,

with exactly $s>0$ of the $F_i$ equal to $g$ and the remaining $F_i$ equal to $1_{[N]^d}$. The rest of the proof is to turn this lower bound into a density increment.

As is customary in the circle method, one expresses the quadratic relations via the integrals