# Sequence for which no closed form can exist

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.

-
What do you mean by "closed form"? – Willie Wong Nov 16 '11 at 16:48
You've tried browsing around the OEIS? There're lots... then again, you should answer Willie's question first. Is the factorial a closed form (it can't be expressed in terms of elementary functions)? Is the $\$10,000$sequence of Hofstadter a closed form? – J. M. Nov 16 '11 at 16:52 @J.M. But just the fact that one didn't find a closed form doesn't mean that no one can exist – stefan Nov 16 '11 at 17:57 Sure. but you still haven't said what "closed form" means to you. I consider the factorial (and the gamma function as well) as a closed form in itself, even though you can't represent it in terms of elementary functions. I treat Hofstadter's sequence as a closed form in itself, even though nobody's found a way to represent it in terms of "simpler" (whatever that means) functions. So, again: what's a "closed form" to you? – J. M. Nov 16 '11 at 18:05 Okay, I saw your edit only now. So I suppose the factorial doesn't have a "closed form" for you. Or the Euler numbers. Or the partition numbers. Or... – J. M. Nov 16 '11 at 18:08 ## 3 Answers 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. - Please explain what$\mu$does. I assume there should be an$x$on the right side after the$e,$? And what does that$0$do? It can't be referring to the$0$'th prime. – Robert Israel Nov 16 '11 at 17:19 @Robert Israel: The post has been edited, and the$\mu$-operator has been defined. And yes, it is the$0$-th prime, which is$2$. People in logic count this way: 0, 1, 2,$\dots$. And there was a bad typo, it should have been$P=0$. – André Nicolas Nov 16 '11 at 17:39 Thank you for your clarification, I removed my answer as it was incorrect. – Listing Nov 16 '11 at 17:54 @Listing: Your answer was certainly not incorrect, the things you wrote are true. And people find the topic of formulas for the primes interesting. – André Nicolas Nov 16 '11 at 18:03 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. - There is an elementary function that generates all primes, and only the primes. It can be built out of addition, subtraction, multiplication, and absolute value. This is a straightforward consequence of the result of Matijasevic that for any recursively enumerable set$S$of positive integers, there is a polynomial$P(x_1,\dots,x_n)$with integer coefficients such that the range of$P$is the elements of$S$, together with some negative numbers. The negative values can be replaced by (say)$2$by using some tricks with the absolute value function. – André Nicolas Nov 16 '11 at 17:50 @AndréNicolas When you say it can be build of addition, do you mean finite addition? The operator mentions that he want no sum to occur in the formula :-) – Listing Nov 16 '11 at 18:42 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\$. – André Nicolas Nov 16 '11 at 20:54

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

-