Finding A Large Reducible Polynomial

There's $3$ possible ways $f_N(x)$ can be factored.

Case 1 : $f_N(x)$ has linear factor(s), then by rational root theorem, $f_N(x) = 0$ has possible rational roots of $\pm 1$ , solving $f_N( \pm 1 ) = 0$ gives $N = -6,2$ , so $\text{max} (N) = 2$

Case 2 : $f_N(x)$ has only cubic factors, so $f_N(x) = (x^3 + ax^2 + bx + c)(x^3 + dx^2 + ex + f)$ for integers $a,b,c,d,e,f$ . Expand and compare different powers of $x$ gives the following equations

$\begin{aligned} a + d & = & 1 \\ b + ad + e & = & 1 \\ cd + be + af & = & 1 \\ ce + bf & = & 1 \\ cf & = & 1 \\ \end{aligned}$

Since they are all integers, we have only two possible subcases: $c = f = 1$ and/or $c = f =-1$

For $c = f = 1$ , we get $a + d = 1, b + ad + e = 1, d + be + a = 1, b + e = 1$ , eliminates one equation from another gives $(a,d) = (1,0), (0,1)$ , and $(b,e) = (1,0), (0,1)$ , so $N = c + bd + ae + f = 2,3$

For $c = f = -1$ , we get $a + d = 1, ad = 2$ , $(a,d)$ satisfy the equation $y^2-y+2 = 0$ , but it has negative discriminant, so $c= f=-1$ is infeasible.

Therefore, $\text{max}(N) = 3$

Case 3 $f_N (x)$ has no linear factors nor cubic factors but have quadratic factor(s), so $f_N(x) = (x^2 + ax + b)(x^4 + cx^3 + dx^2 + ex + f )$ for integers $a,b,c,d,e,f$ . (Note that these values of $a,b,c,d,e,f$ are not necessarily similar to the ones in Case 2). Likewise

$\begin{aligned} a+c & = & 1 \\ b + ac + d & = & 1 \\ bd + ae + f & = & 1 \\ be + af & = & 1 \\ bf & = & 1 \\ \end{aligned}$

Again, there's two possible subcase: $b = f = 1$ and/or $b = f = -1$

For $b=f=1$ , simplify the equations, and let $a = x$ for some integer $x$ , then state $a,c,d,e$ in terms of $x$ gives $a = x, c = 1-x, d = x^2 -x, e = 1-x$ , so $N = bc + ad + e = x^3 - x^2 - 2x + 2$ . Because of the constraint $N < 1000$ , we have $x^3 - x^2 - 2x + 2 < 1000$ , it's easy to see that for $x = 10$ yields the largest $N$ , so $N = 10^3 - 10^2 - 2 \cdot 10 + 2 = 882$

For $b = f =-1$ , we have $a + c = 1, ac + d = 2, -d + ae = 2,-e-a = 1$ . The second equation plus the third equation gives $c + e = \frac {4}{a}$ ; while the first equation minus the fourth equation gives $2a + c + e = 0 \Rightarrow 2a + 4/a = 0 \Rightarrow a^2 = -2$ which is absurd because $a$ is real. Thus $b=f=-1$ is infeasible.

Hence, with all the these 3 cases, $\text{max} (N) = \boxed{882}$

I'll try to write a solution that makes use of the symmetry, but I think it misses some cases so someone else can try to modify it. For these kinds of problems, the first step you should do is factor out $x^3$ . $x^3\left(x^3+x^2+x+N+\frac{1}{x}+\frac{1}{x^2}+\frac{1}{x^3}\right)$ Then rewrite the polynomial in terms of $x+\frac{1}{x}$ . $x^3\left(x^3+\frac{1}{x^3}+x^2+\frac{1}{x^2}+x+\frac{1}{x}+N\right)$ $x^3\left(\left(x+\frac{1}{x}\right)^3-3\left(x+\frac{1}{x}\right)+\left(x+\frac{1}{x}\right)^2-2+\left(x+\frac{1}{x}\right)+N\right)$ $x^3\left(\left(x+\frac{1}{x}\right)^3+\left(x+\frac{1}{x}\right)^2-2\left(x+\frac{1}{x}\right)+N-2\right)$ You can substitute $x+\frac{1}{x}$ with $y$ . $x^3\left(y^3+y^2-2y+N-2\right)$ Factoring this polynomial can translate into a factorization of the original polynomial. The $x^3$ can be ignored since it can be distributed into each factor of the polynomial such that each term in each factor has a degree of at least 0.

We want to find the largest integer $N$ such that the cubic can be factored. At least one factor has to be linear, so you can let the other factor be a quadratic. Assuming one of the factors is $y+a$ where a is an integer, the other factor must be $y^2+(1-a)y+a^2-a-2$ to keep the first 3 coefficients the same. $(y+a)(y^2-(1-a)y+a^2-a-2) = y^3+y^2-2y+a^3-a^2-2a$ $y^3+y^2-2y+a^3-a^2-2a = y^3+y^2-2y+N-2$ $a^3-a^2-2a = N-2$ $N=(a-1)(a^2-2)$ The maximum value of $a$ such that $N$ is less than 1000 is $10$ , so $N=9\cdot 98=\boxed{882}$ .