0
$\begingroup$

The theorem below is from pages 4 and 5 in Singmaster - On polynomial functions $\pmod m$ (Theorem 10) on polynomials in $\mathbb{Z}_m[x]$.

Let $f$ be a polynomial function $\pmod{m}$. Then $f$ has a unique polynomial representation $F=\sum_{k=0}^{n-1}b_kX^k$ with $0\leq b_k < \frac{m}{(k!,m)}.$

Here, $F$ denotes a polynomial in $\mathbb{Z}_m[x]$ and $f$ denotes the corresponding function $f:\mathbb{Z}_m\to \mathbb{Z}_m$ which maps $x\to F(x)$ for all $x\in \mathbb{Z}_m$ (so intuitively, one views $F$ as a mapping).

Does this result imply that for every polynomial function $f:\mathbb{Z}_m\to \mathbb{Z}_m$ (in other words, for every tuple $(f(0), f(1), \dotsc, f(m-1))$), there is a unique polynomial that corresponds to its values (aka., a type of Lagrange interpolation?).

This seems to be wrong though, because, for example, in the zero map (the map where $(f(0), f(1), \dotsc, f(m-1))=(0,0,\dotsc, 0)$), it seems that this result would imply that there is a unique polynomial which vanishes on all values of $\mathbb{Z}_m,$ which is well-known to be false. It also seems impossible to generate a polynomials over $\mathbb Z_m$ which corresponds to the values of the function given by $(1, 0,0,\dotsc)$). But does this not contradict what the theorem is saying?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ The theorem does not say that there is a unique polynomial yielding each polynomial function; it says that, for each polynomial function, there is a unique polynomial yielding it that satisfies a given bound on its coefficients. $\endgroup$
    – LSpice
    Commented May 5, 2022 at 0:33
  • 1
    $\begingroup$ Certainly not every tuple $(f(0),f(1),...,f(m-1))$ of elements of $\mathbb{Z}_m$ corresponds to a polynomial function. For example, if $m$ is even, then $f(2)-f(0)$ must be even. $\endgroup$
    – Fedor Petrov
    Commented May 5, 2022 at 12:22
  • $\begingroup$ I am confused about Fedor Petrov's remark. If it is saying that for every tuple, there is a unique polynomial yielding that tuple that satisfies certain bounds on the coefficients, as LSpice said, then isn't this implying that every tuple corresponds to a polynomial? Am I understanding the theorem wrong? $\endgroup$
    – Justin Zhang
    Commented May 5, 2022 at 21:13
  • 1
    $\begingroup$ The theorem only applies when $f$ is a polynomial function, not any function. In other words, the theorem assumes that $f$ is represented by some polynomial and proves that it is then (uniquely) represented by a polynomial satisfying the given bounds on the coefficients. $\endgroup$
    – Antoine Labelle
    Commented May 6, 2022 at 16:05

0

Reset to default

You must log in to answer this question.