[Math] How to validate that two math expressions are equal

education

Let's say you have a few expressions like the following:

$$\begin{array}((x+17)^2 \\
x^2 + 34x + 289 \end{array} \\
288 + \frac{x^2}{2} + \frac{x^2}{2} + 34x + 1 \\
[…]
$$

You get the idea: there's an infinite number of ways of representing the same expression. The challenge is that my application is validating answers to math problems, input by math students practicing a certain concept. I'd like to make sure that whenever they submit an answer, the checker is completely insensitive to the issues of ordering, simplification, formatting etc. which would be plain frustrating. I'd also ideally like to support more than one variable such as x, y, z in the same expression.

What's a reliable way to check that two expressions are the same? The most brute force way I can think of would be to just plug a number into each variable of each expression and see what the result is.

I have a hunch however that there might be ways of getting false positives this way. That, and I might be either missing something really obvious about this, or there might be a better way of doing the comparison.

Would love to hear what you think.

Best Answer

In general, this is a hard problem. For classes of expressions for which there is a canonical form, such as polynomials (in any number of variables), the answer is straightforward: two expressions are equal if and only if they have the same canonical form. (A canonical form means that for each expression there is one and only one canonical expression to which it is equal, and there is an effective procedure for calculating the canonical form of any given expression.) Then you can get an algorithm for comparing two expressions: calculate the canonical form for each expression and check to see if the canonical forms are identical.

Algebra students learn to do exactly this in order to decide themselves if two polynomials are equal. (Students of arithmetic learn an analogous method for deciding if two arithmetic expressions are equal, for example converting the expression $2\cdot(3+4)$ into the canonical form $14$; this algorithm is a subroutine of the one that reduces polynomial expressions to canonical form.) A canonical form for polynomials is to combine all the like terms, list the terms in descending order of degree, with the terms of equal degree listed in lexicographic order by the variables they contain, or something of that sort. Calculating a canonical form for an arbitrary polynomial is not a difficult matter. It is the sort of thing a competent programmer can produce in a couple of hours; or as several other people here have suggested you could put the solutions into a computer algebra system, which will contain exactly this sort of algorithm for several different sorts of expressions.

But for more general expressions it can be extremely difficult, or even impossible, to decide of the two expressions are equal. There is no canonical form, and recognizing when two particular expressions are equal can be a major theorem. For example, consider the expressions $\cos 2x$ and $\left(\cos x\right)^2 - \left(\sin x\right)^2$. These are equal, but not obviously so. Or for a more difficult example, consider the two expressions $$0$$ and $$\sum_{a,b,c > 1\atop n>2} I(a^n + b^n - c^n)$$ (where $I(x)$ denotes the function which has $I(0)=1$ and $I(x)=0$ for $x\ne 0$). It was conjectured for some time that these two expressions were equal, but the proof turned out to be somewhat tricky.

The previous paragraph was a joke, but it is a serious joke: a substantial part of mathematics is precisely how to perform such calculations and to recognize when two different-seeming expressions are equal. Euler is famous (among other things) for recognizing that $e^{ix}$ and $\cos x + i\sin x$ are equal expressions. Leaving aside jokes, a theorem of Daniel Richardson says that for a fairly small, fairly natural class of expressions, there is no method that can reliably determine equality in all cases.

So to get an answer, you need to be more specific about what your question is. If you only need to compare polynomials, the answer is fairly straightforward. If your expressions are more complicated than that, there may or may not be an answer; it depends on what is in them.

[ Addendum: I see that you have added comments saying that you are only interested in polynomials, and that you want to know if your idea of substituting test values for $x$ is sound. It is sound, but plugging in one number is not enough, even for the simples polyomials. The polynomials $x+1, 3x-1$, and $3-x$ all have the same value at $x=1$. But you can easily avoid false positives by checking $n+1$ different values for an $n$th-degree polynomial. A polynomial of degree $n$ is completely determined by its values at $n+1$ points, so if two polynomials of degree $n$ agree at $n+1$ different points you can be sure they are identical; it does not even matter which $n+1$ values you sample. (In the example above, any value of $x$ other than $x=1$ is sufficient to distinguish the three polynomials.) Similarly if the polynomial has three variables $x$, $y$, and $z$, of degrees $n_x, n_y, $ and $n_z$, it suffices to select $n_x+1$ values for $x$, $n_y+1$ values for $y$, and $n_z+1$ values for $z$, and then check all $(n_x+1)(n_y+1)(n_z+1)$ triples of those values. ]