Given $f(x),g(x) \in \mathbb{Z}[x]$, two irreducible polynomials, is there a polynomial $h(x) \in \mathbb{Z}[x]$ coprime to $f(x)$ such that $f(x) + g(x)h(x)$ is reducible over $\mathbb{Z}[x]$ with factors not congruent to $1 \mod g(x)$?

If so, what is the best way to find one such $h(x) \in \mathbb{Z}[x]$?

Let degree of $f(x),g(x)$ be bounded by $n$ (with degree of $g(x)$ strictly less than degree of $f(x)$) and maximum size of coefficients of $f(x),g(x)$ be $2^{s}$. Is there a $(ns)^{c}$ or $(n2^{s})^{c}$ algorithm to find such an $h(x)$ (if such a polynomial exists) where $c \in \mathbb{N}$ is fixed?

In general, is there a way to define the probability that $f(x) + g(x)h(x)$ is reducible into factors not congruent to $1 \mod g(x)$? It is likely this probability asymptotically goes to zero in terms of $n$ and $s$. However how fast does it go to zero? Does it go to zero asymptotically as $\frac{1}{(ns)^{c_{1}}}$ or $\frac{1}{(n2^{s})^{c_{1}}}$ for some positive constant $c_{1}$?

| cite | improve this question | | | | |
  • $\begingroup$ I suppose you do not want $h$ to be a multiple of $f$, then? In general, can you prove the existence a (non-trivial) $h$ that does the job? $\endgroup$ – RP_ Jun 28 '13 at 22:54
  • $\begingroup$ Good question! There should exist. I do not have a proof. May be I will change the question. $\endgroup$ – T.... Jun 28 '13 at 23:01

Let $h(x)=f(x)(f(x)+g(x))+1$, obviously coprime to $f(x)$. Then $$ f(x)+g(x)h(x) = (f(x)+g(x))(1+f(x)g(x)). $$

| cite | improve this answer | | | | |
  • $\begingroup$ I think $h=1+fg+f$ if your displayed formula is to hold. $\endgroup$ – Venkataramana Jun 29 '13 at 3:05
  • $\begingroup$ not exactly what I was thinking. However with polynomials there is always a sneaky way. $\endgroup$ – T.... Jun 29 '13 at 7:27

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.