Monatsh Math https://doi.org/10.1007/s00605-017-1148-5

On the sum of digits of special sequences in finite fields Cathy Swaenepoel1,2

Received: 7 August 2017 / Accepted: 16 December 2017 © Springer-Verlag GmbH Austria, part of Springer Nature 2017

Abstract In Fq , Dartyge and Sárközy introduced the notion of digits and studied some properties of the sum of digits function. We will provide sharp estimates for the number of elements of special sequences of Fq whose sum of digits is prescribed. Such special sequences of particular interest include the set of n-th powers for each n ≥ 1 and the set of elements of order d in Fq∗ for each divisor d of q − 1. We provide an optimal estimate for the number of squares whose sum of digits is prescribed. Our methods combine A. Weil bounds with character sums, Gaussian sums and exponential sums. Keywords Finite fields · Digits · Sum of digits · Character sums · Squares · Primitive elements Mathematics Subject Classification Primary 11A63; Secondary 11T23 · 11B83

Communicated by A. Constantin. Research supported by the Agence Nationale de la Recherche, Grant ANR-14-CE34-0009 MUDERA.

B

Cathy Swaenepoel [email protected]

1

Aix Marseille Université, CNRS, Centrale Marseille, I2M, Marseille, France

2

Institut de Mathématiques de Marseille UMR 7373 CNRS, 163 Avenue de Luminy, Case 907, 13288 Marseille Cedex 9, France

123

C. Swaenepoel

1 Introduction 1.1 Motivation Let g ≥ 2 be an integer. Every n ∈ N can be written uniquely in base g: n=

r 

cjg j

(1)

j=0

where the digits c j belong to {0, . . . , g − 1} and cr ≥ 1. The study of the connection between the arithmetic properties of n and the properties of its digits in a given basis produces a lot of interesting and difficult questions and many papers have been devoted to this topic. In particular, Gelfond [6] proved an asymptotic formula for the number of integers of an arithmetic progression whose sum of digits modulo m is fixed. More recently, Mauduit and Rivat [9,10] obtained an asymptotic formula for the number of prime numbers and also for the number of squares whose sum of digits modulo m is fixed. In another direction, Maynard [11] showed in a recent work that there are infinitely many prime numbers with one missing digit (e.g. no digit 9) in their decimal expansion. In [3], Dartyge and Sárközy initiated the study of the concept of digits in the context of finite fields. The algebraic structure of finite fields permits us to formulate and study new problems of interest which might be out of reach in the context of integers [8,13]. Let p be a prime number, let q = pr with r ≥ 2 and consider the finite field Fq . Let B = {e1 , . . . , er } be a basis of the vector space Fq over F p . Then every x ∈ Fq can be written uniquely in base B: r  cjej (2) x= j=1

with c1 , . . . , cr ∈ F p . As in [3], we will call c1 , . . . , cr the “digits” of x by analogy with the special case where the basis B consists of the first r powers of a generator (i.e. primitive element) g of Fq∗ since in this situation (2) becomes x=

r 

c j g j−1 ,

j=1

which reminds us of (1). Then Dartyge and Sárközy introduced the function sB defined over Fq by r  sB (x) = cj (3) j=1

which may be called the “sum of digits” function and they estimated the number of squares in Fq whose sum of digits is prescribed. Beyond squares, they also obtained results for sequences in Fq of the form (P(x))x∈Fq and (P(g))g∈G where P ∈ Fq [X ] and G is the set of generators of Fq∗ . Further problems on digits in finite fields have

123

On the sum of digits of special sequences in finite fields

been studied by Dartyge et al. [2], Dietmann et al. [4] and Gabdullin [5]. In particular, an estimate of the number of squares in Fq with restricted digits has been proved in [2] and then improved in [4,5]. In this paper, our goal is to provide sharp estimates for the number of elements of special sequences of Fq whose sum of digits is prescribed. Such special sequences of particular interest include the set of n-th powers for each n ≥ 1 and the set of elements of order d in Fq∗ for each divisor d of q − 1. We will provide an optimal estimate for the number of squares whose sum of digits is prescribed. 1.2 Statement of results Let p be a prime number, let q = pr with r ≥ 2, let B = {e1 , . . . , er } be a basis of Fq over F p and let sB be the sum of digits function defined by (3). 1.2.1 Sum of digits of polynomial values For P ∈ Fq [X ] and for s ∈ F p , we define D(P, s) = {x ∈ Fq : sB (P(x)) = s}. In [3], Dartyge and Sárközy obtained the following estimate for |D(P, s)|: Theorem A If P ∈ Fq [X ] is a polynomial of degree n ≥ 1 with (n, q) = 1 then, for any s ∈ F p ,     |D(P, s)| − q  ≤ (n − 1)√q.  p In the special case where n = 2, we will improve optimally this result by giving an exact formula for ||D(P, s)| − q/ p|: Theorem 1.1 If p ≥ 3 and if P(X ) = a2 X 2 + a1 X + a0 ∈ Fq [X ] with a2 = 0 then, writing ν P = sB (a0 − a12 (4a2 )−1 ), we have, for any s ∈ F p , ⎧√ q ⎪ ⎪ ⎪ √ ⎪ ⎪ ⎪ √p ⎪  ⎪   ⎨ q  |D(P, s)| − q  = p  p ⎪ ⎪ ⎪ 0 ⎪ ⎪ ⎪ p − 1√ ⎪ ⎪ q ⎩ p

if s = ν P and r is odd, if s = ν P and r is even, if s = ν P and r is odd, if s = ν P and r is even.

The fact that |D(P, s)| = q/ p for s = ν P and r ≡ 1 mod 2 does not seem to be obvious at first sight; this will follow from the proof. We will see in Remark 3.2 that if p = 2 then |D(P, s)| is equal to q/ p or 0 or q. Theorem 1.1 will be a consequence of a more precise result (see Theorem 3.1 in Sect. 3.1) which provides an exact formula for |D(P, s)|.

123

C. Swaenepoel

Our next purpose will be to improve Theorem A in the special case where P is a monomial. We will see in Sect. 3.2 that for any monomial a X n ∈ Fq [X ] and for any s ∈ F p , we have |D(a X n , s)| = |D(a X d , s)| where d = (n, q − 1). Thus, it suffices to study |D(P, s)| for monomials P whose degree divides q − 1. In this last case, the statement of Theorem A becomes: if d divides q − 1 and if a ∈ Fq∗ then, for any s ∈ Fp,     |D(a X d , s)| − q  ≤ (d − 1)√q. (4)  p We will obtain the following sharper estimate for |D(a X d , s)|: Theorem 1.2 If d divides q − 1 and if a ∈ Fq∗ then, for any s ∈ F∗p ,    √   p if d | δ, |D(a X d , s)| − q  ≤ (d − 1)√ q/√  (d − 1) q/ p otherwise, p where δ is the integer defined by δ = (q − 1)/( p − 1) and for s = 0,     |D(a X d , 0)| − q  ≤ p − 1 ((d, δ) − 1) √q.  p p √ For s = 0, Theorem 1.2 permits us to improve (4) by a factor at least 1/ p. In the special case where d = 2 (and so p ≥ 3), a comparison between Theorems 1.2 and 1.1 shows that the upper bounds obtained in Theorem 1.2 are the best possible (indeed, d = 2 divides δ if and only if r is even). Theorem 1.2 will be proved in Sect. 3.2 and it will appear as a consequence of a slightly more precise estimate for |D(a X d , s)| (see Theorem 3.7). We will see that Theorem 1.2 provides a sharp estimate for the number of n-th powers in Fq whose sum of digits is prescribed. For s ∈ F p , we define Fs = {x ∈ Fq : sB (x) = s} and Fs∗ = Fs \ {0}. For n ≥ 1, we denote by An the set of n-th powers in Fq : An = {x n : x ∈ Fq }. Since An = Ad where d = (n, q − 1) (see for instance Lemma 2D p. 13 of [15]), the study of |Fs ∩ An | is reduced to the study of |Fs ∩ Ad | where d is a divisor of q − 1. In Sect. 3.3, we will deduce from Theorem 1.2 the following estimate for |Fs ∩ Ad |: Corollary 1.3 If d divides q − 1 then, for any s ∈ F∗p , ⎧ √ q ⎪d −1   ⎪ if d | δ, ⎨   d √p |Fs ∩ Ad | − |Fs |  ≤  d −1 q d  ⎪ ⎪ √ otherwise, ⎩ d p

123

(5)

On the sum of digits of special sequences in finite fields

where δ is the integer defined by δ = (q − 1)/( p − 1) and for s = 0,  ∗

   |F0 ∩ Ad | − |F0 | + 1  ≤ p − 1 (d, δ) − 1 √q.   d p d

(6)

Note that the term |Fs | /d in (5) (resp. |F0∗ |/d + 1 in (6)) is the expected value for |Fs ∩ Ad | when s = 0 (resp. for |F0 ∩ Ad |): the proportion of d-th powers in Fq∗ is 1/d and thus if d-th powers were reasonably well distributed then we would expect this proportion to be preserved in Fs∗ . In the special case of squares, we will deduce from Theorem 1.1 the following optimal result: Corollary 1.4 If p ≥ 3 then, for any s ∈ F∗p , ⎧ √ q ⎪ √ if r is odd,   ⎪ ⎨   |F | 2 p |Fs ∩ A2 | − s  = √  2  ⎪ ⎪ q if r is even, ⎩ 2p and for s = 0, ⎧ 

 ⎨ 0 ∗ if r is odd,   |F0 ∩ A2 | − |F0 | + 1  = p − 1 √   q if r is even. ⎩ 2 2p Our next goal will be to generalize Theorem A in the case of several polynomials. For P1 , . . . , P ∈ Fq [X ] and for s1 , . . . , s ∈ F p , we define D(P1 , . . . , P , s1 , . . . , s ) = {x ∈ Fq : sB (P j (x)) = s j for all 1 ≤ j ≤ }. We will obtain in Sect. 3.4: Theorem 1.5 For any integer 1 ≤  ≤ r , if P1 , . . . , P ∈ Fq [X ] are polynomials of same degree n ≥ 1 with (n, q) = 1 and whose leading coefficients are F p -linearly independent then, for any s1 , . . . , s ∈ F p ,     |D(P1 , . . . , P , s1 , . . . , s )| − q  ≤ (n − 1)√q;   p  in particular, if (n − 1) p  <

√ q then D(P1 , . . . , P , s1 , . . . , s ) = ∅.

Note that, taking  = 1 in this theorem, we end up with Theorem A.

123

C. Swaenepoel

1.2.2 Sum of digits of rational values In order to extend Theorem A to rational functions, we define, for a rational function R = P/Q over Fq and for s ∈ F p :  D(R, s) = x ∈ Fq : Q(x) = 0 and sB (R(x)) = s . We will obtain in Sect. 4 the following estimate for |D(R, s)|: Theorem 1.6 If R = P/Q is a rational function over Fq satisfying ⎧ P = 0, ⎪ ⎪ ⎨ deg (P) − deg (Q) ≡ 0 mod p or deg (P) < deg (Q), Q is not divisible by the p-th power of a nonconstant ⎪ ⎪ ⎩ polynomial over Fq ,

(7)

then, for any s ∈ F p ,      |D(R, s)| − v  ≤ (max(deg P, deg Q) + α ∗ − 2)√q + β   p where – v = |{x ∈ Fq : Q(x) = 0}|, – α is the number of distinct roots of the polynomial Q in the algebraic closure Fq of Fq , – (α ∗ , β) = (α, 1) if deg P ≤ deg Q and (α ∗ , β) = (α + 1, 0) otherwise. Note that, taking Q = 1 in this theorem, we end up with Theorem A. 1.2.3 Sum of digits of polynomial values with generator arguments We denote by G the set of generators (i.e. primitive elements) of Fq∗ . The Euler’s totient function will be denoted by ϕ and for m ≥ 1, the number of distinct prime factors of m will be denoted by ω(m). For P ∈ Fq [X ] and for s ∈ F p , we define DG (P, s) = {g ∈ G : sB (P(g)) = s} = D(P, s) ∩ G. In [3], Dartyge and Sárközy obtained an estimate for |DG (P, s)| for any s ∈ F p and for any polynomial P ∈ Fq [X ] whose degree is coprime with q. Their proof leads to Theorem B If P ∈ Fq [X ] is a polynomial of degree n ≥ 1 with (n, q) = 1 then, for any s ∈ F p ,     |DG (P, s)| − ϕ(q − 1)  ≤ (n2ω(q−1) − 1)√q + ϕ(q − 1) .   p q −1

123

(8)

On the sum of digits of special sequences in finite fields

In this paper, we will improve (8) and obtain in Sect. 5.2: Theorem 1.7 If P ∈ Fq [X ] is a polynomial of degree n ≥ 1 with (n, q) = 1 then, for any s ∈ F p ,       |DG (P, s)| − ϕ(q − 1)  < ϕ(q − 1) (n2ω(q−1) − 1)√q + 1 .   p q −1

(9)

In the special case where P is a monomial, we will be able to further improve the upper bound in (9). We will show in Sect. 5.3 that for any monomial a X n ∈ Fq [X ] and for any s ∈ F p , we have |DG (a X n , s)| = |DG (a X d , s)| where d = (n, q − 1). Thus, it suffices to study |DG (P, s)| for monomials P whose degree divides q − 1. We will obtain the following sharper estimate for |DG (a X d , s)|: Theorem 1.8 If d divides q − 1 and if a ∈ Fq∗ then, for any s ∈ F∗p ,    

√ q−1   |DG (a X d , s)| − q ϕ(q − 1)  ≤ ϕ(q − 1) d 2ω d − 1 √ q ,  p q −1  q −1 p and for s = 0,    



δ   |DG (a X d , 0)| − q − 1 ϕ(q − 1)  ≤ ϕ(q −1) p−1 (d, δ)2ω (d,δ) − 1 √q  p q −1  q −1 p where δ is the integer defined by δ = (q − 1)/( p − 1). √ For s = 0, Theorem 1.8 permits us to improve (9) by a factor at least 1/ p. Theorem 1.8 will be proved in Sect. 5.3 and it will appear as a consequence of a slightly more precise estimate for |DG (a X d , s)| (see Theorem 5.6). We will see that, for any divisor d of q − 1, Theorem 1.8 provides an estimate for the number of elements of order d whose sum of digits is prescribed. For any divisor d of q − 1, we denote by Od the set of elements of order d in Fq∗ . In Sect. 5.4, we will deduce the following estimate for |Fs ∩ Od |: Corollary 1.9 If d divides q − 1 then, for any s ∈ F∗p ,  

√   |Fs ∩ Od | − |Fs | ϕ(d)  ≤ ϕ(d) q − 1 2ω(d) − 1 √ q ,  q − 1 q − 1 d p

(10)

and for s = 0,    

δ   |F0 ∩ Od | − |F ∗ | ϕ(d)  ≤ ϕ(d) p − 1 (d  , δ)2ω (d  ,δ) − 1 √q 0  q − 1 q − 1 p

(11)

where δ is the integer defined by δ = (q − 1)/( p − 1) and d  = (q − 1)/d.

123

C. Swaenepoel

Note that the term |Fs |ϕ(d)/(q − 1) in (10) (resp. |F0∗ |ϕ(d)/(q − 1) in (11)) is the expected value for |Fs ∩ Od | when s = 0 (resp. for |F0 ∩ Od |): the proportion of elements of order d in Fq∗ is ϕ(d)/(q − 1) and thus if elements of order d were reasonably well distributed then we would expect this proportion to be preserved in Fs∗ . In order to extend Theorem 1.7, we will finally provide an estimate for the number of generators g ∈ G such that sB (P(g)) is prescribed for several polynomials P i.e. an estimate for |DG (P1 , . . . , P , s1 , . . . , s )| where P1 , . . . , P ∈ Fq [X ], s1 , . . . , s ∈ F p and DG (P1 , . . . , P , s1 , . . . , s ) is the set defined by DG (P1 , . . . , P , s1 , . . . , s ) = {g ∈ G : sB (P j (g)) = s j for all 1 ≤ j ≤ }. We will obtain in Sect. 5.5: Theorem 1.10 For any integer 1 ≤  ≤ r , if P1 , . . . , P ∈ Fq [X ] are polynomials of same degree n ≥ 1 with (n, q) = 1 and whose leading coefficients are F p -linearly independent then, for any s1 , . . . , s ∈ F p ,       |DG (P1 , . . . , P , s1 , . . . , s )| − ϕ(q − 1)  < ϕ(q − 1) (n2ω(q−1) − 1)√q + 1 ;   q −1 p in particular, if

np  ≤

√ q/2ω(q−1)

(12)

then DG (P1 , . . . , P , s1 , . . . , s ) = ∅. Note that, taking  = 1 in this theorem, we end up with Theorem 1.7. Remark 1.11 One may wonder if condition (12) is not too restrictive. Heuristically, according to the normal order of the ω function (see [7], Theorem 431), for almost all values of q, it is expected that ω(q − 1) = O(log log q). Under this assumption, condition (12) would become np  ≤

√ q (log q) K

for some constant K > 0, so that in most cases condition (12) is not too restrictive as q → ∞. 1.3 Notations We use the notation e(t) = exp(2iπ t). The trivial additive character of Fq is denoted by ψ0 and the trivial multiplicative character of Fq is denoted by χ0 . The trivial multiplicative character of F p is simply denoted by 1. The field F p will be seen as a subfield of Fq so that every multiplicative character χ of Fq induces a multiplicative character of F p denoted by χ F∗p .

123

On the sum of digits of special sequences in finite fields

We introduce the following notations for Gaussian sums. If χ is a multiplicative character of F p , let τ (χ ) be the Gaussian sum  j

χ ( j). τ (χ ) = e p ∗ j∈F p

If ψ is an additive character of Fq and if χ is a multiplicative character of Fq , let G(χ , ψ) be the Gaussian sum G(χ , ψ) =



χ (x)ψ(x).

x∈Fq∗

For s ∈ F p and for a multiplicative character χ of Fq , we denote by S(χ , s) the sum  χ (x). (13) S(χ , s) = x∈Fq∗ sB (x)=s

The trace Tr of Fq over F p defined for x ∈ Fq by: Tr(x) = x + x p + · · · + x p

r −1

is an F p -linear form (see Theorem 2.23 of [8]) and permits defining the canonical additive character ψ1 of Fq by:

Tr(x) . ψ1 (x) = e p

(14)

We define 1 X =Y by  1 X =Y =

1 if X = Y, 0 otherwise.

2 Preparations The following Weil bound will play an important role in the proofs. Theorem 2.1 (Weil) Let P ∈ Fq [X ] be of degree n ≥ 1 with (n, q) = 1 and let ψ be a nontrivial additive character of Fq . Then,       √  ψ(P(x)) ≤ (n − 1) q.   x∈Fq Proof See [8], Theorem 5.38 p. 223.

 

123

C. Swaenepoel

Lemma 2.2 If ψ is an additive character of Fq and χ is a multiplicative character of Fq then ⎧ ⎨ q − 1 if χ = χ0 and ψ = ψ0 , G(χ , ψ) = −1 if χ = χ0 and ψ = ψ0 , ⎩ 0 if χ = χ0 and ψ = ψ0 , √ and |G(χ , ψ)| = q if χ = χ0 and ψ = ψ0 . √ In the special case where χ is a multiplicative character of F p , |τ (χ )| = p if χ is nontrivial and τ (χ ) = −1 if χ is trivial.  

Proof See Theorem 5.11 of [8].

The following lemma will be of basic interest in the proof of most of our results. Lemma 2.3 If χ is a nontrivial multiplicative character of Fq and if s ∈ F p then ⎧ G(χ , ψ1 ) ⎪ ⎪ χ (b)χ (s) ⎪ ⎪ τ (χ F∗p ) ⎪ ⎪ ⎪ ⎪ G(χ , ψ1 ) ⎨ −χ (b) S(χ , s) = p ⎪ ⎪ ⎪0 ⎪ ⎪ ⎪ ⎪ p−1 ⎪ ⎩ χ (b) G(χ , ψ1 ) p

if s = 0 and χ

F∗p

= 1,

if s = 0 and χ

F∗p

= 1,

if s = 0 and χ

F∗p

= 1,

if s = 0 and χ

F∗p

= 1,

(15)

where ψ1 is defined by (14) and b is the element of Fq∗ such that for any x ∈ Fq , sB (x) = Tr(bx). The existence of a unique b ∈ Fq∗ such that, for any x ∈ Fq , sB (x) = Tr(bx) follows from the fact that sB is a linear form and from Theorem 2.24 of [8]. Proof Let χ be a nontrivial multiplicative character of Fq . As in [1], we define the Eisentein sum E(χ ) by  E(χ ) = χ (x). x∈Fq∗ Tr(x)=1

If s ∈ F∗p then the sum S(χ , s) is related to E(χ ) by S(χ , s) =



χ (x) =

x∈Fq∗ Tr(s −1 bx)=1



χ (sb−1 y) = χ (b)χ (s)E(χ ).

y∈Fq∗ Tr(y)=1

Moreover, by Theorem 12.1.1 of [1], ⎧ G(χ , ψ1 ) ⎪ ⎪ if χ ⎨ τ (χ F∗p ) E(χ ) = −G(χ , ψ1 ) ⎪ ⎪ ⎩ if χ p

123

F∗p

= 1,

F∗p

= 1.

(16)

On the sum of digits of special sequences in finite fields

This proves (15) in the case where s ∈ F∗p (note that if χ F∗p = 1 then χ (s) = 1). For s = 0, we write   S(χ , 0) = χ (x) = χ (b) χ (y) x∈Fq∗ Tr(bx)=0

y∈Fq∗ Tr(y)=0

where by Lemma 12.0.2 of [1] and by (16) 

χ (y) =

y∈Fq∗ Tr(y)=0

⎧ ⎨0

if χ ( p − 1)G(χ , ψ1 ) ⎩ −( p − 1)E(χ ) = if χ p

This proves (15) in the case where s = 0.

F∗p

= 1,

F∗p

= 1.

 

We deduce from Lemmas 2.2 and 2.3 an exact formula for the absolute value of character sums over elements whose sum of digits is fixed. Corollary 2.4 If χ is a nontrivial multiplicative character of Fq and if s ∈ F p then ⎧√ q ⎪ ⎪ √ ⎪ ⎪ ⎪ p ⎪ ⎪ √q ⎪ ⎨ |S(χ , s)| = p ⎪ ⎪ 0 ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ p − 1 √q ⎩ p

if s = 0 and χ

F∗p

= 1,

if s = 0 and χ

F∗p

= 1,

if s = 0 and χ

F∗p

= 1,

if s = 0 and χ

F∗p

= 1.

Proof Since χ = χ0 and ψ1 = ψ0 , this result follows immediately from Lemmas 2.3 and 2.2.   From now on, g0 denotes a generator of the cyclic group Fq∗ . The following lemmas regarding the structure of multiplicative characters of Fq will also play an important role in the proofs. Lemma 2.5 The multiplicative characters of Fq are χ1 , . . . , χq−1 where, for every 1 ≤ j ≤ q − 1, χ j is defined by

χ j (g0k )

jk =e q −1

(17)

for any 1 ≤ k ≤ q − 1. Proof See Theorem 5.8 of [8].

 

Lemma 2.6 For any 1 ≤ j ≤ q − 1, the multiplicative character χ j of Fq defined by (17) satisfies: χ j F∗ = 1 if and only if p − 1 divides j. p

123

C. Swaenepoel q−1

Proof We consider g1 = g0p−1 ∈ F∗p . Since g0 is a generator of Fq∗ , g1 is a generator of F∗p . It follows that for 1 ≤ j ≤ q − 1, χ j F∗ = 1 if and only if χ j (g1 ) = 1. Moreover, p   j and thus χ j (g1 ) = 1 if and only if p − 1 divides j, which by (17), χ j (g1 ) = e p−1 completes the proof.  

3 Sum of digits of polynomial values 3.1 Proof of Theorem 1.1 In this section, we denote by η the quadratic character of Fq . Theorem 1.1 will be an immediate consequence of the following result which provides an exact formula for |D(P, s)|: Theorem 3.1 If p ≥ 3 and if P(X ) = a2 X 2 + a1 X + a0 ∈ Fq [X ] with a2 = 0 then, for any s ∈ F p , ⎧ √ q ⎪ r −1 ⎪ I η(a b(s − ν )) ⎪ √ 2 P p ⎪ ⎪ p ⎪ √ ⎪ ⎪ q ⎨ r q |D(P, s)| − = I p η(a2 b) p p ⎪ ⎪ ⎪0 ⎪ ⎪ ⎪ p − 1√ ⎪ r ⎪ q ⎩ −I p η(a2 b) p

if s = ν P and r is odd, if s = ν P and r is even, if s = ν P and r is odd, if s = ν P and r is even,

where – ν P = sB (a0 − a12 (4a2 )−1 ), – I p = 1 if p ≡ 1 mod 4 and I p = i if p ≡ 3 mod 4, – b is the element of Fq∗ such that for any x ∈ Fq , sB (x) = Tr(bx). Remark 3.2 If p = 2 then any element of Fq is a square (the mapping F defined by F(x) = x 2 for x ∈ F2r is the Frobenius automorphism of F2r over F2 ); in particular there exists α ∈ Fq such that ba2 = α 2 and thus, since Tr(y 2 ) = Tr(y) for any y ∈ F2r (see Theorem 2.23 of [8]): sB (a2 x 2 + a1 x) = Tr((αx)2 + ba1 x) = Tr((α + ba1 )x) and it follows that if α + ba1 = 0 then |D(a2 X 2 + a1 X + a0 , s)| = q/ p and if α + ba1 = 0 then |D(a2 X 2 + a1 X + a0 , s)| = q 1s−sB (a0 )=0 . Remark 3.3 In [8], the existence of b is proved by a counting argument. One may wonder how to construct b. For instance, we can consider a generator g of Fq∗ and the associated basis Bg = {1, g, . . . , gr −1 } of Fq . Then, writing sB (g k ) = Tr(bg k ) for all 0 ≤ k ≤ r − 1, we end up with a linear system of r equations and r variables r −1 b, b p , . . . , b p that can be solved by inverting a Vandermonde matrix.

123

On the sum of digits of special sequences in finite fields

To prove Theorem 3.1, we will need the two following lemmas. Lemma 3.4 For any p ≥ 3, the quadratic character η of Fq satisfies  η

F∗p

=

γ if r is odd, 1 if r is even,

where γ is the quadratic character of F p .  

Proof See for instance [16], Lemma 5.1. Lemma 3.5 For any p ≥ 3, the Gaussian sums G(η, ψ1 ) and τ (γ ) satisfy √ √ G(η, ψ1 ) = (−1)r −1 I pr q and τ (γ ) = I p p where I p = 1 if p ≡ 1 mod 4 and I p = i if p ≡ 3 mod 4.

 

Proof See Theorem 5.15 of [8].

We will first prove the following result which establishes Theorem 3.1 in the case where P(X ) = a X 2 with a ∈ Fq∗ . Proposition 3.6 If p ≥ 3 and if a ∈ Fq∗ then, for any s ∈ F p , ⎧ √ q ⎪ r −1 ⎪ ⎪ ⎪ I p η(abs) √ p ⎪ ⎪ √ ⎪ ⎪ q ⎨ r q I η(ab) 2 p |D(a X , s)| − = p p ⎪ ⎪ ⎪ 0 ⎪ ⎪ ⎪ r p − 1√ ⎪ ⎪ q ⎩ −I p η(ab) p

if s = 0 and r is odd, if s = 0 and r is even, if s = 0 and r is odd, if s = 0 and r is even,

where – I p = 1 if p ≡ 1 mod 4 and I p = i if p ≡ 3 mod 4, – b is the element of Fq∗ such that for any x ∈ Fq , sB (x) = Tr(bx). Proof Let a ∈ Fq∗ and s ∈ F p . The number of x ∈ Fq such that sB (ax 2 ) = s is given by |D(a X 2 , s)| =





1ax 2 =y = 1sB (0)=s

y∈Fq x∈Fq sB (y)=s

= 1s=0 +



 x∈Fq

1ax 2 =0 +



2

y∈Fq∗ sB (y)=s a −1 y is a square

(1 + η(a −1 y))

y∈Fq∗ sB (y)=s

123

C. Swaenepoel

thus, since the number of y ∈ Fq such that sB (y) = s is q/ p, |D(a X 2 , s)| =

q + η(a)S(η, s) p

where S(η, s) is defined by (13). By Lemmas 2.3 and 3.4, S(η, s) is given by ⎧ G(η, ψ1 ) ⎪ ⎪ η(b)η(s) ⎪ ⎪ τ (γ ) ⎪ ⎪ ⎪ G(η, ψ1 ) ⎨ −η(b) S(η, s) = p ⎪ ⎪ 0 ⎪ ⎪ ⎪ ⎪ p−1 ⎪ ⎩ η(b) G(η, ψ1 ) p

if s = 0 and r is odd, if s = 0 and r is even, if s = 0 and r is odd,

(18)

if s = 0 and r is even,

where b is defined as in Lemma 2.3. To complete the proof of Proposition 3.6, it suffices to insert the expressions of G(η, ψ1 ) and τ (γ ) given by Lemma 3.5 into (18).   Theorem 3.1 is then a straightforward consequence of Proposition 3.6. Let P(X ) = a2 X 2 +a1 X +a0 ∈ Fq [X ] with a2 = 0 and let s ∈ F p . Since P(X ) = a2 (X −α)2 +β where α = −a1 (2a2 )−1 and β = a0 − a12 (4a2 )−1 , denoting ν P = sB (β), we have |D(P, s)| = |{x ∈ Fq : sB (a2 (x − α)2 ) = s − ν P }| = |D(a2 X 2 , s − ν P )|. Applying Proposition 3.6 to |D(a2 X 2 , s − ν P )|, we obtain the expected exact formula for |D(P, s)|, which completes the proof of Theorem 3.1. 3.2 Sum of digits of monomials and proof of Theorem 1.2 We first show that the study of |D(P, s)| where P is a monomial may be reduced to the case where the degree of P divides q − 1. Let n ≥ 1 and denote d = (n, q − 1). The set of n-th powers in Fq∗ equals the set of d-th powers in Fq∗ and for any n-th power y ∈ Fq∗ , there are exactly d elements x ∈ Fq∗ such that y = x n (see Lemma 2D p. 13 of [15]). It follows that for any a ∈ Fq∗ and for any s ∈ F p , |D(a X n , s) \ {0}| = d · |An ∩ {y ∈ Fq∗ : sB (ay) = s}| = d · |Ad ∩ {y ∈ Fq∗ : sB (ay) = s}| = |D(a X d , s) \ {0}|

(19)

where An (resp. Ad ) is the set of n-th (resp. d-th) powers in Fq and thus |D(a X n , s)| = |D(a X d , s)|. We will now obtain the following result which provides a sharp estimate for |D(a X d , s)| as soon as d divides q − 1.

123

On the sum of digits of special sequences in finite fields

Theorem 3.7 If d divides q − 1 and if a ∈ Fq∗ then, for any s ∈ F∗p ,  

√   q 1 |D(a X d , s)| − q  ≤ d − (d, δ) 1 − √1 − √ √   p p p p where δ is the integer defined by δ = (q − 1)/( p − 1) and for s = 0,     |D(a X d , 0)| − q  ≤ p − 1 ((d, δ) − 1) √q.  p p Theorem 1.2 is an immediate consequence of Theorem 3.7. To prove Theorem 3.7, we will need the following lemma. Lemma 3.8 For any integer 1 ≤ j ≤ q − 1, the multiplicative character χ j of Fq defined by (17) satisfies for any n ≥ 1: 

 χ nj (x)

=

x∈Fq∗

q − 1 if q − 1 | n j, 0 otherwise.

Proof It suffices to write 

χ nj (x)

=

x∈Fq∗



χ nj

  g0k =

1≤k≤q−1



 1≤k≤q−1

n jk e q −1



which is equal to q − 1 if q − 1 | n j and 0 otherwise.

 

We are now able to prove Theorem 3.7. Let d be a divisor of q − 1, let a ∈ Fq∗ and s ∈ F p . Since D(a X d , s) = {x ∈ Fq : sB (ax d ) = s}, we have |D(a X d , s)| =





1ax d =y = 1sB (0)=s

y∈Fq x∈Fq sB (y)=s



1ax d =0 +

x∈Fq





y∈Fq∗ x∈Fq∗ sB (y)=s

1ax d =y .

 Since x∈Fq 1ax d =0 = 1, using the orthogonality relations for multiplicative characters of Fq to detect the equality ax d = y, we obtain: ⎞ ⎛ 

  1 d d ⎠ ⎝ |D(a X , s)| = 1s=0 + χ (ax ) χ (y) q −1 χ ∗ ∗ x∈Fq

= 1s=0 +

1 q −1

 χ

⎛ χ (a) ⎝

y∈Fq sB (y)=s



⎞

χ d (x)⎠ S(χ , s)

x∈Fq∗

123

C. Swaenepoel

where S(χ , s) is defined by (13). In the right-hand side sum, the main term is provided by χ = χ0 and since the number of y ∈ Fq such that sB (y) = s is q/ p, ⎛ ⎞   q 1 χ (a) ⎝ χ d (x)⎠ S(χ , s). |D(a X d , s)| = + p q −1 ∗ χ =χ0

x∈Fq

The nontrivial multiplicative characters of Fq are χ1 , . . . , χq−2 defined by (17) and it follows that 1 q |D(a X d , s)| − = p q −1

⎛



χ j (a) ⎝



⎞ χ dj (x)⎠ S(χ j , s)

x∈Fq∗

1≤ j
and by Lemma 3.8 |D(a X d , s)| −

q = p



χ j (a)S(χ j , s).

1≤ j
Moreover, by Lemma 2.6, for 1 ≤ j ≤ q − 1, χ j j. Thus, by Corollary 2.4, if s = 0 then  √    |D(a X d , s)| − q  ≤ √ q  p p

and for s = 0,

F∗p



= 1 if and only if p − 1 divides

1+

1≤ j≤q−1 q−1 | d j p−1  j

    |D(a X d , 0)| − q  ≤ p − 1 √q  p p

√ q p



1



1.

1≤ j
Since δ = (q − 1)/( p − 1), writing  1≤ j≤q−1 q−1 | d j p−1 | j

and

 1≤ j≤q−1 q−1 | d j p−1  j

123



1=

1=

1≤u≤δ q−1 | du( p−1)

1=

 1≤ j≤q−1 q−1 | d j



1=

1≤u≤δ δ | du

1−

 1≤ j≤q−1 q−1 | d j p−1 | j

(20)

1≤ j


1 = (d, δ)

1≤u≤δ δ (d,δ) | u

1 = d − (d, δ),

(21)

On the sum of digits of special sequences in finite fields

(20) becomes, for s = 0,   √ √   |D(a X d , s)| − q  ≤ √ q (d − (d, δ)) + q ((d, δ) − 1)  p p p and (21) becomes     |D(a X d , 0)| − q  ≤ p − 1 √q((d, δ) − 1)  p p which completes the proof of Theorem 3.7. 3.3 Proof of Corollaries 1.3 and 1.4 To prove Corollary 1.3 (resp. Corollary 1.4), it suffices to remark that if d divides q −1 then, by (19), we have: – for s ∈ F∗p , |Fs | = q/ p and |D(X d , s)| = d · |Fs ∩ Ad |, – for s = 0, |F0∗ | = q/ p − 1 and |D(X d , 0)| = d(|F0 ∩ Ad | − 1) + 1 and to apply Theorem 1.2 (resp. Theorem 1.1). 3.4 Proof of Theorem 1.5 For each 1 ≤ j ≤ , the condition sB (P j (x)) = s j can be handled with an exponential sum by using the classical equality:

 p−1 ja 1 1 if a ≡ 0 mod p, = e 0 otherwise. p p j=0

This permits us to detect the elements of D(P1 , . . . , P , s1 , . . . , s ) by a product of exponential sums as follows: |D(P1 , . . . , P , s1 , . . . , s )| ⎛ ⎞

p−1    h j (sB (P j (x)) − s j ) ⎝1 ⎠ = e p p j=1 h =0 x∈Fq j ⎛ ⎞ ⎞ ⎛       −1 1 e⎝ h jsj⎠ ψB ⎝ h j P j (x)⎠ =  p p 0≤h 1 ,...,h  ≤ p−1

j=1

x∈Fq

j=1

where ψB is the additive character of Fq defined by ψB (y) = e (sB (y)/ p) for any y ∈ Fq . The contribution of (h 1 , . . . , h  ) = (0, . . . , 0) is q/ p  . Since all the P j have degree n and their leading coefficients are F p -linearly independent, it is enough that

123

C. Swaenepoel

one of the h j is not 0 to ensure that the polynomial it follows from Theorem 2.1 that:



j=1 h j P j (x)

has degree n and

     |D(P1 , . . . , P , s1 , . . . , s )| − q  ≤ p − 1 (n − 1)√q ≤ (n − 1)√q.   p p √ In particular, if (n − 1) p  < q then |D(P1 , . . . , P , s1 , . . . , s )| > 0, which completes the proof of Theorem 1.5.

4 Sum of digits of rational values To prove Theorem 1.6, we will need the following result. Theorem 4.1 Let ψ be a nontrivial additive character of Fq and let R = P/Q be a rational function over Fq . Let α be the number of distinct roots of the polynomial Q in the algebraic closure Fq of Fq . If R satisfies R is not of the form A p − A where A is a rational function over Fq

(22)

then      √  ψ (R(x))  ≤ (max(deg P, deg Q) + α ∗ − 2) q + β  x∈Fq Q(x)=0

where (α ∗ , β) = (α, 1) if deg P ≤ deg Q and (α ∗ , β) = (α + 1, 0) otherwise.  

Proof See [12], Theorem 2.

Moreover, by Lemma 2 of [14], if a rational function R = P/Q over Fq satisfies condition (7) then it also satisfies (22). Then, to prove Theorem 1.6, it suffices to follow the same arguments as in the proof of Theorem A and to use Theorem 4.1 instead of Weil’s Theorem 2.1.

5 Sum of digits of polynomial values with generator arguments 5.1 Preliminary results Lemma 5.1 For any integers j ≥ 1 and m ≥ 1, the Ramanujan sum cm ( j) defined by cm ( j) =

 1≤k≤m (k,m)=1

123

e

jk m

,

On the sum of digits of special sequences in finite fields

satisfies

μ ϕ

cm ( j) =

m ϕ(m) ( j, m)

where μ is the Möbius function.  

Proof See [7], Theorem 272. Lemma 5.2 For any integers m ≥ 1 and n ≥ 1, we have m  μ2 =1

Proof We write

ϕ

m  μ2 =1

ϕ

m (n, m)

m (n, m)

= (n, m) 2

=

ω



 μ2 (d) ϕ

m (n,m)



.



d |m

1

(23)

1≤≤m (n,m)= md

and we define D = (n, m), n  = n/D and m  = m/D. If d | m  then (n, m) = md if   and only if (n  , m  ) = md i.e. (, m  ) = md (since (n  , m  ) = 1). If d  m  then the contribution of d in (23) is 0. Hence, m  μ2 =1

ϕ

m (n, m)

=

 μ2 (d) ϕ 

d |m

=D





1=

  μ2 (d) 1 ϕ 

d |m

1≤≤m  (,m  )= md

1≤u≤d D (u,d)=1



μ2 (d) = D 2ω(m )

d | m

where the last equality holds by Theorem 264 of [7]. This completes the proof of Lemma 5.2.   Lemma 5.3 For any integer 1 ≤ j ≤ q − 1, the multiplicative character χ j of Fq defined by (17) satisfies for any n ≥ 1:

 q −1 μ ϕ(q − 1). χ nj (g) = ϕ (n j, q − 1) g∈G

Proof The set G can be described in terms of g0 : G = {g0k : 1 ≤ k ≤ q − 1 and (k, q − 1) = 1} and it follows  g∈G

χ nj (g) =

 1≤k≤q−1 (k,q−1)=1

  χ nj g0k =

 1≤k≤q−1 (k,q−1)=1

e

n jk . q −1

123

C. Swaenepoel

The last sum is the Ramanujan sum cq−1 (n j) and thus, by Lemma 5.1, 

χ nj (g)

g∈G

μ = ϕ



q −1 ϕ(q − 1). (n j, q − 1)  

5.2 Proof of Theorem 1.7 Theorem 1.7 improves Theorem 1.3 in [3]. This improvement can be obtained by using the following result [16, Proposition 6.1]: Proposition 5.4 If P ∈ Fq [X ] is a polynomial of degree n ≥ 1 with (n, q) = 1 and if ψ is a nontrivial additive character of Fq then we have the upper bound       ϕ(q − 1)  ω(q−1)  √ ≤  (n2 ψ(P(g)) − 1) q + 1 .   q −1  g∈G To prove Theorem 1.7, it suffices to follow the same arguments as in the proof of Theorem 1.3 in [3] and to use Proposition 5.4 instead of Lemma 4.1 of [3]. 5.3 Sum of digits of monomials with generator arguments and proof of Theorem 1.8 We first show that the study of |DG (P, s)| where P is a monomial may be reduced to the case where the degree of P divides q − 1. We will need the following lemma. Lemma 5.5 If m ≥ 2 is an integer and if d ≥ 2 divides m then the morphism f : (Z/mZ)∗ → (Z/dZ)∗ k mod m → k mod d is surjective and the preimage of each x ∈ (Z/dZ)∗ has exactly

ϕ(m) ϕ(d)

elements.

Proof If 1 ≤ k  ≤ d − 1 satisfies (k  , d) = 1, by Dirichlet’s theorem on arithmetic progressions (see for instance Theorem 15 in [7]), there are infinitely many prime numbers p such that p ≡ k  mod d, thus, there exists a prime p such that p  m (m has finitely many prime factors) and p ≡ k  mod d. This shows that f is surjective. Therefore, the quotient group (Z/mZ)∗ / ker f is isomorphic to (Z/dZ)∗ and it follows that |ker f | = ϕ(m)/ϕ(d). Moreover, the preimage of each x ∈ (Z/dZ)∗ by f is x0 ker f , where x0 is an element of (Z/mZ)∗ satisfying f (x0 ) = x. It follows that the preimage of each x ∈ (Z/dZ)∗ by f has exactly ϕ(m)/ϕ(d) elements, which completes the proof of Lemma 5.5.  

123

On the sum of digits of special sequences in finite fields

Let n ≥ 1 and denote d = (n, q − 1) and d  = (q − 1)/d. For any generator g, the order of g n is d  . Moreover, we will see that Lemma 5.5 permits us to show that, for any x ∈ Fq∗ of order d  , there are exactly ϕ(q − 1)/ϕ(d  ) generators g such that x = g n . Indeed, there exists 1 ≤ k0 ≤ d  such that (k0 , d  ) = 1 and x = g0k0 d (where g0 is a fixed generator of Fq∗ ) and since G = {g0k : 1 ≤ k ≤ q − 1, (k, q − 1) = 1}, the number of generators g such that g n = x is the number of integers 1 ≤ k ≤ q − 1 such that (k, q − 1) = 1 and kn ≡ k0 d mod (q − 1) i.e. k dn ≡ k0 mod d  which may be written as n  mod d  k ≡ k0 i d  d

 where i d  dn is the inverse of dn modulo d  . By Lemma 5.5, there are exactly ϕ(q − 1)/ϕ(d  ) such integers k. It follows that |DG (a X n , s)| =

ϕ(q − 1) |Od  ∩ {y ∈ Fq : sB (ay) = s}| ϕ(d  )

(24)

and in particular, |DG (a X n , s)| = |DG (a X d , s)|. We will now obtain the following result which provides a sharp estimate for |DG (a X d , s)| as soon as d divides q − 1. Theorem 5.6 If d divides q − 1 and if a ∈ Fq∗ then, for any s ∈ F∗p ,     |DG (a X d , s)| − q ϕ(q − 1)   p q −1     

√ q ϕ(q − 1) 1 1 ω q−1 ω δ ≤ d 2 d − (d, δ) 2 (d,δ) 1 − √ −√ √ q −1 p p p where δ is the integer defined by δ = (q − 1)/( p − 1) and for s = 0,    



δ   |DG (a X d , 0)| − q − 1 ϕ(q − 1)  ≤ ϕ(q −1) p−1 (d, δ) 2ω (d,δ) − 1 √q.  p q −1  q −1 p Theorem 1.8 is an immediate consequence of Theorem 5.6. Proof Let d be a divisor of q − 1, let a ∈ Fq∗ and s ∈ F p . Since DG (a X d , s) = {g ∈ G : sB (ag d ) = s}, by the same arguments as in the proof of Theorem 3.7, |DG (a X d , s)| =

  y∈Fq∗ sB (y)=s

g∈G

1agd =y

⎛ ⎞  1  = χ (a) ⎝ χ d (g)⎠ S(χ , s) q −1 χ g∈G

123

C. Swaenepoel

where S(χ , s) is defined by (13). The main term is provided by χ = χ0 :

|DG (a X d , s)| = Ms +

1 q −1

⎛





χ (a) ⎝

χ =χ0

⎞ χ d (g)⎠ S(χ , s)

g∈G

where ⎧ q ϕ(q − 1) ⎪ ⎪ if s = 0, ⎨ |G| p q − 1 Ms = |{y ∈ Fq∗ : sB (y) = s}| = q ϕ(q − 1) ⎪ q −1 ⎪ −1 if s = 0. ⎩ p q −1

(25)

The nontrivial multiplicative characters of Fq are χ1 , . . . , χq−2 defined by (17). It follows that ⎛ ⎞ q−2   1 |DG (a X d , s)| − Ms = χ j (a) ⎝ χ dj (g)⎠ S(χ j , s) q −1 g∈G

j=1

and by Lemma 5.3 ϕ(q − 1)  μ |DG (a X , s)| − Ms = χ j (a) q −1 ϕ q−2



d

j=1

Moreover, by Lemma 2.6, for 1 ≤ j ≤ q − 1, χ j j. Thus, by Corollary 2.4, if s = 0 then   ϕ(q − 1) √q   d |DG (a X , s)| − Ms  ≤ √ q −1 p +

F∗p

S(χ j , s).

= 1 if and only if p − 1 divides

 1≤ j≤q−1 p−1  j

√ ϕ(q − 1) q q −1 p

q −1 (d j, q − 1)

μ2 ϕ

 1≤ j


q −1 (d j, q − 1)

μ2 ϕ





q −1 (d j, q − 1)

(26)

and for s = 0,   ϕ(q − 1) ( p − 1)√q   |DG (a X d , 0)| − M0  ≤ q −1 p

123

 1≤ j
μ2 ϕ



q −1 . (27) (d j, q − 1)

On the sum of digits of special sequences in finite fields

Lemma 5.2 permits us to compute each sum over j in (26) and (27):  1≤ j
μ2 ϕ



q −1 (d j, q − 1)

=

   μ2 δ

ω δ = (d, δ) 2 (d,δ) − 1 ϕ (d, δ)

(28)

1≤<δ

where δ = (q − 1)/( p − 1) and thus, also by Lemma 5.2,  1≤ j≤q−1 p−1  j

=

μ2 ϕ





μ2 ϕ

1≤ j≤q−1

=d2

ω



q −1 (d j, q − 1)

q−1 d





q −1 (d j, q − 1)



− (d, δ) 2

ω





δ (d,δ)



−

1≤ j≤q−1 p−1 | j



μ2 ϕ



.

q −1 (d j, q − 1)



(29)

To complete the proof of Theorem 5.6, it suffices to insert (28), (29) and (25) into (26) for s = 0 and to insert (28) and (25) into (27) for s = 0.   5.4 Proof of Corollary 1.9 If d divides q − 1, it follows from (24) that: 

|DG (X d , s)| =

ϕ(q − 1) |Fs ∩ Od | ϕ(d)

(30)

where d  = (q − 1)/d. Then, to prove Corollary 1.9, it suffices to insert (30) into Theorem 1.8. 5.5 Proof of Theorem 1.10 By the same argument as in the proof of Theorem 1.5, |DG (P1 , . . . , P , s1 , . . . , s )| is given by: ⎞ ⎛    −1 1 e⎝ h jsj⎠ |DG (P1 , . . . , P , s1 , . . . , s )| =  p p 0≤h 1 ,...,h  ≤ p−1 j=1 ⎞ ⎛    × ψB ⎝ h j P j (g)⎠ . g∈G

j=1

The contribution of (h 1 , . . . , h  ) = (0, . . . , 0) is ϕ(q − 1)/ p  . Again, by the same argument as in the proof of Theorem 1.5, if at least one of the h j is not 0 then the  polynomial j=1 h j P j (x) has degree n and by Proposition 5.4,

123

C. Swaenepoel

      |DG (P1 , . . . , P , s1 , . . . , s )| − ϕ(q − 1)  < ϕ(q − 1) (n2ω(q−1) − 1)√q + 1  q −1 p 

1 ϕ(q − 1) √ n2ω(q−1) q −  , < q −1 p √ and thus, if np  ≤ q/2ω(q−1) then |DG (P1 , . . . , P , s1 , . . . , s )| > 0, which completes the proof of Theorem 1.10.

References 1. Berndt, B.C., Evans, R.J., Williams, K.S.: Gauss and Jacobi Sums. Canadian Mathematical Society Series of Monographs and Advanced Texts. Wiley, New York (1998) 2. Dartyge, C., Mauduit, C., Sárközy, A.: Polynomial values and generators with missing digits in finite fields. Funct. Approx. Comment. Math. 52, 65–74 (2015) 3. Dartyge, C., Sárközy, A.: The sum of digits function in finite fields. Proc. Am. Math. Soc. 141, 4119– 4124 (2013) 4. Dietmann, R., Elsholtz, C., Shparlinski, I.E.: Prescribing the binary digits of squarefree numbers and quadratic residues. Trans. Am. Math. Soc. 369, 8369–8388 (2017) 5. Gabdullin, M.R.: On the squares in the set of elements of a finite field with constraints on the coefficients of its basis expansion. Mat. Zametki 100, 807–824 (2016) 6. Gelfond, A.O.: Sur les nombres qui ont des propriétés additives et multiplicatives données. Acta Arith. 13, 259–265 (1967/1968) 7. Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers, 5th edn. Oxford Science Publications, Oxford (1979) 8. Lidl, R., Niederreiter, H.: Finite Fields, Volume 20 of Encyclopedia of Mathematics and Its Applications, 2nd edn. Cambridge University Press, Cambridge (1997). With a foreword by P. M. Cohn 9. Mauduit, C., Rivat, J.: La somme des chiffres des carrés. Acta Math. 203, 107–148 (2009) 10. Mauduit, C., Rivat, J.: Sur un problème de Gelfond: la somme des chiffres des nombres premiers. Ann. Math. (2) 171, 1591–1646 (2010) 11. Maynard, J.: Primes with restricted digits (2016). arXiv:1604.01041v1 12. Moreno, C., Moreno, O.: Exponential sums and Goppa codes: I. Proc. Am. Math. Soc. 111, 523–531 (1991) 13. Mullen, G.L., Panario, D.: Handbook of Finite Fields, 1st edn. Chapman & Hall, London (2013) 14. Niederreiter, H., Winterhof, A.: Incomplete exponential sums over finite fields and their applications to new inversive pseudorandom number generators. Acta Arith. 93, 387–399 (2000) 15. Schmidt, W.: Equations Over Finite Fields. An Elementary Approach, Volume 536 of Lecture Notes in Mathematics. Springer, Berlin (1976) 16. Swaenepoel, C.: Prescribing digits in finite fields. J. Number Theory (2017). https://doi.org/10.1016/ j.jnt.2017.11.012

123