My Math Forum  

Go Back   My Math Forum > Math Forums > Math Events

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


Reply
 
LinkBack Thread Tools Display Modes
February 5th, 2014, 10:03 AM   #1
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 933

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?
CRGreathouse is offline  
 
February 5th, 2014, 12:28 PM   #2
Math Team
 
mathbalarka's Avatar
 
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?
mathbalarka is offline  
February 5th, 2014, 02:50 PM   #3
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 933

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.
CRGreathouse is offline  
February 5th, 2014, 10:14 PM   #4
Math Team
 
mathbalarka's Avatar
 
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?
mathbalarka is offline  
February 6th, 2014, 02:21 AM   #5
Math Team
 
Joined: Apr 2010

Posts: 2,778
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).
Hoempa is offline  
February 6th, 2014, 02:27 AM   #6
Math Team
 
mathbalarka's Avatar
 
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.
mathbalarka is offline  
February 6th, 2014, 02:43 AM   #7
Math Team
 
Joined: Apr 2010

Posts: 2,778
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).
Hoempa is offline  
February 6th, 2014, 02:49 AM   #8
Math Team
 
mathbalarka's Avatar
 
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.
mathbalarka is offline  
February 6th, 2014, 03:18 AM   #9
Math Team
 
mathbalarka's Avatar
 
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)
mathbalarka is offline  
February 6th, 2014, 03:57 AM   #10
Math Team
 
mathbalarka's Avatar
 
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?
mathbalarka is offline  
Reply

  My Math Forum > Math Forums > Math Events

Tags
preqanda



Thread Tools
Display Modes






Copyright © 2017 My Math Forum. All rights reserved.