5
$\begingroup$

I was wondering whether there exists a (computable) sequence of numbers, for which it can be proven that no closed form can exist.

Edit: By closed form I mean an expression involving only a constant number of elementary functions. So something like a sum can not occur in the expression.

  • 0
    Im apologizing for my fuzzy definition of "closed form". Factorial I would consider as a closed expression, Euler Numbers too. But I realize that this is not very precise: Just because we abbreviate the product of the first n integers by n! doesn't make them much different from other sums/products.2011-11-16

3 Answers 3

5

Inevitably, the answer will depend on what one means by closed form. We consider computable sequences of non-negative integers, that is, computable functions $f(x)$ from the non-negative integers to the non-negative integers. We will allow the least number operator $\mu$, as well as operations of ordinary arithmetic.

The least number operator may not be familiar, so we define it. Let $R(y,x_1,\dots,x_n)$ be a relation such that for all $x_1,\dots,x_n$ there is a $y$ such that $R(y, x_1,\dots,x_n)$ holds. Then $\mu y R(y,x_1,\dots,x_n)$ is the least such $y$.

As a consequence of Matijasevic's solution of Hilbert's Tenth Problem, there is a fixed polynomial $P(e, x, u_1,\cdots, u_k)$ with the following property.

For any computable function $f$, there is a non-negative integer $e=e(f)$ such that for any $x$, $f(x)=[\mu y( P(e, x, [y]_1,[y]_2, \dots, [y]_k)=0)]_0.$ Here by $[w]_i$ we mean the exponent of the $i$-th prime $p_i$ in the prime power decomposition of $w$. (The $0$-th prime is $2$.)

This gives what I would consider a positive answer to the closed form question: Every computable sequence has a closed form. Many theorems of the same general kind were known long before the work of Matijasevic, except that instead of a polynomial $P$, one had a more complicated function.

If the $\mu$-operator is not allowed, there are quite a few different workarounds.

  • 0
    @Listing: Your answer was certainly *not* incorrect, the things you wrote are true. And people find the topic of formulas for the primes interesting.2011-11-16
4

The most famous and interesting one is probably the sequence of primes (if you mean a closed form in terms of elementary functions).

Goldbach proved that no polynomial with integer coefficients can give a prime for all integer values. However it is not fully clear that there isn't some elementary function that generates all primes.

There is a whole wikipedia article on formulas for primes.

  • 1
    The polynomial itself is a single several variable polynomial. So just like $17x^6+5xy-49x^z^7$, but messier. (A version due to Jones and others has I think $10$ variables, and is completely explicit.) No $\sum$, not even $3^x$ for variable $x$.2011-11-16
-2

I am going to guess that closed form numbers can be computed in polynomial time or some kind of bounded complexity (depends on your definition of closed form), but there are for sure computable sequences that take much longer to compute