Search

We address partition regularity problems for homogeneous quadratic equations. A consequence of our main results is that, under natural conditions on the coefficients $a,b,c$, for any finite coloring of the positive integers, there exists a solution to $ax^2+by^2=cz^2$ where $x$ and $y$ have the same color (and similar results for $x,z$ and $y,z$). For certain choices of $(a,b,c)$, our result is conditional on an Elliott-type conjecture. Our proofs build on and extend previous arguments of the authors dealing with the Pythagorean equation. We make use of new uniformity properties of aperiodic multiplicative functions and concentration estimates for multiplicative functions along arbitrary binary quadratic forms., Comment: 49 pages. Small changes made

Originating in harmonic analysis, interpolation sets were first studied in dynamics by Glasner and Weiss in the 1980s. A set $S \subset \mathbb{N}$ is an interpolation set for a class of topological dynamical systems $\mathcal{C}$ if any bounded sequence on $S$ can be extended to a sequence that arises from a system in $\mathcal{C}$. In this paper, we provide combinatorial characterizations of interpolation sets for: $\bullet$ (totally) minimal systems; $\bullet$ topologically (weak) mixing systems; $\bullet$ strictly ergodic systems; and $\bullet$ zero entropy systems. Additionally, we prove some results on a slightly different notion, called weak interpolation sets, for several classes of systems. We also answer a question of Host, Kra, and Maass concerning the connection between sets of pointwise recurrence for distal systems and $IP$-sets., Comment: 31 pages, to appear in Trans. Amer. Math. Soc

In contrast to finite arithmetic configurations, relatively little is known about which infinite patterns can be found in every set of natural numbers with positive density. Building on recent advances showing infinite sumsets can be found, we explore numerous open problems and obstructions to finding other infinite configurations in every set of natural numbers with positive density., Comment: 37 pages

We address a core partition regularity problem in Ramsey theory by proving that every finite coloring of the positive integers contains monochromatic Pythagorean pairs, i.e., $x,y\in \mathbb{N}$ such that $x^2\pm y^2=z^2$ for some $z\in \mathbb{N}$. We also show that partitions generated by level sets of multiplicative functions taking finitely many values always contain Pythagorean triples. Our proofs combine known Gowers uniformity properties of aperiodic multiplicative functions with a novel and rather flexible approach based on concentration estimates of multiplicative functions., Comment: 47 pages. Referees comments incorporated

We prove a pointwise convergence result for additive ergodic averages associated with certain multiplicative actions of the Gaussian integers. We derive several applications in dynamics and number theory, including: (i) Wirsing's theorem for Gaussian integers: if $f\colon \mathbb{G} \to \mathbb{R}$ is a bounded completely multiplicative function, then the following limit exists: $$\lim_{N \to \infty} \frac{1}{N^2} \sum_{1 \leq m, n \leq N} f(m + {\rm i} n).$$ (ii) An answer to a special case of a question of Frantzikinakis and Host: for any completely multiplicative real-valued function $f: \mathbb{N} \to \mathbb{R}$, the following limit exists: $$\lim_{N \to \infty} \frac{1}{N^2} \sum_{1 \leq m, n \leq N} f(m^2 + n^2).$$ (iii) A variant of a theorem of Bergelson and Richter on ergodic averages along the $\Omega$ function: if $(X,T)$ is a uniquely ergodic system with unique invariant measure $\mu$, then for any $x\in X$ and $f\in C(X)$, $$\lim_{N\to\infty}\frac{1}{N^2}\sum_{1 \leq m, n \leq N} f(T^{\Omega(m^2 + n^2)}x)=\int_Xf \ d\mu.$$, Comment: 32 pages. Suggestions and comments of the referee have been incorporated

We show that every set $A$ of natural numbers with positive upper density can be shifted to contain the restricted sumset $\{b_1 + b_2 : b_1, b_2\in B \text{ and } b_1 \neq b_2 \}$ for some infinite set $B \subset A$., Comment: 14 pages. Changes after referee comments, improved exposition

Motivated by questions asked by Erdos, we prove that any set $A\subset{\mathbb N}$ with positive upper density contains, for any $k\in{\mathbb N}$, a sumset $B_1+\cdots+B_k$, where $B_1,\dots,B_k\subset{\mathbb N}$ are infinite. Our proof uses ergodic theory and relies on structural results for measure preserving systems. Our techniques are new, even for the previously known case of $k=2$., Comment: 49 Pages

We give a new proof of a sumset conjecture of Furstenberg that was first proved by Hochman and Shmerkin in 2012: if $\log r / \log s$ is irrational and $X$ and $Y$ are $\times r$- and $\times s$-invariant subsets of $[0,1]$, respectively, then $\dim_\text{H} (X+Y) = \min ( 1, \dim_\text{H} X + \dim_\text{H} Y)$. Our main result yields information on the size of the sumset $\lambda X + \eta Y$ uniformly across a compact set of parameters at fixed scales. The proof is combinatorial and avoids the machinery of local entropy averages and CP-processes, relying instead on a quantitative, discrete Marstrand projection theorem and a subtree regularity theorem that may be of independent interest., Comment: 26 pages. Some of this work was originally posted to the arXiv in the first half of the paper "Additive transversality of fractal sets in the reals and the integers" (arXiv:2007.05480v1); that paper has since been updated (arXiv:2007.05480) and no longer includes any of this work

We study sets of recurrence, in both measurable and topological settings, for actions of $(\mathbb{N},\times)$ and $(\mathbb{Q}^{>0},\times)$. In particular, we show that autocorrelation sequences of positive functions arising from multiplicative systems have positive additive averages. We also give criteria for when sets of the form $\{(an+b)^{\ell}/(cn+d)^{\ell}: n \in \mathbb{N}\}$ are sets of multiplicative recurrence, and consequently we recover two recent results in number theory regarding completely multiplicative functions and the Omega function.

By juxtaposing ideas from fractal geometry and dynamical systems, Furstenberg proposed a series of conjectures in the late 1960's that explore the relationship between digit expansions with respect to multiplicatively independent bases. In this work, we introduce and study - in the discrete context of the integers - analogues of some of the notions and results surrounding Furstenberg's work. In particular, we define a new class of fractal sets of integers that parallels the notion of $\times r$-invariant sets on the 1-torus and investigate the additive and geometric independence between two such fractal sets when they are structured with respect to multiplicatively independent bases. Our main results in this direction parallel the works of Furstenberg, Hochman-Shmerkin, Shmerkin, Wu, and Lindenstrauss-Meiri-Peres and include: -a classification of all subsets of the positive integers that are simultaneously $\times r$- and $\times s$-invariant; -integer analogues of two of Furstenberg's transversality conjectures pertaining to the dimensions of the intersection $A\cap B$ and the sumset $A+B$ of $\times r$- and $\times s$-invariant sets $A$ and $B$ when $r$ and $s$ are multiplicatively independent; and -a description of the dimension of iterated sumsets $A+A+\cdots+A$ for any $\times r$-invariant set $A$. We achieve these results by combining ideas from fractal geometry and ergodic theory to build a bridge between the continuous and discrete regimes. For the transversality results, we rely heavily on quantitative bounds on the $L^q$-dimensions of projections of restricted digit Cantor measures obtained recently by Shmerkin. We end by outlining a number of open questions and directions regarding fractal subsets of the integers., Comment: 51 pages

We obtain new results pertaining to convergence and recurrence of multiple ergodic averages along functions from a Hardy field. Among other things, we confirm some of the conjectures posed by Frantzikinakis in [Fra10; Fra16] and obtain combinatorial applications which contain, as rather special cases, several previously known (polynomial and non-polynomial) extensions of Szemeredi's theorem on arithmetic progressions [BL96; BLL08; FW09; Fra10; BMR17]. One of the novel features of our results, which is not present in previous work, is that they allow for a mixture of polynomials and non-polynomial functions. As an illustration, assume $f_i(t)=a_{i,1}t^{c_{i,1}}+\cdots+a_{i,d}t^{c_{i,d}}$ for $c_{i,j}>0$ and $a_{i,j}\in\mathbb{R}$. Then $\bullet$ for any measure preserving system $(X,{\mathcal B},\mu,T)$ and $h_1,\dots,h_k\in L^\infty(X)$, the limit $$\lim_{N\to\infty}\frac{1}{N}\sum_{n=1}^N T^{[f_1(n)]}h_1\cdots T^{[f_k(n)]}h_k$$ exists in $L^2$; $\bullet$ for any $E\subset \mathbb{N}$ with $\overline{\mathrm{d}}(E)>0$ there are $a,n\in\mathbb{N}$ such that $\{a,\, a+[f_1(n)],\ldots,a+[f_k(n)]\}\subset E$. We also show that if $f_1,\dots,f_k$ belong to a Hardy field, have polynomial growth, and are such that no linear combination of them is a polynomial, then for any measure preserving system $(X,{\mathcal B},\mu,T)$ and any $A\in{\mathcal B}$, $$\limsup_{N\to\infty}\frac{1}{N}\sum_{n=1}^N\mu\Big(A\cap T^{-[ f_1(n) ]}A\cap\ldots\cap T^{-[f_k(n)]}A\Big)\,\geq\,\mu(A)^{k+1}.$$, Comment: 41 pages, 2nd revised version implementing referee comments

Let $T$ be a measure preserving $\mathbb{Z}^\ell$-action on the probability space $(X,{\mathcal B},\mu),$ $q_1,\dots,q_m:{\mathbb R}\to{\mathbb R}^\ell$ vector polynomials, and $f_0,\dots,f_m\in L^\infty(X)$. For any $\epsilon > 0$ and multicorrelation sequences of the form $\displaystyle\alpha(n)=\int_Xf_0\cdot T^{ \lfloor q_1(n) \rfloor }f_1\cdots T^{ \lfloor q_m(n) \rfloor }f_m\;d\mu$ we show that there exists a nilsequence $\psi$ for which $\displaystyle\lim_{N - M \to \infty} \frac{1}{N-M} \sum_{n=M}^{N-1} |\alpha(n) - \psi(n)| \leq \epsilon$ and $\displaystyle\lim_{N \to \infty} \frac{1}{\pi(N)} \sum_{p \in {\mathbb P}\cap[1,N]} |\alpha(p) - \psi(p)| \leq \epsilon.$ This result simultaneously generalizes previous results of Frantzikinakis [2] and the authors [11,13]., Comment: 7 pages

We study multicorrelation sequences arising from systems with commuting transformations. Our main result is a refinement of a decomposition result of Frantzikinakis and it states that any multicorrelation sequences for commuting transformations can be decomposed, for every $\epsilon>0$, as the sum of a nilsequence $\phi(n)$ and a sequence $\omega(n)$ satisfying $\lim_{N\to\infty}\frac{1}{N}\sum_{n=1}^N |\omega(n)|<\epsilon$ and $\lim_{N\to\infty}\frac{1}{|\mathbb{P}\cap [N]|}\sum_{p\in \mathbb{P}\cap [N]} |\omega(p)|<\epsilon$., Comment: 27 pages

Building on previous work of Di Nasso and Luperi Baglini, we provide general necessary conditions for a Diophantine equation to be partition regular. These conditions are inspired by Rado's characterization of partition regular linear homogeneous equations. We conjecture that these conditions are also sufficient for partition regularity, at least for equations whose corresponding monovariate polynomial is linear. This would provide a natural generalization of Rado's theorem. We verify that such a conjecture hold for the equations $x^{2}-xy+ax+by+cz=0$ and $x^{2}-y^{2}+ax+by+cz=0$ for $a,b,c\in \mathbb{Z}$ such that $abc=0$ or $% a+b+c=0$. To deal with these equations, we establish new results concerning the partition regularity of polynomial configurations in $\mathbb{Z}$ such as $\left\{ x,x+y,xy+x+y\right\} $, building on the recent result on the partition regularity of $\left\{ x,x+y,xy\right\} $., Comment: 22 pages

Let $(X, \mathcal{B},\mu,T)$ be an ergodic measure preserving system, $A \in \mathcal{B}$ and $\epsilon>0$. We study the largeness of sets of the form \begin{equation*} \begin{split} S = \left\{ n\in\mathbb{N}\colon\mu(A\cap T^{-f_1(n)}A\cap T^{-f_2(n)}A\cap\ldots\cap T^{-f_k(n)}A)> \mu(A)^{k+1} - \epsilon \right\} \end{split} \end{equation*} for various families $\{f_1,\dots,f_k\}$ of sequences $f_i\colon \mathbb{N} \to \mathbb{N}$. For $k \leq 3$ and $f_{i}(n)=i f(n)$, we show that $S$ has positive density if $f(n)=q(p_n)$ where $q \in \mathbb{Z}[x]$ satisfies $q(1)$ or $q(-1) =0$ and $p_n$ denotes the $n$-th prime; or when $f$ is a certain Hardy field sequence. If $T^q$ is ergodic for some $q \in \mathbb{N}$, then for all $r \in \mathbb{Z}$, $S$ is syndetic if $f(n) = qn + r$. For $f_{i}(n)=a_{i}n$, where $a_{i}$ are distinct integers, we show that $S$ can be empty for $k\geq 4$, and for $k = 3$ we found an interesting relation between the largeness of $S$ and the abundance of solutions to certain linear equations in sparse sets of integers. We also provide some partial results when the $f_{i}$ are distinct polynomials., Comment: 29 pages

In this paper we show that every set $A \subset \mathbb{N}$ with positive density contains $B+C$ for some pair $B,C$ of infinite subsets of $\mathbb{N}$, settling a conjecture of Erd\H{o}s. The proof features two different decompositions of an arbitrary bounded sequence into a structured component and a pseudo-random component. Our methods are quite general, allowing us to prove a version of this conjecture for countable amenable groups., Comment: 54 pages. Corrected proof of Theorem 3.22 and added Example 3.27 Keywords: sum sets, almost periodic functions, ultrafilters

We establish new recurrence and multiple recurrence results for a rather large family $\mathcal{F}$ of non-polynomial functions which includes tempered functions defined in [11], as well as functions from a Hardy field with the property that for some $\ell\in \mathbb{N}\cup\{0\}$, $\lim_{x\to\infty }f^{(\ell)}(x)=\pm\infty$ and $\lim_{x\to\infty }f^{(\ell+1)}(x)=0$. Among other things, we show that for any $f\in\mathcal{F}$, any invertible probability measure preserving system $(X,\mathcal{B},\mu,T)$, any $A\in\mathcal{B}$ with $\mu(A)>0$, and any $\epsilon>0$, the sets of returns $$ R_{\epsilon, A}= \big\{n\in\mathbb{N}:\mu(A\cap T^{-\lfloor f(n)\rfloor}A)>\mu^2(A)-\epsilon\big\} $$ and $$ R^{(k)}_{A}= \big\{ n\in\mathbb{N}: \mu\big(A\cap T^{\lfloor f(n)\rfloor}A\cap T^{\lfloor f(n+1)\rfloor}A\cap\cdots\cap T^{\lfloor f(n+k)\rfloor}A\big)>0\big\} $$ possess somewhat unexpected properties of largeness; in particular, they are thick, i.e., contain arbitrarily long intervals., Comment: 51 pages

We generalize Berg's notion of quasi-disjointness to actions of countable groups and prove that every measurably distal system is quasi-disjoint from every measure preserving system. As a corollary we obtain easy to check necessary and sufficient conditions for two systems to be disjoint, provided one of them is measurably distal. We also obtain a Wiener--Wintner type theorem for countable amenable groups with distal weights and applications to weighted multiple ergodic averages and multiple recurrence., Comment: 28 pages. v2: Small modifications in Section 6 as it previously used an incorrect result from [MR19] that has since been corrected in [MR21] (arxiv.org/abs/1609.03631)

We investigate how spectral properties of a measure preserving system $(X,\mathcal{B},\mu,T)$ are reflected in the multiple ergodic averages arising from that system. For certain sequences $a:\mathbb{N}\to\mathbb{N}$ we provide natural conditions on the spectrum $\sigma(T)$ such that for all $f_1,\ldots,f_k\in L^\infty$, \begin{equation*} \lim_{N\to\infty} \frac{1}{N} \sum_{n=1}^N \prod_{j=1}^k T^{ja(n)}f_j = \lim_{N\rightarrow\infty} \frac{1}{N} \sum_{n=1}^N \prod_{j=1}^k T^{jn}f_j \end{equation*} in $L^2$-norm. In particular, our results apply to infinite arithmetic progressions $a(n)=qn+r$, Beatty sequences $a(n)=\lfloor \theta n+\gamma\rfloor$, the sequence of squarefree numbers $a(n)=q_n$, and the sequence of prime numbers $a(n)=p_n$. We also obtain a new refinement of Szemer\'edi's theorem via Furstenberg's correspondence principle. ERRATUM: Theorem 7.1 in the paper is incorrect as stated, and the error originates with Proposition 7.5, part (iii), which was incorrectly quoted from the literature. In the attached erratum we fix the problem by establishing a slightly weaker version of Theorem 7.1 and use it to give a new proof of Theorem 4.2. This ensures that all main results in our main article remain correct. We thank Zhengxing Lian and Jiahao Qiu for bringing this mistake to our attention., Comment: 32 page article + 5 page erratum

An old question in Ramsey theory asks whether any finite coloring of the natural numbers admits a monochromatic pair $\{x+y,xy\}$. We answer this question affirmatively in a strong sense by exhibiting a large new class of non-linear patterns which can be found in a single cell of any finite partition of $\mathbb{N}$. Our proof involves a correspondence principle which transfers the problem into the language of topological dynamics. As a corollary of our main theorem we obtain partition regularity for new types of equations, such as $x^2-y^2=z$ and $x^2+2y^2-3z^2=w$., Comment: 17 pages, 1 figure

We discuss various forms of the classical van der Corput's difference theorem and explore applications to and connections with the theory of uniform distribution, ergodic theory, topological dynamics and combinatorics., Comment: 43 pages

Ergodic and combinatorial results obtained in [10] involved measure preserving actions of the affine group ${\mathcal A}_K$ of a countable field $K$. In this paper we develop a new approach based on ultrafilter limits which allows one to refine and extend the results obtained in [10] to a more general situation involving the measure preserving actions of the non-amenable affine semigroups of a large class of integral domains. (The results in [10] heavily depend on the amenability of the affine group of a field). Among other things, we obtain, as a corollary of an ultrafilter ergodic theorem, the following result: Let $K$ be a number field and let ${\mathcal O}_K$ be the ring of integers of $K$. For any finite partition $K=C_1\cup\cdots\cup C_r$ there exists $i\in\{1,\dots,r\}$ and many $x\in K$ and $y\in{\mathcal O}_K$ such that $\{x+y,xy\}\subset C_i$., Comment: 24 pages

In 1977 L.T. Ramsey showed that any sequence in $\mathbb{Z}^2$ with bounded gaps contains arbitrarily many collinear points. Thereafter, in 1980, C. Pomerance provided a density version of this result, relaxing the condition on the sequence from having bounded gaps to having gaps bounded on average. We give a higher dimensional generalization of these results. Our main theorem is the following. Theorem: Let $d\in\mathbb{N}$, let $f:\mathbb{Z}^d\to\mathbb{Z}^{d+1}$ be a Lipschitz map and let $A\subset\mathbb{Z}^d$ have positive upper Banach density. Then $f(A)$ contains arbitrarily many collinear points. Note that Pomerance's theorem corresponds to the special case $d=1$. In our proof, we transfer the problem from a discrete to a continuous setting, allowing us to take advantage of analytic and measure theoretic tools such as Rademacher's theorem., Comment: 16 pages, small part of the argument clarified in light of suggestions from the referee

In the 1970s Deuber introduced the notion of $(m,p,c)$-sets in $\mathbb{N}$ and showed that these sets are partition regular and contain all linear partition regular configurations in $\mathbb{N}$. In this paper we obtain enhancements and extensions of classical results on $(m,p,c)$-sets in two directions. First, we show, with the help of ultrafilter techniques, that Deuber's results extend to polynomial configurations in abelian groups. In particular, we obtain new partition regular polynomial configurations in $\mathbb{Z}^d$. Second, we give two proofs of a generalization of Deuber's results to general commutative semigroups. We also obtain a polynomial version of the central sets theorem of Furstenberg, extend the theory of $(m,p,c)$-systems of Deuber, Hindman and Lefmann and generalize a classical theorem of Rado regarding partition regularity of linear systems of equations over $\mathbb{N}$ to commutative semigroups., Comment: Some typos, including a terminology confusion involving the words `clique' and `shape', were fixed

We study the restricted isometry property of a matrix that is built from the discrete Fourier transform matrix by collecting rows indexed by quadratic residues. We find an $\epsilon>0$ such that, conditioned on a folklore conjecture in number theory, this matrix satisfies the restricted isometry property with sparsity parameter $K=\Omega(M^{1/2+\epsilon})$, where $M$ is the number of rows., Comment: 6 pages

The restricted isometry property (RIP) is an important matrix condition in compressed sensing, but the best matrix constructions to date use randomness. This paper leverages pseudorandom properties of the Legendre symbol to reduce the number of random bits in an RIP matrix with Bernoulli entries. In this regard, the Legendre symbol is not special---our main result naturally generalizes to any small-bias sample space. We also conjecture that no random bits are necessary for our Legendre symbol--based construction.

We establish a "diagonal" ergodic theorem involving the additive and multiplicative groups of a countable field $K$ and, with the help of a new variant of Furstenberg's correspondence principle, prove that any "large" set in $K$ contains many configurations of the form $\{x+y,xy\}$. We also show that for any finite coloring of $K$ there are many $x,y\in K$ such that $x,x+y$ and $xy$ have the same color. Finally, by utilizing a finitistic version of our main ergodic theorem, we obtain combinatorial results pertaining to finite fields. In particular we obtain an alternative proof for a result obtained by Cilleruelo [11], showing that for any finite field $F$ and any subsets $E_1,E_2\subset F$ with $|E_1||E_2|>6|F|$, there exist $u,v\in F$ such that $u+v\in E_1$ and $uv\in E_2$., Comment: 25 pages, small changes made according to comments from the referees. To appear, Ergodic Theory Dyn. Syst