The Math Thread

[beero1000]

Was thinking about this brain teaser today:

I have a polynomial p(x) with non-negative integer coefficients. If you give me an integer n, I will tell you the value of p. Find an approach that uses the optimal number of queries in order to completely determine my polynomial. How many queries does it take?

I think I posted this here already (at some point and in some incarnation of the board). It's still a good one if you haven't seen it, or don't remember. The answer is much lower than might seem possible initially (it might actually initially seem impossible ). Anyway, got to thinking about the multivariate case, which I don't think I'd really considered before:

I have a polynomial p(x₁,x₂,...,x_m) with non-negative integer coefficients. If you give me integers n₁,n₂,...,n_m, I will tell you the value of p(n₁,n₂,...,n_m). Find an approach that uses the optimal number of queries in order to completely determine my polynomial. How many queries does it take?

Think I can answer this one too. It's still really low.

 

[Bomb#20]

Was thinking about this brain teaser today:

I have a polynomial p(x) with non-negative integer coefficients. If you give me an integer n, I will tell you the value of p. Find an approach that uses the optimal number of queries in order to completely determine my polynomial. How many queries does it take?

I think I posted this here already (at some point and in some incarnation of the board). It's still a good one if you haven't seen it, or don't remember. The answer is much lower than might seem possible initially (it might actually initially seem impossible ). Anyway, got to thinking about the multivariate case, which I don't think I'd really considered before:

I have a polynomial p(x₁,x₂,...,x_m) with non-negative integer coefficients. If you give me integers n₁,n₂,...,n_m, I will tell you the value of p(n₁,n₂,...,n_m). Find an approach that uses the optimal number of queries in order to completely determine my polynomial. How many queries does it take?

Think I can answer this one too. It's still really low.

I think I can do it with one query.

 

[Phil Scott]

I'm saying 2, but am happy to be outsmarted.

 

[Kharakov]

One? Really? I googled Phil's result, and it makes perfect logical sense, so it technically took me 3 queries. I was thinking along the lines of the answer anyway, but was lazy, so after I grabbed pen and paper... googled.

And beero, you did the same damn pun again... that gave me the answer last time.

I'm so smart, I have an answer, and my paper looks like:

 

[Phil Scott]

Well, without spoiler warnings: query with n = 1 to get an upper bound on the maximum coefficient b. Then query with that upper bound, convert the answer to base b + 1, and read off the coefficients.

 

[Kharakov]

Was thinking about this brain teaser today:

I have a polynomial p(x) with non-negative integer coefficients. If you give me an integer n, I will tell you the value of p. Find an approach that uses the optimal number of queries in order to completely determine my polynomial. How many queries does it take?

I think I posted this here already (at some point and in some incarnation of the board). It's still a good one if you haven't seen it, or don't remember. The answer is much lower than might seem possible initially (it might actually initially seem impossible ). Anyway, got to thinking about the multivariate case, which I don't think I'd really considered before:

I have a polynomial p(x₁,x₂,...,x_m) with non-negative integer coefficients. If you give me integers n₁,n₂,...,n_m, I will tell you the value of p(n₁,n₂,...,n_m). Find an approach that uses the optimal number of queries in order to completely determine my polynomial. How many queries does it take?

Think I can answer this one too. It's still really low.

I think I can do it with one query.

That sounds like a limit.... care to explain?

 

[Bomb#20]

Was thinking about this brain teaser today:

I have a polynomial p(x) with non-negative integer coefficients. If you give me an integer n, I will tell you the value of p. ...
I have a polynomial p(x₁,x₂,...,x_m) with non-negative integer coefficients. If you give me integers n₁,n₂,...,n_m, I will tell you the value of p(n₁,n₂,...,n_m).

I think I can do it with one query.

That sounds like a limit.... care to explain?

He didn't specify how I give him the integers.

So all I need to do is give him integers he can't do any calculations on. For example, I tell him to plug in the kissing numbers in 9, 10 ... m+8 dimensions. So to keep his promise he'll have to give me the value of p(n₁,n₂,...,n_m) not as a sequence of digits but as an algebraic expression in terms of kissing numbers, and then I can just read off his coefficients.

 

[Kharakov]

\(a_{_{_{1 \to m}}}\)

 

[lpetrich]

Phil Scott's algorithm requires only two queries, and it can do polynomials with any degree. I don't see how one can beat that.

 

[Kharakov]

Phil Scott's algorithm requires only two queries, and it can do polynomials with any degree. I don't see how one can beat that.

Bomb was joking....


How many queries, with the restriction no p(1) and p(-1)?


Prove that you totally obfuscate the polynomial* by inputting (nth primorial)^n as n-->infinity.

*hide your

Show

answer

 

[Bomb#20]

Phil Scott's algorithm requires only two queries, and it can do polynomials with any degree. I don't see how one can beat that.

Bomb was joking....

Seriously though...

Granted that a general solution in one query is impossible because for any query there exist polynomials that won't leak information about their coefficients, how likely are you to hit one? If they're a sparse set in the space of polynomials, and the guy posing the polynomial isn't allowed to look at the query before he picks his polynomial, then a solution in one query that probably makes the polynomial leak its coefficients should be feasible.

How many queries, with the restriction no p(1) and p(-1)?

Shouldn't matter. Pick p(2) and you still get an upper bound, so PS's algorithm will still work.

Prove that you totally obfuscate the polynomial* by inputting (nth primorial)^n as n-->infinity.

*hide your

Show

answer

Show

Define "obfuscate".

 

[beero1000]

Well, without spoiler warnings: query with n = 1 to get an upper bound on the maximum coefficient b. Then query with that upper bound, convert the answer to base b + 1, and read off the coefficients.

That is the way it's done, though with decimal notation you might as well query with a sufficiently large power of 10 so you don't have to convert to a different base.

That sounds like a limit.... care to explain?

He didn't specify how I give him the integers.

So all I need to do is give him integers he can't do any calculations on. For example, I tell him to plug in the kissing numbers in 9, 10 ... m+8 dimensions. So to keep his promise he'll have to give me the value of p(n₁,n₂,...,n_m) not as a sequence of digits but as an algebraic expression in terms of kissing numbers, and then I can just read off his coefficients.

Sneaky, but I also didn't specify how I give you the answer either...

Seriously though...

Granted that a general solution in one query is impossible because for any query there exist polynomials that won't leak information about their coefficients, how likely are you to hit one? If they're a sparse set in the space of polynomials, and the guy posing the polynomial isn't allowed to look at the query before he picks his polynomial, then a solution in one query that probably makes the polynomial leak its coefficients should be feasible.

I'd argue that you'd only be able to manage it in one query if we restrict the polynomials to (the equivalent of) a 1D subspace of polynomials. So, if we are allowed multiples of a fixed polynomial, you can just query a non-root point and figure out which multiple with one response. Once there are two independent polynomial options, I can take multiples so that you wouldn't be able to guarantee that you'd could distinguish them.

How many queries, with the restriction no p(1) and p(-1)?

Shouldn't matter. Pick p(2) and you still get an upper bound, so PS's algorithm will still work.

Yeah, any positive first query will work. I wouldn't use p(-1) though...

Anyone figure out the multivariate version?

 

[Bomb#20]

Sneaky, but I also didn't specify how I give you the answer either...

Touche.

If they're a sparse set in the space of polynomials, and the guy posing the polynomial isn't allowed to look at the query before he picks his polynomial, then a solution in one query that probably makes the polynomial leak its coefficients should be feasible.

I'd argue that you'd only be able to manage it in one query if we restrict the polynomials to (the equivalent of) a 1D subspace of polynomials. So, if we are allowed multiples of a fixed polynomial, you can just query a non-root point and figure out which multiple with one response. Once there are two independent polynomial options, I can take multiples so that you wouldn't be able to guarantee that you'd could distinguish them.

Of course -- I'm not talking about a guarantee, or a proof, or getting a paper past peer review. I'm just talking about winning a bar bet.

Anyone figure out the multivariate version?

Seems like a straightforward extension from PS's solution for 1 variable. If you start with p(2) instead of p(1) you should get an upper bound on the degree as well as on the coefficients. Then on the second round you query with m sufficiently large powers of 10 instead of just 1, and make sure they're all sufficiently large factors away from one another. Any reason that wouldn't work?

 

[Don2 (Don1 Revised)]

What kind of precision is needed when we throw big numbers back into polynomial?

 

[Kharakov]

10^m will give you 0 gaps in the answer for differing polynomials.

 

[beero1000]

Anyone figure out the multivariate version?

Seems like a straightforward extension from PS's solution for 1 variable. If you start with p(2) instead of p(1) you should get an upper bound on the degree as well as on the coefficients. Then on the second round you query with m sufficiently large powers of 10 instead of just 1, and make sure they're all sufficiently large factors away from one another. Any reason that wouldn't work?

That would work, and is essentially what I did as well, although the pedant in me wants you to explicitly specify how you'd determine what counts as 'sufficiently large'. ;-)

What kind of precision is needed when we throw big numbers back into polynomial?

I think you'd be fine rounding to the nearest whole number.

 

[Don2 (Don1 Revised)]

I am taking a wild stab at this.

n_i = 10^q^d^m^i. for i in 1 to m

q = p(2)
d = log base 2 of p(2) [rounded up]

Yeah, so I am completely making this up.

 

[Kharakov]

nm...

 

[Kharakov]

Rotation groups

 

[Underseer]

I am an empiricist and I care not for damn proofs!

"Empiricist"?

No. That doesn't apply to math. Either you can prove it or you can't, and you clearly can't.