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? 
Re: PreQ&A This is hard. Just to confirm, you want nonnegative coefficients all in {0, ..., 9}, correct? 
Re: PreQ&A Quote:
It is hard  and related to a talk I went to in this year's JMM. 
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? 
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). 
Re: PreQ&A Quote:

Re: PreQ&A I believe CRG gave the answer here. To answer his bonusquestion, due to Schur's theorem. Quote:

Re: PreQ&A I am not familiar with Schur's theorem, so no comments. 
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) 
Re: PreQ&A Quote:
PS : Does this have anything to do with cyclotomic polynomials? 
All times are GMT 8. The time now is 10:39 AM. 
Copyright © 2019 My Math Forum. All rights reserved.