Timeline for Greatest common divisor in $\mathbb{F}_p[T]$ with powers of linear polynomials
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 21, 2020 at 13:50 | history | edited | Will Sawin | CC BY-SA 4.0 |
edited body
|
| Feb 21, 2020 at 8:10 | vote | accept | Martin Brandenburg | ||
| Feb 20, 2020 at 14:17 | comment | added | François Brunault | @WillSawin Thanks for the explanations. Yes, it is just exhaustive search (of course just testing $t^n=t \bmod{P}$). But enumerating all the elements of $\mathrm{GF}(3^{23})$ takes very long time, so your lower bound on the number of solutions is essential: it tells us a solution will be found in reasonable time, long before testing all elements. E.g. my computer checked that there is no solution in $\mathrm{GF}(3^\ell)$ with $\ell$ prime $\leq 17$, for $\ell=17$ it took several hours... | |
| Feb 20, 2020 at 12:42 | history | edited | Will Sawin | CC BY-SA 4.0 |
added 499 characters in body
|
| Feb 20, 2020 at 12:38 | comment | added | Will Sawin | @FrançoisBrunault Alternately, one can embed it into affine space with coordinates $y_0,\dots, y_{p-1}$ and equations $y_i^m + 1 = y_{i+1}^m$, and then take the projective closure, which has $m^{p-1}$ points at infinity, all smooth. WRT your example: Nice! Thanks for de-geometrizing my proof. Did you find it by an exhaustive search over degree 23 irreducible polynomials, or was it something more intricate? | |
| Feb 20, 2020 at 12:28 | comment | added | Will Sawin | @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$. | |
| Feb 20, 2020 at 8:01 | comment | added | François Brunault | 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); | |
| Feb 20, 2020 at 7:59 | comment | added | François Brunault | 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$. | |
| Feb 20, 2020 at 1:01 | comment | added | Will Sawin | @R.vanDobbendeBruyn This doesn't give any clue for what the solutions are, only a lower bound for how many there are. | |
| Feb 19, 2020 at 21:55 | comment | added | Martin Brandenburg | Unfortunately my GAP program dies during the computation for $\ell=23,m=47$ in $\mathbb{F}_{3^\ell}$. | |
| Feb 19, 2020 at 20:30 | comment | added | R. van Dobben de Bruyn | Does this produce an easily verifiable counterexample that you can write down (or at least check by computer), or is it more complicated? | |
| Feb 19, 2020 at 20:29 | comment | added | Will Sawin | @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. | |
| Feb 19, 2020 at 20:28 | comment | added | Will Sawin | @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. | |
| Feb 19, 2020 at 20:13 | comment | added | Martin Brandenburg | Thank you, Will! This is so fascinating and quite unexpected for me, I mean using arithmetic geometry to produce a counterexample. Unfortunately I don't have enough background to understand it. I hope that others will say something about your answer. When it's correct, I will accept it of course. | |
| Feb 19, 2020 at 20:11 | history | edited | Will Sawin | CC BY-SA 4.0 |
added 396 characters in body
|
| Feb 19, 2020 at 20:02 | history | edited | Will Sawin | CC BY-SA 4.0 |
added 396 characters in body
|
| Feb 19, 2020 at 19:56 | history | answered | Will Sawin | CC BY-SA 4.0 |