3.1 Notation

For a real number $u$ , we let $\text{e}(u)=\exp (2\unicode[STIX]{x1D70B}\text{i}u)$ .

For a real number $c$ , we use Knuth’s notation for the falling factorials defined recursively by $c^{\text{}\underline{0}}=1$ and $c^{\text{}\underline{k}}=c^{\text{}\underline{k-1}}(c-k+1)$ .

For $k$ a positive integer and $h=(h_{1},h_{2},\ldots ,h_{k})\in \mathbb{R}^{k}$ , we let $\Vert h\Vert _{\infty }=\max \{|h_{1}|,\ldots ,|h_{k}|\}$ .

For a real number $x$ , we let $x=\lfloor x\rfloor +\{x\}$ be its only decomposition as a sum of an integer and an element in $[0,1)$ . We notice that the map $x\mapsto \{x\}$ allows us to identify $\mathbb{T}=\mathbb{R}/\mathbb{Z}$ and the interval $[0,1)$ . We let $\Vert x\Vert =\min \{\{x\},1-\{x\}\}$ be the so-called distance of $x$ to the nearest integer. For a positive integer $k$ , we identify $\mathbb{T}^{k}$ and $[0,1)^{k}$ . An interval $I$ in $[0,1)^{k}$ is a Cartesian product $\prod _{1\leqslant i\leqslant k}[a_{i},b_{i})$ with $0\leqslant a_{i}\leqslant b_{i}\leqslant 1$ for $1\leqslant i\leqslant k$ ; its Lebesgue measure $\prod _{1\leqslant i\leqslant k}(b_{i}-a_{i})$ is denoted by $\unicode[STIX]{x1D706}(I)$ . For an interval $I\subset [0,1)^{k}$ , we denote by $\unicode[STIX]{x1D712}_{I}$ its indicator (also called characteristic) function.

The discrepancy of a finite set $X=\{x_{1},x_{2},\ldots ,x_{N}\}$ of elements of $\mathbb{R}^{k}$ is defined by

(1) $$\begin{eqnarray}D_{N}(X)=D_{N}(x_{1},x_{2},\ldots ,x_{N})=\sup _{I\subset [0,1)^{k}}\bigg|\frac{1}{N}\mathop{\sum }_{n=1}^{N}\unicode[STIX]{x1D712}_{I}(\{x_{n}\})-\unicode[STIX]{x1D706}(I)\bigg|.\end{eqnarray}$$

3.2 Trigonometric sums over polynomials

Proposition 1. Let $k\geqslant 1$ and $P(n)=\sum _{i=0}^{k}\unicode[STIX]{x1D6FC}_{i}n^{i}$ be a polynomial of degree $k$ with real coefficients. Let $q,R,h$ be positive integers and $p$ an integer such that

(2) $$\begin{eqnarray}\gcd (p,q)=1,\quad \bigg|\unicode[STIX]{x1D6FC}_{k}-\frac{p}{q}\bigg|\leqslant \frac{1}{q^{2}}\quad \text{and}\quad 2hk!R^{2-1/2^{k-2}}\leqslant q.\end{eqnarray}$$

For $N\geqslant R$ , we have

(3) $$\begin{eqnarray}\frac{1}{N}\bigg|\mathop{\sum }_{1\leqslant n\leqslant N}\text{e}(hP(n))\bigg|~\ll _{k}~\left(\frac{1}{R}+\frac{q}{N}\right)^{1/2^{k-1}}.\end{eqnarray}$$

Proof. Our first step is to use, for $k\geqslant 2$ , the Weyl–van der Corput method to reduce the evaluation of the left-hand side of (3) to the evaluation of geometric sums. We apply Lemma 2.7 of [Reference Graham and Kolesnik8] with

(4) $$\begin{eqnarray}\displaystyle \begin{array}{@{}c@{}}q=k-1,\quad Q=2^{k-1},\quad I=(0,N],\\ H_{j}=R_{j}=R^{1/2^{k-1-j}}\quad \text{for }1\leqslant j\leqslant k-1,\end{array} & & \displaystyle\end{eqnarray}$$

noting that the condition $R\leqslant N=|I|$ is fulfilled, and get

(5) $$\begin{eqnarray}\displaystyle & & \displaystyle \frac{1}{N}\bigg|\mathop{\sum }_{1\leqslant n\leqslant N}\text{e}(hP(n))\bigg|\ll \Bigg(\frac{1}{R}+\frac{1}{NR_{1}\cdots R_{k-1}}\nonumber\\ \displaystyle & & \displaystyle \times \mathop{\sum }_{\substack{ 1\leqslant r_{1}\leqslant R_{1} \\ \ldots \\ 1\leqslant r_{k-1}\leqslant R_{k-1}}}\bigg|\mathop{\sum }_{n=1}^{N-r_{1}-\cdots -r_{k-1}}\text{e}(\unicode[STIX]{x1D6FC}_{k}hk!r_{1}\cdots r_{k-1}n)\bigg|\Bigg)^{1/2^{k-1}}.\end{eqnarray}$$

Let now $\ell =hk!r_{1}\cdots r_{k-1}$ ; for any $M$ , we have

$$\begin{eqnarray}\bigg|\mathop{\sum }_{n=1}^{M}\text{e}(\unicode[STIX]{x1D6FC}_{k}\ell n)\bigg|\leqslant \frac{2}{|\text{e}(\unicode[STIX]{x1D6FC}_{k}\ell )-1|}=\frac{1}{|\text{sin}(\unicode[STIX]{x1D70B}\unicode[STIX]{x1D6FC}_{k}\ell )|}.\end{eqnarray}$$

We are thus looking for a lower bound for $|\text{sin}(\unicode[STIX]{x1D70B}\unicode[STIX]{x1D6FC}_{k}\ell )|$ . We have

$$\begin{eqnarray}|\text{sin}(\unicode[STIX]{x1D70B}\unicode[STIX]{x1D6FC}_{k}\ell )|=\bigg|\text{sin}\bigg(\unicode[STIX]{x1D70B}\frac{\ell p}{q}+\unicode[STIX]{x1D70B}\ell \bigg(\unicode[STIX]{x1D6FC}_{k}-\frac{p}{q}\bigg)\bigg)\bigg|.\end{eqnarray}$$

Relation (2) implies that $1\leqslant \ell \leqslant q-1$ (in particular, $q\geqslant 2$ ) and $\gcd (p,q)=1$ : the number $\ell p$ is never $0$ modulo $q$ . On the other hand, we have

$$\begin{eqnarray}\bigg|\ell \bigg(\unicode[STIX]{x1D6FC}_{k}-\frac{p}{q}\bigg)\bigg|\leqslant \frac{\ell }{q^{2}}\leqslant \frac{1}{2q}.\end{eqnarray}$$

The last two relations imply that

$$\begin{eqnarray}|\text{sin}(\unicode[STIX]{x1D70B}\unicode[STIX]{x1D6FC}_{k}\ell )|\geqslant \sin \bigg(\frac{\unicode[STIX]{x1D70B}}{2q}\bigg)\geqslant \frac{1}{q}\end{eqnarray}$$

and so for any $M$ one has $|\sum _{n=1}^{M}\,\text{e}(\unicode[STIX]{x1D6FC}_{k}\ell n)|\leqslant q$ . This easily implies the validity of Proposition 1 when $k\geqslant 2$ .

The case when $k=1$ is now straightforward. We have

$$\begin{eqnarray}\frac{1}{N}\bigg|\mathop{\sum }_{1\leqslant n\leqslant N}\text{e}(hP(n))\bigg|=\frac{1}{N}\bigg|\mathop{\sum }_{1\leqslant n\leqslant N}\text{e}(\unicode[STIX]{x1D6FC}_{k}hn)\bigg|.\end{eqnarray}$$

Relation (2) implies that $2h\leqslant q$ and the previous reasoning implies that

$$\begin{eqnarray}\frac{1}{N}\bigg|\mathop{\sum }_{1\leqslant n\leqslant N}\text{e}(hP(n))\bigg|\ll \frac{q}{N}\end{eqnarray}$$

and (3) is satisfied for any value of $R$ .◻

3.3 Trigonometric sums involving the function $n^{c}$ at consecutive arguments

Proposition 2. Let $c>1$ be a non-integral real number, let $L=\lfloor c\rfloor ~+~1$ and let $m$ be a positive integer. For any $L$ -tuple $h=(h_{0},h_{1},\ldots ,h_{L-1})$ of integers which are not all $0$ and any positive integer $N$ , we have

$$\begin{eqnarray}\mathop{\sum }_{n=N}^{2N-1}\text{e}\bigg(\frac{1}{m}\mathop{\sum }_{\ell =0}^{L-1}h_{\ell }(n+\ell )^{c}\bigg)~\ll _{L,c,m}~\Vert h\Vert _{\infty }\,N^{1-\Vert c\Vert /2^{(c+1)}}\end{eqnarray}$$

as soon as

$$\begin{eqnarray}\Vert h\Vert _{\infty }=o(N^{1-\{c\}}).\end{eqnarray}$$

Proof. In order to apply classical upper bounds for trigonometrical sums, we need to have a lower and an upper bound for the absolute value of some derivative of the function $f$ defined by $f(x)=(1/m)\sum _{\ell =0}^{L-1}h_{\ell }(x+\ell )^{c}$ .

If $(1/m)\sum _{\ell =0}^{L-1}h_{\ell }\neq 0$ , then for $x\in [N,2N-1]$ and any integer $k\leqslant c+1$ we have

$$\begin{eqnarray}N^{c-k}~\ll _{L,c,m}~|f^{(k)}(x)|~\ll _{L,c,m}~\Vert h\Vert _{\infty }N^{c-k},\end{eqnarray}$$

which is fine for our purpose.

But if $\sum _{\ell =0}^{L-1}h_{\ell }=0$ , the order of magnitude of $f^{(k)}$ is no longer $N^{c-k}$ . In that case, we use the Taylor expansion for $(x+\ell )^{c}$ ; the next term is now $(c/m)\sum _{\ell =0}^{L-1}h_{\ell }\ell (x+\ell )^{c-1}$ . If $\sum _{\ell =0}^{L-1}h_{\ell }\ell \neq 0$ , we have $N^{c-1-k}~\ll _{L,c,m}~|f^{(k)}(x)|~\ll _{L,c,m}~\Vert h\Vert _{\infty }N^{c-1-k}$ and we are done; if $\sum _{\ell =0}^{L-1}h_{\ell }\ell =0$ , we go to the next term in the Taylor expansion and so on.

However, since the vector $h$ is non-zero, there exists $r\in [0,L-1]$ such that

(6) $$\begin{eqnarray}\mathop{\sum }_{\ell =0}^{L-1}h_{\ell }\ell ^{r}\neq 0:\end{eqnarray}$$

if it were not the case, we would have $Ah=0$ , where $A=(j^{i})_{0\leqslant i,j\leqslant L-1}$ is the transposed matrix of an invertible Vandermonde matrix and $h$ a non-zero vector, which is not possible.

Let $r$ be the smallest non-negative integer for which (6) holds. For $k\leqslant c+1$ , we have

(7) $$\begin{eqnarray}N^{c-r-k}~\ll _{L,c,m}~|f^{(k)}(x)|~\ll _{L,c,m}~\Vert h\Vert _{\infty }N^{c-r-k}.\end{eqnarray}$$

Let us first assume that $0\leqslant r\leqslant L-3$ , a case which may occur only when $c>2$ . We let

$$\begin{eqnarray}q=\lfloor c\rfloor -r-1.\end{eqnarray}$$

We notice that

$$\begin{eqnarray}q\geqslant L-1-(L-3)-1=1\end{eqnarray}$$

and that

$$\begin{eqnarray}c-r-(q+2)=c-r-\lfloor c\rfloor +r+1-2=c-\lfloor c\rfloor -1=\{c\}-1.\end{eqnarray}$$

For $x\in [N,2N-1]$ , we have

$$\begin{eqnarray}N^{\{c\}-1}~\ll _{L,c,m}~|f^{(q+2)}(x)|~\ll _{L,c,m}~\Vert h\Vert _{\infty }\,N^{\{c\}-1}.\end{eqnarray}$$

We let

$$\begin{eqnarray}\unicode[STIX]{x1D706}=\min _{x\in [N,2N-1]}|f^{(q+2)}(x)|\quad \text{and}\quad \unicode[STIX]{x1D6FC}\unicode[STIX]{x1D706}=\max _{x\in [N,2N-1]}|f^{(q+2)}(x)|.\end{eqnarray}$$

The previous double inequality implies that there are constants $\unicode[STIX]{x1D705}_{1}$ and $\unicode[STIX]{x1D705}_{2}$ depending at most on $L,c,m$ such that

$$\begin{eqnarray}\unicode[STIX]{x1D706}=\unicode[STIX]{x1D705}_{1}N^{\{c\}-1}\quad \text{and}\quad 1\leqslant \unicode[STIX]{x1D6FC}\leqslant \unicode[STIX]{x1D705}_{2}\Vert h\Vert _{\infty }.\end{eqnarray}$$

Theorem 2.8 of [Reference Graham and Kolesnik8] implies that we have, with $Q=2^{q}$ ,

$$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{n=N}^{2N-1}\text{e}\bigg(\frac{1}{m}\mathop{\sum }_{\ell =0}^{L-1}h_{\ell }(n+\ell )^{c}\bigg)\nonumber\\ \displaystyle & & \displaystyle \quad \ll _{L,c,m}~N(\Vert h\Vert _{\infty }^{2}N^{\{c\}-1})^{1/(4Q-2)}+N^{1-1/2Q}\Vert h\Vert _{\infty }^{1/2Q}\nonumber\\ \displaystyle & & \displaystyle \qquad +\,N^{1-2/Q+1/Q^{2}}N^{(\{c\}-1)/2Q}.\nonumber\end{eqnarray}$$

Using the inequalities

$$\begin{eqnarray}1\leqslant Q\leqslant 2Q\leqslant 4Q-2\leqslant 4\times 2^{c-1}-2\leqslant 2^{c+1}-2\quad \text{and}\quad \{c\}-1\geqslant -\Vert c\Vert ,\end{eqnarray}$$

one obtains Proposition 2.

Let us now assume that $r=L-2=\lfloor c\rfloor -1$ . In this case, we have $c-r-2=c-(\lfloor c\rfloor -1)-2=\{c\}-1$ and, thanks to (7), for $x\in [N,2N-1]$ , we have

$$\begin{eqnarray}N^{\{c\}-1}~\ll _{L,c,m}~|f^{(2)}(x)|~\ll _{L,c,m}~\Vert h\Vert _{\infty }\,N^{\{c\}-1}.\end{eqnarray}$$

We let

$$\begin{eqnarray}\unicode[STIX]{x1D706}=\min _{x\in [N,2N-1]}|f^{(2)}(x)|\quad \text{and}\quad \unicode[STIX]{x1D6FC}\unicode[STIX]{x1D706}=\max _{x\in [N,2N-1]}|f^{(2)}(x)|.\end{eqnarray}$$

The previous double inequality implies that there are constants $\unicode[STIX]{x1D705}_{1}$ and $\unicode[STIX]{x1D705}_{2}$ depending at most on $L,c,m$ such that

$$\begin{eqnarray}\unicode[STIX]{x1D706}=\unicode[STIX]{x1D705}_{1}N^{\{c\}-1}\quad \text{and}\quad 1\leqslant \unicode[STIX]{x1D6FC}\leqslant \unicode[STIX]{x1D705}_{2}\Vert h\Vert _{\infty }.\end{eqnarray}$$

Theorem 2.2 of [Reference Graham and Kolesnik8] implies that we have

$$\begin{eqnarray}\mathop{\sum }_{n=N}^{2N-1}\text{e}\bigg(\frac{1}{m}\mathop{\sum }_{\ell =0}^{L-1}h_{\ell }(n+\ell )^{c}\bigg)~\ll _{L,c,m}~N\Vert h\Vert _{\infty }N^{(\{c\}-1)/2}+N^{(1-\{c\})/2},\end{eqnarray}$$

in which case, Proposition 2 is satisfied.

We now consider the last case, when $r=L-1$ . In this case, we have $c-r-1=c-(\lfloor c\rfloor )-1=\{c\}-1$ and so

$$\begin{eqnarray}N^{\{c\}-1}~\ll _{L,c,m}~|f^{\prime }(x)|~\ll _{L,c,m}~\Vert h\Vert _{\infty }\,N^{\{c\}-1}.\end{eqnarray}$$

Since, by hypothesis, the last term is $o(1)$ , we can apply the Kusmin–Landau lemma (Theorem 2.1 of [Reference Graham and Kolesnik8]) and obtain

$$\begin{eqnarray}\mathop{\sum }_{n=N}^{2N-1}\text{e}\bigg(\frac{1}{m}\mathop{\sum }_{\ell =0}^{L-1}h_{\ell }(n+\ell )^{c}\bigg)~\ll _{L,c,m}~N^{1-\{c\}},\end{eqnarray}$$

in which case, Proposition 2 is again satisfied.◻

3.4 Discrepancy of a perturbed sequence

We will make use of the following elementary property.

Proposition 3. Let $N\geqslant 1$ , $\unicode[STIX]{x1D6FF}\geqslant 0$ and $x_{1},x_{2},\ldots ,x_{N}$ and $y_{1},y_{2},\ldots ,y_{N}$ be two families of real numbers such that for all $n\leqslant N$ we have $|y_{n}-x_{n}|\leqslant \unicode[STIX]{x1D6FF}$ . Then we have

$$\begin{eqnarray}D_{N}(y_{1},y_{2},\ldots ,y_{N})\leqslant 2D_{N}(x_{1},x_{2},\ldots ,x_{N})+2\unicode[STIX]{x1D6FF}.\end{eqnarray}$$

Proof. Let $I=[a,b)\subset [0,1)$ . We let $I_{\unicode[STIX]{x1D6FF}}^{+}=([a-\unicode[STIX]{x1D6FF},b+\unicode[STIX]{x1D6FF})+\mathbb{Z})\cap [0,1)$ and notice that $I_{\unicode[STIX]{x1D6FF}}^{+}$ is either an interval or the union of two intervals; we let $I_{\unicode[STIX]{x1D6FF}}^{-}$ be the interval $[a+\unicode[STIX]{x1D6FF},b-\unicode[STIX]{x1D6FF})$ if $b-a>2\unicode[STIX]{x1D6FF}$ or the empty set otherwise. We have

$$\begin{eqnarray}I_{\unicode[STIX]{x1D6FF}}^{-}\subset I\subset I_{\unicode[STIX]{x1D6FF}}^{+},\qquad \unicode[STIX]{x1D706}(I_{\unicode[STIX]{x1D6FF}}^{+})\leqslant \unicode[STIX]{x1D706}(I)+2\unicode[STIX]{x1D6FF}\quad \text{and}\quad \unicode[STIX]{x1D706}(I_{\unicode[STIX]{x1D6FF}}^{-})\geqslant \unicode[STIX]{x1D706}(I)-2\unicode[STIX]{x1D6FF}.\end{eqnarray}$$

We thus have

$$\begin{eqnarray}\displaystyle \mathop{\sum }_{1\leqslant n\leqslant N}\unicode[STIX]{x1D712}_{I}(y_{n})-\unicode[STIX]{x1D706}(I) & {\leqslant} & \displaystyle \mathop{\sum }_{1\leqslant n\leqslant N}\unicode[STIX]{x1D712}_{I_{\unicode[STIX]{x1D6FF}^{+}}}(x_{n})-\unicode[STIX]{x1D706}(I)\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \unicode[STIX]{x1D706}(I_{\unicode[STIX]{x1D6FF}}^{+})+2D_{N}(x_{1},\ldots ,x_{N})-\unicode[STIX]{x1D706}(I)\nonumber\\ \displaystyle & {\leqslant} & \displaystyle 2D_{N}(x_{1},\ldots ,x_{N})+2\unicode[STIX]{x1D6FF}\nonumber\end{eqnarray}$$

and

$$\begin{eqnarray}\displaystyle \mathop{\sum }_{1\leqslant n\leqslant N}\unicode[STIX]{x1D712}_{I}(y_{n})-\unicode[STIX]{x1D706}(I) & {\geqslant} & \displaystyle \mathop{\sum }_{1\leqslant n\leqslant N}\unicode[STIX]{x1D712}_{I_{\unicode[STIX]{x1D6FF}^{-}}}(x_{n})-\unicode[STIX]{x1D706}(I)\nonumber\\ \displaystyle & {\geqslant} & \displaystyle \unicode[STIX]{x1D706}(I_{\unicode[STIX]{x1D6FF}}^{-})-D_{N}(x_{1},\ldots ,x_{N})-\unicode[STIX]{x1D706}(I)\nonumber\\ \displaystyle & {\geqslant} & \displaystyle -D_{N}(x_{1},\ldots ,x_{N})-2\unicode[STIX]{x1D6FF},\nonumber\end{eqnarray}$$

which implies that

$$\begin{eqnarray}D_{N}(y_{1},y_{2},\ldots ,y_{N})\leqslant 2D_{N}(x_{1},\ldots ,x_{N})+2\unicode[STIX]{x1D6FF}.\Box\end{eqnarray}$$

3.5 The multidimensional Erdős–Turán theorem

For the case $k=1$ , Erdős and Turán [Reference Erdős and Turán7] gave an upper bound for the discrepancy in terms of exponential sums. Their result has been generalized by Koksma [Reference Koksma10] and Szüsz [Reference Szüsz23] in the multidimensional case. The version we give is taken from [Reference Drmota and Tichy6, Theorem 1.21, p. 15].

Proposition 4. Let $X=\{x_{1},x_{2},\ldots ,x_{N}\}$ be a finite set of elements of $\mathbb{R}^{k}$ and $H$ an arbitrary positive integer. We have

(8) $$\begin{eqnarray}D_{N}(X)\leqslant \bigg(\frac{3}{2}\bigg)^{k}\bigg(\frac{2}{H+1}+\mathop{\sum }_{0<\Vert h\Vert _{\infty }\leqslant H}\frac{1}{r(h)}\bigg|\frac{1}{N}\mathop{\sum }_{n=1}^{N}\text{e}(h\cdot x_{n})\bigg|\bigg),\end{eqnarray}$$

where, for $h=(h_{1},h_{2},\ldots ,h_{k})\in \mathbb{Z}^{k}$ , we let $r(h)=\prod _{i=1}^{k}\max \{1,|h_{i}|\}$ and $u\cdot v$ denotes the usual scalar product of two elements $u$ and $v$ in $\mathbb{R}^{k}$ .

3.6 Discrepancy of a polynomial sequence

We give here an upper bound for the discrepancy of a polynomial sequence in terms of rational approximations of its coefficients. This will be useful for the proof of Theorem 2.

Proposition 5. Let $P(x)=\sum _{i=0}^{d}\unicode[STIX]{x1D6FC}_{i}x^{i}$ be a polynomial of degree $d$ with real coefficients. For $i\in [1,d]$ , we let $Q_{i}$ , $q_{i}$ and $p_{i}$ be rational integers such that

(9) $$\begin{eqnarray}\gcd (p_{i},q_{i})=1,\qquad 1\leqslant q_{i}\leqslant Q_{i}\quad \text{and}\quad \bigg|\unicode[STIX]{x1D6FC}_{i}-\frac{p_{i}}{q_{i}}\bigg|\leqslant \frac{1}{q_{i}\cdot Q_{i}}.\end{eqnarray}$$

Then we have for any $k$ such that $1\leqslant k\leqslant d$ ,

(10) $$\begin{eqnarray}\displaystyle D_{N}(P(1),\ldots ,P(N))~\ll _{d}~q^{k}\log (eq_{k})\bigg(\frac{1}{q_{k}^{1/2}}+\frac{q_{k}}{N}\bigg)^{1/2^{(k-1)}}+q_{k}^{1/2^{k}}\mathop{\sum }_{i=k+1}^{d}\frac{N^{i}}{Q_{i}}, & & \displaystyle \nonumber\\ \displaystyle & & \displaystyle\end{eqnarray}$$

where $q:=\prod _{i=k+1}^{d}q_{i}$ .

Proof. We want to separate the contribution of the different $\unicode[STIX]{x1D6FC}_{k}$ to the discrepancy. Relation (10) is trivially true when $q_{k}=1$ and we may assume that $q_{k}\geqslant 2$ ; since $p_{k}$ and $q_{k}$ are coprime, $p_{k}$ is different from $0$ and so is $\unicode[STIX]{x1D6FC}_{k}$ . We approximate the higher degree coefficients by rational numbers. We define

$$\begin{eqnarray}\displaystyle y_{n}:=\mathop{\sum }_{i=0}^{k}\unicode[STIX]{x1D6FC}_{i}n^{i}+\mathop{\sum }_{i=k+1}^{d}\frac{p_{i}}{q_{i}}n^{i},\quad z_{n}:=\mathop{\sum }_{i=k+1}^{d}\bigg(\unicode[STIX]{x1D6FC}_{i}-\frac{p_{i}}{q_{i}}\bigg)n^{i} & & \displaystyle \nonumber\end{eqnarray}$$

with the usual convention that $z_{n}=0$ when $k=d$ .

In order to apply the original one-dimensional Erdős–Turán inequality, we have to estimate trigonometrical sums. We have

$$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{0<h\leqslant H}\frac{1}{h}\bigg|\frac{1}{N}\mathop{\sum }_{n\leqslant N}\text{e}(hP(n))\bigg|=\mathop{\sum }_{0<h\leqslant H}\frac{1}{h}\bigg|\frac{1}{N}\mathop{\sum }_{n\leqslant N}\text{e}(h(y_{n}+z_{n}))\bigg|\nonumber\\ \displaystyle & & \displaystyle \quad =\mathop{\sum }_{0<h\leqslant H}\frac{1}{h}\bigg|\frac{1}{N}\mathop{\sum }_{n\leqslant N}\text{e}(hy_{n})+\frac{1}{N}\mathop{\sum }_{n\leqslant N}\text{e}(hy_{n})(\text{e}(hz_{n})-1)\bigg|\nonumber\\ \displaystyle & & \displaystyle \quad \leqslant \mathop{\sum }_{0<h\leqslant H}\frac{1}{h}\bigg(\bigg|\frac{1}{N}\mathop{\sum }_{n\leqslant N}\text{e}(hy_{n})\bigg|+\frac{1}{N}\mathop{\sum }_{n\leqslant N}|\text{e}(hy_{n})(\text{e}(hz_{n})-1)|\bigg)\nonumber\\ \displaystyle & & \displaystyle \quad \leqslant \mathop{\sum }_{0<h\leqslant H}\frac{1}{h}\bigg|\frac{1}{N}\mathop{\sum }_{n\leqslant N}\text{e}(hy_{n})\bigg|+\mathop{\sum }_{0<h\leqslant H}\frac{1}{hN}\mathop{\sum }_{n\leqslant N}2\unicode[STIX]{x1D70B}|hz_{n}|.\nonumber\end{eqnarray}$$

The last sum is easily treated thanks to (9). We have

$$\begin{eqnarray}\mathop{\sum }_{0<h\leqslant H}\frac{1}{hN}\mathop{\sum }_{n\leqslant N}2\unicode[STIX]{x1D70B}|hz_{n}|\leqslant 2\unicode[STIX]{x1D70B}H\mathop{\sum }_{i=k+1}^{d}\frac{N^{i}}{q_{i}\cdot Q_{i}}\leqslant 2\unicode[STIX]{x1D70B}H\mathop{\sum }_{i=k+1}^{d}\frac{N^{i}}{Q_{i}}.\end{eqnarray}$$

We thus have

(11) $$\begin{eqnarray}\mathop{\sum }_{0<h\leqslant H}\frac{1}{h}\bigg|\frac{1}{N}\mathop{\sum }_{n\leqslant N}\text{e}(hP(n))\bigg|\leqslant \mathop{\sum }_{0<h\leqslant H}\frac{1}{h}\bigg|\frac{1}{N}\mathop{\sum }_{n\leqslant N}\text{e}(hy_{n})\bigg|+2\unicode[STIX]{x1D70B}H\mathop{\sum }_{i=k+1}^{d}\frac{N^{i}}{Q_{i}}.\end{eqnarray}$$

Thus, we want to estimate $|(1/N)\sum _{n\leqslant N}\text{e}(hy_{n})|$ . The following lemma will permit us to reduce the question to the evaluation of trigonometrical sums over polynomials of degree $k$ .

Lemma 1. With the above notation, for any integer $r$ , there exists a polynomial $Q_{r}$ of degree $k$ with leading coefficient $\unicode[STIX]{x1D6FC}_{k}$ such that

$$\begin{eqnarray}y_{tq+r}-q^{k}Q_{r}(t)\in \mathbb{Z}\quad \text{ for any}\;t\in \mathbb{Z}.\end{eqnarray}$$

Proof. We recall that $q=\prod _{i=k+1}^{d}q_{i}$ . This implies that for any integer $t$ , the sum $\sum _{i=k+1}^{d}(p_{i}/q_{i})(tq+r)^{i}$ is equal, up to an integer, to $\sum _{i=k+1}^{d}(p_{i}/q_{i})r^{i}$ , which is independent of $t$ . By the binomial expansion, the first part of $y_{tq+r}$ , namely $\sum _{i=0}^{k}\unicode[STIX]{x1D6FC}_{i}(qt+r)^{i}$ , is easily seen to be a polynomial of degree $k$ with leading coefficient $\unicode[STIX]{x1D6FC}_{k}q^{k}$ .◻

We have

$$\begin{eqnarray}\displaystyle \bigg|\frac{1}{N}\mathop{\sum }_{n\leqslant N}\text{e}(hy_{n})\bigg| & = & \displaystyle \bigg|\frac{1}{N}\mathop{\sum }_{r\leqslant q}\mathop{\sum }_{\substack{ n\leqslant N \\ n\equiv r\operatorname{mod}q}}\text{e}(hy_{n})\bigg|\leqslant \mathop{\sum }_{0\leqslant r<q}\frac{1}{N}\bigg|\mathop{\sum }_{\substack{ n\leqslant N \\ n\equiv r\operatorname{mod}q}}\text{e}(hy_{n})\bigg|\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \mathop{\sum }_{0\leqslant r<q}\frac{1}{N}\bigg|\mathop{\sum }_{0\leqslant t\leqslant (N-r)/q}\text{e}(hy_{tq+r})\bigg|\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \mathop{\sum }_{0\leqslant r<q}\frac{1}{N}\bigg|\mathop{\sum }_{0\leqslant t\leqslant (N-r)/q}\text{e}(hq^{k}Q_{r}(t))\bigg|.\nonumber\end{eqnarray}$$

We define the integers $R$ and $H$ by

$$\begin{eqnarray}R=\lfloor q_{k}^{1/2}\rfloor \quad \text{and}\quad H=\lfloor q_{k}^{(1/2^{k})}/(2k!q^{k})\rfloor .\end{eqnarray}$$

We may assume that $H\geqslant 1$ , since otherwise Proposition 5 is trivial. We readily check that the condition $2Hq^{k}k!R^{2-1/2^{k-2}}\leqslant q_{k}$ holds and that as soon as $N$ is large enough we have $R\leqslant (N-q)/q$ . We can thus apply Proposition 1, which implies that for $1\leqslant h\leqslant H$ we have

$$\begin{eqnarray}\displaystyle \bigg|\mathop{\sum }_{0\leqslant t\leqslant (N-r)/q}\text{e}(hq^{k}Q_{r}(t))\bigg| & \ll & \displaystyle ((N-r)/q)\bigg(\frac{1}{R}+\frac{q_{k}}{(N-r)/q}\bigg)^{1/2^{k-1}}\nonumber\\ \displaystyle & \ll & \displaystyle N\bigg(\frac{1}{R}+\frac{q_{k}}{N}\bigg)^{1/2^{k-1}}.\nonumber\end{eqnarray}$$

This leads to

$$\begin{eqnarray}\displaystyle \mathop{\sum }_{0<h\leqslant H}\frac{1}{h}\bigg|\frac{1}{N}\mathop{\sum }_{n\leqslant N}\text{e}(hy_{n})\bigg| & \ll & \displaystyle q\log (eH)\bigg(\frac{1}{R}+\frac{q_{k}}{N}\bigg)^{1/2^{k-1}}\nonumber\\ \displaystyle & \ll & \displaystyle q\log (eq_{k})\bigg(\frac{1}{q_{k}^{1/2}}+\frac{q_{k}}{N}\bigg)^{1/2^{k-1}}.\nonumber\end{eqnarray}$$

We combine this, Proposition 4 and (11), getting Proposition 5.◻

We notice that the optimal choice of $H$ and $R$ permits to replace the term $q^{k}$ in (10) by $q^{f(k)}$ , where $f(k)$ tends to $1$ as $k$ tends to infinity, but this is irrelevant for our application.

5.1 Coefficients of polynomials with large discrepancy

Our first step is to show that if a sequence which is close to a polynomial has a large discrepancy, the non-constant coefficients of the underlying polynomial have very good approximations with rationals with bounded denominators.

Theorem 5. Let $\unicode[STIX]{x1D6FF}$ be a positive number and $d$ a natural integer. There exists a positive integer $M(\unicode[STIX]{x1D6FF},d)$ having the following property.

Let $P(x)=\sum _{k=1}^{d}\unicode[STIX]{x1D6FC}_{k}x^{k}$ be a polynomial of degree $d$ such that for any sufficiently large $N$ , for any $\unicode[STIX]{x1D702}=(\unicode[STIX]{x1D702}_{1},\ldots ,\unicode[STIX]{x1D702}_{N})$ with $\Vert \unicode[STIX]{x1D702}\Vert _{\infty }\leqslant \unicode[STIX]{x1D6FF}$ , we have

(13) $$\begin{eqnarray}D_{N}(P(1)+\unicode[STIX]{x1D702}_{1},P(2)+\unicode[STIX]{x1D702}_{2},\ldots ,P(N)+\unicode[STIX]{x1D702}_{N})>4\unicode[STIX]{x1D6FF}.\end{eqnarray}$$

Then, for all sufficiently large $N$ , we have

(14) $$\begin{eqnarray}\displaystyle & & \displaystyle \text{for all }k\in [1,d],\text{there exists }(p_{k},q_{k})\text{ with }\gcd (p_{k},q_{k})=1,\nonumber\\ \displaystyle & & \displaystyle 1\leqslant q_{k}\leqslant M(\unicode[STIX]{x1D6FF},d)\text{ and }\bigg|\unicode[STIX]{x1D6FC}_{k}-\frac{p_{k}}{q_{k}}\bigg|\leqslant N^{-(k+2)!/2(d+2)!}.\end{eqnarray}$$

Proof. The perturbation by $\unicode[STIX]{x1D702}$ will be useful for the application, but we can easily cope with it: by Proposition 3, the bounds $\Vert \unicode[STIX]{x1D702}\Vert _{\infty }\leqslant \unicode[STIX]{x1D6FF}$ and (13) imply that

(15) $$\begin{eqnarray}D_{N}(P(1),P(2),\ldots ,P(N))>\unicode[STIX]{x1D6FF},\end{eqnarray}$$

which is the condition we are going to use from now on.

Let $N$ be a sufficiently large integer. For $i\in [1,d]$ , we define

$$\begin{eqnarray}N_{i}=\lfloor N^{(i+2)!/2(d+2)!}+1\rfloor ,\qquad Q_{i}=\lfloor N_{i}^{1-\unicode[STIX]{x1D700}}+1\rfloor ,\quad \text{where }\unicode[STIX]{x1D700}=\frac{1}{2(d+2)}\end{eqnarray}$$

and we let $(p_{i},q_{i})$ be such that

$$\begin{eqnarray}\gcd (p_{i},q_{i})=1,\quad 1\leqslant q_{i}\leqslant Q_{i}\quad \text{and}\quad \bigg|\unicode[STIX]{x1D6FC}_{i}-\frac{p_{i}}{q_{i}}\bigg|\leqslant \frac{1}{q_{i}\cdot Q_{i}}.\end{eqnarray}$$

In order to prove the theorem, we shall show that for any $k$ in $[1,d]$ , there exists $M_{k}(\unicode[STIX]{x1D6FF},d)$ such that

(16) $$\begin{eqnarray}\displaystyle & & \displaystyle \text{for all }i\in [k,d],\text{there exists }(p_{i},q_{i})\text{ with }\gcd (p_{i},q_{i})=1,1\leqslant q_{i}\leqslant M_{k}(\unicode[STIX]{x1D6FF},d)\nonumber\\ \displaystyle & & \displaystyle \quad \text{and }\bigg|\unicode[STIX]{x1D6FC}_{i}-\frac{p_{i}}{q_{i}}\bigg|\leqslant N^{-(i+2)!/2(d+2)!}.\end{eqnarray}$$

We first prove (16) when $k=d$ . By (15) and Proposition 5, we have

$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D6FF}\leqslant D_{N_{d}}(P(1),\ldots ,P(N_{d})) & ~\ll _{d}\ & \displaystyle \log (eq_{d})\bigg(\frac{1}{q_{d}^{1/2}}+\frac{q_{d}}{N_{d}}\bigg)^{1/2^{d-1}}\nonumber\\ \displaystyle & ~\ll _{d}\ & \displaystyle \log (eq_{d})\max \bigg(\frac{1}{q_{d}^{1/2d}},\bigg(\frac{Q_{d}}{N_{d}}\bigg)^{1/2^{d-1}}\bigg).\nonumber\end{eqnarray}$$

By definition, we have $Q_{d}\leqslant 2N_{d}^{1-\unicode[STIX]{x1D700}}$ and so the quantity $\log (eq_{d})(Q_{d}/N_{d})^{1/2^{d-1}}$ , which is less than $\log (eQ_{d})(Q_{d}/N_{d})^{1/2^{d-1}}$ , tends to zero as $N_{d}$ tends to infinity and thus as $N$ tends to infinity; when $N$ is large enough, the term $\log (eq_{d})q_{d}^{-1/2^{d}}$ has to be bounded from below, i.e. $q_{d}$ has to be bounded from above. This is the case $k=d$ of the theorem.

Assume now that (16) is proved for some $k\in [2,d]$ and let us show that it is also true for $k-1$ . We are going to use Proposition 5 with $N=N_{k-1}$ and start with some preliminary computation:

$$\begin{eqnarray}q=\mathop{\prod }_{i=k}^{d}q_{i}\leqslant M_{k}(\unicode[STIX]{x1D6FF},d)^{d}.\end{eqnarray}$$

We also have

$$\begin{eqnarray}\displaystyle Q_{k-1}^{1/2^{k-2}}\mathop{\sum }_{i=k}^{d}\frac{N_{k}^{i}}{Q_{i}} & {\leqslant} & \displaystyle \mathop{\sum }_{i=k}^{d}\frac{N_{k-1}^{i+1}}{Q_{i}}=\mathop{\sum }_{i=k}^{d}\frac{N^{(i+1)((k+1)!/(d+2)!)}}{N^{(1-\unicode[STIX]{x1D700})((i+2)!/(d+2)!)}}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{i=k}^{d}\bigg(\frac{N^{i+1}}{N^{(1-\unicode[STIX]{x1D700})((i+2)!/(k+1)!)}}\bigg)^{(k+1)!/(d+2)!}\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \mathop{\sum }_{i=k}^{d}\bigg(\frac{N^{i+1}}{N^{(1-\unicode[STIX]{x1D700})(i+2)}}\bigg)^{(k+1)!/(d+2)!}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{i=k}^{d}\bigg(\frac{1}{N^{1-\unicode[STIX]{x1D700}(i+2)}}\bigg)^{(k+1)!/(d+2)!}\nonumber\\ \displaystyle & {\leqslant} & \displaystyle (d-k+1)N^{-(1-(d+2)\unicode[STIX]{x1D700})/(d+2)}.\nonumber\end{eqnarray}$$

We recall that $\unicode[STIX]{x1D700}=1/(2(d+2))$ and obtain

$$\begin{eqnarray}q_{k-1}^{1/2^{k-2}}\mathop{\sum }_{i=k}^{d}\frac{N_{k-1}^{i}}{Q_{i}}\leqslant Q_{k-1}^{1/2^{k-2}}\mathop{\sum }_{i=k}^{d}\frac{N_{k-1}^{i}}{Q_{i}}\leqslant dN^{-1/2(d+2)}.\end{eqnarray}$$

From that computation and Proposition 5, we get

$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D6FF} & {\leqslant} & \displaystyle D_{N_{k-1}}(x_{1},\ldots ,x_{N_{k-1}})\nonumber\\ \displaystyle & ~\ll _{d}\ & \displaystyle M_{k}(\unicode[STIX]{x1D6FF},d)^{d}\log (eq_{k-1})\max \bigg(\frac{1}{q_{k-1}^{1/2^{k-1}}},\bigg(\frac{q_{k-1}}{N_{k-1}}\bigg)^{1/2^{k-2}}\bigg)\nonumber\\ \displaystyle & & \displaystyle +\,q_{k-1}^{1/2^{k-2}}\mathop{\sum }_{i=k}^{d}\frac{N_{k-1}^{i}}{Q_{i}}\nonumber\\ \displaystyle & ~\ll _{d}\ & \displaystyle M_{k}(\unicode[STIX]{x1D6FF},d)^{d}\log (eq_{k-1})\max (q_{k-1}^{-1/2^{k-1}},N_{k-1}^{-\unicode[STIX]{x1D700}/2k-2})+N^{-1/2(d+2)}.\nonumber\end{eqnarray}$$

Arguing as above, we see that for $N$ large enough, this relation can hold only if $q_{k-1}$ is bounded from below by $M^{\prime }(\unicode[STIX]{x1D6FF},d)$ , say. We let $M_{k-1}(\unicode[STIX]{x1D6FF},d)=\max (M^{\prime }(\unicode[STIX]{x1D6FF},d),M_{k}(\unicode[STIX]{x1D6FF},d))$ .

Induction implies the validity of Theorem 5 with $M(\unicode[STIX]{x1D6FF},d)=M_{1}(\unicode[STIX]{x1D6FF},d)$ .◻

5.2 Non-uniformity modulo $m\geqslant 3$ of perturbed polynomials

The following result shows that the sequence of the integral parts of the values of a slightly perturbed real polynomial cannot be uniform modulo any $m\geqslant 3$ .

Theorem 6. Let $m$ and $d$ be positive integers with $m\geqslant 3$ . There exist a positive integer $N=N(m,d)$ and a block $B\in \{0,1,\ldots ,m-1\}^{N}$ such that for any real polynomial $P$ of degree $d$ and any sequence $\unicode[STIX]{x1D702}=(\unicode[STIX]{x1D702}_{n})_{n}$ of real numbers bounded by $1/20$ , there exists $n\in [1,N]$ such that

(17) $$\begin{eqnarray}\lfloor P(n)+\unicode[STIX]{x1D702}_{n}\rfloor \not \equiv b_{n}\,(\operatorname{mod}m).\end{eqnarray}$$

Proof. We let $M=M(1/(20m),d)$ (where $M(\cdot \,,\,\cdot )$ was defined in Theorem 5) and $N\geqslant (40mdM!)^{(d+3)!}$ be integers satisfying Theorem 5 (with $d=d$ and $\unicode[STIX]{x1D6FF}=1/(20m)$ ) and define the block $B$ to consist of $M!$ digits $2$ followed by $M!$ digits $1$ followed by $N-2M!$ digits $0$ .

We assume that there exists a polynomial $P$ for which (17) does not hold; in particular, for any $n\in [2M!+1,N]$ , we have $\lfloor P(n)+\unicode[STIX]{x1D702}_{n}\rfloor \equiv 0\,(\operatorname{mod}m)$ . We let $R(x)=P(x)/m$ and $\unicode[STIX]{x1D6FD}_{n}=\unicode[STIX]{x1D702}_{n}/m$ . Since $N\geqslant 8M!$ , the discrepancy of the sequence $(R(n)+\unicode[STIX]{x1D6FD}_{n})_{1\leqslant n\leqslant N}$ is larger than $1/2$ . We can thus apply Theorem 5 with $\unicode[STIX]{x1D6FF}=1/(20m)$ . Let us write $R(x)=\sum _{k=1}^{d}\unicode[STIX]{x1D6FC}_{k}x^{k}$ ; for any $k$ , there exist coprime rational integers $p_{k}$ , $q_{k}$ with $1\leqslant q_{k}\leqslant M$ and

$$\begin{eqnarray}\bigg|\unicode[STIX]{x1D6FC}_{k}-\frac{p_{k}}{q_{k}}\bigg|\leqslant N^{-(k+2)!/2(d+2)!}\leqslant \frac{1}{20md\cdot (2M!)^{d}},\end{eqnarray}$$

where the last inequality comes from the choice of $N$ .

For $k\in [1,d]$ , we let $\unicode[STIX]{x1D700}_{k}=\unicode[STIX]{x1D6FC}_{k}-p_{k}/q_{k}$ and $r(x)=\unicode[STIX]{x1D6FC}_{0}+\sum _{k=1}^{d}\unicode[STIX]{x1D700}_{k}(M!)^{k}x^{k}$ . Since $M!/q_{k}\in \mathbb{N}$ , we have for any integer $\ell$ ,

$$\begin{eqnarray}R(\ell M!)\equiv r(\ell )\,(\operatorname{mod}1).\end{eqnarray}$$

For $\ell \in \{1,2\}$ , we have

$$\begin{eqnarray}\displaystyle |r(0)-r(\ell )|\leqslant \mathop{\sum }_{k=1}^{d}|\unicode[STIX]{x1D700}_{k}|(M!)^{k}\ell ^{k}\leqslant \mathop{\sum }_{k=1}^{d}\frac{1}{20md\cdot (2M!)^{d}}(M!)^{d}2^{d}\leqslant \frac{1}{20m}. & & \displaystyle \nonumber\end{eqnarray}$$

For $\ell \in \{1,2,3\}$ , we have $|r(\ell )+\unicode[STIX]{x1D6FD}_{\ell M!}-r(0)|\leqslant 1/(10m)$ , which implies that the three real numbers $r(\ell )+\unicode[STIX]{x1D6FD}_{\ell M!}$ belong to an interval of length $1/(5m)<1/(3m)$ . This relation is incompatible with the fact that $\{\lfloor P(\ell M!)+\unicode[STIX]{x1D702}_{\ell M!}\rfloor :1\leqslant \ell \leqslant 3\}$ takes three different values.◻

5.3 Non-uniformity modulo $m\geqslant 2$ of smoothly perturbed polynomials

The proof of the previous result makes a crucial use of the fact that we can find at least three different digits in base $m$ . Indeed, the observation that for any sequence $(b_{n})_{n}\in \{0,1\}^{\mathbb{N}}$ , there exists a sequence $(\unicode[STIX]{x1D700}_{n})_{n}$ tending to 0 as quickly as we wish such that for any $n$ we have $\lfloor 2n+1+\unicode[STIX]{x1D700}_{n}\rfloor \equiv b_{n}\,(\operatorname{mod}m)$ shows that Theorem 6 cannot be extended without modification to the case when $m=2$ . Theorem 7 shows that the case $m=2$ can be treated if we add some regularity conditions, as in the following simple lemma.

Proof. We assume that the sequence $x_{1},x_{2},x_{3}$ is non-decreasing. We have

$$\begin{eqnarray}\lfloor x_{1}\rfloor \leqslant \lfloor x_{3}\rfloor \leqslant \lfloor x_{1}+1\rfloor =\lfloor x_{1}\rfloor +1.\end{eqnarray}$$

Since $\lfloor x_{1}\rfloor$ and $\lfloor x_{3}\rfloor$ have the same residue modulo $m$ , they are equal. We have $\lfloor x_{1}\rfloor \leqslant \lfloor x_{2}\rfloor \leqslant \lfloor x_{3}\rfloor$ , which implies that $\lfloor x_{1}\rfloor =\lfloor x_{2}\rfloor$ , which is a contradiction. The case when the sequence $x_{1},x_{2},x_{3}$ is non-increasing is treated in a similar way.◻

Theorem 7. Let $m$ and $d$ be positive integers with $m\geqslant 2$ . There exist a positive integer $N=N(m,d)$ and a block $B\in \{0,1\}^{N}$ such that for any real polynomial $P$ of degree $d$ and any real function $\unicode[STIX]{x1D702}\in {\mathcal{C}}^{d+1}([1,N])$ such that

(18) $$\begin{eqnarray}\text{for all }t\in [1,N]:|\unicode[STIX]{x1D702}(t)|\leqslant 1/20\quad \text{and}\quad \unicode[STIX]{x1D702}^{(d+1)}(t)\neq 0,\end{eqnarray}$$

there exists $n\in [1,N]$ such that

(19) $$\begin{eqnarray}\lfloor P(n)+\unicode[STIX]{x1D702}(n)\rfloor \not \equiv b_{n}\,(\operatorname{mod}m).\end{eqnarray}$$

Proof. We let $M=M(1/(20m),d)$ (where $M(\cdot \,,\,\cdot )$ was defined in Theorem 5) and $N\geqslant (40mdM!)^{(d+3)!}$ be integers satisfying Theorem 5 (with $d=d$ and $\unicode[STIX]{x1D6FF}=1/(20m)$ ) and define the block $B$ to consist of $N$ integers almost all of them being equal to $0$ , with the exception that, for $k=1,2,\ldots ,2d$ , one has $b_{(2kM!)}=1$ .

We assume that there exists a polynomial $P$ for which (19) does not hold; in particular, we have $\operatorname{Card}\{n\in [1,N]:\lfloor P(n)+\unicode[STIX]{x1D702}(n)\rfloor \equiv 0\,(\operatorname{mod}m)\}=N-2d$ . We let $R(x)=P(x)/m$ and $\unicode[STIX]{x1D6FD}(x)=\unicode[STIX]{x1D702}(x)/m$ . The discrepancy of the sequence $(R(n)+\unicode[STIX]{x1D6FD}_{n})_{1\leqslant n\leqslant N}$ is larger than $1/3$ . We can thus apply Theorem 5 with $\unicode[STIX]{x1D6FF}=1/(20m)$ . Let us write $R(x)=\sum _{k=1,d}\unicode[STIX]{x1D6FC}_{k}x^{k}$ ; for any $k$ there exist coprime rational integers $p_{k}$ , $q_{k}$ with $1\leqslant q_{k}\leqslant M$ and

$$\begin{eqnarray}\bigg|\unicode[STIX]{x1D6FC}_{k}-\frac{p_{k}}{q_{k}}\bigg|\leqslant N^{-(k+2)!/2(d+2)!}\leqslant \frac{1}{20md\cdot (4dM!)^{d}},\end{eqnarray}$$

where the last inequality comes from the choice of $N$ .

For $k\in [1,d]$ , we let $\unicode[STIX]{x1D700}_{k}=\unicode[STIX]{x1D6FC}_{k}-p_{k}/q_{k}$ and $r(x)=\unicode[STIX]{x1D6FC}_{0}+\sum _{k=1}^{d}\unicode[STIX]{x1D700}_{k}(M!)^{k}x^{k}$ . Since $M!/q_{k}\in \mathbb{N}$ , we have for any integer $\ell$ ,

$$\begin{eqnarray}R(\ell M!)\equiv r(\ell )\,(\operatorname{mod}1).\end{eqnarray}$$

We define a function $f$ by the relation

$$\begin{eqnarray}\forall t\in [1,4d]:f(t)=mr(t)+\unicode[STIX]{x1D702}(tM!).\end{eqnarray}$$

For any $t\in [1,N]$ , we have

$$\begin{eqnarray}\displaystyle |f(t)-f(0)| & {\leqslant} & \displaystyle m\mathop{\sum }_{k=1}^{d}|\unicode[STIX]{x1D700}_{k}|(M!)^{k}\ell ^{k}+2\times \frac{1}{20}\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \mathop{\sum }_{k=1}^{d}\frac{1}{20d\cdot (4dM!)^{d}}(M!)^{d}(4d)^{d}+\frac{1}{10}\leqslant \frac{3}{20}\nonumber\end{eqnarray}$$

and so for any $t_{1}$ and $t_{2}$ one has $|f(t_{1})-f(t_{2})|\leqslant \frac{3}{10}$ .

Since  $r$  is a polynomial of degree  $d$ , we have  $f^{(d+1)}(t)=(M!)^{d+1}\unicode[STIX]{x1D702}^{(d+1)}(tM!)$ , which is different from $0$ by (18). By repeated applications of Rolle’s theorem, we find that $f^{\prime }$ vanishes at most $d$ times on $[1,4d]$ : there exists at least an integer $\ell _{0}\in [1,4d]$ such that the sequence $f(\ell _{0}),f(\ell _{0}+1),f(\ell _{0}+2)$ is monotonic.

By Lemma 2, the triplet $(\lfloor f(\ell _{0})\rfloor ,\lfloor f(\ell _{0}+1)\rfloor ,\lfloor f(\ell _{0}+2)\rfloor )$ taken modulo $m$ cannot be $(0,1,0)$ nor $(1,0,1)$ .

We finally notice that, for any integer $\ell$ , the difference between $f(\ell )$ and $P(\ell M!)+\unicode[STIX]{x1D702}(\ell m!)$ is a multiple of $m$ ; thus, the triple $(\lfloor P(\ell _{0}M!)+\unicode[STIX]{x1D702}(\ell _{0}M!)\rfloor ,\lfloor P((\ell _{0}+1)M!)+\unicode[STIX]{x1D702}((\ell _{0}+1)M!)\rfloor ,\lfloor P((\ell _{0}+2)M!)+\unicode[STIX]{x1D702}((\ell _{0}+2)M!)\rfloor )$ taken modulo $m$ cannot be $(0,1,0)$ nor $(1,0,1)$ , contrary to our assumption. This contradiction proves Theorem 7.◻

5.4 Proof of Theorem 2

Let $m\geqslant 2$ be an integer and $c>1$ a real number which is not an integer. We let $d=\lfloor c\rfloor$ and consider the number $N=N(m,d)$ and the block $B$ given by Theorem 7. For any positive real numbers $X$ and $t$ , we consider the Taylor approximation of order $d$ of $(X+t)^{c}$ , namely

$$\begin{eqnarray}\displaystyle (X+t)^{c}=P_{X}(t)+\unicode[STIX]{x1D702}_{X}(t), & & \displaystyle \nonumber\end{eqnarray}$$

where

$$\begin{eqnarray}\displaystyle P_{X}(t)=\mathop{\sum }_{k=0}^{d}\frac{c^{\text{}\underline{k}}X^{c-k}}{k!}t^{k}\quad \text{and}\quad |\unicode[STIX]{x1D702}_{X}(t)|\leqslant ct^{(d+1)}X^{\{c\}-1}. & & \displaystyle \nonumber\end{eqnarray}$$

For any sufficiently large integer $X$ , say $X\geqslant X_{0}$ , we have $|\unicode[STIX]{x1D702}_{X}(t)|\leqslant 1/20$ for any $t$ in $[1,N]$ . Moreover, the $(d+1)$ th derivative of $\unicode[STIX]{x1D702}_{X}$ is the $(d+1)$ th derivative of $t\mapsto (X+t)^{c}$ and thus does not vanish. We can thus apply Theorem 7: there exists a block $B$ of length $N$ which does not occur in the sequence of the residues modulo $m$ of the sequence $(\lfloor n^{c}\rfloor )_{n\geqslant X_{0}}$ . Let $U$ be in $\{0,1,\ldots ,m-1\}^{X_{0}}$ ; the word $UB$ , the concatenation of the words $U$ and $B$ , never occurs in the sequence of the residues modulo $m$ of the sequence $(\lfloor n^{c}\rfloor )_{n\geqslant 0}$ . This ends the proof of Theorem 2.

We end this section by noticing that for $m\geqslant 3$ , the more general Theorem 6 is sufficient for proving Theorem 2.

6.1 An upper bound for the complexity

Assume that $L\geqslant 1$ (a block length) and $\unicode[STIX]{x1D700}=1/(4L^{2})$ . Write $\mathbf{a}_{n}=\lfloor n^{c}\rfloor \operatorname{mod}m$ . By Taylor’s theorem (consider the second derivative of $x^{c}$ , which tends to $0$ like $x^{c-2}$ ), there exists a constant $C$ , only depending on $c$ , such that for $a\geqslant 4/(2-c)$ and $N\geqslant CL^{a}$ , the following is satisfied: there are reals $\unicode[STIX]{x1D6FC}$ , $\unicode[STIX]{x1D6FD}$ such that

$$\begin{eqnarray}0\leqslant n^{c}-(n\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD})<\unicode[STIX]{x1D700}\end{eqnarray}$$

for $N\leqslant n<N+L$ . We also assume that $\unicode[STIX]{x1D6FC}$ is irrational, which is no loss of generality. This technical condition will be used later, when we apply the three-gaps theorem. The number of different factors in $\mathbf{a}$ of length $L$ occurring at positions $N<CL^{a}$ is trivially bounded by $CL^{a}$ , which gives the first term of the maximum in the theorem.

It remains to consider start positions $N\geqslant CL^{a}$ , where linear approximation of quality $\unicode[STIX]{x1D700}$ can be applied. Any block $(\mathbf{a}_{N},\ldots ,\mathbf{a}_{N+L-1})$ is obtained by starting from a block $b=(\lfloor N\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\rfloor \operatorname{mod}m,\ldots ,\lfloor (N+L-1)\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\rfloor \operatorname{mod}m)$ and possibly modifying this sequence at indices $n$ such that $1-\unicode[STIX]{x1D700}\leqslant \{n\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\}<1$ . This possible modification consists in adding $1$ modulo $m$ .

We begin by estimating the number of factors of $\lfloor n\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\rfloor \operatorname{mod}m$ . Each such block corresponds to a finite Sturmian word by considering the sequence of differences $\lfloor (n+1)\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\rfloor -\lfloor n\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\rfloor$ . Note that such a sequence of differences corresponds to at most $m$ factors of the Beatty sequence. This follows by taking the first element $\lfloor n_{0}\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\rfloor \operatorname{mod}m$ of the considered factor into account and considering partial sums. Using Mignosi [Reference Mignosi15], we can estimate the number of factors $b$ by $O(L^{3})$ , where here and in the following the implied constant may depend on $m$ .

Consider the interval $I=[1-\unicode[STIX]{x1D700},1)$ and the set

$$\begin{eqnarray}A=\{n:N\leqslant n<N+L,\{n\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\}\in I\}.\end{eqnarray}$$

We make use of the three-gaps theorem (see, for example, the survey by Alessandri and Berthé [Reference Alessandri and Berthé1], in particular the remark in §4), which implies that there are at most three differences $a_{2}-a_{1}$ between consecutive elements of the set $B=\{n\in \mathbb{N}:\{n\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\}\in I\}$ and if three differences occur, the largest one is the sum of the smaller ones.

We distinguish between three cases.

(1) All gaps are ${\geqslant}L$ . In this case, $|A|\leqslant 1$ , so that we have to change the block $b$ at at most one position by adding $1$ modulo $m$ , as noted above. This gives a factor of $L+1$ , which implies that this case contributes $O(L^{3+1})$ many cases.

(2) Exactly one gap is ${<}L$ . In this case, $A$ is an arithmetic progression, consisting of the elements $n_{j}=n_{0}+jd$ for some $n_{0}=\min A$ and $d\geqslant 1$ and $0\leqslant j<k$ . Set $x_{j}=\{n_{j}\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\}$ and $\unicode[STIX]{x1D6FF}=x_{1}-x_{0}$ .

First, we want to show that $(x_{0},\ldots ,x_{k-1})$ is an arithmetic progression with difference $\unicode[STIX]{x1D6FF}$ . Note that $|\unicode[STIX]{x1D6FF}|<\unicode[STIX]{x1D700}<1/2$ . Suppose that we have already shown that $(x_{0},\ldots ,x_{j-1})$ is an arithmetic progression. Clearly we have $x_{j}=x_{j-1}+\unicode[STIX]{x1D6FF}+r$ for some $r\in \mathbb{Z}$ . Suppose that $r\neq 0$ . Then $|x_{j}-x_{j-1}|>1-\unicode[STIX]{x1D700}$ . Since both $x_{j}$ and $x_{j-1}$ are elements of the interval $[1-\unicode[STIX]{x1D700},1)$ , this is a contradiction to $\unicode[STIX]{x1D700}<1/2$ .

Next, we prove that the set $J=\{i<k:\lfloor n_{i}^{c}\rfloor >\lfloor n_{i}\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\rfloor \}$ is an interval. To this end, note that $\lfloor n_{i}^{c}\rfloor >\lfloor n_{i}\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\rfloor$ if and only if $n_{i}^{c}-(n_{i}\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD})\geqslant 1-\{n_{i}\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\}$ , which is the case if and only if $n_{i}^{c}-(n_{i}\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD})+\{n_{0}\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\}+i\unicode[STIX]{x1D6FF}-1\geqslant 0$ . Note that the left-hand side is a convex function of $i$ , which implies the assertion.

In order to obtain the block $(\mathbf{a}_{N},\ldots ,\mathbf{a}_{N+L-1})$ from the block $b=(\lfloor N\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\rfloor \operatorname{mod}m,\ldots ,\lfloor (N+L-1)\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\rfloor \operatorname{mod}m)$ , we modify $b$ at indices $n_{j}$ for $j\in J$ , where $J$ is the interval obtained above. These indices form an arithmetic progression in $[N,N+L-1]$ , of which there are $O(L^{3})$ many. (Note that in fact $L^{2}\log L$ is sufficient.) This implies a contribution of $O(L^{3+3})$ for this case.

(3) There exist two gaps $g_{1}<g_{2}<L$ . We are going to show that this case cannot occur. We first note that $g_{1}\unicode[STIX]{x1D6FC}\not \in \mathbb{Z}$ . Otherwise, the set $B$ would contain an arithmetic progression with difference $g_{1}$ ; therefore, the gap $g_{2}$ would not occur, which is a contradiction. It follows that $0<\Vert g_{1}\unicode[STIX]{x1D6FC}\Vert <\unicode[STIX]{x1D700}$ . Choose $n_{1},n_{2}\in \mathbb{N}$ in such a way that $n_{2}-n_{1}=g_{1}$ and $n_{1},n_{2}\in B$ . Consider the $g_{1}$ points $\{n_{1}\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\},\{(n_{1}+1)\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\},\ldots ,\{(n_{1}+g_{1}-1)\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\}$ . These points dissect the torus into $g_{1}$ many intervals. Therefore, there is an interval $J=[x,y)$ in $\mathbb{R}$ of length ${\geqslant}1/g_{1}\geqslant 1/L=4L\unicode[STIX]{x1D700}$ such that $n\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\not \in J+\mathbb{Z}$ for $n_{1}\leqslant n<n_{2}$ . Assume that $\{g_{1}\unicode[STIX]{x1D6FC}\}<\unicode[STIX]{x1D700}$ , the case $\{g_{1}\unicode[STIX]{x1D6FC}\}>1-\unicode[STIX]{x1D700}$ being analogous. Then

$$\begin{eqnarray}\displaystyle & & \displaystyle \{n\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}:n_{1}\leqslant n<n_{1}+2Lg_{1}\}\nonumber\\ \displaystyle & & \displaystyle \quad =\!\!\mathop{\bigcup }_{0\leqslant k<2L}\!\!\{n\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}:kn_{1}\leqslant n<n_{1}+(k+1)g_{1}\}\nonumber\\ \displaystyle & & \displaystyle \quad \subseteq \{n\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}:n_{1}\leqslant n<n_{1}+g_{1}\}+\mathop{\bigcup }_{0\leqslant k<2L}(kg_{1}\unicode[STIX]{x1D6FC}+\mathbb{Z})\nonumber\\ \displaystyle & & \displaystyle \quad \subseteq \mathbb{R}\setminus (J^{\prime }+\mathbb{Z}),\nonumber\end{eqnarray}$$

where $J^{\prime }=[x+2L\unicode[STIX]{x1D700},y)$ has length ${\geqslant}2\unicode[STIX]{x1D700}$ . We now use the fact that $0\neq \Vert g_{1}\unicode[STIX]{x1D6FC}\Vert <\unicode[STIX]{x1D700}$ in order to shift the interval $J^{\prime }$ over the interval $[1-\unicode[STIX]{x1D700},1)$ by using a multiple of $\unicode[STIX]{x1D6FC}$ . Set $\unicode[STIX]{x1D6FF}=(1-2\unicode[STIX]{x1D700})-(x+2L\unicode[STIX]{x1D700})$ and assume that $n_{0}$ is such that $n_{0}\unicode[STIX]{x1D6FC}\in \unicode[STIX]{x1D6FF}+[0,\unicode[STIX]{x1D700})+\mathbb{Z}$ . Then, for all $n$ such that $n_{1}+n_{0}\leqslant n<n_{1}+n_{0}2Lg_{1}$ , we have

$$\begin{eqnarray}\displaystyle n\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD} & \in & \displaystyle \mathbb{R}\setminus (J^{\prime }+\mathbb{Z})+n_{0}\unicode[STIX]{x1D6FC}\nonumber\\ \displaystyle & \subseteq & \displaystyle [y,x+2L\unicode[STIX]{x1D700}+1)+\unicode[STIX]{x1D6FF}+[0,\unicode[STIX]{x1D700})+\mathbb{Z}\nonumber\\ \displaystyle & \subseteq & \displaystyle [x+2L\unicode[STIX]{x1D700}+2\unicode[STIX]{x1D700},x+2L\unicode[STIX]{x1D700}+1)+(1-2\unicode[STIX]{x1D700})-(x+2L\unicode[STIX]{x1D700})+[0,\unicode[STIX]{x1D700})+\mathbb{Z}\nonumber\\ \displaystyle & \subseteq & \displaystyle [0,1-\unicode[STIX]{x1D700})+\mathbb{Z}.\nonumber\end{eqnarray}$$

It follows that the sequence $(n\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD})_{n\geqslant 0}$ does not visit $I+\mathbb{Z}$ for at least $2L$ many steps, which is a contradiction to the three-gaps theorem: we proved the existence of a gap ${\geqslant}2L$ , but it is the sum of the smaller ones and therefore is at most $2L-1$ .

Therefore, case (3) does not occur and the first part of the theorem is proved.

6.2 A lower bound for the complexity

We use Mignosi [Reference Mignosi15] again; this time we use the fact that there are at least $Ck^{3}$ Sturmian words of length $k$ . Let $a\in \{0,1\}^{k}$ be a subword of a Sturmian word. There exist an irrational $\unicode[STIX]{x1D6FC}_{0}<1$ and some $\unicode[STIX]{x1D6FD}_{0}$ and $n$ such that $a_{\ell }=\lfloor (n+\ell +1)\unicode[STIX]{x1D6FC}_{0}+\unicode[STIX]{x1D6FD}_{0}\rfloor -\lfloor (n+\ell )\unicode[STIX]{x1D6FC}_{0}+\unicode[STIX]{x1D6FD}_{0}\rfloor$ for $0\leqslant \ell <k$ . Let $b\in \{0,\ldots ,m-1\}^{k}$ be the sequence of partial sums modulo $m$ ; moreover, let sequences $b^{(j)}$ be defined by $b^{(j)}(\ell )=b(\ell +j)\operatorname{mod}m$ . Then one out of $b=b^{(0)},\ldots ,b^{(m-1)}$ appears as a subword of $L(\unicode[STIX]{x1D6FD}_{0})$ , where $L(\unicode[STIX]{x1D6FD})=(\lfloor n\unicode[STIX]{x1D6FC}_{0}+\unicode[STIX]{x1D6FD}\rfloor \operatorname{mod}m)_{n\geqslant 0}$ . By irrationality of $\unicode[STIX]{x1D6FC}$ and the three-gaps theorem, it is not difficult to show that there is some $B$ such that, for all $\unicode[STIX]{x1D6FD}$ , every subword of $L(\unicode[STIX]{x1D6FD})$ of length $B$ contains one subword taken from the set $\{b^{(0)},\ldots ,b^{(m-1)}\}$ . (Sturmian words are uniformly recurrent.) We are going to show that $(\lfloor n^{c}\rfloor \operatorname{mod}m)_{n\geqslant 0}$ contains a subword of $L(\unicode[STIX]{x1D6FD})$ of length $B$ , which establishes our claim.

It is elementary to show that there exist an $\unicode[STIX]{x1D700}>0$ and some open interval $I$ such that the following holds: for all $\unicode[STIX]{x1D6FD}$ and $n$ such that $n\unicode[STIX]{x1D6FC}_{0}+\unicode[STIX]{x1D6FD}\in I+\mathbb{Z}$ , we have $\Vert (n+m)\unicode[STIX]{x1D6FC}_{0}+\unicode[STIX]{x1D6FD}\Vert >\unicode[STIX]{x1D700}$ for all $m<B$ .

We use the denseness of $n\unicode[STIX]{x1D6FC}_{0}+\unicode[STIX]{x1D6FD}\operatorname{mod}1$ : let $A$ be so large that for all $\unicode[STIX]{x1D6FD}$ and $n$ , we have $(n+\ell )\unicode[STIX]{x1D6FC}_{0}+\unicode[STIX]{x1D6FD}\in I+\mathbb{Z}$ for some $\ell <A$ .

Finally, let $x_{0}$ be so large such that $\frac{1}{2}f^{\prime \prime }(x)(A+B+1)^{2}<\unicode[STIX]{x1D700}$ for $x\geqslant x_{0}$ , where $f(x)=x^{c}$ . We approximate $x^{c}$ by a linear function $x\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}$ at some point $x\geqslant x_{0}$ satisfying $\unicode[STIX]{x1D6FC}=f^{\prime }(x)\equiv \unicode[STIX]{x1D6FC}_{0}\operatorname{mod}m$ .

We obtain some $\ell <A$ such that $\Vert (\lceil x\rceil +\ell +m)\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\Vert >\unicode[STIX]{x1D700}$ for all $m<B$ . By Taylor’s formula, it follows that $\lfloor (\lceil x\rceil +\ell +m)^{c}\rfloor =\lfloor (\lceil x\rceil +\ell +m)\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}\rfloor$ for all $m<B$ , which shows that there is a subword of $L(\unicode[STIX]{x1D6FD})$ of length $B$ contained in $(\lfloor n^{c}\rfloor \operatorname{mod}m)_{n\geqslant 0}$ .

It follows that $\lfloor n^{c}\rfloor \operatorname{mod}m$ has complexity at least $Ck^{3}$ , which shows (using Allouche and Shallit [Reference Allouche and Shallit2, Corollary 10.4.9]) that this sequence is not morphic. In particular, it is not an automatic sequence.