11
$\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?

Similar question have been asked several times on math.SE but none of the answers there provide 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.

In particular, I do not allow integer parts (floors or ceilings), 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). I am also interested in solutions that use real or complex numbers but remember, no taking integer parts!

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$
22
  • 8
    $\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 15 hours ago
  • 12
    $\begingroup$ is differentiation allowed? $n!=\frac{d^n x^n}{dx^n}$ $\endgroup$
    – Carlo Beenakker
    Commented 14 hours ago
  • 6
    $\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 13 hours ago
  • 7
    $\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 13 hours ago
  • 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 12 hours ago

1 Answer 1

Reset to default
13
$\begingroup$

The question is still ambiguous (or at least was when I started writing this answer): it talks about operations on natural numbers, but $\mathbb N$ is not closed under the operations $-$ and $/$. If these are interpreted so that they refer to the operations $n\mathbin{\dot-}m=\max\{n-m,0\}$ and $\lfloor n/m\rfloor$, then factorial does have a closed formula 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{(2n+1)^{(n+1)n}}{\binom{(2n+1)^{n+1}}n}\right\rfloor. \end{align*}$$ (That is, $n!=\bigl\lfloor r^n/\binom rn\bigr\rfloor$ for any $r>(2n)^{n+1}$. Note that $x-y$ is applied here only when it is known that $x\ge y$; thus, only the interpretation of division as $\lfloor x/y\rfloor$ is essential for this to work.)

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$

You must log in to answer this question.

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