Associated Topics || Dr. Math Home || Search Dr. Math

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

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

about solvable problems representing physical systems was particularly
continue a bit more.

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.

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/
Associated Topics: