Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose I know the following information about a function :

1) Its a polynomial (not an explicit equation, neither the roots nor the degree is known)

2) I have managed to find an algebraic relation between some of the roots (mind you I do not know the roots explicitly, just the form of the algebraic relation is known to me).

Now given this information can one say something about the polynomial itself ?

Now what do I seek for? Well, information on something like the divisors of the degree of the polynomial, or say something about the Galois group of the polynomial may be .... so you can say am asking an inverse question.

I understand that under these very general condition the problem may not even be well posed. I actually have more information about the polynomial in the particular case I encountered it ... the polynomial is a 0-1 polynomial ...some of the roots lie in the unit circle... etc. etc.

But certainly there would be instances of similar problems (with more information available about the polynomial/ the nature and number of algebraic relations that are available etc.) which has been dealt with ?

So, I wanted to ask the question in a more general setting. Any variant of this I would say is quite interesting. So you can assume different kind of condition on the roots, coefficient algebraic relation,

I will greatly appreciate if some one can point out where I should be looking. Reference to literature where such a problem has been dealt with would be great.

Regards

Vagabond

share|improve this question
add comment

3 Answers

up vote 3 down vote accepted

This is rather vague but regarding relations between roots of a polynomial you may try some of Chris Smyth's papers as a starting point. For instance, this one:

C. J. Smyth, Conjugate algebraic numbers on conics, Acta Arith. 40 (1982), 333–346.

share|improve this answer
    
@Nikita the paper you suggested really looks interesting. I actually was looking for some examples like these where an inverse problem has been solved. I know I have been rather vague in asking the question, because I did not want to specify a particular problem with the hope that someone solves it for me. Do you know some more examples where such inverse problems has been dealt with ? If you do not mind can you suggest some other references as well. In any case thanks a lot. I will go through it and see if I can find what I am looking for. –  Vagabond Sep 27 '10 at 10:10
1  
Here's another one: Additive and multiplicative relations connecting conjugate algebraic numbers CJ Smyth - Journal of Number Theory, 1986 ... and then look up all the papers which refer to it (via scholar.google, for example). There are quite a few, I believe. –  Nikita Sidorov Sep 27 '10 at 14:28
    
I reached there already :-) I will follow the trail. Thank you once more, I do not think on my own I would have found these. –  Vagabond Sep 27 '10 at 14:35
1  
My pleasure. In fact, I've discovered these by accident myself - kinda hard to believe this stuff is so recent. –  Nikita Sidorov Sep 27 '10 at 15:55
add comment

I would guess that the most general way of going about this would be through the use of Gröbner bases, since you did mention that the root relations you have are algebraic in nature. To use a simple instance, here's how to reconstruct a quadratic polynomial in Mathematica from some simple algebraic relations of the roots a and b:

GroebnerBasis[{(x - a)(x - b), a + b - 5, a - 3b}, x, {a, b}]

(in English: find the (unique?) quadratic whose roots have a sum of 5 and has one root that is thrice the other)

which returns the polynomial $16x^2-80x+75$ (verify that the roots of this polynomial satisfy the preset conditions).

Of course, as with most algorithms of such generality, I would imagine this to be excruciatingly slow on a problem of even moderate complexity. Exploiting every little bit of structure present in your problem (which you say you have) would certainly help a great deal.

share|improve this answer
    
@J.M Can you suggest a good reference for Gröbner bases, why it works? Also if you could give me a reference where such a problem has been solved using Gröbner bases? A worked out example :) The thing is I want to infer something about the entire solution set here, like if the solution set be generated by some finite number of solutions or be divisible by some polynomials etc. ? –  Vagabond Sep 27 '10 at 12:14
    
@JM the wiki link does not work, just thought would let you know so you can edit. –  Vagabond Sep 27 '10 at 12:18
1  
@Vagabond: Link fixed, thanks. I'm still learning about these myself, so I don't have all the details at hand, but the last time I asked a question of this sort, I was pointed to these books: amazon.com/dp/0387979719 and amazon.com/dp/0387356509 . –  J. M. Sep 27 '10 at 13:27
    
Thanks for the link J.M and the references. Just a mild curiosity, you said you were thinking about a similar question, if you do not mind could you explain in what context you encountered it ? –  Vagabond Sep 27 '10 at 16:40
    
@Vagabond: as I said, Gröbner bases are widely applied in solving algebraic problems symbolically. My case was concerned with systematically determining the Cartesian equation of an algebraic plane curve represented parametrically or in polar coordinates. I was able to apply a few tricks from school, but learning how to use Gröbner bases properly still dazzled me. :) –  J. M. Sep 27 '10 at 17:31
add comment

Such questions formed a substantial part of the classical "theory of equations", before Galois theory was formulated. For example, there is a book by Burnside on theory of equations, that is easy to find on Google Books. Whether you can get anything out of this, without knowing even the degree of the equation, is another matter. That suggests that you have some information about a field extension of unknown finite degree? Some theory about Tschirnhaus transformations might be of use to you, but I wonder who looks at those explicitly these days (maybe computer algebra people)? I get the impression of numerous special cases that are handled by direct algebra (tortuous exam questions, certainly).

share|improve this answer
    
But aren't inverse problem interesting. If not, then I guess they ought to be. –  Vagabond Sep 27 '10 at 10:18
1  
Man muß immer umkehren! –  Charles Matthews Sep 27 '10 at 13:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.