27
$\begingroup$

How to prove that there is no formula for $n!$ that does only use the binary operations $+,-,*,/$ on natural numbers, powers of natural numbers, and fixed natural numbers?

The same question over the reals is asked here. Similar questions have been asked several times on math.SE but none of the answers there provides a formula of the specified type.

I am quite sure that there is no such formula but I have no clue how one could prove that.

Update. As you can see below, I was wrong, there is such a formula for the factorial. In fact, as was communicated to me by the second author, a solution to exactly this problem has found before, see this recent paper for some history.

Older stuff. In particular, I do not allow integer parts (floors or ceilings), except that the division function returns the integral quotient, so it does hide a sort of floor operation, which is allowed in this form.

I do not allow integrals or derivatives, sum or product symbols, I do not allow substitutions into functions with multiple variables etc. The length of the formula should be uniformly bounded for all $n$ (otherwise $1\cdot2\cdot\ldots\cdot n$ would work).

My motivation is that my 9-year-old son asked me this question. This doesn't mean that your solution should be understandable by a 9-year-old, but rather that I only allow the operations that he has heard of. Also note that most likely there is no such formula but I want a proof for that.

Improve this question
$\endgroup$
28
  • 15
    $\begingroup$ I think you need to be very precise with your question for it to have a meaningful answer. You write "I am interested in the existence of a closed formula that uses only the four basic operations and exponential powers" but it is unclear why the definitional formula $n! = \prod_{j=1}^{n} j$ does not qualify according to this "definition." $\endgroup$
    – Sam Hopkins
    Commented yesterday
  • 14
    $\begingroup$ is differentiation allowed? $n!=\frac{d^n x^n}{dx^n}$ $\endgroup$
    – Carlo Beenakker
    Commented yesterday
  • 7
    $\begingroup$ It’s not clear to me whether you consider the basic operations on reals or on natural numbers. In the latter case, i.e., if the allowed operations are $n+m$, $n\cdot m$, $n\mathbin{\dot{\smash-}}m$, $\lfloor n/m\rfloor$, $n^m$ for $n,m\in\mathbb N$, there does exist such a closed formula for $n!$; in fact, such a closed formula exists for every Kalmár elementary function. This is apparently proved in Mazzanti, Plain bases for classes of primitive recursive functions, but I can’t access the paper at the moment. $\endgroup$
    – Emil Jeřábek
    Commented yesterday
  • 10
    $\begingroup$ I suppose your set $S$ is the minimal set of $f:\mathbb N\to k$ such that: i. Every constant function is in $S$. ii. $f(n)=n$ is in $S$. iii. If $f,g\in S$, then any of $f+g$, $-f$, $fg$, $1/f$, $f^g$ is in $S$ whenever well-defined for all $n\in\mathbb N$. In my opinion, the main issue with the question is that you haven't specified $k$. Namely, if $k=\mathbb C$, then $\exp(2\pi in/m)$ is periodic modulo $m$, so, by some geometric series, one concludes that $f-g[f/g]$ is in $S$ for $f,g\in S$, and then so is $n!$ by math.stackexchange.com/q/4605121/#comment9702994_4605121 $\endgroup$
    – te4
    Commented yesterday
  • 3
    $\begingroup$ Factorial grows faster than any polynomial in $n$ and faster than any exponential with constant base, so any closed form will need to involve something like $n^n$. But then it grows too fast. (I know that this is not a proof, just thinking out loud.) $\endgroup$
    – Zach Teitler
    Commented yesterday

1 Answer 1

Reset to default
51
$\begingroup$

Factorial does have a closed formula using integer division $\lfloor n/m\rfloor$ due to J. Robinson [1]: we have $$\begin{align*} n\bmod m&=n-m\lfloor n/m\rfloor,\\ \binom rn&=\left\lfloor\frac{(2^r+1)^r}{2^{rn}}\right\rfloor\bmod 2^r,\\ n!&=\left\lfloor\frac{2^{n^3}}{\binom{2^{n^2}}n}\right\rfloor. \end{align*}$$ (That is, $n!=\bigl\lfloor r^n/\binom rn\bigr\rfloor$ for any $r>(2n)^{n+1}$. That’s how the bound is stated in [1], at any rate; I believe it holds already for $r>n!n^2/2$ or so.)

In fact, the class of functions $\mathbb N^k\to\mathbb N$ that have a closed expression using $n+m$, $n\mathbin{\dot-}m$, $n\cdot m$, $\lfloor n/m\rfloor$, and $n^m$ (or even just $2^n$) is quite vast: it coincides with the class of Kalmár elementary functions aka elementary recursive functions. This was proved by Mazzanti [2,§4].

References

[1] Julia Robinson: Existential definability in arithmetic, Transactions of the American Mathematical Society 72 (1952), no. 3, pp. 437–449, doi 10.2307/1990711.

[2] Stefano Mazzanti: Plain bases for classes of primitive recursive functions, Mathematical Logic Quarterly 48 (2002), no. 1, pp. 93–104, doi 10.1002/1521-3870(200201)48:1%3C93::AID-MALQ93%3E3.0.CO;2-8.

Improve this answer
$\endgroup$
17
  • 4
    $\begingroup$ There is a fun exercise in Knuth's Art of Computer Programming: Suppose you have a computer which can compute any arithmetic operation in time $O(1)$, no matter how large the inputs are. Show that it can factor $N$ in time polynomial in $\log N$. $\endgroup$
    – David E Speyer
    Commented yesterday
  • 4
    $\begingroup$ The idea is that the Euclidean algorithm to compute $\text{GCD}(M, N)$ runs in time $O(\min(\log M, \log N))$ in this model, and you can compute $k!$ in time polynomial in $\log k$ using the formulas in this answer, so you can do a binary search to find $k$ with $1< \text{GCD}(N, k!) <N$. $\endgroup$
    – David E Speyer
    Commented yesterday
  • 2
    $\begingroup$ The ambiguity comes from the fact that when I originally posted the question, I explicitly wrote that only the four basic operations plus exponentials were allowed, having the reals in mind, but later it was edited by Martin Brandenburg, who rewrote the question to clarify it and added that it was about $\mathbb N \to \mathbb N$ functions. As I also didn't know the answer for this problem and I was late to notice the change, I thought I would leave it like that. I'll post a separate question about $\mathbb R\to \mathbb R$ functions. $\endgroup$
    – domotorp
    Commented yesterday
  • 3
    $\begingroup$ The question did seem like a bit of a moving target, but after thinking about it some more I believe the intent was prove there are no simple solutions analogous to $\sum\limits_{k=1}^n k=\frac{ n\, (n+1)}{2}$. $\endgroup$
    – Steven Clark
    Commented yesterday
  • 7
    $\begingroup$ He will be definitely impressed by $\left\lfloor\frac{2^{n^3}}{\binom{2^{n^2}}n}\right\rfloor$ :) $\endgroup$
    – domotorp
    Commented 23 hours ago

You must log in to answer this question.

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