8
$\begingroup$

Richardson's theorem proves that whether an expression A is equal to zero is undecidable. A is in this case an expression, constructed from $x,e^x,\sin(x)$ and the constant function $\pi$ and $\ln(2)$ as well as all integers. Further, various operators are allowed (for a comprehensive list see the wikipedia entry).

Zeilberger, Gosper, Knuth and many others worked on algorithms for finding hypergeometric identities ("A=B" by Marko Petkovsek, Herbert Wilf and Doron Zeilberger gives an overview). And, for a given set of hypergeometric functions, there are algorithms that can determine whether a sum of a subset is an identity. Since $x$, $e^x$ and $\sin(x)$ are all hypergeometric functions, as well as any constant function and the operators yield hypergeometric functions as well (for example, for $a,b$ hypergeometric, $ab$ is hypergeometric as well), why don't these two discoveries contradict each other?

Improve this question
$\endgroup$
6
  • $\begingroup$ Do the hypergeometric identities algorithms allow for arbitrary composition of the functions? $\endgroup$
    – Joel David Hamkins
    Commented Jan 11 at 15:43
  • $\begingroup$ Shouldn't the composition of two hypergeometic functions be hypergeometric? $\endgroup$
    – Martin Clever
    Commented Jan 11 at 16:01
  • 1
    $\begingroup$ There's your answer. $\endgroup$
    – Gerald Edgar
    Commented Jan 11 at 16:14
  • $\begingroup$ While I do have familiarity with the MRDP theorem, the resolution of Hilbert's 10th problem, and the connection with Richardson's theorem, I am less familiar with the hypergeometric identities, and I would appreciate it if someone could post an answer that resolved and summarized the central differences here. $\endgroup$
    – Joel David Hamkins
    Commented Jan 12 at 0:08
  • 4
    $\begingroup$ It's as simple as "the composition of hypergeometric functions is not hypergeometric". $f(n)=2^n$ is a hypergeometric function because $f(n+1)/f(n)=2$ is a rational function of $n$, but $g(n)=(f\circ f)(n)=2^{2^n}$ satisfies $g(n+1)/g(n)=2^{2^n}$ which obviously grows much too fast to be rational. $\endgroup$
    – Steven Stadnicki
    Commented Jan 12 at 0:50

1 Answer 1

Reset to default
18
$\begingroup$

(Comment turned into an answer:) It's as simple as "the composition of hypergeometric terms is not hypergeometric". $f(n)=2^n$ is a hypergeometric term because $\frac{f(n+1)}{f(n)}=2$ is a rational term, but if we take $g(n)=\left(f\circ f\right)(n)=2^{2^n}$, then $\frac{g(n+1)}{g(n)}=2^{2^n}$ grows much too quickly to be a rational term. (Indeed, I'd say that one of the great frustrations with W-Z and similar tools is how many nice looking functions they don't apply to...)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Ah, but $2^{2^n}$ is a hypergeometric function, right? I guess, I confused hypergeometric function (nearly every function used in standard mathematics) and hypergeometric term ($\frac{f(x+1)}{f(x)}$ is rational) $\endgroup$
    – Martin Clever
    Commented Jan 12 at 11:16
  • $\begingroup$ @MartinClever What definition of hypergeometric function are you using? $\endgroup$
    – Will Sawin
    Commented Jan 12 at 12:04
  • $\begingroup$ This one from wikipedia en.wikipedia.org/wiki/Hypergeometric_function $\endgroup$
    – Martin Clever
    Commented Jan 12 at 12:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .