Pascal Autissier
email: pascal.autissier@math.u-bordeaux.fr

AND Dante Bonolis
email: dante.bonolis@math.ethz.ch

Youness Lamzouri
email: youness.lamzouri@univ-lorraine.fr

THE DISTRIBUTION OF THE MAXIMUM OF PARTIAL SUMS OF KLOOSTERMAN SUMS AND OTHER TRACE FUNCTIONS

In this paper, we investigate the distribution of the maximum of partial sums of families of m-periodic complex valued functions satisfying certain conditions. We obtain precise uniform estimates for the distribution function of this maximum in a near optimal range. Our results apply to partial sums of Kloosterman sums and other families of -adic trace functions, and are as strong as those obtained by Bober, Goldmakher, Granville and Koukoulopoulos for character sums. In particular, we improve on the recent work of the third author for Birch sums. However, unlike character sums, we are able to construct families of m-periodic complex valued functions which satisfy our conditions, but for which the Pólya-Vinogradov inequality is sharp.

Introduction

Let m ≥ 2 be an integer, and ϕ : Z/mZ → C a complex valued function which we extend to an m-periodic function ϕ : Z → C. An important problem in analytic number theory is to obtain non-trivial estimates for the quantity

M(ϕ) := max x<m 0≤n≤x ϕ(n) .
The special case where ϕ = χ is a Dirichlet character modulo m has been extensively studied over the last century, going back to the classical inequality proved by Pólya and Vinogradov in 1918:

M(χ) √ m log m.
A straightforward generalization of this bound for a general m-periodic complex valued function ϕ gives where here and throughout we let e(z) := exp(2πiz), and e m (z) := e(z/m) is the standard additive character modulo m. To see this, consider the discrete Plancherel formula The Pólya-Vinogradov bound (1.1) follows by using the elementary estimate (see for example page 1501 of [START_REF] Kowalski | Kloosterman paths and the shape of exponential sums[END_REF])

(1.3) 1 √ m γ m (h; x) = e m (xh) -1 2πih + O 1 m ,
which holds uniformly for 1 ≤ |h| ≤ m/2. We shall only consider those ϕ for which the Fourier transform ϕ is uniformly bounded (this includes primitive Dirichlet characters), which in view of the Pólya-Vinogradov bound (1.1) gives (1.4) M(ϕ) √ m log m.

In the case of character sums, Montgomery and Vaughan [START_REF] Montgomery | Exponential sums with multiplicative coefficients[END_REF] proved that this bound is not optimal conditionally on the generalized Riemann hypothesis GRH. Indeed, they showed that assuming GRH we have

M(χ) √ m log log m,
for all non-principal Dirichlet characters χ (mod m). This last bound is in fact optimal in view of an old result of Paley [START_REF] Paley | A theorem on characters[END_REF] who showed that M(χ m ) √ m log log m for infinitely many m, where χ m is the quadratic character modulo m.

Recently, Bober, Goldmakher, Granville and Koukoulopoulos [START_REF] Bober | The frequency and the structure of large character sums[END_REF] investigated the distribution of M(χ) over non-principal characters χ modulo a large prime q. If we denote by Φ char (V ) the proportion of non-principal characters χ mod q for which M(χ)/ √ q > V , then the main result of [START_REF] Bober | The frequency and the structure of large character sums[END_REF] states that for C ≤ V ≤ C 0 log log q -C (where C is an absolute constant), one has (1.5) Φ char (V ) = exp -e V /C 0 +O (1) V ,

where C 0 = e γ /π, and γ is the Euler-Mascheroni constant.

Building on the work of Kowalski and Sawin [START_REF] Kowalski | Kloosterman paths and the shape of exponential sums[END_REF], Lamzouri [START_REF] Lamzouri | On the distribution of the maximum of cubic exponential sums[END_REF] investigated a similar question for the partial sums of certain exponential sums. For a prime p ≥ 3 the Birch sum associated to a ∈ F p is the following normalized complete cubic exponential sum Bi p (a) := 1 √ p n∈Fp e p (n 3 + an).

These sums were first considered by Birch [START_REF] Birch | How the number of points of an elliptic curve over a fixed prime field varies[END_REF] who conjectured that Bi p (a) becomes equidistributed according to the Sato-Tate measure as a varies in F × p and p → ∞. This conjecture was subsequently proved by Livné in [START_REF] Livné | The average distribution of cubic exponential sums[END_REF]. Let ϕ a (n) = e p (n 3 + an) and define

Φ Bi (V ) = 1 p -1 a ∈ F × p : M(ϕ a ) √ p > V .
Lamzouri [START_REF] Lamzouri | On the distribution of the maximum of cubic exponential sums[END_REF] proved that for V in the range 1 V ≤ (2/π) log log p -2 log log log p, we have (1.6) exp -exp

π 2 V + O(1) ≤ Φ Bi (V ) ≤ exp -exp π 2 -δ V + O(1)
where δ = 4π-π 2 2π+8 = 0.18880.... He also conjectured that the lower bound corresponds to the true order of magnitude for Φ Bi (V ). The techniques are different in this setting, due to the lack of multiplicativity for these exponential sums. Indeed, in the case of character sums, Bober, Goldmakher, Granville and Koukoulopoulos [START_REF] Bober | The frequency and the structure of large character sums[END_REF] exploit the relation with L-functions and smooth numbers, while ingredients from algebraic geometry and notably Deligne's equidistribution theorem play a central role in [START_REF] Lamzouri | On the distribution of the maximum of cubic exponential sums[END_REF].

Lamzouri also showed that the lower bound in (1.6) where n denotes the multiplicative inverse of n modulo p. Similarly to Birch sums, Katz [START_REF] Katz | Gauss sums, Kloosterman sums, and monodromy groups[END_REF] proved that Kl p (a, 1) becomes equidistributed according to the Sato-Tate measure as a varies in F × p and p → ∞. Let ϕ (a,b) (n) = e p (an + bn). The method of [START_REF] Lamzouri | On the distribution of the maximum of cubic exponential sums[END_REF] allows one to prove that in the range 1

V ≤ (2/π) log log p -2 log log log p we have

Φ Kl (V ) := 1 (p -1) 2 (a, b) ∈ F × p × F × p : M(ϕ (a,b) ) √ p > V ≥ exp -exp π 2 V + O(1) .
However, the argument is not strong enough to yield an upper bound for the distribution function Φ Kl (V ) in this case, since it relies on strong bounds for short sums of exponential sums, which are not currently known for Kloosterman sums.

In this paper, we prove Lamzouri's conjecture for the maximum of partial sums of Birch and Kloosterman sums, obtaining estimates for their distribution functions that are as strong as (1.5) for character sums. We also obtain analogous results for families of periodic functions which satisfy certain hypotheses (see Theorem 1.2 below). A corollary of our main theorem is the following result.

Corollary 1.1. Let p be a large prime. There exists a constant C such that for all real numbers C ≤ V ≤ (2/π)(log log p -2 log log log p) -C we have

Φ Kl (V ) = exp -exp π 2 V + O(1) .
The same estimate also holds for Φ Bi (V ).

There are two new ingredients that allow us to prove Lamzouri's conjecture. The first is a non-trivial upper bound for the fourth moment of the maximum over all intervals I of length |I| ≤ p 1/2+ε with ε > 0 (intervals at the edge of the Pólya-Vinogradov range), of short sums of Kloosterman sums over I (see Lemma 3.1 for a general result of this type). This allows us to obtain the analogue of (1.6) for Φ Kl (V ). The second ingredient is a precise asymptotic formula for the maximum of a certain "random" exponential sum (see Theorem 2.1 below), which we use to replace the constant π/2 -δ by π/2 in the upper bound of (1.6), thus proving Lamzouri's conjecture.

1.1. A general result for the maximum of partial sums of m-periodic functions. We shall consider families of periodic functions F = {ϕ a } a∈Ωm , where Ω m is a non-empty finite set, and for each a ∈ Ω m , ϕ a : Z → C is m-periodic and its Fourier transform ϕ a is real-valued and uniformly bounded. For a positive real number V , we define

Φ F (V ) := 1 |Ω m | a ∈ Ω m : M(ϕ a ) √ m > V .
We will obtain precise uniform estimates for this distribution function, assuming that our family F satisfies certain hypotheses, which are mainly related to the distribution of the Fourier transform ϕ a . Such assumptions will be verified by several important functions in analytic number theory, which arise naturally in applications and originate in the deep work of Deligne and others from algebraic geometry. These functions correspond to certain Frobenius trace functions modulo m, and their analytic properties have been investigated by several authors, and notably in a series of recent works by Fouvry, Kowalski, and Michel [START_REF] Fouvry | Trace functions over finite fields and their applications[END_REF], [START_REF] Fouvry | Algebraic twists of modular forms and Hecke orbits[END_REF], [START_REF] Fouvry | A study in sums of products[END_REF], [START_REF] Fouvry | On the conductor of cohomological transforms[END_REF], Fouvry, Kowalski, Michel, Raju, Rivat, and Soundararajan [START_REF] Fouvry | On short sums of trace functions[END_REF], Kowalski and Sawin [START_REF] Kowalski | Kloosterman paths and the shape of exponential sums[END_REF], and Perret-Gentil [START_REF] Perret-Gentil | Gaussian distribution of short sums of trace functions over finite fields[END_REF]. In particular, these include the families of trace functions F Bi = {e p (n 3 + an)} a∈F × p and F Kl = {e p (an + bn)} (a,b)∈F × p ×F × p , which give rise to partial sums of Birch and Kloosterman sums respectively. More specifically, let F = {ϕ a } a∈Ωm be a family of m-periodic complex valued functions, and consider the following assumptions:

-uples (h 1 , . . . , h k ) ∈ (-m/2, m/2] k with h i = 0 for i = 1, ..., k we have 1 |Ω m | a∈Ωm ϕ a (h 1 ) • • • ϕ a (h k ) = E (X(h 1 ) . . . X(h k )) + O C k 1 m η .
Furthermore, if we let X be a random variable with the same distribution as the X(h), then X verifies the following conditions:

3a. There exists a positive constant A such that for all ε ∈ (0, 1] we have P(X > N -ε) ε A , and P(X < -N + ε) ε A . 3b. For all integers ≥ 0 we have E X 2 +1 = 0.

Assumption 4. Strong bounds for short sums on average

There exist absolute constants α ≥ 1, and 0 < δ < 1/2 such that for any interval

I of length |I| ≤ m 1/2+δ , one has 1 |Ω m | a∈Ωm 1 √ m n∈I ϕ a (n) α m -1/2-δ .
Our main result is the following theorem. Theorem 1.2. Let m be large, and F = {ϕ a } a∈Ωm be a family of m-periodic complex valued functions satisfying one of the following subsets of the above assumptions: Then there exists a constant B such that for all real numbers B ≤ V ≤ (N/π)(log log m-2 log log log m) -B we have Kowalski and Sawin [19] but for a different purpose. The authors of [START_REF] Kowalski | Kloosterman paths and the shape of exponential sums[END_REF] investigated Birch and Kloosterman paths, which are the polygonal paths formed by linearly interpolating the partial sums of Birch and Kloosterman sums. They used Assumption 4 to establish a weak-compactness property known as tightness, which was necessary in order to show that the processes obtained from Birch and Kloosterman paths converge in law (in the Banach space C[0, 1]) to a random Fourier series (which is the series inside the absolute value in (1.12) below). In our case, we found a new argument that allows us to use Assumption 4 (which holds for Kloosterman sums) instead of strong point wise bounds for short sums of exponential sums, which were needed in [START_REF] Lamzouri | On the distribution of the maximum of cubic exponential sums[END_REF].

(1.7) Φ F (V ) = exp -exp π N V + O(1
Remark 1.5. One can wonder whether a condition on the size of Ω m is necessary to prove Theorem 1.2. In fact, such a condition is implicitly contained in Assumptions 2 and 3. More specifically, we show in Lemma 7.3 below that if F = {ϕ a } a∈Ωm satisfies these assumptions, then we must have |Ω m | m.

One should note that the implicit upper bound for Φ F (V ) in Theorem 1.2 holds in the slightly larger range B ≤ V ≤ (N/π)(log log m -log log log m) -B for some constant B that depends at most on the parameters in the assumptions of Theorem 1.2. Moreover, our proof of the implicit lower bound gives a much more precise estimate. In this case only Assumptions 2 and 3 are needed.

Theorem 1.6. Let m be large, and F = {ϕ a } a∈Ωm be a family of m-periodic complex valued functions satisfying Assumptions 2 and 3 above. For all real numbers 1 ≤ V ≤ (N/π)(log log m -2 log log log m -B) we have

Φ F (V ) ≥ exp -A 0 exp π N V 1 + O V e -πV /(2N )
where

(1.8) A 0 = N 2 exp -γ -1 - 1 2N ∞ -∞ f X (u) u 2 du , B = log A 0 + 9,
γ is the Euler-Mascheroni constant, and f X : R → R is defined by

(1.9) f X (t) := log E(e tX ) if |t| < 1, log E(e tX ) -N |t| if |t| ≥ 1,
where X is a random variable with the same distribution as the {X(h)} h∈Z * in Assumption 3 above.

As an application of Theorem 1.6 (more specifically of Theorem 7.1 which is stronger), we exhibit large values of partial sums in families of periodic functions {ϕ a } a∈Ωm satisfying Assumptions 2 and 3. This was obtained by Lamzouri [START_REF] Lamzouri | On the distribution of the maximum of cubic exponential sums[END_REF] for Birch and Kloosterman sums, and independently by Bonolis [START_REF] Bonolis | On the size of the maximum of incomplete Kloosterman sums[END_REF] for more general trace functions (though with a smaller constant).

Corollary 1.7. Let m be large, and F = {ϕ a } a∈Ωm be a family of m-periodic complex valued functions satisfying Assumptions 2 and 3 above. There exist at least

|Ω m | 1-1/ log log m elements a ∈ Ω m such that (1.10) 0≤n≤m/2 ϕ a (n) ≥ N π + o(1) √ m log log m.
Given a family F = {ϕ a } a∈Ωm of m-periodic complex valued functions satisfying the assumptions in Theorem 1.2, a natural question to ask is which of the bounds (1.4) and (1.10) is optimal (up to a constant). If we suppose that the estimate (1.7) is valid in the whole "viable" range, that is for 1

V < V max := max a∈Ωm M(ϕ a )/ √ m, then we would have exp -exp π N V max + O(1) = Φ F (V max -o(1)) ≥ 1 |Ω m | ,
and hence

V max ≤ N π log log |Ω m | + O(1
max a∈Ωm M(ϕ a ) ≥ 1 π √ m log m + O( √ m).
Remark 1.9. The family we construct in Proposition 1.8 does not satisfy Assumption 1. In fact one has max a∈Ωm ||ϕ a || ∞ √ m for this family. One therefore wonders whether a similar result to Proposition 1.8 holds for certain families of m-periodic complex valued functions satisfying the assumptions in case C) of Theorem 1.2, which is the case of most interest. Unfortunately, we were unable to construct such families. However, it seems plausible that in this case there are less fluctuations in the partial sums of ϕ a , and that a bound similar to (1.11) holds.

It follows from the results of Kowalski and Sawin [START_REF] Kowalski | Kloosterman paths and the shape of exponential sums[END_REF] that

lim p→∞ Φ Kl (V ) = lim p→∞ Φ Bi (V ) = P(M st > V ),
for any fixed V for which P(M st > V ) is continuous, where (1.12)

M st = max α∈[0,1) αY(0) + h =0 e(αh) -1 2πih Y(h) ,
and {Y(h)} h∈Z is a sequence of independent random variables with Sato-Tate distributions on [-2, 2]. A straightforward generalization of their argument shows that if m is large and F = {ϕ a } a∈Ωm is a family of m-periodic complex valued functions satisfying Assumptions 1, 2, 3, and 4, then for V ≥ 1 fixed we have

lim m→∞ Φ F (V ) = P(M X > V ),
where

M X = max α∈[0,1) αX(0) + h =0 e(αh) -1 2πih X(h) ,
and {X(h)} h∈Z is a sequence of I.I.D. random variables supported on [-N, N ] and satisfying Assumptions 3a and 3b above. Combining this result with Theorem 1.2 leads to the following estimate for the large deviations of the random model M X , which improves on the estimates of Lamzouri [START_REF] Lamzouri | On the distribution of the maximum of cubic exponential sums[END_REF] and Kowalski-Sawin [START_REF] Kowalski | Kloosterman paths and the shape of exponential sums[END_REF] for the large deviations of M st .

Corollary 1.10. Let {X(h)} h∈Z be a sequence of I.I.D. random variables supported on [-N, N ] and satisfying Assumptions 3a and 3b above. For all V 1 we have ). There exists a constant B 1 such that for all real numbers B 1 ≤ V ≤ (2r/π)(log log p -2 log log log p) -B 1 we have

P(M X > V ) = exp -exp π N V + O(1
Φ F 1 (V ) = exp -exp π 2r V + O(1) .
Here B 1 and the implied constant depend only on r.

The next application concerns generalizations of the classical Kloosterman sums ([16, 7.12.3.1]).

Corollary 1.12. Let r ≥ 1 be an odd integer, and

F 2 = {ϕ (a,b) } (a,b)∈F × p ×F ×
p where ϕ (a,b) (n) = e p (bn + (an) r ). There exists a constant B 2 such that for all real numbers B 2 ≤ V ≤ ((r + 1)/π)(log log p -2 log log log p) -B 2 we have

Φ F 2 (V ) = exp -exp π r + 1 V + O(1)
.

Finally our last application concerns additive twists of hyper-Kloosterman sums. Recall that for an integer r ≥ 2, the r-th hyper-Kloosterman sum on F p is defined for

n ∈ F × p by Kl r (n; p) = (-1) r-1 p (r-1)/2 y 1 ,...,yr∈F × p y 1 •...•yr=n e p (y 1 + • • • + y r ) .
Corollary 1.13. Let r ≥ 3 be an odd integer, and

F 4 = {ϕ (a,b) } (a,b)∈F × p ×F ×
p where ϕ a,b (n) = Kl r (an; p)e p (bn). There exists a constant B 3 such that for all real numbers B 3 ≤ V ≤ ((r + 1)/π)(log log p -2 log log log p) -B 3 we have

Φ F 4 (V ) = exp -exp π r + 1 V + O(1)
.

Our method also works in the case where the Fourier transforms ϕ a are complex valued, but yields weaker estimates for Φ F in this case. This corresponds for example to certain families of -adic trace functions whose monodromy group is SL N (C) for some integer N ≥ 3 (since in the case N = 2 we have SL 2 (C) = Sp 2 (C)). In this case we need to change Assumption 3 to include all mixed moments of ϕ a (h 1 ), . . . , ϕ a (h k ) and their complex conjugates. We also assume that the {X(h)} h∈Z * are supported inside the disk {z ∈ C : |z| ≤ N }, and replace X by ReX in Assumption 3a. Then, given a family F = {ϕ a } a∈Ωm of m-periodic complex valued functions such that | ϕ a (h)| ≤ N , and F verifies (the new) Assumption 3 with η > 1, or Assumptions 1 and 3 with 1/2 < η ≤ 1, or Assumptions 1, 4, and 3 with η = 1/2, we can prove that in the range

B ≤ V ≤ (N/π)(log log m -2 log log log m) -B we have 1 exp -exp π N V + O(1) ≤ Φ F (V ) ≤ exp -exp π 2 4N V + O(1)
.

The plan of the paper is as follows. In the next section we present the key ingredients of the proof of the upper bound of Theorem 1.2, and show how to deduce this upper bound in each of the cases A), B) and C) assuming these results. In section 3 we prove Theorem 2.3 below, which shows that for almost all m-periodic functions in our families, the maximum of all partial sums is very close to the maximum of a "small number" of these sums. Section 4 will be devoted to the proof of Theorem 2.1 below, which provides a precise asymptotic formula for the maximum of a certain "random" exponential sum. In section 5, we collect several results on the probabilistic random model. Section 6 contains the proof of Theorem 2.2 below, which is the last ingredient of the proof of the upper bound of Theorem 1.2. In section 7, we prove Theorem 1.6. Section 8 contains the construction of the family F which satisfies Proposition 1.8. Finally, in section 9, we exhibit examples of families of -adic trace functions satisfying our assumptions, and prove Corollaries 1.11, 1.12 and 1.13.

Acknowledgements. We would like to thank the anonymous referees for carefully reading the paper and for their remarks and suggestions.

Proof of the upper bound in Theorem 1.2: Main ideas and key ingredients

Let {ϕ a } a∈Ωm be a family of m-periodic complex valued functions satisfying Assumptions 2 and 3. Recall that

M(ϕ a ) = max 0≤x<m 0≤n≤x ϕ a (n) .
1 In the case of families of trace functions whose arithmetic and geometric monodromy groups are both equal to SL N (C) for some odd integer N ≥ 3, the constant π/N should be replaced by the larger constant 2π/(N (1 + cos(π/N ))) in the lower bound for Φ F (V ), since the condition P(ReX < -N + ε) ε A in Assumption 3a is not satisfied in this case.

Using the discrete Plancherel formula (1.2) and the estimate (1.3) we obtain

M(ϕ a ) √ m = 1 2π max 0≤j≤m-1 1≤|h|<m/2 e m (jh) -1 h ϕ a (h) + O (1) .
Similarly as in [START_REF] Lamzouri | On the distribution of the maximum of cubic exponential sums[END_REF], we shall treat the Fourier transforms ϕ a (h) for small h as random values in [-N, N ]. This yields

(2.1) M(ϕ a ) √ m ≤ N 2π G(H) + 1 2π max 0≤j≤m-1 H<|h|<m/2 e m (jh) -1 h ϕ a (h) + O(1),
where H is a positive integer and

G(H) := max α∈[0,1) max (y -H ,...y -1 ,y 1 ,...,y H )∈[-1,1] 2H 1≤|h|≤H e(αh) -1 h y h .
One has the trivial bounds

(2.2) 2 log H + O(1) ≤ G(H) ≤ 4 log H + O(1),
where the upper bound follows from the trivial inequality |e(αh) -1| ≤ 2, and the lower bound follows by taking α = 1/2, y h = -1 if h > 0 and y h = 1 if h < 0. Using Fourier analytic techniques, the third author showed in [START_REF] Lamzouri | On the distribution of the maximum of cubic exponential sums[END_REF] that

G(H) ≤ 1 + 4 π log H + O(1),
and conjectured that the lower bound of (2.2) is closer to the true order of magnitude of G(H). In section 4 we shall prove a stronger form of this conjecture.

Theorem 2.1. Let H be a positive integer. Then, we have

G(H) = 2 log H + 2 log 2 + 2γ + O 1 H .
In order to prove the upper bound in Theorem 1.2, it remains to show that for large H, and for "most" a ∈ Ω m , the maximum of the sum | H<|h|<m/2 em(jh)-1 h ϕ a (h)| is "small". To this end we prove the following result in section 6.

Theorem 2.2. Let m be large, and k be an integer such that 10 5 N 2 < k ≤ (log m)/(50 log log m). Let {ϕ a } a∈Ωm be a family of m-periodic complex valued functions satisfying Assumptions 2 and 3. Let S be a non-empty subset of [0, 1), and put y = 10 5 N 2 k. Then we have

1 |Ω m | a∈Ωm max α∈S y≤|h|<m/2 e (αh) -1 h ϕ a (h) 2k e -2k + |S|(4C 1 log m) 8k m η .
In the case where {ϕ a } a∈Ωm satisfies Assumption 3 with η > 1, we can deduce the upper bound of Theorem 1.2 from Theorems 2.1 and 2.2.

Proof of the upper bound in case A) of Theorem 1.2. Let k ≤ (η-1) log m/(50 log log m) be a large positive integer to be chosen, and put H = 10 5 N 2 k. First, combining equation (2.1) with Theorem 2.1 we deduce that

M(ϕ a ) √ m ≤ N π log k + 1 2π max 0≤j≤m-1 H≤|h|<m/2 e m (jh) -1 h ϕ a (h) + C 0 ,
for some positive constant C 0 . We assume that V is sufficiently large and choose k = [C 2 exp(πV /N )], where

C 2 = exp(-π N (C 0 + 1 2π )). Therefore, appealing to Theorem 2.2 with S = {j/m : 0 ≤ j ≤ m -1} we obtain (2.3) Φ F (V ) ≤ 1 |Ω m |    a ∈ Ω m : max 0≤j≤m-1 H≤|h|<m/2 e m (jh) -1 h ϕ a (h) ≥ 1    ≤ 1 |Ω m | a∈Ωm max 0≤j≤m-1 H≤|h|<m/2 e m (jh) -1 h ϕ a (h) 2k e -2k + (4 log m) 10k m 1-η exp -C 2 exp π N V ,
as desired.

If {ϕ a } a∈Ωm satisfies Assumption 3 with η ≤ 1 (which corresponds to cases B) and C) of Theorem 1.2), then the above argument no longer works since |{j/m : 0 ≤ j ≤ m -1}| = m is too big. To overcome this problem, we shall suppose that our family satisfies Assumption 1, and use it to reduce the number of points j ≤ m -1 where the maximum of 0≤n≤j ϕ a (n) can occur. Let J ≤ √ m be a parameter to be chosen, and split the interval [0, m] into J intervals I j := [x j , x j+1 ] where for each j = 0, ..., J we put

x j := j J m.
We first consider case B) of Theorem 1.2 (where η ∈ (1/2, 1]) since it is easier.

Proof of the upper bound in case B) of Theorem 1.2. We choose J = √ m . For a ∈ Ω m , let r a be an integer in the interval [0, m) such that

M(ϕ a ) = 0≤n≤ra ϕ a (n) .
Then there exists 0 ≤ j ≤ J -1 such that r a ∈ [x j , x j+1 ], and hence

1 √ m 0≤n≤ra ϕ a (n) ≤ 1 √ m 0≤n≤x j ϕ a (n) + 1 √ m x j <n≤ra ϕ a (n) ≤ 1 √ m 0≤n≤x j ϕ a (n) + O(1), since max a∈Ωm ||ϕ a || 1 and |r a -x j | ≤ m/J √ m. This implies that M(ϕ a ) √ m = max 0≤j≤J-1 1 √ m 0≤n≤x j ϕ a (n) + O(1)
.

We now use the same argument leading up to (2.3) with the same choices of k ≤ (η -1/2) log m/(30 log log m) and H, but with S = {x j /m : 0 ≤ j ≤ J -1} (and perhaps a different choice for the constant C 0 ). This gives

Φ F (V ) ≤ 1 |Ω m | a∈Ωm max 0≤j≤J-1 H≤|h|<m/2 e m (x j h) -1 h ϕ a (h) 2k e -2k + (4 log m) 10k m 1/2-η exp -C 2 exp π N V .
The above argument fails if {ϕ a } a∈Ωm satisfies Assumption 3 with η = 1/2, which is the most interesting case of Theorem 1.2. In this case, to reduce the number of points of S further (below m 1/2-ε for some ε), we need power saving bounds for short sums x≤n≤x+h ϕ a (n) in the Pólya-Vinogradov range, which corresponds to h being of size around √ m. Unfortunately, such bounds are only known in very few cases (for example they are known for Birch sums but not for Kloosterman sums). To overcome this problem, we use Assumption 4 in order to obtain strong bounds for these short sums uniformly over all intervals I of length |I| ≤ m 1/2+δ/2 (intervals at the edge of the Pólya-Vinogradov range), in an average sense. In fact, it is this uniformity aspect (see Lemma 3.1 below) that allows us to obtain the upper bound of Theorem 1.2 in this case. Let α and δ be as in Assumption 4. As before we will split the interval [0, m] into J intervals I j := [x j , x j+1 ] where x j := j J m, and where we now choose J = m 1/2-δ/5 . We shall prove the following result in section 3.

Theorem 2.3. Let m be large and J = m 1/2-δ/5 . Let {ϕ a } a∈Ωm be a family of mperiodic complex valued functions satisfying Assumptions 1 and 4. There exists a set

E m ⊂ Ω m with |E m | ≤ m -δ/10 |Ω m | such that for all a ∈ Ω m \ E m we have M(ϕ a ) = max 0≤j≤J-1 0≤n≤x j ϕ a (n) + O m 1/2-δ/(8α
M(ϕ a ) √ m = 1 2π max 0≤j≤J-1 1≤|h|<m/2 e m (x j h) -1 h ϕ a (h) + O (1) .
Let k ≤ δ(log m)/(200 log log m) be a large positive integer to be chosen, and put

H = 10 5 N 2 k. First, combining equation (2.1) with Theorem 2.1, we deduce that if a ∈ Ω m \ E m we have M(ϕ a ) √ m ≤ N π log k + 1 2π max 0≤j≤J-1 H≤|h|<m/2 e m (x j h) -1 h ϕ a (h) + C 0 ,
for some positive constant C 0 . Repeating the same argument leading up to (2.3) with the same choice of k gives

Φ F (V ) ≤ 1 |Ω m |    a ∈ Ω m \ E m : max 0≤j≤J-1 H≤|h|<m/2 e m (x j h) -1 h ϕ a (h) ≥ 1    + O |E m | |Ω m | ≤ 1 |Ω m | a∈Ωm max 0≤j≤J-1 H≤|h|<m/2 e m (x j h) -1 h ϕ a (h) 2k + O m -δ/10 e -2k + (4 log m) 10k m -δ/10 exp -C 2 exp π N V .
3. Controlling short sums of periodic functions: Proof of Theorem

2.3

In order to prove Theorem 2.3, we will use Assumptions 1 and 4 to obtain a nontrivial upper bound for the α-th moment of the maximum over intervals I (with length up to a certain parameter L) of the short sum n∈I ϕ a (n). Lemma 3.1. Let m be large, and {ϕ a } a∈Ωm be a family of m-periodic complex valued functions satisfying Assumptions 1 and 4. For any real number

1 ≤ L ≤ m 1/2+δ/2 we have 1 |Ω m | a∈Ωm max |I|≤L 1 √ m n∈I ϕ a (n) α Lm -1/2-δ/2 + m -δ/4 ,
where the maximum is taken over all intervals

I = [x, y] ⊂ [0, m] with |I| ≤ L.
Proof. The intervals I = [x, y] with 0 ≤ x < y ≤ m, and |I| = y -x ≤ L can be parametrized by the set of points in the region of the plane delimited by the trapezoid

T L := {(x, y) ∈ R 2 : 0 ≤ x < y ≤ m, y ≤ x + L}. Let 0 < B ≤
√ m be a parameter to be chosen, and for any k, ∈ N we define S k, ,B := [kB, (k + 1)B) × [ B, ( + 1)B). The set of squares given by

{S k, ,B | S k, ,B ∩ T L = ∅} is a disjoint cover of T L of size N L,B := |{S k, ,B | S k, ,B ∩ T L = ∅}| A(T L ) B 2 + m B mL B 2 + m B , (3.1)
where A(D) denotes the area of D. For any a ∈ Ω m let us denote by

I a = [x a , y a ] an interval with |I a | ≤ L such that 1 √ m n∈Ia ϕ a (n) = max |I|≤L 1 √ m n∈I ϕ a (n) .
Then there exists k a , a ∈ N such that (x a , y a ) ∈ S ka, a,B . Hence

1 √ m n∈Ia ϕ a (n) = 1 √ m kaB≤n≤ aB ϕ a (n) + O x a -k a B + y a -a B √ m = 1 √ m kaB≤n≤ aB ϕ a (n) + O B √ m ,
by Assumption 1. Using this estimate together with the elementary inequality

|x+y| α ≤ (2 max(|x|, |y|)) α ≤ 2 α (|x| α + |y| α ) we get 1 |Ω m | a∈Ωm max |I|≤L 1 √ m n∈I ϕ a (n) α = 1 |Ω m | a∈Ωm 1 √ m kaB≤n≤ aB ϕ a (n) + O B √ m α 1 |Ω m | a∈Ωm 1 √ m kaB≤n≤ aB ϕ a (n) α + B α m α/2 .
Furthermore, observe that

1 |Ω m | a∈Ωm 1 √ m kaB≤n≤ aB ϕ a (n) α ≤ 1 |Ω m | a∈Ωm k, ∈N: S k, ,B ∩T L =∅ 1 √ m kB≤n≤ B ϕ a (n) α = k, ∈N: S k, ,B ∩T L =∅ 1 |Ω m | a∈Ωm 1 √ m kB≤n≤ B ϕ a (n) α m -1/2-δ N L,B .
by Assumption 4, since B ≤ m 1/2 . Therefore, we deduce from (3.1) that

1 |Ω m | a∈Ωm max |I|≤L 1 √ m n∈I ϕ a (n) α Lm 1/2-δ B 2 + m 1/2-δ B + B α m α/2 .
Choosing B = m 1/2-δ/4 gives the result.

Proof of Theorem 2.3. It only suffices to prove the implicit upper bound, since one trivially has

M(ϕ a ) ≥ max 1≤j≤J-1 0≤n≤x j ϕ a (n) .
Let L = m 1/2+δ/4 and define E m to be the set of elements a ∈ Ω m such that max

|I|≤L 1 √ m n∈I ϕ a (n) > m -δ/(8α) .
Then, it follows from Lemma 3.1 that

|E m | |Ω m | ≤ m δ 8 |Ω m | a∈Ωm max |I|≤L 1 √ m n∈I ϕ a (n) α m -δ/8 .
Moreover, for a ∈ Ω m , let r a be an integer in the interval [0, m) such that

M(ϕ a ) = 0≤n≤ra ϕ a (n) .
Then there exists 0 ≤ j ≤ J -1 such that r a ∈ [x j , x j+1 ], and hence

1 √ m 0≤n≤ra ϕ a (n) ≤ 1 √ m 0≤n≤x j ϕ a (n) + 1 √ m x j <n≤ra ϕ a (n) .
Recall that J = m 1/2-δ/5 , and hence r a -

x j ≤ x j+1 -x j = m/J ≤ L if m is large enough. Therefore, we deduce that if a ∈ Ω m \ E m then 1 √ m x j <n≤ra ϕ a (n) ≤ m -δ/(8α) .
This implies

M(ϕ a ) √ m ≤ max 1≤j≤J-1 1 √ m 0≤n≤x j ϕ a (n) + O m -δ/(8α) ,
for all a ∈ Ω m \ E m , completing the proof.

4. An asymptotic estimate for the maximum of a random sum: Proof of Theorem 2.1

Recall that

G(H) = max α∈[0,1] max (x h ) 1≤|h|≤H ∈[-1,1] 2H 1≤|h|≤H e(αh) -1 h x h .
We shall deduce Theorem 2.1 from the following result, which is an exact formula for G(H) when H is odd.

Proposition 4.1. If H is an odd positive integer, then

G(H) = 2 H h=1 1 -(-1) h h .
To prove this result, we need the following lemma.

Lemma 4.2. Let α be a real number. If H ≥ 1 is odd, then H h=1 sin 2 (παh) h ≤ H h=1 1 -(-1) h 2h .
Proof. Since sin 2 (π(1 -α)h) = sin 2 (παh) we may assume that α ∈ [0, 1/2]. Let g : [0, 1/2] → R be defined by

g(t) := cos(2πtH) 4H + H h=1 sin 2 (πth) h = cos(2πtH) 4H + H h=1 1 -cos(2πth) 2h .
Since g is differentiable and

g (t) = - π 2 sin(2πtH) + π H h=1 sin(2πth) = π -sin(πtH) cos(πtH) + sin(πtH) sin(πt(H + 1)) sin(πt) = π sin 2 (πtH) cos(πt) sin(πt) ≥ 0,
we deduce that g is increasing on [0, 1/2]. This implies that for all α ∈ [0, 1/2] we have

H h=1 sin 2 (παh) h ≤ g(1/2)- cos(2παH) 4H = H h=1 1 -(-1) h 2h - cos(2παH) + 1 4H ≤ H h=1 1 -(-1) h 2h ,
as desired.

Proof of Proposition 4.1. The lower bound follows easily by taking α = 1/2, x h = -1 if h > 0 and x h = 1 if h < 0. Let us now show the upper bound. Let α ∈ R and

(x h ) 1≤|h|≤H ∈ [-1, 1] 2H . Put S = 1≤|h|≤H e(αh) -1 h x h and S 0 = H h=1 sin 2 (παh) h .
On one hand, we have the relation

Im(S) = 2 H h=1 sin(παh) cos(παh) x h + x -h h .
Moreover, using the Cauchy-Schwarz inequality we get

Im(S) 2 ≤ 4 H h=1 sin 2 (παh) h |x h + x -h | H h=1 cos 2 (παh) h |x h + x -h | .
On the other hand, we have

Re(S) = 2 H h=1 sin 2 (παh) h (x -h -x h ). Observe that |x h -x -h | + |x h + x -h | ≤ 2. This implies the upper bound |Re(S)| ≤ 4S 0 -2 H h=1 sin 2 (παh) h |x h + x -h |.
We are now ready to estimate |S| 2 = Re(S) 2 + Im(S) 2 . We infer

|S| 2 ≤ 16S 2 0 -16S 0 H h=1 sin 2 (παh) h |x h + x -h | + 4 H h=1 sin 2 (παh) h |x h + x -h | H h=1 |x h + x -h | h ≤ 16S 2 0 + 8 H h=1 sin 2 (παh) h |x h + x -h | H h=1 1 h -2S 0 .
To finish the proof, let us study two cases:

i) If 2S 0 ≥ H h=1 1 h , then |S| 2 ≤ 16S 2 0
and we conclude by applying Lemma 4.2.

ii)

If 2S 0 ≤ H h=1 1 h , then |S| 2 ≤ 16S 2 0 + 16S 0 H h=1 1 h -2S 0 ≤ 4 H h=1 1 h 2 ≤ 2 H h=1 1 -(-1) h h 2 .
Whence the result.

We end this section by deducing Theorem 2.1.

Proof of Theorem 2.1. If H ≥ 1 is odd, the desired asymptotic follows directly from Proposition 4.1, so it only remains to prove the result when H is even. To this end, we observe that if k ≥ 1 is an integer, then we have

G(k + 1) = max α∈[0,1] max (x h ) 1≤|h|≤k+1 ∈[-1,1] 2k+2 1≤|h|≤k+1 e(αh) -1 h x h ≥ G(k),
which follows by taking x k+1 = x -k-1 = 0. Hence it follows from Proposition 4.1 applied to G(H -1) and G(H + 1), together with the inequality

G(H -1) ≤ G(H) ≤ G(H + 1) that G(H) = 2 H h=1 1 -(-1) h h + O 1 H = 2 log H + 2 log 2 + 2γ + O 1 H ,
as desired.

Remark 4.3. Using the same method of proof as in Proposition 4.1, we can in fact obtain the following exact formula for G(H) when H is even

G(H) = 2 H h=1 1 h 1 -(-1) h cos πh H + 1 .

Investigating the probabilistic random model

Let {X(h)} h∈Z * be a sequence of independent random variables supported on [-N, N ] and satisfying Assumptions 3a and 3b above. In this section we shall study the moments and the moment generating function of the sum of random variables y≤|h|<z c(h)X(h), where c(h) are certain complex numbers such that c(h) 1/|h| for |h| ≥ 1. It follows from the results of section 9 below that the families of -adic trace functions we consider in Corollaries 1.11, 1.12 and 1.13 satisfy Assumption 3, where the random variables X(h) are distributed like the traces of random matrices on the compact classical group USp 2r . At the end of this section we will show that these random variables satisfy Assumptions 3a and 3b.

The moments of y≤|h|<z c(h)X(h).

The purpose of this section is to prove the following lemma, which is a generalization of Lemma 3.1 of [START_REF] Lamzouri | On the distribution of the maximum of cubic exponential sums[END_REF].

Lemma 5.1. Let X(h) be a sequence of I.I.D. random variables satisfying Assumption 3b above. Let {c(h)} h∈Z * be a sequence of complex numbers such that |c(h)| ≤ c 0 /|h|, where c 0 is a positive constant. Let 1 ≤ y < z be real numbers. Then, for all integers k ≥ 1 we have

(5.1) E    y≤|h|<z c(h)X(h) k    ≤ 8(c 0 N ) 2 k y k/2 . Moreover, if k > y then (5.2) E    y≤|h|<z c(h)X(h) k    ≤ (10c 0 N log k) k .
Proof. We first prove (5.1) when k = 2n is even. Expanding the moments we obtain

(5.3) E   y≤|h|<z c(h)X(h) 2n   ≤ c 2n 0 y≤|h 1 |,...,|h 2n |<z |E (X(h 1 ) • • • X(h 2n ))| |h 1 • • • h 2n | .
By the independence of the {X(h)} and Assumption 3b, we get (5.4)

y≤|h 1 |,...,|h 2n |<z |E (X(h 1 ) • • • X(h 2n ))| |h 1 • • • h 2n | = 2n =1 j 1 <•••<j y≤|j 1 |,...,|j |<z n 1 ,...,n ≥1 n 1 +•••+n =2n 2n n 1 , . . . , n |E(X(j 1 ) n 1 )| • • • |E(X(j ) n )| |j n 1 1 • • • j n | ≤ N 2n n =1 j 1 <•••<j y≤|j 1 |,...,|j |<z r 1 ,...,r ≥1 r 1 +•••+r =n 2n 2r 1 , . . . , 2r 1 j 2r 1 1 • • • j 2r ,
where we have used that E(X(h) m ) = 0 if m is odd, and

|E(X(h) m )| ≤ N m if m is even, since |X(h)| ≤ N for all h. Furthermore, observe that 2n 2r 1 , . . . , 2r ≤ 2n! n! n r 1 , . . . , r ≤ (2n) n n r 1 , . . . , r .
Inserting this bound in (5.4) gives

y≤|h 1 |,...,|h 2n |<z |E (X(h 1 ) • • • X(h 2n ))| |h 1 • • • h 2n | ≤ (2N 2 n) n   y≤|j|<z 1 j 2   n .
Therefore, in view of (5.3) and the elementary inequality y≤|j|<z 1/j 2 ≤ 4/y we deduce that (5.5)

E   y≤|h|<z c(h)X(h) 2n   ≤ 8(c 0 N ) 2 n y n .
We now establish (5.1) when k is odd. By the Cauchy-Schwarz inequality and (5.5) we have

E    y≤|h|<z c(h)X(h) k    ≤ E    y≤|h|<z c(h)X(h) 2k    1/2 ≤ 8(c 0 N ) 2 k y k/2
, as desired. We now prove (5.2). By (5.1) and Minkowski's inequality we have

E    y≤|h|<z c(h)X(h) k    1/k ≤ E    y≤|h|<k c(h)X(h) k    1/k + E    k≤|h|<z c(h)X(h) k    1/k ≤ c 0 N y≤|h|<k 1 |h| + √ 8c 0 N ≤ 10c 0 N log k.
This completes the proof.

The moment generating function of a sum involving the X(h).

In this section we shall estimate the moment generating function of the sum of random variables

-m/2<h≤m/2 h =0 γ m (h)X(h)
, where the γ m (h) are defined by

γ m (h) =: - 1 m Im 0≤n≤m/2 e m (nh) .
This is in fact the probabilistic random model corresponding to the imaginary part of the partial sum 0≤n≤x ϕ a (n) when x = m/2. Indeed, by (1.2) we have

(5.6) 1 √ m Im 0≤n≤m/2 ϕ a (n) = -m/2<h≤m/2 h =0 γ m (h) ϕ a (h), since γ m (0) = 0. For s ∈ C we define L X (s) := E exp s • -m/2<h≤m/2 h =0 γ m (h)X(h) .
We prove the following proposition, which generalizes Proposition 3.2 of [START_REF] Lamzouri | On the distribution of the maximum of cubic exponential sums[END_REF], and will be used to prove the lower bound of Theorem 1.2 in section 7.

Proposition 5.2. Let m be a large integer and 2 ≤ s ≤ m 1/3 be a real number. Then we have

L X (s) = exp N π s log s + B 0 s + O log 2 s ,
where

B 0 = N π γ + log 2 -log π + 1 2N ∞ -∞ f X (u) u 2 du .
To prove this result we need the following lemma.

Lemma 5.3. Let X be a random variable with values in [-N, N ], such that E(X) = 0 and X satisfies Assumption 3a. Let f X be the function defined in (1.9). Then we have the following estimates

(5.7) f X (t) t 2 if |t| < 1, log(2|t|) if |t| ≥ 1, and
(5.8) f X (t)    |t| if |t| < 1, log(2|t|) |t| if |t| > 1.
Proof of Lemma 5.3. We start by proving (5.7). If |t| ≤ 1, we use the Taylor expansion

E(e tX ) = E(1 + tX + O(t 2 X 2 )) = 1 + O(t 2
) since E(X) = 0 and |X| ≤ N . This implies the desired estimate for f X (t) when |t| ≤ 1. We now suppose that |t| > 1. We will only prove the result when t > 1, since the proof in the case t < -1 is similar. Let ε > 0 be a parameter to be chosen. Then we have P(X > N -ε)e t(N -ε) ≤ E(e tX ) ≤ e tN .

Choosing ε = 1/(2t) and using Assumption 3a we obtain (5.9) e tN (2t) A E(e tX ) ≤ e tN , from which the desired estimate for f X (t) follows in this case. Next, we establish (5.8). Note that f X is differentiable on R \ {-1, 1} and we have

(5.10) f X (t) := E(Xe tX ) E(e tX ) +      0 if |t| < 1, -N if t > 1, N if t < -1.
As before, in the case |t| < 1 the estimate of f X (t) follows from the Taylor expansions

E(e tX ) = 1 + O(t 2 ) and E(Xe tX ) = E(X + tX 2 + O(t 2 |X 3 |)) = tE(X 2 ) + O(t 2 ).
We now suppose that t > 1, and let δ > 0 be a parameter to be chosen. Let A be the event X > N -δ, and A c be its complement. Then we have

E(Xe tX ) = E(1 A • Xe tX ) + E(1 A c • Xe tX ) ≥ (N -δ)E(1 A • e tX ) + O(e t(N -δ) ).
where 1 B denotes the indicator function of an event B. Hence, using that E(1 A c • e tX ) ≤ e t(N -δ) we deduce (5.11) E(Xe tX ) ≥ (N -δ)E(e tX ) + O(e t(N -δ) ).

We choose δ = (A + 1)(log 2t)/t. Then, it follows from (5.9) that e t(N -δ) = e tN (2t) A+1

E(e tX ) t .

Inserting this estimate in (5.11), and using the bound X ≤ N gives

N -C log(2t) t ≤ E(Xe tX ) E(e tX )
≤ N, for some positive constant C which depends only on A. This implies the desired estimate for f X in this case. The proof in the case t < -1 follows along the same lines.

Proof of Proposition 5.2. First, note that for -m/2 < h ≤ m/2 with h = 0 we have (5.12)

|γ m (h)| = Im e m h m 2 + 1 -1 m (e m (h) -1) ≤ 1 m| sin(πh/m)| ≤ 1 2|h|
, since sin(πα) ≥ 2α for 0 ≤ α ≤ 1/2. Furthermore, it follows from (1.3) that (5.13)

γ m (h) = Im 1 -e πih 2πih + O 1 m = O( 1 m ) if h is even, -1 πh + O( 1 m ) if h is odd. By the independence of the X(h) we have log L X (s) = -m/2<h≤m/2 h =0 log E exp (s • γ m (h)X(h)) .
Using the estimate (5.13) and Lemma 5.3 we obtain

-m/2<h≤m/2 h =0 is even log E exp (s • γ m (h)X(h)) -m/2<h≤m/2 h =0 is even s 2 m 2 1 m 1/3 .
We now restrict ourselves to the case h = 2k + 1 is odd. First, it follows from (5.12) and Lemma 5.3 that

|k|>s 2 log E exp (s • γ m (2k + 1)X(2k + 1)) |k|>s 2 s 2 k 2 1.
Moreover, when |k| ≤ s 2 we use (5.13) to get

log E exp (s • γ m (2k + 1)X(2k + 1)) = log E exp - s (2k + 1)π X(2k + 1) +O s m .
Combining these estimates, and using Lemma 5.3 we obtain

(5.14) log L X (s) = 2N π s 1≤2k+1≤s/π 1 2k + 1 + -s 2 ≤k≤s 2 f X - s (2k + 1)π + O(1).
Next, we observe that 1≤2k+1≤s/π

1 2k + 1 = 1 2 1≤k≤s/2π 1 k +log 2+O 1 s = log s 2 + 1 2 (γ + log 2 -log π)+O 1 s .
Furthermore, by partial summation and Lemma 5.3 we get

-s 2 ≤k≤s 2 f X - s (2k + 1)π = -1 -s 2 f X - s (2u + 1)π du + s 2 0 f X - s (2u + 1)π du + O(log 2 s).
Finally, making the change of variables v = -s/((2u + 1)π), the main term on the right hand side of this estimate becomes whence E(X ) = 0. In the same way, we have P(X > N -ε) = P(X < -N + ε) for every ε > 0. Let us now verify Assumption 3a.

s 2π -s/((2s 2 +1)π) -s/π f X (v) v 2 dv + s 2π s/π s/((2s 2 -1)π) f X (v) v 2 dv = s 2π ∞ -∞ f X (v) v 2 dv + O(log
Lemma 5.4. There exists a positive real number c n such that for every ε ∈ (0, 2], one has

P(X > N -ε) ≥ c n ε n(2n+1)/2 . Proof. Put A = θ = (θ 1 , • • • , θ n ) ∈ [0, π] n n h=1 2 cos θ h > N -ε = θ ∈ [0, π] n n h=1 sin 2 θ h 2 < ε 4 and B = {t ∈ R n + | t 2 1 + • • • + t 2 n < 1}.
The Weyl integration formula (see for example page 117 of [START_REF] Conrey | Notes on eigenvalue distributions for the classical compact groups[END_REF]) gives

P(X > 2n -ε) = 2 n 2 n!π n A 1≤j<k≤n (cos θ k -cos θ j ) 2 n h=1 sin 2 θ h dθ 1 • • • dθ n . Let us remark that if θ ∈ A then n h=1 cos 2 θ h 2 = n h=1 1 -sin 2 θ h 2 ≥ 1 - n h=1 sin 2 θ h 2 > 1 - ε 4 .
We infer that

P(X > N -ε) = 2 n(2n+1) n!π n A j<k sin 2 θ j 2 -sin 2 θ k 2 2 n h=1 sin 2 θ h 2 cos 2 θ h 2 dθ 1 • • • dθ n ≥ 2 n(2n+1) n!π n 1 - ε 4 A j<k sin 2 θ j 2 -sin 2 θ k 2 2 n h=1 sin 2 θ h 2 cos θ h 2 dθ 1 • • • dθ n = 2 n ε n(2n+1)/2 n!π n 1 - ε 4 B 1≤j<k≤n (t 2 j -t 2 k ) 2 n h=1 t 2 h dt 1 • • • dt n ,
where we use the change of variables

t h = 2 √ ε sin θ h 2 .
Whence the result.

6.

Completing the proof of the upper bound in Theorem 1.2: Proof of Theorem 2.2

In this section, we assume that F = {ϕ a } a∈Ωm is a family of m-periodic complex valued functions satisfying Assumptions 2 and 3. We start by proving the following lemma which follows from combining Assumption 3 with Lemma 5.1. Lemma 6.1. Let m be a large positive integer, and 1 ≤ y < z ≤ m/2 be real numbers. Let {ϕ a } a∈Ωm be a family of m-periodic complex valued functions satisfying Assumptions 2 and 3. Let {c(h)} h∈Z * be a sequence of complex numbers such that |c(h)| ≤ c 0 /|h|, where c 0 is a positive constant. Then, for all positive integers k ≤ (log m)/(5 log log m) we have

1 |Ω m | a∈Ωm y≤|h|<z c(h) ϕ a (h) 2k 16(c 0 N ) 2 k y k + (4C 1 c 0 log m) 2k m η .
Proof. Expanding the moments and using Assumptions 2 and 3, we obtain

1 |Ω m | a∈Ωm y≤|h|<z c(h) ϕ a (h) 2k = y≤|h 1 |,...,|h k |<z y≤|r 1 |,...,|r k |<z c(h 1 ) • • • c(h k )c(r 1 ) • • • c(r k ) 1 |Ω m | a∈Ωm k u=1 ϕ a (h u ) k v=1 ϕ a (r v ) = y≤|h 1 |,...,|h k |<z y≤|r 1 |,...,|r k |<z c(h 1 ) • • • c(h k )c(r 1 ) • • • c(r k ) E k u=1 X(h u ) k v=1 X(r v ) + E k (y, z),
where the error term satisfies

E k (y, z) C 2k 1 m η y≤|h|<z |c(h)| 2k ≤ C 2k 1 m η y≤|h|<z c 0 |h| 2k (4C 1 c 0 log m) 2k m η ,
by Assumption 3. The result follows upon noting that

y≤|h 1 |,...,|h k |<z y≤|r 1 |,...,|r k |<z c(h 1 ) • • • c(h k )c(r 1 ) • • • c(r k ) E k u=1 X(h u ) k v=1 X(r v ) = E    y≤|h|<z c(h)X(h) 2k    ≤ 16(c 0 N ) 2 k y k ,
by Lemma 5.1.

We will deduce Theorem 2.2 from the following results, which generalize Propositions 6.1 and 6.2 of [START_REF] Lamzouri | On the distribution of the maximum of cubic exponential sums[END_REF]. In both results we assume that {ϕ a } a∈Ωm is a family of m-periodic complex valued functions satisfying Assumptions 2 and 3. Proposition 6.2. Let m be large, and k be an integer such that 10 5 N 2 < k ≤ (log m)/(5 log log m). Let S be a non-empty subset of [0, 1), and put y = 10 5 N 2 k. Then we have

1 |Ω m | a∈Ωm max α∈S y≤|h|<k 2 e (αh) -1 h ϕ a (h) 2k e -4k .
Proposition 6.3. Let m be a large positive integer, and k be an integer such that 3 ≤ k ≤ (log m)/(50 log log m). Let S be a non-empty finite subset of [0, 1). Then we have

1 |Ω m | a∈Ωm max α∈S k 2 ≤|h|<m/2 e (αh) -1 h ϕ a (h) 2k e -4k + |S|(2C 1 log m) 8k m η .
We start by proving Proposition 6.2, as its proof is simpler since the inner sum over |h| is short.

Proof of Proposition 6.2.

Let A k = {b/k 4 : 1 ≤ b ≤ k 4 }.
Then for all α ∈ S, there exists

β α ∈ A k such that |α -β α | ≤ 1/k 4 .
In this case we have e(αh) = e(β α h) + O(h/k 4 ), and hence

y≤|h|<k 2 e (αh) -1 h ϕ a (h) = y≤|h|<k 2 e(β α h) -1 h ϕ a (h) + O 1 k 2 .
Therefore, using the elementary inequality |x + y| 2k ≤ 2 2k (|x| 2k + |y| 2k ) we deduce that (6.1)

max α∈S y≤|h|<k 2 e (αh) -1 h ϕ a (h) 2k ≤ 2 2k max α∈A k y≤|h|<k 2 e (αh) -1 h ϕ a (h) 2k + c 1 k 2 2k ≤ 2 2k α∈A k y≤|h|<k 2 e (αh) -1 h ϕ a (h) 2k + c 1 k 2 2k
, for some positive constant c 1 . Thus, it follows from Lemma 6.1 that in this case we have (6.2)

1 |Ω m | a∈Ωm max α∈S y≤|h|<k 2 e (αh) -1 h ϕ a (h) 2k ≤ 2 2k α∈A k 1 |Ω m | a∈Ωm y≤|h|<k 2 e (αh) -1 h ϕ a (h) 2k + c 1 k 2 2k k 4 2 2k 64N 2 k y k + (8C 1 log m) 2k m η + c 1 k 2 2k e -4k ,
which completes the proof.

Proof of Proposition 6.3. Since the inner sum over |h| is long in this case, we shall split it into dyadic intervals. Let J 1 = log(k 2 )/ log 2 and J 2 = log(m/2)/ log 2 . We define z J 1 := k 2 , z J 2 +1 := m/2, and z j := 2 j for J 1 + 1 ≤ j ≤ J 2 . Then, using Hölder's inequality we obtain (6.3)

k 2 ≤|h|<m/2 e (αh) -1 h ϕ a (h) 2k = J 1 ≤j≤J 2 1 j 2 •   j 2 z j ≤|h|<z j+1 e (αh) -1 h ϕ a (h)   2k ≤ J 1 ≤j≤J 2 1 j 4k/(2k-1) 2k-1    J 1 ≤j≤J 2 j 4k z j ≤|h|<z j+1 e (αh) -1 h ϕ a (h) 2k    ≤ c 2 log k 2k+1 J 1 ≤j≤J 2 j 4k z j ≤|h|<z j+1 e (αh) -1 h ϕ a (h) 2k ,
for some constant c 2 > 0. Therefore, this reduces the problem to bounding the corresponding moments over each dyadic interval [z j , z j+1 ], namely

1 |Ω m | a∈Ωm max α∈S z j ≤|h|<z j+1 e (αh) -1 h ϕ a (h) 2k .
We shall consider two cases, depending on whether j is large in terms of |S|. First, if 4 j ≥ |S| then by Lemma 6.1 we have (6.4)

1 |Ω m | a∈Ωm max α∈S z j ≤|h|<z j+1 e (αh) -1 h ϕ a (h) 2k ≤ α∈S 1 |Ω m | a∈Ωm z j ≤|h|<z j+1 e (αh) -1 h ϕ a (h) 2k 4 j 64N 2 k 2 j k + |S|(8C 1 log m) 2k m η .
since z j ≥ 2 j for J 1 ≤ j ≤ J 2 . We now suppose that 4 j < |S|, and let B j = {b/4 j : 1 ≤ b ≤ 4 j }. Then for all α ∈ S there exists β α ∈ B j such that |α -β α | ≤ 1/4 j . In this case we have e(αh) = e(β α h) + O(h/4 j ), and hence we obtain

z j ≤|h|<z j+1 e (αh) -1 h ϕ a (h) = z j ≤|h|<z j+1 e(β α h) -1 h ϕ a (h) + O 1 2 j ,
since z j+1 z j 2 j . Therefore, similarly to (6.1) we derive max

α∈S z j ≤|h|<z j+1 e (αh) -1 h ϕ a (h) 2k ≤ 2 2k max α∈B j z j ≤|h|<z j+1 e (αh) -1 h ϕ a (h) 2k + c 3 2 j 2k ,
for some positive constant c 3 . Thus, appealing to Lemma 6.1 we get (6.5)

1 |Ω m | a∈Ωm max α∈S z j ≤|h|<z j+1 e (αh) -1 h ϕ a (h) 2k ≤ 2 2k α∈B j 1 |Ω m | a∈Ωm z j ≤|h|<z j+1 e (αh) -1 h ϕ a (h) 2k + c 3 2 j 2k 4 j 2 8 N 2 k 2 j k + |S|(16C 1 log m) 2k m η , since |B j | = 4 j < |S|.
Combining (6.4) and (6.5) we deduce that in all cases we have

1 |Ω m | a∈Ωm max α∈S z j ≤|h|<z j+1 e (αh) -1 h ϕ a (h) 2k 4 j 2 8 N 2 k 2 j k + |S|(16C 1 log m) 2k m η .
Inserting this bound in (6.3) gives (6.6)

1 |Ω m | a∈Ωm max α∈S k 2 ≤|h|<m/2 e (αh) -1 h ϕ a (h) 2k c 4 log k 2k+1 k k J 1 ≤j≤J 2 4 j j 4 2 j k + |S|(2C 1 log m) 8k m η e -4k + |S|(2C 1 log m) 8k m η ,
for some positive constant c 4 , where the last estimate follows since j 4 ≤ 2 j/4 for j large enough, and 2 J 1 k 2 . This completes the proof.

Finally, we deduce Theorem 2.2.

Proof of Theorem 2.2. By Minkowski's inequality we have

   a∈Ωm max α∈S y≤|h|<m/2 e (αh) -1 h ϕ a (h) 2k    1/2k ≤    a∈Ωm max α∈S y≤|h|<k 2 e (αh) -1 h ϕ a (h) 2k    1/2k +    a∈Ωm max α∈S k 2 ≤|h|<m/2 e (αh) -1 h ϕ a (h) 2k    1/2k
.

The result follows upon using Propositions 6.2 and 6.3.

Proof of Theorem 1.6

In this section we shall investigate the distribution of the partial sums 0≤n≤x ϕ a (n) in the special case x = m/2, where F = {ϕ a } a∈Ωm is a family of m-periodic complex valued functions satisfying Assumptions 2 and 3. For a real number t, we define

(7.1) Ψ F (t) := 1 |Ω m | a ∈ Ω m : 1 √ m Im 0≤n≤m/2 ϕ a (n) > t ,
and similarly we write Ψ - F (t) for the proportion of a ∈ Ω m such that 1 √ m Im 0≤n≤m/2 ϕ a (n) < -V . We will prove the following result from which Theorem 1.6 follows.

Theorem 7.1. Let m be large and F = {ϕ a } a∈Ωm be a family of m-periodic complex valued functions satisfying Assumptions 2 and 3. Uniformly for V in the range 1 ≤ V ≤ N π (log log m -2 log log log m -B) we have

Ψ F (V ) = exp -A 0 exp π N V 1 + O V e -πV /(2N ) .
Furthermore, in the same range of V we also have

Ψ - F (V ) = exp -A 0 exp π N V 1 + O V e -πV /(2N ) .
Recall from (5.6) that

1 √ m Im 0≤n≤m/2 ϕ a (n) = -m/2<h≤m/2 h =0 γ m (h) ϕ a (h).
In order to prove Theorem 7. 2 we have

1 |Ω m | a∈Ωm\Em exp     s • -m/2<h≤m/2 h =0 γ m (h) ϕ a (h)     = L X (s) + O exp - log m 20 log log m . Proof. Let E m be the set of a ∈ Ω m such that -m/2<h≤m/2 h =0 γ m (h) ϕ a (h) ≥ 4N log log m.
Using Assumption 2 together with the bound (5.12) we get

-m/2<h≤m/2 h =0 γ m (h) ϕ a (h) ≤ 3N log log m + (log m) 2 <|h|<m/2 γ m (h) ϕ a (h) ,
if m is sufficiently large. Therefore, it follows from Lemma 6.1 that for r = log m/(10 log log m) we have

(7.2) |E m | ≤ a ∈ Ω m : (log m) 2 <|h|<m/2 γ m (h) ϕ a (h) ≥ N log log m ≤ (N log log m) -2r a∈Ωm (log m) 2 <|h|<m/2 γ m (h) ϕ a (h) 2r m -1/10 |Ω m |.
Let L = log m/(20 log log m) . Then we have

(7.3) 1 |Ω m | a∈Ωm\Em exp     s • -m/2<h≤m/2 h =0 γ m (h) ϕ a (h)     = L k=0 s k k! 1 |Ω m | a∈Ωm\Em     -m/2<h≤m/2 h =0 γ m (h) ϕ a (h)     k + E 1 where E 1 k>L |s| k k! (4N log log m) k ≤ k>L 15N |s| log log m L k e -L
by Stirling's formula and our assumption on s. Furthermore, note that

-m/2<h≤m/2 h =0 |γ m (h) ϕ a (h)| ≤ N 2 1≤|h|≤m/2 1 |h| ≤ 3N log m,
if m is sufficiently large. Therefore, it follows from equation (7.2) that for all integers 0 ≤ k ≤ L we have

(7.4) 1 |Ω m | a∈Ωm\Em     -m/2<h≤m/2 h =0 γ m (h) ϕ a (h)     k = 1 |Ω m | a∈Ωm     -m/2<h≤m/2 h =0 γ m (h) ϕ a (h)     k + O m -1/10 (3N log m) k = E     -m/2<h≤m/2 h =0 γ m (h)X(h) k     + O m -1/25 ,
where the last equality follows from expanding the moments and using Assumption 3 as in the proof of Lemma 6.1. Furthermore, it follows from equation (5.12), Lemma 5.1 and Stirling's formula that

k>L |s| k k! E     -m/2<h≤m/2 h =0 γ m (h)X(h) k     k>L 15N |s| log k k k k>L 15N |s| log L L k e -L .
Finally, combining this bound with (7.3) and (7.4), we derive

1 |Ω m | a∈Ωm\Em exp     s • -m/2<h≤m/2 h =0 γ m (h) ϕ a (h)     = L k=0 s k k! E     -m/2<h≤m/2 h =0 γ m (h)X(h) k     + O e -L + m -1/25 e |s| = L X (s) + O e -L ,
as desired.

Using the saddle-point method and Propositions 5.2 and 7.2, we prove Theorem 7.1.

Proof Theorem 7.1. Let E m be the set in the statement of Proposition 7.2, and Ψ F (t) be the proportion of

a ∈ Ω m \ E m such that -m/2<h≤m/2 h =0 γ m (h) ϕ a (h) > t.
Then, it follows from equation (5.6) and Proposition 7.2 that

Ψ F (t) = Ψ F (t) + O m -1/10 .
Furthermore, it follows from Propositions 7.2 and 5.2 that for all positive real numbers s such that 2N ≤ N s ≤ (log m)/(50 log log m) 2 we have

(7.5) ∞ -∞ e st Ψ F (t)dt = 1 |Ω m | a∈Ωm\Em -m/2<h≤m/2 h =0 γm(h) ϕa(h) -∞ e st dt = 1 s|Ω m | a∈Ωm\Em exp     s • -m/2<h≤m/2 h =0 γ m (h) ϕ a (h)     = exp N π s log s + B 0 s + O(log 2 s) .
The result trivially holds if V is small, so we might assume that V is a sufficiently large real number such that V ≤ (N/π)(log log m -2 log log log m -B), where B = log(N/π) + 8 -B 0 π/N . We shall choose s (the saddle point) such that

(7.6) N π s log s + B 0 s -sV = 0 ⇐⇒ s = exp π N V - π N B 0 -1 .
Let 0 < ε < 1 be a small parameter to be chosen, and put S = se ε . Then, it follows from (7.5) that

∞ V +N ε/π e st Ψ F (t)dt ≤ exp (s(1 -e ε )(V + N ε/π)) ∞ V +N ε/π e St Ψ F (t)dt ≤ exp s(1 -e ε )(V + N ε/π) + N π se ε log s + N π se ε ε + B 0 se ε + O(log 2 s) = exp N π s log s + B 0 s + N π s(1 + ε -e ε ) + O(log 2 s) .
Therefore, choosing ε = C 0 (log s)/ √ s for a suitably large constant C 0 and using (7.5) we obtain

∞ V +N ε/π e st Ψ F (t)dt ≤ e -V 2 ∞ -∞ e st Ψ F (t)dt.
A similar argument shows that

V -N ε/π -∞ e st Ψ F (t)dt ≤ e -V 2 ∞ -∞ e st Ψ F (t)dt.
Combining these bounds with (7.5) gives (7.7)

V +N ε/π V -N ε/π e st Ψ F (t)dt = exp N π s log s + B 0 s + O(log 2 s) .
Furthermore, since Ψ F (t) is non-increasing as a function of t we can bound the above integral as follows

e sV +O(sε) Ψ F (V + N ε/π) ≤ V +N ε/π V -N ε/π e st Ψ F (t)dt ≤ e sV +O(sε) Ψ F (V -N ε/π).
Inserting these bounds in (7.7) and using the definition of s in terms of V , we obtain

Ψ F (V + N ε/π) ≤ exp - N π exp π N V - π N B 0 -1 1 + O(ε) ≤ Ψ F (V -N ε/π),
and thus

Ψ F (V ) = exp - N π exp π N V - π N B 0 -1 1 + O V e -πV /(2N ) ,
as desired.

We end this section by proving Corollary 1.7. By Theorem 7.1, it follows that there are

|Ω m |m -1/ log log m elements a ∈ Ω m such that 0≤n≤m/2 ϕ a (n) ≥ N π + o(1) √ m log log m.
Hence, in order to deduce Corollary 1.7 it suffices to show that |Ω m | is larger than a multiple of m.

Lemma 7.3. Let F = {ϕ a } a∈Ωm be a family of m-periodic complex valued functions satisfying Assumptions 2 and 3. Then, we must have |Ω m | m, where the implied constant depends only on the involved constants in the Assumptions.

Proof. Set J = (-m/2, m/2] ∩ Z {0}. Let us recall the following elementary result: if M is a symmetric real matrix, then (Tr M ) 2 ≤ (rkM ) Tr(M 2 ); one sees this by applying the Cauchy-Schwarz inequality to the non-zero eigenvalues of M . We use it with M = [b hj ] h,j = t LL where L = [ ϕ a (h)] a,h (here the index a is in Ω m and h, j are in J). Putting β = E(X 2 ), Assumption 3 with k = 2 gives

b hh = a∈Ωm ϕ a (h) 2 = |Ω m |β + O |Ω m | √ m
for every h ∈ J and

b hj = a∈Ωm ϕ a (h) ϕ a (j) = O |Ω m | √ m
for every distinct h, j. We deduce the estimates

Tr M = h∈J b hh = |Ω m |(βm + O( √ m)) , Tr(M 2 ) = h,j b 2 hj = O(m|Ω m | 2 ) .
One gets

|Ω m | 2 (β 2 m 2 + O(m 3/2 )) = (Tr M ) 2 ≤ (rkM ) Tr(M 2 ) m|Ω m | 2 rkM.
Whence m rkM ≤ rkL ≤ |Ω m |.

An example with very large partial sums

In this section we shall prove Proposition 1.8. Let m ≥ 7 be an integer. Put r = 3 log m/ log 2 and P = r k=1 X 2k-1 . Take a finite field Ω m with 2 r elements and ψ :

Ω m → {-1, 1} a non-trivial additive character. By Weil's theorem [START_REF] Weil | On some exponential sums[END_REF] one has

a∈Ωm ψ(P (a)) ≤ (2r -2)2 r/2 , so |{a ∈ Ω m | ψ(P (a)) = 1}| ≥ 2 r 2 -(r -1)2 r/2 > m 2
and the same is true for |{a ∈ Ω m | ψ(P (a)) = -1}|. Putting J = (-m/2, m/2] ∩ Z, we can therefore choose distinct elements (α h ) h∈J of Ω × m such that ψ(P (α h )) = 1 if h ≥ 1 and ψ(P (α h )) = -1 if h ≤ 0. For every a ∈ Ω m , we define ϕ a in such a way that ∀h ∈ J ϕ a (h) = ψ(P (α h a)), that is, we put

∀n ∈ Z ϕ a (n) = 1 √ m h∈J ψ(P (α h a))e m (-nh).
Let {h 1 , • • • , h k } be a non-empty subset of J with at most r elements. By Vandermonde's formula, the polynomial P (α

h 1 X) + • • • + P (α h k X)
has at least one non-zero coefficient and has odd degree. Applying Weil's theorem, we obtain

a∈Ωm ϕ a (h 1 ) • • • ϕ a (h k ) ≤ (2r -2)2 r/2 m 3/2 log m.
This implies Assumption 3 with any 1 < η < 3/2. Indeed, take a sequence (X(h)) h∈Z of I.I.D. random variables such that P(X(h) = 1) = P(X(h) = -1) = 1/2. For every positive integer k ≤ 3 log m/ log 2 and every (h 1 , . . . , h k ) ∈ J k , one has

1 |Ω m | a∈Ωm ϕ a (h 1 ) • • • ϕ a (h k ) = E(X(h 1 ) • • • X(h k )) + O log m m 3/2
(one can in fact prove this estimate for all positive k ≤ 2r). Thus, we deduce that our family satisfies Assumption 2 with N = 1, and Assumption 3 with η = 4/3.

To conclude the proof of Proposition 1.8, let us look at a = 1: we have ϕ 1 (h) = 1 if h ≥ 1 and ϕ 1 (h) = -1 if h ≤ 0. Using the estimate (1.3) we deduce

M(ϕ 1 ) ≥ 0≤n≤m/2 ϕ 1 (n) = √ m 1≤n≤m/2 1 -(-1) n iπn + O( √ m) = √ m π log m + O( √ m).
9. Applications to families of -adic trace functions: Proof of Corollaries 1.11, 1.12 and 1.13

In this section we recall some notions of the formalism of -adic trace functions and list some examples of families of functions for which we can apply Theorem 1.2 and Theorem 1.6. We are assuming the definition of a constructible -adic sheaf, for which, as well as for a general introduction on the subject, we refer the reader to [6, Section 1.1] and [START_REF] Katz | Sommes exponentielles[END_REF]Section 3.4.2]. We start by introducing the notion of a trace function attached to a constructible -adic sheaf as in [16, 7.3.7]. In the following p, > 2 are distinct prime numbers and ι : Q → C is a fixed embedding. Let F be a constructible -adic sheaf on

A 1 Fp . For any x ∈ A 1 Fp (F p n ) one defines t F ,n (x) := ι(Tr(Fr p n |F x )),
where Fr p n is the geometric Frobenius automorphism of F p n and F x is the stalk of F at a geometric point x over x. The function t F ,n is called the trace function attached to F over F p n . If there is not ambiguity, we denote by t F the trace function t F ,1 . i) The sheaf F is said to be a middle-extension -adic sheaf if F = j * j * F (see [14, 4.4, 4.5] for the definition of j * j * F and its basic properties). ii) The sheaf F is said to be a middle-extension -adic sheaf, punctually pure of weight 0 if it is a middle-extension sheaf and if for every n ≥ 1 and every x ∈ U (F p n ), the images of the eigenvalues of (Fr p n |F x ) via the fixed embedding ι : Q → C, are complex numbers of modulus 1.

Remark 9.2. In accordance with [9, Definition 1.12], we will refer to trace functions attached to punctually pure of weight 0 middle-extension -adic sheaves on A Let F be a middle-extension -adic sheaf on A 1 Fp and let t F ,n be the trace function attached to F over F p n . We recall that the normalized Fourier transform of t F ,n is given by In what follows, we recall some key results about the Fourier transform in the trace functions setting. In particular, c(FT(F)) ≤ 10c(F) 2 .

FT(t F ,n )(x) := - 1 √ p n y∈F p n t F ,n (
Proof. The construction of the sheaf FT(F) and the proof of (i) can be found in [START_REF] Katz | Gauss sums, Kloosterman sums, and monodromy groups[END_REF]Definition 8.2.3], [START_REF] Katz | Gauss sums, Kloosterman sums, and monodromy groups[END_REF]Theorem 8.2.5] and [START_REF] Katz | Gauss sums, Kloosterman sums, and monodromy groups[END_REF]Theorem 8.4.1]. For the part (ii), (iii) and (iv), we refer to the proof of [START_REF] Fouvry | Algebraic twists of modular forms and Hecke orbits[END_REF]Proposition 8.2].

Here the main examples of trace functions we should keep in mind (many of them already appearing in Paragraph 1.2):

(i) For any f, g ∈ F p (T ), and any multiplicative character χ on F × p , the function x → e(f (x)/p)χ(g(x)) is the trace function attached to the Artin-Schreier sheaf L ep(f (T ))χ(g(T )) .

(ii) The r-th hyper-Kloosterman sums: the map

x → Kl r (x; p) = (-1) r-1 p (r-1)/2 y 1 ,...,yr∈F × p y 1 •...•yr=x e y 1 + • • • + y r p
can be seen as the trace function attached to the Kloosterman sheaf K r (see [START_REF] Katz | Gauss sums, Kloosterman sums, and monodromy groups[END_REF] for the definition of such sheaf and for its basic properties). iii) The Birch sums, a → -Bi p (a), can be seen as the trace function attached to the sheaf FT(L ep(T 3 ) ). 9.2. λ-parameter families.

Definition 9.7. Let r ≥ 2 be an integer. A middle-extension -adic sheaf K is said of Sp 2r -type if [START_REF] Katz | Gauss sums, Kloosterman sums, and monodromy groups[END_REF]Chapter 3] for the definition of the monodromy groups).

i) K is punctually pure of weight 0, ii) one has G arith K = G geom K = Sp 2r (C) (see
We are finally ready to introduce the notion of a λ-parameter family which is a refinement of [24, Definition 2.6]: Definition 9.8. Let r ≥ 2 and λ ≥ 1 be integers. A family {F a } a∈(F × p ) λ is said to be a λ-parameter family of Sp 2r -type if the following conditions hold i) for any a ∈ (F × p ) λ , F a is a Fourier, irreducible middle-extension -adic sheaf on A 1 Fp punctually pure of weight 0, ii) there exists C ≥ 1 such that c(F a ) ≤ C for any a ∈ (F × p ) λ . We call the smallest C with this property the conductor of the family and we denote it by C F , iii) for any a ∈ (F × p ) λ-1 the -adic sheaf K a ,1 = FT(F a ,1 ) is of Sp 2r -type, iv) for any a, z ∈ F × p and a ∈ (F × p ) λ-1 , there exists γ z ∈ PGL 2 (F p ) such that

t K a ,a (z) = t K a ,1 (γ z (a)),
and

γ z = γ z if z = z , v) for any a ∈ (F × p ) λ-1 and any z 1 , z 2 ∈ F × p , if z 1 = z 2 then [γ z 1 γ -1 z 2 ] * K a ,1 = geom K a ,1 ⊗ L
for any -adic sheaf L of rank 1, vi) there exists δ, α > 0 such that for any interval I of length |I| ≤ p 1/2+δ , one has

1 p λ a∈(F × p ) λ 1 √ p n∈I t a (n) α p -1/2-δ .
Proposition 9.9. Let λ, r ≥ 1 be integers. Let {F a } a∈(F × p ) λ be a λ-parameter family of Sp 2r -type. Then Theorem 1.2 and 1.6 hold for {t Fa } a∈(F × p ) λ .

Proof. It is enough to show that the set {t Fa } a∈(F × p ) λ satisfies Assumptions 1, 2, 3 and 4. We start with Assumption 1: for any a ∈ (F × p ) λ one has that t Fa ∞ ≤ Rank(F a ) thanks to [6, Lemma 1.

(p -1) λ a ∈(F × p ) λ-1 a∈F × p t K a ,a (h 1 ) • • • t K a ,a (h k ).
We know that for any a ∈ (F × p ) λ-1 and any a, h i ∈ F × p , it holds that t K a ,a (h i ) = t K a ,1 (γ h i (a)) for some γ h i ∈ PGL 2 (F p ) ((iv) in Definition 9.8). Thus we can rewrite equation (9.1) as

1 (p -1) λ a∈(F × p ) λ-1 a∈F × p t K a ,1 (γ h 1 (a)) • • • t K a ,1 (γ h k (a)).
Thanks to the property (v) in Definition 9.8, we can argue as in [24, 4.2.1] to obtain

(-1) k a∈F × p t K a ,1 (γ h 1 (a)) • • • t K a ,1 (γ h k (a)) = E(X(h 1 )...X(h k ))(p -1) + O(c(H) √ p), where H = [γ h 1 ] * K a ,1 ⊗ • • • ⊗ [γ h k ] * K a ,
x (H) ≤ Rank(H) • k i=1 Swan x ([γ h i ] * K a ,1 ) ≤ Rank(K a ,1 ) k kc(K a ,1 ). Thus we have that c(H) ≤ Rank(K a ,1 ) k + k| Sing(K a ,1 )| + k| Sing(K a ,1 )| • Rank(K a ,1 ) k kc(K a ,1 ) ≤ c(K a ,1 ) k + kc(K a ,1 ) + k 2 c(K a ,1 ) k+2 C 8k F ,
where in the last step we used property (ii) in Definition 9.8 together with Theorem 9.6. Thus (9.1) becomes

(-1) k (p -1) λ a∈(F × p ) λ-1 a∈F × p t K a ,a (h 1 ) • • • t K a ,a (h k ) = E (X(h 1 ) . . . X(h k )) + O C 8k F √ p ,
as we wanted. Finally, Assumption 4 simply follows from the definition of a λ-parameter family (property (vi)).

1 = G arith K 1 . iv) Let β ∈ F × p .
By definition of the Fourier transform we have that ii) One has that Sing(L ep(bT

t K β (z) = - 1 √ p x∈Fp e p (x + g(x) + (β + z -1)x) = t K 1 (β + z -1) and therefore t K β (z) = t K 1 (γ z (β)) for γ z := 1 z -1 0 1 . v)
+(aT ) d ) ) = {0, ∞} for any (a, b) ∈ F × p × F × p . Moreover, if d < p then Swan 0 (L ep(bT +(aT ) d ) ) = d, Swan ∞ (L ep(bT +(aT ) d ) ) = 1. Thus c(L ep(bT +(aT ) d ) ) = d + 4 for any (a, b) ∈ F × p × F × p . iii) In [16, Theorem 7.12.3.1] is it shown that for any a ∈ F × p , G geom K a,1 = Sp d+1 (C) if d is odd SL d+1 (C) if d is even.
Hence, when d is odd one concludes also that

G geom K a,1 = G arith K a,1 (by [24, 7.2.(1)]). iv) Let (a, b) ∈ F × p × F × p .
By definition of the Fourier transform we have

t K a,b (z) = - 1 √ p x∈F × p e p (bx + (ax) d + xz) = - 1 √ p x∈F × p e p ((ax) d + (b + z)x) = t K a,1 (b + z -1) and thus t K a,b (z) = t K a,1 (γ z (b)) for γ z = 1 z -1 0 1 .
v) For any a, z 1 , z 2 = 0 with z 1 = z 2 , we need to prove that

(9.2) [γ z 1 γ -1 z 2 ] * K a,1 = geom K a,1 ⊗ L,
for any -adic sheaf L of rank 1, where γ z 1 , γ z 2 are as in (iv). First of all, observe ). Moreover, using Laumon's theory of the -adic Fourier transform, one gets that K a,0 has an unique slope at d/(d + 1) at ∞, and that it is tame at 0 ([16, Theorem 7.5.4]). Thus, Swan 0 (K a,0 ) = 0, Swan ∞ (K a,0 ) = d.

that γ z 1 γ -1 z 2 = 1 z 1 -z 2 0 1 . Let us denote K a,0 = FT(L ep((aT ) d ) ). Arguing as in (iv), one has that K a,1 = geom [τ ] * K a,0 with τ = 1 1 0 1 . Thus, in order to check (9.2) it is enough to show that [γ z ] * K a,0 = geom K a,0 ⊗ L,
Then for any a, z one has Sing([γ z ] * K a,0 ) = {-z, ∞}. Moreover, [γ z ] * K a,0 has an unique slope at d/(d + 1) at ∞ and it is tame at -z. By contradiction, assume that there exists a rank 1 sheaf L such that [γ z ] * K a,0 = geom K a,0 ⊗ L. Without loss of generality, we may assume that L is punctually pure of weight 0 since K a,0 is punctually pure of weight 0. From the discussion above it would follow that {0, -z} ⊂ Sing(L) ⊂ {0, -z, ∞}, and that L is tame everywhere. At this point it is useful to compute some data about FT(L): (9.

3)

The next step is to show that we can see FT(K a,0 ⊗ L) as a cohomological transform in the sense of [START_REF] Fouvry | On the conductor of cohomological transforms[END_REF]. Let us start with the Artin-Schreier sheaf on We use the same strategy as in [19, For n 1 + n 2 = 0, the system Choosing |I| ≤ p 1/2+1/8 we get the result.

n 1 + n 2 = m 1 + m 2 n d 1 + n d 2 = m d 1 + m d

(1. 1 )

 1 M(ϕ) || ϕ|| ∞ √ m log m,where ϕ : Z → C is the normalized discrete Fourier transform of ϕ, defined byϕ(h) = 1 √ m n (mod m) ϕ(n)e m (hn), 2010 Mathematics Subject Classification. Primary 11L03, 11T23; Secondary 14F20, 60F10. The third author is partially supported by a Discovery Grant from the Natural Sciences and Engineering Research Council of Canada.

2 γ

 2 m (h; x) ϕ(h), where γ m (h; x) := 1 √ m 0≤n≤x e m (nh) are the Fourier coefficients modulo m of the characteristic function of the interval [0, x].

  holds for the maximum of partial sums of Kloosterman sums. The normalized classical Kloosterman sums are defined by Kl p (a, b) := 1 √ p n∈F × p e p (an + bn),

Assumption 1 .

 1 Uniform boundednessWe have max a∈Ωm ||ϕ a || ∞ 1, where the implied constant is independent of m.Assumption 2. Support of the Fourier transformThere exists an absolute constant N > 0 such that for all a ∈ Ω m and h ∈ Z/mZ we have ϕ a (h) ∈ [-N, N ].Assumption 3. Joint distribution of the Fourier transformThere exists a sequence of I.I.D. random variables {X(h)} h∈Z * supported on [-N, N ], and absolute constants η ≥ 1/2 and C 1 > 1, such that for all positive integers k ≤ log m/ log log m, and all k

A. Assumption 2 and

 2 Assumption 3 with η > 1. B. Assumptions 1, 2, and Assumption 3 with 1/2 < η ≤ 1. C. Assumptions 1, 2, 4, and Assumption 3 with η = 1/2.

5 . 3 .

 53 s), by Lemma 5.3. Inserting these estimates in (5.14) completes the proof. The distribution of traces of random matrices in the classical group USp 2n . Fix a positive integer n and put N = 2n. Let us endow the unitary symplectic group G = USp 2n with its Haar measure µ (which is normalized throughout), and consider the random variable X : G → [-N, N ] that maps M to Tr M . Assumption 3b is easy to check for X. Indeed, let be an odd positive integer. Observing that -I 2n ∈ USp 2n we get G (Tr M ) dµ(M ) = G (Tr(-M )) dµ(M ) = -G (Tr M ) dµ(M ),

Definition 9 . 1 . 1 Fp 1 1 Fp

 91111 Let F be a constructible -adic sheaf on A and j : U → A Fp the largest dense open subset of A where F is lisse.

1 Fp as trace functions. 9 . 1 . 1 Fp 1 Fp 1 FpA 1 Fp 1 Fp 1 FpRemark 9 . 4 . 1 Fp 1 Fp

 1911111119411 Conductor and Fourier transform. Definition 9.3 ([11], pp. 4 -6). Let F be a constructible -adic sheaf on A 1 Fp and j : U → A the largest dense open subset of A where F is lisse. The conductor ofF is defined as c(F) := Rank(F) + | Sing(F)| + x∈P (Fp) Swan x (j * j * F) + dim H 0 c (, F),where i) Rank(F) := dim F x , for any x where F is lisse.ii) Sing(F) := {x ∈ P (F p ) : F is not lisse at x}. iii) For any x ∈ P (F p ), Swan x (j * j * F) is the Swan conductor of F at x (see[15, Chapter 1] for the definition of the Swan conductor). Recall that if F is a middle-extension sheaf thenc(F) = Rank(F) + | Sing(F)| + x∈P (Fp) Swan x (F),since in this case F ∼ = j * j * F and dim H 0 c (A , F) = 0.

  y)e p (Tr F p n /Fp (xy)).

Definition 9 . 5 ( 1 FpTheorem 9 . 6 . 1 Fp 1 Fp

 9519611 [START_REF] Katz | Gauss sums, Kloosterman sums, and monodromy groups[END_REF], Definition 8.2.1.2). A middle-extension -adic sheaf F over A is said to be a Fourier sheaf if it does not contain any Artin-Schreier sheaf L ep(aT ) in its geometric Jordan-Hölder decomposition. Let F be a middle-extension -adic Fourier sheaf over A . Then there exists a middle-extension -adic sheaf FT(F) over A such thatt FT(F ),n (x) = -1 p n/2 y∈F p nt F ,n (y)e p (Tr F p n /Fp (xy)), for any n ≥ 1 and any x ∈ F p n . Moreover one has that: i) If F is geometrically irreducible, punctually pure of weight 0 then the same holds for FT(F). Moreover FT(F) is a Fourier sheaf with the property FT(FT(F)) = [×(-1)] * F, where [×(-1)] * F denotes the inverse image sheaf [x → -x] * F. ii) Rank(FT(F)) ≤ x Swan x (F) + | Sing(F)| • Rank(F), iii) | Sing(FT(F))| ≤ 2 + Rank(F), iv) Swan x (FT(F)) ≤ c(F).

  8.1]. Hence, using (ii) in the definition of a λ-parameter family we get t Fa ∞ ≤ c(F a ) ≤ C F . Assumption 2 is just an application of [24, Lemma 3.2]. Let us check Assumption 3. Let (h 1 , ..., h k ) ∈ (-p/2, p/2] k with h i = 0 for i = 1, ..., k and consider (9.1) 1

9. 3 . 1 Fp 1 =

 311 Examples of 1-parameter families. Let g ∈ Z[t] be an odd polynomial of degree 2r + 1, such that r ≥ 1. For p large enough{L ep(βT +g(T )) } β∈F × p is a 1-parameter family of Sp 2r -type. i) For any β ∈ F × p , the Artin-Schreier sheaf L ep(βT +g(T )) is a Fourier, irreducible middle-extension -adic sheaf on A punctually pure of weight 0. Moreover its trace function is t F β : x → e p (βx + g(x)). ii) One has that Sing(L ep(βT +g(T )) ) = {∞} for any β ∈ F × p . Moreover, if p > 2r + 1 then Swan ∞ (L ep(βT +g(T )) ) = deg g = 2r + 1. Thus, c(L ep(βT +g(T )) ) = 2r + 3 for any β ∈ F × p . iii) In[16, 7.13 Sp-example (2)], it is shown that the sheaf K 1 is such that G geom K Sp 2r (C). Moreover, as explained in[24, 7.2.(1)], this implies that G geom

K

αp 9 . 4 . 1 Fp

 941 -αη . Choosing a suitable α > 1, property (vi) in Definition 9.8 is satisfied. Examples of 2-parameter families. In this section we present some examples of families of Sp 2r -type. In the following, for a sheaf F a,b we denote K a,b = FT(F a,b ). 9.4.1. Exponential sums II. Let d ∈ N ≥1 with d odd. For p large enough {L ep(bT +(aT ) d )) } (a,b)∈F × p ×F × p is a 2-parameter family of Sp d+1 -type. i) For any (a, b) ∈ F × p × F × p , the Artin-Schreier sheaf L ep(bT +(aT ) d ) is a Fourier, irreducible middle-extension -adic sheaf on A punctually pure of weight 0. Moreover, its trace function is t F a,b : x → e p (bx + (ax) d ).

  for any -adic sheaf L of rank 1, where γ z = 1 z 0 1 with z = 0. Since L ep((aT ) d ) is lisse at {∞}, then K a,0 = FT(L ep((aT ) d ) ) is singular at {0, ∞} ([15, Corollary 8.5.8]

1 FpA 1 Fp 1 Fp 1 Fp 1 Fp- ω n p n/ 2 y- ω n p n/ 2 y

 1111122 a) Sing(FT(L)) = {0, ∞}, since L is tame at ∞ ([15, Corollary 8.5.8]), b) Rank(FT(L)) = dim(H 1 c (A , L ⊗ L ep(αT ) )) for any α = 0. On the other hand, the Grothendieck-Ogg-Shafarevich formula ([18, Chapter 14]) implies thatdim(H 1 c (, L ⊗ L ep(αT ) )) = -Rank(L ⊗ L ep(αT ) ) + x∈A Drop x (L ⊗ L ep(αT ) ) + x∈P Swan x (L ⊗ L ep(αT ) ) = -1 + 2 + 1 = 2,where for a constructible -adic sheafF, Drop x (F) = Rank F -dim F x . Hence, Rank(FT(L)) = 2. c) Since L is not lisse on A \{0}, [15, Corollary 8.5.8] implies that FT(L)(∞)has a break at 1. Thus Swan ∞ (FT(L)) ≥ 1. Since we are assuming that [γ z ] * K a,0 = geom K a,0 ⊗ L, it follows thatFT(K a,0 ⊗ L) = geom FT([γ z ] * K a,0 ) = L ep(-zT -(aT ) d ) .Hence, for any n ≥ 1 there exists a complex number ω n of modulus 1 such that for any s ∈ F × p one has e p (Tr F p n /Fp (-zs -(as) d )) = FT(t [γ z ] * K a,0 ,n )(s) = ω n • FT(t K a,0 ,n • t L,n )(s)= FT(t L,n )(y) FT(t K a,0 ,n )(s -y) = FT(t L,n )(y)e p (Tr F p n /Fp ((a(y -s)) d )).

A 1 Fp × A 1 Fp 1 Fp ×A 1 Fp → A 1 Fp 1 FpA 1 Fp 1 Fp 1 Fp

 111111111 , L ep((a(Y -T)) d ) (see[START_REF] Fouvry | On the conductor of cohomological transforms[END_REF] Definition 2.2]), and consider the -adic sheafG := R 1 p 1,! (p * 2 FT(L) ⊗ L ep((a(Y -T )) d ) )(1/2), where p 1 , p 2 are the two projections p i : A . As pointed out in[START_REF] Fouvry | On the conductor of cohomological transforms[END_REF] Remark 2.4.(1)], G is a constructible -adic sheaf. Let j : U → A be the largest dense open subset on which G is lisse (we remark that Sing(G) ≤ c(G) d 1, thanks to[START_REF] Fouvry | On the conductor of cohomological transforms[END_REF] Theorem 2.3]), and consider the sheaf H = j * j * G; this is a middle-extension -adic sheaf punctually pure of weight 0 on U , such that Rank H = Rank G and for any n ≥ 1 and anys ∈ U (F p n ) t H,n (s) = t G,n (s) = -1 p n/2 y FT(t L,n )(y)e p (Tr F p n /Fp ((a(y -s)) d )),thanks to[START_REF] Fouvry | On the conductor of cohomological transforms[END_REF] Corollary 5.3]. Moreover, one has that1 p n s∈F p n |t H,n (s)| 2 = 1 p n s∈U (F p n ) |t H,n (s)| 2 + O d (1/p n ) = 1 p n s∈U (F p n ) |e p (Tr F p n /Fp (-sx -(as) d ))| 2 + O d (1/p n ) = 1 + O d (1/p n ).Hence, using[17, Lemma 7.0.3], we conclude that H is geometrically irreducible. Since the trace functions attached to the irreducible middle-extension sheaves L ep(-zT -(aT ) d ) and H coincide up to a multiplicative factor of modulus 1 on U (F p ) and c(H), c(L ep(-zT -(aT ) d ) ) d 1 ([11, Theorem 2.3]), it follows that L ep(-zT -(aT ) d ) = geom H thanks to [7, Corollary 3.6]. In particular, Rank H = Rank(L ep(-zT -(aT ) d ) ). To get a contradiction it is enough to show that Rank H = Rank G ≥ d + 1: in this case we would get that 1 = Rank(L ep(-zT -(aT) d ) ) = Rank G ≥ d + 1 > 1 which is absurd. We know that Rank G is equal to the dimension of the stalk G s for any s ∈ A 1Fp , where G is lisse. Using the Proper Base-Change Theorem ([5, Arcata, IV, Theorem 5.4]) one getsG s = (R 1 p 1,! (p * 2 FT(L) ⊗ L ep((a(Y -T )) d ) )) s = H 1 c (, FT(L) ⊗ L ep((a(Y -s)) d )). Thus we need to computeN := dim(H 1 c (A , FT(L) ⊗ L ep((a(Y -s)) d ) )),for some s / ∈ Sing(G). To simplify the notation let us denote N := FT(L) ⊗ L ep((a(Y -s)) d ) where s ∈ A \ {0}. Observe that Rank(N ) = Rank(FT(L)) • Rank(L ep((a(Y -s)) d ) ) = 2. Moreover, since Sing(FT(L)) = {0, ∞} and Sing(L ep((a(Y -s)) d ) ) = {s} we have that Sing(N ) = {0, s, ∞} and Swan 0 (N ) = Swan 0 ( FT(L)) = 0, Swan ∞ (N ) = Swan ∞ (FT(L)) ≥ 1, Swan s (N ) = Swan s (L ep((a(Y -s)) d ) ) = d. Thus, using the Grothendieck-Ogg-Shafarevich formula we get N = -Rank(N ) + Drop 0 (N ) + Drop s (N ) + Swan ∞ (N ) + Swan 0 (N ) + Swan s (N ), ≥ -2 + 1 + 1 + 1 + d = d + 1 as we wanted.

4 a∈Fp b∈Fp n 1 ,n 2 ,m 1 ,m 2

 41212 ∈I e p (b(n 1 + n 2 -m 1 -m 2 ) + a(n 1 d + n 2 d -m 1 d -m 2 d )).

2 4 ≤ 9 . 4 . 2 . 1 Fp

 49421 has at most 2d pairs of solutions (m 1 , m 2 ). On the other hand, if n 1 + n 2 = 0 then m 1 +m 2 = 0. Thus we can bound M 4 as M 4 d |I| 2 p -2 . Now, by positivity wee p (bn + (an) d ) (d, p -1)M 4 d |I| 2 p -2 .Choosing |I| ≤ p 1/2+1/6 we obtain the result. Hyper-Kloosterman sums. For any r ≥ 2, let K r denote the r-th Kloosterman sheaf. For any r ≥ 3 odd the family{[x → ax] * K r ⊗ L ep(bT ) } (a,b)∈F × p ×F × p is a 2-parameter family of Sp r+1 -type. i) For any (a, b) ∈ F × p ×F × p , the sheaf [x → ax] * K r ⊗L ep(bT ) isa Fourier, irreducible middle-extension -adic sheaf on A punctually pure of weight 0. Moreover, the trace function attached to [x → ax] * K r ⊗ L ep(bT ) is given by t F a,b : x → Kl r (ax; p)e p (bx). ii) Thanks to [9, Proposition 8.2] and [15, 11.0.2], one has that c(F a,b ) ≤ 5c([x → ax] * K r ) 2 c(L ep(bT ) ) 2 = 45c([x → ax] * K r ) 2 = 45(r + 3) 2 . is of size p if and only if either (n 1 = -n 2 and m 1 = -m 2 ) or (n 1 = m 1 and n 2 = m 2 ) or (n 1 = m 2 and n 2 = m 1 ), and it has size O r ( √ p) otherwise ([10, Corollary 3.3]). Choose n 1 , n 2 ∈ I. We need to distinguish between two cases: (1) n 1 = -n 2 , thus we have at most two choices of m 1 , m 2 such that the sum in (9.4) has size p, (2) n 1 = -n 2 , then the sum in (9.4) has size p for at most |I| couples (m 1 , m 2 ). Thus we obtain M 4 r |I| 2 p -2 + |I| 3 p -5/2 .

  Let m be large. There exists a family F = {ϕ a } a∈Ωm of m-periodic complex valued functions satisfying Assumption 2 with N = 1 and Assumption 3 with η = 4/3, such that |Ω m | m 3 and

	Proposition 1.8.
					all
	the families we consider), this simple heuristic argument suggests that
	(1.11)	max a∈Ωm	M(ϕ a )	√	m log log m,
	a bound similar to the one proved by Montgomery and Vaughan for character sums
	under the assumption of the Generalized Riemann Hypothesis. Surprisingly, we show
	that unlike this case (in which multiplicativity plays a central role), the above heuristic
	argument is false for certain families of m-periodic complex valued functions satisfying
	the assumptions in case A) of Theorem 1.2 (namely Assumption 2, and Assumption 3
	with η > 1). More precisely, we construct such a family F = {ϕ a } a∈Ωm with |Ω m |
	m 3 , for which the Pólya-Vinogradov inequality (1.4) is sharp (up to the value of the
	implicit constant). This suggests the existence of a transition in the behavior of the
	distribution function Φ F (V ) near the maximal values. It also confirms the common
	belief in analytic number theory that the Pólya-Vinogradov inequality, though simple
	to derive, is extremely difficult to improve.

).

In particular, if |Ω m | m B with an absolute constant B > 0 (which is the case in

  ) . Let g ∈ Z[t] be an odd polynomial of degree 2r + 1, such that r ≥ 1.Let F 1 = {ϕ a } a∈F ×p where ϕ a (n) = e p (an + g(n)

	1.2. Examples of families of -adic trace functions satisfying our assump-
	tions. We exhibit several examples of families of exponential sums that satisfy the
	assumptions in part C) of Theorem 1.2, namely Assumptions 1, 2, 4, and Assumption
	3 with η = 1/2. These correspond to families of -adic trace functions which satisfy
	several conditions, and notably that their arithmetic and geometric monodromy groups
	are both equal to Sp 2r (C), for a certain integer r ≥ 1. We shall describe these families
	in details in section 9. In particular, we obtain the following applications of Theorem
	1.2. In all of these examples, m = p is a large prime, and Ω p = F × p or Ω p = F × p × F × p .
	The first corollary concerns generalizations of Birch sums ([16, 7.13, Sp-example (2)]).
	Corollary 1.11.

  We end this section by deducing the upper bound in case C) of Theorem 1.2 from Theorems 2.1, 2.2 and 2.3.Proof of the upper bound in case C) of Theorem 1.2. Let E m be the exceptional set in Theorem 2.3, and a ∈ Ω m \ E m . Combining this result with the discrete Plancherel formula (1.2) and the estimate (1.3) we obtain

) .

  is very close to the moment generating function of the probabilistic random model Let m be large. There exists a set E m ⊂ Ω m with cardinality |E m | ≤ m -1/10 |Ω m | such that for all complex numbers s with N |s| ≤ (log m)/(50 log log m)

	-m/2<h≤m/2	γ m (h)X(h), which we already estimated in Proposition 5.2.
	h =0
	Proposition 7.2.

1, we will show that the moment generating function of the sum -m/2<h≤m/2 h =0 γ m (h) ϕ a (h) (after removing a "small" set of "bad" points a)

  Rank([γ hi ] * K a ,1 ) = Rank(K a ,1 ) k and that | Sing(H)| ≤ Sing([γ h i ] * K a ,1 )| ≤ k| Sing(K a ,1 )|.On the other hand,[START_REF] Katz | Gauss sums, Kloosterman sums, and monodromy groups[END_REF] Lemma 1.3] implies that Swan

	Assumptions 3a (Lemma 5.4) and 3b. Let us bound c(H). Recall that
	c(H) = Rank(H) + | Sing(H)| +
	One has that Rank(H) = i

1 and the X(h i )'s are independent random variables uniformly distributed with respect to the Haar measure on USp 2r which satisfy x Swan x (H).

i |

  page 1505]: the orthogonality of the additive characters implies thatM 4 = 1 p 3 a∈Fp n 1 ,n 2 ,m 1 ,m 2 ∈I n 1 +n 2 =m 1 +m 2 ,n 2 ,m 1 ,m 2 ∈I n 1 +n 2 =m 1 +m 2

			e p (a(n 1	d + n 2	d -m 1	d -m 2	d ))
	and then
	M 4 =	1 p 2	1 +n d 2 =m d 1 +m d 2 n 1 n d	1.

iii) We start with computing the Fourier transform of t F a,b :

If z = -b, then we apply the change of variables t = x(b + z) getting

We need to show that for any a, z 1 , z 2 ∈ F × p with z 1 = z 2 , one has

for any -adic sheaf L of rank 1. This is just a consequence of ([10, Proposition 3.6]). vi) We compute

Kl r (an 1 ; p) Kl r (an 2 ; p) Kl r (-am 1 ; p) Kl r (-am 2 ; p)×

By orthogonality of the additive characters, we get

Kl r (an 1 ; p) Kl r (an 2 ; p) Kl r (-am 1 ; p) Kl r (-am 2 ; p).

On the other hand, the sum (9.4) a∈F × p Kl r (an 1 ; p) Kl r (an 2 ; p) Kl r (-am 1 ; p) Kl r (-am 2 ; p)