Hacker News Reader

>> Some of them don't even really have solutions (non-linear differential equations).

> There certainly are differential equations without solutions [---]

These statements are confusing, I think. Some DE:s might not have analytical solutions in terms of _elementary_functions_. For example, 'sin(x)' is considered an elementary function, and it is a certain curve that solves some differential equations.

Now lets say I give you a non-linear ODE that no-one can solve, but I say "'foo(x)' is the function which describes the solution to this ODE". It is a more or less pointless statement, but all it means is that 'foo(x)' gives the curve that solves the ODE. Just like 'sin(x)' for the DE that it solves, difference is we do not know any properties of 'foo(x)' -- but there is a cruve that we could call 'foo(x)'.

All I'm trying to say is: A DE "not having a solution" and "not having a solution in terms of elementary functions" are two very different things. "Not having a solution" means (or at least _should_ mean) you could not even numerically solve it in a small neighbourhood (e.g. the curve 'foo(x)' does not exists), "not in terms of elementary functions" means no analytical expression in terms of trigonometric, hyperbolic, exponentials, powers, and so on, can be written down.

edit: Reading others comments they seem to be saying the similar things. Sorry for unnecessarily reiterating this.

> It is a more or less pointless statement, but all it means is that 'foo(x)' gives the curve that solves the ODE.

Oh, one more thing: you say, and I understand why, that this is "more or less pointless", but it's not! It is a perfectly good way of producing new functions. For some reason (alphabetical filing in my mind?), I always think first of the Airy function (https://en.wikipedia.org/wiki/Airy_function), but the Bessel functions (https://en.wikipedia.org/wiki/Bessel_function) and, more generally, most (all?) special functions (https://en.wikipedia.org/wiki/Special_functions) also arise in this way.

In fact, even the logarithmic function (boringly, via $\dot y = 1/x$) and the exponential and sine functions (more interestingly, via $\dot y = y$ and $\ddot y = -y$) can be defined this way (by imposing suitable initial conditions, once you know the relevant existence and uniqueness theorems). They can also be defined by their power series, without direct reference to differential equations, but I find such a definition hard to motivate without reference to the differential-equations definition.

Yes, good point. I was actually thinking about special functions and that they are usually defined through differential equations (so, yeah, I more or less stole the idea from there and did not cite it properly :-/ but I did not want to bring all of that in to my comment).

Thanks for elaborating on this.

> A DE "not having a solution" and "not having a solution in terms of elementary functions" are two very different things. "Not having a solution" means (or at least _should_ mean) you could not even numerically solve it in a small neighbourhood (e.g. the curve 'foo(x)' does not exists), "not in terms of elementary functions" means no analytical expression in terms of trigonometric, hyperbolic, exponentials, powers, and so on, can be written down.

I agree with all this; in fact, it's almost exactly what I meant by:

> there is a huge difference between an equation that doesn't have a solution and one whose solution we can't find.

I add the caveat 'almost' because not having a solution is an even stricter condition than not being locally soluble numerically (I think—I'm no expert on numerical methods); but there are equations that meet this stricter condition.

'I say "'foo(x)' is the function which describes the solution to this ODE"'

You can't say this until you've proven that a solution exists (and that it's unique, if you really mean 'the' solution). I think that was part of the point.

Now lets say I give you a non-linear ODE that no-one can solve, but I say "'foo(x)' is the function which describes the solution to this ODE". It is a more or less pointless statement, but all it means is that 'foo(x)' gives the curve that solves the ODE.

Sounds like how we got Bessel functions, no?

Yep; see https://news.ycombinator.com/item?id=9655901 above

You are correct, sort of.

However, there are a number of differential equations where to simulate it requires exponential complexity w.r.t. to the given degree of accuracy or amount of "time" to simulate it for. For instance, pretty much any chaotic problem.

Agreed! There's a reason that non-linear equations are regarded as much harder than linear ones, and I don't mean to gloss over it. However, possibly just because I am a mathematician and not an engineer or hacker, I still find the distinction between "solution that is hard to find" and "no solution" meaningful and important. (It is the difference between "we can't predict the weather" and "there is no such thing as weather"!)

The classic example is Navier–Stokes equations of viscous fluid flow. True story, one of my college professors handed out a homework assignment that no one could solve. Far as I could tell the boundary conditions described journal bearing that wasn't stable. Such things exist.

I think other very hard to deal with are equations where the solution diverges exponentially due to small changes in boundary conditions. Orbital mechanics is like that.

Not sure but I can see a situation where the set of equations that describe the solution form a series that never converges to a regular pattern. (irrational series? as irrational numbers but with equations) I think quantum mechanics is like that (Don't quote me)

Oh it's worse than that, decision problems like computing the sign of the solution at a given point are undecidable in general.

Yes, you can encode arbitrary Turing machines as differential equations.

> Yes, you can encode arbitrary Turing machines as differential equations.

That's neat! Do you have a reference?

You can build a physical Turing machine and describe its behavior using Newton's equations of motion, then do a change of variable t -> 1/t. The value at 0 gives you the result of the computation. Q.E.D

That's … unsatisfying. I mean that it's unsatisfying in a theoretical sense (because it gives me no theoretical feeling for the Turing-machine-to-differential-equation transformation), but, if I really wanted to be picky, I could point out that (a) nothing in the definition of a Turing machine guarantees its physical realisability (what if its number of states is bigger than the power set of the number of elementary particles in the universe, or, similarly, if it writes on an unbounded amount of tape?), and (b) Newton's equations of motion are only approximations to, not exact descriptions of, the physical universe.

Is there any more-or-less explicit recipe that says "given a description of a Turing machine (as a 7-tuple, say https://en.wikipedia.org/wiki/Turing_machine#Formal_definiti...), here is a (possibly unmanageably huge) differential equation such that …"—well, I don't even really know what. Your answer suggests that I might ask that, say, the solution $y$ to the differential equation where $y(1)$ somehow encodes a given initial state of the tape is such that $y(0)$ somehow encodes the final state of the tape (with the understanding that $y$ is not defined at $0$ if the machine doesn't halt on the corresponding input).

Fine, fine, I just think it's an elegant way to say it :)

You want something like this http://www.sciencedirect.com/science/article/pii/S1571066108... or like this http://www.sciencedirect.com/science/article/pii/S0196885807...

> Fine, fine, I just think it's an elegant way to say it :)

You're absolutely right that it's an elegant and compelling argument for the plausibility of the claim; I was just looking for the rigour behind it (even a statement, if not a proof). Your second reference is exactly the sort of thing that I had in mind; thanks!

Isn't this exponential precision = polynomial time?

> "there is a huge difference between an equation that doesn't have a solution and one whose solution we can't find."

Of particular note, with some classes of differential equations, we can't write an explicit solution, but we can characterize the solutions very well. For example, we might be able to describe the solution in terms of its long-term behavior ("it approaches such-and-such point" or "it has a stable orbit around such-and-such path".)

I have long wanted to, but have never actually got to, teach a differential-equations course from Hubbard & West (http://www.amazon.com/Differential-Equations-Dynamical-Appro...). I thought that there was an article in Math. Mag. about their approach via "fences and funnels", but MathSciNet only knows about a 1995 CMS conference proceedings: http://www.ams.org/mathscinet-getitem?mr=1483923 . EDIT: The article I wanted (which has the same title as the proceedings article above) is actually in College Math. J.; it's http://www.jstor.org/stable/2687507 .

Another, I think, slightly gentler approach along similar lines is Blanchard, Devaney, & Hall (http://math.bu.edu/odes). The pedigree for this latter is very good; Devaney gave the (as far as I know) first rigorous mathematical definition of chaos. I have taught out of this one a number of times, and very much enjoy it.

At a more advanced level: my favorite graduate course was taught out of http://www.amazon.com/Introduction-Applied-Nonlinear-Dynamic... .

Another one that I meant to mention in my previous post is Strogatz (http://www.stevenstrogatz.com/books/nonlinear-dynamics-and-c...). Do you know how Wiggins compares?

I have the first edition of Strogatz' book. It's fairly accessible to students who have taken calculus and been exposed to ODEs, and can be worked through in about a semester. Great for a 200 or 300 level course.

Wiggins is a much more advanced, and much more thorough, book. It's appropriate for 400 level at a minimum, and probably more accessible to graduate students. I wouldn't even attempt it without having taken ODEs and Linear Algebra, and probably some real analysis or PDEs or another high level course just for exposure to mathematical rigor (and I might be leaving out other prereqs; I can't presently locate my copy of the book.) It's tremendously well presented for a book at that level, and could be enough material for a three-quarter or two-semester sequence. It's advanced enough that someone working on a related Masters or Doctoral thesis would likely refer to it regularly.

The thing that always bugged me about differential equations when I encountered them in the MIT analog circuits course was that the professor said that the way to figure them out was to use "guesswork". For example, the diffeq describing how RLC circuits work is well known, but can not be solved using a systematic algorithm that a person could do by hand.

You might be confusing straightforward linear systems of differential equations (some exceptions when you have a nasty heterogenous part, but which are 'always' solvable by a standard method) with so-called Differential Algebraic Equations (DAEs).

These beasts often pop up when trying to solve larger electrical circuits with time-dependent elements (ie. RLC). The only thing you can really do to solve them usually is linearizing them approximate them by some integration scheme (this is what Spice, the electronics simulator is based on).

Uni-level math on the reals always bugged me for the exact reason that I thought well-defined problems not involving funny self-reference tricks ought to have algorithms. Despite this, math professors kept presenting us with patterns to match, but no exhaustive algorithms.

Little did I know, considering the reals are uncountable, so you can't really come up with exhaustive algorithms for lots of things dealing with them.

Perhaps you would like to study constructive analysis, a la Bishop? You lose a lot of intuition in the hypotheses, which necessarily become more complicated—or perhaps I should say that you are forced to develop a different intuition about hypotheses—but you gain conclusions of exactly the sort that you want.

https://en.wikipedia.org/wiki/Constructive_analysis

EDIT: Also, the fact that a structure is uncountable doesn't prevent you from operating algorithmically on it (not that you claimed it did!); it just means that there are some elements of it that cannot be singled out algorithmically.

> Despite this, math professors kept presenting us with patterns to match, but no exhaustive algorithms.

This is basically what math is all about. If a problem can be effectively and easily solved algorithmically, it is considered trivial, and little attention is given to it. The focus is on actually difficult problems, ones that need clever tricks to get a handle of.

To be frank: bull. A problem that can always be solved algorithmically is "trivial", in the mathematical sense, but since the mind is algorithmic, you can't just say, "Well, clever tricks, not algorithms." A mathematician's mind works somehow.

> the mind is algorithmic

Huh? If you mean this:

> A mathematician's mind works somehow.

then it seems like you may be using 'algorithmic' to mean something like "unfolding according to (possibly unknown, possibly probabilistic) laws", in which case it seems so broad a term as to be almost useless.

>then it seems like you may be using 'algorithmic' to mean something like "unfolding according to (possibly unknown, possibly probabilistic) laws"

They're certainly currently unknown, and we have good reason to believe they're probabilistic.

Even such vague, loose descriptions are better than invoking "mathematical intuition" or "it just comes to me" or other explanations for how one does math.

There are ways to systematically get at DE solutions, the first that come to mind are power series or fourier series or decomposing into other orthogonal functions (of course, assuming the solution obeys relevant boundary conditions), but that won't give you an elegant result unless you have the time to wade through the recursion relations and sum it up. Sometimes, a smart guess just gives you the result, so why not do that?

There are methods to solve them. RLC in particular can be approached with Laplace Transforms. However these kinds of equations need certain approximations and simplifications in order to become analytically tractable.

This bothered me too. Actually, it started with the computation of anti-derivatives (integrals) in high-school.

Isn't there a theorem that says that no closed-form, analytic solutions to such equations can be found, in general?

> Isn't there a theorem that says that no closed-form, analytic solutions to such equations can be found, in general?

'Analytic' has a mathematical meaning (https://en.wikipedia.org/wiki/Analytic_function) which is probably not what you mean here. Taking it in the more colloquial (Eulerian) sense of "given by a formula", not only are there such general results, but there are even specific functions for which it is known that no elementary (https://en.wikipedia.org/wiki/Elementary_function) anti-derivative exists (the strong form of "impossible to solve" that I mentioned above), and an algorithm for deciding of a given function whether it has an elementary anti-derivative (https://en.wikipedia.org/wiki/Risch_algorithm).

> $\dot y = 1/y$, whose solutions have graphs lying on straight lines through the origin

Oops! I mentioned this as an example of an easily soluble, non-linear equation—which it is; it may be solved by solution of variables—but the solutions are not at all what I said (I was thinking of $\dot y = y/t$).

point taken

I appreciate your response and edit to the post; that was an admirably quick turn-around time! However, I think that, in the context of the article, TheLoneWolfling (https://news.ycombinator.com/item?id=9654767 )'s comment is more important than mine: a mention of non-linear equations and the difficulty of their solution is highly relevant and appropriate, as long as you don't imply the theoretical impossibility of their solution.