Wednesday, June 22, 2016

[bltothha] Testing equality of algebraic expressions

Given an algebraic expression, test whether it is identical to zero for all possible assignments of variables.  How difficult is this problem?  It probably depends on the operators and functions in the expression.  I wouldn't be surprised if it is Turing incomputable.

Suppose we limit to asking whether it is zero for all but a set of measure zero, where it could be undefined or take a value different from zero.  For example, (x/x)-1.  Is the problem easier?

For all but a set of finite measure (area)?  Probably look at asymptotic behavior.

Pick a few random values and plug them into variables.  Evaluate and test if the result is equal to zero (this is potentially tricky).  If it is nonzero on a set of measure zero, then one has to have been tremendously unlucky to find a nonzero.

Difficult cases: a expression that is nonzero only for small neighborhood around the first hypothetical counterexample to the Riemann hypothesis.  Or around all counterexamples, perhaps summing up to an infinite area.

An expression which zero outside of a sphere of radius G, where G is some huge finite number.

Zero for all irrational numbers, nonzero for rationals (Dirichlet function).  Or, zero for all non-computable numbers, nonzero for computable numbers.

No comments :