15
$\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), except that the division function returns the 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$
26
  • 11
    $\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 21 hours ago
  • 12
    $\begingroup$ is differentiation allowed? $n!=\frac{d^n x^n}{dx^n}$ $\endgroup$
    – Carlo Beenakker
    Commented 19 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 18 hours ago
  • 9
    $\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 18 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 17 hours ago

1 Answer 1

Reset to default
31
$\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$
15
  • 2
    $\begingroup$ The answer explicitly points out that this restriction was only added while I was finishing the answer. $\endgroup$
    – Emil Jeřábek
    Commented 3 hours 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 3 hours ago
  • 4
    $\begingroup$ @domotorp Since you posted the version for $\mathbb R$ as a separate question, are you going to change this question so that it explicitly allows integer division? Right now you have basically two identical question except that one is written more clearly. $\endgroup$
    – Emil Jeřábek
    Commented 3 hours ago
  • 2
    $\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 2 hours ago
  • 1
    $\begingroup$ He will be definitely impressed by $\left\lfloor\frac{2^{n^3}}{\binom{2^{n^2}}n}\right\rfloor$ :) $\endgroup$
    – domotorp
    Commented 1 hour ago

You must log in to answer this question.

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