How do you validate that two math expressions are equal?

Question

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.

Answer 1

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. ]

Answer 2

@AlexandrKurilin I believe the mathematical approach is not the problem. The software is the key. Two expressions $A$ and $B$ are equal iff: you can go from $A$ to $B$, or you can go from $B$ to $A$, or you can go from $A$ to $C$ and from $B$ to $C$. Where go means that you only use iff operations.

As you mentioned, there might be infinitely many representations. So, solutions for your problem that come to mind are:

• Ask the students to express the solution in a fully simplified expression. This is application dependent, maybe some times it won't be unique. But as an example, if the answer must be a polynomial, then you can request them to factor it, or fully expand it and group like terms, etc.
• Provide a list of possible answers or answer templates. I am not particularly fond of multiple choices problems in math, but maybe you can provide them with guidelines of how the different possible answers might be expressed as. From there, creating a parser like you suggested would be easier.
• Use an engine like Mathematica or Mapple that can compare the solutions for you. The automation you are looking for might be achieved by coding in those programs. Here the math aspect of your question would be resolved fully.

Your suggestion of using values is very error prone for two reasons. 1. Unless you are coding in an environment with arbitrary precision algebra capabilities, then two different correct expressions might yield (slightly) different results. 2. Unless you test on every possible value for your variables, then you can't confirm the proposed solution is equal to your correct expression.

Considering this, then I would test over a list of test values and not just one. An easy way in one variable would be to define ends to a segment $a$ and $b$, and a step size $\delta$ and populate the list with $a$, $a+\delta$, $a+2\delta$,$\cdots$,$b$. Let's call them $x_1$, $x_2$,$\cdots$,$x_n$, and let $A(x)$ and $B(x)$ the two expressions to compare. Because of numeric errors, I would define a metric and a tolerance to compare them and declare them equal if, for instance, $$\sum_{i=1}^n\left[A(x_i)-B(x_i)\right]^2<\epsilon$$

The tolerance $\epsilon$ may need to be adapted for problems that have sensitive regions.

Answer 3

For polynomials you can expand all products and collect like terms to get a canonical form. Or you could compute the maximum possible degree d and check that two polynomials have the same values at d+1 points.