## Covering the natural numbers with generalized arithmetic progressions

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:

Theorem 1 Let ${\alpha,\beta>1}$ be irrational numbers such that ${\frac1\alpha+\frac1\beta=1}$. Then ${L_\alpha}$ and ${L_\beta}$ are disjoint and moreover ${L_\alpha\cup L_\beta={\mathbb N}}$.

Proof: Assume ${\alpha<\beta}$, so that ${1<\alpha<2<\beta}$. Since ${\alpha<2}$, the set ${L_\alpha}$ has only “holes” of size ${1}$, i.e., if ${x}$ is a natural number not in ${L_\alpha}$ then both ${x-1}$ and ${x+1}$ are in ${L_\alpha}$.

For intuition it may be useful to think of ${\alpha}$ as being close to ${1}$, although all the equations remain true for any ${\alpha<2}$. We have for small natural numbers ${k}$ that ${\lfloor k\alpha\rfloor=k}$, until the first hole, which happens at the smallest natural number ${k}$ such that ${k\alpha>k+1}$. Solving this for ${k}$ we get ${k>\frac1{\alpha+1}>k-1}$ and adding ${1}$ we get ${k+1>\frac\alpha{1-\alpha}=\beta>k}$, so ${k}$ is the first hole in ${L_\alpha}$ and also ${k=\lfloor\beta\rfloor}$, so ${k}$ is the first element in ${L_\beta}$.

Using the same procedure we find that the ${n}$-th hole in ${L_\alpha}$ happens at ${k+n-1}$, where ${k}$ is the least natural number ${k}$ such that ${k\alpha>k+n}$. Solving this for ${k}$ we get ${k>\frac n{\alpha-1}>k-1}$ and adding ${n}$ we get ${k+n>n\frac\alpha{\alpha-1}=n\beta>k+n-1}$, so that ${\lfloor n\beta\rfloor=k+n-1}$.

We conclude that the ${n}$-th hole in ${L_\alpha}$ is the ${n}$-th element in ${L_\beta}$, so in other words ${L_\alpha}$ and ${L_\beta}$ are disjoint and the union ${L_\alpha\cup L_\beta={\mathbb N}}$. $\Box$

This can be used to provide simple counter-examples to some other combinatorial questions. Recall the notion of IP-set: Given an increasing sequence ${\{x_n\}_n}$ of natural numbers, we define the set of finite sums ${\displaystyle FS(\{x_n\}):=\left\{\sum_{n\in A}x_n:A\subset{\mathbb N};0<|A|<\infty\right\}}$. A subset ${E\subset{\mathbb N}}$ is called an IP-set if it contains the set ${FS(\{x_n\})}$ for some increasing sequence ${\{x_n\}}$.

Maybe more important than IP-sets are the sets that intersect non-trivially every IP-set, such sets are called IP${^*}$:

Definition 2 {IP${^*}$} Let ${I\subset{\mathbb N}}$. We say that ${I}$ is an IP${^*}$ set if for any IP-set ${E\subset{\mathbb N}}$ the intersection ${I\cap E}$ is nonempty.

For instance it is not hard to see that the set ${n{\mathbb N}}$ of all multiples of ${n}$ is IP${^*}$ sets for any ${n\in{\mathbb N}}$. One of the most important features of the IP${^*}$ sets is that the intersection of two such sets is still an IP${^*}$, this follows almost immediately from Hindman’s theorem. From this we see that for any IP${^*}$ set ${I}$ and any ${n\in{\mathbb N}}$, the intersection ${I\cap n{\mathbb N}}$ is not only non-empty but actually an IP${^*}$ itself. Moreover, if we divide each element in that intersection by ${n}$ we still get an IP${^*}$ set, in other words, the set ${I/n:=\{a\in{\mathbb N}:an\in I\}}$ is an IP${^*}$ as long as ${I}$ is an IP${^*}$ (I will not prove this here, but this is a non-trivial result).

This result implies that for any IP${^*}$ set ${I}$ and any rational number ${r=n/m}$, the set ${\lfloor rI\rfloor:=\{\lfloor rx\rfloor:x\in I\}}$ is an IP${^*}$, because ${\lfloor rI\rfloor}$ contains ${n(I/m)}$. Thus it is natural to ask if for any real number ${\alpha}$ on has that ${\lfloor\alpha I\rfloor}$ is an IP${^*}$ itself. Using the theorem 1 one concludes promptly that this is not the case, because if so, then both ${\lfloor\alpha{\mathbb N}\rfloor}$ and ${\lfloor\beta{\mathbb N}\rfloor}$ would be IP${^*}$, but they are disjoint when ${\frac1\alpha+\frac1\beta=1}$ (note that ${\lfloor\alpha{\mathbb N}\rfloor=L_\alpha}$).

This entry was posted in Combinatorics and tagged . Bookmark the permalink.

### 2 Responses to Covering the natural numbers with generalized arithmetic progressions

1. Pedro Vieira says:

Seems like an interesting topic. I’ll be waiting for new posts!
Joel, by the way, you have a typo in the beginning of the proof of Thm 1: the x+2 should be an x+1.

• Joel Moreira says:

Thanks for noticing the typo, Pedro, it is now corrected.