1

The below was inspired by this question, in which the OP was surprised that the "simple" equation $x^3 + x = 1$ could have such a "complex" solution.

In rough form, the question here is a bit more general:

  • What is an example of the "simplest" symbolic equation whose solution is "most complex"?

That rough statement is of course inadequate to constrain or compare candidate answers. Thus, to be specific, here are the conditions:

  • The equation involves a single variable, say $x$, and any number of constants.
  • The "complexity" of the problem equation and of the symbolic solution is the number of bytes in its expression (for instance in a MathJax representation).
  • The global criterion to be optimized is the ratio of the number of bytes in the solution to the number of bytes in the problem equation.
  • Both the problem and solution must be represented in their simplest canonical form. For instance, one must use $\sin x$ rather than its infinite series representation.
  • All standard special functions and symbols (factorial !, power ^, etc.) are allowed, where the complexity is in the number of bytes in their canonical MathJax representation.
  • Both the problem and the solution must be symbolic, not numerical. (Otherwise simple problem equations such as $x^2 = 2$, which have an "infinitely complex" numerical solution, would trivially optimize the criterion.)
  • There must be a true, single closed-form solution. (Thus one cannot include, for example, $x^{9!} = 2$ and get a large list of solutions.)
  • The solution is not a simple numerical calculation, for instance $x = 9 \uparrow \uparrow \uparrow$ (using Knuth's uparrow notation) or $x = (9!)^{9!}$, etc. As illustrated by the linked question above, it is rather the algebraic complexity of a solution.

One can get lost in nit picking (e.g., deciding which is to be preferred, \sqrt{x} versus x^{1/2}, or a/b versus \frac{a}{b}, and such). I suspect there are some dramatic examples where such minutia are irrelevant.

David G. Stork
  • 29,774
  • There are, of course, simple equations that have solutions but no closed-form solution, e.g., $x^5-x-1=0$, $y'=e^{x^2}$, $x\log x=7$, etc., etc. – Gerry Myerson Nov 22 '20 at 00:04
  • The smallest positive integral solution to $x^2-1789y^2=1$ has $x=13673687937600285436522338047798889300505982960692087644059539022368201$ – Gerry Myerson Nov 22 '20 at 00:11
  • @GerryMyerson: As for your first comment: "There must be a true, single closed-form solution." As for your second... hmmm... the issue of a $y$ complicates matters. I certainly didn't imagine that class of equation. I presume one could make even larger solutions using $y$, $z$, $w$, ... Perhaps I should add a restriction against those. – David G. Stork Nov 22 '20 at 01:11
  • I think I'll include some restriction against extraordinary large numerical solutions. After all, $9 \uparrow \uparrow \uparrow$ (using Knuth's uparrow notation) leads to an integer larger than the number of atomic particles in the universe. Likewise Graham's number and its ilk. That's not what my problem was driving at. – David G. Stork Nov 22 '20 at 01:20
  • Do you have any examples of what you were driving at? – Gerry Myerson Nov 22 '20 at 02:19
  • @GerryMyerson: See the problem I linked to at the top. – David G. Stork Nov 22 '20 at 02:30
  • OK, then, $x^4+x=1$ has a considerably more complicated solution than $x^3+x=1$. – Gerry Myerson Nov 22 '20 at 11:30
  • @GerryMyerson: Alas, $x^4 + x = 1$ has four (not just one) solutions. But this is in the right direction. Can't we find something even more extreme? – David G. Stork Nov 22 '20 at 19:39
  • OK, though it has only one solution in $[0,1]$. There is a right triangle with all rational sides and area $157$. The simplest such has hypotenuse ${\displaystyle {\frac {224403517704336969924557513090674863160948472041}{8912332268928859588025535178967163570016480830}}}$. – Gerry Myerson Nov 22 '20 at 21:30
  • @GerryMyerson: But how complex is the statement of the problem? – David G. Stork Nov 22 '20 at 22:57
  • Not very. I've given it in simple words. In symbols, $a,b,c\rm{\ in\ }{\bf Q}$, $a^2+b^2=c^2$, $ab/2=157$. – Gerry Myerson Nov 22 '20 at 23:00
  • So... following my requirement of a single unknown $x$, where is $x$? – David G. Stork Nov 22 '20 at 23:07
  • You could take $x$ to be $c$. If you want a single integer, you could take it to be the numerator of $c$. – Gerry Myerson Nov 23 '20 at 01:38

2 Answers2

3

The unique real root $x$ of $x^5-5x+12=0$ is given by $$-cx=\root5\of{(a+c)^2(b-c)}+\root5\of{(-a+c)(b-c)^2}+\root5\of{(a+c)(b+c)^2}-\root5\of{(-a+c)^2(b+c)}$$ where $c=\root4\of5$, $a=\sqrt{2\phi^{-1}}$, $b=\sqrt{2\phi}$, and $\phi=(1+\sqrt5)/2$, according to Wikipedia.

Gerry Myerson
  • 3,404
  • Fine...thanks... but I have a feeling there are far more extreme cases. Let me see as they arrive. – David G. Stork Nov 23 '20 at 02:17
  • See also https://mathematica.stackexchange.com/questions/133550/solving-quintic-in-radicals – Gerry Myerson Nov 23 '20 at 02:20
  • 1
    Daniel Lazard, Solving quintics by radicals, available at https://hal.archives-ouvertes.fr/hal-02547734/file/lip6.1998.023.pdf gives a general formula for solving solvable quintics. The formula is three pages long. Understandably, he doesn't give an example. – Gerry Myerson Nov 23 '20 at 02:32
  • GerryMyerson: Your linked question (mathematica.stackexchange.com/questions/133550) has an extremely long ("complex") mathematical problem... surely this cannot be "optimal" by the current problem criteria of the ratio of solution complexity to problem statement complexity. Right? But yes... the quintic is an excellent example! Let's see if others surpass it. – David G. Stork Nov 23 '20 at 02:39
  • "Your linked question (mathematica.stackexchange.com/questions/133550) has an extremely long ("complex") mathematical problem.." Sure, but have you worked out how long the solution is? Remember, you're not interested in the size of the problem, only the ratio of solution size to problem size. – Gerry Myerson Nov 23 '20 at 03:26
2

Problem: express $\sin(2\pi/17)$ in algebraic terms.

Solution: Let $\epsilon=\sqrt{17+\sqrt{17}}$.

Let $\epsilon'=\sqrt{17-\sqrt{17}}$.

Let $\delta=\sqrt{17}-1$.

Let $\alpha=\sqrt{34+6\sqrt{17}+\sqrt2\delta\epsilon'-8\sqrt2\epsilon}$.

Then $\sin(2\pi/17)={1\over16}\sqrt2\sqrt{4\epsilon'^2-2\sqrt2\delta\epsilon'+8\sqrt2\epsilon-(\sqrt2\delta+2\epsilon')\alpha}$

Note: it's even worse for $\sin(2\pi/257)$, and far worse for $\sin(2\pi/65537)$. For the first, see https://math.stackexchange.com/q/517218 – for the second, you're on your own.

Gerry Myerson
  • 3,404