Pre-Q&A

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
While we're working out the specifics for a question-and-answer thread, let's have a question-and-answer thread!

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
Mar 2012
3,871
86
India, West Bengal
This is hard. Just to confirm, you want nonnegative coefficients all in {0, ..., 9}, correct?
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
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
Mar 2012
3,871
86
India, West Bengal
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
Apr 2010
2,780
361
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
Mar 2012
3,871
86
India, West Bengal
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
Apr 2010
2,780
361
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
Mar 2012
3,871
86
India, West Bengal
I am not familiar with Schur's theorem, so no comments.
 

mathbalarka

Math Team
Mar 2012
3,871
86
India, West Bengal
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
Mar 2012
3,871
86
India, West Bengal
CRGreathouse said:
While we're working out the specifics for a question-and-answer thread, let's have a question-and-answer thread!

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?
Why is 2 so hard? I can do with 1, for example : x^5 + x + 1 = (x^2(x - 1) + 1)*(x^2 + x + 1)

PS : Does this have anything to do with cyclotomic polynomials?