Definitions
Let $p$ be a prime, and let $f:{\mathbb Z}/p\to{\mathbb Z}/p$ be a function. Then we say that $f$ is Hamiltonian in ${\mathbb Z}/p$ if the directed graph of $f$ is just one cycle --- a Hamiltonian cycle.
To be explicit, let $G$ be the directed graph whose nodes are the residues modulo $p$, and whose arcs are $x\to f(x)$. Then we say that $f$ is Hamiltonian in ${\mathbb Z}/p$ if $G$ is just a Hamiltonian directed cycle.
Question
So, for which prime $p$ is there a $d\in{\mathbb Z}/p$ where $f(x)=x^3+d$ is Hamiltonian in ${\mathbb Z}/p$?
My thoughts
$p=1\mod 6$ is no good, because only a third of the non-zero residues modulo $p$ are cubes. Such cubics exist for the simple cases $p=2, 3$. So for any chance of such $d$ existing with $p>3$, $p=-1\mod 6$.
I note that $x^3-d$ is Hamiltonian iff $x^3+d$ is, so only half the residues modulo $p$ need be tested as values for $d$.
Examples: $p=2, 3, 11, 47, 59, 71, 83, 131, 167, 251, 311, 347, 443, 467,\dots$ (not in OEIS).
I note from brute force search that if $p=5\mod 12$, there are no such $d$. ($p\leqslant 31121$ checked so far.) How come? Such a $p$ is the sum of two squares but I don't see how that would imply my observed result. The nearest approaches I've found are when $f$ is a $p-1$-cycle and a fixed point; this happens when $(p, \pm d)=(29, 2), (29, 7), (41, 11), (41, 19)$.
Broadening the scope to cubics $f(x)=ax^3+d$ might be useful. Fix $p$, and suppose $f(x)=a_0x^3+d_0$ is Hamiltonian. Then, by replacing each element $x$ in the cycle by $kx$ for some non-zero constant $k$, we get the function $g(x)=a_0 k^{-2}x^3+kd_0$. This shows that if such cubics exist, their respective values for $a$ are either the squares or the non-squares modulo $p$. Every non-zero residue is a possible value for $d$; for example, by taking $k=d_0^{-1}$ we get $g(x)=a_0 d_0^2+1$.
Now for some prime $p=5\mod 12$ some cubics $f(x)=ax^3+d$ are Hamiltonian, but in every case I've found, the values of $a$ are the non-squares modulo $p$. Examples: $p=5, 29, 101, 137, 149, 173, 197, 233, 257, 269,\dots$ (not in OEIS).
That is, the $(p,a)$ where $ax^3+d$ is Hamiltonian modulo $p$ for some $d$ are in two classes:
- $p=-1\mod 12$ so $-1$ is not a square modulo $p$; $a$ is a square modulo $p$
- $p=5\mod 12$ so $-1$ is a square modulo $p$; $a$ is not a square modulo $p$
So in each case if $ax^3+d$ is Hamiltonian, $-a$ is not a square modulo $p$. Alternatively (if this is conceptually better) if $-a$ is a square modulo $p$, $ax^3+d$ as a permutation is not Hamiltonian but has two or more cycles.
The parity of the number of cycles of $f$
Denote the number of cycles of $f$ by $C(f)$.
After some testing I make the following conjecture. For given prime $p=5\mod 6$, and given $a$, as $d$ varies, with $f(x)=ax^3+d$, the parity of $C(f)$ is invariant. The value of $C(f)$ might be different for different $d$, but the parity is the same.
For given $p$ and $a$, $C(x\to ax^3+d)$ being odd doesn't guarantee a $d$ where $C(x\to ax^3+d)=1$, but if $C(x\to ax^3+d)$ is even for any $d$, then, for every $d$, it is not 1.
A cycle of length $l$ is $l-1$ transpositions. So, if $f$ is a $p$-element permutation consisting of $C(f)$ cycles, then $f$ is $p-C(f)$ transpositions. So, if $p$ is odd, then $f$ and $C(f)$ have opposite parity. So we have Hamiltonian $f$ only if we have odd $C(f)$ and thus even $f$.
It turns out that the conditions determining this parity are easily stated (though I have no proof): If $p=-1\mod 6$, and $f(x)=ax^3+d$, then $C(f)$ is even iff $-a$ is a square modulo $p$. This is independent of $d$.
$f$ is Hamiltonian only if $C(f)$ is odd, but I don't know of sufficient, or further necessary, preconditions.
Iterates of $f$; any use?
Because I'm only considering primes $p$ as moduli, $f$ is Hamiltonian iff $f(0)\ne0$ and $f^p(0)=0$, where $f^p$ means $p$ iterations of $f$. But I can't see how to exploit this given that $f(x)$ is more complicated than $ax+b$ or $ax^k$.
Literature?
I haven't found any published literature on such functions. Perhaps I am not using the correct word? I have borrowed the term "Hamiltonian cycle'' from graph theory. What is the corresponding term in the theory of permutations or permutation functions? "Cycle'' and "cyclic permutation'' do not restrict to cycles which involve all the elements in the permutation set. Or perhaps Hamiltonian functions are just not distinctive among permutation functions, so whether or not one is Hamiltonian is as unpredictable as, say, whether or not a prime is a Mersenne prime's exponent?
I have used key words such as "permutation cubic function modulo cycle'' in OEIS, but with no luck.