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

1 Answer 1

Reset to default
24
$\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] (note that $n-m$ is applied below only when it is known that $n\ge m$; thus, only the interpretation of division as $\lfloor n/m\rfloor$ is essential for this to work): 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$
12
  • $\begingroup$ The question explicitly forbids the floor (and ceiling) function. $\endgroup$
    – Peter Mueller
    Commented 1 hour ago
  • 1
    $\begingroup$ The answer explicitly points out that this restriction was only added while I was finishing the answer. $\endgroup$
    – Emil Jeřábek
    Commented 41 mins ago
  • $\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 32 mins ago
  • $\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 30 mins ago
  • 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 26 mins ago

You must log in to answer this question.

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