When do disjoint sequences with bounded consecutive differences exist?

Question

Let $N_1, N_2,\dots, N_n \in \mathbb{N}^{>1}$. On what conditions do disjoint increasing sequences $a_1, a_2, \dots, a_n: \mathbb{N} \rightarrow \mathbb{N}$ with consecutive differences bounded by $N_1, N_2, \dots, N_n$, respectively, exist?

[By bounded consecutive differences, I mean that for each sequence $a_i=(a_i^1, a_i^2, \dots)$ we have $$a_i^{j+1} - a_i^j \leq N_i.$$]

So far, I have only been able to answer this questions for all possible values of $N_i$ for $n \leq 3$:

n=2: Any $N_i$ work;

n=3:

• $\min N_i=2$ works iff $\min N_j \geq 4$ for all other j ;
• $\min N_i=3$ always works;

For n=4, I think only the following combinations work:

• $\min N_i=2$ works iff $\min N_j \geq 6$ for all other j;
• $\min N_i=3$ works iff $\min N_j \geq 5$ for all other j;
• $\min N_i=4$ always works.

I have not been able to check this pattern for $n>4$.

Note: The necessity of $\sum_i 1/N_i \leq 1$ is easy to see from counting the numbers used in the sequences $a_i$ up to $N_1 \cdot \dots \cdot N_n$.

Answer 1

For a particular tuple of values, we test it by constructing a directed graph of all tuples smaller then it, element-wise, representing the distance from the last element of each series, with the edges being "increase all values by 1, except for one which is set to 0", and then testing whether there's a cycle in the graph.

For example, for $(2, 4, 4)$, we get this graph:

Note the $(1,0,2), (0, 1, 3), (1, 2,0), (0, 3, 1)$ cycle, which gives the solution $1312$ repeating (each number is the index of the series the value occurs in)

This immediately proves that $\sum_i {\frac1{N_i}} \leq 1$ is necessary, otherwise $f(p) = \sum_i {\frac{p_i}{N_i}}$ gives a topological sort of the graph.

I have programmed this, and for $n \leq 6$, a tuple $N_1, N_2, ..., N_n$ is valid if it's elementwise greater than or equal to any of the following:

$n=1$: $$(2)$$

$n=2$: $$(2, 2)$$

$n=3$: $$(2, 4, 4), (3, 3, 3)$$

$n=4$: $$(2, 4, 8, 8), (2,6,6,6),(3,3,6,6),(3,4,5,8),(3,5,5,5),(4,4,4,4)$$

$n=5$: $$(2, 4, 8, 16, 16), (2, 4, 12, 12, 12), (2, 6, 6, 12, 12), (2, 6, 8, 10, 16), (2, 6, 10, 10, 10), (2, 8, 8, 8, 8), (3, 3, 6, 12, 12), (3, 3, 9, 9, 9), (3, 4, 5, 14, 14), (3, 4, 6, 10, 16), (3, 4, 6, 11, 11), (3, 4, 8, 8, 8), (3, 5, 5, 9, 9), (3, 5, 6, 7, 12), (3, 5, 7, 7, 9), (3, 5, 7, 8, 8), (3, 6, 6, 6, 6), (4, 4, 4, 8, 8), (4, 4, 5, 7, 12), (4, 4, 6,6, 6), (4, 5, 5, 6, 10), (4, 5, 5, 7, 7), (5, 5, 5, 5, 5)$$

$n=6$: $$(2, 4, 8, 16, 32, 32), (2, 4, 8, 24, 24, 24), (2, 4, 12, 12, 24, 24), (2, 4, 12, 20, 20, 20), (2, 4, 16, 16, 16, 16), (2, 6, 6, 12, 24, 24), (2, 6, 6, 18, 18, 18), (2, 6, 8, 10, 28, 28), (2, 6, 8, 12, 20, 32), (2, 6, 8, 12, 22, 22), (2, 6, 8, 16, 16, 16), (2, 6, 12, 12, 12, 12), (2, 10, 10, 10, 10, 10), (3, 3, 6, 12, 24, 24), (3, 3, 6, 18, 18, 18), (3, 3, 9, 9, 18, 18), (3, 3, 9, 15, 15, 15), (3, 3, 12, 12, 12, 12), (3, 4, 5, 14, 28, 28), (3, 4, 5, 22, 22, 22), (3, 4, 6, 10, 32, 32), (3, 4, 6, 11, 21, 32), (3, 4, 6, 11, 22, 22), (3, 4, 6, 16, 16, 16), (3, 4, 8, 8, 16, 16), (3, 4, 8, 13, 13, 13), (3, 4, 11, 11, 11, 11), (3, 5, 5, 9, 18, 18), (3, 5, 5, 14, 14, 14), (3, 5, 6, 7, 24, 24), (3, 5, 6, 8, 21, 21), (3, 5, 6, 9, 15, 24), (3, 5, 6, 9, 17, 17), (3, 5, 6, 12, 12, 12), (3, 5, 9, 9, 9, 9), (3, 8, 8, 8, 8, 8), (4, 4, 4, 8, 16, 16), (4, 4, 4, 12, 12, 12), (4, 4, 6, 6, 12, 12), (4, 4, 6, 10, 10, 10), (4, 4, 8, 8, 8, 8), (4, 7, 7, 7, 7, 7), (6, 6, 6, 6, 6, 6)$$

I can't see any clear pattern which would allow a simpler solution, but it's definitely possible one exists.

Answer 2

Not an answer, but remarks that may be useful.

There is an obvious link between solutions for $(2,2)$ and $(2,4,4)$ tuples: the later is obtained from the former by dividing the second sequence into two parts.
Similarly we obtain $(2, 6, 6, 6)$ from $(2, 2)$ by dividing one sequence in three.

More generally, let's call $T$ the set of tuples $(N_1, \dots, N_n)$ (for any $n$) that verify the problem conditions.
$\forall x, y \in T$, multiply any element of $x$ by the elements of $y$ and expand the tuple: this makes another element of $T$.
Examples, noting $x \times_k y$ the multiplication of $x_k$ by all elements in $y$ :
$(2,2) \times_2 (3,4,5,8) = (2,6,8,10,16)$.
$(2,4,4) \times_1 (3,5,5,5) = (6,10,10,10,4,4) $.
$\forall x \in T, \; x \times_k (1) = x \Rightarrow$ $(1)$ is the neutral element.

Some elements in $T$ do not have divisors: these are the prime tuples.
Another interesting subset is tuples in $T$ which admit no smaller tuple in $T$, using the element-wise partial order: let's call them minimal tuples.
So we are mostly interested in getting the minimal prime tuples, as we can then easily get the other ones.

The fancy multiplication gives some difficulties:

• We have to note on which left-hand element we apply the multiplication. This prevents us from having only one multiplication operator.
• We do not get the result tuple elements in increasing order.
• The operation is not commutative.
• Factorization is not unique. E.g. $(3,3,6) \times_2 (2,2) = (3,6,6,6) = (3,2) \times_2 (3,3,3)$.

One way to get rid of the need to note which element in $x$ is multiplied, would be to always multiply the first one and to rely upon permutations to generate all equivalent tuples.

Another point: let's call saturating tuples those $x$ for which $\sum_{i=1}^n \frac 1 {x_i} = 1$. Their disjoint sequences occupy all places in $\mathbb N$. Saturating tuples are minimal, but the reverse is not true: $(3,5,5,5)$.
Multiplying two saturating tuples always gives a saturating tuple.
Multiplying two minimal elements does not always produce a minimal element: $(3,4,5,8) \times_1 (2,2) = (6,6,4,5,8)$ which is greater than $(6,6,4,4,6)$.

What a rich problem!

Answer 3

Below are some observations which can be useful.

We shall use the following definitions. For any natural numbers $n_1<n_2$ put $[n_1,n_2]=\{n_1,\dots, n_2\}$ and $[n_2]=[1,n_2]$. Given a natural number $m$, let $\mathbb Z_m$ be the quotient group $\mathbb Z/m\mathbb Z$ and $q_m:\mathbb Z\to\mathbb Z_m$ be the quotient homomorphism.

We shall call a finite sequence $(N_1,N_2,\dots,N_n)$ of natural numbers admissible if there exist sequences $a_1, a_2, \dots, a_n: \mathbb{N} \rightarrow \mathbb{N}$ with pairwise disjoint ranges $a_1[\mathbb N],a_2[\mathbb N],\dots, a_n[\mathbb N]$ such that for each $i\in [n]$ and each $j\in\mathbb N$ we have $0<a_i(j+1)-a_i(j)\le N_i$.

Lemma 1. Let $m,N$ be any natural numbers and $A$ be any nonempty subset of $\mathbb Z_m$. Then $A\cap (a+q_m[N])\ne\varnothing$ for each $a\in A$ iff $A\cap (a+q_m[N])\ne\varnothing$ for each $a\in \mathbb Z_m$.

Proof. Suppose that $A\cap (a+q_m[N])\ne\varnothing$ for each $a\in A$. Let $A^*=q_m^{-1}[A]$. Then $(a^*+[N])\ne\varnothing$ for each $a^*\in A^*$. Now it is easy to see that $(a^*+[N])\ne\varnothing$ for each $a^*\in\mathbb Z$. Then $A\cap (a+q_m[N])\ne\varnothing$ for each $a\in \mathbb Z_m$. $\square$.

Proposition 2. For any finite sequence $\tilde N=(N_1,N_2,\dots,N_n)$ of natural numbers the following conditions are equivalent.

1)) The sequence $\tilde N$ is admissible.

2)) There exists a partition $\mathbb N=A_1\cup A_2\cup\dots \cup A_n$ into pairwise disjoint infinite sets such that for each $i\in [n]$ and each $a\in A_i$, we have $A_i\cap (a+[N_i])\ne\varnothing$.

3)) There exist a natural number $m\le n^{\max_{i\in [n]} N_i}$ and a partition $\mathbb Z_m=A'_1\cup A'_2\cup\dots \cup A'_n$ into pairwise disjoint nonempty sets such that for each $i\in [n]$ and each $a\in A'_i$, we have $A'_i\cap (a+q_m[N_i])\ne\varnothing$.

4)) There exist a natural number $m$ and a partition $\mathbb Z_m=A'_1\cup A'_2\cup\dots \cup A'_n$ into pairwise disjoint nonempty sets such that for each $i\in [n]$ and each $a\in A'_i$, we have $A'_i\cap (a+q_m[N_i])\ne\varnothing$.

Proof. $(1 \Rightarrow 2)$ There exist sequences $a_1, a_2, \dots, a_n: \mathbb{N} \rightarrow \mathbb{N}$ with pairwise disjoint ranges such that for each $i\in [n]$ and each $j\in\mathbb N$ we have $0<a_i(j+1)-a_i(j)\le N_i$. Let $A=a_1[\mathbb N]\cup a_2[\mathbb N]\cup ...\cup a_n[\mathbb N]$ and $e:A\to\mathbb N$ be the increasing enumeration. For each $i\in [n]$ put $A_i=e[a_i[\mathbb N]]$. It is easy to check that for each $a\in A_i$, we have $A_i\cap (a+[N_i])\ne\varnothing$ and $\mathbb N=A_1\cup A_2\cup\dots \cup A_n$ is a partition of $\mathbb N$ into pairwise disjoint infinite sets.

$(2 \Rightarrow 3)$ Let $N=\max_{i\in [n]} N_i$, $n_0=\max_{i\in [n]}\min A_i$ and $M=n^N$. By the pigeohole principle, among $M+1$ numbers $n_0,n_0+1,\dots, n_0+M$ there exists numbers $n_1<n_2$ such that for each $i\in [n]$ and $j\in [N]$ we have $n_1+j\in A_i$ iff $n_2+j\in A_i$. Put $m=n_2-n_1$ and $A'_i=q_m([n_1+1,n_2+N]\cap A_i)$ for each $i\in [n]$. It is easy to check that $\mathbb Z_m=A'_1\cup A'_2\cup\dots \cup A'_n$ is a required partition.

$(3 \Rightarrow 4)$ Trivial.

$(4 \Rightarrow 1)$ For each $i\in [n]$ let $a_i:\mathbb{N} \rightarrow q_m^{-1}[A'_i]\cap\mathbb N$ be the monotone bijection. Using the proof of Lemma 1, it is easy to check that the sequences $a_1, a_2, \dots, a_n$ witness that the sequence $\tilde N$ is admissible. $\square$

Proposition 2. Let $(N_1,\dots,N_n)$ be any admissible sequence and $N$ be any natural number bigger than $1$. Then the sequence $$\tilde S=\left(N,N_1+\left\lfloor\frac{N_1-1}{N-1}\right\rfloor+1, \dots,N_n+\left\lfloor\frac{N_n-1}{N-1}\right\rfloor+1\right)$$ is admissible.

Proof. By Proposition 1.(2), there exists a partition $\mathbb N=A_1\cup A_2\cup\dots \cup A_n$ into pairwise disjoint infinite sets such that for each $i\in [n]$ and each $a\in A_i$, we have $A_i\cap (a+[N_i])\ne\varnothing$. Define a partition $$\mathbb N=A'_1\cup A'_2\cup\dots \cup A'_n\cup A'_{n+1}$$ as follows. Let $A'_{n+1}=N\mathbb N$ and $b:\mathbb N\to \mathbb N\setminus A'_{n+1}$ be the monotone bijection. For each $i\in [n]$ put $A'_i=b(A_i)$. By Proposition 1.(2), the partition $$\mathbb N=A'_1\cup A'_2\cup\dots \cup A'_n\cup A'_{n+1}$$ witness that the sentence $\tilde S$ is admissible. $\square$