# Normality of the Thue-Morse function for finite fields along polynomial
values

Mehdi Makhul and Arne Winterhof

###### Abstract

Let $\mathbb{F}_{q}$ be the finite field of $q$ elements, where $q=p^{r}$ is a
power of the prime $p$, and $\left(\beta_{1},\beta_{2},\dots,\beta_{r}\right)$
be an ordered basis of $\mathbb{F}_{q}$ over $\mathbb{F}_{p}$. For

$\xi=\sum_{i=1}^{r}x_{i}\beta_{i},\quad\quad x_{i}\in\mathbb{F}_{p},$

we define the Thue-Morse or sum-of-digits function $T(\xi)$ on
$\mathbb{F}_{q}$ by

$T(\xi)=\sum_{i=1}^{r}x_{i}.$

For a given pattern length $s$ with $1\leq s\leq q$, a subset ${\cal
A}=\\{\alpha_{1},\ldots,\alpha_{s}\\}\subset\mathbb{F}_{q}$, a polynomial
$f(X)\in\mathbb{F}_{q}[X]$ of degree $d$ and a vector
$\underline{c}=(c_{1},\ldots,c_{s})\in\mathbb{F}_{p}^{s}$ we put

${\cal T}(\underline{c},{\cal
A},f)=\\{\xi\in\mathbb{F}_{q}:T(f(\xi+\alpha_{i}))=c_{i},~{}i=1,\ldots,s\\}.$

In this paper we will see that under some natural conditions, the size of
${\cal T}(\underline{c},{\cal A},f)$ is asymptotically the same for all
$\underline{c}$ and ${\cal A}$ in both cases, $p\rightarrow\infty$ and
$r\rightarrow\infty$, respectively. More precisely, we have

$\left||{\cal T}(\underline{c},{\cal A},f)|-p^{r-s}\right|\leq(d-1)q^{1/2}$

under certain conditions on $d,q$ and $s$. For monomials of large degree we
improve this bound as well as we find conditions on $d,q$ and $s$ for which
this bound is not true. In particular, if $1\leq d<p$ we have the dichotomy
that the bound is valid if $s\leq d$ and fails for some $\underline{c}$ and
${\cal A}$ if $s\geq d+1$. The case $s=1$ was studied before by Dartyge and
Sárközy.

Johann Radon Institute for Computational and Applied Mathematics, Austrian
Academy of Sciences, Altenberger Str. 69, 4040 Linz, Austria

E-mail<EMAIL_ADDRESS>
MSC 2010. 11A63, 11T06, 11T23, 11L99

Keywords. finite fields, polynomial equations, Thue-Morse function,
exponential sums, sum of digits, normality.

##  1 Introduction

###  1.1 The problem for binary sequences

For positive integers $M$ and $s$, a binary sequence $(a_{n})$ and a binary
pattern

${\cal E}_{s}=(\varepsilon_{0},\ldots,\varepsilon_{s-1})\in\\{0,1\\}^{s}$

of length $s$ we denote by $N(a_{n},M,{\cal E}_{s})$ the number of $n$ with
$0\leq n<M$ and $(a_{n},a_{n+1},\ldots,a_{n+s-1})={\cal E}_{s}.$ The sequence
$(a_{n})$ is normal if for any fixed $s$ and any pattern ${\cal E}_{s}$ of
length $s$,

$\lim_{M\rightarrow\infty}\frac{N(a_{n},M,{\cal E}_{s})}{M}=\frac{1}{2^{s}}.$

The Thue-Morse or sum-of-digits sequence $(t_{n})$ is defined by

$t_{n}=\sum_{i=0}^{\infty}n_{i}\bmod 2,\quad n=0,1,\ldots$

if

$n=\sum_{i=0}^{\infty}n_{i}2^{i},\quad n_{0},n_{1},\ldots\in\\{0,1\\},$

is the binary expansion of $n$. Recently, Drmota, Mauduit and Rivat [6] showed
that the Thue-Morse sequence along squares, that is, $(t_{n^{2}})$ is normal.
It is conjectured but not proved yet that the subsequence of the Thue-Morse
sequence along any polynomial of degree $d\geq 3$ is normal as well, see [6,
Conjecture 1]. Even the weaker problem of determining the frequency of $0$ and
$1$ in the subsequence of the Thue-Morse sequence along any polynomial of
degree $d\geq 3$ seems to be out of reach, see [6, above Conjecture 1].

However, the analog of the latter weaker problem for the Thue-Morse sequence
in the finite field setting was settled by Dartyge and Sárközy [3].

###  1.2 The analog for finite fields

This paper deals with the following analog of the normality problem. Let
$q=p^{r}$ be the power of a prime $p$ and

${\cal B}=(\beta_{1},\ldots,\beta_{r})$

be an ordered basis of the finite field $\mathbb{F}_{q}$ over
$\mathbb{F}_{p}$. Then any $\xi\in\mathbb{F}_{q}$ has a unique representation

$\xi=\sum_{j=1}^{r}x_{j}\beta_{j}\quad\mbox{with }x_{j}\in\mathbb{F}_{p},\quad
j=1,\ldots,r.$

The coefficients $x_{1},\ldots,x_{r}$ are called the digits with respect to
the basis ${\cal B}$.

Dartyge and Sárközy [3] introduced the Thue-Morse or sum-of-digits function
$T(\xi)$ for the finite field $\mathbb{F}_{q}$ with respect to the basis
${\cal B}$:

$T(\xi)=\sum_{i=1}^{r}x_{i},\quad\xi=x_{1}\beta_{1}+\cdots+x_{r}\beta_{r}\in\mathbb{F}_{q}.$

For a given pattern length $s$ with $1\leq s\leq q$, a subset

${\cal A}=\\{\alpha_{1},\ldots,\alpha_{s}\\}\subset\mathbb{F}_{q},$

a polynomial $f(X)\in\mathbb{F}_{q}[X]$ and a vector
$\underline{c}=(c_{1},\ldots,c_{s})\in\mathbb{F}_{p}^{s}$ we put

${\cal T}(\underline{c},{\cal
A},f)=\\{\xi\in\mathbb{F}_{q}:T(f(\xi+\alpha_{i}))=c_{i},~{}i=1,\ldots,s\\}.$

In [3] the Weil bound, see Lemma 1 below, was used to bound the cardinality of
${\cal T}(\underline{c},{\cal A},f)$ for $s=1$:

Let $f(X)\in\mathbb{F}_{q}[X]$ be a polynomial of degree $d$. Then for all
$c\in\mathbb{F}_{p}$

$\left||{\cal T}(c,f)|-p^{r-1}\right|\leq(d-1)q^{1/2},\quad\gcd(d,p)=1,$ (1)

where

${\cal T}(c,f)=\\{\xi\in\mathbb{F}_{q}:T(f(\xi))=c\\}.$

Note that the condition $\gcd(d,p)=1$ can be relaxed to the condition that
$f(X)$ is not of the form $g(X)^{p}-g(X)+c$ for some
$g(X)\in\mathbb{F}_{q}[X]$ and $c\in\mathbb{F}_{q}$. For example, $f(X)=X^{p}$
is not of the form $g(X)^{p}-g(X)+c$ but does not satisfy $\gcd(d,p)=1$.

Our goal is to prove that, under some natural conditions, the size of ${\cal
T}(\underline{c},{\cal A},f)$ is asymptotically the same for all
$\underline{c}$ and ${\cal A}$.

###  1.3 Results of this paper

First we study monomials and prove the following result in Section 4.

######  Theorem 1.

Let $d$ be any integer with $1\leq d<q$ with unique representation

$d=(d_{0}+d_{1}p+\ldots+d_{n-1}p^{n-1})\gcd(d,q)$

where

$1\leq n\leq r-\frac{\log(\gcd(d,q))}{\log p},\quad 0\leq
d_{i}<p,~{}i=0,\ldots,n-1,~{}d_{0}d_{n-1}\neq 0.$

Let denote by

$f_{d}(X)=X^{d}\in\mathbb{F}_{q}[X]$

the monomial of degree $d$ and if $n\geq 2$, assume

$d_{m}=d_{m+1}=\ldots=d_{m+k-1}=p-1$

for some $m$ and $k$ with

$1\leq m\leq m+k\leq n-1.$

1\. For any positive integer

$s\leq\left\\{\begin{array}[]{cc}\max\left\\{d_{0},(d_{m+k}+1)p^{k}\right\\},&n\geq
2,\\\ d_{0},&n=1,\end{array}\right.$ (2)

any ${\cal A}\subset\mathbb{F}_{q}$ of size $s$ and any
$\underline{c}\in\mathbb{F}_{p}^{s}$ we have

$\left||{\cal T}(\underline{c},{\cal
A},f_{d})|-p^{r-s}\right|\leq\left(\frac{d}{\gcd(d,q)}-1\right)q^{1/2}.$

2\. Conversely, if

$(d_{0}+1)(d_{1}+1)\cdots(d_{n-1}+1)\leq p,$ (3)

for any integer $s$ with

$q\geq s\geq(d_{0}+1)(d_{1}+1)\cdots(d_{n-1}+1),$ (4)

there is ${\cal A}\subset\mathbb{F}_{q}$ of size $s$ and a vector
$\underline{c}\in\mathbb{F}_{p}^{s}$ for which ${\cal T}(\underline{c},{\cal
A},f_{d})$ is empty.

3\. For any $s$ with

$q\geq s>((d_{0}+1)(d_{1}+1)\cdots(d_{n-1}+1)-1)r$ (5)

and any ${\cal A}\subset\mathbb{F}_{q}$ of size $s$ there is a vector
$\underline{c}\in\mathbb{F}_{p}^{s}$ for which ${\cal T}(\underline{c},{\cal
A},f_{d})$ is empty.

For $d<p$ we have the following dichotomy:

######  Corollary 1.

Assume $1\leq d<p$. For $s\leq d$ we have

$\left||{\cal T}(\underline{c},{\cal
A},f_{d})|-p^{r-s}\right|\leq(d-1)q^{1/2}$

and for any $s$ with $q\geq s>d$ there is ${\cal A}\subset\mathbb{F}_{q}$ of
size $s$ and a vector $\underline{c}\in\mathbb{F}_{p}^{s}$ for which ${\cal
T}(\underline{c},{\cal A},f_{d})$ is empty.

Theorem 1 provides two asymptotic formulas for $|{\cal T}(\underline{c},{\cal
A},X^{d})|$ for $r\rightarrow\infty$ and $p\rightarrow\infty$, respectively.

Assume that $p$, $j$, $n$, $d=(d_{0}+d_{1}p+\ldots+d_{n-1}p^{n-1})p^{j}$ and
$s$ satisfying $(\ref{scond})$ are fixed. Then we have

$\lim_{r\rightarrow\infty}\frac{|{\cal T}(\underline{c},{\cal
A},f_{d})|}{p^{r-s}}=1$

for any $\underline{c}\in\mathbb{F}_{p}^{s}$ and ${\cal
A}\subset\mathbb{F}_{q}$ of size $|{\cal A}|=s$. We may say that $T(f_{d})$ is
$r$-normal if $(\ref{scond})$ is satisfied.

Assume that $j=0$ and $d$, $r$ and $s$ are fixed with $1\leq
s\leq\min\\{d,\lfloor(r-1)/2\rfloor\\}$. Then we have

$\lim_{p\rightarrow\infty}\frac{|{\cal T}(\underline{c},{\cal
A},f_{d})|}{p^{r-s}}=1$

for any $\underline{c}\in\mathbb{F}_{p}^{s}$ and ${\cal
A}\subset\mathbb{F}_{q}$ of size $|{\cal A}|=s$. We may say that $T(f_{d})$ is
$p$-normal for $1\leq s\leq\min\\{d,\lfloor(r-1)/2\rfloor\\}$.

Theorem 1 is only non-trivial for small degrees. However, for very large
degrees we prove the following non-trivial result in Section 5.

######  Theorem 2.

Let $f_{q-1-d}(X)=X^{q-1-d}$ be a monomial of degree $q-1-d$ with $1\leq d<q$.
Then for any ${\cal A}\subset\mathbb{F}_{q}$ of size $s$ and any
$\underline{c}\in\mathbb{F}_{p}^{s}$, we have

$\left||{\cal T}(\underline{c},{\cal
A},f_{q-1-d})|-p^{r-s}\right|\leq\left(\left(\frac{d}{\gcd(d,q)}+1\right)s-2\right)q^{1/2}+s+1.$

Note that with the convention $0^{-1}=0$ we have

$\xi^{q-1-d}=\xi^{-d}\quad\mbox{for any }\xi\in\mathbb{F}_{q}$

and can identify the monomial $f_{q-1-d}(X)=X^{q-1-d}$ with the rational
function $f_{-d}(X)=X^{-d}$. However, the latter representation is independent
of $q$ and we can state two asymptotic formulas for $|{\cal
T}(\underline{c},{\cal A},f_{-d})|$ as well.

For any fixed $d$, $p$ and $s$ we have

$\lim_{r\rightarrow\infty}\frac{|{\cal T}(\underline{c},{\cal
A},f_{-d})|}{p^{r-s}}=1,$

that is, $T(f_{-d})$ is $r$-normal.

For any fixed $d$, $s$ and $r$ with $1\leq s\leq\lfloor(r-1)/2\rfloor$ we have

$\lim_{p\rightarrow\infty}\frac{|{\cal T}(\underline{c},{\cal
A},f_{-d})|}{p^{r-s}}=1,$

that is, $T(f_{-d})$ is $p$-normal for $1\leq s\leq\lfloor(r-1)/2\rfloor$.

Finally, we extend our results to arbitrary polynomials in Section 6.

######  Theorem 3.

Let $d$ be any integer with $1\leq d<q$ and $\gcd(d,q)=1$. Denote

$d_{0}\equiv d\bmod p,\quad 1\leq d_{0}<p.$

Let $f(X)\in\mathbb{F}_{q}[X]$ be any polynomial of degree $d$.

1\. For any integer $s$ with

$1\leq s\leq d_{0},$

any ${\cal A}\subset\mathbb{F}_{q}$ of size $s$ and any
$\underline{c}\in\mathbb{F}_{p}^{s}$ we have

$\left||{\cal T}(\underline{c},{\cal A},f)|-p^{r-s}\right|\leq(d-1)q^{1/2}.$

2\. Conversely, if $f(X)\in\mathbb{F}_{p}[X]$, then for any integer $s$ with

$q\geq s\geq d+1,$

there is ${\cal A}\subset\mathbb{F}_{q}$ of size $s$ and a vector
$\underline{c}\in\mathbb{F}_{p}^{s}$ for which ${\cal T}(\underline{c},{\cal
A},f)$ is empty.

3\. For any $f(X)\in\mathbb{F}_{q}[X]$, any $s$ with

$q\geq s\geq dr$

and any ${\cal A}\subset\mathbb{F}_{q}$ of size $s$ there is a vector
$\underline{c}\in\mathbb{F}_{p}^{s}$ for which ${\cal T}(\underline{c},{\cal
A},f)$ is empty.

The restriction $\gcd(d,p)=1$ is needed. We give counter-examples of degree
$d$ with $\gcd(d,p)>1$ in Section 7.1.

Again, for $f(X)\in\mathbb{F}_{p}[X]$ and $1\leq d<p$ we have a dichotomy.

Moreover, for any fixed $d$, $p$ and $s$ with $\gcd(d,q)=1$ and $1\leq s\leq
d_{0}$ and any $f(X)\in\mathbb{F}_{p}[X]$ of degree $d$, $T(f)$ is $r$-normal.
Note that any $f(X)\in\mathbb{F}_{p}[X]$ is an element of
$\mathbb{F}_{p^{r}}[X]$ for $r=1,2,\ldots$

For fixed $d$, $r$ and $s$ with $1\leq s\leq\min\\{d,\lfloor(r-1)/2\rfloor\\}$
and any $f(X)\in\mathbb{Z}[X]$ of degree $d$, $T(f)$ is $p$-normal. Here
$f(X)\in\mathbb{Z}[X]$ can be identified with an element of
$\mathbb{F}_{p}[X]$ for all primes $p$.

We start with a section on preliminary results used in the proofs. Then we
show that

$\left||{\cal T}(\underline{c},{\cal
A},f)|-p^{r-s}\right|\leq(\deg(f)-1)q^{1/2}$ (6)

under certain conditions in Section 3. In Sections 4 to 6 we show that these
conditions are fulfilled under the assumptions of our theorems. We finish the
paper with some remarks on related work in Section 7.

##  2 Preliminary results

We start with the Weil bound, see [11, Theorem 5.38 and comments below], [20,
Theorem 2E] or [23].

######  Lemma 1.

Let $\psi$ be the additive canonical character of the finite field
$\mathbb{F}_{q}$, and $f(X)$ be a polynomial of degree $d\geq 1$ over
$\mathbb{F}_{q}$, which is not of the form $g(X)^{p}-g(X)+c$ for some
polynomial $g(X)\in\mathbb{F}_{q}[X]$ and $c\in\mathbb{F}_{q}$. Then we have

$\left|\sum_{\xi\in\mathbb{F}_{q}}\psi\left(f(\xi)\right)\right|\leq(d-1)q^{1/2}.$

We also use the analog of the Weil bound for rational functions

$\frac{f(X)}{g(X)}\in\mathbb{F}_{q}(X)$

of C. Moreno and O. Moreno [14, Theorem $2$]. We only need the special case
that $\deg(f)\leq\deg(g)$.

######  Lemma 2.

Let $\psi$ be a nontrivial additive character of $\mathbb{F}_{q}$ and let
$\frac{f(X)}{g(X)}\in\mathbb{F}_{q}(X)$ be a rational function over
$\mathbb{F}_{q}$. Let $s$ be the number of distinct roots of the polynomial
$g(X)$ in the algebraic closure $\overline{\mathbb{F}_{q}}$ of
$\mathbb{F}_{q}$. Suppose that $\frac{f(X)}{g(X)}$ is not of the form
$H(X)^{p}-H(X)$, where $H(X)$ is a rational function over
$\overline{\mathbb{F}_{q}}$. If $\deg(f)\leq\deg(g)$, then we have

$\left|\sum_{\xi\in\mathbb{F}_{q},g(\xi)\not=0}\psi\left(\frac{f(\xi)}{g(\xi)}\right)\right|\leq(\deg(g)+s-2)\sqrt{q}+1.$

Note that $g(X)^{p}-g(X)+c$ with $g(X)\in\mathbb{F}_{q}(X)$ and
$c\in\mathbb{F}_{q}$ can be written as $h(X)^{p}-h(X)$ for
$h(X)=g(X)+\gamma\in\overline{\mathbb{F}_{q}}(X)$, where
$\gamma\in\overline{\mathbb{F}_{q}}$ is a zero of the polynomial $X^{p}-X-c$.

Next we state Lucas’ congruence, see [12] or [19, Lemma 6.3.10].

######  Lemma 3.

Let $p$ be a prime. If $m$ and $n$ are two natural numbers with $p$-adic
expansions

$m=m_{r-1}p^{r-1}+m_{r-2}p^{r-2}+\ldots+m_{1}p+m_{0},\quad 0\leq
m_{0},\ldots,m_{r-1}<p,$

and

$n=n_{r-1}p^{r-1}+n_{r-2}p^{r-2}+\ldots+n_{1}p+n_{0},\quad 0\leq
n_{0},\ldots,n_{r-1}<p,$

then we have

${m\choose n}\equiv\prod_{j=0}^{r-1}{m_{j}\choose n_{j}}\mod p.$

As a consequence of Lucas’ congruence we can count the number of nonzero
binomials coefficients ${m\choose n}\bmod p$ for fixed $m$. Indeed, by Lucas’
congruence

${m\choose n}\not\equiv 0\mod p\mbox{ if and only if }{m_{j}\choose
n_{j}}\not\equiv 0\mod p\mbox{ for $j=0,\ldots,r-1$},$

or equivalently,

$0\leq n_{j}\leq m_{j}\quad\mbox{for }j=0,\ldots,r-1.$

Therefore, we have the following result of Fine [7, Theorem $2$]:

######  Lemma 4.

Let $p$ be a prime and $m$ an integer with $p$-adic expansion

$m=m_{r-1}p^{r-1}+m_{r-2}p^{r-2}+\ldots+m_{1}p+m_{0},\quad 0\leq
m_{0},\ldots,m_{r-1}<p.$

Then the number of nonzero binomial coefficients ${m\choose n}\bmod p$ with
$0\leq n\leq m$ is

$\prod_{j=0}^{r-1}(m_{j}+1).$

##  3 Trace, dual basis and exponential sums

Let

${\rm Tr}(\xi)=\sum_{i=0}^{r-1}\xi^{p^{i}}\in\mathbb{F}_{p}$

denote the (absolute) _trace_ of $\xi\in\mathbb{F}_{q}$. Let
$(\delta_{1},\ldots,\delta_{r})$ denote the (existent and unique) _dual basis_
of the basis ${\cal B}=(\beta_{1},\ldots,\beta_{r})$ of $\mathbb{F}_{q}$, see
for example [11], that is,

${\rm Tr}(\delta_{i}\beta_{j})=\begin{cases}1&{\rm if}\ i=j,\\\ 0&{\rm if}\
i\not=j,\end{cases}\quad 1\leq i,j\leq r.$

Then we have

${\rm Tr}(\delta_{i}\xi)=x_{i}\quad\mbox{for
any}\quad\xi=\sum_{j=1}^{r}x_{j}\beta_{j}\in\mathbb{F}_{q}\quad\mbox{with
}x_{j}\in\mathbb{F}_{p},$

and

$T(\xi)={\rm Tr}(\delta\xi),\quad\mbox{where
}\delta=\sum_{i=1}^{r}\delta_{i}.$

Note that

$\delta\neq 0$

since $\delta_{1},\ldots,\delta_{r}$ are linearly independent.

Put

$e_{p}(x)=\exp\left(\frac{2\pi ix}{p}\right)\quad\mbox{for
}x\in\mathbb{F}_{p}.$

Since

$\sum_{a\in\mathbb{F}_{p}}e_{p}(ax)=\left\\{\begin{array}[]{cc}0,&x\neq 0,\\\
p,&x=0,\end{array}\right.\quad x\in\mathbb{F}_{p},$

we get

$\displaystyle|{\cal T}(\underline{c},{\cal A},f)|$ $\displaystyle=$
$\displaystyle\frac{1}{p^{s}}\sum_{\xi\in\mathbb{F}_{q}}\prod_{i=1}^{s}\sum_{a\in\mathbb{F}_{p}}e_{p}\left(a(T(f(\xi+\alpha_{i}))-c_{i})\right)$
$\displaystyle=$
$\displaystyle\frac{1}{p^{s}}\sum_{a_{1},\ldots,a_{s}\in\mathbb{F}_{p}}\sum_{\xi\in\mathbb{F}_{q}}e_{p}\left(\sum_{i=1}^{s}a_{i}(T(f(\xi+\alpha_{i}))-c_{i})\right).$

Separating the term for $a_{1}=\ldots=a_{s}=0$ we get

$\left||{\cal T}(\underline{c},{\cal
A},f)|-p^{r-s}\right|\leq\max_{(a_{1},\ldots,a_{s})\neq(0,\ldots,0)}\left|\sum_{\xi\in\mathbb{F}_{q}}\psi(F_{a_{1},\ldots,a_{s}}(\xi))\right|,$
(7)

where

$\psi(\xi)=e_{p}({\rm Tr}(\xi))$

denotes the additive canonical character of $\mathbb{F}_{q}$ and

$F_{a_{1},\ldots,a_{s}}(X)=\delta\sum_{i=1}^{s}a_{i}f(X+\alpha_{i}).$ (8)

If $F_{a_{1},\ldots,a_{s}}(X)$ is not of the form $g(X)^{p}-g(X)+c$ for any
$(a_{1},\ldots,a_{s})\neq(0,\ldots,0)$, then the Weil bound, Lemma 1, can be
applied and yields $(\ref{main})$.

##  4 Monomials $f_{d}(X)=X^{d}$

Now we study the special case

$f(X)=f_{dp^{j}}(X)=X^{dp^{j}}\quad\mbox{with}\quad\gcd(d,p)=1\mbox{ and
}j=0,1,\ldots$

Put ${\cal A}^{k}=\\{\alpha^{k}:\alpha\in{\cal A}\\}$. Since
$(X+\alpha)^{dp^{j}}=(X^{p^{j}}+\alpha^{p^{j}})^{d}$ and
$\xi\mapsto\xi^{p^{j}}$ permutes $\mathbb{F}_{q}$ we have

${\cal T}(\underline{c},{\cal A},f_{dp^{j}})={\cal T}(\underline{c},{\cal
A}^{p^{j}},f_{d})$

and we may assume $j=0$. Since

$\xi^{q}=\xi\quad\mbox{for all }\xi\in\mathbb{F}_{q}$

we may restrict ourselves to the case $d<q$.

To prove the first part of Theorem 1 we have to show that $(\ref{main})$ is
applicable. By $(\ref{Fdef})$ with

$f(X)=f_{d}(X)=X^{d}$

we have

$F_{a_{1},\ldots,a_{s}}(X)=\delta\sum_{i=1}^{s}a_{i}(X+\alpha_{i})^{d}$

and thus

$F^{\prime}_{a_{1},\ldots,a_{s}}(X)=\delta
d\sum_{\ell=0}^{d-1}{d-1\choose\ell}\left(\sum_{i=1}^{s}a_{i}\alpha_{i}^{\ell}\right)X^{d-\ell-1}.$
(9)

Assume that for some
$(a_{1},\ldots,a_{s})\in\mathbb{F}_{p}^{s}\setminus\\{(0,\ldots,0)\\}$ we have

$F_{a_{1},\ldots,a_{s}}(X)=g(X)^{p}-g(X)+c$

for some polynomial $g(X)\in\mathbb{F}_{q}[X]$ and some constant
$c\in\mathbb{F}_{q}$. We have

$\mbox{either
}F_{a_{1},\ldots,a_{s}}(X)=c\quad\mbox{or}\quad\deg(F_{a_{1},\ldots,a_{s}})\equiv
0\bmod p$ (10)

and

$F^{\prime}_{a_{1},\ldots,a_{s}}(X)=-g^{\prime}(X).$

Then either

$F^{\prime}_{a_{1},\ldots,a_{s}}(X)=0$ (11)

or

$\deg(F^{\prime}_{a_{1},\ldots,a_{s}})<\deg(g)=\frac{\deg(F_{a_{1},\ldots,a_{s}})}{p}.$
(12)

Let

$d=d_{0}+d_{1}p+\dots+d_{r-1}p^{r-1},\quad 0\leq d_{0},\ldots,d_{r-1}<p,\quad
d_{0}\not=0,$

be the $p$-adic expansion of $d$. Assume that there are $k\geq 0$ consecutive
digits

$d_{m}=d_{m+1}=\ldots=d_{m+k-1}=p-1,\quad 1\leq m\leq m+k\leq r-1,$

of maximal size and

$s\leq\max\left\\{d_{0},(d_{m+k}+1)p^{k}\right\\}.$

Note that $\deg(F_{a_{1},\ldots,a_{s}})\leq d-d_{0}$ by $(\ref{dmodp})$ with
the convention $\deg(0)=-1$. In both cases, $(\ref{F'1})$ and $(\ref{F'2})$,
the coefficients of $F^{\prime}_{a_{1},\ldots,a_{s}}(X)$ at $X^{d-1-\ell}$ are
zero for $\ell=0,\ldots,d-(d-d_{0})/p-1$. Since $\delta d\not=0$ we get from
$(\ref{deriv})$

${d-1\choose\ell}\left(\sum_{i=1}^{s}a_{i}\alpha_{i}^{\ell}\right)=0,\quad\ell=0,\ldots,d-(d-d_{0})/p-1.$
(13)

By Lucas’ congruence, Lemma 3, we have

${d-1\choose\ell}\equiv{d_{0}-1\choose\ell}\not\equiv 0\bmod
p,\quad\ell=0,\ldots,d_{0}-1,$ (14)

as well as

${d-1\choose p^{m}\ell}\not\equiv 0\bmod
p,\quad\ell=0,\ldots,(d_{m+k}+1)p^{k}-1,$ (15)

since

$d-1=e_{0}+(p-1)(p^{m}+\ldots+p^{m+k-1})+d_{k+m}p^{k+m}+e_{1}p^{k+m+1}$

for some

$0\leq e_{0}<p^{m},~{}0\leq e_{1}<p^{r-k-m-1},$

and

$p^{m}\ell=\ell_{0}p^{m}+\ldots+\ell_{k-1}p^{m+k-1}+\ell_{k}p^{m+k}$

for some

$0\leq\ell_{0},\ldots,\ell_{k-1}<p,~{}0\leq\ell_{k}\leq d_{k+m},$

and any $0\leq\ell\leq(d_{m+k}+1)p^{k}-1$. Combining $(\ref{withbinom})$ with
$(\ref{bin1})$ and $(\ref{bin2})$, respectively, we get

$\sum_{i=1}^{s}a_{i}\alpha_{i}^{\ell}=0,\quad\ell=0,\dots d_{0}-1,$ (16)

and

$\sum_{i=1}^{s}a_{i}\alpha_{i}^{p^{m}\ell}=0,\quad\ell=0,\ldots,(d_{m+k}+1)p^{k}-1,$
(17)

respectively. Hence, if $s\leq d_{0}$ or $s\leq(d_{m+k}+1)p^{k}$, the $s\times
s$ coefficient matrix of the equations for $\ell=0,\ldots,s-1$ of
$(\ref{eqsyst1})$ or $(\ref{eqsyst2})$, respectively, is an invertible
Vandermonde matrix and we get

$a_{i}=0,\quad i=1,\ldots,s,$

contradicting
$(a_{1},\ldots,a_{s})\in\mathbb{F}_{p}^{s}\setminus\\{(0,\ldots,0)\\}$. For
the second case we used that $\xi\mapsto\xi^{p^{m}}$ permutes $\mathbb{F}_{q}$
and the $\alpha_{i}^{p^{m}}$, $i=1,\ldots,s$, are pairwise distinct.

Proof of the second part of Theorem 1: Now assume $d<p^{n}$ for some $n$ with
$1\leq n\leq r$, that is, $d_{n}=\ldots=d_{r-1}=0$, and assume $(\ref{Dcond})$
and $(\ref{scond2})$. Let $D$ be the number of binomial coefficients
${d\choose\ell}$, $\ell=1,\ldots,d$, which are nonzero modulo $p$. By Lemma 4
we have

$D=(d_{0}+1)\cdots(d_{n-1}+1)-1.$

For any $\alpha\in\mathbb{F}_{q}$ the polynomial

$(X+\alpha)^{d}-\alpha^{d}=\sum_{\ell=0}^{d-1}{d\choose\ell}\alpha^{\ell}X^{d-\ell}$

is in the vector space generated by the monomials $X^{d-\ell}$ with nonzero
${d\choose\ell}\bmod p$, $\ell=0,\ldots,d-1$, of dimension $D$. For $D<s\leq
q$ and any subset $\\{\alpha_{1},\ldots,\alpha_{s}\\}$ of $\mathbb{F}_{q}$
there is a nontrivial linear combination

$\sum_{i=1}^{s}\rho_{i}\left((X+\alpha_{i})^{d}-\alpha_{i}^{d}\right)=0$

of the zero polynomial with
$(\rho_{1},\ldots,\rho_{s})\in\mathbb{F}_{q}^{s}\setminus\\{(0,\ldots,0)\\}$.
If $D<s\leq p$ and we take $\alpha_{i}\in\mathbb{F}_{p}$, $i=1,\ldots,s$, then
we may assume $\rho_{i}=a_{i}\in\mathbb{F}_{p}$ and

$\sum_{i=1}^{s}a_{i}{\rm
Tr}\left(\delta\left((\xi+\alpha_{i})^{d}-\alpha_{i}^{d}\right)\right)=0\quad\mbox{for
all }\xi\in\mathbb{F}_{q},$

Taking $(a_{1},\ldots,a_{s})\in\mathbb{F}_{p}^{s}\setminus\\{(0,\ldots,0)\\}$
from the previous step, the vector space of solutions
$(c_{1},\ldots,c_{s})\in\mathbb{F}_{p}^{s}$ of the equation

$a_{1}c_{1}+\ldots+a_{s}c_{s}=0$

is of dimension $s-1$. More precisely, the mapping

$\varphi:\mathbb{F}_{p}^{s}\rightarrow\mathbb{F}_{p},\quad\varphi(c_{1},\ldots,c_{s})=a_{1}c_{1}+\ldots+a_{s}c_{s}$

is surjective since $(a_{1},\ldots,a_{s})$ is not the zero vector. By the
rank-nullity theorem its kernel is of dimension $s-1$. That is, not all
$\underline{c}=(c_{1},\ldots,c_{s})\in\mathbb{F}_{p}^{s}$ are attained as
$\underline{c}=\left({\rm
Tr}\left(\delta\left((\xi+\alpha_{i})^{d}-\alpha_{i}^{d}\right)\right)\right)_{i=1}^{s}$
for any $\xi\in\mathbb{F}_{q}$, namely those $\underline{c}$ which are not in
the kernel of $\varphi$. We can extend this argument to $s>p$ by extending
$(a_{1},\ldots,a_{p})\in\mathbb{F}_{p}^{p}\setminus\\{(0,\ldots,0)\\}$ to
$(a_{1},\ldots,a_{p},0,\ldots,0)\in\mathbb{F}_{p}^{s}\setminus\\{(0,\ldots,0)\\}$.

Proof of the third part of Theorem 1: Now we drop the condition
$(\ref{Dcond})$ but then $s$ has to satisfy the stronger condition
$(\ref{Dcond2})$ instead of $(\ref{scond2})$. For each
$\alpha\in\mathbb{F}_{q}$ we have

${\rm
Tr}(\delta((X+\alpha)^{d}-\alpha^{d}))=\sum_{\ell=0}^{d-1}{d\choose\ell}{\rm
Tr}(\delta\alpha^{\ell}X^{d-\ell}),$

since the trace is $\mathbb{F}_{p}$-linear, and thus it lies in the
$\mathbb{F}_{p}$-linear space generated by the polynomials ${\rm
Tr}(\beta_{i}X^{d-\ell})$ with nonzero ${d\choose\ell}$ modulo $p$,
$i=1,\ldots,r$, $\ell=1,\ldots,d$, of dimension at most $Dr$, where
$\\{\beta_{1},\ldots,\beta_{r}\\}$ is a basis of $\mathbb{F}_{q}$ over
$\mathbb{F}_{p}$. Now let $s>Dr$, then for any subset ${\cal
A}=\left\\{\alpha_{1},\dots\alpha_{s}\right\\}$ of $\mathbb{F}_{q}$ consider
the set of polynomials

$\left\\{{\rm
Tr}(\delta((X+\alpha_{i})^{d}-\alpha_{i}^{d})):i=1,\ldots,s\right\\}.$

Since $s>Dr$ there is a nontrivial $\mathbb{F}_{p}$-linear combination

$\sum_{i=1}^{s}a_{i}{\rm Tr}(\delta((X+\alpha_{i})^{d}-\alpha_{i}^{d}))=0$

of the zero polynomial. Now consider the linear subspace of solutions
$(c_{1},\ldots,c_{s})\in\mathbb{F}_{p}^{s}$ of the equation
$a_{1}c_{1}+\dots+a_{s}c_{s}=0$ which is of dimension $s-1$. Let
$\underline{c}\in\mathbb{F}_{p}^{s}$ be a point which does not lie in this
linear subspace, then $\underline{c}$ is not attained as $\underline{c}=({\rm
Tr}(\delta((\xi+\alpha_{i})^{d}-\alpha_{i}^{d})))_{i=1}^{s}$ for any
$\xi\in\mathbb{F}_{q}$.

##  5 Rational functions $f_{-d}(X)=X^{-d}$

Let $f_{q-d-1}(X)=X^{q-1-d}$ be a monomial of degree $q-d-1$, where $1\leq
d<q$. With the convention $0^{-1}=0$ we can identify $f_{q-d-1}(X)$ with the
rational function $f_{-d}(X)=X^{-d}$. Let $\gcd(d,q)=p^{j}$. Since

$(X+\alpha)^{-p^{j}}=(X^{p^{j}}+\alpha^{p^{j}})^{-1}$

and $\xi\mapsto\xi^{p^{j}}$ permutes $\mathbb{F}_{q}$ we have

${\cal T}(\underline{c},{\cal A},f_{-dp^{j}})={\cal T}(\underline{c},{\cal
A}^{p^{j}},f_{-d})$

and may restrict ourselves to the case $\gcd(d,q)=1$, that is,

$d=d_{0}+t_{1}p,\quad\mbox{where }1\leq d_{0}<p.$

We first show that there is no nonzero $s$-tuple

$(a_{1},\ldots,a_{s})\in\mathbb{F}_{p}^{s}\setminus\\{(0,\ldots,0)\\}$

such that

$F_{a_{1},\dots,a_{s}}(X)=\delta\sum_{i=1}^{s}a_{i}(X+\alpha_{i})^{-d}=H(X)^{p}-H(X)$

for any rational function $H(X)\in\overline{\mathbb{F}_{p}}(X)$. We have

$F_{a_{1},\dots,a_{s}}(X)=\frac{f(X)}{g(X)},$

where

$f(X)=\sum_{j=1}^{s}a_{j}\prod_{i\not=j}(X+\alpha_{i})^{d}$

and

$g(X)=\prod_{i=1}^{s}(X+\alpha_{i})^{d}.$

Suppose to the contrary that there exists a rational function

$H(X)=\frac{u(X)}{v(X)}\in\overline{\mathbb{F}_{p}}(X)\quad\mbox{with
}\gcd(u,v)=1\mbox{ and }v(X)\mbox{ is monic}$

satisfying

$F_{a_{1},\ldots,a_{s}}(X)=H(X)^{p}-H(X).$

Therefore, we have

$\frac{f(X)}{g(X)}=\frac{u(X)^{p}}{v(X)^{p}}-\frac{u(X)}{v(X)}.$ (18)

Clearing denominators we obtain

$f(X)v(X)^{p}=(u(X)^{p}-u(X)v(X)^{p-1})g(X)$

and thus $v(X)^{p}$ divides $g(X)$, hence

$v(X)=\prod_{i=1}^{s}(X+\alpha_{i})^{e_{i}}\quad\mbox{for some }0\leq
e_{i}\leq t_{1},~{}i=1,\ldots,s.$

Now by taking derivatives of both sides of (18) and clearing denominators we
get

$(f^{\prime}(X)g(X)-f(X)g^{\prime}(X))v(X)^{2}=(u(X)v^{\prime}(X)-u^{\prime}(X)v(X))g(X)^{2}.$
(19)

Without loss of generality we may assume $a_{1}\neq 0$, thus

$f(-\alpha_{1})=a_{1}\prod_{i=2}^{s}(\alpha_{i}-\alpha_{1})^{d}\neq 0$

and

$X+\alpha_{1}\mbox{ does not divide }f(X).$

Moreover, $(X+\alpha_{1})^{d-1}$ and $(X+\alpha_{1})^{d}$ are the largest
powers dividing $g^{\prime}(X)$ and $g(X)$, respectively, that is,

$(X+\alpha_{1})^{d-1+2e_{1}}$

is the largest power of $(X+\alpha_{1})$ dividing the left hand side of
$(\ref{deriveq})$. Observing that $g(X)^{2}$ and thus the right hand side of
$(\ref{deriveq})$ is divisible by

$(X+\alpha_{1})^{2d}$

we get

$d-1+2e_{1}\geq 2d$

and thus

$e_{1}\geq\frac{d+1}{2}>\frac{t_{1}p}{2}\geq t_{1},$

which is a contradiction.

We showed that the conditions of Lemma 2 are satisfied and Theorem 2 follows
from $(\ref{redchar})$ and Lemma 2 since

$\left|\sum_{\xi\in\mathbb{F}_{q}}\psi(F_{a_{1},\ldots,a_{s}}(\xi))\right|\leq\left|\sum_{\xi\in\mathbb{F}_{q}\setminus-{\cal
A}}\psi(F_{a_{1},\ldots,a_{s}}(\xi))\right|+s,$

where $-{\cal A}=\\{-\alpha_{1},\ldots,-\alpha_{s}\\}$.

##  6 Arbitrary polynomials

In this section we prove Theorem 3.

Let

$f(X)=\sum_{j=0}^{d}\gamma_{j}X^{j}\in\mathbb{F}_{q}[X],\quad\gamma_{d}\neq
0,$

be a polynomial of degree

$d=d_{0}+t_{1}p,\quad 1\leq d_{0}<p,~{}0\leq t_{1}<q/p.$

Proof of the first part: We have to show that $(\ref{main})$ is applicable,
that is, the polynomial $F_{a_{1},\ldots,a_{s}}(X)$ defined by $(\ref{Fdef})$
is not of the form $g(X)^{p}-g(X)+c$ for any
$(a_{1},\ldots,a_{s})\neq(0,\ldots,0)$.

Suppose the contrary that there exists an $s$-tuple

$(a_{1},\ldots,a_{s})\in\mathbb{F}_{p}^{s}\setminus\\{(0,\ldots,0)\\}$

such that the polynomial

$F_{a_{1},\ldots,a_{s}}(X)=\delta\sum_{\ell=0}^{d}\left(\sum_{j=\ell}^{d}\sum_{i=1}^{s}a_{i}\gamma_{j}{j\choose\ell}\alpha_{i}^{j-\ell}\right)X^{\ell}$

can be written as

$g(X)^{p}-g(X)+c\quad\mbox{for some }g(X)\in\mathbb{F}_{q}[X]\mbox{ and
}c\in\mathbb{F}_{q}.$

We have either

$F_{a_{1},\dots,a_{s}}(X)=0$

or

$\deg(F_{a_{1},\ldots,a_{s}})\equiv 0\bmod p.$

Hence,

$\deg(F_{a_{1},\dots,a_{s}})\leq d-d_{0},$

where we used the convention $\deg(0)=-1$. We conclude that the coefficients
$\delta R_{\ell}$ of $F_{a_{1},\dots,a_{s}}(X)$ at $X^{\ell}$ vanish for
$\ell=d-d_{0}+1,\dots,d$. Since $\delta\not=0$ we have

$R_{\ell}=\sum_{j=\ell}^{d}\sum_{i=1}^{s}a_{i}\gamma_{j}{j\choose\ell}\alpha_{i}^{j-\ell}=0,\quad\ell=(d-d_{0})+1,\ldots,d.$
(20)

Note that by Lucas’ congruence, Lemma 3,

${d\choose r}\equiv{d_{0}\choose r}\not\equiv 0\bmod p,\quad
r=0,\ldots,d_{0}.$ (21)

Define $T_{\ell}$, $\ell=0,\ldots d_{0}-1$, recursively by

$T_{0}=R_{d}$

and

$T_{\ell}=R_{d-\ell}-\gamma_{d}^{-1}\sum_{r=0}^{\ell-1}\gamma_{d-\ell+r}{r+d-\ell\choose
d-\ell}{d\choose r}^{-1}T_{r},$ (22)

for $\ell=1,\ldots,d_{0}-1$.

Next we show that

$T_{\ell}=\gamma_{d}{d\choose\ell}\sum_{i=1}^{s}a_{i}\alpha_{i}^{\ell}=0,\quad\ell=0,\ldots,d_{0}-1.$
(23)

For $\ell=0$ the formula follows from (20) and for $\ell=1,\ldots,d_{0}-1$
from (22) we get by induction

$T_{\ell}=R_{d-\ell}-\sum_{r=0}^{\ell-1}\gamma_{d-\ell+r}{r+d-\ell\choose
d-\ell}\sum_{i=1}^{s}a_{i}\alpha_{i}^{r}$

and from (20)

$T_{\ell}=\gamma_{d}{d\choose\ell}\sum_{i=1}^{r}a_{i}\alpha_{i}^{\ell}.$

Moreover, we get

$T_{\ell}=0,\quad\ell=0,\ldots,d_{0}-1,$

from (20), (22) again by induction.

By (23) and $(\ref{binr})$ we get since $\gamma_{d}\neq 0$,

$\sum_{i=1}^{s}a_{i}\alpha_{i}^{\ell}=0,\quad\ell=0,\ldots,d_{0}-1.$

Thus for $s\leq d_{0}$, the $(s\times s)$-coefficient matrix

$\left(\alpha_{i}^{\ell}\right)_{i=1,\ldots,s,\ell=0,1,\ldots,s-1}$

of the system of the first $s$ equations is a regular Vandermonde matrix and
we get $(a_{1},\ldots,a_{s})=(0,\ldots,0)$, which is a contradiction.

For the second part of Theorem 3 we assume $f(X)\in\mathbb{F}_{p}[X]$ and
notice that for any $\alpha\in\mathbb{F}_{q}$ the element
$f(X+\alpha)-f(\alpha)$ is in the vector space generated by the monomials
$X^{i}$, $i=1,\ldots,d$, of dimension $d$.

If $d<s\leq p$, we can choose any ${\cal A}\subset\mathbb{F}_{p}$. Then

$f(X+\alpha_{i})-f(\alpha_{i}),\quad i=1,\ldots,s,$

are linearly dependent over $\mathbb{F}_{p}$ as well as

${\rm Tr}(\delta(f(X+\alpha_{i})-f(\alpha_{i}))),\quad i=1,\ldots,s,$

that is,

$\sum_{i=1}^{s}a_{i}{\rm Tr}(\delta(f(X+\alpha_{i})-f(\alpha_{i})))=0$

for some
$(a_{1},\ldots,a_{s})\in\mathbb{F}_{p}^{s}\setminus\\{(0,\ldots,0)\\}$ and the
result follows since not all $(c_{1},\ldots,c_{s})\in\mathbb{F}_{p}^{s}$
satisfy $a_{1}c_{1}+\ldots+a_{s}c_{s}=0$.

If $d<p$ and $s>p$, we can choose
$(a_{1},\dots,a_{p})\in\mathbb{F}_{p}^{p}\setminus\\{(0,\ldots,0)\\}$ as in
the case $s=p$ and extend it to
$(a_{1},\dots,a_{p},a_{p+1},\ldots,a_{s})\in\mathbb{F}^{s}_{p}\setminus\\{(0,\ldots,0)\\}$
with $a_{p+1}=\dots=a_{s}=0$.

Proof of the third part of Theorem 3: Recall that
$\\{\beta_{1},\ldots,\beta_{r}\\}$ is a basis of $\mathbb{F}_{q}$ over
$\mathbb{F}_{p}$. Each $f(X+\alpha)-f(\alpha)$ lies in the
$\mathbb{F}_{p}$-vector space generated by

$\beta_{j}X^{i},\quad j=1,\ldots,r,~{}i=1,\ldots,d,$

of dimension $dr$. The dimension of the vector space generated by

${\rm Tr}(\beta_{j}X^{i})\quad j=1,\ldots,r,~{}i=1,\ldots,d,$

is at most $dr$. If $q\geq s>dr$, there is a nontrivial linear combination

$\sum_{i=1}^{s}a_{i}{\rm Tr}(\delta(f(X+\alpha_{i})-f(\alpha_{i})))=0$

for any ${\cal A}\subset\mathbb{F}_{q}$ of size $s$ and the result follows.

##  7 Final Remarks

###  7.1 A counter-example for $\gcd(d,p)>1$

Now we provide an example that the restriction $\gcd(d,q)=1$ in Theorem 3 is
needed.

Choose any $f(X)$ of the form

$f(X)=\delta^{-1}(g(X)^{p}-g(X)+c)\quad\mbox{for some
}g(X)\in\mathbb{F}_{q}[X]\mbox{ and }c\in\mathbb{F}_{q},$

$a_{1}=1$ and $a_{2}=\ldots=a_{s}=0$. Then we obtain

$F_{a_{1},\ldots,a_{s}}(X)=\delta
f(X+\alpha_{1})=g(X+\alpha_{1})^{p}-g(X+\alpha_{1})+c$

and thus

$\displaystyle T(f(\xi+\alpha_{1}))$ $\displaystyle=$ $\displaystyle{\rm
Tr}(\delta f(\xi+\alpha_{1}))={\rm Tr}(F_{a_{1},\ldots,a_{s}}(\xi))$
$\displaystyle=$ $\displaystyle{\rm
Tr}(g(\xi+\alpha_{1})^{p}-g(\xi+\alpha_{1})+c)={\rm Tr}(c)$

for all $\xi\in\mathbb{F}_{q}$, that is, any vector
$(c_{1},\ldots,c_{r})\in\mathbb{F}_{p}^{r}$ with $c_{1}\neq{\rm Tr}(c)$ is not
attained as $(T(f(\xi+\alpha_{i})))_{i=1}^{s}$.

We conclude that for polynomials of degree $d$ with $\gcd(d,p)>1$, the bound
of Theorem 3 may not hold. However, by Theorem 1, for monomials the
restriction $\gcd(d,p)=1$ is not needed.

###  7.2 Missing digits and subsets

For subsets ${\cal D}$ of $\mathbb{F}_{p}$, the closely related problem of
estimating the number of $\xi\in\mathbb{F}_{q}$ with

$f(\xi)\in\\{d_{1}\beta_{1}+\ldots+d_{r}\beta_{r}:d_{1},\ldots,d_{r}\in{\cal
D}\\}$

was studied in [1, 5, 8], that is, $f(\xi)$ ’misses’ the digits in
$\mathbb{F}_{p}\setminus{\cal D}$. It is straightforward to extend these
results combining our approach with certain bounds on character sums to
estimate the number of $\xi\in\mathbb{F}_{q}$ with

$f(\xi+\alpha_{i})\in\\{d_{1}\beta_{1}+\ldots+d_{r}\beta_{r}:d_{1},\ldots,d_{r}\in{\cal
D}\\},\quad i=1,\ldots,s.$

For example, for ${\cal D}=\\{0,\ldots,t-1\\}$ we can use the bound on
exponential sums of [10].

Instead of restricting the set of digits we may restrict the set of $\xi$.
That is, for a subset ${\cal S}$ of $\mathbb{F}_{q}$ we are interested in the
number of solutions $\xi\in{\cal S}$ of

$(T(f(\xi+\alpha_{1})),\ldots,T(f(\xi+\alpha_{s})))=\underline{c}$

for any fixed $\underline{c}\in\mathbb{F}_{p}^{s}$. Typical choices of ${\cal
S}$ are ’boxes’ [4, 10] and ’consecutive’ elements [24].

###  7.3 Optimality and prescribed digits

Swaenepoel [21] improved the bound (1) of [3] in the case when the polynomial
$f(X)$ has degree $2$ or is a monomial. In particular, for $s=1$ and $d=2$ the
improved bound of [21] is optimal. She also generalized (1) to several
polynomials with $\mathbb{F}_{p}$-linearly independent leading coefficients
[21, Theorem 5.1].

Moreover, in [22] Swaenepoel studied the number of solutions
$\xi\in\mathbb{F}_{q}$ for which some of the digits of $f(\xi)$ are
prescribed, that is, for given ${\cal I}\subset\\{1,\ldots,r\\}$ and given
$c_{i}\in\mathbb{F}_{p}$, $i\in{\cal I}$, the number of $\xi\in\mathbb{F}_{q}$
with

${\rm Tr}(\delta_{i}f(\xi))=c_{i},\quad i\in{\cal I}.$

###  7.4 Related work on pseudorandom number generators

Some of the ideas of the proofs in this paper are based on earlier work on
nonlinear, in particular, inversive pseudorandom number generators, see [13,
17, 18].

More precisely, in [18] the $q$-periodic sequence $(\eta_{n})$ over
$\mathbb{F}_{q}$ defined by

$\eta_{n_{1}+n_{2}p+\dots+n_{r}p^{r-1}}=f(n_{1}\beta_{1}+\ldots+n_{r}\beta_{r}),\quad
0\leq n_{1},\ldots,n_{r}<p,$

passes the $s$-dimensional lattice test if $s$ polynomials of the from

$f(X+\alpha_{j})-f(X),\quad j=1,\ldots,s,$

are $\mathbb{F}_{q}$-linearly independent. However, in the proofs of this
paper we need that they are linearly independent over $\mathbb{F}_{p}$.

To prove Theorem 2 for $d<p$, the method of [17] can be easily adjusted using
[17, Lemma 2]. However, for $d\geq p$ we had to use a different approach since
[17, Lemma 2] is not applicable in this case.

Finally, in the proof of [13, Theorem 4] we showed that polynomials of the
form $F_{a_{1},\ldots,a_{s}}(X)$ can only be identical $0$ if
$a_{1}=\ldots=a_{s}=0$. However, in the proof of Theorem 3 we had to show that
$F_{a_{1},\ldots,a_{s}}(X)$ is not of the form $g(X)^{p}-g(X)+c$ and we had to
modify the idea of [13].

###  7.5 Rudin-Shapiro function

The Rudin-Shapiro sequence $(r_{n})$ is defined by

$r_{n}=\sum_{i=0}^{\infty}n_{i}n_{i+1},\quad n=0,1,\ldots$

if

$n=\sum_{i=0}^{\infty}n_{i}2^{i},\quad n_{0},n_{1},\ldots\in\\{0,1\\}.$

Müllner showed that the Rudin-Shapiro sequence along squares $(r_{n^{2}})$ is
normal [15].

The _Rudin-Shapiro function_ $R(\xi)$ for the finite field $\mathbb{F}_{q}$
with respect to the ordered basis $(\beta_{1},\ldots,\beta_{r})$ is defined as

$R(\xi)=\sum_{i=1}^{r-1}x_{i}x_{i+1},\quad\xi=x_{1}\beta_{1}+x_{2}\beta_{2}+\dots+x_{r}\beta_{r},\quad
x_{1},\ldots,x_{r}\in\mathbb{F}_{p}.$

For $f(X)\in\mathbb{F}_{q}[X]$ and $c\in\mathbb{F}_{p}$ let

${\cal R}(c,f)=\left\\{\xi\in\mathbb{F}_{q}:R(f(\xi))=c\right\\}.$

It seems to be not possible to use character sums to estimate the size of
${\cal R}(c,f)$. However, in [2] the Hooley-Katz Theorem, see [16, Theorem
7.1.14] or [9] was used to show that if $d=\deg(f)\geq 1$,

$\left|{\cal R}(c,f)-p^{r-1}\right|\leq C_{r,d}p^{\frac{3r+1}{4}},$

where $C_{r,d}$ is a constant depending only on $r$ and $d$. In particular, we
have for fixed $d$ and $r\geq 6$,

$\lim_{p\rightarrow\infty}\frac{|{\cal R}(c,f)|}{p^{r-1}}=1,$

that is, $R(f)$ is $p$-normal for $s=1$ and $r\geq 6$.

However, we are not aware of a result on the $r$-normality of $R(f)$.

## Acknowledgment

The authors are partially supported by the Austrian Science Fund FWF Project P
30405. They wish to thank the anonymous referee for very useful suggestions.

## References

  * [1] C. Dartyge, C. Mauduit, A. Sárközy, Polynomial values and generators with missing digits in finite fields. Funct. Approx. Comment. Math. 52 (2015), no. 1, 65–74.
  * [2] C. Dartyge, L. Mérai, A. Winterhof, On the distribution of the Rudin-Shapiro function for finite fields, Proc. Amer. Math. Soc., to appear.
  * [3] C. Dartyge, A. Sárközy, The sum of digits function in finite fields. Proc. Amer. Math. Soc. 141 (2013), no. 12, 4119–4124.
  * [4] H. Davenport, D. J. Lewis, Character sums and primitive roots in finite fields. Rend. Circ. Mat. Palermo (2) 12 (1963), 129–136.
  * [5] R. Dietmann, C. Elsholtz, I. E. Shparlinski, Prescribing the binary digits of squarefree numbers and quadratic residues. Trans. Amer. Math. Soc. 369 (2017), no. 12, 8369–8388.
  * [6] M. Drmota, C. Mauduit, J. Rivat, Normality along squares. J. Eur. Math. Soc. (JEMS) 21 (2019), no. 2, 507–548.
  * [7] N. Fine, Binomial coefficients modulo a prime. Amer. Math. Monthly 54 (1947), 589–-592.
  * [8] M. R. Gabdullin, On the squares in the set of elements of a finite field with constraints on the coefficients of its basis expansion. (Russian) Mat. Zametki 100 (2016), no. 6, 807–824; translation in Math. Notes 101 (2017), no. 1-2, 234–249.
  * [9] C. Hooley, On the number of points on a complete intersection over a finite field. With an appendix by N. M. Katz. J. Number Theory 38 (1991), no. 3, 338–358.
  * [10] S. V. Konyagin, Estimates for character sums in finite fields. (Russian) Mat. Zametki 88 (2010), no. 4, 529–542; translation in Math. Notes 88 (2010), no. 3-4, 503–515.
  * [11] R. Lidl, H. Niederreiter, Finite fields. Second edition. Encyclopedia of Mathematics and its Applications, 20. Cambridge University Press, Cambridge, 1997.
  * [12] E. Lucas, Théorie des Fonctions Numériques Simplement Périodiques. Amer. J. Math. 1 (2) (1878), 184–196.
  * [13] W. Meidl, A. Winterhof, On the linear complexity profile of explicit nonlinear pseudorandom numbers. Inform. Process. Lett. 85 (2003), no. 1, 13–18.
  * [14] C. J. Moreno, O. Moreno, Exponential sums and Goppa codes. I. Proc. Amer. Math. Soc. 111 (1991), no. 2, 523–531.
  * [15] C. Müllner, The Rudin-Shapiro sequence and similar sequences are normal along squares. Canad. J. Math. 70 (2018), no. 5, 1096–1129.
  * [16] G. L. Mullen, D. Panario (eds.) Handbook of finite fields. Discrete Mathematics and its Applications (Boca Raton). CRC Press, Boca Raton, FL, 2013.
  * [17] H. Niederreiter, A. Winterhof, Incomplete exponential sums over finite fields and their applications to new inversive pseudorandom number generators. Acta Arith. 93 (2000), no. 4, 387–399.
  * [18] H. Niederreiter, A. Winterhof, On the lattice structure of pseudorandom numbers generated over arbitrary finite fields. Appl. Algebra Engrg. Comm. Comput. 12 (2001), no. 3, 265–272.
  * [19] H. Niederreiter, A. Winterhof, Applied number theory. Springer, Cham, 2015.
  * [20] W. M. Schmidt, Equations over finite fields. An elementary approach. Lecture Notes in Mathematics, Vol. 536. Springer-Verlag, Berlin-New York, 1976.
  * [21] C. Swaenepoel, On the sum of digits of special sequences in finite fields. Monatsh. Math. 187 (2018), no. 4, 705–728.
  * [22] C. Swaenepoel, Prescribing digits in finite fields. J. Number Theory 189 (2018), 97–114.
  * [23] A. Weil, On some exponential sums. Proc. Nat. Acad. Sci. USA 34 (1948), 204–207.
  * [24] A. Winterhof, Incomplete additive character sums and applications. Finite fields and applications (Augsburg, 1999), 462–474, Springer, Berlin, 2001.


(B.14) $\displaystyle=\sum_{\ell_{1}+\ell_{2}=\ell\atop\pi(\ell_{2})\parallel
v(j)}\frac{-\left(2\pi(\ell_{1})\cdot\pi(\ell_{2})\right)V(\ell_{1})V(\ell_{2})}{(\omega\cdot\ell_{2}+2b(j)\frac{|\pi(\ell_{2})|}{|v(j)|}-|\pi(\ell_{2})|^{2})(\omega\cdot\ell_{2}+2b(j)\frac{|\pi(\ell_{2})|}{|v(j)|}-2\pi(\ell_{1})\cdot\pi(\ell_{2})-|\pi(\ell_{2})|^{2})}\,,$

and we are going to prove that its symbol

${\mathfrak{T}}(\ell,b,v):=\sum_{\ell_{1}+\ell_{2}=\ell\atop\pi(\ell_{2})\parallel
v}\frac{-\left(2\pi(\ell_{1})\cdot\pi(\ell_{2})\right)V(\ell_{1})V(\ell_{2})}{(\omega\cdot\ell_{2}+2b(j)\frac{|\pi(\ell_{2})|}{|v|}-|\pi(\ell_{2})|^{2})(\omega\cdot\ell_{2}+2b\frac{|\pi(\ell_{2})|}{|v|}-2\pi(\ell_{1})\cdot\pi(\ell_{2})-|\pi(\ell_{2})|^{2})}$

is of order $-2$. In the second case, we set

$R_{j}^{h}(\ell):=\sum_{\ell_{1}+\ell_{2}=\ell\atop\pi(\ell_{2})\nparallel
v(j)}\frac{-\left(2\pi(\ell_{1})\cdot\pi(\ell_{2})\right)V(\ell_{1})V(\ell_{2})}{(\omega\cdot\ell_{2}+2j\cdot\pi(\ell_{2})-|\pi(\ell_{2})|^{2})(\omega\cdot\ell_{2}+2(j-\pi(\ell_{1}))\cdot\pi(\ell_{2})-|\pi(\ell_{2})|^{2})}\,,$
(B.15)

with $h=j-\pi(\ell),$ and we shall prove that
$R\in{{\mathcal{L}}}_{\frac{a^{\prime}}{2};-(2,0)}\,.$
We start with exhibiting estimates on
$|[S_{0},M_{V}]^{\mathtt{T}}|^{\mathtt{T}}_{a^{\prime},-2}$. Let

$f^{\epsilon}(\ell_{1},\ell_{2}):=\omega\cdot\ell_{2}-|\pi(\ell_{2})|^{2}-2\epsilon\pi(\ell_{1})\cdot\pi(\ell_{2})\,,\quad\epsilon\in\\{0,1\\}\,,$
(B.16)

so that the denominators appearing in (B.15) have the form

$(2j\cdot\pi(\ell_{2})+f^{0}(\ell_{1},\ell_{2}))(2j\cdot\pi(\ell_{2})+f^{1}(\ell_{1},\ell_{2}))\,;$

arguing as to obtain estimates (B.10), we observe that
$\forall\epsilon\in\\{0,1\\}$, if $\langle
b\rangle\geq|f^{\epsilon}(\ell_{1},\ell_{2})|\,,$ one has

$\left|\frac{2\langle
b\rangle}{(\omega\cdot\ell_{2}+2b(j)\frac{|\pi(\ell_{2})|}{|v(j)|}-2\epsilon\pi(\ell_{1})\cdot\pi(\ell_{2})-|\pi(\ell_{2})|^{2})}\right|\leq
2\,,$ (B.17)

while if $\langle b\rangle<|f^{\epsilon}(\ell_{1},\ell_{2})|\,,$ one has

$\displaystyle\left|\frac{2\langle
b\rangle}{(\omega\cdot\ell_{2}+2b(j)\frac{|\pi(\ell_{2})|}{|v(j)|}-2\epsilon\pi(\ell_{1})\cdot\pi(\ell_{2})-|\pi(\ell_{2})|^{2})}\right|\leq$
(B.18)
$\displaystyle\frac{2|f^{\epsilon}(\ell_{1},\ell_{2})|}{\left|(\omega\cdot\ell_{2}+2b(j)\frac{|\pi(\ell_{2})|}{|v(j)|}-2\epsilon\pi(\ell_{1})\cdot\pi(\ell_{2})-|\pi(\ell_{2})|^{2})\right|}\lesssim\frac{|\ell_{2}|^{2}|\ell_{1}|}{\gamma|\ell_{2}|^{-\tau}}\lesssim\gamma^{-1}|\ell_{2}|^{\tau+2}|\ell_{1}|\,.$

Let now $\theta:=({\mathtt{a}}-2a^{\prime})/2$. Combining (B.17) and (B.18)
and recalling that, since $\pi(\ell_{2})\parallel v$ and $v$ is a generator,
one has ${\mathtt{c}}|v|\leq{\mathtt{c}}|\pi(\ell_{2})|\leq|\ell_{2}|$, one
obtains

$\displaystyle{|[S_{0},M_{V}]^{\mathtt{T}}|}^{\mathtt{T}}_{a^{\prime},-2}\lesssim\sum_{\ell}e^{{a^{\prime}{\mathtt{c}}|v|+{a^{\prime}}|\ell|}}\sum_{\ell_{1}+\ell_{2}=\ell\atop\pi(\ell_{2})\parallel
v}|V(\ell_{1})V(\ell_{2})||\ell_{2}|^{2(\tau+2)+1}|\ell_{1}|^{3}$
$\displaystyle\lesssim\sum_{\ell}{e^{{a^{\prime}}|\ell|}}\sum_{\ell_{1}+\ell_{2}=\ell\atop\pi(\ell_{2})\parallel
v}{e^{a^{\prime}|\ell_{2}|}}|V(\ell_{1})V(\ell_{2})||\ell_{2}|^{2(\tau+2)+1}|\ell_{1}|^{3}$
$\displaystyle\lesssim\sum_{\ell_{1},\ell_{2}}{e^{{a^{\prime}}|\ell_{1}|+{2a^{\prime}}|\ell_{2}|}}|\ell_{2}|^{2(\tau+2)+1}|\ell_{1}|^{3}|V(\ell_{1})||V(\ell_{2})|\lesssim_{{\mathtt{c}},\tau}{({\mathtt{a}}-2a^{\prime})}^{-2(\tau+2)-4}\|V\|_{{\mathtt{a}},{\mathtt{p}}}^{2}\,,$

provided $2a^{\prime}\leq{\mathtt{a}}$.
We now turn to prove that $R$ defined as in (B.15) belongs to
${\mathcal{L}}_{\frac{a^{\prime}}{2},-(2,0)}$. Letting $j_{\rm
min}:=2^{\frac{1}{2\delta}}$, we decompose $R=R_{1}+R_{2}+R_{3}$ as follows:

$\displaystyle(R_{1})_{j}^{h}(\ell)=R_{j}^{h}(\ell)\quad\textrm{ if
}\max\\{|\ell|,|\ell_{1}|,|\ell_{2}|\\}>{\mathtt{c}}\langle
j\rangle^{\delta}\,,\quad(R_{1})_{j}^{h}(\ell)=0\quad\textrm{otherwise}\,;$
$\displaystyle(R_{2})_{j}^{h}(\ell)=R_{j}^{h}(\ell)\quad\textrm{ if }\langle
j\rangle\leq j_{\min}\,,\quad(R_{2})_{j}^{h}(\ell)=0\quad\textrm{
otherwise}\,;$
$\displaystyle(R_{3})_{j}^{h}(\ell)=R_{j}^{h}(\ell)\quad\textrm{ if
}\max\\{|\ell|,|\ell_{1}|,|\ell_{2}|\\}\leq{\mathtt{c}}\langle
j\rangle^{\delta}\quad\textrm{ and }\langle j\rangle\geq
j_{\min}\,,\quad(R_{3})_{j}^{h}(\ell)=0\quad\textrm{otherwise}\,.$

Arguing as to prove estimate (B.12), one easily sees that
$R_{1},R_{2}\in{\mathcal{L}}_{\frac{a^{\prime}}{2},-(N,0)}$ for any
$N\in{\mathbb{N}}$. We now prove that
$R_{3}\in{\mathcal{L}}_{\frac{a^{\prime}}{2},-(2,0)}$.
First of all, we claim the following:

$(R_{3})_{j}^{h}(\ell)\neq
0\quad\Longrightarrow\quad|j\cdot\pi(\ell_{2})|>\langle j\rangle^{\mu}\,.$
(B.19)

Indeed, if $(R_{3})_{j}^{h}(\ell)\neq 0,$ then by definition of $R_{3}$ and
$R$ one has $\langle j\rangle\geq j_{\min},$ $|\ell_{2}|<{\mathtt{c}}\langle
j\rangle^{\delta}$ and $\pi(\ell_{2})\not\parallel v(j)$. But then
$|\ell_{2}|<{\mathtt{c}}\langle j\rangle^{\delta}$ implies that
$|\pi(\ell_{2})|<\langle j\rangle^{\delta}$. Fixing $w\in{\mathcal{V}}$ to be
the direction parallel to $\pi(\ell_{2})$ one has $|w|<\langle
j\rangle^{\delta}$, hence

$|\pi(\ell_{2})\cdot j|\geq|w\cdot
j|\geq|b(j)|:=\min_{v\in{\mathcal{V}}:|v|<\langle j\rangle^{\delta}}|j\cdot
v|$

Then, if $|b(j)|>\langle j\rangle^{\mu}$ our claim follows. Otherwise, we
prove the claim by contradiction. Recall that $v(j)$ attains the minimum above
and, since $\pi(\ell_{2})\nparallel v(j)$, $v(j)\not\parallel w$. If $|w\cdot
j|\leq\langle j\rangle^{\mu}$ then, by Lemma 2.11

$\langle j\rangle<\sqrt{2}\langle j\rangle^{1-\delta}$

which contradicts $\langle j\rangle\geq 2^{\frac{1}{2\delta}}$. This proves
that (B.19) holds.
As a consequence, taking $f^{\epsilon}(\ell_{1},\ell_{2})$ as in (B.16), one
has that, if $(R_{3})_{j}^{j}(\ell)\neq 0$, then $\forall\epsilon\in\\{0,1\\}$

$\displaystyle\frac{\langle
j\rangle^{\mu}}{|\omega\cdot\ell_{2}+2j\cdot\pi(\ell_{2})-\epsilon
2\pi(\ell_{1})\cdot\pi(\ell_{2})-|\pi(\ell_{2})|^{2}|}=\frac{\langle
j\rangle^{\mu}}{|2j\cdot\pi(\ell_{2})+f^{\epsilon}(\ell_{1},\ell_{2})|}$
$\displaystyle\leq\frac{\langle j\rangle^{\mu}}{2\langle
j\rangle^{\mu}-|\omega||\ell_{2}|-\mathtt{c}^{-2}|\ell_{2}|^{2}-2\mathtt{c}^{-2}|\ell_{1}||\ell_{2}|}\leq\frac{\langle
j\rangle^{\mu}}{2\langle
j\rangle^{\mu}-(|\omega|+2\mathtt{c}^{-2}){\mathtt{c}}^{2}\langle
j\rangle^{2\delta}}\leq 1\,,$

since $\langle j\rangle\geq j_{\rm min}.$ This proves that

$\displaystyle\left|((\underline{R_{3}})_{\frac{a^{\prime}}{2};-(2,0)})_{j}^{h}\right|:=\sum_{\ell:j-h=\pi(\ell)}e^{\frac{a^{\prime}}{2}|\ell|}|(R_{3})_{j}^{j^{\prime}}(\ell)|\langle
j\rangle^{2\mu}$
$\displaystyle\lesssim_{\mathtt{c}}\sum_{\ell:j-h=\pi(\ell)}e^{\frac{a^{\prime}}{2}|\ell|}\sum_{\ell_{1}+\ell_{2}=\ell\atop\pi(\ell_{2})\nparallel
v(j)}|V(\ell_{1})V(\ell_{2})||\pi(\ell_{1})||\pi(\ell_{2})|\lesssim_{\mathtt{c}}{\mathtt{a}}^{-2}e^{-({\mathtt{a}}-\frac{a^{\prime}}{2})|j-h|}\|V\|^{2}_{{\mathtt{a}},{\mathtt{p}}}\,,$

and thus estimate (4.10) follows. ∎

##  Appendix C Covariant properties

Assume that $H$ is an Hamiltonian function which is invariant by translation
and gauge:

$H\circ\tau_{\zeta}=H,\qquad H\circ e^{{\rm i}t}=H\
,\quad\forall\varsigma\in{\mathbb{R}},\ \ \forall t\in{\mathbb{R}}\ .$ (C.1)

Its Hamiltonian vector field $X_{H}$ thus fulfill

$\tau_{\zeta}X_{H}(u)=X_{H}(\tau_{\zeta}u),\qquad e^{{\rm i}t}X_{H}(u)=e^{{\rm
i}t}X_{H}(u)\ ,\quad\forall\varsigma\in{\mathbb{R}},\ \forall
t\in{\mathbb{R}}\ .$ (C.2)

Consider now a quasi-periodic traveling wave $q(\varphi,x)$ fulfilling (1.8),
(1.9). Denote by

$A(\varphi)u:=dX_{H}\big{(}q(\varphi,\cdot)\big{)}u$

and

${\mathcal{N}}(\varphi,u):=X_{H}\big{(}q(\varphi,\cdot)+u\big{)}-X_{H}\big{(}q(\varphi,\cdot)\big{)}-dX_{H}\big{(}q(\varphi,\cdot)\big{)}u$

Following [2, 3, Section 3.4], now we prove the following lemma.

######  Lemma C.1.

For any
$(\varphi,\zeta,t)\in{\mathbb{T}}^{d}\times{\mathbb{R}}^{2}\times{\mathbb{R}}$
one has

$\displaystyle A(\varphi+{\bf K}\zeta)\circ\tau_{\zeta}=\tau_{\zeta}\circ
A(\varphi),\quad A(\varphi+t\vec{1})\circ e^{{\rm i}t}=e^{{\rm i}t}\circ
A(\varphi),$ (C.3) $\displaystyle{\mathcal{N}}(\varphi+{\bf
K}\zeta,\tau_{\zeta}u)=\tau_{\zeta}\circ{\mathcal{N}}(\varphi,u),\qquad{\mathcal{N}}(\varphi+t\vec{1},e^{{\rm
i}t}u)=e^{{\rm i}t}\circ{\mathcal{N}}(\varphi,u)\,.$ (C.4)

###### Proof.

We prove just the first identities in both line, the second one being similar.
We start with the first identity of (C.3). Differentiating the first of (C.2)
at $q(\varphi,x)$ in direction $w$ we get

$\tau_{\zeta}\left[dX_{H}(q(\varphi,\cdot))w\right]=dX_{H}(\tau_{\zeta}q(\varphi,\cdot))\tau_{\zeta}w\
.$ (C.5)

Then the covariance property (1.9) implies immediately

$A(\varphi+{\bf K}\zeta)\circ\tau_{\zeta}=\tau_{\zeta}\circ A(\varphi)$ (C.6)

To prove (C.4) just use again that, by (C.2), (C.5) and the covariance
properties (1.9) of the quasi-periodic traveling wave,

$\displaystyle\tau_{\zeta}\circ{\mathcal{N}}(\varphi,u)$
$\displaystyle=X_{H}(\tau_{\zeta}q(\varphi,\cdot)+\tau_{\zeta}u)-X_{H}(\tau_{\zeta}q(\varphi,\cdot))-dX_{H}(\tau_{\zeta}q(\varphi,\cdot))\tau_{\zeta}w$
$\displaystyle=X_{H}(q(\varphi+{\bf
K}\zeta,\cdot)+\tau_{\zeta}u)-X_{H}(q(\varphi+{\bf
K}\zeta,\cdot))-dX_{H}(q(\varphi+{\bf K}\zeta,\cdot))\tau_{\zeta}w$
$\displaystyle={\mathcal{N}}(\varphi+{\bf K}\zeta,\tau_{\zeta}u)\,.$

∎

## References

  * [1] M. Berti and L. Biasco.  Branching of Cantor manifolds of elliptic tori and applications to PDEs.  Comm. Math. Phys., 305(3):741–796, 2011.
  * [2] M. Berti, L. Franzoi and A. Maspero. _Traveling quasi-periodic water waves with constant vorticity_ , Archive for Rational Mechanics, 240: 99–202, 2021.
  * [3] M. Berti, L. Franzoi and A. Maspero. _Pure gravity traveling quasi-periodic water waves with constant vorticity_ , arXiv:2101.12006, 2021, to appear on Communications in Pure and Applied Mathematics.
  * [4] J. Bernier, E. Faou, and B. Grébert.  Rational normal forms and stability of small solutions to nonlinear Schrödinger equations.  Annals of PDE, 6(14), 2020.
  * [5] D. Bambusi and B. Grébert.  Birkhoff normal form for partial differential equations with tame modulus.  Duke Math. J., 135(3):507–567, 2006.
  * [6] J. Bernier and B. Grébert.  Birkhoff normal forms for hamiltonian pdes in their energy space.  Journal de l’Ecole Polytechnique - Mathematiques, 9:681–745, 2022\.
  * [7] D. Bambusi, B. Langella, and R. Montalto.  On the spectrum of the Schrödinger operator on $\mathbb{T}^{d}$: a normal form approach.  Comm. Partial Differential Equations, 45(4):303–320, 2020.
  * [8] D. Bambusi, B. Langella, and R. Montalto.  Spectral asymptotics of all the eigenvalues of Schrödinger operators on flat tori.  Nonlinear Anal., 216:Paper No. 112679, 37, 2022.
  * [9] L. Biasco, J. E. Massetti, and M. Procesi.  An Abstract Birkhoff Normal Form Theorem and Exponential Type Stability of the 1d NLS.  Comm. Math. Phys., 375(3):2089–2153, 2020.
  * [10] L. Biasco, J.E. Massetti, and M. Procesi.  Almost-periodic invariant tori for the NLS on the circle.  Ann. Inst. H. Poincaré Anal. Non Linéaire, 38(3):711–758, 2021.
  * [11] J. Bourgain.  Fourier transform restriction phenomena for certain lattice subsets and application to nonlinear evolution equations. i. Schrödinger equations.  Geom. Funct. Anal., 3(2):107–156, 1993.
  * [12] J. Bourgain.  On the growth in time of higher Sobolev norms of smooth solutions of Hamiltonian PDE.  Internat. Math. Res. Notices, 6:277–304, 1996.
  * [13] J. Bourgain.  On invariant tori of full dimension for 1D periodic NLS.  J. Funct. Anal., 229(1):62–94, 2005.
  * [14] J. Colliander, M. Keel, G. Staffilani, H. Takaoka, and T. Tao.  Transfer of energy to high frequencies in the cubic defocusing nonlinear Schrödinger equation.  Invent. Math., 181(1):39–113, 2010.
  * [15] H. L. Eliasson and S. B. Kuksin.  On reducibility of Schrödinger equations with quasiperiodic in time potentials.  Comm. Math. Phys., 286(1):125–135, 2009.
  * [16] L. H. Eliasson and S. B. Kuksin.  KAM for the nonlinear Schrödinger equation.  Ann. of Math. (2), 172(1):371–435, 2010.
  * [17] E. Faou and B. Grébert.  A Nekhoroshev-type theorem for the nonlinear Schrödinger equation on the torus.  Anal. PDE, 6(6):1243–1262, 2013.
  * [18] E. Faou, L. Gauckler, and C. Lubich.  Sobolev stability of plane wave solutions to the cubic nonlinear Schrödinger equation on a torus.  Comm. Partial Differential Equations, 38(7):1123–1140, 2013.
  * [19] J. Feldman, H. Knörrer, and E. Trubowitz.  The perturbatively stable spectrum of a periodic Schrödinger operator.  Invent. Math., 100(2):259–300, 1990.
  * [20] J. Feldman, H. Knörrer, and E. Trubowitz.  Perturbatively unstable eigenvalues of a periodic Schrödinger operator.  Comment. Math. Helv., 66(4):557–579, 1991.
  * [21] M. Guardia, Z. Hani, E. Haus, A. Maspero, and M.Procesi.  Strong nonlinear instability and growth of Sobolev norms near quasiperiodic finite gap tori for the 2d cubic NLS equation.  J. Eur. Math. Soc., published online first, 2022.
  * [22] M. Guardia, E. Haus, and M. Procesi.  Growth of Sobolev norms for the analytic NLS on $\mathbb{T}^{2}$.  Adv. Math., 301:615–692, 2016.
  * [23] A. Giorgilli.  Exponential stability of Hamiltonian systems.  In Dynamical systems. Part I, Pubbl. Cent. Ric. Mat. Ennio Giorgi, pages 87–198. Scuola Norm. Sup., Pisa, 2003.
  * [24] M. Guardia and V. Kaloshin.  Growth of Sobolev norms in the cubic defocusing nonlinear Schrödinger equation.  J. Eur. Math. Soc. (JEMS), 17(1):71–149, 2015.
  * [25] G. Gentile and M. Procesi.  Periodic solutions for a class of nonlinear partial differential equations in higher dimension.  Comm. Math. Phys., 289(3):863–906, 2009.
  * [26] J. Geng, X. Xu, and J. You.  An infinite dimensional KAM theorem and its application to the two dimensional cubic Schrödinger equation.  Adv. Math., 226(6):5361–5402, 2011.
  * [27] Z. Hani.  Long-time instability and unbounded Sobolev orbits for some periodic nonlinear Schrödinger equations.  Arch. Ration. Mech. Anal., 211(3):929–964, 2014.
  * [28] E. Haus and M. Procesi.  KAM for beating solutions of the quintic NLS.  Comm. Math. Phys., 354(3):1101–1132, 2017.
  * [29] Yu. E. Karpeshina.  Perturbation series for the Schrödinger operator with a periodic potential near planes of diffraction.  Comm. Anal. Geom., 4(3):339–413, 1996.
  * [30] Yulia E. Karpeshina.  Perturbation theory for the Schrödinger operator with a periodic potential, volume 1663 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin, 1997.
  * [31] S.B. Kuksin.  Growth and oscillations of solutions of nonlinear Schrödinger equation.  Comm. Math. Phys., 178(2):265–280, 1996.
  * [32] S. B. Kuksin.  On turbulence in nonlinear Schrödinger equations.  Geom. Funct. Anal., 7(4):783–822, 1997.
  * [33] S.B. Kuksin.  Oscillations in space-periodic nonlinear Schrödinger equations.  Geom. Funct. Anal., 7(2):338–363, 1997.
  * [34] A. Maspero and M. Procesi.  Long time stability of small finite gap solutions of the cubic nonlinear Schrödinger equation on $\mathbb{T}^{2}$.  J. Differential Equations, 265(7):3212–3309, 2018.
  * [35] N. N. Nekhorošev.  An exponential estimate of the time of stability of nearly integrable Hamiltonian systems.  Uspehi Mat. Nauk, 32(6(198)):5–66, 287, 1977.
  * [36] M. Procesi and C. Procesi.  A normal form for the Schrödinger equation with analytic non-linearities.  Comm. Math. Phys., 312(2):501–557, 2012.
  * [37] C. Procesi and M. Procesi.  A KAM algorithm for the resonant non-linear Schrödinger equation.  Adv. Math., 272:399–470, 2015.
  * [38] L. Parnovski and A. V. Sobolev.  Bethe-Sommerfeld conjecture for periodic operators with strong perturbations.  Invent. Math., 181(3):467–540, 2010.
  * [39] L. Parnovski and R. Shterenberg.  Complete asymptotic expansion of the integrated density of states of multidimensional almost-periodic Schrödinger operators.  Ann. of Math. (2), 176(2):1039–1096, 2012.
  * [40] M. Procesi and X. Xu.  Quasi-Töplitz Functions in KAM Theorem.  SIAM J. of Math. Anal., 45(4):2148 – 2181, 2013.
  * [41] O. Veliev.  Multidimensional periodic Schrödinger operator, volume 263 of Springer Tracts in Modern Physics.  Springer, Cham, 2015.  Perturbation theory and applications.
  * [42] W.-M. Wang.  Supercritical Nonlinear Schrödinger equations I: Quasi-Periodic Solutions.  arXiv:1007.0156, 2010.