Existence of constant $c$ such that polynomial $P(x_1,\ldots,x_d)+c$ factors

Question

While trying to simplify multivariate polynomials $\mathbb{Z}[x_1,\ldots,x_d]$,

I was wondering,

1. if it is possible to decide, if there is a constant $c$, such that for a given polynomial $p \in \mathbb{Z}[x_1,\ldots,x_d]$ the expression $p(x_1,\ldots,x_d) + c$ factors into linear factors

2. if it is possible to find such constants $c$

3. if one can parametrize the constants $c$ as function of the coefficients of the given polynomial

4. if constants do not work, perhaps a linear term might do the job

My smallest test polynomial starting with dimension 4, is the following

$p_1(x_1,x_2,x_3,x_4) =\\ +750x_2x_3x_4-750x_1x_3x_4\\ +375x_2x_4^2-375x_1x_4^2+375x_2^2x_4-375x_1^2x_4\\ +375x_2x_3^2-375x_1x_3^2+375x_2^2x_3-375x_1^2x_3\\ +125x_2^3-125x_1^3\\ +150x_2x_4-150x_1x_4+150x_2x_3-150x_1x_3\\ +75x_2^2-75x_1^2 +10x_2-10x_1$

which is essentially an alternating sum of binomial coefficients.

Edit 2019-07-29 The polynomial from Hagen's answer divided by 5

$p_2(x_1,x_2,x_3,x_4) =\\ +75x_4^2+75x_3x_4+75x_2x_4+75x_1x_4\\ +75x_3^2+75x_3x_4+75x_2x_3+75x_1x_3\\ +25x_2^2+25x_1x_2+25x_1^2\\ +15x_1+15x_2+30x_3+30x_4+2$.

So essentially, what I'm looking for is an algorithm,
which adds constants and splits off linear factors repeatedly.

Answer 1

Let $D$ be the total degree of $p$ and assume $p(x_1,\ldots, x_r)-c$ splits into (apparently $D$) linear factors. Fix $q\in \Bbb Q$. In general, $f(t):=p(t,\ldots,t,qt)\in\Bbb Q[t]$ will have degree $D$. There are two exceptions: If $p-c$ has a linear factor $a_1x_1+\cdots +a_dx_d-b$ with $a_1+\cdots +a_{d-1}+qa_d=0$, then $f$ is either constant (if $b=0$) and that constant is $c$; or it is of degree $D$ minus the number of such linear factors with $b\ne 0$.If we find $q$ with either of these properties, we have found some condition on the possible form of the linear factors.

In your example, we note that any choice of $q$ makes $f(t)=0$, i.e., if there is such $c$ as desired, then it must be $$\fbox{$c=0$}$$ and one of the factors (depending on $q$) is of the form $a_1x_1+a_2x_2+a_3x_3+a_4x_4$ with $a_1+a_2+a_3+qa_4=0$. As there are infinitely many $q$ and inly finitely many factors, we infer that for one factor $a_1+a_2+a_3=0=a_4$.

We find the same result when placing the $q$ to $x_3$ instead of $x_4$. So either there is a second linear factor with $a_1+a_2+a_4=a_3=0$, or it is the same factor as above and $a_1+a_2=a_3=a_4=0$. Indeed one verifies that $$\fbox{$x_2-x_1$}$$ is a factor, and after getting rid of it we are left with $$ 750 x_3x_4+375x_4^2+375 x_2x_4+375x_1x_4+375x_3^2+375x_2x_3+375x_1x_3 +125x_2^2+125x_2x_1+125x_1^2+150x_4+150x_3+75x_2+75x_1+10.$$ Let's plug in $q_1=x_2=x_3=t$ and $x_4=qt$ again: $$750t^2q+375t^2q^2+375t^2q+375t^2q+375t^2+375t^2+375t^2+125t^2+125t^2+125t^2+150tq+150t+75t+75t+10\\ =(375q^2+1500q +1500)t^2 +(\ldots)t+10\\ =375(q+2)^2t^2+(\ldots)t+10$$ is of lower degree only for $q=-2$. Therefore all remaining linear factors must be of the form $ a_1x_1+a_2x_2+a_3x_3+a_4x_4-b$ with $a_1+a_2+a_3=2a_4$. It is hardly surprising that we find by the same method that $a_1+a_2+a_4=2a_3$ for both factors, hence $a_1+a_2=a_3=a_4$ for both.

With $x_2=qt$ instead, we arrive at $$ (2375+875q+125q^2)t^2+\ldots = 125(q^2+7q+19)t^2+\ldots$$ and that quadratic on $q$ has no rational solution. We conclude that the linear factors cannot exist after all (at least not with integer or rational coefficients) or that I made a mistake in the substitution :)