YAMB

Covering the natural numbers with generalized arithmetic progressions

Posted on 25/05/2012 by Joel Moreira

In this short post I will present some curious facts I came across recently.

Given a real number ${\alpha>1}$ construct the set ${L_\alpha:=\{\lfloor n\alpha\rfloor:n\in{\mathbb N}\}}$ , where, as usual, ${\lfloor.\rfloor}$ denotes the floor function. Note that if ${\alpha}$ is an integer, then ${L_\alpha}$ is an (infinite) arithmetic progression starting at ${0}$ , so we can think of the sets ${L_\alpha}$ as generalized arithmetic progressions. In this post I will consider two types of questions about this sets: “can ${L_\alpha}$ be disjoint from ${L_\beta}$ ?” and “Can the union of finitely many ${L_\alpha}$ contain all sufficiently large integer?”.

To try to get some intuition, let’s assume first that ${\alpha}$ is a rational number, say ${\alpha=a/b}$ with ${a,b\in{\mathbb N}}$ coprime. Then it should be clear that ${L_\alpha}$ is a periodic set with period ${a}$ , because ${(n+b)\alpha=n\alpha+a}$ and since ${a}$ is integer, taking floors we get ${\lfloor(n+b)\alpha\rfloor=\lfloor n\alpha\rfloor+a}$ . Thus for any finitely many ${\alpha_1,...,\alpha_k}$ with ${\alpha_i=a_i/b_i}$ , if we make ${c}$ be the least common multiple of ${a_1,a_2,...,a_k}$ we have that each multiple of ${c}$ is contained in each ${L_{\alpha_i}}$ , answering the first question in the negative. Moreover it’s not hard to see that ${a_i-1\notin L_{\alpha_i}}$ , so ${c-1}$ is not in any of the ${L_{\alpha_i}}$ and, more generally, no number of the form ${mc-1}$ is in the union ${\bigcup L_{\alpha_i}}$ , answering the second question in the negative.

This gives some intuition about what we could expect for a general ${\alpha}$ (not necessarily rational). Note that if ${\alpha}$ and ${\beta}$ are very close then the sets ${L_\alpha}$ and ${L_\beta}$ agree in the beginning, so one can hope to approximate an arbitrary ${\alpha}$ with rational numbers. After this reasoning the following result should come as a surprise: Continue reading →

Posted in Combinatorics | Tagged arithmetic progressions | 2 Comments

Koopman-von Neumann Decomposition

Posted on 11/05/2012 by Joel Moreira

In my previous post I presented an ergodic theoretical proof of Roth’s Theorem, assuming the Koopman-von Neumann Decomposition (and some other minor facts). In this post I present a proof of this Decomposition and moreover prove that the compact vectors form a factor.

— 1. Introduction —

Recall that a measure preserving system is a quadruple ${(X,{\cal B},\mu,T)}$ where ${(X,{\cal B})}$ is a Borel space, ${\mu}$ is a probability measure and ${T:X\rightarrow X}$ is an invertible measure preserving map. We denote by ${H}$ the Hilbert space of all ${L^2}$ functions on ${(X,\mu)}$ and define the unitary operator ${U:H\rightarrow H}$ by ${(Uf)(x):=f(Tx)}$ . In this post we are interested in writing ${H}$ as the direct sum of two orthogonal subspaces, one contains the compact vectors and the other contains the weak-mixing vectors. We defined these objects now:

Definition 1 Let ${f\in H}$ . We say that ${f}$ is a compact or almost periodic function if the orbit closure ${\overline{\{U^nf|n\in{\mathbb Z}\}}\subset H}$ is compact as a subset of ${H}$ with the strong topology. The set of all compact functions is denoted by ${H_c}$ .

Definition 2 Let ${g\in H}$ . We say that ${g}$ is a weak-mixing function if
$\displaystyle \lim_{n\rightarrow\infty}\frac1n\sum_{k=1}^n|\langle U^kg,g\rangle|=0$

The set of all weak-mixing functions is denoted by ${H_{wm}}$ .

We can now state the Koopman-von Neumann Decomposition:

Theorem 3 (Koopman-von Neumann) The set ${H_c}$ is a closed subspace of ${H}$ and the it’s orthogonal complement is ${H_{wm}}$ .

Continue reading →

Posted in Number Theory | 1 Comment

Proof of Roth’s Theorem using Ergodic Theory

Posted on 24/04/2012 by Joel Moreira

In 1975 Szemerédi proved what is now known as Szemerédi’s theorem on arithmetic progressions, answering an old question by Erdös and Turán. Twenty years earlier Roth had proved the (much simpler) case of arithmetic progressions of length 3.

Theorem 1 (Roth) Let ${E\subset{\mathbb Z}}$ with positive upper density:
$\displaystyle \overline d(E):=\limsup_{n\rightarrow\infty}\frac{|E\cap\{-n,-n+1,...,n-1,n\}|}{2n+1}>0$

Then there exists an arithmetic progression of length ${3}$ in ${E}$ .

In 1977 Furstenberg gave a new proof of Szemerédi’s theorem using ergodic theory. Thus he also found a new proof of Roth’s theorem. In this post I will present an ergodic theoretical proof of Roth’s theorem, which sheds some light on the ergodic theoretical proof of the full Szemerédi’s theorem. This proof does not quite follows Furstenberg’s original argument, and is more close to a second (somewhat different) ergodic theoretical proof by Furstenberg, Katznelson and Ornstein. Other sources where this proof is presented include the chapter 7 of the recent book of Einsiedler and Ward, the section 4 of this Bergelson’s survey and this exposition by Zhao.

In this post I will focus on the technical aspects of the proof and my goal is to write a short but complete proof, assuming only some basic knowledge on ergodic theory. For all the (vast and important) motivational aspects of the proof I recommend any of the above sources.

Also, to keep things short, I will not prove the so-called Koopman-von Neumann decomposition (Theorem 8 bellow) which is a fundamental piece of this proof, I plan to write a post soon about that (there are also other not so important ergodic theoretical results which I don’t prove here, such as the Ergodic Decomposition, Theorem 4 bellow or the mean ergodic theorem, I plan to also address this results in a future post)

Continue reading →

Posted in Ergodic Theory, Ramsey Theory | 1 Comment

Recurrence theorems

Posted on 15/04/2012 by Joel Moreira

Let ${(X,\mu)}$ be a probability space and let ${T:X\rightarrow X}$ be a (measurable) map such that for any (measurable) set ${A\subset X}$ we have ${\mu(T^{-1}A)=\mu(A)}$ , where as usual ${T^{-1}A:=\{x\in X:Tx\in A\}}$ . Such ${T}$ is called a measure preserving transformation. In this setting, all sets in the pre-orbit of some given set ${A}$ , i.e. the sets ${T^{-n}A}$ , have the same measure. If in addition ${\mu(A)>0}$ then it is clear that two of those sets must intersect (since the total measure is ${1}$ ). This simple observation is (a consequence of) the Poincaré recurrence theorem.

Several improvements can be made to this theorem: we can ask for more than two sets in the orbit to intersect simultaneously, we can ask to have not one but many pairs with non-empty intersection, we can require the intersection to be not only non-empty but to have positive measure (how much measure are we guaranteed to find?). In this post I will list many such extensions that have been proved so far, as well as related results and some questions (that as far as I know are open). I will not provide the proof to most of the results, however I will always put a reference. Continue reading →

Posted in Ergodic Theory | Leave a comment

Topological recurrence versus measure recurrence; a theorem of Kříž

Posted on 27/03/2012 by Joel Moreira

— 1. Introduction —

Previously on this blog I presented a proof of van der Waerden’s theorem which asserts that given a finite partition of ${{\mathbb N}}$ , one of the cells of the partition contains arbitrarily long arithmetic progressions.

It turns out that actually each subset of ${{\mathbb N}}$ with positive upper density contains arbitrarily long arithmetic progressions, and this is the famous Szemerédi’s theorem. Here, as usual, the upper density of a set ${A\subset{\mathbb N}}$ is defined by

$\displaystyle \overline d(A)=\limsup_{n\rightarrow\infty}\frac1n|A\cap[1,n]|$

It is easy to prove that given a finite partition partition of ${{\mathbb N}}$ , one of the cells must have positive upper density, so van der Waerden becomes a corollary of Szemerédi’s theorem.

A different situation happens with Schur’s theorem, which states that given a finite partition of ${{\mathbb N}}$ , one of the cells contain three numbers ${x,y,z}$ such that ${x+y=z}$ . However, in the set ${2{\mathbb N}-1}$ of odd numbers, which has density ${1/2>0}$ , no such ${x,y,z}$ exist (because of the trivial fact that the sum of two odd numbers is an even number).

One difference between this two cases lies in the fact that when we translate an arithmetic progression we get again an arithmetic progression, but when we translate a set ${(x,y,z)}$ with ${x+y=z}$ by a non-zero integer ${a}$ , the resulting set ${(x',y',z')=(x+a,y+a,z+a)}$ no longer has the property that ${x'+y'=z'}$ .

This brings us to the following conjecture (which turned out to be false) posed by Bergelson: If in every finite partition of ${{\mathbb N}}$ one can find a “configuration” of some sort and if those configurations are invariant under translation, then every subset of ${{\mathbb N}}$ with positive density contains one such configuration.

Continue reading →

Posted in Ergodic Theory, Ramsey Theory, Topological Dynamics | Leave a comment

Furstenberg’s Correspondence Theorem

Posted on 19/11/2011 by Joel Moreira

In 1977 Furstenberg gave a new proof of Szemerédi’s theorem using ergodic theory. The first step in that proof was to turn the combinatorial statement into a statement in ergodic theory. Thus Furstenberg created what is now known as Furstenberg’s correspondence principle. While this was not (by far) the most difficult part of the proof of Szemerédi’s theorem, it was this principle that allowed many generalizations of Szemerédi’s theorem to be proved via ergodic theoretical arguments. Most of those generalizations had to wait a long time before seeing a combinatorial proof, and for some, no combinatorial proof was ever found (yet).

In this post I will state and prove the correspondence principle and then I will use it to give another proof of Sárközi’s theorem, discussed in my previous post.

Continue reading →

Posted in Ergodic Theory | 3 Comments

Equidistribution of polynomials, recurrence and van der Corput trick

Posted on 19/09/2011 by Joel Moreira

According to legend, in the early twenty century Hardy and Littlewood were trying to solve the following problem: given a polynomial ${f\in {\mathbb R}[x]}$ with real coefficients, when do we have that the set ${\{f(n)-\lfloor f(n)\rfloor,n\in {\mathbb Z}\}}$ is dense in the interval ${[0,1]}$ ? (actually I remember having heard this somewhere, but I can’t find a reference). They didn’t succeed in this task, the difficulty was that being dense is a property too weak to bootstrap.

In ${1890}$ Poincaré obtained an important result which today can be given as an easy exercise; this is called Poincaré recurrence theorem. It states that in a probability space ${(X,\mu)}$ , if ${T:X\rightarrow X}$ is a map that preserves the measure ${\mu}$ and ${A\subset X}$ is a set of positive measure, then there is some ${n\in {\mathbb Z}}$ such that ${\mu(A\cap T^n A)>0}$ .

More recently, in the late ${1970}$ ‘s, Sárközy proved the following combinatorial result: if a subset ${A\subset {\mathbb Z}}$ has positive upper density (the upper density is defined by ${\displaystyle\overline d(A):=\limsup_{n\rightarrow \infty} \frac1n|A\cap[1,n]|}$ ) then there is some ${n\in {\mathbb Z}}$ and ${a\in A}$ such that ${a+n^2\in A}$ .

This three seemingly different topics are entangled together, with the so-called van der Corput trick in the center. In this post I want to make this relation clear by proving the following theorem (I believe this theorem as stated here was only completely solved by Kamae and Mendes France in this paper). (Update: Actually there is another way to prove this that was probably known before. Ideas in that line go as back as this Furstenberg’s paper where the case when $p(x)=x^2$ is proved.)

Theorem 1 Let ${p\in {\mathbb Z}[x]}$ be a polynomial with integer coefficients and assume that
$\displaystyle \text{for all positive integer }k\text{ there is some }n\in {\mathbb Z}\text{ such that }k|p(n).\ \ \ \ \ (1)$

Then, for any set ${A\subset {\mathbb Z}}$ with positive upper density there exists some integer ${m}$ such that $p(m)\neq0$ and ${A\cap (A-p(m))}$ is non-empty.