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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s