# Proof there is no algorithm to compute the intersection of a line and sinusoidal wave?

There is obviously a set of situations where one lack an algorithm to compute the exact solution of an equation via symbolic manipulation only, for example x = sin(x).

One has to resort to numerical analysis and iteration methods (for example) to estimate a value resolving the above.

My question is: is there an accepted mathematical proof or set of evidence demonstrating that it is impossible to resolve this equation via symbolic manipulation or is there a possibility that one comes with a solution through some clever trick in the future?

If such a proof exist, which mathematical concepts do I need to Google for further investigation?

• I can solve symbolically the afore-mentionned equation: the only real solution is $0$. Do you mean to solve it on $\mathbb C$ ? In which case, I guess it is equivalent to solving $w=z\exp(z)$ for some special $w$. The general equation is known not to be symbolically invertible using formulas in $w$, $\log(w)$ and $\exp(w)$ (look for Lambert function). So, I'd advise you to give a more detailed question regarding the kind of symbolic formula you're after, because I'm confident there exists symbolic formulas involving Lambert functions (I may be wrong, though). – Loïc Teyssier Dec 10 '17 at 14:03
• I should have written ax = sin(x) where a is any positive real. I was only thinking about real solutions when I wrote my question. I could have chosen another example. Iterations are performed until a threshold of quality is reached around the intersection. I was wondering about mechanical, step-by-step, resolutions, like that of resolving a set of linear equations. – Jérôme Verstrynge Dec 10 '17 at 14:24
• Yes, I secretly understood what you meant ;) My point was to underline the fact that depending on the choice of the type of formula you allow, different outcomes arise (my comment is still valid for your modified sine equation). For instance, why should it be felt legitimate to obtain «exact» solutions in finitely many steps in terms of $\log$ and $\exp$ and not in terms of other special functions? What if you allow only rational formulas? Joel's answer below gives a precise reference to the fact that defining properly the formal framework you work in is of paramount importance. – Loïc Teyssier Dec 10 '17 at 14:35
• It is not clear what you mean by "total recursive" (in the context of real numbers). It is not even clear to me whether you consider the equations $e^x=2$ or even $x^2=2$ "solvable by symbolic manipulations". Which symbols do you allow? – Goldstern Dec 10 '17 at 14:52
• "recursive functions" in your sense are usually defined on the integers, or on some other set which comes with an enumeration. Not on the reals. – Goldstern Dec 10 '17 at 17:28

## 2 Answers

Your question is addressed in my paper What is a closed-form number?

The first step is to decide which "symbols" or functions you accept as furnishing a "symbolic solution." In my paper I focus on perhaps the most restrictive set, namely exp and log and the arithmetic operations.

The second issue you have to address is whether you're asking for a symbolic expression for a function or for a symbolic expression for a number (namely, the root of some equation that you're trying to solve). This distinction seems not to have been emphasized in the literature prior to my paper. There is quite a bit of literature about closed-form functions, but knowing, for example, that the smallest positive root of the equation $kx = \sin x$, thought of as a function of $k$, has no closed-form expression, doesn't answer the question of whether there is some ad hoc expression for specific values of $k$.

In my paper I show that Schanuel's conjecture implies that there is no closed-form expression for the roots of equations such as $x + e^x = 0$. I think that this is pretty much the best answer we can currently give to this type of question.

• Your paper is really interesting. – Loïc Teyssier Dec 10 '17 at 23:45
• There certainly are closed-form solutions of $kx = \sin x$ for specific values of $k$, namely $k = \sin(x)/x$ where $x$ is any nonzero closed-form number. – Robert Israel Dec 11 '17 at 6:11

You may be interested in Richardson's theorem, an amazing theorem which implies that the problem of determining for a given mathematical expression $E(x)$, of particularly simple form, whether $E(x)=0$ for all real $x$ is undecidable. Not only is there no computable algorithm to determine the answers to all such questions, but for any given axiomatic system such as ZFC there are some expressions $E$ for which the fact of the matter of whether $E(x)$ is identically $0$ is not settled by those axioms.