Narrow Results

The intention of the paper is to move a step towards a classification of network topologies that exhibit periodic quantum dynamics. We show that the evolution of a quantum system whose hamiltonian is identical to the adjacency matrix of a circulant graph is periodic if and only if all eigenvalues of the graph are integers (that is, the graph is integral). Motivated by this observation, we focus on relevant properties of integral circulant graphs. Specifically, we bound the number of vertices of integral circulant graphs in terms of their degree, characterize bipartiteness and give exact bounds for their diameter. Additionally, we prove that circulant graphs with odd order do not allow perfect state transfer.

In this paper, we study various arithmetic properties of d + n/d, where d runs through all the τ(n) positive divisors of n. For example, denoting by ϖ(n) the number of prime values among these sums, we study how often ϖ(n) > 0 and also ϖ(n) = τ(n), and we also evaluate the average value of ϖ(n). We estimate some character sums with d + n/d and study the distribution of quadratic nonresidues and primitive roots among these sums on average over n ≤ x.

We give bounds on the number of integers 1 ≤ n ≤ N such that p | s(n), where p is a prime and s(n) is the sum of aliquot divisors function given by s(n) = σ(n) - n, where σ(n) is the sum of divisors function. Using this result, we obtain nontrivial bounds in certain ranges for rational exponential sums of the form

We obtain a lower bound on the multiplicative order of Gauss periods which generate normal bases over finite fields. This bound improves the previous bound of von zur Gathen and Shparlinski.

We estimate multiplicative character sums along the orbits of a class of nonlinear recurrence vector sequences. In the one-dimensional case, only much weaker estimates are known and our results have no one-dimensional analogs.

We use bounds of mixed character sum modulo a prime p to study the distribution of points on the hypersurface

Using a recent improvement by Bettin and Chandee to a bound of Duke, Friedlander and Iwaniec [Bilinear forms with Kloosterman fractions, Invent. Math.128 (1997) 23–43] on double exponential sums with Kloosterman fractions, we establish a uniformity of distribution result for the fractional parts of Dedekind sums $s(m,n)$ with $m$ and $n$ running over rather general sets. Our result extends earlier work of Myerson [Dedekind sums and uniform distribution, J. Number Theory28 (1988) 233–239] and Vardi [A relation between Dedekind sums and Kloosterman sums, Duke Math. J.55 (1987) 189–197]. Using different techniques, we also study the least denominator of the collection of Dedekind sums $\{s(m,n):m\in {({\mathbb{Z}}/n{\mathbb{Z}})}^{\ast }\}$ on average for $n\in [1,N]$.

Assuming the Generalized Riemann Hypothesis, we design a deterministic algorithm that, given a prime $p$ and positive integer $m=o(p^{1/2}{(\mathrm{\text{log}}p)}^{-4})$, outputs an elliptic curve $E$ over the finite field ${𝔽}_p$ for which the cardinality of $E({𝔽}_p)$ is divisible by $m$. The running time of the algorithm is $m{p}^{1/2+o(1)}$, and this leads to more efficient constructions of rational functions over ${𝔽}_p$ whose image is small relative to $p$. We also give an unconditional version of the algorithm that works for almost all primes $p$, and give a probabilistic algorithm with subexponential time complexity.

We obtain several estimates for double rational exponential sums modulo a prime $p$ with products $n{g}^m$ where both $n$ and $m$ run through short intervals and $g$ is fixed integer. We also obtain some new estimates for the number of points on exponential modular curves $a{g}^m\equiv n(\mathrm{\text{mod}}p)$ and similar.

We obtain several estimates for trilinear form with double Kloosterman sums. In particular, these bounds show the existence of nontrivial cancellations between such sums.

Over the last two decades, there has been a wave of activity establishing the Sato-Tate kind of distribution in various families of elliptic curves over prime fields. Typically the goal here is to prove this for families which are as thin as possible. We consider a function field analogue of this question, that is, for high degree extensions of a finite field where new effects allow us to study families, which are much thinner that those typically investigated over prime fields.

The following sections are included:

• Introduction

• Exponential Sums — Basic Notions
  • Getting started
    • Exponential sums — What are they?
    • Exponential sums — What do we want from them?
    • Exponential sums — How do we classify them?
  • Timeline
    • Johann Carl Friedrich Gauss, 1801
    • Hermann Klaus Hugo Weyl, 1916
    • Godfrey Harold Hardy and John Edensor Littlewood, 1920
    • Louis Joel Mordell, 1932
    • Ivan Matveevich Vinogradov, 1935
    • Loo-Keng Hua, 1940
    • André Weil, 1948
    • Pierre Deligne, 1914
    • You, ????
  • Some terminology
    • Rational exponential sums
    • Complete and incomplete exponential sums

• Simplest Bounds and Applications
  • The basic case — Linear sums
  • Nice result almost for free
  • Gaussian sums
  • Linear sums once again
  • Distribution of functions modulo p

• More Sophisticated Methods
  • Extend and conquer
  • Clone, extend and conquer
  • Mordell's bound
  • Shorter sums … but large bound

• Some Strongest Known Results
  • Weil's kingdom
  • Exponential functions
  • More applications
  • What else can we estimate?

• Twin Brothers of Exponential Sums — Character Sums
  • Definitions
  • Polya—Vinogradov bound again
  • Let's push it down!—Other methods are helpful as well

• Applications to Coding Theory
  • Direct applications
  • Less obvious applications: Dimension of BCH codes
    • Definitions
    • Preparations
    • Main result
    • Discussion: Some lessons to learn

• Applications to Cryptography
  • Distribution of some cryptographic primitives
    • Security of exponentiation with precomputation
    • Diffie-Hellman triples and RSA pairs
  • Lattices and exponential sums
    • Introduction and notation
    • Hidden number problem and lattices
    • Extended hidden number problem, lattices and exponential sums
    • Bit security of the Diffie-Hellman secret key
    • Attack on the digital signature algorithm
    • Other applications and open questions

• Applications to Algorithms
  • Primitive roots
  • Pseudorandom regular graphs
  • Polynomial factorisation
  • Complexity lower bounds

• Tutorial Problems

• References

We give a survey of several recent results and pose several open problems about the distribution and some geometric properties of points (x, y) on modular hyperbolas xy ≡ a (mod m). We also outline a very diverse range of applications of such results and discuss multivariate generalisations.

We give a brief survey of several recently suggested constructions of generating sequences of pseudorandom points on elliptic curves. Such constructions are of interest for both classical and elliptic curve cryptography and are also of intrinsic mathematical interest. We present an account of various results obtained for such sequences and outline several open questions (of different level of difficulty) and directions for further research.

We study possible collisions among the values of the DSA function f(s) = (g^srem p) rem t where g is order t modulo a prime p and n rem k denotes the remainder of n on division by k. In particular, in a certain range of p and t we guarantee the existence of collisions and also give a nontrivial algorithm for inverting this function.

The following sections are included:

• Introduction

• Notation

• Problems

• Acknowledgements

• References