Define $F(t)=\ln(t+1)$ for $t\geq 0$.

For each sequence of integers $ s=s_0s_1s_2...\in \mathbb Z^\omega$ define $$t^*_{ s}=\sup_{n\geq 0}F^{n}(|s_n|)$$ where $F^{n}$ is the $n$-fold composition of $F$.

Let $\sigma$ be the shift mapping on $\mathbb Z^\omega$; so $\sigma(s_0s_1s_2...)=s_1s_2s_3...$., and let $\sigma^k$ be the $k$-fold composition of $\sigma$.

Is the set $$\mathbb S:=\{s\in \mathbb Z^\omega:t^*_{\sigma^k(s)}\to\infty \text{ as }k\to\infty\}$$ an $F_{\sigma\delta}$-subset of $\mathbb Z ^\omega$? Assume $\mathbb Z$ is given the discrete topology and $\mathbb Z ^\omega$ has the product topology.

A positive answer to this question would imply that a certain set in complex dynamics is an Erdős space factor. See this paper, Remark 5.3 in particular, for more about this problem. Essentially a space $E$ is an Erdős space factor if $E\times \mathfrak E\simeq \mathfrak E$ where $\mathfrak E$ is the rational Hilbert space.

EDIT 10/26/20: I proved that the space from complex dynamics (mentioned above) is not an Erdős space factor, answering a question by Dijkstra and van Mill: link to paper. This result implies in particular that the set $\mathbb S$ is not $F_{\sigma\delta}$.

  • $\begingroup$ It seems that you obtain $F_{\sigma\delta}$ writing down the definition of your set: $\bigcap_{n\in\mathbb N}\bigcup_{k\in\mathbb N}\bigcap_{m\ge k}\{s\in\mathbb Z^\omega:s(m)\ge n\}$. $\endgroup$ – Taras Banakh Jul 12 '20 at 9:48
  • $\begingroup$ @TarasBanakh Your set is a proper subset of the one I wrote. For instance I believe the sequence $0,1,0,2,0,3,0,4...$ belongs to my set but not yours. $\endgroup$ – D.S. Lipham Jul 12 '20 at 16:14
  • $\begingroup$ The sequence of $t^*$'s for $0,1,0,2,...$ would be above the sequence $F^{1}(1), 1, F^{1}(2), 2, F^{1}(3),3, …$ which goes to $\infty$ $\endgroup$ – D.S. Lipham Jul 12 '20 at 16:41
  • $\begingroup$ @TarasBanakh I wonder if $t^*\to\infty$ is the same as saying that a subsequence of s goes to infinity? In this case, my set is probably not $F_{\sigma\delta}$. Assuming these sets are equal, how would you prove that? By the way, I have shown that the original set is both $F_{\sigma\delta\sigma}$ and $G_{\delta\sigma\delta}$. $\endgroup$ – D.S. Lipham Jul 12 '20 at 16:56
  • 1
    $\begingroup$ Definitely this is not the same as being unbounded, as suggested in the penultimate comment, just insert sufficiently long zero runs in the sequence $\mathbb{N}$. $\endgroup$ – Ville Salo Jul 12 '20 at 20:34

Here's what I had in mind. Consider a $\Sigma^0_3$-set $$ T = \bigcup_{n \in \mathbb{N}} \bigcap_{m \in \mathbb{N}} \bigcup_{k \in \mathbb{N}} C_{n,m,k}. $$ where each $C_{n,m,k} \subset 2^\mathbb{N}$ is clopen. We show that there is a continuous map $f : 2^{\mathbb{N}} \to \mathbb{Z}^\omega$ such that $f^{-1}(S) = T$ where $$ S = \{s \in \mathbb{Z}^\omega \;:\; t^*_{\sigma^k(s)} \rightarrow \infty \text{ as } k \rightarrow \infty \} $$ is the set from the question. This proves that $S$ is not $F_{\sigma \delta}$, since that would imply all $\Sigma^0_3$ sets $T$ in $2^\mathbb{N}$ are $\Pi^0_3$.

You are at the concert. On the stage, there is a conductor and $\omega$ many cellists. The conductor is reading a point $x \in 2^\mathbb{N}$. Whenever she notices $x \in C_{n,m,k}$, the conductor cues the $n$th cellist to play the note $m$, assuming it hasn't been played before, and $n$ has played all the notes before $m$. Only one cellist plays at a time, there is a rest when all the events $x \in C_{n,m,k}$ visible so far are exhausted, and if $m$ cannot be played yet because previous notes have not been played, the conductor makes a note of it and it is played once they have. As you listen to these rising scales, you note that $x \in T$ if and only if one of the cellists plays the entire scale $\mathbb{N}$.

From this continuously revealed information you will construct the continuous function $f : 2^\mathbb{N} \to \mathbb{Z}^\omega$. The construction for $f(t) = s$ is thusly. We go through $\ell = 0, 1, ...$ and by default we just set $s_\ell = 100$ for all $\ell$. Whenever the $n$th cellist plays, we do as follows:

  • if one of the cellists $n' < n$ has played between the last time the $n$th cellist played (or the beginning of time if $n$ hasn't played anything) and the present time, then we set $s_{\ell} = 100$. As long as no cellist $n' < n$ plays again we ensure that also $t^*_{\sigma^\ell(s)} = 100$.
  • otherwise (if no cellist $n' < n$ has played between), then if the last time $n$ played we set $s_{\ell'} = 100+h$ then we now set such a high value at $s_\ell$ that we have $\lfloor t^*_{\sigma^{\ell'+1}(s)} \rfloor \geq 100+h+1$. Namely, set $s_\ell = \lceil \text{pexp}^{\ell-\ell'-1}(100+h+1) \rceil$ where $\text{pexp}(x) = \exp(x) - 1$. Note that in fact we get precisely $\lfloor t^*_{\sigma^{\ell'+1}(s)} \rfloor = 100+h+1$ because of basic properties of $\text{pexp}$. It also follows, because $\log (103 + h) < 100 + h$ and by induction, that we do not disturb any of the ensured values $t^*_{\sigma^\ell(s)} = 100$ for any $n' \leq n$: those were ensured before setting the value of $s_{\ell'}$.

Now suppose indeed $t \in T$, and some cellist plays infinitely many times. Then if the $n$th cellist is the first cellist that does, then the first item applies only finitely many times for $n$, and after that whenever we set $s_{\ell} = \text{pexp}^{\ell-\ell'-1}(100+h+1)$ we actually set $t^*_{\sigma^{\ell''}(s)} \geq 100+h+1$ for all $\ell'' \in [\ell'+1, \ell]$. So since $n$ plays infinitely many times, actually $t^*_{\sigma^{\ell''}(s)} \rightarrow \infty$ as $\ell'' \rightarrow \infty$.

Suppose then $t \notin T$. If the song is finite, obviously $\lim_\ell t^*_{\sigma^{\ell}(s)} = 100$. Otherwise, whenever $n$ plays for the last time, we have a new ensured value at which $t^*_{\sigma^{\ell}(s)} = 100$, thus $\liminf_\ell t^*_{\sigma^{\ell}(s)} \leq 100$.

An observation:

  • As far as I can tell all we are using is that $F$ is monotone, $F(h + 2) < h$ for $h \geq 100$ and that $\lfloor F^n(h) \rfloor \rightarrow \infty$ as $h \rightarrow \infty$ for any $n$, and the values range over $[100, \infty) \cap \mathbb{N}$. And I guess $100$ can be replaced by some other number (probably $1$ or $2$ for your function). Maybe I missed some axioms.


Your set is not $G_{\delta \sigma}$ either. Namely, any $\Pi^0_3$ set $$ T' = \bigcap_{n \in \mathbb{N}} \bigcup_{m \in \mathbb{N}} \bigcap_{k \in \mathbb{N}} D_{n,m,k} $$ clearly continuously reduces to $$ S' = \{s \in \mathbb{Z}^\omega \;:\; \lim_i s_i = \infty\}. $$ To see this, for each $n$ separately go through $(m,k)$ in lexicographical order, advancing to the next $m$ when you observe the point is not in $D_{n,m,k}$. On step $\ell$, output $n$ if $m$ is updated for $n$, otherwise output $\ell$. This way you construct $g(t) \in \mathbb{Z}^\omega$ for $t \in 2^\mathbb{N}$.

Clearly $t \in T'$ if and only if $m$ is updated for each $n$ only finitely many times. If $m$ is updated infinitely many times for $n$, then the limit of $g(t)$ is at most $n$, while if $m$ is updated finitely many times for each $n = 0, 1, ..., N$ then $g(t)$ stays above $N$ from some point on.

Now it's easy to further reduce to your set, observing that if a sequence satisfies $|s_{i+1} - s_i| \in \{-1,0,1\}$ and $s_i \geq 100$ for all $i$, then $s \in S' \iff s \in S$. Just replace all jumps by arithmetic progressions.

By taking the coordinatewise minimum of this process and the above, I suppose we have

Every set of the form $A \cap B$ for $A \in \Sigma^0_3$ and $B \in \Pi^0_3$ continuously reduces to your set.

But I don't know if your set can be written as $C \cap D$ for $C \in F_{\sigma \delta}$ and $D \in G_{\delta \sigma}$.

  • $\begingroup$ Thank you for your answers! I will try to understand soon. $\endgroup$ – D.S. Lipham Jul 13 '20 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.