Abstracts

The distribution of spacings between quadratic residues: We study the distribution of spacings between squares modulo q, where q is square-free and highly composite, in the limit as the number of prime factors of q goes to infinity. We show that all correlation functions are Poissonian, which among other things, implies that the spacings between nearest neighbors, normalized to have unit mean, have an exponential distribution.
The distribution of spacings between quadratic residues, II: We study the distribution of spacings between squares in Z/QZ as the number of prime divisors of Q tends to infinity. In an ealier paper Kurlberg and Rudnick proved that the spacing distribution for square free Q is Poissonian, this paper extends the result to arbitrary Q.

Hecke theory and equidistribution for the quantization of linear maps of the torus: We study semi-classical limits of eigenfunctions of a quantized linear hyperbolic automorphism of the torus (``cat map''). For some values of Planck's constant, the spectrum of the quantized map has large degeneracies. Our first goal in this paper is to show that these degeneracies are coupled to the existence of quantum symmetries. There is a commutative group of unitary operators on the state-space which commute with the quantized map and therefore act on its eigenspaces. We call these ``Hecke operators'', in analogy with the setting of the modular surface.

We call the eigenstates of both the quantized map and of all the Hecke operators ``Hecke eigenfunctions''. Our second goal is to study the semiclassical limit of the Hecke eigenfunctions. We will show that they become equidistributed with respect to Liouville measure, that is the expectation values of quantum observables in these eigenstates converge to the classical phase-space average of the observable.

On quantum ergodicity for linear maps of the torus: We prove a strong version of quantum ergodicity for linear hyperbolic maps of the torus (``cat maps''). We show that there is a density one sequence of integers so that as N tends to infinity along this sequence, all eigenfunctions of the quantum propagator at inverse Planck constant N are uniformly distributed.

A key step in the argument is to show that for a hyperbolic matrix in the modular group, there is a density one sequence of integers N for which its order (or period) modulo N is somewhat larger than the square root of N.
On a character sum problem of H. Cohn: Let f be a complex valued function on a finite field F such that f(0) = 0, f(1) = 1, and |f(x)| = 1 for x ≠ 0. Cohn asked if it follows that f is a nontrivial multiplicative character provided that $\sum_{x \in F} f(x) \overline{f(x+h)} = -1$ for $h \neq 0$. We prove that this is the case for finite fields of prime cardinality under the assumption that the nonzero values of f are roots of unity.
Value distribution for eigenfunctions of desymmetrized quantum maps: We study the value distribution and extreme values of eigenfunctions for the ``quantized cat map''. This is the quantization of a hyperbolic linear map of the torus. In a previous paper it was observed that there are quantum symmetries of the quantum map - a commutative group of unitary operators which commute with the map, which we called ``Hecke operators''. The eigenspaces of the quantum map thus admit an orthonormal basis consisting of eigenfunctions of all the Hecke operators, which we call ``Hecke eigenfunctions''.

In this note we investigate suprema and value distribution of the Hecke eigenfunctions. For prime values of the inverse Planck constant N for which the map is diagonalizable modulo N (the ``split primes'' for the map), we show that the Hecke eigenfunctions are uniformly bounded and their absolute values (amplitudes) are either constant or have a semi-circle value distribution as N tends to infinity. Moreover in the latter case different eigenfunctions become statistically independent. We obtain these results via the Riemann hypothesis for curves over a finite field (Weil's theorem) and recent results of N. Katz on exponential sums. For general N we obtain a nontrivial bound on the supremum norm of these Hecke eigenfunctions.

On the order of unimodular matrices modulo integers: Assuming the Generalized Riemann Hypothesis, we prove the following: If b is an integer greater than one, then the multiplicative order of b modulo N is larger than $N^{1-\epsilon}$ for all N in a density one subset of the integers. If A is a hyperbolic unimodular matrix with integer coefficients, then the order of A modulo p is greater than $p^{1-\epsilon}$ for all p in a density one subset of the primes. Moreover, the order of A modulo N is greater than $N^{1-\epsilon}$ for all N in a density one subset of the integers.
On the distribution of matrix elements for the quantum cat map: For many classically chaotic systems it is believed that the quantum wave functions become uniformly distributed, that is the matrix elements of smooth observables tend to the phase space average of the observable. In this paper we study the fluctuations of the matrix elements for the desymmetrized quantum cat map. We present a conjecture for the distribution of the normalized matrix elements, namely that their distribution is that of a certain weighted sum of traces of independent matrices in SU(2). This is in contrast to generic chaotic systems where the distribution is expected to be Gaussian. We compute the second and fourth moment of the normalized matrix elements and obtain agreement with our conjecture.

On the period of the linear congruential and power generators: We consider the periods of the linear congruential and the power generators modulo n and, for fixed choices of initial parameters, give lower bounds that hold for ``most'' n when n ranges over three different sets: the set of primes, the set of products of two primes (of similar size), and the set of all integers. For most n in these sets, the period is at least $n^{1/2+\epsilon(n)}$ for any monotone function $\epsilon(n)$ tending to zero as $n$ tends to infinity. Assuming the Generalized Riemann Hypothesis, for most n in these sets the period is greater than $n^{1-\epsilon}$ for any $\epsilon > 0$. Moreover, the period is unconditionally greater than $n^{1/2+\delta}$, for some fixed $\delta>0$ for a positive proportion of $n$ in the above mentioned sets. These bounds are related to lower bounds on the multiplicative order of an integer e modulo $p-1$, modulo $\lambda(pl)$, and modulo $\lambda(m)$ where $p,l$ range over the primes, $m$ ranges over the integers, and where $\lambda(n)$ is the order of the largest cyclic subgroup of $(Z/nZ)^\times$.

Lattice points on circles and discrete velocity models for the Boltzmann equation: The construction of discrete velocity models or numerical methods for the Boltzmann equation, may lead to the necessity of computing the collision operator as a sum over lattice points. The collision operator involves an integral over a sphere, which corresponds to the conservation of energy and momentum. In dimension two there are difficulties even in proving the convergence of such an approximation since many circles contain very few lattice points, and some circles contain many badly distributed lattice points. However, by showing that lattice points on most circles are equidistributed we find that the collision operator can indeed be approximated as a sum over lattice points in the two-dimensional case. For higher dimensions, this result has already been obtained by A. Bobylev et. al. (SIAM J. Numerical Analysis 34 no 5 p. 1865-1883 (1997) )

Poisson statistics via the Chinese remainder theorem: We consider the distribution of spacings between consecutive elements in subsets of $Z/qZ$ where $q$ is highly composite and the subsets are defined via the Chinese remainder theorem. We give a sufficient criterion for the spacing distribution to be Poissonian as the number of prime factors of q tends to infinity, and as an application we show that the value set of a generic polynomial modulo q have Poisson spacings. We also study the spacings of subsets of $Z/q_1 q_2Z$ that are created via the Chinese remainder theorem from subsets of $Z/q_1Z$ and $Z/q_2Z$ (for $q_1,q_2$ coprime), and give criteria for when the spacings modulo $q_1q_2$ are Poisson. We also give some examples when the spacings modulo $q_1q_2$ are not Poisson, even though the spacings modulo $q_1$ and modulo $q_2$ are both Poisson.
Poisson spacing statistics for value sets of polynomials: If f is a polynomial with integer coefficients and q is an integer, we may regard f as a map from Z/qZ to Z/qZ. We show that the distribution of the (normalized) spacings between consecutive elements in the image of these maps becomes Poissonian as q tends to infinity along any sequence of square free integers such that the mean spacing modulo q tends to infinity.

Bounds on supremum norms for Hecke eigenfunctions of quantized cat maps: We study extreme values of desymmetrized eigenfunctions (so called Hecke eigenfunctions) for the quantized cat map, a quantization of a hyperbolic linear map of the torus. In a previous paper it was shown that for prime values of the inverse Planck's constant N=1/h, such that the map is diagonalizable (but not upper triangular) modulo N, the Hecke eigenfunctions are uniformly bounded. The purpose of this paper is to show that the same holds for any prime N provided that the map is not upper triangular modulo N.

We also find that the supremum norms of Hecke eigenfunctions are O_epsilon (N^epsilon) for all epsilon>0 in the case of N square free.

Matrix elements for the quantum cat map: Fluctuations in short windows: We study fluctuations of the matrix coefficients for the quantized cat map. We consider the sum of matrix coefficients corresponding to eigenstates whose eigenphases lie in a randomly chosen window, assuming that the length of the window shrinks with Planck's constant. We show that if the length of the window is smaller than the square root of Planck's constant, but larger than the separation between distinct eigenphases, then the variance of this sum is proportional to the length of the window, with a proportionality constant which coincides with the variance of the individual matrix elements corresponding to Hecke eigenfunctions.

Bounds on exponential sums over small multiplicative subgroups: We show that there is significant cancellation in certain exponential sums over small multiplicative subgroups of finite fields, giving an exposition of the arguments by Bourgain and Chang.

Products in Residue Classes: We consider a problem of P. Erdos, A. M. Odlyzko and A. Sarkozy about the representation of residue classes modulo m by products of two not too large primes. While it seems that even the Extended Riemann Hypothesis is not powerful enough to achieve the expected results, here we obtain some unconditional results ``on average'' over moduli m and residue classes modulo m and somewhat stronger results when the average is restricted to prime moduli m = p. We also consider the analogous question wherein the primes are replaced by easier sequences so, quite naturally, we obtain much stronger results.

The Dynamical Mordell-Lang Conjecture: We prove a special case of a dynamical analogue of the classical Mordell-Lang conjecture. In particular, let phi be a rational function with no superattracting periodic points other than exceptional points. If the coefficients of phi are algebraic, we show that the orbit of a point outside the union of proper preperiodic subvarieties of (P¹)^g has only finite intersection with any curve contained in (P¹)^g. Our proof uses results from p-adic dynamics together with an integrality argument.

A gap principle for dynamics: Let $f_1,...,f_g \in C(z)$ be rational functions, let $\Phi=(f_1,...,f_g)$ denote their coordinatewise action on $(P^1)^g$, let $V \subset (P^1)^g$ be a proper subvariety, and let $P=(x_1,... ,x_g) \in (P^1)^g(C)$ be a nonpreperiodic point for $\Phi$. We show that if $V$ does not contain any periodic subvarieties of positive dimension, then the set of $n$ such that $\Phi^n(P) \in V(C)$ must be very sparse. In particular, for any $k$ and any sufficiently large $N$, the number of $n \leq N$ such that $\Phi^n(P) \in V(C)$ is less than $\log^k N$, where $log^k$ denotes the k-th iterate of the log function. This can be interpreted as an analog of the gap principle of Davenport-Roth and Mumford.
Gaussian point count statistics for families of curves over a fixed finite field: We produce a collection of families of curves, whose point count statistics over $F_p$ becomes Gaussian for $p$ fixed. In particular, the average number of $F_p$-points on curves in these families tends to infinity.