# Prime number theorem for regular Toeplitz subshifts

Krzysztof Frączek  Faculty of Mathematics and Computer Science, Nicolaus
Copernicus University, ul. Chopina 12/18, 87-100 Toruń, Poland
<EMAIL_ADDRESS>,  Adam Kanigowski  Department of Mathematics, University
of Maryland, 4176 Campus Drive, William E. Kirwan Hall, College Park, MD
20742-4015, USA<EMAIL_ADDRESS>and  Mariusz Lemańczyk  Faculty of
Mathematics and Computer Science, Nicolaus Copernicus University, ul. Chopina
12/18, 87-100 Toruń, Poland<EMAIL_ADDRESS>
###### Abstract.

We prove that neither a prime nor a semiprime number theorem holds in the
class of regular Toeplitz subshifts but when the regularity (with respect to
the periodic structure) is strengthened to the regularity with respect to the
values of the Euler totient function of the periods then they both do hold.

###### Key words and phrases:

prime number theorem, Toeplitz systems, semi-prime numbers, non-conventional
ergodic theorems

###### 2000 Mathematics Subject Classification:

37B10, 37A45, 11N05, 11N13

Research supported by Narodowe Centrum Nauki grant 2019/33/B/ST1/00364.

##  1\. Introduction

Given a topological dynamical system $(X,T)$, where $T$ is a homeomorphism of
a compact metric space $X$, one says that a prime number theorem (PNT) holds
if the limit

(1) $\lim_{N\to\infty}\frac{1}{\pi(N)}\sum_{p<N}f(T^{p}x)$

($p$ stands always for a prime number) exists for each $x\in X$, an arbitrary
$f\in C(X)$ and $\pi(N)$ denotes the number of primes up to $N$. In fact,
then, via Riesz theorem, for all $f\in C(X)$, we have

$\lim_{N\to\infty}\frac{1}{\pi(N)}\sum_{p<N}f(T^{p}x)=\int_{X}f\,d\nu_{x},$

for a probability (Borel) measure $\nu_{x}$ on $X$, where $\nu_{x}$ depends
only on $x\in X$.

Let us first consider the cyclic case: $X={\mathbb{Z}}/k{\mathbb{Z}}$ and
$Tx=x+1$. Fix $x\in X$ and notice that (1) indeed holds by the classical prime
number theorem in arithmetic progressions, where $\nu_{x}$ is the uniform
probability measure on the “coset” $\\{a<k:\>(a,k)=1\\}+x$. Hence, a PNT holds
in cyclic (hence, in finite) systems.

If instead of cyclic systems we consider the procyclic case, that is, an
odometer system $(H,T)$:

$H={\rm
liminv}_{t\to\infty}\,{\mathbb{Z}}/n_{t}{\mathbb{Z}},\;Tx=x+(1,1,\ldots)$

(here $n_{t}|n_{t+1}$ for $t\geq 0$) then a PNT still holds, but a reason for
it is that, compared to the finite case, we did not add too many continuous
functions. Indeed, in the odometer, there is a natural partition
$D^{t}=(D^{t}_{0},\ldots,D^{t}_{n_{t}-1})$, $TD^{t}_{i}=D^{t}_{i+1}$ mod
$n_{t}$, consisting of closed (hence clopen) sets, having the same diameter
(as $T$ is an isometry) and the diameter is going to 0 when $t\to\infty$
(reflecting the fact that the levels of the towers $D^{t}$ form a basis of
topology on $H$). Hence, each $f\in C(H)$ can be approximated uniformly by
functions which are constant on the levels of towers $D^{t}$ (it is not hard
to see that each character of the group $H$ is constant on the levels of the
towers $D^{t}$ for $t$ sufficiently large) and a PNT holds because it does in
the finite case.

We will deal with extensions of odometers but before we describe our results
toward PNT, let us first discuss basic topological properties of odometers.
These are zero entropy topological systems which are minimal (all $T$-orbits
are dense) and uniquely ergodic (there is only one $T$-invariant measure -
Haar measure in this case). But not so much can be said about a PNT for a
general uniquely ergodic system: while (1) holds a.e. with respect to the
unique invariant measure [3], [22], one can easily construct a counterexample
to the validity of (1) for all $x\in X$. Indeed, denote by ${\mathbb{P}}$ the
set of prime numbers and consider the left shift $S$ on
$\\{0,1\\}^{{\mathbb{Z}}}$ and the subshift
$(X_{{\mathbf{1}}_{{\mathbb{P}}\cup-{\mathbb{P}}}},S)$ obtained by the orbit
closure of the characteristic function
${\mathbf{1}}_{{\mathbb{P}}\cup-{\mathbb{P}}}$ of the “symmetrized” primes. It
has a unique invariant measure (which is the Dirac measure at the fixed point
$\ldots 0.00\ldots$) and a PNT fails in it (see e.g. [8] for details). Now,
this particular uniquely ergodic model of the one-point system implies
paradoxically that each ergodic dynamical system has a uniquely ergodic model
$(X,T)$ 111Recall that the Jewett-Kreiger theorem says the following: Suppose
$(Z,\kappa,R)$ is an ergodic measure-theoretic dynamical system. Then there
exists a uniquely ergodic (even strictly ergodic, that is, additionally
minimal) topological system $(Y,S)$ with the unique invariant measure $\nu$
such that $(Z,\kappa,R)$ and $(Y,\nu,S)$ are measure-theoretically isomorphic.
in which a PNT does not hold. To see this, take any uniquely ergodic model
$(Y,\nu,R)$ of the given measure-theoretic dynamical system. Since the one-
point system is (Furstenberg) disjoint with any other system, the product
system $(X_{{\mathbf{1}}_{{\mathbb{P}}\cup-{\mathbb{P}}}}\times Y,S\times R)$
is still uniquely ergodic, with the unique invariant measure $\delta_{\ldots
0.00\ldots}\otimes\nu$. It is not hard to see that the product measure-
theoretic system is still measure-theoretically isomorphic to the original
system. Since the new system has
$(X_{{\mathbf{1}}_{{\mathbb{P}}\cup-{\mathbb{P}}}},S)$ as its topological
factor, a PNT does not hold in
$(X_{{\mathbf{1}}_{{\mathbb{P}}\cup-{\mathbb{P}}}}\times Y,S\times R)$.222To
illustrate this, consider an irrational $R_{\alpha}$ on ${\mathbb{T}}$ for
which a PNT holds because of Vinogradov’s theorem (prime “orbits” are
equidistributed). However, our observation shows that there is a uniquely
ergodic model of $R_{\alpha}$ in which the eigenfunctions are still continuous
but a PNT fails, that is, some of the prime “orbits” are not equidistributed.
Hence, if we think about a necessary condition for a PNT to hold, it looks
reasonable to add the minimality assumption to avoid a problem of ,,exotic”
orbits on which PNT does not hold (we also recall that a uniquely ergodic
system has a unique subsystem which is strictly ergodic). In this class
however still one can produce counterexample to a PNT, see [18] for the first
symbolic (counter)examples (though the entropy is not determined in examples
in [18]), or more recent non-symbolic (counter)examples from [13]. On the
other hand, we have quite a few classes in which a PNT holds, including
systems of algebraic origin [11], [21], symbolic systems [4], [10], [15], [16]
or recently [13] in the category of smooth systems, where a PNT has been
proved in the class of analytic Anzai skew products. Finding a sufficient
dynamical condition for a PNT to hold, postulated a few years ago by P. Sarnak
[20] seems to be an important and difficult task in dynamics, however we
rather expect the following:

Working Conjecture: Each ergodic and aperiodic measure-theoretic dynamical
system has a strictly ergodic model in which a PNT fails

which, if true, makes Sarnak’s postulate even harder to realize. The present
paper should be viewed as introductory steps in trying to understand the
conjecture.

A PNT can be reformulated as the existence of a limit of
$\frac{1}{N}\sum_{n<N}f(T^{n}x)\Lambda(n)$, where $\Lambda$ stands for the von
Mangoldt function: $\Lambda(p^{\ell})=\log p$ for $\ell\geq 1$ and 0
otherwise. In the last decade, the PNT problem in dynamics goes in parallel
with a related to it Sarnak’s conjecture [19] on Möbius orthogonality:

(2) $\lim_{N\to\infty}\frac{1}{N}\sum_{n<N}f(T^{n}x)\boldsymbol{\mu}(n)=0$

for each $x\in X$, $f\in C(X)$ in each zero entropy dynamical system $(X,T)$
($\boldsymbol{\mu}$ stands for the Möbius function: $\boldsymbol{\mu}(1)=1$,
$\boldsymbol{\mu}(p_{1}\cdot\ldots\cdot p_{k})=(-1)^{k}$ for different primes
$p_{1},\ldots,p_{k}$, and $\boldsymbol{\mu}(n)=0$ for the remaining
$n\in{\mathbb{N}}$). Here, the class of objects for which we expect the
positive answer is precisely defined. In fact, in quite a few cases: cf. [4],
[5], [9], [10], [11] [15], [16], one can observe the following principle: once
we can prove Sarnak’s conjecture for $(X,T)$ with a “sufficient” speed of
convergence to zero in (2) then a PNT holds in $(X,T)$.

With all the above in mind we come back to extensions of odometers we intend
to study. We stay in the zero entropy category of systems and we assume
minimality. Further, we assume that the systems are almost 1-1 extensions of
odometers.333If $(H,T)$ is a factor of $(X,S)$ via $\pi:X\to H$, then $(X,S)$
is called an almost 1-1 extension of $(H,T)$ if there is a point $h\in H$ such
that $|\pi^{-1}(h)|=1$; in fact, in this case the set of points with singleton
fibers is $G_{\delta}$ and dense. We also assume that our systems are
symbolic.444We recall that each zero entropy system has an extension which is
symbolic [2], and clearly if a PNT holds for a system, it does for a factor.
All these natural assumptions determine however a very precise class of
topological systems, namely Toeplitz subshifts $(X_{x},S)$, where $x$ is a
Toeplitz sequence over a finite alphabet $\mathcal{A}$, see Downarowicz’s
survey [7], Section 7. That is, $x\in\mathcal{A}^{{\mathbb{Z}}}$ and for
$a\in{\mathbb{Z}}$ there is $\ell\in{\mathbb{N}}$ such that
$x(a)=x({a+k\ell})$ for each $k\in{\mathbb{Z}}$ and $X_{x}$ stands for the set
of all $y\in\mathcal{A}^{{\mathbb{Z}}}$ whose each subblock appears also in
$x$. One shows then that there is a sequence $n_{t}|n_{t+1}$ such that if
${\rm Per}_{n_{t}}(x):=\\{a\in{\mathbb{Z}}:\>x(a)=x(a+kn_{t})\text{ for each
}k\in{\mathbb{Z}}\\}$ then

(3) $\bigcup_{t\geq 0}{\rm Per}_{n_{t}}(x)={\mathbb{Z}}.$

Moreover, there is a natural continuous factor map $\pi:X_{x}\to H$, where $H$
stands for the odometer determined by $(n_{t})$. In fact, we will still
restrict the class of Toeplitz subshifts to so called regular Toeplitz
subshifts, whose formal definition is that the density of
$\bigcup_{t=0}^{M}{\rm Per}_{n_{t}}(x)$ is going to 1. Regular Toeplitz
subshifts are zero entropy strictly ergodic systems, measure-theoretically
isomorphic to rotations given by the maximal equicontinuous factors. Although
in [7] there are four other equivalent conditions for regularity (see Theorem
13.1 in [7]), we will choose a different path. Namely, first notice that since
$\pi:X_{x}\to H$ is a continuous and equivariant surjection,

$E^{t}:=\pi^{-1}(D^{t})=(E^{t}_{0},\ldots,E^{t}_{n_{t}-1})\text{ with
}E^{t}_{j}=\pi^{-1}(D^{t}_{j})$

is an $S$-tower of height $n_{t}$ whose level are closed (hence clopen). By
the minimality of $(X_{x},S)$ there is a unique tower with clopen levels and
of fixed height. Let us consider on $\mathcal{A}^{\mathbb{Z}}$ a metric
inducing the product topology being given by

$d(x,y)=2^{-\inf\\{|n|:x(n)\neq y(n)\\}}.$

The diameters of the levels of towers $E^{t}$ do not converge to zero, unless
$x$ is periodic. Moreover, the diameters of different levels are in general
different as the shift $S$ is not an isometry. Let us consider the diameter of
the tower $E^{t}$ given by:

$\delta(E^{t}):=\sum_{0\leq j<n_{t}}\operatorname{diam}(E_{j}^{t}).$

It is not hard to see (see Appendix A) that the regularity of a Toeplitz
sequence is equivalent to

(4) $\lim_{t\to\infty}\frac{\delta(E^{t})}{n_{t}}=0.$

It is also not hard to see that this property does not depend on the choice of
$(n_{t})$ satisfying (3). We recall that the Möbius orthogonality of subshifts
given by regular Toeplitz sequences has been proved in [1]. Here are two first
results of the paper proved in Section 2 and Section 4, respectively:

######  Theorem A.

A PNT does not hold in the class of minimal almost 1-1 symbolic extensions
satisfying (4) of odometers. That is, a PNT need not hold in a strictly
ergodic subshift determined by a regular Toeplitz sequence.

######  Theorem B.

A PNT holds in the class of minimal almost 1-1 symbolic extensions of
odometers in which (4) holds with a speed:

(5) $\lim_{t\to\infty}\frac{\delta(E^{t})}{\varphi(n_{t})}=0,$

where $\varphi$ denotes the Euler totient function.

As for all Toeplitz dynamical systems constructed in the proof of Theorem A we
have

$0<\liminf_{t\to\infty}\frac{\delta(E^{t})}{\varphi(n_{t})}\leq\limsup_{t\to\infty}\frac{\delta(E^{t})}{\varphi(n_{t})}<+\infty,$

the condition (5) in Theorem B is optimal to have a PNT.

We then turn our attention to a semi-prime number theorem (SPNT) which is much
less explored than the PNT case and which, for the first time in dynamics, is
studied in [14] (for some smooth Anzai skew products). In Section 3 and
Section 5 we provide sketches of proofs of the exact analogues of Theorems A
and B for an SPNT for regular Toeplitz subshifts.

In Section 6.1 we prove a new non-conventional ergodic theorem:

$\lim_{N\to\infty}\frac{1}{N}\sum_{n\leq N}f(S^{P(n)}x)\ \text{ exists}$

for monic polynomials $P$ with positive integer coefficients for all symbolic
minimal almost 1-1 extensions of odometers with a modified condition (5). In
Section 6.2 we provide a regular Toeplitz subshift which does not satisfy the
non-conventional ergodic theorem for squares but it satisfies a PNT.

While Theorem A confirms Working Conjecture for a subclass of odometers, we
have been unable to confirm it for the whole class of odometers. Confirming
Working Conjecture for the class of automorphisms with discrete spectrum seems
to be the first step toward a possible general statement. In Appendix B, we
provide a simple argument showing that in the classical symbolic models of
irrational rotations given by Sturmian sequences, a PNT holds. The Sturmian
systems are strictly ergodic and are almost 1-1 extensions of irrational
rotations.

##  2\. Regular Toeplitz subshifts which do not satisfy PNT (proof of Theorem
A)

For all $K,n\in{\mathbb{N}}$ and $a\in{\mathbb{Z}}$ let

$\pi(K;n,a)=\\{1\leq p\leq K:p\in\mathbb{P},p=a\\!\mod n\\}.$

######  Theorem 2.1 (Dirichlet).

For any natural $n$ and any integer $a$ with $(a,n)=1$ we have

$\lim_{K\to\infty}\frac{\pi(K;n,a)}{\frac{\pi(K)}{\varphi(n)}}=1.$

We construct a Toeplitz sequence $x\in\\{0,1\\}^{{\mathbb{Z}}}$ with the
period structure $(n_{t})$:

(6) $n_{t+1}=k_{t+1}n_{t},\;(k_{t+1},n_{t})=1$

for each $t\geq 1$. We will show that for this $x$:

$\lim_{t\to\infty}\frac{1}{\pi(n_{t})}\sum_{p<n_{t}}F(S^{p}x)\text{ does not
exist,}$

where $F(y)=(-1)^{y(0)}$. At stage $t$, $x$ is approximated by the infinite
concatenation of $x_{t}[0,n_{t}-1]\in\\{0,1,?\\}^{n_{t}}$ (that is, we see a
periodic sequence of $0,1,?$ with period $n_{t}$). Successive “?” will be
filled in in the next steps of construction of $x$. We require that:

(7) $\displaystyle\frac{\varphi(n_{t})}{n_{t}}\leq\frac{1}{2^{t}},$ (8)
$\displaystyle\\{0\leq i<n_{t}:\>x_{t}(i)=?\\}\subset\\{0\leq
j<n_{t}:(j,n_{t})=1\\},$ (9) $\displaystyle\\#\\{0\leq
i<n_{t}:\>x_{t}(i)=?\\}\geq\Big{(}1-\sum_{l=1}^{t}\tfrac{1}{100^{l}}\Big{)}\varphi(n_{t}),$
(10) $\displaystyle\\#\\{p<n_{t}:\>x_{t}(p)=?\\}\geq\frac{1}{2}\pi(n_{t}).$

We choose $k_{t+1}$ satisfying (6) and:

(11) $\displaystyle\frac{\varphi(k_{t+1})}{k_{t+1}}\leq\frac{1}{2},~{}$ (12)
$\displaystyle\varphi(k_{t+1})\geq 100^{t+1},$ (13) $\displaystyle 8\log
n_{t+1}\leq\pi(n_{t+1}),\quad 8\pi(n_{t})\leq\pi(n_{t+1})$

and for each $0<a<n_{t}$, $(a,n_{t})=1$, we have

(14)
$\\#\big{(}\\{a+jn_{t}:\>j=0,\ldots,k_{t+1}\\}\cap{\mathbb{P}}\big{)}=\pi(n_{t+1};n_{t},a)\leq
2\frac{\pi(n_{t+1})}{\varphi(n_{t})}.$

The latter we obtain from the Dirichlet theorem (remembering that $n_{t}$ is
fixed, so the number of $a$ is known, we can obtain the accuracy as good as we
want by taking $k_{t+1}$ sufficiently large).

We need two simple observations:

(15) $\\{0\leq
k<n_{t+1}:\>(k,n_{t+1})=1\\}\subset\bigcup_{\begin{subarray}{c}0\leq
a<n_{t}\\\ (a,n_{t})=1\end{subarray}}\\{a+jn_{t}:\>j=0,\ldots,k_{t+1}-1\\}.$

######  Lemma 2.2.

For every $0\leq a<n_{t}$ with $(a,n_{t})=1$, we have

$\\#\\{0\leq j<k_{t+1}:(a+jn_{t},n_{t+1})=1\\}=\varphi(k_{t+1}).$

###### Proof.

First note that $(a+jn_{t},n_{t+1})=1$ iff $(a+jn_{t},k_{t+1})=1$. Indeed,
assume that $(a+jn_{t},k_{t+1})=1$. If for some prime $p$ we have
$p|(a+jn_{t})$ and $p|n_{t+1}=n_{t}k_{t+1}$, then $p|k_{t+1}$. Otherwise, we
have $p|n_{t}$, so $p|a$. As $(a,n_{t})=1$, this gives a contradiction. Thus
$(a+jn_{t},k_{t+1})=1$ implies $(a+jn_{t},n_{t+1})=1$. The opposite
implication is obvious. Thus

$\\{0\leq j<k_{t+1}:(a+jn_{t},n_{t+1})=1\\}=\\{0\leq
j<k_{t+1}:(a+jn_{t},k_{t+1})=1\\}.$

Let us consider the affine map

${\mathbb{Z}}/k_{t+1}{\mathbb{Z}}\ni j\stackrel{{\scriptstyle
A}}{{\mapsto}}a+jn_{t}\in{\mathbb{Z}}/k_{t+1}{\mathbb{Z}}.$

If $J:=\\{0\leq\ell<k_{t+1}:\>(\ell,k_{t+1})=1\\}$ then

$\\{0\leq j<k_{t+1}:\>(a+jn_{t},k_{t+1})=1\\}=A^{-1}(J).$

Since $(n_{t},k_{t+1})=1$, the map $A$ is a bijection. It follows that

$\displaystyle\\#\\{0\leq j<k_{t+1}:(a+jn_{t},k_{t+1})=1\\}$
$\displaystyle=\\#\\{0\leq\ell<k_{t+1}:(\ell,k_{t+1})=1\\}$
$\displaystyle=\varphi(k_{t+1}),$

which completes the proof.

We need to describe now which and how we fill "?" in $x_{t+1}[0,n_{t+1}-1]$.
This block is divided into $k_{t+1}$ subblocks

$\underbrace{x_{t}[0,n_{t}-1]x_{t}[0,n_{t}-1]\ldots
x_{t}[0,n_{t}-1]}_{k_{t+1}}.$

We fill in all "?" in the first block $x_{t}[0,n_{t}-1]$ in such a way to
“destroy” a PNT for the time $n_{t}$, namely

$\displaystyle\frac{1}{\pi(n_{t})}$
$\displaystyle\sum_{p<n_{t}}F(S^{p}x)=\frac{1}{\pi(n_{t})}\sum_{\begin{subarray}{c}p<n_{t}\\\
p|n_{t}\end{subarray}}(-1)^{x(p)}+$
$\displaystyle\frac{1}{\pi(n_{t})}\Big{(}\sum_{\begin{subarray}{c}p<n_{t}\\\
(p,n_{t})=1\\\ x_{t}(p)=0\end{subarray}}1-\sum_{\begin{subarray}{c}p<n_{t}\\\
(p,n_{t})=1\\\ x_{t}(p)=1\end{subarray}}1+\sum_{\begin{subarray}{c}p<n_{t}\\\
(p,n_{t})=1\\\ x_{t}(p)=?\end{subarray}}(-1)^{x(p)}\Big{)}.$

As the number of the primes dividing $n_{t}$ is bounded by $\log n_{t}$, it is
negligible compared to $\pi(n_{t})=n_{t}/\log n_{t}$. It follows that

$\Big{|}\frac{1}{\pi(n_{t})}\sum_{\begin{subarray}{c}p<n_{t}\\\
p|n_{t}\end{subarray}}(-1)^{x(p)}\Big{|}\leq\frac{\log
n_{t}}{\pi(n_{t})}=o(1),$

so the first summand does not affect the asymptotic of the averages in (1).
Since the number of $p$ in the last summand is at least
$\frac{1}{2}\pi(n_{t})$ in view of (10), we can fill in $x_{t+1}$ at places
$\\{p<n_{t}:(p,n_{t})=1,\ x_{t}(p)=?\\}$ to obtain the sum completely
different that the known number which we had from stage $t-1$.

We fill in (in an arbitrary way) all remaining places between $0$ and
$n_{t}-1$ and all places $a+jn_{t}$ for $0\leq j<k_{t+1}$ such that this
number is not coprime with $n_{t+1}$, so that (8) will be satisfied at stage
$t+1$. We must remember that for certain $0<a<n_{t}$ coprime to $n_{t}$,
$x_{t}(a)$ was already defined at previous stages, so along the corresponding
arithmetic progressions $a+jn_{t}$, $0\leq j<k_{t+1}$, these places are also
filled in previously. On the other side, if $x_{t+1}(a+jn_{t})\neq?$ (that is,
$x_{t+1}(a+jn_{t})=0$ or $x_{t+1}(a+jn_{t})=1$) and $(a+jn_{t},n_{t+1})=1$ for
some $0<j<k_{t+1}$ then $x_{t}(a)\neq?$. In view of (15), it gives

$\displaystyle\\{$ $\displaystyle 0\leq
i<n_{t+1}:(i,n_{t+1})=1,x_{t+1}(i)\neq?\\}$
$\displaystyle\subset\\{0<a<n_{t}:(a,n_{t})=1,x_{t+1}(a)\neq?\\}$
$\displaystyle\quad\cup\bigcup_{\begin{subarray}{c}0\leq a<n_{t}\\\
(a,n_{t})=1\\\
x_{t}(a)\neq?\end{subarray}}\\{a+jn_{t}:0<j<k_{t+1},\>(a+jn_{t},n_{t+1})=1\\}.$

By (8), Lemma 2.2, (9) and (12), it follows that

$\displaystyle\\#$ $\displaystyle\\{0\leq
i<n_{t+1}:(i,n_{t+1})=1,x_{t+1}(i)\neq?\\}$
$\displaystyle\leq\varphi(n_{t})+\\#\\{0\leq
a<n_{t}:(a,n_{t})=1,x_{t}(a)\neq?\\}\varphi(k_{t+1})$
$\displaystyle\leq\varphi(n_{t})+\Big{(}\sum_{k=1}^{t}\frac{1}{100^{k}}\Big{)}\varphi(n_{t})\varphi(k_{t+1})=\Big{(}\frac{1}{\varphi(k_{t+1})}+\sum_{k=1}^{t}\frac{1}{100^{k}}\Big{)}\varphi(n_{t+1})$
$\displaystyle\leq\sum_{k=1}^{t+1}\frac{1}{100^{k}}\varphi(n_{t+1})\leq\frac{1}{99}\varphi(n_{t+1}).$

In particular, at stage $t+1$, also (9) is satisfied.

Similar arguments show that

$\displaystyle\\{$ $\displaystyle
p<n_{t+1}:x_{t+1}(p)\neq?\\}\subset\\{p<n_{t+1}:p|n_{t+1}\\}\cup\\{p<n_{t}:x_{t+1}(p)\neq?\\}$
$\displaystyle\cup\bigcup_{\begin{subarray}{c}0\leq a<n_{t}\\\ (a,n_{t})=1\\\
x_{t}(a)\neq?\end{subarray}}\\{a+jn_{t}:0<j<k_{t+1},\>a+jn_{t}\in{\mathbb{P}}\\}.$

In view of (14), (9) and (13), it follows that

$\displaystyle\\#\\{$ $\displaystyle p<n_{t+1}:x_{t+1}(p)\neq?\\}$
$\displaystyle\leq\log n_{t+1}+\pi(n_{t})+2\\#\\{0\leq
a<n_{t}:(a,n_{t})=1,x_{t}(a)\neq?\\}\frac{\pi(n_{t+1})}{\varphi(n_{t})}$
$\displaystyle\leq\log
n_{t+1}+\pi(n_{t})+\frac{2}{99}\varphi(n_{t})\frac{\pi(n_{t+1})}{\varphi(n_{t})}\leq\frac{1}{2}\pi(n_{t+1}).$

Therefore, at stage $t+1$, also (10) is satisfied.

Finally, note that

$\frac{\varphi(n_{t+1})}{n_{t+1}}=\frac{\varphi(n_{t})}{n_{t}}\frac{\varphi(k_{t+1})}{k_{t+1}}\leq\frac{\varphi(n_{t})}{n_{t}}\frac{1}{2},$

so (7) holds and the resulting Toeplitz sequence is regular.

##  3\. Toeplitz subshifts for which an SPNT does not hold

We now intend to give an example of a (regular) Toeplitz sequence $x$ such
that an SPNT does not hold for the corresponding subshift, in fact:

$\lim_{t\to\infty}\frac{1}{\pi_{2}(n_{t})}\sum_{p_{1}p_{2}<n_{t}}F(S^{p_{1}p_{2}}x)\text{
does not exist,}$

where $\pi_{2}(N)$ stands for the number of semiprimes $<N$. We recall that
$\pi_{2}(N)\sim\frac{N\log\log N}{\log N}$. We also recall briefly that if we
look for semiprime numbers in arithmetic progressions $a+m{\mathbb{Z}}$ then
(for our purposes), we may assume that $(a,m)=1$. Indeed, if
$(a,m)\in\mathbb{S}\mathbb{P}$ (or has more than two prime divisors) then in
$a+m{\mathbb{N}}$ we can have at most one semiprime number. If
$(a,m)\in\mathbb{P}$, say $(a,m)=p$, then the number of semiprimes $\leq N$ in
$a+m{\mathbb{N}}$ is the same as the number of primes $\leq N/p$ in
$a/p+(m/p){\mathbb{Z}}$. Thus (as $m$ is fixed)

(16) $\sum_{(a,m)>1}\sum_{\begin{subarray}{c}p_{1}p_{2}\equiv a\pmod{m}\\\
p_{1}p_{2}\leq
N\end{subarray}}1=O\Big{(}\sum_{p|m}\frac{m/p}{\varphi(m/p)}\frac{N/p}{\log(N/p)}\Big{)}=o\Big{(}\pi_{2}(N)\Big{)}$

when $N\to\infty$ (with “$o$” which depends on $m$).

Now, suppose that $(a,m)=1$. Assume that $p_{1},p_{2}$ are prime numbers such
that $p_{1}p_{2}\leq N$, $p_{1}p_{2}=a\\!\mod m$ and $p_{1}\leq p_{2}$. Then
$p_{1}\leq\sqrt{N}$. Since $(p_{1},m)=1$, there exists a unique $0\leq
a(p_{1})<m$ such that $p_{1}\cdot a(p_{1})=a\\!\mod m$ and $(a(p_{1}),m)=1$.
Then

$\sum_{\begin{subarray}{c}p_{1}p_{2}\equiv a\\!\pmod{m}\\\ p_{1}p_{2}\leq
N\end{subarray}}1=\sum_{p_{1}\leq\sqrt{N}}\sum_{\begin{subarray}{c}p_{2}\leq\frac{N}{p_{1}}\\\
p_{2}\equiv
a(p_{1})\\!\pmod{m}\end{subarray}}1=\sum_{p_{1}\leq\sqrt{N}}\pi([N/p_{1}];m,a(p_{1})).$

As $p_{1}\leq\sqrt{N}$ implies $N/p_{1}\geq\sqrt{N}$, in view of Theorem 2.1,
for every $\varepsilon>0$ there exists $N_{\varepsilon}$ such that for all
$N\geq N_{\varepsilon}$ and $p_{1}\leq\sqrt{N}$ with $(p_{1},m)=1$, we have

$(1-\varepsilon)\frac{\pi([N/p_{1}])}{\varphi(m)}<\pi([N/p_{1}];m,a(p_{1}))<(1+\varepsilon)\frac{\pi([N/p_{1}])}{\varphi(m)}.$

Since $\pi_{2}(N)=\sum_{p_{1}\leq\sqrt{N}}\pi([N/p_{1}])$, it follows that

$(1-\varepsilon)\frac{\pi_{2}(N)}{\varphi(m)}<\sum_{\begin{subarray}{c}p_{1}p_{2}\equiv
a\\!\pmod{m}\\\ p_{1}p_{2}\leq
N\end{subarray}}1<(1+\varepsilon)\frac{\pi_{2}(N)}{\varphi(m)}$

for every $N\geq N_{\varepsilon}$. Therefore

(17) $\sum_{\begin{subarray}{c}p_{1}p_{2}\equiv a\\!\pmod{m}\\\ p_{1}p_{2}\leq
N\end{subarray}}1\sim\frac{\pi_{2}(N)}{\varphi(m)}.$

Now, we repeat the scheme of the previous construction almost word for word,
although we have to take care how to choose $k_{t+1}$.

First of all, we require that $k_{t+1}$ is large enough so that (16) and (17)
hold (with $m=n_{t}$). So, we replace (10) by

$\\#\\{p_{1}p_{2}<n_{t}:\>x_{t}(p_{1}p_{2})=?\\}\geq\frac{1}{2}\pi_{2}(n_{t})$

and requiring (instead of (14)) that for $(a,n_{t})=1$, we have

$\\#(\\{a+jn_{t}:\>0\leq j<k_{t+1}\\}\cap\mathbb{S}{\mathbb{P}})\leq
2\frac{\pi_{2}(n_{t+1})}{\varphi(n_{t})}.$

Furthermore, we replace (13) by the requirement that

$\sum_{(a,n_{t})>1}\sum_{\begin{subarray}{c}p_{1}p_{2}\equiv a\pmod{n_{t}}\\\
p_{1}p_{2}\leq n_{t+1}\end{subarray}}1\leq\frac{1}{8}\pi_{2}(n_{t+1})$

which is possible as explained at the beginning of this section.

To carry over the previous proof, it remains to show that

$\frac{1}{\pi_{2}(n_{t})}\sum_{p_{1}p_{2}<n_{t},(p_{1}p_{2},n_{t})>1}(-1)^{x(p_{1}p_{2})}=o(1).$

To show this, for simplicity, we assume additionally that $k_{t}$ are chosen
to be perfect squares. If so then also all numbers $n_{t}$ are perfect squares
and

(18) if $p|n_{t}$ then $\frac{n_{t}}{p}\geq\sqrt{n_{t}}$.

Now, using that $\sum_{p|k}\frac{1}{p}\ll\log\log\log k$, see e.g. [12] and
(18), it follows that

$\sum_{p_{1}p_{2}<n_{t},(p_{1}p_{2},n_{t})>1}1\ll\log^{2}n_{t}+\sum_{p|n_{t}}\pi(n_{t}/p)=$
$\log^{2}n_{t}+\sum_{p|n_{t}}O\Big{(}\frac{n_{t}/p}{\log(n_{t}/p)}\Big{)}=\log^{2}n_{t}+n_{t}\sum_{p|n_{t}}\frac{1}{p}O\Big{(}\frac{1}{\log(n_{t}/p)}\Big{)}=$
$\log^{2}n_{t}+\frac{2n_{t}}{\log
n_{t}}O\Big{(}\sum_{p|n_{t}}\frac{1}{p}\Big{)}\ll\log^{2}n_{t}+\frac{2n_{t}\log\log\log
n_{t}}{\log n_{t}}=o(\pi_{2}(n_{t}))$

as needed.

##  4\. Regular Toeplitz subshifts which satisfy a PNT (proof of Theorem B)

Let $x\in\mathcal{A}^{\mathbb{Z}}$ be a regular Toeplitz sequence. Then, for
every $k\in{\mathbb{N}}$, there is an $n_{k}$-periodic sequence
$x_{k}\in(\mathcal{A}\cup\\{?\\})^{\mathbb{Z}}$ so that

$x_{k}(j)\neq?\text{ implies }x(j)=x_{k}(j)=x_{l}(j)\text{ for all }l\geq k$

and

$?_{k}=?_{k}(x):=\\#\\{0\leq j<n_{k}:x_{k}(j)=?\\}=o(n_{k}).$

For every Toeplitz sequence $x\in\mathcal{A}^{\mathbb{Z}}$ and natural $m$ let
us consider a new Toeplitz sequence
$x^{(m)}\in(\mathcal{A}^{2m+1})^{\mathbb{Z}}$ given by

$x^{(m)}(j)=(x(j-m),\ldots,x(j+m))\text{ for every }j\in{\mathbb{Z}}.$

If $(n_{t})_{t\geq 1}$ is a periodic structure of $x$, then it is also a
periodic structure of $x^{(m)}$. Moreover,

(19) $?_{k}(x^{(m)})\leq(2m+1)?_{k}(x)\text{ for every }k\geq 1.$

Hence, the regularity of $x$ implies the regularity of $x^{(m)}$.

Theorem B follows directly from Lemma A.1 and the following result.

######  Theorem 4.1.

Suppose that $(X_{x},S)$ is a Toeplitz system such that

$?_{k}=o(\varphi(n_{k})).$

Then $(X_{x},S)$ satisfies a PNT.

###### Proof.

To show a PNT for $(X_{x},S)$, we need to show that for every continuous
$F:X_{x}\to{\mathbb{C}}$ and every $\varepsilon>0$ there exists
$N_{\varepsilon}$ so that for every $N,M\geq N_{\varepsilon}$ and every
$r\in{\mathbb{Z}}$, we have

(20) $\Big{|}\frac{1}{\pi(N)}\sum_{p\leq
N}F(S^{p+r}x)-\frac{1}{\pi(M)}\sum_{p\leq M}F(S^{p+r}x)\Big{|}<\varepsilon.$

We first assume that $F:X_{x}\to{\mathbb{R}}$ depends only on the zero
coordinate, i.e. $F(y)=f(y(0))$ for some $f:\mathcal{A}\to{\mathbb{R}}$.

Fix $\varepsilon>0$. Fix also $k\geq 1$ so that

(21) $?_{k}<\frac{\varepsilon}{8}\varphi(n_{k}).$

Next choose $N_{\varepsilon}$ such that for every $N\geq N_{\varepsilon}$, we
have

(22)
$\displaystyle\Big{|}\pi(N;n_{k},a)-\frac{\pi(N)}{\varphi(n_{k})}\Big{|}<\frac{\varepsilon}{8}\frac{\pi(N)}{\varphi(n_{k})}\text{
for all }a\in{\mathbb{Z}}\text{ with }(a,n_{k})=1,$ (23)
$\displaystyle\\#\\{p\leq N:p|n_{k}\\}\leq\log
n_{k}<\frac{\varepsilon}{8}\pi(N).$

We will show that for all $N\geq N_{\varepsilon}$ and $r\in{\mathbb{Z}}$ we
have

(24) $\Big{|}\frac{1}{\pi(N)}\sum_{p\leq
N}F(S^{p+r}x)-\frac{1}{\varphi(n_{k})}\sum_{\begin{subarray}{c}0\leq
a<n_{k}\\\ (a-r,n_{k})=1\\\
x_{k}(a)\neq?\end{subarray}}F(S^{a}x)\Big{|}\leq\varepsilon\|F\|_{\sup},$

which implies (20).

Recall that $x_{k}\in(\mathcal{A}\cup\\{?\\})^{\mathbb{Z}}$ is an
$n_{k}$-periodic sequence (used to construct $x$ at stage $k$). If for some
$a\in{\mathbb{Z}}$ we have

$x_{k}(a)\neq\;?,$

then

$x(a+j\cdot n_{k})=x_{k}(a)\text{ for every }j\in{\mathbb{Z}}.$

This implies that if $p\leq N$ and $x_{k}(p+r\\!\mod n_{k})\neq\;?$, then

(25) $F(S^{p+r}x)=F(S^{p+r\\!\mod n_{k}}x).$

Note that

$\displaystyle\\#\\{$ $\displaystyle p\leq N:x_{k}(p+r\\!\mod n_{k})=\;?\\}$
$\displaystyle\leq\sum_{\begin{subarray}{c}0\leq a<n_{k}\\\ (a-r,n_{k})=1\\\
x_{k}(a)=?\end{subarray}}\\#\\{p\leq N:p=a-r\\!\mod n_{k}\\}$
$\displaystyle\quad+\sum_{\begin{subarray}{c}0\leq a<n_{k}\\\
(a-r,n_{k})>1\end{subarray}}\\#\\{p\leq N:p=a-r\\!\mod n_{k}\\}.$

Assume that $N\geq N_{\varepsilon}$. By (22) and (23), for every integer $v$
with $(v,n_{k})=1$ we have

$\\#\\{p\leq N:p=v\\!\mod
n_{k}\\}=\pi(N;n_{k},v)\leq(1+\varepsilon/8)\frac{\pi(N)}{\varphi(n_{k})}$

and

(26) $\sum_{\begin{subarray}{c}0\leq a<n_{k}\\\
(a-r,n_{k})>1\end{subarray}}\\#\\{p\leq N:p=a-r\\!\mod n_{k}\\}\leq\\#\\{p\leq
N:p|n_{k}\\}<\frac{\varepsilon}{8}\pi(N),$

where left inequality follows from the fact that if $(a-r,n_{k})>1$ and
$p_{a}=a-r\\!\mod n_{k}$ for a prime $p_{a}$, then $(a-r,n_{k})=p_{a}$ and

$\\{p\leq N:\>p=a-r\\!\mod n_{k}\\}=\\{p_{a}\\}.$

It follows that (use also (21))

$\displaystyle\\#$ $\displaystyle\\{p\leq N:x_{k}(p+r\\!\mod n_{k})=\;?\\}$
$\displaystyle\leq\\#\\{0\leq
a<n_{k}:(a-r,n_{k})=1,x_{k}(a)=?\\}(1+\varepsilon/8)\frac{\pi(N)}{\varphi(n_{k})}+\frac{\varepsilon}{8}\pi(N)$
$\displaystyle\leq?_{k}(1+\varepsilon/8)\frac{\pi(N)}{\varphi(n_{k})}+\frac{\varepsilon}{8}\pi(N)\leq\frac{\varepsilon}{2}\pi(N).$

Let

$P_{N}:=\\{p\leq N:x_{k}(p+r\\!\mod n_{k})\neq\;?\\}.$

Then by the above, for every $N\geq N_{\varepsilon}$,

(27) $\displaystyle\Big{|}\frac{1}{\pi(N)}\sum_{p\leq
N}F(S^{p+r}x)-\frac{1}{\pi(N)}\sum_{p\in
P_{N}}F(S^{p+r}x)\Big{|}\leq\frac{\varepsilon}{2}\|F\|_{\sup}.$

But by (25),

$\displaystyle\sum_{p\in P_{N}}F(S^{p+r}x)$
$\displaystyle=\sum_{\begin{subarray}{c}0\leq a<n_{k}\\\
x_{k}(a)\neq?\end{subarray}}\sum_{\begin{subarray}{c}p\leq N\\\ p\equiv
a-r\\!\mod n_{k}\end{subarray}}F(S^{a}x)$
$\displaystyle=\sum_{\begin{subarray}{c}0\leq a<n_{k}\\\
x_{k}(a)\neq?\end{subarray}}F(S^{a}x)\\#\\{p\leq N,p=a-r\\!\mod n_{k}\\}.$

If $(a-r,n_{k})=1$, then again by (22), we have

$\Big{|}\\#\\{p\leq N,p=a-r\\!\mod
n_{k}\\}-\frac{\pi(N)}{\varphi(n_{k})}\Big{|}=\Big{|}\pi(N;n_{k},a-r)-\frac{\pi(N)}{\varphi(n_{k})}\Big{|}<\frac{\varepsilon}{8}\frac{\pi(N)}{\varphi(n_{k})}.$

In view of (26), it follows that

$\displaystyle\Big{|}\frac{1}{\pi(N)}\sum_{p\in
P_{N}}F(S^{p+r}x)-\frac{1}{\varphi(n_{k})}\sum_{\begin{subarray}{c}0\leq
a<n_{k}\\\ (a-r,n_{k})=1\\\ x_{k}(a)\neq?\end{subarray}}F(S^{a}x)\Big{|}$
$\displaystyle=\Big{|}\sum_{\begin{subarray}{c}0\leq a<n_{k}\\\
x_{k}(a)\neq?\end{subarray}}F(S^{a}x)\frac{\pi(N;n_{k},a-r)}{\pi(N)}-\frac{1}{\varphi(n_{k})}\sum_{\begin{subarray}{c}0\leq
a<n_{k}\\\ (a-r,n_{k})=1\\\ x_{k}(a)\neq?\end{subarray}}F(S^{a}x)\Big{|}$
$\displaystyle\leq\frac{1}{\pi(N)}\sum_{\begin{subarray}{c}0\leq a<n_{k}\\\
(a-r,n_{k})=1\\\
x_{k}(a)\neq?\end{subarray}}|F(S^{a}x)|\Big{|}\pi(N;n_{k},a-r)-\frac{\pi(N)}{\varphi(n_{k})}\Big{|}+\frac{\varepsilon}{8}\|F\|_{\sup}$
$\displaystyle\leq\|F\|_{\sup}\Big{(}\frac{\varepsilon}{8}\frac{\\#\\{0\leq
a<n_{k}:x_{k}(a)\neq?,(a-r,n_{k})=1\\}}{\varphi(n_{k})}+\frac{\varepsilon}{8}\Big{)}\leq\|F\|_{\sup}\frac{\varepsilon}{2}.$

Together with (27), this gives (24), which completes the proof in the case of
$F$ depending only on the zero coordinate.

Now suppose that $F:X_{x}\to{\mathbb{C}}$ depends only on finitely many
coordinates. Then there exists natural $m$ and
$f:\mathcal{A}^{2m+1}\to{\mathbb{C}}$ such that $F(y)=f(y(-m),\ldots,y(m))$
for every $y=(y(k))_{k\in{\mathbb{Z}}}\in X_{x}$. Denote by
$X_{x^{(m)}}\subset(\mathcal{A}^{2m+1})^{{\mathbb{Z}}}$ the orbit closure of
$x^{(m)}\in(\mathcal{A}^{2m+1})^{{\mathbb{Z}}}$. Then every $y^{(m)}\in
X_{x^{(m)}}$ is of the form $y^{(m)}(k)=(y(k-m),\ldots,y(k+m))$ for some
$y=(y(k))_{k\in{\mathbb{Z}}}\in X_{x}$.

In view of (19), $(X_{x^{(m)}},S)$ is a regular Toeplitz shift with
$?_{k}(x^{(m)})=o(\varphi(n_{k}))$. Let us consider
$\bar{F}:X_{x^{(m)}}\to{\mathbb{C}}$ given by
$\bar{F}(y^{(m)})=f(y^{(m)}(0))=f(y(-m),\ldots,y(m))$ for $y^{(m)}\in
X_{x^{(m)}}$. Since $\bar{F}$ depends only on the zero coordinate, by (20)
applied to $x^{(m)}$ and the map $\bar{F}$, for every $\varepsilon>0$ there
exists $N_{\varepsilon}$ such that for $N,M\geq N_{\varepsilon}$, we have

$\displaystyle\Big{|}$ $\displaystyle\frac{1}{\pi(N)}\sum_{p\leq
N}F(S^{p+r}x)-\frac{1}{\pi(M)}\sum_{p\leq M}F(S^{p+r}x)\Big{|}$
$\displaystyle=\Big{|}\frac{1}{\pi(N)}\sum_{p\leq
N}\bar{F}(S^{p+r}x^{(m)})-\frac{1}{\pi(M)}\sum_{p\leq
M}\bar{F}(S^{p+r}x^{(m)})\Big{|}<\varepsilon.$

Thus (20) holds for every $F:X_{x}\to{\mathbb{C}}$ depending only on finitely
many coordinates. As the set of such functions is dense in $C(X_{x})$, (20)
also holds for every $F\in C(X_{x})$, which completes the proof.

As $\varphi(n)\to\infty$ when $n\to\infty$, we obtain the following result.

######  Corollary 4.2.

If $x$ is Toeplitz for which the sequence $(?_{k})$ is bounded then
$(X_{x},S)$ satisfies a PNT.

##  5\. Toeplitz subshifts for which an SPNT holds

######  Theorem 5.1.

Suppose that $(X_{x},S)$ is a Toeplitz system such that

$?_{k}=o(\varphi(n_{k})).$

Then, for every $F\in C(X_{x})$ and $y\in X_{x}$, the limit

$\lim_{N\to\infty}\frac{1}{\pi_{2}(N)}\sum_{p_{1}p_{2}<N}F(S^{p_{1}p_{2}}y)\text{
exists.}$

###### Proof.

The proof proceeds along the same lines as the proof of Theorem 4.1. It relies
on the following counterpart of (24): for every $\varepsilon>0$ there exists a
natural $N_{\varepsilon}$ such that for all $N\geq N_{\varepsilon}$ and
$r\in{\mathbb{Z}}$, we have

(28) $\Big{|}\frac{1}{\pi_{2}(N)}\sum_{p_{1}p_{2}\leq
N}F(S^{p_{1}p_{2}+r}x)-\frac{1}{\varphi(n_{k})}\sum_{\begin{subarray}{c}0\leq
a<n_{k}\\\ (a-r,n_{k})=1\\\
x_{k}(a)\neq?\end{subarray}}F(S^{a}x)\Big{|}\leq\varepsilon\|F\|_{\sup}.$

In turn, the proof of (24) is based on only two elements: (22) and (26). Their
semi-prime counterparts follows directly from (17) and (16), respectively.
Now, we repeat the arguments of the proof of (24) almost word for word,
replacing (22) and (26) by their semi-prime counterparts.

######  Remark 5.2.

In view of (24) and (28), under the assumption $?_{k}=o(\varphi(n_{k}))$, we
have

$\lim_{N\to\infty}\frac{1}{\pi_{2}(N)}\sum_{p_{1}p_{2}<N}F(S^{p_{1}p_{2}}y)=\lim_{N\to\infty}\frac{1}{\pi(N)}\sum_{p<N}F(S^{p}y)$

for every $F\in C(X_{x})$ and $y\in X_{x}$, so a PNT and an SPNT fully
coincide for this class of regular Toeplitz systems.

##  6\. Ergodic averages along polynomial times

Let $P$ be a monic polynomial666The leading coefficient of $P$ equals 1. This
assumption is only for simplicity. In fact, Theorem 6.8 below is true whenever
the set of (non-zero) coefficients of $P-P(0)$ is coprime, see the proof of
Corollary 6.3 and the assumptions of Albis theorem in [17]. of degree $d>1$
with non-negative integer coefficients. Note that, under these assumptions,
$P(\cdot)$ is a strictly increasing function on ${\mathbb{N}}$. For every
$n\in{\mathbb{N}}$, let

$R^{P}_{n}:=\\{0\leq a<n:a=P(m)\\!\mod n\text{ for some
}m\in{\mathbb{N}}\\}\text{ and }\psi^{P}(n):=\\#R^{P}_{n}.$

For all $N,n\in{\mathbb{N}}$ and $a\in R^{P}_{n}$, let

$\rho^{P}(N;n,a)=\\#\\{1\leq m\leq N:P(m)=a\\!\mod n\\}.$

and

$\rho^{P}(n,a):=\rho^{P}(n;n,a),\;\;\rho^{P}(n):=\max_{a\in
R^{P}_{n}}\rho^{P}(n;n,a).$

######  Lemma 6.1.

The function $\psi^{P}$ is multiplicative, i.e.
$\psi^{P}(n_{1}n_{2})=\psi^{P}(n_{1})\psi^{P}(n_{2})$ if $(n_{1},n_{2})=1$. If
$a\in{\mathbb{Z}}/n{\mathbb{Z}}$, $n_{1},\ldots,n_{k}$ are pairwise coprime
and $n=n_{1}\cdots n_{k}$ then $a\in R^{P}_{n}$ iff $a_{i}\in R^{P}_{n_{i}}$
for $i=1,\ldots,k$, where $0\leq a_{i}<n_{i}$ is the remainder of $a$ when
divided by $n_{i}$ (that is, $0\leq a_{i}<n_{i}$ and $a_{i}=a$ mod $n_{i}$).
Moreover,

(29) $\rho^{P}(n,a)=\prod_{i=1}^{k}\rho^{P}(n_{i},a_{i}).$

###### Proof.

Note that the multiplicativity of $\psi^{P}$ follows from the second part of
the lemma.

Moreover, note that $a\in R^{P}_{n}$ iff $a=P(m)\\!\mod n$ for some $0\leq
m<n$. Indeed, if $a=P(m)\\!\mod n$ for some $m\in{\mathbb{N}}$, then
$a=P(m^{\prime})\\!\mod n$, where $0\leq m^{\prime}<n$ is the remainder of $m$
when divided by $n$.

If $a\in R^{P}_{n_{1}\cdots n_{k}}$, i.e. $a=P(m)\\!\mod n_{1}\cdots n_{k}$
for some $0\leq m<n$, then $a_{i}=a=P(m)=P(m_{i})\\!\mod n_{i}$ for every
$i=1,\ldots,k$, where $0\leq m_{i}<n_{i}$ is the remainder of $m$ when divided
by $n_{i}$.

Now, suppose $a\in{\mathbb{Z}}/n{\mathbb{Z}}$, $a_{i}=a$ mod $n_{i}$ and
$a_{i}\in R^{P}_{n_{i}}$ for $i=1,\ldots,k$. Then, for every $i=1,\ldots,k$,
there exists $0\leq m_{i}<n_{i}$ such that $a_{i}=P(m_{i})\\!\mod n_{i}$. By
the Chinese Remainder Theorem, there exists a unique $0\leq m<n$ such that
$m=m_{i}\\!\mod n_{i}$ for $i=1,\ldots,k$. It follows that

$P(m)=P(m_{i})=a_{i}=a\\!\mod n_{i}\text{ for all }i=1,\ldots,k.$

This yields $a=P(m)\\!\mod n_{1}\cdots n_{k}$ and $a\in R^{P}_{n}$.

The argument above also shows (29).

######  Remark 6.2.

Note that in the argument above we used the fact that the $a_{i}$’s determine
$a$ as by the ChRT there exists only one $0\leq a<n$ such that $a=a_{i}$ mod
$n_{i}$ for each $i=1,\ldots,k$.

For any natural $n$ denote by $\omega(n)$ the number of its prime divisors
(counted without multiplicities) and by $p(n)$ the product of its prime
divisors.

######  Corollary 6.3.

The arithmetic function $\rho_{P}$ is multiplicative and
$\rho^{P}(n)\leq\frac{d^{\omega(n)}}{p(n)}n$.

###### Proof.

The multiplicativity of $\rho^{P}$ follows directly from (29). By Albis
theorem (see Corollary 3 of Theorem 1.23 in [17] 777Note that compared to
notation from [17], we have:
$\rho^{P}(n;n,a)=\lambda_{P-a}(n),\;\rho^{P}(n)=\max_{a\in
R^{P}_{n}}\lambda_{P-a}(n);$ the estimate on $\lambda_{P}$ in [17] depends
only on the degree of the polynomial.), for any prime number we have
$\rho^{P}(p^{n})\leq dp^{n-1}$. This result combined with the multiplicativity
of $\rho^{P}$ gives the required bound of $\rho^{P}(n)$.

######  Lemma 6.4.

For all $n\in{\mathbb{N}}$, $a\in R^{P}_{n}$ and $N\geq P(n)$, we have

$\displaystyle\rho^{P}(n,a)\Big{(}\frac{P^{-1}(N)}{n}-1\Big{)}$
$\displaystyle\leq\\#\\{m\in{\mathbb{N}}:1\leq P(m)\leq N,P(m)=a\\!\mod n\\}$
$\displaystyle\leq\rho^{P}(n,a)\Big{(}\frac{P^{-1}(N)}{n}+1\Big{)}.$

###### Proof.

Let $s:=\rho^{P}(n,a)$ and let $1\leq m_{1}<\ldots<m_{s}\leq n$ be all numbers
such that $P(m_{i})=a\\!\mod n$. Note that a natural number $m$ satisfies
$P(m)\leq N$ and $P(m)=a\\!\mod n$ iff $m=jn+r$ with $0\leq
j\leq(P^{-1}(N)-r)/n$ and $0<r\leq n$ satisfies $P(r)=a\\!\mod n$. Thus,
$r=m_{i}$ for some $i=1,\ldots,s$. It follows that

$\displaystyle\rho:$ $\displaystyle=\\#\\{m\in{\mathbb{N}}:1\leq P(m)\leq
N,P(m)=a\\!\mod n\\}$
$\displaystyle=\sum_{i=1}^{s}\Big{(}\Big{[}\frac{P^{-1}(N)-m_{i}}{n}\Big{]}+1\Big{)}.$

Since

$\displaystyle\frac{P^{-1}(N)}{n}-1$
$\displaystyle\leq\frac{P^{-1}(N)-m_{i}}{n}<\Big{[}\frac{P^{-1}(N)-m_{i}}{n}\Big{]}+1$
$\displaystyle\leq\frac{P^{-1}(N)-m_{i}}{n}+1<\frac{P^{-1}(N)}{n}+1,$

by summing up, this gives

$s\Big{(}\frac{P^{-1}(N)}{n}-1\Big{)}\leq\rho\leq
s\Big{(}\frac{P^{-1}(N)}{n}+1\Big{)}.$

######  Remark 6.5.

As $P$ is an increasing function, we can apply the above inequalities to
$P(N)$ instead of $N$ (as $P(N)\geq N$). Then $P(m)\leq P(N)$ iff $m\leq N$,
and the result of the lemma implies

$\rho^{P}(n,a)\Big{(}\frac{N}{n}-1\Big{)}\leq\rho^{P}(N;n,a)\leq\rho^{P}(n,a)\Big{(}\frac{N}{n}+1\Big{)}.$

We now focus on the simplest case when $P(n)=n^{2}$. We continue to write $R$
for $R^{P}$, $\psi$ for $\psi^{P}$ and $\rho$ for $\rho^{P}$. In view of
Theorems 1.27 and 1.30 in [17], we have the following result.

######  Proposition 6.6.

For every prime number $p>2$, for every $a\in R_{p^{N}}$, where $N=2n$ or
$2n+1$, we have

$\rho(p^{N},a)=\left\\{\begin{array}[]{cl}2&\text{ if }a=a^{\prime}\\!\mod
p\text{ for }a^{\prime}\in R_{p}\setminus\\{0\\}\\\ 2p^{r}&\text{ if
}a=p^{2r}a^{\prime}\text{ and }a^{\prime}=a^{\prime\prime}\\!\mod p\text{ for
}a^{\prime\prime}\in R_{p}\setminus\\{0\\}\\\ p^{n}&\text{ if
}a=0.\end{array}\right.$

Moreover, we have

$\psi(p^{2n+1})=\frac{p^{2n+2}+2p+1}{2(p+1)}\text{ and
}\psi(p^{2n})=\frac{p^{2n+1}+p+2}{2(p+1)}.~{}$

Furthermore, If $p=2$ then

$\rho(2,a)=1\text{ for all }a\in R_{2},\;\;\rho(4,a)=2\text{ for all }a\in
R_{4}$

and for any $N\geq 3$, where $N=2n$ or $2n+1$, for every $a\in R_{2^{N}}$, we
have

$\rho(2^{N},a)=\left\\{\begin{array}[]{cl}4&\text{ if }a=1\\!\mod 8\\\ 4\cdot
2^{r}&\text{ if }a=2^{2r}a^{\prime},\,2r\leq N-3,\,a^{\prime}=1\\!\mod 8\\\
2\cdot 2^{r}&\text{ if }a=2^{2r}a^{\prime},\,2r=N-2,\,a^{\prime}=1\\!\mod 4\\\
2^{r}&\text{ if }a=2^{2r}a^{\prime},\,2r=N-1,\,a^{\prime}=1\\!\mod 2\\\
2^{n}&\text{ if }a=0.\end{array}\right.$

Moreover,

$\psi(2^{2n})=\frac{2^{2n-1}+4}{3}\text{ and
}\psi(2^{2n+1})=\frac{2^{2n}+5}{3}.$

######  Corollary 6.7.

For every natural $n\geq 2$, we have $\rho(n)\leq 4\sqrt{n}$. Moreover, if $n$
is square-free, then $\rho(n)\leq 2^{\omega(n)}$.

###### Proof.

By a direct inspection of the formulas in Proposition 6.6, we obtain:

$\rho(2^{N})\leq 2\sqrt{2^{N}},\;\rho(3^{N})\leq 2\sqrt{3^{N}}$

but for all $p\geq 5$, we have

$\rho(p^{N})\leq\sqrt{p^{N}}.$

Indeed, for the cases $a=a^{\prime}$ mod $p$ (for $a^{\prime}\in
R_{p}\setminus\\{0\\}$) and $a=0$, it is direct. For the case
$\rho(p^{N},a)=2p^{r}$, we have $a=p^{2r}a^{\prime}<p^{N}$, so $2r\leq N-1$
and then indeed $2p^{r}\leq p^{N/2}$.

The second inequality follows directly from $\rho(p)\leq 2$.

For some future purposes, we are interested in cases (in Proposition 6.6)
which gives possibly smallest values for the function $\rho$, hence, for every
prime number $p$ and any natural $n$, let

$\widetilde{R}_{p^{n}}:=\left\\{\begin{array}[]{cl}\\{0\leq
a<p^{n}:a=a^{\prime}\\!\mod p\text{ for }a^{\prime}\in
R_{p}\setminus\\{0\\}\\}&\text{ if }p>2\\\ R_{2}&\text{ if }p^{n}=2\\\
R_{4}&\text{ if }p^{n}=4\\\ \\{0\leq a<2^{n}:a=1\\!\mod 8\\}&\text{ if }n\geq
3.\end{array}\right.$

By Proposition 6.6, $\widetilde{R}_{p^{n}}\subset{R}_{p^{n}}$.

Let $n=p_{1}^{m_{1}}p_{2}^{m_{2}}\cdots p_{k}^{m_{k}}$ be the canonical
representation of $n$. Let

$\Phi:{\mathbb{Z}}/n{\mathbb{Z}}\to{\mathbb{Z}}/p_{1}^{m_{1}}{\mathbb{Z}}\times\ldots\times{\mathbb{Z}}/p_{k}^{m_{k}}{\mathbb{Z}}$

be the canonical ring isomorphism. Recall (cf. Lemma 6.1 and Remark 6.2) that
$\Phi$ establishes a one-to-one correspondence between $R_{n}$ and
$R_{p_{1}^{m_{1}}}\times\ldots\times R_{p_{k}^{m_{k}}}$. Set

$\widetilde{R}_{n}:=\Phi^{-1}(\widetilde{R}_{p_{1}^{m_{1}}}\times\ldots\times\widetilde{R}_{p_{k}^{m_{k}}})$

and

$\widetilde{\psi}(n):=\\#\widetilde{R}_{n}.$

Then, clearly, $\widetilde{\psi}$ is a multiplicative function. Moreover, by
Proposition 6.6, for each $a\in\widetilde{R}_{p^{N}}$, we have

$\rho(p^{N},a)=\left\\{\begin{array}[]{cl}1&\text{ if }p^{N}=2\\\ 2&\text{ if
}p^{N}=2\text{ or }p>2\\\ 4&\text{ if }p=2\text{ and }N\geq
3.\end{array}\right.$

Hence, in view of (29), for every $a\in\widetilde{R}_{n}$, we have

(30) $\frac{1}{2}\cdot 2^{\omega(n)}\leq\rho(n,a)\leq 2\cdot 2^{\omega(n)}.$

Moreover, by definition,

$\widetilde{\psi}(p^{n}):=\left\\{\begin{array}[]{cl}p^{n-1}\frac{p-1}{2}&\text{
if }p>2\\\ 2&\text{ if }p^{n}=2\\\ 2&\text{ if }p^{n}=4\\\ 2^{n-3}&\text{ if
}p=2\text{ and }n\geq 3.\end{array}\right.$

It follows that

(31)
$\frac{1}{2}\prod_{p|n}\Big{(}1-\frac{1}{p}\Big{)}\leq\frac{2^{\omega(n)}\widetilde{\psi}(n)}{n}\leq
4\prod_{p|n}\Big{(}1-\frac{1}{p}\Big{)}.$

(To obtain these inequalities, for $n=p_{1}^{m_{1}}p_{2}^{m_{2}}\cdots
p_{k}^{m_{k}}$, write
$\frac{2^{\omega(n)}\widetilde{\psi}(n)}{n}=\prod_{i=1}^{k}\frac{2\tilde{\psi}(p_{i}^{m_{i}})}{p_{i}^{m_{i}}}$
and apply the formula above.)

###  6.1. Non-conventional ergodic theorem

######  Theorem 6.8.

Suppose that $(X_{x},S)$ is a Toeplitz system such that

(32) $?_{k}=o(n_{k}/{\rho^{P}(n_{k})}).$

Then, for every continuous map $F:X_{x}\to{\mathbb{C}}$ and $y\in X_{x}$, the
limit

(33) $\lim_{N\to\infty}\frac{1}{N}\sum_{m\leq N}F(S^{P(m)}y)$

exists.

###### Proof.

To show (33), we need to prove that for every $\varepsilon>0$ there exists
$N_{\varepsilon}$ so that for every $N,M\geq N_{\varepsilon}$ and every
$r\in{\mathbb{Z}}$, we have

(34) $\Big{|}\frac{1}{N}\sum_{m\leq N}F(S^{P(m)+r}x)-\frac{1}{M}\sum_{m\leq
M}F(S^{P(m)+r}x)\Big{|}<\varepsilon.$

We first assume that $F:X_{x}\to{\mathbb{R}}$ depends only on the zero
coordinate, i.e. $F(y)=f(y(0))$ for some $f:\mathcal{A}\to{\mathbb{R}}$.

Fix $\varepsilon>0$. Choose $k\geq 1$ so that

(35) $?_{k}<\frac{\varepsilon}{8}\frac{n_{k}}{{\rho^{P}(n_{k})}}.$

Next, choose $N_{\varepsilon}\geq 8n_{k}^{2}/\varepsilon$. Then, in view of
Remark 6.5 (and the choice of $N_{\varepsilon}$), for every $N\geq
N_{\varepsilon}$ and $a\in R^{P}_{n_{k}}$, we have

(36)
$\displaystyle\left|\rho^{P}(N;n_{k},a)-\rho^{P}(n_{k},a)\frac{N}{n_{k}}\right|<\rho^{P}(n_{k})\leq
n_{k}\leq\frac{\varepsilon}{8}\frac{N}{n_{k}}.$

From now on, we write that an integer number $v$ belongs to $R^{P}_{n_{k}}$ if
there exists $0\leq v^{\prime}<n_{k}$ such that $v^{\prime}=v\\!\mod n_{k}$
and $v^{\prime}\in R^{P}_{n_{k}}$. We will show that for all $N\geq
N_{\varepsilon}$ and $r\in{\mathbb{Z}}$, we have

(37) $\Big{|}\frac{1}{N}\sum_{m\leq
N}F(S^{P(m)+r}x)-\frac{1}{n_{k}}\sum_{\begin{subarray}{c}0\leq a<n_{k}\\\
a-r\in R^{P}_{n_{k}}\\\
x_{k}(a)\neq?\end{subarray}}{\rho^{P}(n_{k},a-r)}F(S^{a}x)\Big{|}\leq\varepsilon\|F\|_{\sup},$

and this implies (34).

Recall that $x_{k}\in(\mathcal{A}\cup\\{?\\})^{\mathbb{Z}}$ is an
$n_{k}$-periodic sequence (used to construct $x$ at stage $k$). Note that for
every $a\in{\mathbb{Z}}$, we have

$x_{k}(a)\neq\;?\Rightarrow x(a+j\cdot n_{k})=x_{k}(a)\text{ for every
}j\in{\mathbb{Z}}.$

This implies that if $m\leq N$ and $x_{k}(P(m)+r\\!\mod n_{k})\neq\;?$, then

(38) $F(S^{P(m)+r}x)=F(S^{P(m)+r\\!\mod n_{k}}x).$

Therefore,

$\displaystyle\\#\\{$ $\displaystyle m\leq N:x_{k}(P(m)+r\\!\mod
n_{k})=\;?\\}$ $\displaystyle=\sum_{\begin{subarray}{c}0\leq a<n_{k}\\\ a-r\in
R^{P}_{n_{k}}\\\ x_{k}(a)=?\end{subarray}}\\#\\{m\leq N:P(m)=a-r\\!\mod
n_{k}\\}=\sum_{\begin{subarray}{c}0\leq a<n_{k}\\\ a-r\in R^{P}_{n_{k}}\\\
x_{k}(a)=?\end{subarray}}\rho^{P}(N;n_{k},a-r).$

Assume that $N\geq N_{\varepsilon}$. By (36), for every integer $v\in
R^{P}_{n_{k}}$, we have

$\rho^{P}(N;n_{k},v)\leq 2{\rho^{P}(n_{k})}\frac{N}{n_{k}}.$

In view of (35), it follows that

$\displaystyle\\#$ $\displaystyle\\{m\leq N:x_{k}(P(m)+r\\!\mod n_{k})=\;?\\}$
$\displaystyle\leq\\#\\{0\leq a<n_{k}:a-r\in
R^{P}_{n_{k}},x_{k}(a)=?\\}2{\rho^{P}(n_{k})}\frac{N}{n_{k}}$
$\displaystyle\leq
2?_{k}{\rho^{P}(n_{k})}\frac{N}{n_{k}}\leq\frac{\varepsilon}{4}N.$

Let

$U_{N}:=\\{m\leq N:x_{k}(P(m)+r\\!\mod n_{k})\neq\;?\\}.$

Then by the above, for every $N\geq N_{\varepsilon}$,

(39) $\displaystyle\Big{|}\frac{1}{N}\sum_{m\leq
N}F(S^{P(m)+r}x)-\frac{1}{N}\sum_{m\in
U_{N}}F(S^{P(m)+r}x)\Big{|}\leq\frac{\varepsilon}{4}\|F\|_{\sup}.$

But by (38),

$\displaystyle\sum_{m\in U_{N}}F(S^{P(m)+r}x)$
$\displaystyle=\sum_{\begin{subarray}{c}0\leq a<n_{k}\\\ a-r\in
R^{P}_{n_{k}}\\\ x_{k}(a)\neq?\end{subarray}}\sum_{\begin{subarray}{c}m\leq
N\\\ P(m)=a-r\\!\mod n_{k}\end{subarray}}F(S^{a}x)$
$\displaystyle=\sum_{\begin{subarray}{c}0\leq a<n_{k}\\\ a-r\in
R^{P}_{n_{k}}\\\ x_{k}(a)\neq?\end{subarray}}F(S^{a}x)\\#\\{m\leq
N:\>P(m)=a-r\\!\mod n_{k}\\}$ $\displaystyle=\sum_{\begin{subarray}{c}0\leq
a<n_{k}\\\ a-r\in R^{P}_{n_{k}}\\\
x_{k}(a)\neq?\end{subarray}}F(S^{a}x)\rho^{P}(N;n_{k},a-r).$

By (36), we have

$\Big{|}\rho^{P}(N;n_{k},a-r)-\rho^{P}(n_{k},a-r)\frac{N}{n_{k}}\Big{|}<\frac{\varepsilon}{8}\frac{N}{n_{k}}.$

It follows that

$\displaystyle\Big{|}\frac{1}{N}\sum_{m\in
U_{N}}F(S^{P(m)+r}x)-\frac{1}{n_{k}}\sum_{\begin{subarray}{c}0\leq a<n_{k}\\\
a-r\in R^{P}_{n_{k}}\\\
x_{k}(a)\neq?\end{subarray}}{\rho^{P}(n_{k},a-r)}F(S^{a}x)\Big{|}$
$\displaystyle=\Big{|}\frac{1}{N}\sum_{\begin{subarray}{c}0\leq a<n_{k}\\\
a-r\in R^{P}_{n_{k}}\\\
x_{k}(a)\neq?\end{subarray}}F(S^{a}x)\rho^{P}(N;n_{k},a-r)-\frac{1}{n_{k}}\sum_{\begin{subarray}{c}0\leq
a<n_{k}\\\ a-r\in R^{P}_{n_{k}}\\\
x_{k}(a)\neq?\end{subarray}}{\rho^{P}(n_{k},a-r)}F(S^{a}x)\Big{|}$
$\displaystyle\leq\frac{1}{N}\sum_{\begin{subarray}{c}0\leq a<n_{k}\\\ a-r\in
R^{P}_{n_{k}}\\\
x_{k}(a)\neq?\end{subarray}}|F(S^{a}x)|\Big{|}\rho^{P}(N;n_{k},a-r)-{\rho^{P}(n_{k},a-r)}\frac{N}{n_{k}}\Big{|}$
$\displaystyle\leq\|F\|_{\sup}\frac{\varepsilon}{8}\frac{\\#\\{0\leq
a<n_{k}:x_{k}(a)\neq?,a-r\in
R^{P}_{n_{k}}\\}}{n_{k}}\leq\|F\|_{\sup}\frac{\varepsilon}{8}.$

Together with (39), this gives (37), which completes the proof in the case of
$F$ depending only on the zero coordinate. The rest of the proof runs as in
the proof of Theorem 4.1, this is by passing to the Toeplitz sequences
$x^{(m)}\in(\mathcal{A}^{2m+1})^{\mathbb{Z}}$ for $m\geq 1$.

######  Remark 6.9.

Denote by ${\mathbb{P}}_{(n_{t})}$ the set of all prime divisors of elements
of the sequence $(n_{t})_{t\geq 1}$. In view of Corollary 6.3,
$?_{t}=o({p(n_{t})}/d^{\omega(n_{t})})$ implies (32). Unfortunately, if
${\mathbb{P}}_{(n_{t})}$ is finite then the sequence
$({p(n_{t})}/d^{\omega(n_{t})})_{t\geq 1}$ is bounded, so Theorem 6.8, in the
way, is not applicable. Fortunately, if ${\mathbb{P}}_{(n_{t})}$ is infinite
then ${p(n_{t})}/d^{\omega(n_{t})}\to+\infty$ as $t\to+\infty$, so Theorem 6.8
applies to a non-trivial class of regular Toeplitz shifts, in particular, it
applies when the periodic sequences $x_{t}$ defining $x$ have a bounded number
of “?”.

However, Theorem 6.8 applies to a much wider class of regular Toeplitz shifts
when $P(n)=n^{2}$. Then, by Corollary 6.7, $?_{t}=o(\sqrt{n_{t}})$ implies
(32). Here the finiteness or the infinity of the set ${\mathbb{P}}_{(n_{t})}$
does not matter.

The assumption (32) about the growth of the sequence $(?_{t})_{t\geq 1}$ is
the least restrictive when all $n_{t}$ are square-free. Then, by the second
part of Corollary 6.7, $?_{t}=o({n_{t}}/2^{\omega(n_{t})})$ implies (32).
Therefore, $?_{t}=O({n_{t}}^{1-\frac{1}{\log_{2}\log_{2}n_{t}}})$ also implies
(32). Indeed, it suffices to show that
$2^{\omega(n)}=o({n}^{\frac{1}{\log_{2}\log_{2}n}})$ for square-free numbers
$n\to+\infty$. Suppose that $\omega(n)=k$ and denote by $(p_{l})_{l\geq 1}$
the increasing sequence of all prime numbers. Since

$\ln n\geq\sum_{l=1}^{k}\ln p_{l}\geq k\ln k,$

we have

$\frac{2^{\omega(n)}}{{n}^{\frac{1}{\log_{2}\log_{2}n}}}=\frac{2^{k}}{{2}^{\frac{\log_{2}n}{\log_{2}\log_{2}n}}}\leq\frac{2^{k}}{2^{\frac{k\log_{2}k}{\log_{2}(k\log_{2}k)}}}=\frac{1}{2^{\frac{k\log_{2}\log_{2}k}{\log_{2}k+\log_{2}\log_{2}k}}}.$

As $\tfrac{k\log_{2}\log_{2}k}{\log_{2}k+\log_{2}\log_{2}k}\to+\infty$ when
$k\to+\infty$, this gives
$2^{\omega(n)}=o({n}^{\frac{1}{\log_{2}\log_{2}n}})$.

###  6.2. Counter-examples

We will show that there exists a regular Toeplitz sequence
$x\in\\{0,1\\}^{\mathbb{Z}}$ with the period structure $(n_{t})_{t\geq 1}$
satisfying

(40) $n_{t+1}=k_{t+1}n_{k}\text{ with }(k_{t+1},n_{t})=1,\;n_{t+1}\geq
2^{4}n_{t}^{2}\text{ and
}\sum_{p\in{\mathbb{P}}_{(n_{t})}}\tfrac{1}{p}<+\infty$

and such that

$\lim_{t\to\infty}\frac{1}{\sqrt{n_{t}}}\sum_{0\leq
m<\sqrt{n_{t}}}F(S^{m^{2}}x)\text{ does not exist,}$

where $F(y)=(-1)^{y(0)}$. Let

$0<\beta:=\frac{1}{16}\prod_{p\in{\mathbb{P}}_{(n_{t})}}\frac{p-1}{p}.$

By (31), for every $t\geq 1$, we have

(41) $\frac{2^{\omega(n_{t})}\widetilde{\psi}(n_{t})}{n_{t}}\geq 8\beta.$

Passing to a subsequence of $(n_{t})_{t\geq 1}$ (and remembering that
$\widetilde{\psi}(m)\to\infty$ when $m\to\infty$), we can assume that

$\sum_{t\geq 1}\frac{1}{\widetilde{\psi}(k_{t})}\leq\frac{1}{2}.$

Set

$\gamma_{t}:=\sum_{l=1}^{t}\frac{1}{\widetilde{\psi}(k_{l})}\;\big{(}\leq\frac{1}{2}\big{)}.$

At stage $t$, $x$ is approximated by the infinite concatenation of
$x_{t}[0,n_{t}-1]\in\\{0,1,?\\}^{n_{t}}$ (that is, we see a periodic sequence
of $0,1,?$ with period $n_{t}$). Successive “?” will be filled in in the next
steps of construction of $x$. We require that:

(42) $\displaystyle\\{0\leq i<n_{t}:\>x_{t}(i)=?\\}\subset R_{n_{t}};$ (43)
$\displaystyle\\#\\{a\in\widetilde{R}_{n_{t}}:\>x_{t}(a)=?\\}\geq(1-\gamma_{t})\widetilde{\psi}(n_{t});$
(44) $\displaystyle\\#\\{0\leq
m<\sqrt{n_{t}}:\>x_{t}(m^{2})=?\\}\geq\beta\sqrt{n_{t}}.$

Recall that, in view of Lemma 6.4 (remembering that
$P^{-1}(n_{t+1})=\sqrt{n_{t+1}}$), (30) and (40), for each
$a\in\widetilde{R}_{n_{t}}$, we have999${\mathbb{N}}^{2}$ stands for
$\\{m^{2}:m\geq 0\\}$.

$\displaystyle\\#($
$\displaystyle\\{a+jn_{t}:\>0<j<k_{t+1}\\}\cap{\mathbb{N}}^{2})\geq\\#(\\{m^{2}=a~{}\text{mod
}n_{t}:\>m^{2}<n_{t+1}\\})-1$
$\displaystyle\geq\Big{(}\frac{\sqrt{n_{t+1}}}{n_{t}}-1\Big{)}\rho(n_{t},a)-1\geq\Big{(}\frac{\sqrt{n_{t+1}}}{n_{t}}-1\Big{)}\frac{1}{2}2^{\omega(n_{t})}-1$
$\displaystyle\geq\frac{1}{2}2^{\omega(n_{t})}\Big{(}\frac{\sqrt{n_{t+1}}}{n_{t}}-2\Big{)}\geq\frac{1}{4}2^{\omega(n_{t})}\frac{\sqrt{n_{t+1}}}{n_{t}},$

so

(45)
$\\#(\\{a+jn_{t}:\>0<j<k_{t+1}\\}\cap{\mathbb{N}}^{2})\geq\frac{2^{\omega(n_{t})}}{4}\frac{\sqrt{n_{t+1}}}{n_{t}}.$

By the definition of the sets $R_{n}$ and $\widetilde{R}_{n}$, we have

(46) $\displaystyle R_{n_{t+1}}\subset\bigcup_{a\in
R_{n_{t}}}\\{a+jn_{t}:\>0\leq j<k_{t+1}\\},$ (47)
$\displaystyle\widetilde{R}_{n_{t+1}}\subset\bigcup_{a\in\widetilde{R}_{n_{t}}}\\{a+jn_{t}:\>0\leq
j<k_{t+1}\\}.$

Moreover, by Lemma 6.1, for every $a\in\widetilde{R}_{n_{t}}$, we have

(48) $\\#\\{i\in\widetilde{R}_{n_{t+1}}:i=a\\!\mod
n_{t}\\}=\\#\widetilde{R}_{k_{t+1}}=\widetilde{\psi}(k_{t+1}).$

We need to describe now which and how we fill "?" in $x_{t+1}[0,n_{t+1}-1]$.
This block is divided into $k_{t+1}$ subblocks

$\underbrace{x_{t}[0,n_{t}-1]x_{t}[0,n_{t}-1]\ldots
x_{t}[0,n_{t}-1]}_{k_{t+1}}.$

We fill in all "?" in the first block $x_{t}[0,n_{t}-1]$ in such a way to
“destroy” the convergence of averages in (40) for the time $n_{t}$, namely

$\frac{1}{\sqrt{n_{t}}}\sum_{0\leq
m<\sqrt{n_{t}}}F(S^{m^{2}}x)=\frac{1}{\sqrt{n_{t}}}\Big{(}\sum_{\begin{subarray}{c}m<\sqrt{n_{t}}\\\
x_{t}(m^{2})=0\end{subarray}}1-\sum_{\begin{subarray}{c}m<\sqrt{n_{t}}\\\
x_{t}(m^{2})=1\end{subarray}}1+\sum_{\begin{subarray}{c}m<\sqrt{n_{t}}\\\
x_{t}(m^{2})=?\end{subarray}}(-1)^{x(m^{2})}\Big{)}.$

And, since the number of $m$ in the last summand is at least
$\beta\sqrt{n_{t}}$ in view of (44), we can fill in these places at stage
$t+1$ to obtain the sum completely different that the known number which we
had from stage $t-1$. We also fill in (in an arbitrary way) the remaining
places in $\\{0,\ldots,n_{t}-1\\}$.

We fill in (in an arbitrary way) all places in
$\\{n_{t},\ldots,n_{t+1}-1\\}\setminus R_{n_{t+1}}$ and only these places, so
that (42) will be satisfied at stage $t+1$.

We must remember that for any $a\in R_{n_{t}}$ if $x_{t}(a)\neq?$ then for
every $0\leq j<k_{t+1}$, we have
$x_{t+1}(a+jn_{t})=x_{t}(a+jn_{t})=x_{t}(a)\neq?$. Moreover, for any
$a\in\widetilde{R}_{n_{t}}$ if $x_{t}(a)=?$ then for every $0<j<k_{t+1}$ with
$a+jn_{t}\in\widetilde{R}_{n_{t+1}}$ we have $x_{t+1}(a+jn_{t})=?$. In view of
(47), this gives

$\displaystyle\\#\\{$ $\displaystyle
i\in\widetilde{R}_{n_{t+1}}:x_{t+1}(i)\neq?\\}$
$\displaystyle\leq\widetilde{\psi}(n_{t})+\sum_{a\in\widetilde{R}_{n_{t}}:x_{t}(a)\neq?}\\#\\{a+jn_{t}\in\widetilde{R}_{n_{t+1}}:0<j<k_{t+1}\\}.$

In view of (48) and (43), it follows that

$\displaystyle\\#$
$\displaystyle\\{i\in\widetilde{R}_{n_{t+1}}:x_{t+1}(i)\neq?\\}\leq\widetilde{\psi}(n_{t})+(\widetilde{\psi}(k_{t+1})-1)\\#\\{a\in\widetilde{R}_{n_{t}}:x_{t}(a)\neq?\\}$
$\displaystyle\leq\widetilde{\psi}(n_{t})+(\widetilde{\psi}(k_{t+1})-1)\gamma_{t}\widetilde{\psi}(n_{t})=\Big{(}\gamma_{t}+\frac{1-\gamma_{t}}{\widetilde{\psi}(k_{t+1})}\Big{)}\widetilde{\psi}(n_{t+1})\leq\gamma_{t+1}\widetilde{\psi}(n_{t+1}).$

Therefore, at stage $t+1$, also (43) is satisfied.

A similar argument combined with (45), (43) and (41) shows that

$\displaystyle\\#\\{$ $\displaystyle 0\leq
m^{2}<n_{t+1}:x_{t+1}(m^{2})=?\\}=\\#\\{i\in
R_{n_{t+1}}\cap{\mathbb{N}}^{2}:x_{t+1}(i)=?\\}$ $\displaystyle\geq\sum_{a\in
R_{n_{t}}:x_{t}(a)=?}\\#\\{a+jn_{t}\in
R_{n_{t+1}}\cap{\mathbb{N}}^{2}:0<j<k_{t+1}\\}$
$\displaystyle\geq\sum_{a\in\widetilde{R}_{n_{t}}:x_{t}(a)=?}\frac{2^{\omega(n_{t})}}{4}\frac{\sqrt{n_{t+1}}}{n_{t}}=\frac{\sqrt{n_{t+1}}}{4n_{t}}2^{\omega(n_{t})}\\#\\{a\in\widetilde{R}_{n_{t}}:x_{t}(a)=?\\}$
$\displaystyle=(1-\gamma_{t})\frac{\sqrt{n_{t+1}}}{4n_{t}}2^{\omega(n_{t})}\widetilde{\psi}(n_{t})\geq\beta\sqrt{n_{t+1}}.$

Therefore, at stage $t+1$, also (44) is satisfied. This completes the
construction.

######  Remark 6.10.

In view of (42), in the constructed example of Toeplitz system $(X_{x},S)$ we
have $?_{t}\leq\psi(n_{t})$. Moreover, $\psi(n_{t})=o(\varphi(n_{t}))$.
Indeed, by Proposition 6.6, for every prime number $p$ we have
$\psi(p^{n})\leq p^{n-1}\tfrac{p+2}{2}$. It follows that

$\frac{\psi(p^{n})}{\varphi(p^{n})}\leq\frac{1}{2}\cdot\frac{p+2}{p-1}\leq\frac{3}{4}$

for all prime $p\geq 7$. It follows that

$\frac{\psi(n_{t})}{\varphi(n_{t})}=O\Big{(}\Big{(}\frac{3}{4}\Big{)}^{\omega(n_{t})}\Big{)}=o(1).$

Consequently, we have $?_{t}=o(\varphi(n_{t}))$. Therefore, in view of Theorem
4.1, $(X_{x},S)$ satisfies a PNT.

##  Appendix A The diameter of a tower

Let $x\in\mathcal{A}^{\mathbb{Z}}$ be a Toeplitz sequence with the periodic
structure given by $(n_{t})_{t\geq 1}$. Recall that

$\operatorname{Per}_{n_{t}}(x)=\\{a\in{\mathbb{Z}}:x(a+jn_{t})=x(a)\text{ for
all }j\in{\mathbb{Z}}\\}.$

Let
$\operatorname{Aper}_{n_{t}}(x):={\mathbb{Z}}\setminus\operatorname{Per}_{n_{t}}(x)$.
Then, we define the periodic sequence
$x_{t}\in(\mathcal{A}\cup\\{?\\})^{{\mathbb{Z}}}$ by: $x_{t}(k)=x(k)$ if
$k\in\operatorname{Per}_{n_{t}}(x)$ and $x_{t}(k)=?$ if
$k\in\operatorname{Aper}_{n_{t}}(x)$. Note that the density of the set
$\operatorname{Aper}_{n_{t}}(x)$ is equal to $\frac{?_{t}}{n_{t}}$, where

$?_{t}=\\#\\{0\leq
k<n_{t}:x_{t}(k)=?\\}=\\#(\operatorname{Aper}_{n_{t}}(x)\cap\\{0,1,\ldots,n_{t}-1\\}).$

It follows that the regularity of $(X_{x},S)$ is equivalent to
$?_{t}=o(n_{t})$.

######  Lemma A.1.

For any Toeplitz sequence $x\in\mathcal{A}^{\mathbb{Z}}$ we have

$?_{t}\leq\delta(E^{t})\leq 3?_{t}\text{ for every }t\geq 1.$

###### Proof.

First note that for every $0\leq j<n_{t}$ we have

$E^{t}_{j}=\\{y\in X_{x}:y(k-j)=x(k)=x_{t}(k)\text{ for all
}k\in\operatorname{Per}_{n_{t}}\\}.$

Moreover, if $k\in\operatorname{Aper}_{n_{t}}(x)$ then we can find $y,z\in
E^{t}_{j}$, so that $y(k-j)\neq z(k-j)$. It follows that

$\operatorname{diam}(E^{t}_{j})=2^{-\inf\\{|n|:n\in\operatorname{Aper}_{n_{t}}(x)-\\{j\\}\\}}.$

Suppose that

$\operatorname{Aper}_{n_{t}}(x)\cap\\{0,1,\ldots,n_{t}-1\\}=\\{l_{1},l_{2},\ldots,l_{s}\\}$

with $1\leq l_{1}\leq\ldots\leq l_{s}\leq n_{t}$ and $s=?_{t}$. Thus,
$\operatorname{diam}(E^{t}_{l_{i}})=1$ and if $l_{i-1}<j<l_{i}$
($l_{0}=l_{s}-n_{t}$ and $l_{s+1}=l_{1}+n_{t}$) then
$\operatorname{diam}(E^{t}_{j})=2^{-\min\\{j-l_{i-1},l_{i}-j\\}}$. Therefore,

$\delta(E^{t})=\sum_{0\leq
j<n_{t}}\operatorname{diam}(E^{t}_{j})\geq\sum_{i=1}^{s}\operatorname{diam}(E^{t}_{l_{i}})=s$

and

$\displaystyle\delta(E^{t})$ $\displaystyle=\sum_{0\leq
j<n_{t}}\operatorname{diam}(E^{t}_{j})=\sum_{i=1}^{s}\sum_{\frac{l_{i-1}+l_{i}}{2}\leq
j<\frac{l_{i}+l_{i+1}}{2}}\operatorname{diam}(E^{t}_{j})$
$\displaystyle=\sum_{i=1}^{s}\Big{(}1+\sum_{1\leq
j<\frac{l_{i+1}-l_{i}}{2}}2^{-j}+\sum_{1\leq
j\leq\frac{l_{i}-l_{i-1}}{2}}2^{-j}\Big{)}\leq 3s,$

which completes the proof.

As the regularity of $x$ is equivalent to $?_{t}=o(n_{t})$, we have the
following conclusion.

######  Corollary A.2.

A Toeplitz sequence is regular if and only if $\delta(E^{t})=o(n_{t})$.

##  Appendix B Sturmian dynamical systems satisfy a PNT

Let $T:{\mathbb{T}}\to{\mathbb{T}}$
(${\mathbb{T}}:={\mathbb{R}}/{\mathbb{Z}}$) be an irrational rotation on
${\mathbb{T}}$ by $\alpha$. For every non-zero $\beta\in{\mathbb{T}}$ let
$\\{A_{0},A_{1}\\}$ be the partition given by the intervals $A_{0}=[0,\beta)$
and $A_{1}=[\beta,1)$. For every $x\in{\mathbb{T}}$ denote by
$\bar{x}\in\\{0,1\\}^{\mathbb{Z}}$ the code of $x$ defined by $\bar{x}(k)=i$
if and only if $T^{k}x\in A_{i}$. Finally, denote by
$X_{\alpha,\beta}\subset\\{0,1\\}^{\mathbb{Z}}$ the closure of the set
$\\{\bar{x}\in\\{0,1\\}^{\mathbb{Z}}:x\in{\mathbb{T}}\\}$. Since
$X_{\alpha,\beta}$ is an invariant subset for the left shift $S$ on
$\\{0,1\\}^{\mathbb{Z}}$, we can focus the topological dynamical system
$S:X_{\alpha,\beta}\to X_{\alpha,\beta}$.

######  Theorem B.1.

For the topological dynamical system $S:X_{\alpha,\beta}\to X_{\alpha,\beta}$
a PNT holds.

###### Proof.

For every $y=(y(n))_{n\in{\mathbb{Z}}}\in X_{\alpha,\beta}$ the set
$\bigcap_{n\in{\mathbb{Z}}}\overline{A}_{y(n)}\subset{\mathbb{T}}$ has exactly
one element $\pi(y)\in{\mathbb{T}}$. Moreover,
$\pi:X_{\alpha,\beta}\to{\mathbb{T}}$ is a continuous map intertwining $S$ and
$T$ and there exists a unique $S$-invariant probability measure $\mu$ on
$X_{\alpha,\beta}$. The $\pi$-image of $\mu$ coincides with Lebesgue measure
on ${\mathbb{T}}$.

By Vinogradov’s theorem, for any character $f(x)=e^{2\pi inx}$,
$n\in{\mathbb{Z}}$, we have

(49)
$\lim_{N\to\infty}\frac{1}{\pi(N)}\sum_{p<N}f(T^{p}x)=\int_{{\mathbb{T}}}f(x)\,dx\text{
for every }x\in{\mathbb{T}}.$

Since every continuous function $f:{\mathbb{T}}\to{\mathbb{C}}$ is uniformly
approximated by trigonometric polynomials, (49) holds also for any continuous
$f$. Moreover, (49) holds for any Riemann integrable
$f:{\mathbb{T}}\to{\mathbb{R}}$. Indeed, for every $\varepsilon>0$ there are
two continuous functions $f_{-},f_{+}:{\mathbb{T}}\to{\mathbb{R}}$ such that
$f_{-}(x)\leq f(x)\leq f_{+}(x)$ for every $x\in{\mathbb{T}}$ and
$\int_{{\mathbb{T}}}(f_{+}(x)-f_{-}(x))dx<\varepsilon$. It follows that

$\displaystyle\limsup_{N\to\infty}\frac{1}{\pi(N)}\sum_{p<N}f(T^{p}x)$
$\displaystyle\leq\lim_{N\to\infty}\frac{1}{\pi(N)}\sum_{p<N}f_{+}(T^{p}x)$
$\displaystyle=\int_{{\mathbb{T}}}f_{+}(x)\,dx<\int_{{\mathbb{T}}}f(x)\,dx+\varepsilon$

and

$\displaystyle\liminf_{N\to\infty}\frac{1}{\pi(N)}\sum_{p<N}f(T^{p}x)$
$\displaystyle\geq\lim_{N\to\infty}\frac{1}{\pi(N)}\sum_{p<N}f_{-}(T^{p}x)$
$\displaystyle=\int_{{\mathbb{T}}}f_{-}(x)\,dx>\int_{{\mathbb{T}}}f(x)\,dx-\varepsilon.$

As $\varepsilon>0$ can be chosen freely, this gives (49).

Suppose that $f:X_{\alpha,\beta}\to{\mathbb{R}}$ depends only on finitely many
coordinates. More precisely, assume that $f(y)=g(y(-n),\ldots,y(n))$ for some
$g:\\{0,1\\}^{2n+1}\to{\mathbb{R}}$. Then there exists
$F:{\mathbb{T}}\to{\mathbb{R}}$ such that $f=F\circ\pi$ and $F$ is constant on
the atoms of the partition $\bigvee_{i=-n}^{n}T^{-i}\\{A_{0},A_{1}\\}$ (for
example, if $n=0$ and $f$ is the characteristic function of $\\{y\in
X_{\alpha,\beta}:\>y(0)=0\\}$ then $F$ is $\mathbf{1}_{A_{0}}$). It follows
that $F$ is Riemann integrable. Therefore, for every $y\in X_{\alpha,\beta}$,
we have

$\displaystyle\frac{1}{\pi(N)}\sum_{p<N}f(S^{p}y)=\frac{1}{\pi(N)}\sum_{p<N}F(T^{p}\pi(y))\to\int_{{\mathbb{T}}}F(x)dx=\int_{X_{\alpha,\beta}}f\,d\mu.$

Since every continuous function $f:X_{\alpha,\beta}\to{\mathbb{R}}$ is
uniformly approximated by functions depending on finitely many coordinates,

$\frac{1}{\pi(N)}\sum_{p<N}f(S^{p}y)\to\int_{X_{\alpha,\beta}}f\,d\mu\text{
for any }y\in X_{\alpha,\beta}$

holds for every continuous $f$.

## References

  * [1] H. Abdalaoui, M. Lemańczyk, S. Kasjan, 0-1 sequences of the Thue-Morse type and Sarnak’s conjecture, Proc. Amer. Math. Soc. 144 (2016), no. 1, 161-176.
  * [2] M. Boyle, D. Fiebig, U. Fiebig, _Residual entropy, conditional entropy and subshift covers_ , Forum Math. 14 (2002), 713-757.
  * [3] J. Bourgain, _An approach to pointwise ergodic theorems_ , In Geometric aspects of functional analysis (1986/87), volume 1317 of Lecture Notes in Math., pages 204-223. Springer, Berlin, 1988.
  * [4] J. Bourgain, _Möbius-Walsh correlation bounds and an estimate of Mauduit and Rivat_ , J. Anal. Math. 119 (2013), 147-163.
  * [5] J. Bourgain, _On the correlation of the Möbius function with rank-one systems_ , J. Anal. Math. 120 (2013), 105–130.
  * [6] P.G.L. Dirichlet, _Lectures on number theory. Supplements by R. Dedekind._ Translated from the 1863 German original and with an introduction by John Stillwell. History of Mathematics, 16. American Mathematical Society, Providence, RI; London Mathematical Society, London, 1999. xx+275 pp.
  * [7] T. Downarowicz, _Survey of odometers and Toeplitz flows_. Algebraic and topological dynamics, 7–37, Contemp. Math., 385, Amer. Math. Soc., Providence, RI, 2005.
  * [8] S. Ferenczi, J. Kułaga-Przymus, M. Lemańczyk, _Sarnak’s Conjecture – what’s new_ , in: Ergodic Theory and Dynamical Systems in their Interactions with Arithmetics and Combinatorics, CIRM Jean-Morlet Chair, Fall 2016, Editors: S. Ferenczi, J. Kułaga-Przymus, M. Lemańczyk, Lecture Notes in Mathematics 2213, Springer International Publishing, pp. 418.
  * [9] S. Ferenczi, C. Mauduit, _On Sarnak’s conjecture and Veech’s question for interval exchanges_ , J. Anal. Math. 134 (2018), 545–573.
  * [10] B. Green, _On (not) computing the Möbius function using bounded depth circuits_ , Combin. Probab. Comput. 21 (2012), 942-951.
  * [11] B. Green, T. Tao, _The Möbius function is strongly orthogonal to nilsequences_ , Annals of Math. (2), 175 (2012), 541-566.
  * [12] ]A. Kanigowski, M. Lemańczyk, M. Radziwiłł, Rigidity in dynamics and Möbius disjointness, arXiv:1905.13256 (submitted).
  * [13] A. Kanigowski, M. Lemańczyk, M. Radziwiłł, _Prime number theorem for analytic skew products_ , in preparation.
  * [14] A. Kanigowski, M. Lemańczyk, M. Radziwiłł, _Semiprime number theorem for smooth Anzai skew products_ , in preparation.
  * [15] C. Mauduit, J. Rivat, _Prime numbers along Rudin–Shapiro sequences_ , J. Eur. Math. Soc. 17 (2015), 2595–2642.
  * [16] C. Müllner, _Automatic sequences fulfill the Sarnak conjecture_ , Duke Math. J. 166 (2017), 3219-3290.
  * [17] W. Narkiewicz, _Number theory_. Translated from the Polish by S. Kanemitsu. World Scientific Publishing Co., Singapore; distributed by Heyden & Son, Inc., Philadelphia, PA, 1983. xii+371 pp.
  * [18] R. Pavlov, _Some counterexamples in topological dynamics_ , Ergodic Theory Dynam. Systems 28 (2008), 1291-1322.
  * [19] P. Sarnak, Three lectures on the Möbius function, randomness and dynamics, http://publications.ias.edu/sarnak/.
  * [20] P. Sarnak, Möbius randomness and Dynamics six years later at CIRM at 1h 08 minute https://library.cirm-math.fr/Record.htm?idlist=1&record=19282918124910001909
  * [21] I.M. Vinogradov, _The method of trigonometrical sums in the theory of numbers_ , (Russian) Trav. Inst. Math. Stekloff 23, (1947). 109 pp.
  * [22] M. Wierdl, _Pointwise ergodic theorem along the prime numbers_ , Israel J. Math. 64 (1989), 315-336.