Skip to main content
Added Proposition 2.
Source Link
Alex Ravsky
  • 93.3k
  • 5
  • 57
  • 173

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$

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$

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$

Source Link
Alex Ravsky
  • 93.3k
  • 5
  • 57
  • 173

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$