An official website of the United States government
Green used an arithmetic analogue of Szemerédi's celebrated regularity lemma to prove the following strengthening of Roth's theorem in vector spaces. For every α>0, β<α3, and prime number p, there is a least positive integer n_p(α,β) such that if n≥n_p(α,β), then for every subset of 𝔽np of density at least α there is a nonzero d for which the density of three-term arithmetic progressions with common difference d is at least β. We determine for p≥19 the tower height of n_p(α,β) up to an absolute constant factor and an additive term depending only on p. In particular, if we want half the random bound (so β=α^{3}/2), then the dimension n required is a tower of twos of height Θ((log p)loglog(1/α)). It turns out that the tower height in general takes on a different form in several different regions of α and β, and different arguments are used both in the upper and lower bounds to handle these cases.
more »
« less
This content will become publicly available on June 17, 2026
Quantitative finiteness of hyperplanes in hybrid manifolds
We prove a quantitative finiteness theorem for the number of totally geodesic hyperplanes of non-arithmetic hyperbolic n-manifolds that arise from a gluing construction of Gromov and Piatetski-Shapiro for n ≥ 3. This extends work of LindenstraussMohammadi in dimension 3. This follows from effective density theorem for periodic orbits of SO(n −1,1) acting on quotients of SO(n,1) by a lattice for n ≥ 3. The effective density result uses a number of a ideas including Margulis functions, a restricted projection theorem, and an effective equidistribution result for measures on the horospherical subgroup that are nearly full dimensional.
more »
« less
- Award ID(s):
- 2103136
- PAR ID:
- 10639735
- Publisher / Repository:
- arXiv
- Date Published:
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
An integer is called almost-prime if it has fewer than a fixed number of prime factors. In this paper, we study the asymptotic distribution of almost-prime entries in horospherical flows on Gamma\SL(n,R), where Gamma is either SL(n,Z) or a cocompact lattice. In the cocompact case, we obtain a result that implies density for almost-primes in horospherical flows where the number of prime factors is independent of basepoint, and in the space of lattices we show the density of almost-primes in abelian horospherical orbits of points satisfying a certain Diophantine condition. Along the way we give an effective equidistribution result for arbitrary horospherical flows on the space of lattices, as well as an effective rate for the equidistribution of arithmetic progressions in abelian horospherical flows.more » « less
-
Milliken’s tree theorem is a deep result in combinatorics that generalizes a vast number of other results in the subject, most notably Ramsey’s theorem and its many variants and consequences. In this sense, Milliken’s tree theorem is paradigmatic of structural Ramsey theory, which seeks to identify the common combinatorial and logical features of partition results in general. Its investigation in this area has consequently been extensive. Motivated by a question of Dobrinen, we initiate the study of Milliken’s tree theorem from the point of view of computability theory. The goal is to understand how close it is to being algorithmically solvable, and how computationally complex are the constructions needed to prove it. This kind of examination enjoys a long and rich history, and continues to be a highly active endeavor. Applied to combinatorial principles, particularly Ramsey’s theorem, it constitutes one of the most fruitful research programs in computability theory as a whole. The challenge to studying Milliken’s tree theorem using this framework is its unusually intricate proof, and more specifically, the proof of the Halpern-Laüchli theorem, which is a key ingredient. Our advance here stems from a careful analysis of the Halpern-Laüchli theorem which shows that it can be carried out effectively (i.e., that it is computably true). We use this as the basis of a new inductive proof of Milliken’s tree theorem that permits us to gauge its effectivity in turn. The key combinatorial tool we develop for the inductive step is a fast-growing computable function that can be used to obtain a finitary, or localized, version of Milliken’s tree theorem. This enables us to build solutions to the full Milliken’s tree theorem using effective forcing. The principal result of this is a full classification of the computable content of Milliken’s tree theorem in terms of the jump hierarchy, stratified by the size of instance. As usual, this also translates into the parlance of reverse mathematics, yielding a complete understanding of the fragment of second-order arithmetic required to prove Milliken’s tree theorem. We apply our analysis also to several well-known applications of Milliken’s tree theorem, namely Devlin’s theorem, a partition theorem for Rado graphs, and a generalized version of the so-called tree theorem of Chubb, Hirst, and McNicholl. These are all certain kinds of extensions of Ramsey’s theorem for different structures, namely the rational numbers, the Rado graph, and perfect binary trees, respectively. We obtain a number of new results about how these principles relate to Milliken’s tree theorem and to each other, in terms of both their computability-theoretic and combinatorial aspects. In particular, we establish new structural Ramsey-theoretic properties of the Rado graph theorem and the generalized Chubb-Hirst-McNicholl tree theorem using Zucker’s notion of big Ramsey structure.more » « less
-
Abstract A nonlinear version of Roth's theorem states that dense sets of integers contain configurations of the form , , . We obtain a multidimensional version of this result, which can be regarded as a first step toward effectivising those cases of the multidimensional polynomial Szemerédi theorem involving polynomials with distinct degrees. In addition, we prove an effective “popular” version of this result, showing that every dense set has some non‐zero such that the number of configurations with difference parameter is almost optimal. Perhaps surprisingly, the quantitative dependence in this result is exponential, compared to the tower‐type bounds encountered in the popular linear Roth theorem.more » « less
-
null (Ed.)Motivated by the increasing need to understand the distributed algorithmic foundations of large-scale graph computations, we study some fundamental graph problems in a message-passing model for distributed computing where k ≥ 2 machines jointly perform computations on graphs with n nodes (typically, n >> k). The input graph is assumed to be initially randomly partitioned among the k machines, a common implementation in many real-world systems. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation. Our main contribution is the General Lower Bound Theorem , a theorem that can be used to show non-trivial lower bounds on the round complexity of distributed large-scale data computations. This result is established via an information-theoretic approach that relates the round complexity to the minimal amount of information required by machines to solve the problem. Our approach is generic, and this theorem can be used in a “cookbook” fashion to show distributed lower bounds for several problems, including non-graph problems. We present two applications by showing (almost) tight lower bounds on the round complexity of two fundamental graph problems, namely, PageRank computation and triangle enumeration . These applications show that our approach can yield lower bounds for problems where the application of communication complexity techniques seems not obvious or gives weak bounds, including and especially under a stochastic partition of the input. We then present distributed algorithms for PageRank and triangle enumeration with a round complexity that (almost) matches the respective lower bounds; these algorithms exhibit a round complexity that scales superlinearly in k , improving significantly over previous results [Klauck et al., SODA 2015]. Specifically, we show the following results: PageRank: We show a lower bound of Ὼ(n/k 2 ) rounds and present a distributed algorithm that computes an approximation of the PageRank of all the nodes of a graph in Õ(n/k 2 ) rounds. Triangle enumeration: We show that there exist graphs with m edges where any distributed algorithm requires Ὼ(m/k 5/3 ) rounds. This result also implies the first non-trivial lower bound of Ὼ(n 1/3 ) rounds for the congested clique model, which is tight up to logarithmic factors. We then present a distributed algorithm that enumerates all the triangles of a graph in Õ(m/k 5/3 + n/k 4/3 ) rounds.more » « less
