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?

  • 2
    $\begingroup$ Obviously this doesn't work for linear $f$. $\endgroup$ – Siksek Feb 6 '13 at 8:12
  • $\begingroup$ It's amazing how difficult it is to find reducible polynomials... $\endgroup$ – Lior Bary-Soroker Feb 6 '13 at 9:23
  • $\begingroup$ 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. $\endgroup$ – Barry Cipra Feb 6 '13 at 21:51
  • $\begingroup$ Roughly speaking, how general is the class of polynomials $p\cdot q+r\cdot s$, where $p\ q\ r\ s$ are non-constant polynomials? $\endgroup$ – Włodzimierz Holsztyński May 12 '13 at 21:14
  • $\begingroup$ Let me state it more cartefully: how general is the class of polynomials $f := p\cdot q+r\cdot s$, where $p\ q\ r\ s$ are non-constant polynomials such that $\deg(f)\ =\ \max(\deg(p\cdot q)\ \ \deg(r\cdot s))$ ? $\endgroup$ – Włodzimierz Holsztyński May 12 '13 at 21:18

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).

  • $\begingroup$ 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. $\endgroup$ – Barry Cipra Feb 7 '13 at 1:20
  • $\begingroup$ @DavidSpeyer If the decomposition is not unique is it possible to have $p,q,r$ even and $s$ odd? Nothing says it cannot be done and even having such restrictions still does not guarantee $p,q,r,s$ can be found quickly since you use factors of $f(a)$ in your decomposition $\endgroup$ – Brout Mar 31 '17 at 10:01

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$.

  • $\begingroup$ I was thinking something else where $s(a) \ne 1$ $\endgroup$ – Brout Feb 6 '13 at 19:24
  • $\begingroup$ may be I should add it as condition. $\endgroup$ – Brout Feb 6 '13 at 19:24
  • $\begingroup$ @unknown, maybe you want to require that all four factors have degree at least 1. $\endgroup$ – 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. $

  • $\begingroup$ your offer didn't satisfy the assumptions deg(p) < deg(f) nor deg(r) < deg(p). $\endgroup$ – Włodzimierz Holsztyński Feb 6 '13 at 9:00
  • $\begingroup$ 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. $\endgroup$ – Barry Cipra Feb 6 '13 at 22:08

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.