4
$\begingroup$

Suppose I have a set $S$ and I want to find a polynomial $p$ such that $p(s) = 0 \mod n$ if $s \in S$, and that it is non-zero modulo $n$ otherwise.

In the literature such an $S$ is sometimes called a root set (see http://www.sciencedirect.com/science/article/pii/S0195669896901249).

Finding such a polynomial is always possible if $n$ is a prime number, but if $p$ is a non-prime, it may not be.

For example, if $S = \{1,2\}$ and we try to find a polynomial $p$ such that $p(1) = p(2) = 0 \mod 6,$ then this implies that $p(4)=p(5)=0 \mod 6.$ So $\{1,2\}$ is not a root set modulo 6.

Is there some characterization of root sets (modulo a certain integer)? Do you maybe have useful references for me?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Given the prime power case (which is considered in the paper you mention), use the Chinese Remainder Theorem. $\endgroup$
    – user83633
    Dec 18, 2015 at 10:57
  • $\begingroup$ @user83633: as the OP suggests with her example mod 6, this is not as simple (due to the condition that $p$ must be non zero outside of $S$). $\endgroup$
    – Oblomov
    Dec 18, 2015 at 13:40
  • $\begingroup$ Since roots give factorisation of polynomials even over the ring $\mathbf Z/n$, it is equivalent to search a characterisation of subsets $S \subset \mathbf Z/n$ s. t. for every $x$ not in $S$, $\prod_{s \in S} (x-s) \neq 0$. $\endgroup$
    – Oblomov
    Dec 18, 2015 at 13:45
  • $\begingroup$ My previous comment is wrong: over Z/n, one root of a polynomial gives a linear factor, but two distinct roots don't give a factorization by a product of two linear factors (due to the non integrity of the ring). $\endgroup$
    – Oblomov
    Dec 18, 2015 at 16:14
  • 1
    $\begingroup$ @Oblomov: I don't understand your comment. Isn't every root system modulo $\prod p_i^{n_i}$ the product of root systems modulo $p_i^{n_i}$ under the isomorphism $\mathbb Z / \prod p_i^{n_i} \cong \prod \mathbb Z / p_i^{n_i}$ ? $\endgroup$
    – user83633
    Dec 21, 2015 at 9:30

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.