## Multiplicative obstructions to syndeticity on the Natural numbers

The notion of syndetic set has some important applications. For instance, the definition, due to Bohr, of almost periodic functions relies on syndetic sets.

Definition 1 (Syndetic set) Let ${G}$ be a topological semi-group. Let ${S\subset G}$. We say that ${S}$ is (left) syndetic (in some places in literature it is called relatively dense) if there exists a compact set ${F\in G}$ such that ${\displaystyle F^{-1}S:=\bigcup_{f\in F} \{a:fa\in S\}}$ is the whole semi-group ${G}$.

We will take the special case ${G=({\mathbb N},+)}$ so in particular the semi-group operation is abelian and the (left) in the definition can be omitted. The topology we consider is the discrete topology, so ${F}$ is compact if and only if ${F}$ is finite. It is not hard to see that in this case a set ${S\subset {\mathbb N}}$ is syndetic if and only if it has bounded gaps, i.e., if we set ${S=\{s_1,s_2,...\}}$ where ${s_1 then ${\displaystyle\sup_{i\in {\mathbb N}}s_{i+1}-s_i}$ is bounded (and the set ${F}$ in the definition can be choose with cardinality equal to that ${\sup}$).

Although not related with the rest of the post I will now give Bohr’s definition of almost periodic functions, since I mentioned it. When ${G=({\mathbb R},+)}$, since all compact set is bounded and all bounded set is inside some compact, it is also easy to see that a set ${S\subset {\mathbb R}}$ is syndetic if and only if it has bounded gaps. In this case we can define bounded gaps as “there is some ${b>0}$ such that ${\forall x\in S \ \exists y\in S}$ verifying ${0“. Let ${P}$ denote the set of continuous functions ${f:{\mathbb R}\rightarrow {\mathbb R}}$ which are periodic, i.e., ${f\in P}$ if there is some period ${\tau}$ such that for all ${x\in {\mathbb R}}$ we have ${f(x+\tau)=f(x)}$. Let ${AP}$ denote the closed subspace generated by ${P}$ (in the uniform topology). Bohr noticed that functions in ${AP}$ may not be periodic but they admit almost periods in the following sense. ${f\in AP}$ if and only if ${\forall \epsilon>0}$ the set of almost periods ${\displaystyle S_\epsilon:=\{\tau:\sup_{x\in {\mathbb R}} |f(x+\tau)-f(x)|<\epsilon\}}$ is syndetic. If one uses different conditions for ${S_\epsilon}$, one may end up with a set of functions which is not a subspace (for instance, if we just require ${S_\epsilon}$ to be infinite.) This is somehow related to the fact that if ${\alpha}$ is irrational, then for any ${\epsilon>0}$, the set ${\{n:\|n\alpha\|<\epsilon\}}$ is syndetic (here ${\|x\|}$ denotes the distance of ${x}$ to the closest integer).

In this post I will list some sets which are know NOT to be syndetic and some which are conjecture not to be syndetic. One can easily check from the definition that to say that a set ${S}$ is not syndetic is the same as to say that for each ${m\in {\mathbb N}}$ one can find ${m}$ consecutive integers, none of which is in ${S}$. The first example is well know:

Proposition 2 The set ${\mathop{\mathbb P}}$ of primes is not syndetic.

Proof: For each ${m\in {\mathbb N}}$, the set ${\{m!+2,m!+3,...,m!+m\}}$ is disjoint from ${\mathop{\mathbb P}}$, so there are intervals disjoint from ${\mathop{\mathbb P}}$ with arbitrarily long length. $\Box$

The next proposition, which generalizes the previous one, appeared as a problem in the IMO of 1989

Proposition 3 Let ${\mathop{\mathbb P}^{\mathbb N}}$ be the set ${\{p^n:p\in \mathop{\mathbb P}, n\in {\mathbb N}\}}$. Then ${\mathop{\mathbb P}^{\mathbb N}}$ is not syndetic.

Proof: The proof is still quite simple, if one remembers the fact that the product of two coprime numbers (bigger than ${1}$) is not in ${\mathop{\mathbb P}^{\mathbb N}}$. Now for each ${m\in {\mathbb N}}$ and ${2\leq k\leq m}$ we have ${(m!)^2+k=k\left(\frac{(m!)^2}k+1\right)}$, and since ${k|m!}$, it is coprime with ${\left(\frac{(m!)^2}k+1\right)}$. Therefore ${(m!)^2+k}$ is not in ${\mathop{\mathbb P}^{\mathbb N}}$ for ${k=2,3,...,m}$ and so there are intervals disjoint from ${\mathop{\mathbb P}^{\mathbb N}}$ with arbitrarily long length. l$\Box$

We can also generalize proposition 2 in a different direction. In the next proposition, instead of considering numbers which are divisible by at most one prime, we consider numbers which are divisible at most once by each prime.

Proposition 4 Let ${SF}$ be the set of square free numbers, i.e., the numbers which are not divisible by any square. Then ${SF}$ is not syndetic.

Proof: To prove this proposition we need to use a different approach. Applying the Chinese remainder theorem we can find, for each ${m\in {\mathbb N}}$, some ${x\in {\mathbb N}}$ such that ${x\equiv -k \mod p_k^2}$, for all ${k=1,...,m}$, where ${p_k}$ is the ${k-th}$ prime number. Then ${x+k}$ is divisible by ${p_k^2}$, so in particular is not in ${SF}$. Thus the interval ${\{x+1,...,x+m\}}$ is disjoint from ${SF}$ and so ${SF}$ is not syndetic. $\Box$

Both propositions 3 and 4 are the first case of stronger results. In proposition 3 we consider numbers which are divisible by at most one prime. We can extend this to numbers which have at most ${l}$ prime divisors, for any ${l\in{\mathbb N}}$. On the other hand, proposition 4 which deals with numbers whose exponents in the prime factorization are bounded by ${1}$, can be generalized to numbers whose exponents in the prime factorization are bounded by ${l}$ for any ${l\in {\mathbb N}}$.

Proposition 5 Let ${l\in {\mathbb N}}$. Let ${\mathop{\mathbb P}_l\subset {\mathbb N}}$ be the set of numbers which are divisible by at most ${l}$ primes (this can be defined symbolically as ${\mathop{\mathbb P}_1:=\mathop{\mathbb P}^{\mathbb N}}$ and for each ${l>1}$, we define recursively ${\mathop{\mathbb P}_l=\mathop{\mathbb P}_{l-1}.\mathop{\mathbb P}_1:=\{ab:a\in \mathop{\mathbb P}_{l-1}, b\in \mathop{\mathbb P}_1\}}$). Then ${\mathop{\mathbb P}_l}$ is not syndetic.

Proof: We use induction on ${l}$. The proof of proposition 3 provides both the base case and the induction step. Assume proved that ${\mathop{\mathbb P}_{l-1}}$ is not syndetic. For each ${m\in {\mathbb N}}$, let ${\{n+1,...,n+m\}}$ be an interval disjoint from ${\mathop{\mathbb P}^{l-1}}$. Now let ${T=\prod (n+k)}$ be a multiple of all those numbers. Then ${T^2+n+k=(n+k)\left(\frac{T^2}{n+k}+1\right)}$ for any ${1\leq k\leq m}$. Thus ${n+k}$ is coprime with ${\frac {T^2}{n+k}+1}$, so ${T^2+n+k}$ has at least one more prime factor than ${n+k}$. Therefore ${T^2+n+k}$ has at least ${l}$ prime factors and so ${\{T^2+n+1,T^2+n+2,...,t^2+n+m\}}$ is an interval of length ${m}$ disjoint from ${\mathop{\mathbb P}_l}$ and since ${m}$ was arbitrary we conclude that ${P_l}$ in not syndetic. $\Box$

We now generalize proposition 4:

Proposition 6 For each ${l\in {\mathbb N}}$ define ${F_l\subset {\mathbb N}}$ to be the set of numbers which are not multiple of any perfect ${l}$-th power. (Formally, ${F_1:=SF}$ and for each ${l>1}$, we define recursively ${F_l:=F_{l-1}F_1=\{ab:a\in F_{l-1}, b\in F_1\}}$). Then ${F_l}$ is not syndetic.

Proof: This proof is practically the same as the proof of proposition 4. Let ${m\in {\mathbb N}}$. Applying the Chinese remainder theorem we can find, some ${x\in {\mathbb N}}$ such that ${x\equiv -k \mod p_k^l}$, for all ${k=1,...,m}$, where again ${p_k}$ is the ${k-th}$ prime number. Then ${x+k}$ is divisible by ${p_k^l}$, so in particular is not in ${F_l}$. Thus the interval ${\{x+1,...,x+m\}}$ is disjoint from ${F_l}$ and so ${F_l}$ is not syndetic. l$\Box$

So far we have considered sets of integers with restrictions in the prime factorization. Using the fundamental theorem of arithmetic we can identify each ${n\in {\mathbb N}}$ with the exponents of its prime factorization. More precisely, let ${E}$ be the set of sequences of non-negative integers with only finitely many positive entries. Thus we can map ${E\rightarrow {\mathbb N}}$ by ${(e_1,e_2,...,e_n,0,0,...)\mapsto p_1^{e_1}p_2^{e_2}...p_n^{e_n}}$ (where again ${p_i}$ is the ${i}$-th prime). Call ${\phi}$ to that map. The fundamental theorem of arithmetic tells us that ${\phi}$ is bijective (furthermore this map is a semi-group isomorphism, where ${{\mathbb N}}$ is equipped with the multiplication).

Thus ${\phi^{-1}(\mathop{\mathbb P}^{\mathbb N})}$ is the set of sequences with only one non-zero entry and ${\phi^{-1}(\mathop{\mathbb P}_l)}$ is the set of sequences with only ${l}$ non-zero entries. On the other hand ${\phi^{-1}(SF)}$ is the set of sequences with all entries less or equal to ${1}$ and ${\phi^{-1}(F_l)}$ is the set of sequences with all entries less or equal to ${l}$.

We can consider weaker restrictions, for instance consider the set ${E_1}$ of all sequences with no entry equal to ${1}$. Is ${\phi(E_1)}$ syndetic? Or more generally, for each ${l\in {\mathbb N}}$, is the set ${\phi(E_l)}$ syndetic (where ${E_l}$ is the set of all sequences with no entry equal to ${l}$)? In a paper of Beiglbock, Bergelson, Hindman and Strauss a far reaching generalization of proposition 6, including this cases, was proved.

Theorem 7 (Beiglbock et. al., Theorem 3.9) Let ${f:{\mathbb N}\rightarrow {\mathbb N}}$ be any function. Let ${E_f\subset E}$ be the set of all sequences such that, for each ${n}$, the ${n}$-th coordinate is not ${f(n)}$. Then ${\phi(E_f)}$ is not syndetic.

In fact, the theorem is true even when we just impose restrictions in some infinite subset of primes. Of course if ${A\subset E_f}$ (for instance, if ${A}$ has more restrictions than ${E_f}$) then ${\phi(A)}$ is also not syndetic. The proof is similar to that of proposition 6 but a clever adjustment is needed.

Proof: For a fixed ${n\in {\mathbb N}}$, we can apply the Chinese remainder theorem to find ${x\in {\mathbb N}}$ such that, for each ${i=1,...,n}$, we have ${x\equiv -i \mod p_i^{f(i)}}$. Thus we can write ${x+i=s_ip_i^{f(i)}}$. But we need that ${p_i\not|s_i}$ in order to have ${x+i\notin \phi(E_f)}$.

Let ${q=\prod_{i=1}^n p_i^{f(i)}}$. Note that we have ${x+q\equiv -i\mod p_i^{s_i}}$ for any ${i}$, so if we add a multiple of ${q}$ to ${x}$ we still have the same congruences. Now we just have to find the right multiple of ${q}$ to add. Let ${\displaystyle q_i=\frac q{p_i^{f(i)}}}$. Then ${x+q+i=(s_i+q_i)p_i^{f(i)}}$, and more generally, for each ${k\in {\mathbb N}}$ we have ${x+kq+i=(s_i+kq_i)p_i^{f(i)}}$. We want to make ${s_i+kq_i}$ not multiple of ${p_i}$, but we want this to happen for all ${i}$, while ${k}$ is the same. We can make better, we will require that ${s_i+kq_i\equiv 1 \mod p_i}$ for all ${i}$.

Note that ${q_i}$ is not multiple of ${p_i}$, so there is an inverse ${v_i}$ for ${q_i}$ ${\mod p_i}$, i.e. ${v_iq_i\equiv 1\mod p_i}$. Then ${s_i+kq_i\equiv 1 \mod p_i}$ is equivalent to ${k\equiv v_i(1-s_i)\mod p_i}$. We can now apply again the Chinese remainder theorem to find such ${k}$, and as we saw, the numbers ${x+kq+i}$ for ${i=1,...,n}$ are not in ${\phi(E_f)}$. $\Box$

One could also think on generalizing proposition 5 this situation: instead of considering the sequences on ${E}$ which don’t have more than ${l}$ non-zero entries, we can consider the sequences on ${E}$ which don’t have exactly ${l}$ non-zero entries. Is the correspondent (by ${\phi}$) subset of ${{\mathbb N}}$ syndetic? The answer is no (and the proof quite simple).

Proposition 8 Let ${l\in {\mathbb N}}$ and let ${F_l\subset E}$ be the set of all sequences with exactly ${l}$ non-zero entries. Let ${E_l:=E\setminus F_l}$ be the set of all sequences that don’t have exactly ${l}$ nonzero entries. Then ${\phi(E_l)}$ is syndetic.

Proof: I thank Ali Adali for showing me a proof of this fact. Let ${R}$ be the product of the first ${l+1}$ primes. Then all the multiples of ${R}$ are in ${\phi(E_l)}$ and so ${\phi(E_l)}$ is syndetic. $\Box$

As we saw, if we forbid numbers with more than ${l}$ prime divisors we kill syndeticity (proposition 5), but if we forbid numbers with exactly ${l}$ prime divisors we don’t, the simple reason being that there are numbers with no multiple with exactly ${l}$ divisors. A new question can be asked now, namely, for an infinite set ${A\subset {\mathbb N}}$, is the set of numbers ${n\in {\mathbb N}}$ such that the number of prime divisors of ${n}$ is not in ${A}$ syndetic? More precisely:

Question Let ${A\subset {\mathbb N}}$. Let ${E_A\subset E}$ be the set of sequences with number of non-zero components in ${A}$. Which conditions on ${A}$ make ${\phi(E_A)}$ syndetic? In particular, if ${{\mathbb N}\setminus A}$ is infinite can we guarantee that ${\phi(E_A)}$ is not syndetic?

I don’t know if the answer to this question is currently available in the literature.

Finally an open problem stated in the paper of Beiglbock, Bergelson, Hindman and Strauss mentioned above, about multiplicative obstructions to syndeticity is the following:

Conjecture Let ${A\subset {\mathbb N}}$ be a set which doesn’t contain arbitrarily long geometric progressions. Is such ${A}$ necessarily not syndetic? Even if we just require ${A}$ to be such that for all ${a\in A}$ and ${n\in {\mathbb N}}$ we have ${an^2\notin A}$, the answer is not known.