10
$\begingroup$

Given a strictly positive integer $m$ let $\alpha(m)=\mathrm{rad}(m\phi(m))$ be the radical (product of all distinct prime divisors) of the product of $m$ and of Euler's totient function $\phi(m)=m\prod_{p\vert m} \left(1-\frac{1}{p}\right)$ (where the product is over all prime-divisors of $m$). (Equivalently, $\alpha(m)=\mathrm{rad}(\phi(m^2))$.

Since $\alpha(m)$ is bounded above by the product of all primes at most equal to the largest prime-divisor of $m$, iterating $\alpha$ yields a fixed point $\alpha^\infty(m)=\alpha^k(m)=\alpha(F(m))$ for huge enough $k$ ($k=m$ certainly works).

Curiously, the sequence $$1,2,6,10,30,34,42,78,102,110,\ldots$$ (given by enumerating in increasing order all elements of $\alpha^\infty(\mathbb N)$) of fixpoints for $\alpha$ is not recognized by the OEIS!

If $m$ is square-free (i.e. if $m=\mathrm{rad}(m)$), we have the easy inequalities $\mathrm{loglog}(m)\leq \mathrm{loglog}(\alpha^\infty(m))\leq 2\mathrm{loglog}(m)$ (where $\mathrm{loglog}(x)=\log(\log(x))$) which imply the existence of a constant $$a=\limsup_{m\rightarrow \infty,\,\mathrm{rad(m)=m}}\frac{\mathrm{loglog}\,\alpha^\infty(m)}{\mathrm{loglog}\,m}\,.$$ ($\limsup$ is in fact attained over the set of prime-numbers.)

Can the obvious bounds $1\leq a\leq 2$ be improved?

The bound should be close to $2$ if there are very large 'towers' of Sophie Germain primes (primes such that iterating $p\longmapsto 2 p+1$ is also prime). The factor $2$ in $p\longmapsto 2 p+1$ can in fact be replaced by arbitrary small varying numbers (larger than $1$).

Motivation I know of at least two motivations related to the map $\alpha^\infty$ considered above:

(1) Prime certificates: Primality of a prime number $p$ is proven by exhibiting an element $g=g_p$ of order exactly $p-1$ in the cyclic group $(\mathbb Z/p\mathbb Z)^*$ of invertibles. This can be achieved by showing $g^{p-1}\equiv 1\pmod p$ and $g^{(p-1)/q}\not\equiv 1\pmod p$ for every prime divisor $q$ of $p-1$. (Finding such an integer $g$ should not be difficult: a positive proportion of random elements in $\{2,\ldots,p-2\}$ should work. Computing $g^r\pmod m$ is easy using fast exponentiation underlying for example the RSA cryptosystem). The constant $a$ above is thus related to the worst case of such prime certificates (which involve all primes dividing $\alpha^\infty(p)$).

(2) Consider the orbit of an initial integer $s_0\geq 2$ under $x\longmapsto x+x^x$. The sequence $s_0,s_1=s_0+s_0^{s_0},s_2=s_1+s_1^{s_1},\ldots$ grows extraordinarily fast but is easily computable modulo $m$ (and eventually periodic modulo every integer $m$). Computations modulo $m$ involve however also the computation modulo suitable powers of all divisors of $A(m)$.

$\endgroup$

1 Answer 1

6
$\begingroup$

Your observation on towers of primes is spot on. To study the iterations of $\alpha$ at $m$, for each prime $p$ dividing $m$, one builds a tree whose descending branches are the primes that divide $p-1$, and repeats iteratively. These are known as Pratt trees; the primes that appear in (the union of) the tree for $m$ are those appearing in $\alpha^\infty (m)$.

The current state of the art on general Pratt trees is Ford, Konyagin, and Luca, which still is a long way from the full structure of those trees. That the problem is likely difficult can be seen even by considering a single prime, as very large prime factors of $p-1$ are only known under Elliott-Halberstam. Unfortunately the extra structure coming from the full tree (as opposed to just going down one level) only comes into play when seeking for lower bounds, whereas upper bounds depend on constructions with specific primes for the worst-case scenario.

What I can tell you is that in virtually all these situations, if you have an obvious bound like $1 \leq a(m) \leq 2$, one tipically has (search in the literature for "iterated totient") statements like: infinitely many $m$ come close to the upper bound (conditionally), while most $m$ are close to the lower bound; there are quantitative forms of the latter as well, i.e. that read like "all but $O(f(x))$ of $m \leq x$ have $a(m)<1+\varepsilon(m)$" for various explicit pairs of $f$, $\varepsilon$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .