A random walk through mathematics -- mostly through the random part.
17 March 2010
A puzzle about polynomials
I have a polynomial, P, with nonnegative integer coefficients. You want to know what it is. For any algebraic number x, you're allowed to ask me what P(x) is. How many questions do you have to ask me to be sure that you know what P is?
10 comments:
Anonymous
said...
Depends on the degree of the polynomial. Any polynomial of degree N is uniquely determined by its values at N+1 points via Lagrange Interpolation.
Can we do any better knowing the coefficients are non-negative? I can't see how myself, but given it was specified in the question it is likely to be useful.
2: First ask for the value at 1, this gives you the sum of the coefficients. Now ask for the value at b=this sum +1. Since all coefficients are <b, we can read the coefficients by reading P(b) in base b.
@Julian: In this solution you also need that it is integers. I don't know if it is possible to determine P if we only know that it has non-negative coefficients.
The fact that x can be algebraic, on the other hand, is a bit of a red herring. I was just ruling out the trick of evaluating P at a transcendental. This solution works even if you're only allowed to evaluate P at integers.
I take it the "evaluate at a transcendental" trick is that the only way to express P(pi) is as P(pi), so asking for the value at pi would immediately yield you P?
It's not obvious to me. For instance, if you restrict the coefficients of powers of pi to rationals I'm not sure it's possible to express sqrt(pi) as a finite linear combination of powers of pi.
My comment was that I don't think there is any good way to express a polynomial with integer coefficients at pi except as a linear combination of powers of pi, which gives you the polynomial coefficients immediately.
@Qiaochu Yuan: If you are expressing a number as a non-negative integer linear combination of powers of pi, then yes, it is possible to determine the coefficients. This is because the set of non-negative integer linear combination of powers of pi is discrete -- indeed, there are only finitely many combinations below any given cutoff. This means that if you have a sufficiently good approximation to a real number (which is how computable reals are usually presented), then you can tell which combination is meant.
If you are using arbitrary integer linear combinations, then there's no chance. There are infinitely many combinations that fall into any given interval.
10 comments:
Depends on the degree of the polynomial. Any polynomial of degree N is uniquely determined by its values at N+1 points via Lagrange Interpolation.
Anonymous,
Can we do any better knowing the coefficients are non-negative? I can't see how myself, but given it was specified in the question it is likely to be useful.
2: First ask for the value at 1, this gives you the sum of the coefficients. Now ask for the value at b=this sum +1. Since all coefficients are <b, we can read the coefficients by reading P(b) in base b.
@Julian: In this solution you also need that it is integers. I don't know if it is possible to determine P if we only know that it has non-negative coefficients.
@Sune,
Nice!
Sune, that's the solution I had in mind.
The fact that x can be algebraic, on the other hand, is a bit of a red herring. I was just ruling out the trick of evaluating P at a transcendental. This solution works even if you're only allowed to evaluate P at integers.
I take it the "evaluate at a transcendental" trick is that the only way to express P(pi) is as P(pi), so asking for the value at pi would immediately yield you P?
Is it obvious that there exists a computable procedure to write a computable real number as a linear combination of the powers of pi?
It's not obvious to me. For instance, if you restrict the coefficients of powers of pi to rationals I'm not sure it's possible to express sqrt(pi) as a finite linear combination of powers of pi.
My comment was that I don't think there is any good way to express a polynomial with integer coefficients at pi except as a linear combination of powers of pi, which gives you the polynomial coefficients immediately.
@Qiaochu Yuan: If you are expressing a number as a non-negative integer linear combination of powers of pi, then yes, it is possible to determine the coefficients. This is because the set of non-negative integer linear combination of powers of pi is discrete -- indeed, there are only finitely many combinations below any given cutoff. This means that if you have a sufficiently good approximation to a real number (which is how computable reals are usually presented), then you can tell which combination is meant.
If you are using arbitrary integer linear combinations, then there's no chance. There are infinitely many combinations that fall into any given interval.
What if you ask for only one evaluation and that at 0.1?
Post a Comment