Pre-Q&A

CRGreathouse

Forum Staff

Q1. Find a polynomial f(x) with all coefficients in {0, 1, ..., 9} such that f(2) is prime but f(x) is reducible (i.e., f(x) = g(x)h(x) with g, h in Z[x]).

Bonus question: Why did I choose the constant 9?

mathbalarka

Math Team
This is hard. Just to confirm, you want nonnegative coefficients all in {0, ..., 9}, correct?

CRGreathouse

Forum Staff
mathbalarka said:
This is hard. Just to confirm, you want nonnegative coefficients all in {0, ..., 9}, correct?
Correct -- nonnegative integer coefficients, none greater than 9. Although if it makes it easier you can use coefficients up to, say, 20. (I don't guarantee it will make it easier! It should be doable with 1 or more 9s and 0 or more of the other numbers.)

It is hard -- and related to a talk I went to in this year's JMM.

mathbalarka

Math Team
Since f(2) is prime, g(2)h(2) must be prime, so either h(2) = 1 or g(2) = 1. WLOG h(2) = 1 implies at least one of the coefficients of h(x) is negative. Thus h(x) has a positive root, by rule of signs. g(x) * h(x) also has a positive root, implies a sign change happens, so none such f(x) exists.

EDIT This reasoning is false since we can choose h(x) to have 2 sign changes, thus failing Descartes rule of signs and construct one that has signed coefficients yet no positive roots, right?(*) Then h(x) cannot have more than 2 sign changes, since otherwise it is bound to have a real root.

EXAMPLE (*) -x^3 + x - 1

Okay, let's put it together all : f(x) = g(x)h(x). f(x) has all nonnegative coefficients. By rule of signs, f(x) has no positive root. That clearly means g(x) and h(x) has no positive roots. But h(2) = 1 (WLOG) hence coefficients of h(x) must not be all positive. Assume it has n sign changes in the coefficients. By rule of signs, it has either n or n - 2 positive roots. Only way to make at least one of them vanish is to set n = 2 or n = 0, and since the latter is not possible, n = 2. We now know that there must be two sign changes in at least on of the prime factors of f(x), precisely the one which returns 1 with argument being 2.

EDIT I just realized this is insanely hard, and my heuristic above is just a scratch on the surface. My bet : no factor of f(x) in Z[x] is quadratic.

EDIT Question : Are you sure there exists any?

Hoempa

Math Team
Does such f(x) with degree > 0 even exist?

Let f(x) be a polynomial of the lowest degree possible that satisfies f(2) = p where p is prime, and coeficients in {0, 1, ..., 9}
Then wlog let g(2) = p. We have deg(g) <= deg(f), (where deg(A) denotes degrees of function A).
Since deg(f) is minimal, deg(g) = deg(f) and so deg(h) = 0. i.e. h is a constant.

Only candidates I can think of is (g(x), h(x)) = (1, 2) (in any order).

mathbalarka

Math Team
Hoempa said:
Since deg(f) is minimal, deg(g) = deg(f) and so deg(h) = 0. i.e. h is a constant.
You are missing something here. f have to have coefficients all nonnegative, whereas we can let g(x) (say, or else h(x). WLOG the same) to have negative coefficients, so concept of 'minimality' does not stand.

Hoempa

Math Team
I believe CRG gave the answer here. To answer his bonusquestion, due to Schur's theorem.
[color=#AA0000 said:
CRGreathouse[/color]]If they were between 0 and 9, Schur's theorem would tell us that the polynomial is irreducible.
Where I wrote (g(x), h(x)) = (1, 2) (in any order), I should have written (g(x), h(x)) = (1, p) (in any order).

mathbalarka

Math Team
I am not familiar with Schur's theorem, so no comments.

mathbalarka

Math Team
Okay, I am still attacking it. I am quite sure this has a solution. Please don't post the answer, CRG.

EDIT1 f(x) = g(x)h(x). WLOG g(2) = 1. Okay. Then we need 2 to be a zero of g(x) - 1. g(x) - 1 is then (x - 2)P(x). We need to prove that it is a positive multiple of a polynomial with coefficients all nonnegative.

EDIT2 (still thinking)

mathbalarka

Math Team
CRGreathouse said: