5

About a month ago, I asked a similar question about a certain class of polynomials that seem to defy the odds of "eventual divisibility", i.e. iterating an "eventually divisible" polynomial we can guarantee that any input will yield a number that is divisible by a certain prime $p$ at least once (and thus infinitely often). Please refer to that question for a thorough explanation of the idea. 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 4 \cdot 10^6$ by Mike Daas with no hits)

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

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

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$: Symmetric iteration graph; quite unusual outside of easy examples like x^2

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?

TheOutZ
  • 1,256
  • 8
  • 18
  • 1
    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 – Mike Daas Mar 13 '24 at 00:46
  • 1
    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! – Jyrki Lahtonen Mar 13 '24 at 17:37
  • 1
    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$ – Mike Daas Mar 14 '24 at 00:58

1 Answers1

0

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$$

TheOutZ
  • 1,256
  • 8
  • 18