When are a set and its complement both syndetic?

168 Views Asked by At

Let $G$ be a semigroup. A subset $S\subseteq G$ is syndetic if $G$ is covered by finitely many translates of $S$: i.e. there are elements $g_1,\ldots,g_m\in G$ such that $G=Sg_1\cup \cdots\cup Sg_m$.

If $G$ is a group $H$ is a subgroup of finite index then of course any coset $Hg$ is syndetic. Any set containing such $Hg$ would also be syndetic, since the family of syndetic sets is upper-closed.

Syndetic sets are viewed as "combinatorially large" sets.


Connection to dynamics

Here are two theorems connecting this "combinatorial large"-ness to return sets in dynamical systems. They concern orbits $Gx=\{gx : g\in G\}$ intersecting with open/closed sets.

Theorem 1. If $G$ is a group acting on a compact space $X$, then for any open set $U$ and point $x_0\in X$, the return set $N:=\{g\in G: gx_0\in U\}$ is syndetic.

Theorem 2. If $\varphi:X\rightarrow X$ is a continuous mapping of a noetherian space $X$, then for any closed set $C$ and point $x_0\in X$, the return set $M:=\{n\geq 0: \varphi^n(x_0)\in C\}$ either has zero density or contains an infinite arithmetic progression.

(A noetherian space is one satisfying the ascending chain condition on open sets. These are always compact, but never Hausdorff unless they are finite and discrete. Algebraic varieties are important examples.)

Theorem 1 is about open sets while Theorem 2 is about closed sets. So we can combine them: if $U=X\setminus C$, we get $N=\mathbb{N}_0\setminus M$.

If we view an arithmetic progression as a coset of a subsemigroup of $(\mathbb{N}_0,+)$, then we can view the combinations of Theorem 1 and 2 as saying: $N$ is syndetic, and its complement is either sparse or contains a coset of a subsemigroup.

The first alternative makes sense: "$N$ is large and its complement is thin." But the second one says "$N$ is large, but so is its complement." One example I can think of is when $G=\mathbb{N}_0$ and $N$ is the set of even numbers. Then the complement the odd numbers, which is a coset of a subsemigroup of finite index.

Is this the only way a set and its complement can both by syndetic?


This leads me to the following purely combinatorial question.

Question. Suppose that $S$ and and its complement $S^c=G\setminus S$ are both syndetic (in $G$). Must $S$ contain a coset of a subsemigroup of $G$?

Some common terminology: $S$ is thick if its complement $S^c$ is not syndetic. So in the above question we are trying to show that if $S$ is syndetic but not thick, then $S$ contains a translate of a subsemigroup.

1

There are 1 best solutions below

1
On BEST ANSWER

The Thue-Morse sequence $0110100110010110\dotsc$ gives a counterexample. Denoting the $n$th term of this sequence by $a_n$, let $S$ be the set of all those indices $n$ with $a_n=0$; thus, the complement $S^c$ is the set of those $n$ with $a_n=1$. Both $S$ and $S^c$ are syndetic, as the original sequence does not contain any run of three or more consecutive elements. On the other hand, neither $S$ nor $S^c$ contains a coset, as the Thue-Morse sequence is known to show cancellation on arithmetic progressions.