11
$\begingroup$

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.

$\endgroup$
8
  • 2
    $\begingroup$ 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$. $\endgroup$ Feb 18, 2020 at 8:10
  • $\begingroup$ Thanks Henrik, and nice to hear from you! I will try that. $\endgroup$ Feb 18, 2020 at 20:49
  • $\begingroup$ 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)$. $\endgroup$ Feb 18, 2020 at 21:03
  • $\begingroup$ @MartinBrandenburg Oh sorry, add one to all the numbers that I said. $\endgroup$
    – Will Sawin
    Feb 19, 2020 at 19:11
  • 1
    $\begingroup$ @MartinBrandenburg I think I figured out how to abstractly show the existence of a counterexample in this case - see my answer. $\endgroup$
    – Will Sawin
    Feb 19, 2020 at 19:58

1 Answer 1

11
$\begingroup$

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);

$\endgroup$
11
  • 1
    $\begingroup$ @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. $\endgroup$
    – Will Sawin
    Feb 19, 2020 at 20:28
  • 1
    $\begingroup$ @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. $\endgroup$
    – Will Sawin
    Feb 19, 2020 at 20:29
  • 1
    $\begingroup$ 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$. $\endgroup$ Feb 20, 2020 at 7:59
  • 2
    $\begingroup$ 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); $\endgroup$ Feb 20, 2020 at 8:01
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Will Sawin
    Feb 20, 2020 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.