# Greatest common divisor in $\mathbb{F}_p[T]$ with powers of linear polynomials

Let $$n>1$$ and $$p$$ be an odd prime with $$p-1 \mid n-1$$ such that $$p^k - 1 \mid n-1$$ does not hold for any $$k>1$$. Notice that, since $$p-1 \mid n-1$$, we have $$T^p - T \mid T^n-T$$ in $$\mathbb{F}_p[T]$$ and hence also $$T^p - T = (T+u)^p - (T+u) \mid (T+u)^n - (T+u)$$ for all $$u \in \mathbb{F}_p$$.

Question. Is $$T^p - T$$ actually the gcd of $$\{(T+u)^n - (T+u) : u \in \mathbb{F}_p\}$$ in $$\mathbb{F}_p[T]$$?

I have verified this with computer algebra software for $$n \leq 7000$$ (code link). For many $$n$$ actually $$u=0,1$$ are sufficient.

I tried to find a proof, but my first idea didn't work. The only thing I know so far is that the gcd is invariant under $$T \mapsto T+1$$ and therefore contained in $$\mathbb{F}_p[T^p-T]$$. I expect that there are two proofs (if the statement is true at all), namely one using finite fields $$\mathbb{F}_{p^m}$$, and one using a direct calculation with polynomials. I am more interested in a direct calculation here. The background is a new proof of Jacobson's theorem I am working on. Notice that the statement is false for $$p=2$$ (but still true for many $$n$$ in this case) and that it is clearly false without the $$p^k-1$$-requirement.

• Here is a wild guess. Let $D$ be the difference operator,i.e. $Df(x)=f(x)-f(x-1)$. Then the upper gcd is also the gcd of $f,Df,D^2f,..,D^{p-1}f$ for $f=T^n-T$. Maybe that gcd is already the gcd of $f$ and $D^{p-1}f$. Could you run a computer experiment to check this ? Then when computing $D^{p-1}$ for $p>2$, we have to derive twice,i.e. the last summand in $T^n-T$does not matter. This could be why the behaviour is different for $p=2$. – HenrikRüping Feb 18 at 8:10
• Thanks Henrik, and nice to hear from you! I will try that. – Martin Brandenburg Feb 18 at 20:49
• Unfortunately $T^p - T = \mathrm{gcd}(f,D^{p-1}(f))$ is not true for the following pairs $(n,p)$ for $n \leq 200$: $(33,5),(73,7),(81,5),(109,7),(113,5),(127,7)$. – Martin Brandenburg Feb 18 at 21:03
• @MartinBrandenburg Oh sorry, add one to all the numbers that I said. – Will Sawin Feb 19 at 19:11
• @MartinBrandenburg I think I figured out how to abstractly show the existence of a counterexample in this case - see my answer. – Will Sawin Feb 19 at 19:58

This is false.

Let $$p$$ be an odd prime, let $$\ell$$ be another prime, and let $$m$$ be a small prime divisor of $$p^{\ell}-1$$, that doesn't divide $$p-1$$. Let $$n= 1 + \frac{ p^{\ell}-1}{m}$$.

Then $$n-1$$ is a multiple of $$p-1$$, is not a multiple of $$p^{\ell}-1$$, and is not a multiple of $$p^{k}-1$$ for any other $$k$$ because $$p^{\ell}-1$$ is not a multiple of $$p^{k}-1$$ for any $$1 < k < \ell$$.

Then $$x \in \mathbb F_{p^\ell}$$ is a root of $$T^{n } - T$$ if and only if $$x$$ is an $$m$$'th power in $$\mathbb F_{p^\ell}$$. So roots of the gcd of $$(T+u)^n - (T+u)$$ for all $$u$$ in $$\mathbb F_p$$ are exactly those $$x \in \mathbb F_{p^\ell}$$ such that $$x = y_0^m, x+1 = y_1^m, \dots, x+p-1 = y_1^{m}$$ for some $$y_0, \dots, y_{p-1}$$ in $$\mathbb F_{p^\ell}$$.

Thus, to find a counterexample, it suffices to check that the number of $$\mathbb F_{p^\ell}$$ points of the curve $$C_m$$ with variables $$x,y_0,\dots, y_{p-1}$$ and equations $$x +i = y_i^m$$ is greater than the number $$p m^{p-1}$$ of solutions with $$x \in \mathbb F_p$$. Then the $$x$$ coordinates of the extra points will be roots of the gcd but not roots of $$T^p- T$$.

By Riemann-Hurwitz, the genus $$g$$ of $$C$$ satisfies $$2-2g = 2 m^p - (p+1) m^{p-1} (m-1)$$ since the degree over $$\mathbb P^1$$ (under the map $$x$$) is $$m^p$$, there are $$p+1$$ branch points $$0,1\dots, \infty$$, and each branch point has ramification of order $$m$$ on each point lying above it. There are $$m^{p-1}$$ missing points at $$\infty$$.

So by Weil's theorem, the number of $$\mathbb F_{p^\ell}$$-points of $$C$$ is at least $$p^\ell - p^{\ell/2} ((p+1) m^{p-1} (m-1) + 2 - 2 m^p) +1 - m^{p-1}$$ with the first term the main term, the second term coming from the Frobenius eigenvalues, and the last term coming from the missing points.

Thus, as long as

$$p^\ell > p^{\ell/2} ((p+1) m^{p-1} (m-1) + 2 - 2 m^p) + m^{p-1} + p m^{p-1},$$ there is a counterexample.

Plugging into Wolfram Alpha, this inequality fails for $$p=3, \ell=11, m=23$$ but succeeds for $$p=3,\ell=23, m=47$$ and $$p=3, \ell=29, m=59$$.

I found these by looking at the sequence of multiplicative orders of $$3$$ modulo primes and looking for prime values, which became $$\ell$$, with the modulus prime becoming $$m$$.

It seems there are many examples with $$\ell$$ not much smaller than $$m$$, which as long as both are much larger than $$p$$, means this inequality is easily satisfied, since anything of the form $$p^\ell$$ beats anything of the form $$m^p$$.

In the comments, François Brunault found an explicit example: The polynomial $$T^{23}-T^{22}-T^{21}-T^{20}-T^{19}+T^{18}-T^{16}+T^{13}+T^{12}+T^{11}-T^{10}+T^8+T^6+T^4-T^2-T-1$$ divides $$\gcd( T^{n} - T, (T-1)^n - (T-1) , (T+1)^n - (T+1))$$ in $$\mathbb F_3[T]$$ when $$n= 1 + \frac{3^{23}-1}{47}$$ and provided the following Pari/GP code to check it:

P = Mod(x^23-x^22-x^21-x^20-x^19+x^18-x^16+x^13+x^12+x^11-x^10+x^8+x^6+x^4-x^2-x-1, 3); n = 1 + (3^23-1)/47; t = Mod(x, P); print(t^n == t & (t+1)^n == t+1 & (t-1)^n == t-1);

• @MartinBrandenburg If no one else looks at it I can also try to fill in some of the details. When this is done it should all be very elementary algebraic geometry + statements taken as a black box. – Will Sawin Feb 19 at 20:28
• @MartinBrandenburg Another approach is to check these examples by doing a computer search over $\mathbb F_{3^\ell}$, rather than a gcd calculation, which might be easier as you only have one number in memory at a time, but I don't have the knowledge of computer algebra systems to say for sure. – Will Sawin Feb 19 at 20:29
• Very nice! Could you explain how you find the points at infinity of $C_m$? (In which space are you working so that the closure is non-singular?) Otherwise, I found an explicit solution in the case $(p,\ell,m)=(3,23,47)$ using Pari/GP: $P=x^{23}-x^{22}-x^{21}-x^{20}-x^{19}+x^{18}-x^{16}+x^{13}+x^{12}+x^{11}-x^{10}+x^8+x^6+x^4-x^2-x-1$. – François Brunault Feb 20 at 7:59
• To check it: P = Mod(x^23-x^22-x^21-x^20-x^19+x^18-x^16+x^13+x^12+x^11-x^10+x^8+x^6+x^4-x^2-x-1, 3); n = 1 + (3^23-1)/47; t = Mod(x, P); print(t^n == t & (t+1)^n == t+1 & (t-1)^n == t-1); – François Brunault Feb 20 at 8:01
• @FrançoisBrunault The point is to calculate the local monodromy at infinity. When we have a fiber product of coverings, the Galois group is (contained in) the product of the Galois groups, and a generator of the local monodromy is the product of generators of the local monodromy of each covering. We have $p$ coverings $y_i^m = x+i$, each with Galois group $\mathbb Z/m$ and generator of the local monodromy at $\infty$ going to a generator of the group. So the local monodromy at $\infty$ is the elements $(1,\dots, 1)$ of $(\mathbb Z/m)^p$, which acts on $m^{p-1}$ orbits of size $m$. – Will Sawin Feb 20 at 12:28