3
$\begingroup$

During some casual investigation of polynomials over an integer ring $\mathbb{Z}_n$ (or $\mathbb{Z}/n\mathbb{Z}$ if you prefer), I noticed that some polynomials induce the same map. I'm curious about how one could tell if two polynomials are equivalent in this way without checking directly.

For example, in $\mathbb{Z}_8$, $f(x) = 2x^3 + 5x + 3$ is the same as $g(x)=x^4 + 3x^2 + 3x + 3$. They are bijective and act on $\mathbb{Z}_8$ as the permutation $(3, 2, 5, 0, 7, 6, 1, 4)$.

My main question is: What are the criteria for two polynomials to induce the same map on $\mathbb{Z}_n$?

I'm also interested in other information about this, such as: For a given polynomial, are there infinitely many equivalent polynomials? Will the lowest-degree polynomial in an equivalence class always have a degree less than $n$? Does it matter what kind of number $n$ is (e.g. prime or composite)? Are there unique polynomials with $deg\geq1$ having no equivalent?

Without knowing much about this situation, my guess is that the Chinese Remainder Theorem, Euler's Theorem, and/or Fermat's Little Theorem will come into play. I'm exploring a bit outside of my mathematical comfort zone and I have very little experience with number theory, so this is where I get kind of lost.

$\endgroup$
  • $\begingroup$ Euler, and Polynomial remainder theorem may be of use. $\endgroup$ – Roddy MacPhee Oct 9 at 14:57
  • 2
    $\begingroup$ Try looking at $g-f$. This is a polynomial that is zero for any value of $x$. In this case it factorises very nicely as a product of four consecutive numbers - these will always have a multiple of 4 and another even number among them, so the product is 0 mod 8. For a prime modulus $p$, you have $x^p-x=0$ for all $x$, so you can add any multiple of this to a polynomial to get an equivalent one (and one of these will have degree less than $p$). I'm not sure what you'd need for composite moduli in general (at least not if it has to work even when $x$ and $n$ are not coprime). $\endgroup$ – Jaap Scherphuis Oct 9 at 15:36
  • 1
    $\begingroup$ See also math.stackexchange.com/questions/3387540/… $\endgroup$ – lhf Oct 9 at 23:47
1
$\begingroup$

Two polynomials induce the same function iff their difference induces the zero function.

Here is a general result about polynomials that induce the zero function:

If $r$ is the maximum exponent in the prime factorization of $n$, then $x \mapsto x^{r+\lambda (n)}-x^r$ is the zero function mod $n$. [Wikipedia]

Here, $\lambda$ is the Carmichael function.

I don't know whether this is the polynomial of least degree that induces the zero function mod $n$.

$\endgroup$
  • $\begingroup$ Can you expand on how this relates to polynomials with more terms and coefficients? If I'm not mistaken, $f-g$ from my example is $x^4+6x^3+3x+6x$ and the $\lambda$ version of the zero function is $x^5+7x^3$. $\endgroup$ – Era Oct 9 at 17:49
  • $\begingroup$ @Era, you're quite right. So, in this case, $x^5+7x^3$ is not the polynomial of least degree that induces the zero function mod $8$. $\endgroup$ – lhf Oct 9 at 18:17
  • $\begingroup$ The polynomial of least degree that induces the zero function mod $8$ is $4x^2+4x$. $\endgroup$ – lhf Oct 9 at 18:27
  • $\begingroup$ The monic polynomial of least degree that induces the zero function mod $8$ is $x^4+2x^3+3x^2+2x$, which is your $f-g$, up to sign. $\endgroup$ – lhf Oct 9 at 18:34
  • $\begingroup$ The quoted theorem is a special case of the theorem I prove here. and is also proved elsewhere here. $\endgroup$ – Bill Dubuque Oct 9 at 19:09
-1
$\begingroup$

By Euler's totient function, $$x^{\varphi (n)\cdot y+k}\equiv x^k\bmod n$$

Meaning any univariate polynomial, with degree more than $$\varphi(n)$$ is redundant as the coefficients from higher terms is congruent to adding it to the coefficient of a lower degree term.

Furthermore, by polynomial remainder theorem, the values of the polynomial differing in input by $n$ are also congruent.

$\endgroup$
  • 1
    $\begingroup$ Can you explain what you mean by "by Euler's totient function"? I know what the function is, but how does it produce this result? Is that a theorem? $\endgroup$ – Era Oct 9 at 16:54
  • $\begingroup$ it's an extension of the normal use, just like my extension of Fermat, used to find the remainder of a 78 digit number on division by 7. $\endgroup$ – Roddy MacPhee Oct 9 at 16:56
  • $\begingroup$ math.stackexchange.com/questions/3152587/… $\endgroup$ – Roddy MacPhee Oct 9 at 16:57
  • 1
    $\begingroup$ You're making an obvious mistake (what if $n=4$ and $x=2$?). $\endgroup$ – metamorphy Oct 9 at 17:09
  • $\begingroup$ then only the last 2 terms matter... $\endgroup$ – Roddy MacPhee Oct 9 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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