On the fixed points of the map $x\mapsto x^x$ modulo a prime, II

Abstract

We study number theoretic properties of the map $x\mapsto x^x\mathrm{mod}p$, where $x\in \{1,2,\dots ,p-1\}$, and improve on some recent upper bounds, due to Kurlberg, Luca, and Shparlinski, on the number of primes $p<N$ for which the map only has the trivial fixed point $x=1$. A key technical result, possibly of independent interest, is the existence of subsets ${\mathcal{N}}_q\subset \{2,3,\dots ,q-1\}$ such that almost all $k$-tuples of distinct integers $n_1,n_2,\dots ,n_k\in {\mathcal{N}}_q$ are multiplicatively independent (if $k$ is not too large), and $|{\mathcal{N}}_q|=q\cdot (1+o(1))$ as $q\to \infty$. For $q$ a large prime, this is used to show that the number of solutions to a certain large and sparse system of ${\mathbb{F}}_q$-linear forms $\{{\mathcal{L}}_n{\}}_{n=2}^{q-1}$ "behaves randomly" in the sense that $|\{\mathbf{v}\in {\mathbb{F}}_q^d:{\mathcal{L}}_n(\mathbf{v})=1,n=2,3,\dots ,q-1\}|\sim q^d(1-1/q{)}^q\sim q^d/e$. (Here $d=\pi (q-1)$ and the coefficents of ${\mathcal{L}}_n$ are given by the exponents in the prime power factorization of $n$.)

20 pages, 2 figures

References in corpus (2)

• Congruences involving product of intervals and sets with small multiplicative doubling modulo a prime and applications
• Statistics for fixed points of the self-power map