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 be a topological semi-group. Let . We say that is (left) syndetic (in some places in literature it is called relatively dense) if there exists a compact set such that is the whole semi-group .
We will take the special case 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 is compact if and only if is finite. It is not hard to see that in this case a set is syndetic if and only if it has bounded gaps, i.e., if we set where then is bounded (and the set in the definition can be choose with cardinality equal to that ).
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 , since all compact set is bounded and all bounded set is inside some compact, it is also easy to see that a set is syndetic if and only if it has bounded gaps. In this case we can define bounded gaps as “there is some such that verifying “. Let denote the set of continuous functions which are periodic, i.e., if there is some period such that for all we have . Let denote the closed subspace generated by (in the uniform topology). Bohr noticed that functions in may not be periodic but they admit almost periods in the following sense. if and only if the set of almost periods is syndetic. If one uses different conditions for , one may end up with a set of functions which is not a subspace (for instance, if we just require to be infinite.) This is somehow related to the fact that if is irrational, then for any , the set is syndetic (here denotes the distance of 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 is not syndetic is the same as to say that for each one can find consecutive integers, none of which is in . The first example is well know:
Proof: For each , the set is disjoint from , so there are intervals disjoint from with arbitrarily long length.
The next proposition, which generalizes the previous one, appeared as a problem in the IMO of 1989
Proof: The proof is still quite simple, if one remembers the fact that the product of two coprime numbers (bigger than ) is not in . Now for each and we have , and since , it is coprime with . Therefore is not in for and so there are intervals disjoint from with arbitrarily long length. l
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.
Proof: To prove this proposition we need to use a different approach. Applying the Chinese remainder theorem we can find, for each , some such that , for all , where is the prime number. Then is divisible by , so in particular is not in . Thus the interval is disjoint from and so is not syndetic.
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 prime divisors, for any . On the other hand, proposition 4 which deals with numbers whose exponents in the prime factorization are bounded by , can be generalized to numbers whose exponents in the prime factorization are bounded by for any .
Proof: We use induction on . The proof of proposition 3 provides both the base case and the induction step. Assume proved that is not syndetic. For each , let be an interval disjoint from . Now let be a multiple of all those numbers. Then for any . Thus is coprime with , so has at least one more prime factor than . Therefore has at least prime factors and so is an interval of length disjoint from and since was arbitrary we conclude that in not syndetic.
We now generalize proposition 4:
Proof: This proof is practically the same as the proof of proposition 4. Let . Applying the Chinese remainder theorem we can find, some such that , for all , where again is the prime number. Then is divisible by , so in particular is not in . Thus the interval is disjoint from and so is not syndetic. l
So far we have considered sets of integers with restrictions in the prime factorization. Using the fundamental theorem of arithmetic we can identify each with the exponents of its prime factorization. More precisely, let be the set of sequences of non-negative integers with only finitely many positive entries. Thus we can map by (where again is the -th prime). Call to that map. The fundamental theorem of arithmetic tells us that is bijective (furthermore this map is a semi-group isomorphism, where is equipped with the multiplication).
Thus is the set of sequences with only one non-zero entry and is the set of sequences with only non-zero entries. On the other hand is the set of sequences with all entries less or equal to and is the set of sequences with all entries less or equal to .
We can consider weaker restrictions, for instance consider the set of all sequences with no entry equal to . Is syndetic? Or more generally, for each , is the set syndetic (where is the set of all sequences with no entry equal to )? 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 be any function. Let be the set of all sequences such that, for each , the -th coordinate is not . Then is not syndetic.
In fact, the theorem is true even when we just impose restrictions in some infinite subset of primes. Of course if (for instance, if has more restrictions than ) then is also not syndetic. The proof is similar to that of proposition 6 but a clever adjustment is needed.
Proof: For a fixed , we can apply the Chinese remainder theorem to find such that, for each , we have . Thus we can write . But we need that in order to have .
Let . Note that we have for any , so if we add a multiple of to we still have the same congruences. Now we just have to find the right multiple of to add. Let . Then , and more generally, for each we have . We want to make not multiple of , but we want this to happen for all , while is the same. We can make better, we will require that for all .
Note that is not multiple of , so there is an inverse for , i.e. . Then is equivalent to . We can now apply again the Chinese remainder theorem to find such , and as we saw, the numbers for are not in .
One could also think on generalizing proposition 5 this situation: instead of considering the sequences on which don’t have more than non-zero entries, we can consider the sequences on which don’t have exactly non-zero entries. Is the correspondent (by ) subset of syndetic? The answer is no (and the proof quite simple).
Proposition 8 Let and let be the set of all sequences with exactly non-zero entries. Let be the set of all sequences that don’t have exactly nonzero entries. Then is syndetic.
Proof: I thank Ali Adali for showing me a proof of this fact. Let be the product of the first primes. Then all the multiples of are in and so is syndetic.
As we saw, if we forbid numbers with more than prime divisors we kill syndeticity (proposition 5), but if we forbid numbers with exactly prime divisors we don’t, the simple reason being that there are numbers with no multiple with exactly divisors. A new question can be asked now, namely, for an infinite set , is the set of numbers such that the number of prime divisors of is not in syndetic? More precisely:
Question Let . Let be the set of sequences with number of non-zero components in . Which conditions on make syndetic? In particular, if is infinite can we guarantee that 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 be a set which doesn’t contain arbitrarily long geometric progressions. Is such necessarily not syndetic? Even if we just require to be such that for all and we have , the answer is not known.