My Math Forum Pre-Q&A
 User Name Remember Me? Password

 Math Events Math Events, Competitions, Meetups - Local, Regional, State, National, International

 February 5th, 2014, 10:03 AM #1 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Pre-Q&A 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?
 February 5th, 2014, 12:28 PM #2 Math Team     Joined: Mar 2012 From: India, West Bengal Posts: 3,871 Thanks: 86 Math Focus: Number Theory Re: Pre-Q&A This is hard. Just to confirm, you want nonnegative coefficients all in {0, ..., 9}, correct?
February 5th, 2014, 02:50 PM   #3
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
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.

 February 5th, 2014, 10:14 PM #4 Math Team     Joined: Mar 2012 From: India, West Bengal Posts: 3,871 Thanks: 86 Math Focus: Number Theory 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?
 February 6th, 2014, 02:21 AM #5 Math Team   Joined: Apr 2010 Posts: 2,780 Thanks: 361 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).
February 6th, 2014, 02:27 AM   #6
Math Team

Joined: Mar 2012
From: India, West Bengal

Posts: 3,871
Thanks: 86

Math Focus: Number Theory
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.

February 6th, 2014, 02:43 AM   #7
Math Team

Joined: Apr 2010

Posts: 2,780
Thanks: 361

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).

 February 6th, 2014, 02:49 AM #8 Math Team     Joined: Mar 2012 From: India, West Bengal Posts: 3,871 Thanks: 86 Math Focus: Number Theory Re: Pre-Q&A I am not familiar with Schur's theorem, so no comments.
 February 6th, 2014, 03:18 AM #9 Math Team     Joined: Mar 2012 From: India, West Bengal Posts: 3,871 Thanks: 86 Math Focus: Number Theory 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)
February 6th, 2014, 03:57 AM   #10
Math Team

Joined: Mar 2012
From: India, West Bengal

Posts: 3,871
Thanks: 86

Math Focus: Number Theory
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?

 Tags preqanda