# Decomposing irreducible polynomials with a prescribed condition - Existence

Let $f(x)$ be an irreducible polynomial in $\mathbb{Z}[x]$ or $\mathbb{F}_{q}[x]$ with $deg(f(x)) \ge 2$ (assume constant coefficient is $1$).

Let $a \in \mathbb{Z}$ or $\mathbb{F}_{q}$. Let $f(a)$ be composite if $a \in \mathbb{Z}$.

Let $char(\mathbb{F}_{q}) \ne 2$.

Is it always possible to find polynomials $p(x),q(x),r(x)$ and $s(x) \in \mathbb{Z}[x]$   such that: $$2f(x) = p(x)q(x) + r(x)s(x),$$ $$1 \le deg(p(x)) < deg(f(x)),\qquad 1 \le deg(q(x)) < deg(f(x)),$$ $$1 \le deg(r(x)) < deg(f(x)),\qquad 1 \le deg(s(x)) < deg(f(x)),$$ and $$p(a)q(a)=r(a)s(a)=f(a),\quad p(a) \ne \pm 1,\ q(a) \ne \pm 1,\ r(a) \ne \pm 1,\ s(a) \ne \pm 1?$$

If such a decomposition is found, is it unique?

-
Obviously this doesn't work for linear $f$. –  Siksek Feb 6 '13 at 8:12
I forgot that condition. –  J.A Feb 6 '13 at 8:44
It's amazing how difficult it is to find reducible polynomials... –  Lior Bary-Soroker Feb 6 '13 at 9:23
You can drop the condition that $p(a)$ etc. not equal 1, unless you also disallow them equalling $-1$ (and it's irrelevant in the finite field case anyway). The requirement that the factors all have degree at least 1 is, I think, sufficient to make the problem interesting. –  Barry Cipra Feb 6 '13 at 21:51
Roughly speaking, how general is the class of polynomials $p\cdot q+r\cdot s$, where $p\ q\ r\ s$ are non-constant polynomials? –  Wlodzimierz Holsztynski May 12 '13 at 21:14

The problem as stated is unsolvable in the case of $\mathbb{Z}$ coefficients with $f(a)$ a prime power. Proof: Let $a=0$, let $f(0) = p^n$ and let the coefficient of $x$ in $f$ not be divisible by $p$. Then $p(0)$, $q(0)$, $r(0)$ and $r(0)$ are all of the form $\pm p^k$, and the hypotheses forbid that $k=0$. So all of the constant terms of $p(x)$, $q(x)$, $r(x)$ and $s(x)$ are divisible by $p$. But then the linear term of $f(x) = (p(x)q(x)+r(x)s(x))/2$ is divisible by $p$ as well, a contradiction. $\square$

Here is a solution for $\mathbb{Z}$ coefficients, assuming that $f(a)$ is not a prime power. Adapting it for coefficients in a finite field should be easy, since there are fewer things to worry about.

Without loss of generality, let $a=0$. Since $f(0)$ is not a prime power, we can factor it as factor $f(0)$ as $p_0 \cdot r_0$ with $GCD(p_0,r_0)=1$. Find $c$ and $d$ such that $c p_0 -d r_0=1$, note for future reference that this implies $GCD(c,d)=1$. We will take $p(x) = dx+p_0$ and $r(x) = cx+r_0$, and slowly construct $q(x)$ and $s(x)$.

Step 1 Making $2 f(x) = p(x) q_0(x) + r(x) s_0(x)$.

We just need to show that $2 f(x)$ is in the ideal generated by $p(x)$ and $r(x)$. But $c p(x) - d r(x) = c (dx+p_0) - d (cx+r_0) = c p_0 - d r_0 = 1$, so this ideal is the whole ring and every polynomial is in it. Explicitly, $2 f(x) = (2 c f(x)) p(x) - (2 d f(x)) r(x)$. $\square$

Step 2 Making $2 f(x) = p(x) q_1(x) + r(x) s_1(x)$ with $\deg q_1$ and $\deg s_1 \leq \deg f -1$.

Suppose that we have found polynomial $Q(x)$ and $S(x)$ with $2 f(x) = p(x) Q(x) + r(x) S(x)$ and $\deg Q$ or $\deg R \geq \deg f$. We will show that we can replace them by polynomials $Q'(x)$ and $S'(x)$ of lower degree, still obeying the equation $2 f(x) = p(x) Q'(x) + r(x) S'(x)$.

Since we are supposing that at least one of $p(x) Q(x)$ and $r(x) S(x)$ has degree larger than the sum $p(x) Q(x) + r(x) S(x)$, we see that the leading terms must cancel. Let the leading terms of $Q$ and $S$ be $Q_m x^m + \cdots$ and $S_m x^m + \cdots$. So $d Q_m + c S_m=0$. Using our above observation that $GCD(c,d)=1$, we see that $Q_m = c F$ and $S_m = -d F$ for some integer $F$. Replace $Q(x)$ and $S(x)$ by $Q(x) - F r(x) x^{m-1}$ and $S(x) + F p(x) x^{m-1}$. $\square$.

Step 3 Achieving $2 f(x) = p(x) q(x) + r(x) s(x)$ with $p(0) q(0) = r(0) s(0)$, and $\deg q$, $\deg s \leq \deg f-1$.

At this point in the proof we already have $2 f(x) = p(x) q_1(x) + r(x) s_1(x)$ with $q_1$ and $s_1$ of sufficiently low degree; we just must change their values at $0$ without making their degree larger.

Comparing constant terms, $$2 f(0) = 2 p_0 r_0 = p_0 q_1(0) + r_0 s_1(0).$$ Using $GCD(p_0, r_0) = 1$, we see that $r_0 | q_1(0)$ and $p_0 | s_1(0)$. Let $q_1(0) = r_0 (1-G)$ and $s_1(0) = p_0 (1+G)$ for some integer $G$. Then replace $q_1(x)$ and $s_1(x)$ by $q_1(x) + G r(x)$ and $s_1(x) - G p(x)$. Since $\deg p = \deg r =1 \leq \deg f-1$, this replacement can't make the degrees of $q$ and $s$ larger than $\deg f-1$. $\square$.

Where did this problem come from? It would make a nice Putnam problem (not now, of course).

-
Nice answer! As for where the problem came from, if you look at its history of edits, you'll see it slowly accreted hypotheses. I recommended not requiring $p(a)\neq 1$ etc. (and the attendant requirement that $f(a)$ be composite), thinking it was sufficient to require all the degrees to be positive, but I see from your answer that it does add something of interest. –  Barry Cipra Feb 7 '13 at 1:20

Am I missing something?* If $f(x) = x^n + \cdots$ is a monic polynomial of degree $n$, one can let $r(x)=2x^{n-1}-2a^{n-1}+f(a)$ and $s(x)=x-a+1$, so that $r(a)s(a)=f(a)\cdot1=f(a)$, and then $p(x)=1$ and $q(x)=2f(x)-r(x)s(x)$ (which has lower degree than $f$), obtaining $p(a)q(a)=2f(a)-r(a)s(a)=f(a)$ also.

*(Added later): This answer was posted for a previous version of the problem, which now disallows factors from taking the value 1 at $x=a$.

-
I was thinking something else where $s(a) \ne 1$ –  J.A Feb 6 '13 at 19:24
may be I should add it as condition. –  J.A Feb 6 '13 at 19:24
@unknown, maybe you want to require that all four factors have degree at least 1. –  Barry Cipra Feb 6 '13 at 19:33

Not sure if u want the additional constraints $p(x), q(x),r(x),s(x)\neq -f(x)$, the following choices would work every time for any value of $a$:

$p(x)=-f(x)$, $q(x)=x-a-1$, $r(x)=-f(x)$, $s(x)=-x+a-1.$

-
your offer didn't satisfy the assumptions deg(p) < deg(f) nor deg(r) < deg(p). –  Wlodzimierz Holsztynski Feb 6 '13 at 9:00
I wonder if this answer was down-voted because someone thought that adas had not read the question carefully. In fact, the early versions of the question did not include any assumptions on the degrees of $p$, $q$, etc. –  Barry Cipra Feb 6 '13 at 22:08
I wrongly downvoted last night. I cannot upvote now. –  J.A Feb 7 '13 at 0:05