21–30 of 39 posts
Just make the expressions into polynomials with variables x_1..x_k for the k different numbers, and see if they agree at (degree + 1) distinct points.
Just make the expressions into polynomials with variables x_1..x_k for the k different numbers, and see if they agree at (degree + 1) distinct points.
Could you please show the polynomial forms for these, and an example of your technique? 3*(8*(3/3)) = 24 3+((3*8)-3) = 24
x*(y*(x/x)) = f(x,y)
x+((x*y)-x) = g(x,y)
(1,1) => 1(1(1/1)) = 1 = 1+((1*1)-1) (1,0) => 0 for both (1,2) => 2 etc.
It's an old technique; Alan Perlis taught it to me. If two polynomials of degree d agree on more than d points, then their difference (of degree <= d) has more than d roots, so their difference must be 0.
Just make the expressions into polynomials with variables x_1..x_k for the k different numbers, and see if they agree at (degree + 1) distinct points.
Nice! Maybe rational functions rather than polynomials though, because division is allowed. Anyway, equality of rational functions is reducible to equality of polynomials.
I believe this is used in symbolic solvers to prove identities; that's the context where I learned it.
Within its domain, that's what the Oppen-Nelson simplifier did. Many provers since can do that. Amusingly, Plato, the first on-line teaching system, had a solver for that. It was used to check student's answers to math problems. It worked by plugging in some random numeric values and evaluating. If many sets of random values evaluated the same as the desired answer, it was accepted as equivalent.
what kind of math problems were the students supposed to solve? I ask because the approach you mention is still the best way we have of determining whether two polynomials are equivalent: https://en.wikipedia.org/wiki/Polynomial_identity_testing
Earlier quoted context omitted.
Could you please show the polynomial forms for these, and an example of your technique? 3*(8*(3/3)) = 24 3+((3*8)-3) = 24
I'm guessing two variables here; I didn't look too closely. x=3, y=8 x*(y*(x/x)) = f(x,y) x+((x*y)-x) = g(x,y) These are pretty obviously both xy, but rather than solve it, find the maximum degree, which is 2, and make a few points: (1,1) => 1 (1 (1/1)) = 1 = 1+((1*1)-1) (1,0) => 0 for both (1,2) => 2 etc. It's an old technique; Alan Perlis taught it to me. If two polynomials of degree d agree on more than d points,…
Earlier quoted context omitted.
Could you please show the polynomial forms for these, and an example of your technique? 3*(8*(3/3)) = 24 3+((3*8)-3) = 24
I'm guessing two variables here; I didn't look too closely. x=3, y=8 x*(y*(x/x)) = f(x,y) x+((x*y)-x) = g(x,y) These are pretty obviously both xy, but rather than solve it, find the maximum degree, which is 2, and make a few points: (1,1) => 1 (1 (1/1)) = 1 = 1+((1*1)-1) (1,0) => 0 for both (1,2) => 2 etc. It's an old technique; Alan Perlis taught it to me. If two polynomials of degree d agree on more than d points,…
Or you could cheat...jam them both into wolfram and see what comes out.
Earlier quoted context omitted.
I'm guessing two variables here; I didn't look too closely. x=3, y=8 x*(y*(x/x)) = f(x,y) x+((x*y)-x) = g(x,y) These are pretty obviously both xy, but rather than solve it, find the maximum degree, which is 2, and make a few points: (1,1) => 1 (1 (1/1)) = 1 = 1+((1*1)-1) (1,0) => 0 for both (1,2) => 2 etc. It's an old technique; Alan Perlis taught it to me. If two polynomials of degree d agree on more than d points,…
But your last sentence is only true among single-variable polynomials, isn't it? For example, f(x,y)=xy and g(x,y)=x^2 agree on infinitely many points.
Pick another value for x, do the same.
Pick a third...
I didn't prove this works, but I think it should. It is however exponential in the number of variables which may be seen as a downside.
Edit:
This can be proven by induction. Let V = (y, z, ...). Then the polynomial can be expressed as
p = (x-x2)(x-x3)f(V) + (x-x1)(x-3)g(V) + (x-x1)(x-x2)h(V), where x1, x2, x3 are the values we test for x. By inductive hypothesis we can prove each of f, g and h to be zero by testing. But if those are all zero then p is zero.
Isn't that the distributive property of multiplication over addition? There is a -1 that gets multiplied.