Return to Answer

On the theme of how large a prime has to be for computations modulo that prime to be assured of approximating characteristic 0, an example that looks quite striking is offered in the first three sentences of Ruppert's paper "Reducibility of polynomials $f(x,y)$ modulo $p$" in Journal of Number Theory 77 (1999), 62-70, which is available online at http://arxiv.org/pdf/math/9808021.pdf. The start of the paper is also quoted in the review of this paper on MathSciNet (MR1695700). Here is how it starts:

"It is well known that the reduction $f \bmod p$ of an absolutely irreducible polynomial $f \in {\mathbf Z}[x,y]$ is also absolutely irreducible if the prime $p$ is large enough, e.g. $f = x^9y-9x^9-2x+9y+2$ is absolutely irreducible over $\mathbf Q$ but reducible modulo $p = 186940255267545011$, where $x - 93470127633772547$ divides $f \bmod p$. It is natural to ask how large $p$ has to be to be sure that $f \bmod p$ is absolutely irreducible."

When I first saw that I was shocked. How does anyone discover such stuff? The example is actually less surprising than it appears at first glance if you use resultants. The polynomial is linear in $y$, so its $y$-partial derivative is a polynomial in $x$: $f_y = x^9 + 9$. The resultant of $f$ and $f_y$ is $-186940255267545011 = -p$. Therefore $f(x,y) \bmod p$ and $f_y(x,y) \bmod p$ have resultant $0$, so by the theory of resultants they share a common factor mod $p$. The reduction $f_y \bmod p$ has a single linear factor, namely $x+93470127633772547 \bmod p$. Notice the sign here is $+$ rather than $-$, so Ruppert's paper has a typographical error. Indeed, setting $a =93470127633772547$, you can check $f(-a,y) \equiv 0 \bmod p$ while $f(a,y) \not\equiv 0 \bmod p$, so $f(x,y) \bmod p$ is divisible by $x + a \bmod p$ and not $x - a \bmod p$.

Resultants come up in other problems where first instances of phenomena can be incredibly large compared to the sizes of the coefficients. For example, the polynomials $x^{19}+6$ and $(x+1)^{19}+6$ are relatively prime in characteristic 0. For any prime $p$ not dividing the resultant of these polynomials, $x^{19}+6 \bmod p$ and $(x+1)^{19}+6 \bmod p$ are relatively prime. What about primes that divide the resultant? The resultant of $x^{19}+6$ and $(x+1)^{19}+6$ is $5299875888670549565548724808121659894902032916925752559262837 $, a 61-digit prime number. Modulo this prime, the reductions of $x^{19}+6$ and $(x+1)^{19}+6$ share one common root: $1578270389554680057141787800241971645032008710129107338825798$. This number has 61 digits. For all positive integers less than this, so in particular for all positive integers $n < 10^{50}$, $n^{19}+6$ and $(n+1)^{19}+6$ are relatively prime. That patterns breaks for the first time at $n = 1578270389554680057141787800241971645032008710129107338825798$, where the gcd of $n^{19}+6$ and $(n+1)^{19}+6$ is the 61-digit prime 5299...837 listed above.

On the theme of how large a prime has to be for computations modulo that prime to be assured of approximating characteristic 0, an example that looks quite striking is offered in the first three sentences of Ruppert's paper "Reducibility of polynomials $f(x,y)$ modulo $p$" in Journal of Number Theory 77 (1999), 62-70, which is available online here. The start of the paper is also quoted in the review of this paper on MathSciNet (MR1695700). Here is how it starts:

"It is well known that the reduction $f \bmod p$ of an absolutely irreducible polynomial $f \in {\mathbf Z}[x,y]$ is also absolutely irreducible if the prime $p$ is large enough, e.g. $f = x^9y-9x^9-2x+9y+2$ is absolutely irreducible over $\mathbf Q$ but reducible modulo $p = 186940255267545011$, where $x - 93470127633772547$ divides $f \bmod p$. It is natural to ask how large $p$ has to be to be sure that $f \bmod p$ is absolutely irreducible."

When I first saw that I was shocked. How does anyone discover such stuff? The example is actually less surprising than it appears at first glance if you use resultants. View $f(x,y)$ as a linear polynomial in $y$ with $y$-coefficient $x^9 + 9$ and constant term $-9x^9-2x+2$: the resultant of $x^9 + 9$ and $-9x^9-2x+2$ is that 18-digit prime $p=186940255267545011$, so those two polynomials in $x$ have a common root $a$ in $\mathbf F_p$ for that 18-digit prime $p$, and in fact their unique root mod $p$ is $a \bmod p$ where $a = 93470127633772547$. You can check $f(a,y) \bmod p$ is $0$ in $\mathbf F_p[y]$. Therefore in $\mathbf F_p[x,y]$, $f(x,y) \bmod p$ is reducible with factor $x - a \bmod p$.

Resultants come up in other problems where first instances of phenomena can be incredibly large compared to the sizes of the coefficients. For example, the polynomials $x^{19}+6$ and $(x+1)^{19}+6$ are relatively prime in characteristic 0. For any prime $p$ not dividing the resultant of these polynomials, $x^{19}+6 \bmod p$ and $(x+1)^{19}+6 \bmod p$ are relatively prime. What about primes that divide the resultant? The resultant of $x^{19}+6$ and $(x+1)^{19}+6$ is $5299875888670549565548724808121659894902032916925752559262837 $, a 61-digit prime number. Modulo this prime, the reductions of $x^{19}+6$ and $(x+1)^{19}+6$ share one common root: $1578270389554680057141787800241971645032008710129107338825798$. This number has 61 digits. For all positive integers less than this, so in particular for all positive integers $n < 10^{50}$, $n^{19}+6$ and $(n+1)^{19}+6$ are relatively prime. That patterns breaks for the first time at $n = 1578270389554680057141787800241971645032008710129107338825798$, where the gcd of $n^{19}+6$ and $(n+1)^{19}+6$ is the 61-digit prime 5299...837 listed above.

On the theme of how large a prime has to be for computations modulo that prime to be assured of approximating characteristic 0, an example that looks quite striking is offered in the first three sentences of Ruppert's paper "Reducibility of polynomials $f(x,y)$ modulo $p$" in Journal of Number Theory 77 (1999), 62-70, which is available online at http://arxiv.org/pdf/math/9808021.pdf. The start of the paper is also quoted in the review of this paper on MathSciNet (MR1695700). Here is how it starts:

"It is well known that the reduction $f \bmod p$ of an absolutely irreducible polynomial $f \in {\mathbf Z}[x,y]$ is also absolutely irreducible if the prime $p$ is large enough, e.g. $f = x^9y-9x^9-2x+9y+2$ is absolutely irreducible over $\mathbf Q$ but reducible modulo $p = 186940255267545011$, where $x - 93470127633772547$ divides $f \bmod p$. It is natural to ask how large $p$ has to be to be sure that $f \bmod p$ is absolutely irreducible."

When I first saw that I was shocked. How does anyone discover such stuff? The example is actually less surprising than it appears at first glance if you use resultants. The polynomial is linear in $y$, so its $y$-partial derivative is a polynomial in $x$: $f_y = x^9 + 9$. The resultant of $f$ and $f_y$ is $-186940255267545011 = -p$. Therefore $f(x,y) \bmod p$ and $f_y(x,y) \bmod p$ have resultant $0$, so by the theory of resultants they share a common factor mod $p$. The reduction $f_y \bmod p$ has a single linear factor, namely $x + 93470127633772547 \bmod p$. Notice the sign here is $+$ rather than $-$, so Ruppert's paper has a typographical error. Indeed, setting $a = 93470127633772547$, you can check $f(-a,y) \equiv 0 \bmod p$ while $f(a,y) \not\equiv 0 \bmod p$, so $f(x,y) \bmod p$ is divisible by $x + a \bmod p$ and not $x - a \bmod p$.

Resultants come up in other problems where first instances of phenomena can be incredibly large compared to the sizes of the coefficients. For example, the polynomials $x^{19}+6$ and $(x+1)^{19}+6$ are relatively prime in characteristic 0. For any prime $p$ not dividing the resultant of these polynomials, $x^{19}+6 \bmod p$ and $(x+1)^{19}+6 \bmod p$ are relatively prime. What about primes that divide the resultant? The resultant of $x^{19}+6$ and $(x+1)^{19}+6$ is $5299875888670549565548724808121659894902032916925752559262837 $, a 61-digit prime number. Modulo this prime, the reductions of $x^{19}+6$ and $(x+1)^{19}+6$ share one common root: $1578270389554680057141787800241971645032008710129107338825798$. This number has 61 digits. For all positive integers less than this, so in particular for all positive integers $n < 10^{50}$, $n^{19}+6$ and $(n+1)^{19}+6$ are relatively prime. That patterns breaks for the first time at $n = 1578270389554680057141787800241971645032008710129107338825798$, where the gcd of $n^{19}+6$ and $(n+1)^{19}+6$ is the 61-digit prime 5299...837 listed above.

On the theme of how large a prime has to be for computations modulo that prime to be assured of approximating characteristic 0, an example that looks quite striking is offered in the first three sentences of Ruppert's paper "Reducibility of polynomials $f(x,y)$ modulo $p$" in Journal of Number Theory 77 (1999), 62-70, which is available online at http://arxiv.org/pdf/math/9808021.pdf. The start of the paper is also quoted in the review of this paper on MathSciNet (MR1695700). Here is how it starts:

"It is well known that the reduction $f \bmod p$ of an absolutely irreducible polynomial $f \in {\mathbf Z}[x,y]$ is also absolutely irreducible if the prime $p$ is large enough, e.g. $f = x^9y-9x^9-2x+9y+2$ is absolutely irreducible over $\mathbf Q$ but reducible modulo $p = 186940255267545011$, where $x - 93470127633772547$ divides $f \bmod p$. It is natural to ask how large $p$ has to be to be sure that $f \bmod p$ is absolutely irreducible."

When I first saw that I was shocked. How does anyone discover such stuff? The example is actually less surprising than it appears at first glance if you use resultants. The polynomial is linear in $y$, so its $y$-partial derivative is a polynomial in $x$: $f_y = x^9 + 9$. The resultant of $f$ and $f_y$ is $-186940255267545011 = -p$. Therefore $f(x,y) \bmod p$ and $f_y(x,y) \bmod p$ have resultant $0$, so by the theory of resultants they share a common factor mod $p$. The reduction $f_y \bmod p$ has a single linear factor, namely $x+93470127633772547 \bmod p$. Notice the sign here is $+$ rather than $-$, so Ruppert's paper has a typographical error. Indeed, setting $a =93470127633772547$, you can check $f(-a,y) \equiv 0 \bmod p$ while $f(a,y) \not\equiv 0 \bmod p$, so $f(x,y) \bmod p$ is divisible by $x + a \bmod p$ and not $x - a \bmod p$.

Resultants come up in other problems where first instances of phenomena can be incredibly large compared to the sizes of the coefficients. For example, the polynomials $x^{19}+6$ and $(x+1)^{19}+6$ are relatively prime in characteristic 0. For any prime $p$ not dividing the resultant of these polynomials, $x^{19}+6 \bmod p$ and $(x+1)^{19}+6 \bmod p$ are relatively prime. What about primes that divide the resultant? The resultant of $x^{19}+6$ and $(x+1)^{19}+6$ is $5299875888670549565548724808121659894902032916925752559262837 $, a 61-digit prime number. Modulo this prime, the reductions of $x^{19}+6$ and $(x+1)^{19}+6$ share one common root: $1578270389554680057141787800241971645032008710129107338825798$. This number has 61 digits. For all positive integers less than this, so in particular for all positive integers $n < 10^{50}$, $n^{19}+6$ and $(n+1)^{19}+6$ are relatively prime. That patterns breaks for the first time at $n = 1578270389554680057141787800241971645032008710129107338825798$, where the gcd of $n^{19}+6$ and $(n+1)^{19}+6$ is the 61-digit prime 5299...837 listed above.

On the theme of how large a prime has to be for computations modulo that prime to be assured of approximating characteristic 0, an example that looks quite striking is offered in the first three sentences of Ruppert's paper "Reducibility of polynomials $f(x,y)$ modulo $p$" in Journal of Number Theory 77 (1999), 62-70, which is available online at http://arxiv.org/pdf/math/9808021.pdf. The start of the paper is also quoted in the review of this paper on MathSciNet (MR1695700). Here is how it starts:

"It is well known that the reduction $f \bmod p$ of an absolutely irreducible polynomial $f \in {\mathbf Z}[x,y]$ is also absolutely irreducible if the prime $p$ is large enough, e.g. $f = x^9y-9x^9-2x+9y+2$ is absolutely irreducible over $\mathbf Q$ but reducible modulo $p = 186 940 255 267 545 011$, where $x - 93 470 127 633 772 547$ divides $f \bmod p$. It is natural to ask how large $p$ has to be to be sure that $f \bmod p$ is absolutely irreducible."

When I first saw that I was shocked. How does anyone discover such stuff? The example is actually less surprising than it appears at first glance if you use resultants. The polynomial is linear in $y$, so its $y$-partial derivative is a polynomial in $x$: $f_y = x^9 + 9$. The resultant of $f$ and $f_y$ is $-186 940 255 267 545 011 = -p$. Therefore $f(x,y) \bmod p$ and $f_y(x,y) \bmod p$ have resultant $0$, so by the theory of resultants they share a common factor mod $p$. The reduction $f_y \bmod p$ has a single linear factor, namely $x + 93 470 127 633 772 547 \bmod p$. Notice the sign here is $+$ rather than $-$, so Ruppert's paper has a typographical error. Indeed, setting $a = 93 470 127 633 772 547$, you can check $f(-a,y) \equiv 0 \bmod p$ while $f(a,y) \not\equiv 0 \bmod p$, so $f(x,y) \bmod p$ is divisible by $x + a \bmod p$ and not $x - a \bmod p$.

Resultants come up in other problems where first instances of phenomena can be incredibly large compared to the sizes of the coefficients. For example, the polynomials $x^{19}+6$ and $(x+1)^{19}+6$ are relatively prime in characteristic 0. For any prime $p$ not dividing the resultant of these polynomials, $x^{19}+6 \bmod p$ and $(x+1)^{19}+6 \bmod p$ are relatively prime. What about primes that divide the resultant? The resultant of $x^{19}+6$ and $(x+1)^{19}+6$ is $5299875888670549565548724808121659894902032916925752559262837 $, a 61-digit prime number. Modulo this prime, the reductions of $x^{19}+6$ and $(x+1)^{19}+6$ share one common root: $1578270389554680057141787800241971645032008710129107338825798$. This number has 61 digits. For all positive integers less than this, so in particular for all positive integers $n < 10^{50}$, $n^{19}+6$ and $(n+1)^{19}+6$ are relatively prime. That patterns breaks for the first time at $n = 1578270389554680057141787800241971645032008710129107338825798$, where the gcd of $n^{19}+6$ and $(n+1)^{19}+6$ is the 61-digit prime 5299...837 listed above.

On the theme of how large a prime has to be for computations modulo that prime to be assured of approximating characteristic 0, an example that looks quite striking is offered in the first three sentences of Ruppert's paper "Reducibility of polynomials $f(x,y)$ modulo $p$" in Journal of Number Theory 77 (1999), 62-70, which is available online at http://arxiv.org/pdf/math/9808021.pdf. The start of the paper is also quoted in the review of this paper on MathSciNet (MR1695700). Here is how it starts:

"It is well known that the reduction $f \bmod p$ of an absolutely irreducible polynomial $f \in {\mathbf Z}[x,y]$ is also absolutely irreducible if the prime $p$ is large enough, e.g. $f = x^9y-9x^9-2x+9y+2$ is absolutely irreducible over $\mathbf Q$ but reducible modulo $p = 186940255267545011$, where $x - 93470127633772547$ divides $f \bmod p$. It is natural to ask how large $p$ has to be to be sure that $f \bmod p$ is absolutely irreducible."

When I first saw that I was shocked. How does anyone discover such stuff? The example is actually less surprising than it appears at first glance if you use resultants. The polynomial is linear in $y$, so its $y$-partial derivative is a polynomial in $x$: $f_y = x^9 + 9$. The resultant of $f$ and $f_y$ is $-186940255267545011 = -p$. Therefore $f(x,y) \bmod p$ and $f_y(x,y) \bmod p$ have resultant $0$, so by the theory of resultants they share a common factor mod $p$. The reduction $f_y \bmod p$ has a single linear factor, namely $x + 93470127633772547 \bmod p$. Notice the sign here is $+$ rather than $-$, so Ruppert's paper has a typographical error. Indeed, setting $a = 93470127633772547$, you can check $f(-a,y) \equiv 0 \bmod p$ while $f(a,y) \not\equiv 0 \bmod p$, so $f(x,y) \bmod p$ is divisible by $x + a \bmod p$ and not $x - a \bmod p$.

Resultants come up in other problems where first instances of phenomena can be incredibly large compared to the sizes of the coefficients. For example, the polynomials $x^{19}+6$ and $(x+1)^{19}+6$ are relatively prime in characteristic 0. For any prime $p$ not dividing the resultant of these polynomials, $x^{19}+6 \bmod p$ and $(x+1)^{19}+6 \bmod p$ are relatively prime. What about primes that divide the resultant? The resultant of $x^{19}+6$ and $(x+1)^{19}+6$ is $5299875888670549565548724808121659894902032916925752559262837 $, a 61-digit prime number. Modulo this prime, the reductions of $x^{19}+6$ and $(x+1)^{19}+6$ share one common root: $1578270389554680057141787800241971645032008710129107338825798$. This number has 61 digits. For all positive integers less than this, so in particular for all positive integers $n < 10^{50}$, $n^{19}+6$ and $(n+1)^{19}+6$ are relatively prime. That patterns breaks for the first time at $n = 1578270389554680057141787800241971645032008710129107338825798$, where the gcd of $n^{19}+6$ and $(n+1)^{19}+6$ is the 61-digit prime 5299...837 listed above.