2
$\begingroup$

Let $f(x) \in F_p[x]$ and I know $f(x)$ modulo two polynomials $\phi_1(x)$ and $\phi_2(x)$. What sort of information about $f$ modulo the composition $\phi_1(\phi_2(x))$ can I recover?

I'm looking for a Chinese remainder theorem for the composition.

Degree considerations on $\phi_1(x)$ and $\phi_2(x)$ reveal that it is impossible to fully recover $f(x)$ but I'm wondering if there are any intermediate results.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Think of it this way: knowing $f$ mod $\phi$ essentially means knowing the values of $f$ on the roots of $\phi$ (in an algebraic closure). It seems unlikely you can say anything interesting about the values of $f$ on the roots of $\phi_1\circ\phi_2$ from its values on the roots of $\phi_1$ and of $\phi_2$. Now maybe if you were to ask about $f\circ\phi_2$, of if this were about some different kind of “modulo” or by changing the question in other ways there might be something to say — I don't know. $\endgroup$
    – Gro-Tsen
    Commented Aug 11, 2023 at 18:02
  • $\begingroup$ To be concrete, its like I know how $f$ behaves with $x^2+1$ and $x^3+1$ and I just want to figure out how it behaves with $(x^2+1)^3+1$. Playing around with the system of equations gives some information. In this case (with degrees 2 and 3), I should be able to narrow down $f$ to one of $p$ elements in $F_{p^6}$ $\endgroup$
    – mtheorylord
    Commented Aug 11, 2023 at 18:11
  • $\begingroup$ "Narrow down $f$ to one of $p$ elements in $F_{p^6}$." So, you are viewing a polynomial $f$ as an element of the field of $p^6$ elements? $\endgroup$
    – Gerry Myerson
    Commented Aug 12, 2023 at 6:27

1 Answer 1

Reset to default
3
$\begingroup$

Knowing $f$ modulo $x^2+1$ and $x^3+1$ is equivalent to knowing $x$ modulo $\operatorname{lcm} (x^2+1,x^3+1)$, i.e. $(x^2+1) (x^3+1)$ unless $p=2$ in which case it is $(x+1)(x+1)^3$.

So the ordinary chinese remainder theorem implies that $f$ modulo $(x^2+1)^3+1$ is completely free except that $f$ modulo $$\operatorname{gcd} ( (x^2+1)(x^3+1), (x^2+1)^3+1) = \operatorname{gcd} ( (x^3+1), (x^2+1)^3+1)$$ (since $x^2+1$ is relatively prime to $(x^2+1)^3+1$ in every characteristic) is completely determined.

We have $(x^2+1)^3+1 = x^6 + 3x^4 + 3x^2 +2$ and dividing by $x^3+1$ gives remainder $ 3x^2 - 3x + 3$ so in characteristic $3$ this gcd is $(x^3+1)$ and in every other characteristic it is $x^2-x+1$.

So for $p$ not $3$, we see that $f$ is determined modulo $x^2-x+1$ and otherwise $f$ modulo $(x^2+1)^3+1$ is completely free.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Ah, I see, thank you for the example. I'm still looking for general results though about $f$ modulo compositions. $\endgroup$
    – mtheorylord
    Commented Aug 11, 2023 at 21:32
  • $\begingroup$ I have some trouble parsing the sentence "completely free except that $f$ modulo …" at the end of the second paragraph. What is the claim about the residue? (There's an equals sign, but that seems just to be saying that two $\gcd$s are equal. Incidentally, on that note, \gcd is pre-defined, and need not be \operatornamed, though of course it's harmless.) $\endgroup$
    – LSpice
    Commented Aug 11, 2023 at 21:57
  • 1
    $\begingroup$ @LSpice It was missing a few words, fixed, though it may still be a bit unclear. $\endgroup$
    – Will Sawin
    Commented Aug 11, 2023 at 22:59
  • $\begingroup$ Re, thanks. It is clear to me now. $\endgroup$
    – LSpice
    Commented Aug 11, 2023 at 23:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .