Conjectures for fixed-point counts of the discrete logarithm map

Let pp be prime. For divisors and predicates appearing as subscripts, let FgANY,hANY(p)F_{g\,\mathsf{ANY},h\,\mathsf{ANY}}(p) denote the corresponding fixed-point count, and similarly for the restrictions PR\mathsf{PR}, RP\mathsf{RP}, and RPPR\mathsf{RPPR}; here ϕ\phi is Euler's totient function and \bullet denotes an unrestricted condition.

Fixed-point counting conjectures.

FgANY,hANY(p)p1,F_{g\,\mathsf{ANY},h\,\mathsf{ANY}}(p) \approx p-1, FgPR,hANY(p)ϕ(p1),F_{g\,\mathsf{PR},h\,\mathsf{ANY}}(p) \approx \phi(p-1), FgRP,h(p)ϕ(p1)p1FgANY,h(p),F_{g\,\mathsf{RP},h\,\bullet}(p) \approx \frac{\phi(p-1)}{p-1}F_{g\,\mathsf{ANY},h\,\bullet}(p), FgRPPR,h(p)ϕ(p1)p1FgPR,h(p).F_{g\,\mathsf{RPPR},h\,\bullet}(p) \approx \frac{\phi(p-1)}{p-1}F_{g\,\mathsf{PR},h\,\bullet}(p).

These conjectures refine heuristic independence assumptions about discrete logarithms and fixed points. Some special cases are stated in the surrounding text as theorems or are justified by the paper's heuristics, but the displayed asymptotic relations are presented as conjectures.

Sources & referencesView supporting material

Primary source

Joshua Holden and Pieter Moree, “Some Heuristics and Results for Small Cycles of the Discrete Logarithm”, arXiv:math/0401013 (2004).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.