Solvable and Unsolvable Equations
Date: 01/18/2004 at 01:37:33 From: Glen Subject: understanding why certain equations can not be solved In Fermat's Last Theorem, the power n is not considered a variable. It appears impossible to solve the equation for n, even though n(a,b,c) is single valued for all "potential" non-trivial solutions. I'm interested in knowing how mathematicians recognize when a solution to an equation can never be found. Any description of the intuition mathematicians bring to bear on such questions would be interesting.
Date: 01/20/2004 at 10:18:10 From: Doctor Tom Subject: Re: understanding why certain equations can not be solved Hi Glen, You've asked a very interesting question, and part of the question is simply, "what do you mean by 'solved'?" Let me talk about a couple of examples to show what I mean: 1) Find a real number x such that x^2 = -1. We can show that this one can't be solved by simply saying that since x is real, it is either positive or negative, and if you square a positive number or a negative number, you always obtain a positive result and -1 is not positive. But what is often useful is to extend the system so that there is a solution. In the example above, we simply add the imaginary number i to the reals and all the other stuff that "has" to be there giving the set of complex numbers a + bi, where a and b are real. This is an amazingly good extension, since not only does it solve the single problem above, but it allows us to solve EVERY polynomial equation of the form: a x^n + b x^(n-1) + ... + k x + m = 0 (A) not only for real a, b, c, .. but also if they're complex. It becomes completely closed. 2) Following the same sort of example, what does it mean to "solve" an equation like the one labeled (A) above? If n < 5, we can write down the explicit solutions in terms of addition, subtraction, multiplication, division, and roots. But if n = 5 or more, it can be shown (using arguments from group theory and galois theory) that no such solution can be written down. So you have to decide for yourself whether these are "solvable". If n = 5, for example, and we are looking for a solution to one of those irreducible polynomials of degree 5, then we can't write it down using numbers and the primitive operations (addition, ...) but we can find all 5 roots to arbitrary arithmetic precision using numerical methods. If you want 100 decimal places, it's simply a matter of enough computing time. Is that "solved"? 3) For some important situations where the problem can't be solved, we simply give a name to the solution and study its properties. For example, the integral from 1 to t of (1/t) dt cannot be expressed in terms of polynomials, but what we do is declare the solution to be called "log(t)" and then we study the properties of the newly-defined function. We can numerically evaluate it for any t > 0, find relations with other functions, and so on, and in this case, the result is very valuable. We define its inverse as e^x, et cetera. Similar functions are the elliptic functions, modular functions, the error function and the Bessel functions found in complex analysis (among many others). These are defined to be the result of certain integrals that can't be expressed in terms of more "elementary" functions. In fact, it can be proved that the vast majority of indefinite integrals cannot be evaluated in terms of the elementary functions. The values exist, surely, but can't be expressed. Some of them, like the ones I mentioned above, come up so often that we just give them a name and study their properties. Your problem (to solve for n in Fermat's equation) CAN be solved numerically (if there is a solution). It's just that you can't write down a formula for it. In general, it is difficult to prove that you can't write down a formula, and as far as I know, proofs that particular functions cannot be written down explicitly are not easy to find. There are other "unsolvable" problems in the sense that you can prove that no solution exists. The classic example is called the "halting problem for Turing machines". Basically a Turing machine is a description of a computer with unlimited memory and a well-defined instruction set. Basically every computer made today is a Turing machine, except that the memory is bounded. So certain computer programs will go into an infinite loop, and others will halt with a solution, right? What would be great would be to write a computer program that would examine another computer program to see if it will halt or go into an infinite loop. No such program is possible; here's why. Suppose P is such a program such that if Q is any computer program P(Q) = 1 if Q eventually halts and P(Q) = 0 if Q does not halt. Let me write a new program R(Q) as follows: X: if P(Q) = 1 goto X What is R(R)? If R halts, then it doesn't. If R does not halt, then it does. No such R can exist, but if a P exists that satisfies our problem, then surely R exists. Therefore no such P can exist. - Doctor Tom, The Math Forum http://mathforum.org/dr.math/
Date: 01/20/2004 at 14:44:19 From: Glen Subject: Thank you (understanding why certain equations can not be solved) I am indeed grateful for your considered, and rapid, response to my question. While your various examples took you well beyond the intent of my question, I found your answer helpful and thought provoking. When I say "solved" I do mean write down an equation. I do understand that numerical solutions are often the best you can do. Mathematicians and others who use mathematics to find solutions to problems often attempt to guess the "form" of a solution by studying the problem with an eye towards identifying the properties that the solution must have (in the region of interest). I chose the Fermat equation because, almost everywhere, it "looks like" there might be a way to solve for n. It only goes bonkers at the two endpoints of the region of interest. It does this in such way that it might lead one to conclude early that no explicit formula is possible because the answer itself (when evaluating the solution at a point just outside the region of interest) can not even be a "traditional" function. I was hoping for a set of ad hoc, heuristic, exception-laden rules of thumb which serve as warning signposts in the twilight zone of not-known-to-be solvable and not-known-to-be unsolvable problems. So perhaps the best way to rephrase the question is in a more personal form: When you look at a new well-defined problem (one that you fully understand), what general things do you have to see that will immediately lead you to guess that there is no explicit solution to the problem?
Date: 01/21/2004 at 10:10:22 From: Doctor Tom Subject: Re: understanding why certain equations can not be solved Hi Glen, Of course I have a set of "ad hoc, heuristic, exception-laden rules". The main one is this: 1) The problem, whatever it is, CANNOT be solved analytically. By this I mean that if you were to write a computer program to generate equations in one variable randomly using the so-called "elementary functions" (addition, subtraction, multiplication, division, roots, powers, trig functions, logs, exponents), say up to N operations, then as N -> infinity, the proportion of those equations that can be solved analytically will tend rapidly to zero. If you look in math books and journals, of course people write down the equations they can solve. The ones that are particularly interesting are those that at first look impossible, but that can be solved. Notice that in applied math there's a HUGE emphasis on systems of linear equations. That's because they can be solved, and given almost any weird curved surface, if you look at it in a small enough region around a point, it looks flat, like a linear equation. That's what derivatives do--they toss out curvature and consider small areas about the points. A slightly better hueristic is that as long as the equation doesn't have "different elements" in it, it may be possible to solve. Here are some "obviously bad" (I'm not 100% positive these can't be solved, but I suspect so) equations, where the elements are different: sin(x) = x - 1/2 cos(1/x) = tan(x) e^cos(x) = x cos(sqrt(x)) = log(x) log(x+10) = x Maybe another way to look at the stuff above is that none of them make "physical" sense. If x had units, like seconds, or feet, or degrees, none of the equations above would make sense in that the units on both sides would be different. That might be yet another hueristic! sin(x) = cos(x) and similar, MAY admit a solution. - Doctor Tom, The Math Forum http://mathforum.org/dr.math/
Date: 01/21/2004 at 14:56:24 From: Glen Subject: understanding why certain equations can not be solved Thanks for your answer. It was about what I hoped for. The part about solvable problems representing physical systems was particularly helpful. My question is answered--but perhaps the discussion can continue a bit more. First, I was intrigued by your comment about initially perceived difficulty--"ones that are particularly interesting are those that at first look impossible, but that can be solved." Something in your head is telling you that it doesn't look like a solution is possible. It's that little engine/process that I'm interested in. Second, regarding your comment about a computer program that would look at the solvability of equations, at a given size, having all combinations of elementary functions, has anyone taken a close look at the magnitude of actually doing such a thing?
Date: 01/22/2004 at 20:36:22 From: Doctor Tom Subject: Re: understanding why certain equations can not be solved With regard to your first question, there's no doubt when I look at such a problem I subconsciously see patterns that tell me "it's solvable" or "it's not". I can articulate just a few of them, but I'm sure there's much more going on underneath. As for the computer program, I have no idea how to write a program that could look at the solvability of equations. It could try to solve them, and if it succeeded, fine. But if it failed, maybe it's just bad code and the equation really could have been solved. I just claim that if you were to list all equations of a certain complexity C, and if some oracle were to tell you what percentage of those could be solved analytically, that as the complexity C increased, the percentage would fall. I can't prove it, but my intuition from 40 years of working with equations tells me it's true. - Doctor Tom, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.