Author |
Topic: Polynomials with no complex roots (Read 1224 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Polynomials with no complex roots
« on: Apr 23rd, 2009, 4:04pm » |
 Quote  Modify
|
Find all polynomials with all coefficients 1 or -1 which have no complex roots (i.e all roots are real).
|
|
 IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Polynomials with no complex roots
« Reply #1 on: Apr 24th, 2009, 6:15am » |
Quote Modify
|
Just to clarify, do you mean all coefficients are +- 1, or all coefficients are +-1 or 0?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Polynomials with no complex roots
« Reply #2 on: Apr 24th, 2009, 8:23am » |
Quote Modify
|
+- 1.
Each power appears, with either a + or - sign before it.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Polynomials with no complex roots
« Reply #3 on: Apr 25th, 2009, 11:16am » |
Quote Modify
|
Are you allowing finite polynomials, or requiring infinite polynomials?
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Polynomials with no complex roots
« Reply #4 on: Apr 25th, 2009, 11:24am » |
Quote Modify
|
Requiring finite. So if it has degree n, the coefficients of 1, x, x^2, ... , x^n are all either +1 or -1.
This question seems hard; I'm curious what the trick is. My guess for the answer is that
the degree can be at most 3, and the ones of degree at most 3 can be found easily case by case.
|
| « Last Edit: Apr 25th, 2009, 11:27am by Obob » |
IP Logged |
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: Polynomials with no complex roots
« Reply #5 on: Apr 25th, 2009, 11:38am » |
Quote Modify
|
Consider thinking about cyclotomic polynomials
(which often, but not always, have all coefficients
in {1,-1}) and Lehmer's Mahler-measure problem,
since the polynomial in question has exactly the form
of Lehmer's divisibility restriction.
|
|
IP Logged |
Regards,
Michael Dagg
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Polynomials with no complex roots
« Reply #6 on: Apr 26th, 2009, 10:16am » |
Quote Modify
|
This can be done using elementary mathematics.
btw, Obob, you guessed right.
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Polynomials with no complex roots
« Reply #7 on: Apr 30th, 2009, 6:29am » |
Quote Modify
|
Are there any hints you can give without totally giving this away? Or are people still trying to come up with a proof?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Polynomials with no complex roots
« Reply #8 on: Apr 30th, 2009, 7:50am » |
Quote Modify
|
I can still give hidden hints. People who don't want to see can avoid that...
Hint: You don't have to consider all coefficients being 1 or -1 to prove the upper bound on n.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Polynomials with no complex roots
« Reply #9 on: Apr 30th, 2009, 12:29pm » |
Quote Modify
|
on Apr 30th, 2009, 7:50am, Aryabhatta wrote:
Hint: You don't have to consider all coefficients being 1 or -1 to prove the upper bound on n. |
|
Only sum and product? 
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Polynomials with no complex roots
« Reply #10 on: Apr 30th, 2009, 1:45pm » |
Quote Modify
|
on Apr 30th, 2009, 12:29pm, Barukh wrote:
Only sum and product?
|
|
Close...  -
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Polynomials with no complex roots
« Reply #11 on: May 11th, 2009, 10:49am » |
Quote Modify
|
Just so I don't forget, here is one (partial) solution:
Suppose the roots are r_1, r_2, ... , r_n.
We have that
Sum (r_i)^2 = (Sum r_i)^2 - 2 * (Sum r_i * r_j) which is either 1 - 2 *(-1) or 1 - 2(1).
Since it is non-negative, it can only be 3.
Thus Sum r_i^2 = 3.
Using AM >= GM we get
Sum r_i^2 / n >= (Product r_i^2)^(1/n) = 1.
This n <= Sum r_i^2 = 3.
btw the problem is from here: http://www.math.washington.edu/~challenge/archive/20090414/index.php
|
|
IP Logged |
|
|
|
jpk2009
Junior Member
Gender: 
Posts: 60
|
|
Re: Polynomials with no complex roots
« Reply #12 on: May 13th, 2009, 5:08pm » |
Quote Modify
|
Isn't the problem statement here as posted different from the problem statement in the pdf? I mean, "all coefficients 1 or -1" means they are all "either 1 or -1". In the pdf, the statement just means that they can be any combination of 1 or -1.
I just noticed that Obob interpreted it like that too.
|
| « Last Edit: May 13th, 2009, 5:15pm by jpk2009 » |
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Polynomials with no complex roots
« Reply #13 on: May 13th, 2009, 5:40pm » |
Quote Modify
|
No, I interpreted it as each coefficient can independently be either +1 or -1. Sorry if my language was confusing. The polynomial 1 + x + ... + x^n pretty clearly only has all real roots if and only if n = 1, since otherwise exp(2pi * i / (n+1)) is a nonreal root.
|
|
IP Logged |
|
|
|
jpk2009
Junior Member
Gender:
Posts: 60
|
|
Re: Polynomials with no complex roots
« Reply #14 on: May 13th, 2009, 6:01pm » |
Quote Modify
|
Right. According to the pdf, they can independently be either 1 or -1. But when you state "all coefficients 1 or -1" then this does not seem to be about independence but about all of them as a whole either being 1 or -1. Inclusion of "all" seems to lead to confusion to me.
Besides, "no complex roots" does not mean "real roots".
|
| « Last Edit: May 13th, 2009, 6:12pm by jpk2009 » |
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Polynomials with no complex roots
« Reply #15 on: May 13th, 2009, 7:37pm » |
Quote Modify
|
on May 13th, 2009, 6:01pm, jpk2009 wrote:
Besides, "no complex roots" does not mean "real roots".
|
|
Sure it does, provided you interpret "complex" as "properly complex," i.e. not real.
|
|
IP Logged |
|
|
|
jpk2009
Junior Member
Gender:
Posts: 60
|
|
Re: Polynomials with no complex roots
« Reply #16 on: May 14th, 2009, 9:22am » |
Quote Modify
|
"Properly complex"?
Can anyone point me to a book that states "properly complex" so to make this distinction, or maybe even better "complex number proper"? The empty set is not "properly complex" but that empty set contains no real numbers either. That seems to be a precise statement too.
So, if you asked "Find all polynomials which have no properly complex solutions.", I am sure someone would call for clarification because the empty set is a correct answer too.
It is clear to me what is meant in the problem statement, but I think we are talking more about a "loosely speaking" description rather than one that is "precise", after all, all polynomials have complex solutions and that is not only a proper statement but it is precise.
I also know that math majors tend to argue about definitions because I hear them doing it all the time. I guess this is one of those times....
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Polynomials with no complex roots
« Reply #17 on: May 14th, 2009, 9:58am » |
Quote Modify
|
on May 14th, 2009, 9:22am, jpk2009 wrote:"Properly complex"?
Can anyone point me to a book that states "properly complex" so to make this distinction, or maybe even better "complex number proper"? The empty set is not "properly complex" but that empty set contains no real numbers either. That seems to be a precise statement too.
So, if you asked "Find all polynomials which have no properly complex solutions.", I am sure someone would call for clarification because the empty set is a correct answer too.
It is clear to me what is meant in the problem statement, but I think we are talking more about a "loosely speaking" description rather than one that is "precise", after all, all polynomials have complex solutions and that is not only a proper statement but it is precise.
I also know that math majors tend to argue about definitions because I hear them doing it all the time. I guess this is one of those times.... |
|
If you read the first three posts, the problem statement should be clear enough (if there was any doubt).
The first post clearly states that all roots are required to be real (in parentheses)
The third post (response to second) says that each can be independently 1 or -1.
As to "properly complex" here is a book that has it:
Analysis and mathematical physics by Hans Triebel, page number 41, Theorem 3.
Analysis and mathematical physics
By Hans Triebel
Edition: illustrated
Published by Springer, 1986
ISBN 9027720770, 9789027720771
456 pages
|
| « Last Edit: May 14th, 2009, 10:02am by Aryabhatta » |
IP Logged |
|
|
|
jpk2009
Junior Member
Gender:
Posts: 60
|
|
Re: Polynomials with no complex roots
« Reply #18 on: May 14th, 2009, 8:52pm » |
Quote Modify
|
Thanks. What you said in your first few lines does indicate that clarity was desired. That is what I meant to begin with, apart from the fact that the usage of "all" implies the possibility of two different problems.
As for "properly complex" I will have to see if our library has that book, it probably does, but since you mention that it is in a theorem, I must guess that it is used "loosely speaking", as I doubt that anyone can show me a "definition" from a reviewed book that uses that terminology. That's just not the way mathematicians make the distinction.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Polynomials with no complex roots
« Reply #19 on: May 14th, 2009, 11:41pm » |
Quote Modify
|
on May 14th, 2009, 8:52pm, jpk2009 wrote:Thanks. What you said in your first few lines does indicate that clarity was desired. That is what I meant to begin with, apart from the fact that the usage of "all" implies the possibility of two different problems.
As for "properly complex" I will have to see if our library has that book, it probably does, but since you mention that it is in a theorem, I must guess that it is used "loosely speaking", as I doubt that anyone can show me a "definition" from a reviewed book that uses that terminology. That's just not the way mathematicians make the distinction. |
|
If you read Obob's post which first mentions "properly complex", he also gives a definition and that is good enough. Why does it have to come from a book or be one of ways the "mathematicians make the distinction"?
Also, there will be plenty of "reviewed" books which say "not complex" when they mean real. Especially books that deal with roots of polynomials. Frankly, I don't understand your objections.
And, the fact that this problem was in Medium should have been enough to deduce that all the coefficients are independently 1 or -1 (otherwise it deserves be in the "trivial" forum).
Also, the clarity which Obob was after was not whether the coefficients are independent, but if some coefficients are allowed to be zero. As, sometimes, when "mathematicians" talk of "all" coefficients, they mean only the non-zero coefficients.
|
| « Last Edit: May 14th, 2009, 11:43pm by Aryabhatta » |
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Polynomials with no complex roots
« Reply #20 on: May 15th, 2009, 4:41am » |
Quote Modify
|
The fact of the matter is there is no good concise term for a number that is complex but not real. When good terminology does not exist, one can come up with terminology which describes the present situation. Mathematicians do this all the time. If it makes you happier, I could have made it a formal definition instead:
Definition. A complex number is properly complex if it is not real.
Your discussion of the empty set is irrelevant; while all members of the empty set are properly complex, this does not mean that a polynomial whose set of properly complex roots is the empty set has a properly complex root.
Despite the fact that I've never heard anybody use this particular term, my choice to use it is perfectly legal because I made it clear what I meant by the term. If we couldn't make new definitions without finding them in books, mathematics would be extremely verbose. For instance, suppose I am writing the very first paper about algebraic geometry, which is the study of simultaneous roots of polynomial equations. In algebraic geometry, a variety is (loosely speaking) a subset of the n-fold complex plane which is the common zero locus of arbitrarily many polynomials in n variables with coefficients in C. If I can't make this definition at the outset of my paper, then every time the word variety appears I have to make some summary of my definition of variety.
Mathematicians are only as precise as they need to be for a given audience. While teaching a class, they may make every detail extremely precise. While speaking with peers, they skip any details which the peer can reasonably be expected to understand. Hopefully while writing a paper for experts, they fill in most of the details, leaving only a few things that the reader should easily be able to fill in themselves.
|
| « Last Edit: May 15th, 2009, 6:18am by Obob » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print