alphaFeedback

WorksMathematics

Quasipolynomial density bounds for KK-point configurations in Zd\mathbb{Z}^d

AI contributions
  • Large language models
View details

Abstract

Let d,K,N∈Nd,K,N\in \mathbb{N} with K≥3K\geq 3 and d≥4K+4d\geq 4K+4. Let Δ⊂ZdΔ\subset \mathbb{Z}^d be the vertex set of a nondegenerate (K−1)(K-1)-simplex, and let A⊆[N]dA\subseteq[N]^d contain no nontrivial similar copy of ΔΔ. We prove that ∣A∣≪Δ,dNdexp⁡ ⁣(−cΔ,dlog⁡N) |A|\ll_{Δ,d} N^d\exp\!\left(-c_{Δ,d}\sqrt{\log N}\right) improving upon a polylogarithmic bound due to Magyar. We perform a density increment argument using the circle method, and we introduce a ``cut operator'' method to decouple the weighted exponential sum over the system of quadratic forms describing the simplex. Our proof combines ideas from graph theory, functional analysis, and the geometry of numbers. In the process, we apply Finner's fractional form of Hölder's inequality, the analytic large sieve, and Kim's mean value formula for primitive lattice flags.

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 [7] gives a general answer: for every finite set F⊆ZdF \subseteq\mathbb{Z}^d, every subset of Zd\mathbb{Z}^d of positive upper Banach density contains a homothetic copy x+qFx+qF, with x∈Zdx \in\mathbb{Z}^d and q∈Nq \in\mathbb{N}. The quantitative bounds obtainable from this general theorem are, however, extremely weak; see [9, 28].

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

Δ={v0,…,vK−1}⊆Zd\Delta= \{v_0,\ldots,v_{K-1}\} \subseteq\mathbb{Z}^d

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

∣xi−xj∣2=t∣vi−vj∣2(0≤i<j≤K−1)(1)\lvert x_i-x_j\rvert^2=t\lvert v_i-v_j\rvert^2 \qquad(0 \leq i < j \leq K-1) \tag*{(1)}

for some t>0t>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≥3K \geq3, and let Δ⊆Zd\Delta\subseteq\mathbb{Z}^d be the vertex set of a fixed nondegenerate integral (K−1)(K-1)-simplex. If d≥4K+4d \geq4K+4, then there are constants C,c>0C,c>0, depending only on Δ\Delta and dd, such that every set A⊆[N]dA \subseteq[N]^d containing no nontrivial similar copy of Δ\Delta satisfies

∣A∣≤CNdexp⁡(−clog⁡N).\lvert A\rvert\leq CN^d\exp\left(-c\sqrt{\log N}\right).

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

∣A∣≤CΔ,dNd(log⁡N)−2/(11K).\lvert A\rvert\leq C_{\Delta,d}N^d(\log N)^{-2/(11K)}.

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 [4, 6, 29]. Let P\mathbb{P} denote the set of primes.

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

∣A∣≤C∣P∩[N]∣dexp⁡(−clog⁡N).\lvert A\rvert\leq C\lvert\mathbb{P}\cap[N]\rvert^d\exp\left(-c\sqrt{\log N}\right).

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

N≥exp⁡(CΔ,d(1+log⁡(1/α))2).(2)N \geq\exp\left(C_{\Delta,d}\left(1+\log(1/\alpha)\right)^2\right). \tag*{(2)}

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

Corollary 1.3. Let K≥3K \ge3, d≥4K+4d \ge4K+4, and let Δ⊆Zd\Delta\subseteq\mathbb{Z}^{d} be as above. For every measurable E⊆[0,1]dE \subseteq[0,1]^{d} with ∣E∣≥α>0|E| \ge\alpha> 0, there are x∈Rdx \in\mathbb{R}^{d}, U∈O⁡(d)U \in\operatorname{O}(d), and

λ≥exp⁡(−CΔ,d(1+log⁡(1/α))2)\lambda\ge\exp\left(-C_{\Delta,d}(1+\log(1/\alpha))^{2}\right)

such that x+λUΔ⊆Ex+\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≥Kd \ge K [1, 21]. 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 [22], 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 [15], Jaber, Liu, Lovett, Ostuni and Sawhney [14] recently proved that every corner-free set A⊆[N]2A \subseteq[N]^{2} satisfies

∣A∣≤N2exp⁡(−c(log⁡N)1/600).|A| \le N^{2}\exp\left(-c(\log N)^{1/600}\right).

For an integral planar triangle, complex multiplication gives a parametrization of its similar copies in the form xx, x+T1yx+T_{1}y, x+T2yx+T_{2}y, where T1T_{1}, T2T_{2}, and T1−T2T_{1}-T_{2} are nonsingular rational matrices. Thus the problem becomes a matrix-valued version of Roth’s theorem. Pilatte [24] gives a density bound of the form (log⁡N)−1−c(\log N)^{-1-c}, for some absolute constant c>0c>0, for sets avoiding these configurations. Quaternionic constructions, and more generally integral orthogonal pairwise anticommuting Hurwitz–Radon matrices [8], similarly give four-term parametrizations of tetrahedral shapes after passage to a suitable auxiliary lattice. Prendiville’s theorem [25] then yields a density bound of the form (log⁡log⁡N)−c(\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)(K-1)-simplex represented in this way to use matrices of order exp⁡(Ω(K))\exp(\Omega(K)); Geramita and Pullman [8] 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 [19, 18], this suggests that one might hope for a density bound of the form

exp⁡(−(log⁡log⁡N)cK)\exp\left(-(\log\log N)^{cK}\right)

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 NN than Theorem 1.1 and, through the Hurwitz–Radon parametrization, would require an exponentially large dimension.

Acknowledgments and AI disclosure

This project was initiated while the authors were supported by the HUN-REN Alfréd Rényi Institute of Mathematics (Erdős Center) from January to June 2026. The authors thank the Institute for its hospitality.

The second author was supported by Simons Foundation grant MPS-TSM-854813 and grant NFKIH Excellence 15421 from the Research Development and Innovation Office of Hungary.

Large language models were used as a sounding board during the brainstorming phase of the project. They were also used for literature search and copyediting. However, the final argument is the authors’ own, and the manuscript was entirely written and verified by the authors, who take full responsibility for the contents of the proof.

Outline of the proof

Setup

Let F0,…,FK−1:[N]d→[−1,1]F_0,\ldots,F_{K-1}:[N]^d\to[-1,1], extended by zero to Zd\mathbb{Z}^d, and L:=(K2)L:=\binom{K}{2}, and let w=1[1,2)w=\mathbf{1}_{[1,2)}. Fix R=⌊σN⌋R=\lfloor\sigma N\rfloor for some sufficiently small constant 0<σ<10<\sigma<1 depending only on Δ\Delta, assume NN is sufficiently large depending on Δ\Delta and dd, and write wR(n)=R−2w(n/R2)w_R(n)=R^{-2}w(n/R^2). We count weighted solutions to equation (1) for t=n∈Nt=n\in\mathbb{N}, n≍R2n\asymp R^2, via the multilinear expression

ΛN(F0,…,FK−1)=∑nwR(n)∑z0,…,zK−1∈[N]d∣zi−zj∣2=n∣vi−vj∣2 (i<j)∏i=0K−1Fi(zi).(3)\Lambda_N(F_0,\ldots,F_{K-1})=\sum_n w_R(n)\sum_{\substack{z_0,\ldots,z_{K-1}\in[N]^d\\ |z_i-z_j|^2=n|v_i-v_j|^2\ (i<j)}}\prod_{i=0}^{K-1}F_i(z_i). \tag*{(3)}

Kitaoka’s estimate [17] supplies

ΛN(1[N]d,…,1[N]d)≳NdR(K−1)d−2L.(4)\Lambda_N(\mathbf{1}_{[N]^d},\ldots,\mathbf{1}_{[N]^d})\gtrsim N^dR^{(K-1)d-2L}. \tag*{(4)}

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

Suppose that A⊂[N]dA\subset[N]^d has density α>0\alpha>0 and contains no nontrivial similar copy of Δ\Delta. Then ΛN(1A,…,1A)=0\Lambda_N(\mathbf{1}_A,\ldots,\mathbf{1}_A)=0. Thus, writing 1A=α1[N]d+g\mathbf{1}_A=\alpha\mathbf{1}_{[N]^d}+g, the pigeonhole principle yields, for some F0,…,FK−1F_0,\ldots,F_{K-1},

∣ΛN(F0,…,FK−1)∣≳αsNdR(K−1)d−2L,(5)|\Lambda_N(F_0,\ldots,F_{K-1})|\gtrsim\alpha^sN^dR^{(K-1)d-2L}, \tag*{(5)}

with exactly s>0s>0 of the FiF_i equal to gg and the remaining FiF_i equal to 1[N]d\mathbf{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

References

  1. [1]J. Bourgain, A Szemerédi type theorem for sets of positive density in R^k, Israel J. Math. 54 (1986), no. 3, 307–316.DOI
  2. [2]J. W. S. Cassels, An introduction to the geometry of numbers, Classics in Mathematics, Springer-Verlag, Berlin, 1997, Reprint of the corrected 1971 edition.
  3. [3]B. Cook and Á. Magyar, Diophantine equations in the primes, Invent. Math. 198 (2014), no. 3, 701–737.DOI
  4. [4]B. Cook, Á. Magyar, and T. Titichetrakun, A multidimensional Szemerédi theorem in the primes via combinatorics, Ann. Comb. 22 (2018), no. 4, 711–768.DOI
  5. [5]H. Finner, A generalization of Hölder’s inequality and some probability inequalities, Ann. Probab. 20 (1992), no. 4, 1893–1901.DOI
  6. [6]J. Fox and Y. Zhao, A short proof of the multidimensional Szemerédi theorem in the primes, Amer. J. Math. 137 (2015), no. 4, 1139–1145.DOI
  7. [7]H. Furstenberg and Y. Katznelson, An ergodic Szemerédi theorem for commuting transformations, J. Analyse Math. 34 (1978), no. 1, 275–291.DOI
  8. [8]A. V. Geramita and N. J. Pullman, A theorem of Hurwitz and Radon and orthogonal projective modules, Proc. Amer. Math. Soc. 42 (1974), no. 1, 51–56.
  9. [9]W. T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, Ann. of Math. (2) 166 (2007), no. 3, 897–946.
  10. [10]B. Green, Quadratic forms in 8 prime variables, Geom. Funct. Anal. 35 (2025), no. 6, 1587–1637.arxiv.org/abs/2108.10401
  11. [11]A. Greenleaf, A. Iosevich, and K. Taylor, On k-point configuration sets with nonempty interior, Mathematika 68 (2022), no. 1, 163–190.
  12. [12]———, Nonempty interior of configuration sets via microlocal partition optimization, Math. Z. 306 (2024), no. 4, Paper No. 66, 20.arxiv.org/abs/2209.02084
  13. [13]L. Hochfilzer, Systems of bihomogeneous forms of small bidegree, Acta Arith. 213 (2024), no. 4, 325–368.arxiv.org/abs/2305.16159
  14. [14]M. Jaber, Y. P. Liu, S. Lovett, A. Ostuni, and M. Sawhney, Quasipolynomial bounds for the corners theorem, 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2025, pp. 2027–2036.arxiv.org/abs/2504.07006
  15. [15]Z. Kelley and R. Meka, Strong bounds for 3-progressions, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2023, pp. 933–973.arxiv.org/abs/2302.05537
  16. [16]S. Kim, Mean value formulas on sublattices and flags of the random lattice, J. Number Theory 241 (2022), 330–351.arxiv.org/abs/2005.10874
  17. [17]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 by Springer-Verlag, Berlin, 1986.
  18. [18]J. Leng, A. Sah, and M. Sawhney, Improved bounds for Szemerédi’s theorem, 2024, arXiv:2402.17995.
  19. [19]———, Quasipolynomial bounds on the inverse theorem for the Gowers U^{s+1}[N]-norm, 2024, arXiv:2402.17994.arxiv.org/abs/2402.17994
  20. [20]J. Liu, Integral points on quadrics with prime coordinates, Monatsh. Math. 164 (2011), no. 4, 439–465.DOI
  21. [21]N. Lyall and Á. Magyar, Weak hypergraph regularity and applications to geometric Ramsey theory, Trans. Amer. Math. Soc. Ser. B 9 (2022), 160–207.arxiv.org/abs/2301.11319
  22. [22]Á. Magyar, k-point configurations in sets of positive density of Zⁿ, Duke Math. J. 146 (2009), no. 1, 1–34.DOI
  23. [23]H. L. Montgomery and R. C. Vaughan, The large sieve, Mathematika 20 (1973), no. 2, 119–134.
  24. [24]C. Pilatte, New bound for Roth’s theorem with generalized coefficients, Discrete Anal. (2022), Paper No. 16, 21.DOI
  25. [25]S. Prendiville, Matrix progressions in multidimensional sets of integers, Mathematika 61 (2015), no. 1, 14–48.DOI
  26. [26]S. L. Rydin Myerson, Quadratic forms and systems of forms in many variables, Invent. Math. 213 (2018), no. 1, 205–235.DOI
  27. [27]W. M. Schmidt, Asymptotic formulae for point lattices of bounded determinant and subspaces of bounded height, Duke Math. J. 35 (1968), no. 2, 327–339.DOI
  28. [28]T. Tao, A variant of the hypergraph removal lemma, J. Combin. Theory Ser. A 113 (2006), no. 7, 1257–1280.
  29. [29]T. Tao and T. Ziegler, A multi-dimensional Szemerédi theorem for the primes via a correspondence principle, Israel J. Math. 207 (2015), no. 1, 203–228.

Paper details

vlnc:W_6hjwk7mk

published ·

added ·

Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

CC BY 4.0

Original source

  • Mathematics

Large language models · View statement →

Looking for related papers…
Contents