February 5th, 2014, 10:03 AM  #1 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 937 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  PreQ&A
While we're working out the specifics for a questionandanswer thread, let's have a questionandanswer 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: PreQ&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: 937 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: PreQ&A Quote:
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: PreQ&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,778 Thanks: 361  Re: PreQ&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: PreQ&A Quote:
 
February 6th, 2014, 02:43 AM  #7  
Math Team Joined: Apr 2010 Posts: 2,778 Thanks: 361  Re: PreQ&A
I believe CRG gave the answer here. To answer his bonusquestion, due to Schur's theorem. Quote:
 
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: PreQ&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: PreQ&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: PreQ&A Quote:
PS : Does this have anything to do with cyclotomic polynomials?  