skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Khintchine-type recurrence for 3-point configurations
Abstract The goal of this paper is to generalise, refine and improve results on large intersections from [2, 8]. We show that if G is a countable discrete abelian group and $$\varphi , \psi : G \to G$$ are homomorphisms, such that at least two of the three subgroups $$\varphi (G)$$ , $$\psi (G)$$ and $$(\psi -\varphi )(G)$$ have finite index in G , then $$\{\varphi , \psi \}$$ has the large intersections property . That is, for any ergodic measure preserving system $$\textbf {X}=(X,\mathcal {X},\mu ,(T_g)_{g\in G})$$ , any $$A\in \mathcal {X}$$ and any $$\varepsilon>0$$ , the set $$ \begin{align*} \{g\in G : \mu(A\cap T_{\varphi(g)}^{-1} A \cap T_{\psi(g)}^{-1} A)>\mu(A)^3-\varepsilon\} \end{align*} $$ is syndetic (Theorem 1.11). Moreover, in the special case where $$\varphi (g)=ag$$ and $$\psi (g)=bg$$ for $$a,b\in \mathbb {Z}$$ , we show that we only need one of the groups $aG$ , $bG$ or $(b-a)G$ to be of finite index in G (Theorem 1.13), and we show that the property fails, in general, if all three groups are of infinite index (Theorem 1.14). One particularly interesting case is where $$G=(\mathbb {Q}_{>0},\cdot )$$ and $$\varphi (g)=g$$ , $$\psi (g)=g^2$$ , which leads to a multiplicative version of the Khintchine-type recurrence result in [8]. We also completely characterise the pairs of homomorphisms $$\varphi ,\psi $$ that have the large intersections property when $$G = {{\mathbb Z}}^2$$ . The proofs of our main results rely on analysis of the structure of the universal characteristic factor for the multiple ergodic averages $$ \begin{align*} \frac{1}{|\Phi_N|} \sum_{g\in \Phi_N}T_{\varphi(g)}f_1\cdot T_{\psi(g)} f_2. \end{align*} $$ In the case where G is finitely generated, the characteristic factor for such averages is the Kronecker factor . In this paper, we study actions of groups that are not necessarily finitely generated, showing, in particular, that, by passing to an extension of $$\textbf {X}$$ , one can describe the characteristic factor in terms of the Conze–Lesigne factor and the $$\sigma $$ -algebras of $$\varphi (G)$$ and $$\psi (G)$$ invariant functions (Theorem 4.10).  more » « less
Award ID(s):
1926686
PAR ID:
10447724
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Forum of Mathematics, Sigma
Volume:
10
ISSN:
2050-5094
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. (, Ergodic Theory and Dynamical Systems)
    Abstract We prove a Khintchine-type recurrence theorem for pairs of endomorphisms of a countable discrete abelian group. As a special case of the main result, if$$\Gamma $$is a countable discrete abelian group,$$\varphi , \psi \in \mathrm {End}(\Gamma )$$, and$$\psi - \varphi $$is an injective endomorphism with finite index image, then for any ergodic measure-preserving$$\Gamma $$-system$$( X, {\mathcal {X}}, \mu , (T_g)_{g \in \Gamma } )$$, any measurable set$$A \in {\mathcal {X}}$$, and any$${\varepsilon }> 0$$, there is a syndetic set of$$g \in \Gamma$$such that$$\mu ( A \cap T_{\varphi(g)}^{-1} A \cap T_{\psi(g)}^{-1} A ) > \mu(A)^3 - \varepsilon$$. This generalizes the main results of Ackelsberget al[Khintchine-type recurrence for 3-point configurations.Forum Math. Sigma10(2022), Paper no. e107] and essentially answers a question left open in that paper [Question 1.12; Khintchine-type recurrence for 3-point configurations.Forum Math. Sigma10(2022), Paper no. e107]. For the group$$\Gamma = {\mathbb {Z}}^d$$, the result applies to pairs of endomorphisms given by matrices whose difference is non-singular. The key ingredients in the proof are: (1) a recent result obtained jointly with Bergelson and Shalom [Khintchine-type recurrence for 3-point configurations.Forum Math. Sigma10(2022), Paper no. e107] that says that the relevant ergodic averages are controlled by a characteristic factor closely related to thequasi-affine(orConze–Lesigne) factor; (2) an extension trick to reduce to systems with well-behaved (with respect to$$\varphi $$and$$\psi $$) discrete spectrum; and (3) a description of Mackey groups associated to quasi-affine cocycles over rotational systems with well-behaved discrete spectrum. 
    more » « less
  2. ; (, Combinatorics, Probability and Computing)
    Abstract Given a hereditary property of graphs $$\mathcal{H}$$ and a $$p\in [0,1]$$ , the edit distance function $$\textrm{ed}_{\mathcal{H}}(p)$$ is asymptotically the maximum proportion of edge additions plus edge deletions applied to a graph of edge density p sufficient to ensure that the resulting graph satisfies $$\mathcal{H}$$ . The edit distance function is directly related to other well-studied quantities such as the speed function for $$\mathcal{H}$$ and the $$\mathcal{H}$$ -chromatic number of a random graph. Let $$\mathcal{H}$$ be the property of forbidding an Erdős–Rényi random graph $$F\sim \mathbb{G}(n_0,p_0)$$ , and let $$\varphi$$ represent the golden ratio. In this paper, we show that if $$p_0\in [1-1/\varphi,1/\varphi]$$ , then a.a.s. as $$n_0\to\infty$$ , \begin{align*} {\textrm{ed}}_{\mathcal{H}}(p) = (1+o(1))\,\frac{2\log n_0}{n_0} \cdot\min\left\{ \frac{p}{-\log(1-p_0)}, \frac{1-p}{-\log p_0} \right\}. \end{align*} Moreover, this holds for $$p\in [1/3,2/3]$$ for any $$p_0\in (0,1)$$ . A primary tool in the proof is the categorization of p -core coloured regularity graphs in the range $$p\in[1-1/\varphi,1/\varphi]$$ . Such coloured regularity graphs must have the property that the non-grey edges form vertex-disjoint cliques. 
    more » « less
  3. ; ; (, Forum of Mathematics, Pi)
    Abstract Letfbe an$$L^2$$-normalized holomorphic newform of weightkon$$\Gamma _0(N) \backslash \mathbb {H}$$withNsquarefree or, more generally, on any hyperbolic surface$$\Gamma \backslash \mathbb {H}$$attached to an Eichler order of squarefree level in an indefinite quaternion algebra over$$\mathbb {Q}$$. Denote byVthe hyperbolic volume of said surface. We prove the sup-norm estimate$$\begin{align*}\| \Im(\cdot)^{\frac{k}{2}} f \|_{\infty} \ll_{\varepsilon} (k V)^{\frac{1}{4}+\varepsilon} \end{align*}$$ with absolute implied constant. For a cuspidal Maaß newform$$\varphi $$of eigenvalue$$\lambda $$on such a surface, we prove that$$\begin{align*}\|\varphi \|_{\infty} \ll_{\lambda,\varepsilon} V^{\frac{1}{4}+\varepsilon}. \end{align*}$$ We establish analogous estimates in the setting of definite quaternion algebras. 
    more » « less
  4. ; ; ; (, International Mathematics Research Notices)
    Abstract Let $$X$$ be a measure space with a measure-preserving action $$(g,x) \mapsto g \cdot x$$ of an abelian group $$G$$. We consider the problem of understanding the structure of measurable tilings $$F \odot A = X$$ of $$X$$ by a measurable tile $$A \subset X$$ translated by a finite set $$F \subset G$$ of shifts, thus the translates $$f \cdot A$$, $$f \in F$$ partition $$X$$ up to null sets. Adapting arguments from previous literature, we establish a “dilation lemma” that asserts, roughly speaking, that $$F \odot A = X$$ implies $$F^{r} \odot A = X$$ for a large family of integer dilations $$r$$, and use this to establish a structure theorem for such tilings analogous to that established recently by the second and fourth authors. As applications of this theorem, we completely classify those random tilings of finitely generated abelian groups that are “factors of iid”, and show that measurable tilings of a torus $${\mathbb{T}}^{d}$$ can always be continuously (in fact linearly) deformed into a tiling with rational shifts, with particularly strong results in the low-dimensional cases $d=1,2$ (in particular resolving a conjecture of Conley, the first author, and Pikhurko in the $d=1$ case). 
    more » « less
  5. ; (, IEEE)
    Given a set of points $$P = (P^+ \sqcup P^-) \subset \mathbb{R}^d$$ for some constant $$d$$ and a supply function $$\mu:P\to \mathbb{R}$$ such that $$\mu(p) > 0~\forall p \in P^+$$, $$\mu(p) < 0~\forall p \in P^-$$, and $$\sum_{p\in P}{\mu(p)} = 0$$, the geometric transportation problem asks one to find a transportation map $$\tau: P^+\times P^-\to \mathbb{R}_{\ge 0}$$ such that $$\sum_{q\in P^-}{\tau(p, q)} = \mu(p)~\forall p \in P^+$$, $$\sum_{p\in P^+}{\tau(p, q)} = -\mu(q) \forall q \in P^-$$, and the weighted sum of Euclidean distances for the pairs $$\sum_{(p,q)\in P^+\times P^-}\tau(p, q)\cdot ||q-p||_2$$ is minimized. We present the first deterministic algorithm that computes, in near-linear time, a transportation map whose cost is within a $$(1 + \varepsilon)$$ factor of optimal. More precisely, our algorithm runs in $$O(n\varepsilon^{-(d+2)}\log^5{n}\log{\log{n}})$$ time for any constant $$\varepsilon > 0$$. While a randomized $$n\varepsilon^{-O(d)}\log^{O(d)}{n}$$ time algorithm for this problem was discovered in the last few years, all previously known deterministic $$(1 + \varepsilon)$$-approximation algorithms run in~$$\Omega(n^{3/2})$$ time. A similar situation existed for geometric bipartite matching, the special case of geometric transportation where all supplies are unit, until a deterministic $$n\varepsilon^{-O(d)}\log^{O(d)}{n}$$ time $$(1 + \varepsilon)$$-approximation algorithm was presented at STOC 2022. Surprisingly, our result is not only a generalization of the bipartite matching one to arbitrary instances of geometric transportation, but it also reduces the running time for all previously known $$(1 + \varepsilon)$$-approximation algorithms, randomized or deterministic, even for geometric bipartite matching. In particular, we give the first $$(1 + \varepsilon)$$-approximate deterministic algorithm for geometric bipartite matching and the first $$(1 + \varepsilon)$$-approximate deterministic or randomized algorithm for geometric transportation with no dependence on $$d$$ in the exponent of the running time's polylog. As an additional application of our main ideas, we also give the first randomized near-linear $$O(\varepsilon^{-2} m \log^{O(1)} n)$$ time $$(1 + \varepsilon)$$-approximation algorithm for the uncapacitated minimum cost flow (transshipment) problem in undirected graphs with arbitrary \emph{real} edge costs. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email