2
$\begingroup$

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?

$\endgroup$
6
  • 2
    $\begingroup$ Obviously this doesn't work for linear $f$. $\endgroup$
    – Siksek
    Feb 6, 2013 at 8:12
  • $\begingroup$ It's amazing how difficult it is to find reducible polynomials... $\endgroup$ Feb 6, 2013 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$ Feb 6, 2013 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$ May 12, 2013 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$ May 12, 2013 at 21:18

3 Answers 3

4
$\begingroup$

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

$\endgroup$
2
  • $\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$ Feb 7, 2013 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$
    – Turbo
    Mar 31, 2017 at 10:01
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I was thinking something else where $s(a) \ne 1$ $\endgroup$
    – Turbo
    Feb 6, 2013 at 19:24
  • $\begingroup$ may be I should add it as condition. $\endgroup$
    – Turbo
    Feb 6, 2013 at 19:24
  • $\begingroup$ @unknown, maybe you want to require that all four factors have degree at least 1. $\endgroup$ Feb 6, 2013 at 19:33
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ your offer didn't satisfy the assumptions deg(p) < deg(f) nor deg(r) < deg(p). $\endgroup$ Feb 6, 2013 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$ Feb 6, 2013 at 22:08

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.