Abstract:
The Pratt tree for a prime $p$ is defined recursively as the tree with root node $p$, and below $p$ are links to the prime factors $q$ of $p-1$, below each $q$ are links to the prime factors of $q-1$, and so on. It was used by Pratt in 1975 to show that every prime has a short certificate (proof) of primality. We investigate the distribution of the height $H(p)$ of the tree with root $p$, in particular illuminating the connection between $H(p)$, the distribution of primes in arithmetic progressions and branching random walks. In particular, based on an appropriate ``random model" of the tree, we make a conjecture about the distribution of $H(p)$ which is perhaps surprising.
This is joint work with Sergei Konyagin and Florian Luca.
This talk will be accessible to graduate students.