Everyone is welcome to attend. Refreshments will be served in the Math Lounge before the exam.
Wednesday, December 5th, 2012 @ 2:00 PM
BA 6183, 40 St. George Street
PhD Candidate: Catalina V. Anghel
PhD Advisor: V. Kumar Murty
Thesis Title: The self-power map and its image modulo a prime
http://www.math.toronto.edu/~canghel/SelfPowerMapCAnghel.pdf
Thesis Abstract:
The self-power map is the function from the set of natural numbers to itself which sends the number $n$ to $n^n$. Motivated by applications to cryptography, we consider the image of this map modulo a prime $p$. We study the question of how large $x$ must be so that $n^n \equiv a \bmod p$ has a solution with $1 \le n \le x$, for every residue class $a$ modulo $p$. While $n^n \bmod p$ is not uniformly distributed, it does appear to behave in certain ways as a random function. We give a heuristic argument to show that the expected $x$ is approximately $(p-1)^2\log \phi(p-1)/\phi(p-1)$, using the coupon collector problem as a model. Rigorously, we prove the bound $x <p^{2-\alpha}$ for sufficiently large $p$ and a fixed constant $\alpha > 0$ independent of $p$, using a counting argument and exponential sum bounds.
Additionally, we prove nontrivial bounds on the number of solutions of $n^n \equiv a \bmod p$ for a fixed residue class $a$ when $1 \le n \le x$, extending the known bounds when $1 \le n \le p-1$.
no comment as of now