c Pleiades Publishing, Ltd., 2017. ISSN 2070-0466, p-Adic Numbers, Ultrametric Analysis and Applications, 2017, Vol. 9, No. 4, pp. 257–266. 

RESEARCH ARTICLES

p-Adic Valuation of Exponential Sums Associated to Trinomials and Some Consequences∗ ´ Figueroa*** Francis N. Castro** and Raul Department of Mathematics, University of Puerto Rico, San Juan, PR 00936 Received July 19, 2017

Abstract—In this paper, we compute the p-adic valuation of exponential sums associated to trinomials F (X) = aX d1 + bX d2 + cX d3 over Fp . As a byproduct of our results, we obtain restrictions for permutation polynomials of type aX d1 + bX d2 + cX d3 over Fp . DOI: 10.1134/S2070046617040021 Key words: p-adic valuation of exponential sums, permutation polynomials.

1. INTRODUCTION Exponential sums over finite fields have been useful in mathematics since many problems can be formulated in terms of exponential sums. For example, the number of solutions of an equation over a finite field can be expressed in terms of an exponential sum. In particular, two very well known exponential sums are the Gauss sums and the Kloosterman sums. The general goal is to understand better the behavior of exponential sums since this will improve understanding of many problems in mathematics. In this work we focus on the p-adic valuation of exponential sums over Fp . In general the problem of computing the p-adic valuation of exponential sums is a hard one. There are good estimates for the p-adic valuation of exponential sums associated to polynomials in many variables (see for example [1–3, 5, 6, 13, 14, 18]). Unfortunately, these estimates do not provide the exact pvaluation of the exponential sum. In this paper, we study the exact p-adic valuation of exponential sums associated to trinomials of type aX d1 + bX d2 + cX d3 over Fp when p is an odd prime and d3 ∈ {1, 2}. In [7–9, 17], the authors computed the exact p-adic valuation for exponential sums associated to binomials over Fp . The natural next step is to compute the exact p-adic valuation for exponential sums associated to trinomials over Fp as we do in this note. As a consequence of our results, we prove that the γ s1 p-adic valuation for exponential sums associated to aX d1 + bX d2 + cX d3 over Fp is  p−1 d1  +  d2  + d3 , s1 where d3 ∈ {1, 2}, p − 1 =  p−1 d1 d1 + s1 and s1 =  d2 d2 + γ under some natural conditions. This result provides restrictions in determining when aX d1 + bX d2 + cX d3 is a permutation of Fp . In particular, we obtain that aX d1 + bX d2 + cX does not permute Fp whenever d12 < p − 1 and d22 + d2 ≤ d1 . We state a conjecture about the number permutation trinomials of type aX d1 + bX d2 + cX of Fp .

Using the language of [3], the Hasse invariant controls when the p-valuation of the exponential sum is equal to the bound given by the minimal solutions of a system modular equations. Theorem 6.6 in [3] provided a formula for the Hasse invariant as a sum of certain A-hypergeometric systems. In this paper we prove that the Hasse invariant of the exponential sums associated to aX d1 + bX d2 + cX d3 is a monomial and gives its p-valuation. The techniques used in this paper can be summarized as follows: ∗

The text was submitted by the authors in English. E-mail: [email protected] *** E-mail: [email protected] **

257

258

CASTRO, FIGUEROA

1) Solve the following optimization problem μp (d1 , d2 , d3 ) =

min

i+j+k

(i,j,k)=(0,0,0)

satisfying d1 i + d2 j + d3 k ≡ 0 mod p − 1. 2) Determine when μp (d1 , d2 , d3 ) comes from a unique solution of d1 i + d2 j + d3 k ≡ 0 mod p − 1. 3) Combine p-adics tools, Stickbelger’s theorem with parts (1) and (2) to obtain the exact pvaluation of the exponential sum. 4) Combine the criterion of exponential sums for permutation polynomials and part (3) to obtain that the trinomial is not a permutation polynomial.

2. PRELIMINARIES In this section we state all the results that we are going to use in the following section. Throughout  di is a non-constant polynomial of degree the paper, we assume that a polynomial F (X) = N i=1 ai X less than p − 1 and p is an odd prime. We denote by VF the image of F , i.e., VF = {F (x) | x ∈ Fp } and |VF | its cardinality. ¨ representatives of Fp Let Qp be the p-adic field with ring of integers Zp . Let T denote the Teichmuller in Qp . Denote by ξ a primitive p-th root of unity in Qp . Define θ = 1 − ξ and denote by νθ the valuation over θ. Note that νθ (p) = p − 1 and νp (x) =

νθ (x) p−1 . To more details of the previous discussion see [10, 11].

Let φ : Fp → Q(ξ) be a nontrivial additive character. The exponential sum associated to F (X) = N di i=1 ai X is defined as follows:  φ(F (x)). Sp (F ) = x∈Fp

The next theorem gives a bound for the θ-adic valuation of an exponential sum with respect to θ. Theorem 2.1 ([14]). Let F (X) = exponential sum

N

i=1 ai X

di ,

Sp (F ) =

ai = 0 for every i ∈ {1, . . . , N }. If Sp (F ) is the 

(2.1)

φ(F (x)),

x∈Fp

then νθ (Sp (F )) ≥ μp (d1 , . . . , dN ), where μp (d1 , . . . , dN ) =

min (j1 ,...,jN )

 N 

 ji | 0 ≤ ji < p

 + (p − 1) ,

i=1

for (j1 , . . . , jN ) a solution to the modular equation d1 j1 + d2 j2 + . . . + dN jN ≡ 0 mod p − 1 and

(2.2)

⎧ ⎨ 1 if (j , . . . , j ) = (0, . . . , 0) 1 N = ⎩0 otherwise. p-ADIC NUMBERS, ULTRAMETRIC ANALYSIS AND APPLICATIONS

Vol. 9 No. 4 2017

p-ADIC VALUATION

259

Following the notation in [14], we expand the exponential sum Sp (F ):

 N

 N

p−1 p−1    j Sp (F ) = ··· c(ji ) td1 i1 +···+dN jN a i i , j1 =0

jN =0

i=1

(2.3)

i=1

t∈T

¨ representatives of the coefficients ai of F , and c(ji ) is defined in Lemma where ai ’s are the Teichmuller 2.4 below. Each solution (j1 , · · · , jN ) of (2.2) is associated to a term T in the above sum with  N

 N



  j c(ji ) td1 j1 +···+dN jN a i i νθ (Tj1 ,...,jN ) = νθ i=1

=

N 

ji ,

i=1

t∈T

for (j1 , . . . , jN ) = (0, . . . , 0)(Theorem 2.5).

(2.4)

i=1

Sometimes there is not equality in the bound of Theorem 2.1 on the p-adic valuation of Sp (F ) because it could happen that there is more than one solution (j1 , . . . , jN ) providing the minimum value for N i=1 ji . Remark 2.2. In the case that there is a unique (j1 , . . . , jN ) such that μp (d1 , . . . , dN ) = j1 + · · · + jN , then ⎛ ⎞ ⎜ ⎜ νθ (Sp (F )) = νθ ⎜ ⎝

 (j  ,...,j  ) 1 N  +···+d j  ≡0 mod p−1 d1 j1 N N

⎟ ⎟ Tj1 ,...,jN ⎟ = νθ (Tj1 ,...,jN ) ⎠

 ) = (j , . . . , j ) and (j  , . . . , j  ) satisfies (2.2). since νθ (Tj1 ,...,jN ) > νθ (Tj1 ,...,jN ) for any (j1 , . . . , jN 1 N 1 N

In [12], the author proved that μp (d1 , . . . , dN ) ≤ p−1 2 for N > 1. From now on, we call any solution (j1 , · · · , jN ) of (2.2) that has νθ (T ) = μp (d1 , . . . , dN ) of minimum value a minimal solution. Remark 2.3. If F (X) = X p−2 + aX d + bX over Fp , then the unique minimal solution of (p − 2)i + dj + k ≡ 0 mod p − 1 is (i, j, k) = (1, 0, 1) whenever d = p−1 2 . Using Remark 2.2, we have that p−2 d + bX + cX)) = 2. In [9], the authors studied the p-valuation of exponential sums νθ (Sp (aX associated to polynomials of degree p − 2 over Fp . We need to use the following lemma together with Stickelberger’s Theorem to compute the p-adic valuation.  j Lemma 2.4 ([10, 15]). There is a unique polynomial C(X) = p−1 j=0 c(j)X ∈ Qp (ξ)[X] of degree p − 1 such that C(t) = ξ t ,

for all t ∈ T.

Moreover, the coefficients of C(X) satisfy g(j) p , c(j) = p−1 p−1  −j where g(j) is the Gauss sum, given by g(j) = t∈T ∗ t ξ t . c(0) = 1, c(p − 1) = −

for 0 < j < p − 1,

Theorem 2.5 (Stickelberger [11, 15]). For 0 ≤ j < p − 1, g(j) · j! ≡ −1 mod θ. θj p-ADIC NUMBERS, ULTRAMETRIC ANALYSIS AND APPLICATIONS

(2.6)

Vol. 9 No. 4 2017

260

CASTRO, FIGUEROA

Now we state a criterion to determine when a polynomial is a permutation of a finite field using exponential sums: Theorem 2.6 ( [16]). The polynomial F (X) in one variable over Fp is a permutation polynomial of  Fp if and only if Sp (F ) = x∈Fp φ(F (x)) = 0 for all nontrivial additive characters φ of Fp . Remark 2.7. Theorem 2.6 implies that if Sp (F ) = 0 for at least one nontrivial additive character, then F is not a permutation polynomial of Fp . Now we state a result that is going be used to give a lower bound of the value set of the polynomials considered here.  d1 be a polynomial over F . Then the value set V of F Theorem 2.8. [8] Let F (X) = N p F i=1 ai X satisfies |VF | ≥ μp (d1 , . . . , dN ) + 1 3. RESULTS In this section we solve the optimization problem given in Lemma 2.1 for the modular equation d1 i + d2 j + d3 k ≡ 0 mod p − 1 under certain natural conditions. Using this, we compute the p-valuation for trinomials of the form aX d1 + bX d2 + cX d3 over Fp , where d3 ∈ {1, 2}. The study of when a binomial is a permutation of Fp has received a lot of attention (see Chapter 8 in [16]). Ayad-Belghaba-Kihel in [4] proved that if aX d1 + bX d2 is a permutation of Fp , then p − 1 ≤ d(d − 1), where d = gcd(d1 − d2 , p − 1). In the special case that (d1 − 1) | (p − 1), in [8], the authors proved that if aX d1 + bX is a permutation of Fp , then 2(p − 1) < d12 . Combining Theorem 2.6 with our calculation of the p-valuation of Sp (aX d1 + bX d2 + cX d3 ), we obtain restrictions for permutation trinomials of type aX d1 + bX d2 + cX d3 over Fp . Throughout this section, we assume that abc = 0. Now we consider the solutions of the modular equation d1 i + d2 j + k ≡ 0 mod p − 1.

(3.1)

Lemma 3.1. Let d1 > d2 > 1 be integers. If (i1 , j1 , k1 ) is a minimal solution of the modular equation (3.1), then k1 < d2 . Proof. Assume k1 ≥ d2 . Then i1 d1 + j1 d2 + k1 = i1 d1 + (j1 + 1)d2 + k1 − d2 and this one has sum i1 + j1 + 1 + k1 − d2 which is less than i1 + j1 + k1 since d2 > 1. Now we obtain the p-divisibility of some exponential sums. Theorem 3.2. Let d1 > d2 > 1 be integers. Let p − 1 = αd1 + s1 and s1 = βd2 + γ with α = (p − 1)/d1 , β = s1 /d2 . Assume that d2 ≤ s1 , d1 (β + γ) < p − 1 and (d1 − d2 )/d2 ≥ γ. Then the modular equation (3.1) has a unique minimal solution given by (i1 , j1 , k1 ) = (α, β, γ). Hence • νθ (Sp (aX d1 + bX d2 + cX)) = α + β + γ. • p > |VaX d1 +bX d2 +cX | ≥ α + β + γ + 1. In particular F (X) = aX d1 + bX d2 + cX is not a permutation polynomial of Fp . Proof. We have that (α, β, γ) is a solution with sum α + β + γ since p − 1 = αd1 + s1 = αd1 + βd2 + γ. Let (i1 , j1 , k1 ) = (0, 0, 0) be a solution with minimal sum i1 + j1 + k1 . From c(p − 1) = i1 d1 + j1 d2 + k1 for some integer c ≥ 1, we have that c(p − 1) ≤ d1 (i1 + j1 + k1 ) ≤ d1 (α + β + γ) = d1 α + d1 (β + γ) < 2(p − 1), therefore c = 1. We have i1 d1 + j1 d2 + k1 = p − 1 and i1 + j1 + k1 ≤ α + β + γ. We are going to prove that i1 = α, j1 = β, k1 = γ. 1) Case i1 > α. Then i1 d1 ≥ (α + 1)d1 > p − 1, but i1 d1 + j1 d2 + k1 = p − 1. This is a contradiction. p-ADIC NUMBERS, ULTRAMETRIC ANALYSIS AND APPLICATIONS

Vol. 9 No. 4 2017

p-ADIC VALUATION

261

2) Case i1 = α. From i1 d1 + j1 d2 + k1 = p − 1 = αd1 + βd2 + γ, we have (j1 − β)d2 = γ − k1 . Then j1 = β and k1 = γ since 0 ≤ k1 , γ < d2 . 3) Case i1 < α. From αd1 + βd2 + γ = i1 d1 + j1 d2 + k1 we have (α − i1 )d1 + γ = (j1 − β)d2 + k1 . We now consider different cases for k1 . (a) If k1 = 0 and γ = 0, then i1 + j1 ≤ α + β and j1 − β ≤ α − i1 . Now from (α − i1 )d1 = (j1 − β)d2 ≤ (α − i1 )d2 we have d1 ≤ d2 , which is a contradiction. (b) If k1 = 0 and γ > 0, then i1 + j1 ≤ α + β + γ and j1 − β ≤ α − i1 + γ. Now (j1 − β)d2 = (α − i1 )d1 + γ > (α − i1 )d1 implies j1 − β > (α − i1 )(d1 /d2 ) ≥ (α − i1 ) + (α − i1 )γ ≥ α − i1 + γ, which is not possible since j1 − β ≤ α − i1 + γ. (c) If k1 = 0 (and γ ≥ 0). Then (α − i1 )d1 + γ = (j1 − β)d2 + k1 < (j1 − β + k1 )d2 and j1 − β + k1 > (α − i1 )(d1 /d2 ) + γ/d2 ≥ α − i1 + (α − i1 )γ ≥ α − i1 + γ , therefore j1 − β + k1 > γ + α − i1 . Thus i1 + j1 + k1 > α + β + γ, which is a contradiction. We have proved that the modular equation (3.1) has a unique minimal solution. Then Remark 2.2 implies that νθ (S(aX d1 + bX d2 + cX)) = α + β + γ. Also, Remark 2.7 and Theorem 2.8 imply that p > |VaX d1 +bX d2 +cX | ≥ α + β + γ + 1. Example 3.3. These examples show that if one of the assumptions d1 (β + γ) < p − 1 or d1 ≥ d2 + d2 γ fails in Theorem 3.2, then the modular equation (3.1) has more that one minimal solution. Let us consider p = 101. 1) If d1 = 13, d2 = 5, then α = 7, s1 = 9 = d2 + 4, β = 1, γ = 4. In this case d1 (β + γ) = 65 < p − 1 and d1 > d2 + d2 γ = 25 fails. The minimal solutions are (7, 1, 4) and (5, 7, 0). In this case we have νθ (S101 (aX 13 + bX 5 + cX)) ≥ 12. 2) If d1 = 27, d2 = 2, then α = 3, s1 = 19, β = 9, γ = 1. We have d1 ≥ d2 + d2 γ = 5 and d1 (β + γ) = 27(10) < 100 fails. The modular equation has three minimal solutions: (3, 9, 1), (7, 5, 1) and (11, 1, 1). In this case we have νθ (S101 (aX 27 + bX 2 + cX)) ≥ 13. In the next case we consider the case when d2 > s1 . Theorem 3.4. Let d1 > d2 > 1 be integers. Let p − 1 = αd1 + s1 with α = (p − 1)/d1 . Assume s1 < d2 . Let d1 + s1 = βd2 + γ with β = (d1 + s1 )/d2 . If d1 (β + γ) < p − 1 and (d1 − d2 )/d2 ≥ γ, then the modular equation (3.1) has a unique minimal solution or two minimal solutions according to 1) If s1 ≥ β + γ, then (i1 , j1 , k1 ) = (α − 1, β, γ) is the unique minimal solution. Hence • νθ (Sp (aX d1 + bX d2 + cX)) = α − 1 + β + γ. • p > |VaX d1 +bX d2 +cX | ≥ α + β + γ. In particular, F (X) = aX d1 + bX d2 + cX is not a permutation polynomial of Fp . 2) If s1 + 1 < β + γ, then (i1 , j1 , k1 ) = (α, 0, s1 ) is the unique minimal solution. Hence • νθ (Sp (aX d1 + bX d2 + cX)) = α + s1 . • p > |VaX d1 +bX d2 +cX | ≥ α + s1 + 1. In particular, F (X) = aX d1 + bX d2 + cX is not a permutation polynomial of Fp . 3) If s1 + 1 = β + γ, then (α, 0, s1 ) and (α − 1, β, γ) are the minimal solutions. • νθ (Sp (aX d1 + bX d2 + cX)) ≥ α − 1 + β + γ. p-ADIC NUMBERS, ULTRAMETRIC ANALYSIS AND APPLICATIONS

Vol. 9 No. 4 2017

262

CASTRO, FIGUEROA

• |VaX d1 +bX d2 +cX | ≥ α + β + γ. Proof. Since p − 1 = αd1 + s1 = (α − 1)d1 + d1 + s1 = (α − 1)d1 + βd2 + γ, we have that (α − 1, β, γ) and (α, 0, s1 ) are solutions of the modular equation (3.1). Let (i1 , j1 , k1 ) be a minimal solution with sum i1 + j1 + k1 . We have c(p − 1) = i1 d1 + j1 d2 + k1 , for some integer c ≥ 1. Then c(p − 1) = i1 d1 + j1 d2 + k1 ≤ d1 (i1 + j1 + k1 ) ≤ d1 (α − 1 + β + γ) = d1 (α − 1) + d1 (β + γ) < 2(p − 1), therefore c = 1. We now consider two cases: j1 > 0 and j1 = 0. 1) Case j1 > 0. We have that i1 d1 + j1 d2 + k1 = p − 1 and i1 + j1 + k1 ≤ α − 1 + β + γ. We are going to prove that i1 = α − 1, j1 = β, k1 = γ. (a) Case i1 > α − 1. Then i1 = α and i1 d1 + j1 d2 + k1 = αd1 + j1 d2 + k1 = p − 1 = αd1 + s1 , from here j1 d2 + k1 = s1 , which is not possible since j1 > 0 and s1 < d2 . (b) Case i1 = α − 1. Then p − 1 = i1 d1 + j1 d2 + k1 = (α − 1)d1 + βd2 + γ implies j1 d2 + k1 = βd2 + γ and j1 = β, k1 = γ since 0 ≤ k1 , γ < d2 . (c) Case i1 < α − 1. This case is similar to part (iii) in Theorem 3.2 after substituting α by α − 1 2) Case j1 = 0. If (i1 , 0, k1 ) is a minimal solution then k1 < d2 < d1 by Lemma 3.1, and from p − 1 = αd1 + s1 = i1 d1 + k1 , we have i1 = α and k1 = s1 . Therefore, we have that (α − 1, β, γ) is a minimal solution of the modular equation (3.1) when j = 0 and (α, 0, s1 ) is a minimal solution when j = 0. We have to decide which of these solutions is the minimal solution. For (α, 0, s1 ) the sum is α + s1 and for (α − 1, β, γ) the sum is α − 1 + β + γ. • If s1 ≥ β + γ, then α + s1 > α − 1 + β + γ and (α − 1, β, γ) is the minimal solution. • If s1 + 1 < β + γ, then α + s1 < α − 1 + β + γ and (α, 0, s1 ) is the minimal solution. • If s1 + 1 = β + γ, then (α, 0, s1 ) and (α − 1, β, γ) are both minimal solutions with the same sum. We have proved that the minimal solution of the modular equation (3.1) satisfies conditions 1, 2 and 3 of Theorem 3.4. Using Remarks 2.2 and 2.7 and Theorem 2.8 we obtain the desired result. Example 3.5. In these examples for the given prime p, the integers α, s1 , β and γ are defined as in Theorem 3.4. These integers satisfy d1 (β + γ) < p − 1, d1 ≥ d2 + γd2 and s1 < d2 . 1) For p = 373, d1 = 26, d2 = 11 we have α = 14, s1 = 8, β = 3, γ = 1, and α − 1 + β + γ = 17 < α + s1 , so (α − 1, β, γ) is the minimal solution. Hence νθ (S373 (aX 26 + bX 11 + cX)) = 13 + 3 + 1 = 17 and 373 > |VaX 26 +bX 11 +cX | ≥ 18. 2) For p = 373, d1 = 23, d2 = 5 we have α = 16, s1 = 4, β = 5, γ = 2 and α + s1 = 20 < α − 1 + β + γ = 22, so (α, 0, s1 ) is the minimal solution. Hence νθ (S373 (aX 23 + bX 5 + cX)) = 15 + 4 = 19 and 373 > |VaX 26 +bX 11 +cX | ≥ 20. 3) For p = 907, d1 = 43, d2 = 15 we have α = 21, s1 = 3, β = 3, γ = 1. In this case 1 + s1 = β + γ. Hence νθ (S907 (aX 43 + bX 15 + cX)) ≥ 20 + 3 + 1 = 17 and 373 > |VaX 26 +bX 11 +cX | ≥ 18. Combining the last two theorems we obtain the following result. Corollary 3.6. Let d1 > d2 be integers. Assume d12 < p − 1 and d2 + d22 ≤ d1 . If p − 1 = αd1 + s1 , s1 = βd2 + γ, where α = (p − 1)/d1 , β = s1 /d2 . Then • νθ (Sp (aX d1 + bX d2 + cX)) = α + β + γ p-ADIC NUMBERS, ULTRAMETRIC ANALYSIS AND APPLICATIONS

Vol. 9 No. 4 2017

p-ADIC VALUATION

263

• p > |VaX d1 +bX d2 +cX | ≥ α + β + γ + 1. In particular F (X) = aX d1 + bX d2 + cX is not a permutation polynomial of Fp . Proof. Let p − 1 = αd1 + s1 with s1 < d1 . Assume d2 ≤ s1 . Let s1 = βd2 + γ with γ < d2 . Then s1 > β + γ and d1 (β + γ) < d1 s1 < d21 < p − 1. Since γ < d2 we have d1 ≥ d2 + d22 > d2 + γd2 . Theorem 3.2 implies that (α, β, γ) is the unique minimal solution. Using Remark 2.2 and Theorem 2.8 the conclusion of the theorem follows for the case d2 ≤ s1 . Assume now d2 > s1 . Let d1 + s1 = β1 d2 + γ with γ < d2 and β1 = (d1 + s1 )/d2 . Then β1 d2 + γ < d1 + d2 and (β1 − 1)d2 + γ < d1 . If β1 ≥ 2, then (β1 − 1)d2 ≥ 2(β1 − 1) ≥ β1 . Hence d1 > β1 + γ and d1 (β1 + γ) < d21 < p − 1. If β1 = 1, then d2 + γ = d1 + s1 < d1 + d2 , so γ < d1 , 1 + γ ≤ d1 and d1 (1 + γ) ≤ d21 < p − 1. If β1 = 0, then d1 ≤ d1 + s1 = 0d2 + γ < d2 which is not possible since d1 > d2 . The above proof that for d2 > s1 the hypothesis of Theorem 3.4 hold. We now apply Theorem 3.4. If 1 + s1 ≥ β1 + γ, then from d1 + s1 = β1 d2 + γ we have β1 d2 + γ ≥ d1 + β1 + γ − 1 and β1 (d2 − 1) ≥ d1 − 1 ≥ d2 + d22 − 1, (β1 − 1)(d2 − 1) ≥ d22 , but then β1 d2 ≥ (β1 − 1)(d2 − 1) ≥ d22 . Hence β1 > d2 , 1 + s1 ≥ β1 + γ ≥ β1 > d2 and s1 ≥ d2 , but s1 < d2 . Therefore 1 + s1 < β1 + γ and Theorem 3.4 implies that (α, 0, s1 ) = (α, 0, γ) is the minimal solution. Using Remarks 2.2, 2.7 and Theorem 2.8 the proof follows for the case d2 > s1 . The next example implies that both conditions are necessary in Corollary 3.6. Example 3.7. The polynomial X 3 + X 2 + 6X is a permutation of F17 . Note that 9 = (3)2 < 16 but 3 ≤ 22 + 2 = 6. The polynomial X 22 + 6X 4 + 2X is a permutation of F37 . Note that 42 + 4 < 22 but 222 > 100. Example 3.8. For p = 101, the families of polynomials aX d1 + bX d2 + cX are not permutations of F101 for (d1 , d2 ) ∈ {(10, 3), (9, 3), (9, 2), (8, 2), (7, 2), (6, 2)} and abc = 0. In the next corollary, we use the results about the minimal solution of (3.1) obtained previously to compute the exact p-valuation of the exponential sums associated to aX d1 + bX d2 + cX 2 . Corollary 3.9. Let d1 > d2 > 2 be integers. Assume d12 < p − 1 and d1 ≥ d2 + d22 . If p − 1 = αd1 + s1 , s1 = βd2 + γ, where α = (p − 1)/d1 , β = s1 /d2  and γ is even. Then • νθ (Sp (aX d1 + bX d2 + cX 2 )) = α + β + γ2 . • p > |VaX d1 +bX d2 +cX 2 | ≥ α + β + permutation polynomial of Fp .

γ 2

+ 1. In particular F (X) = aX d1 + bX d2 + cX 2 is not a

Proof. If d1 | (p − 1), the conclusion of the corollary is true. From now on, we assume that d1  (p − 1). Note that (α, β, γ2 ) is a solution of the modular equation: d1 i + d2 j + 2k ≡ 0 mod p − 1.

(3.2)

Let (i1 , j1 , k1 ) be a minimal solution of (3.2) satisfying γ γ and (i1 , j1 , k1 ) = (α, β, ). i1 + j1 + k1 ≤ α + β + 2 2 Note that (i1 , j1 , 2k1 ) is solution of d1 i + d2 j + k ≡ 0 mod p − 1. We have that

(3.3)

(3.4)

i1 + j1 + 2k1 > α + β + γ

since Corollary 3.6 implies that the unique minimal solution of d1 i + d2 j + k ≡ 0 mod p − 1 is (α, β, γ). (3.2) implies that d1 i1 + d2 j1 + 2k1 = c(p − 1) for integer c ≥ 1. We have c(p − 1) = i1 d1 + j1 d2 + 2k1 ≤ d1 (i1 + j1 + k1 ) ≤ d1 (α + β + γ) = d1 α + d1 (β + γ) < 2(p − 1) p-ADIC NUMBERS, ULTRAMETRIC ANALYSIS AND APPLICATIONS

Vol. 9 No. 4 2017

264

CASTRO, FIGUEROA

since d1 α < p − 1 and d1 (β + γ) ≤ d1 s1 < d21 < p − 1. Hence c = 1. From (3.3) and (3.4) we obtain 0 < k1 − γ2 . We can rewrite (3.3) in this form γ 0 < k1 − ≤ (α − i1 ) + (β − j1 ). 2 Now using that c = 1, we have

(3.5)

γ p − 1 = d1 i1 + d2 j1 + 2k1 = d1 α + d2 β + 2( ) 2 γ d1 d2 (3.6) k1 − = (α − i1 ) + (β − j1 ) > (α − i1 ) + (β − j1 ), 2 2 2 whenever α − i1 > 0 and β − j1 > 0. Using (3.5) we obtain contradiction. Note that α − i1 ≥ 0 since d1 (α + 1) > p − 1. The only missing case is (β − j1 ) ≤ 0. Suppose β − j1 ≤ 0. Then k1 − γ2 = d21 (α − i1 ) + d22 (β − j1 ) ≥ d21 (α − i1 ) + d21 (β − j1 ) = d21 (α − i1 + β − j1 ) > α − i1 + β − j1 . Using (3.5) we obtain contradiction. The next theorem computes the divisibility for families of trinomials not included in the previous theorems. Theorem 3.10. Let d > 3 be an integer. Assume (d − 1) | (p − 1). If p − 1 < (d − 1)2 , then the modular equation di + (d − 1)j + k ≡ 0 mod p − 1 has a unique minimal solution. In particular • d

νθ (Sp (aX + bX

d−1

⎧ ⎪ ⎪ ⎪ ⎨ + cX)) =

⎪ ⎪ ⎪ ⎩

p−1 d−1

if d  (p − 1),

p−1 d

if d | (p − 1).

• p > |VaX d +bX d−1 +cX | ≥ p−1 d− + 1, where  = 0 if d | (p − 1), and otherwise  = 1. In particular d d−1 + cX is not a permutation polynomial of Fp . F (X) = aX + bX Proof. Let p − 1 = αd + s1 . If s1 = 0, then the unique minimal solution is p−1 d . From now on, suppose d  (p − 1). Suppose (i1 , j1 , k1 ) is a minimal solution of (3.1) satisfying i1 + j1 + k1 ≤ p−1 d−1 . Suppose di1 + (d − 1)j1 + k1 = c(p − 1) where c ≥ 1. Then c(p − 1) = di1 + (d − 1)j1 + k1 < di1 + dj1 + dk1 ≤ This implies that c ≤

d d−1 .

d(p − 1) . d−1

This is a contradiction unless c = 1. We have p − 1 . di1 + (d − 1)j1 + k1 = (d − 1) d−1

Therefore p − 1  − j1 . di1 + k1 = (d − 1) d−1

(3.7)

p−1 . If i1 + k1 = 0, then (d − 1) | (di1 + k1 ). Hence (d − 1) | i1 + k1 . If p − 1 < If i1 + j1 = 0, then j2 = d−1 p−1 2 . This is a contradiction. (d − 1) , then i1 + j1 + k1 ≥ i1 + k1 ≥ d − 1 > d−1

The next example shows that the condition (p − 1) < (d − 1)2 is necessary in Theorem 3.10. p-ADIC NUMBERS, ULTRAMETRIC ANALYSIS AND APPLICATIONS

Vol. 9 No. 4 2017

p-ADIC VALUATION

265

Example 3.11. Let p = 101 and d = 11. The modular equation 11i + 10j + k ≡ 0 mod 100 has two minimal solutions (9, 0, 1), (0, 10, 0). Note that 100 = p − 1 = (d − 1)2 = 100. In the following table, we find the number of permutation polynomials of type X d1 + aX d2 + bX for some p. p

number of trinomials number of pairs [d1 , d2 ]

7

6

{[5, 3]}

11 20

{[7, 4], [3, 2]}

13 116

{[5, 3], [9, 7], [9, 5], [10, 4], [10, 7], [7, 3], [7, 4]}

17 128

{[5, 3], [13, 5], [11, 7], [9, 5], [13, 9], [13, 7], [11, 6], [3, 2]}

19 60

{[13, 7]}

23 110

{[5, 3], [15, 8], [15, 9], [9, 5], [3, 2]}

29 280

{[21, 9], [21, 17], [19, 10], [21, 5], [15, 8], [25, 21], [22, 8], [22, 15], [3, 2]}

31 449

{[21, 11], [25, 13], [25, 16], [11, 6], [16, 6], [26, 6], [21, 16], [25, 7], [26, 21], [19, 13], [25, 19], [26, 16], [13, 7], [19, 7]}

37 848

{[17, 9], [31, 19], [25, 13], [28, 19], [31, 7], [28, 10], [25, 7], [19, 13], [31, 25], [5, 3], [29, 15], [25, 19], [31, 13], [19, 10], [22, 4], [13, 7], [19, 7]}

41 870

{[17, 9], [36, 26], [31, 21], [21, 11], [27, 14], [9, 5], [36, 21], [33, 17], [36, 31], [25, 9], [31, 11], [33, 25], [25, 17], [3, 2], [33, 9]}

47 230

{[37, 19], [31, 17], [5, 3], [31, 16], [3, 2]}

59 116

{[39, 20], [3, 2]}

83 410

{[3, 2], [55, 29], [55, 28], [5, 3], [33, 17]}

107 530

{[71, 37], [5, 3], [3, 2], [71, 36], [85, 43]}

Using the above table we state a conjecture about the number permutation trinomials of type X d1 + aX d2 + bX. Conjectures. • Let p = 2p1 + 1 be a Sophie Germain prime with p1 > 3. Then the number of permutation trinomials of type X d1 + aX d2 + bX is 4 · p1 if p ≡ ±1 mod 10 and 10 · p1 if p ≡ ±3 mod 10. • Let p be a prime number. Let Nd1 ,d2 be the number permutation polynomials of Fp of type X d1 + aX d2 + bX. If Nd1 ,d2 · Nd1 ,d2 > 0, then Nd1 ,d2 = Nd1 ,d2 . p-ADIC NUMBERS, ULTRAMETRIC ANALYSIS AND APPLICATIONS

Vol. 9 No. 4 2017

266

CASTRO, FIGUEROA

ACKNOWLEDGMENTS The authors would like to thank the referee for her/his helpful suggestions that improved the presentation of this paper. Also, we would like to thank Francis N. Castro Velez for his comments in previous versions of this paper. The first author would like to thank Tatiana Castro Velez for her valuable assistance with the last details of this paper. REFERENCES 1. A. Adolphson and S. Sperber, “p-Adic estimates for exponential sums and the theorem of ChevalleyWarning,” Ann. Sci. Ecole Norm. Sup. 20, 545–556 (1987). 2. A. Adolphson and S. Sperber, “Exponential sums nondegenerate relative to a lattice,” Alg. Numb. Theory 8, 881–906 (2009). 3. A. Adolphson and S. Sperber, “Hasse invariants and mod p solutions of A-hypergeometric systems,” J. Numb. Theory 142, 183–210 (2014). 4. M. Ayad, K. Belghaba and O. Kihel, “On permutations binomials over finite fields,” Bull. Aust. Math. Soc. 89, 116–124 (2014). 5. R. Blache, “Valuation of exponential sums and the generic first slope for Artin-Schreier curves,” J. Numb. Theory 132, 2336–2352 (2012). 6. J. Chen and W. Cao, “Degree matrices and divisibility of exponential sums over finite fields,” Arch. Math. 94, 435–441 (2010). 7. F. Castro, R. Figueroa and J. Ortiz-Ubarri, “Divisibility of exponential sums in one variable associated to binomials over Fp ,” Contemporary Developments in Finite Fields and Applications, 11–21 (2016). 8. F. Castro, R. Figueroa and P. Guan, “p-Adic valuation of exponential sums in one variable associated to binomials,” Unif. Distr. Theory 12, 37–53 (2107). 9. F. Castro, R. Figueroa and L. Medina, “Exact divisibility of exponential sums and some consequences,” Contemp. Math. 579, 55–66 (2012). 10. N. Koblitz, p-Adic Numbers, p-Adic Analysis, and Zeta-Functions, GTM 58 (Springer-Verlag, New York, 1984). 11. N. Koblitz, p-Adic Analysis: A Short Course on Recent Work, 46 (Cambridge University Press, 1980). 12. X. Liu, “A problem related to the divisibility of exponential sums,” http://arxiv.org/pdf/1502.07281.pdf, (2015). 13. O. Moreno and C. J. Moreno, “Improvements of the Chevalley-Warning and the Ax-Katz theorems,” Amer. J. Math. 117, 241–244 (1995). 14. O. Moreno, K. Shum, F. N. Castro and P. V. Kumar, “Tight bounds for Chevalley-Warning-Ax type estimates, with improved applications,” Proc. London Math. Soc. 88, 545–564 (2004). 15. C. J. Moreno, Algebraic Curves Over Finite Fields (Cambridge University Press, 1991). 16. G. Mullen and D. Panario, Handbook of Finite Fields, Discrete Mathematics and its Applications (CRC Press, 2013). 17. S. Scholten and H. J. Zhu, “The first case of Wan’s conjecture,” Fin. Fields Their Appl. 8, 414–419 (2002). 18. S. Sperber, “On the p-adic theory of exponential sums,” Amer. J. Math 108, 255–296 (1986).

p-ADIC NUMBERS, ULTRAMETRIC ANALYSIS AND APPLICATIONS

Vol. 9 No. 4 2017