My Math Forum (http://mymathforum.com/math-forums.php)
-   Math Events (http://mymathforum.com/math-events/)
-   -   Pre-Q&A (http://mymathforum.com/math-events/41264-pre-q.html)

 CRGreathouse February 5th, 2014 10:03 AM

Pre-Q&A

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 February 5th, 2014 12:28 PM

Re: Pre-Q&A

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

 CRGreathouse February 5th, 2014 02:50 PM

Re: Pre-Q&A

Quote:
 Originally Posted by mathbalarka 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 February 5th, 2014 10:14 PM

Re: Pre-Q&A

[color=#C0C0C0]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[/color]

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 February 6th, 2014 02:21 AM

Re: Pre-Q&A

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 February 6th, 2014 02:27 AM

Re: Pre-Q&A

Quote:
 Originally Posted by Hoempa 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 February 6th, 2014 02:43 AM

Re: Pre-Q&A

I believe CRG gave the answer here. To answer his bonusquestion, due to Schur's theorem.
Quote:
 Originally Posted by [color=#AA0000 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 February 6th, 2014 02:49 AM

Re: Pre-Q&A

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

 mathbalarka February 6th, 2014 03:18 AM

Re: Pre-Q&A

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 February 6th, 2014 03:57 AM

Re: Pre-Q&A

Quote:
 Originally Posted by CRGreathouse 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?

All times are GMT -8. The time now is 10:39 AM.