Strange behaviour of $x^2-7x+5$ under iteration

About a month ago, I asked a similar question about a certain class of polynomials that seem to defy the odds of "eventual divisibility", a property that is best explained by a slightly modified excerpt of the original question:

Look at the graph $$G$$ that is generated by the polynomial $$q(x) = x^2+ax+b$$ ($$a,b \in \mathbb{Z}$$) via the edge set $$\{(n, q(n) \text{ mod } p) : n =0,\ldots,p-1\}$$ for some prime $$p \in \mathbb{P}$$. After some thought, it should be clear that the statements $$\text{Iterating } q \text{ for any input will always eventually lead to divisibility by some prime at least once.} $$ and $$G \text{ has a path from any node to 0.}$$ are equivalent. A polynomial $$q$$ with a prime $$p$$ has the property of "eventual divisibility" if one of these statements hold. Furthermore, "at least once" can be replaced by "periodically infinitely many times" and "every node has a path to $$0$$" can be characterized by "$$G$$ is weakly connected and has exactly one loop containing $$0$$".

After some careful case elimination, I was left with (i.e. could not prove/disprove the property for) three quadratic polynomials where linear and constant coefficients are absolutely smaller than $$10$$:

$$(1)$$ $$x^2-7x-7$$ (which is checked up to $$p \leq 35800000$$ by Mike Daas and me with no hits)

$$(2)$$ $$x^2-7x+5$$ (which is checked up to $$p \leq 7100000$$ by Mike Daas and me with no hits)

$$(3)$$ $$x^2+5x+7$$ (which was shown by Oscar Lanzi to be provably non-eventually divisible)

"No hits" just means that up to now this polynomial does not have a corresponding $$p$$ that gives it the "eventually divisible" property. Since the property seems to hold except for trivial exceptions (see other question), it seems highly unusual that these polynomials just happen to not have it by pure chance - even up in the millions as it turns out! The method that was used for $$(3)$$ can be applied similarly, but does not yield an exhaustive proof: Let's focus on $$(2)$$, since it has the smaller discriminant $$\Delta = 29$$. A key idea for disproving eventual divisibility is $$x^2-7x+5 \equiv 0 \mod p \text{ is not solvable} \iff \left(\frac{\Delta}{p}\right) = \left(\frac{29}{p}\right) = -1$$ Using quadratic reciprocity, we can figure out that $$\left(\frac{29}{p}\right) = \left(\frac{p}{29}\right) = -1 \iff p \equiv 2,3,8,10,11,12,14,15,17,18,19,21,26,27 \mod 29$$ i.e. $$p$$ congruent to one of these residues need not to be checked since the existence of a cycle at $$0$$ is disproven by the lack of solutions leading to $$0$$ when iterated. The same argument can also be applied to the fixed-point-method in the mentioned question, but the CRT guarantees that we will never cover all primes with this (and the discriminants get very, very big leading to extra casework). Thus, the list of $$p$$ left after this procedure begins $$p = 5,7,13,23,53,59,67,71,83,103,107,109,139,\ldots$$

For convenience, let's list the cycles present in the iteration graphs for each of these primes:

$$\begin{array}{c|c} p & \text{Cycles} \\ 5 & (0),(3) \\ 7 & (2),(6) \\ 13 & (0,5,8),(9,10) \\ 23 & (3,16,11) \\ 53 & (12),(16,43),(30,6,52,13) \\ 59 & (0,5,54,6,58,13,24),(14,44,40,27) \\ 67 & (15,58),(12,65,23,38,44,25,53,31) \\ 71 & (12,65),(48,56,51) \\ 83 & (33),(58),(36,53) \\ 103 & (48,16,46) \\ 109 & (20,47,32,42,58) \\ 139 & (21),(126),(85,102,104) \end{array}$$

As a bonus, here is a quite bizarre pattern that I spotted while generating the graph for $$x^2-7x+5$$ with $$p=43$$:

I used Mathematica to generate this picture, to view different examples just change the parameters of the function:

PolyModGraph[poly_,var_,mod_] := Graph[Table[t \[DirectedEdge] Mod[poly/.x -> t,mod], {t,0,mod-1}], VertexLabels->"Name"];
PolyModGraph[x^2-7x+5,x,43]


There are many polynomial-prime combinations that show a $$2$$-fold, $$3$$-fold,... "rotational symmetry" of this kind, but there are also many that do not exhibit any symmetry at all.

The erratic behaviour of the cycle's lengths and their residue classes left me clueless and it does not spark much hope for a proof, but nonetheless:

Is it possible that the non-eventual divisibility of $$x^2-7x-7$$ and $$x^2-7x+5$$ happens to be just by chance, i.e. some anti-"strong law of small numbers" is at work here? Is there another way of proving this property besides the one given by Oscar Lanzi?

• I wrote some slow-ish sagemath code and let it run for about 12 hours today on the polynomial $x^2 - 7x + 5$. I have confirmed that it is not eventually divisible for all primes $p \leq 6,881,261$. For all but $500$ or so of these, $1 \mod p$ already fails to reach $0 \mod p$, and most of these exceptions then fail for $2 \mod p$. If those pass, some first-fails occur more often than others, but it's erratic. Notable are $p = 1327$, which fails first only for $606$, and perhaps most impressively, $p = 572,357$ which only fails first for $117,997$. I'll run the same code for $x^2- 7x - 7$ soon Commented Mar 13 at 0:46
• Now I really begin to wonder whether this is at all related to what Sangchul Lee asked about a few years ago. This is likely to be more complicated, because it is not just about squaring (conjugated or not). Intriguing! Commented Mar 13 at 17:37
• As promised, I also ran my code on $x^2 - 7x - 7$ and I was able to confirm that it is not eventually divisible for all primes $p < 4,000,000$. In this range, only about $400$ did not already fail for $1 \mod p$, again many of those failing for $2 \mod p$, and this time the only prime that really put up a fight being $p = 92,377$ that first fails only for $14,839$ Commented Mar 14 at 0:58
• @MikeDaas I wrote some (quite fast) C++ code that is currently checking these examples. The combination of your idea to just look at $0, 1, ... \mod p$ and check if we are stuck in a non-zero loop combined with the Jacobi symbol eliminating hopeless cases leads to blazingly fast checking! One could probably further speed this up by parallelizing the checking, since the computations are independent of one another. Commented Aug 9 at 15:34
• @QiaochuYuan I am honored that this question has attracted your interest! Sure thing: I used a Mathematica Graph object that is based on a table that maps the residues to their output (with [DirectedEdge]) under a certain given polynomial. The image is generated by simply evaluating such a Graph object. I will add the code snippet to the question while I polish it. Commented 14 hours ago

I will post further developments as an answer to not clutter the exposition in the question too much. To reduce the amount of case checking we have to do, we can put the ideas about higher iterates mentioned in the question to the test: Define $$q(x):=x^2-7x+5$$. Since

$$q(x)-x = \underbrace{x^2-8x+5}_{\Delta_1=44}$$ $$q^{(2)}(x)-x = \underbrace{(x^2-8x+5)}_{\Delta_1}\underbrace{(x^2-6x-1)}_{\Delta_2 = 40}$$ $$q^{(3)}(x)-x = (x^2-8x+5)(x^3-13x^2+40x+13)(x^3-7x^2+4x+1) \stackrel{t = x+\frac{13}{3},s=x+\frac{7}{3}}{=} \underbrace{(x^2-8x+5)}_{\Delta_1}\underbrace{(t^3-\frac{49}{3}t+\frac{637}{27})}_{-\frac{\Delta_t}{108} = -\frac{2401}{108}}\underbrace{(s^3-\frac{37}{3}s-\frac{407}{27})}_{-\frac{\Delta_s}{108} = -\frac{1369}{108}}$$ we get additional conditions based on if one of the discriminants of these factors is a quadratic residue (refer to the quadratic and cubic formula if this is not clear):

$$\left(\frac{\Delta_1}{p}\right) = \left(\frac{44}{p}\right) = \left(\frac{11}{p}\right) \stackrel{!}{=} 1$$

$$\left(\frac{\Delta_2}{p}\right) = \left(\frac{40}{p}\right) = \left(\frac{2}{p}\right) \left(\frac{5}{p}\right) \stackrel{!}{=} 1$$

$$\left(\frac{-108^{-1}\Delta_t}{p}\right) = \left(-\frac{108^{-1}2401}{p}\right) = \left(\frac{-3^{-1}}{p}\right) = \left(\frac{-3}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{3}{p}\right) \stackrel{!}{=} 1$$

$$\left(\frac{-108^{-1}\Delta_s}{p}\right) = \left(\frac{108^{-1}1369}{p}\right) = \left(\frac{-3^{-1}}{p}\right) = \left(\frac{-3}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{3}{p}\right) \stackrel{!}{=} 1$$

Putting everything together, we have the existence of one-cycles if (remember that $$p$$ is prime) $$p \equiv 1, 4, 5, 6, 7, 9, 16, 19, 20, 24, 25, 26, 28, 30, 34, 35, 36, 37, 39, \ 42, 43 \mod 44 \iff p \equiv 1,5,7,9,19,25,35,37,39,43 \mod 44$$ the existence of (true) two-cycles if $$p \equiv 1,3,9,13,27,31,37,39 \mod 40$$ and the existence of (true) three-cycles if $$p \equiv 1,4,7,10 \mod 12 \iff p \equiv 1,7 \mod 12$$ in addition to the $$\mod 29$$-condition given in the question. Now, the list of primes that have precursors to zero (quadratic residue modulo $$29$$) but no cycles of length upto three (quadratic nonresidue, so not fulfilling their modulo conditions) starts as [TODO: There must be some mistake in either my table or this calculation.] $$p = 23, 59, 149, 179, 233, 383, 419, 593, 647, 701, \ldots$$