IMC 2023 · Day 2 · P10

We show that there does exist such a number $n$.

Let $\varepsilon = 10^{-10}$. Call a prime $p$ special, if for certain $k \in \{1, 2, \dots, p-1\}$ there exist at least $\varepsilon \cdot k$ positive integers $j \le k$ for which $p$ divides $f(j)$.

Lemma. There exist only finitely many special primes.

Proof. Let $p$ be a special prime number, and $p$ divides $f(j)$ for at least $\varepsilon \cdot k$ values of $j \in \{1, 2, \dots, k\}$. Note that if $p$ divides $f(j)$ and $f(j + r)$, then $p$ divides $$(j + r)! \left( \frac{f(j+r)}{g(j+r)} - \frac{f(j)}{g(j)} \right) = 1 + (j + r) + (j + r)(j + r - 1) + \dots + (j + r) \dots (j + 2)$$ that is a polynomial of degree $r - 1$ with respect to $j$. Thus, for fixed $j$ it equals to 0 modulo $p$ for at most $r - 1$ values of $j$. Look at our $\ge \varepsilon \cdot k$ values of $j \in \{1, 2, \dots, k\}$ and consider the gaps between consecutive $j$'s. The number of such gaps which are greater than $2/\varepsilon$ does not exceed $\varepsilon \cdot k / 2$ (since the total sum of gaps is less than $k$). Therefore, at least $\varepsilon \cdot k / 2 - 1$ gaps are at most $2/\varepsilon$. But the number of such small gaps is bounded from above by a constant (not depending on $k$) by the above observation. Therefore, $k$ is bounded, and, since $p$ divides $f(1) f(2) \dots f(k)$, $p$ is bounded too.

Now we want to bound the product $g(1) g(2) \dots g(n)$ (for a large integer $n$) from below. Let $p \le n$ be a non-special prime. Our nearest goal is to prove that $$\tag{1} \nu_p \bigl( g(1) g(2) \dots g(n) \bigr) \ge (1 - \varepsilon) \nu_p (1! \cdot 2! \cdot \dots \cdot n!)$$ Partition the numbers $p, p+1, \dots, n$ onto the intervals of length $p$ (except possibly the last interval which may be shorter): $\{p, p+1, \dots, 2p-1\}$, …, $\{p \lfloor n/p \rfloor, \dots, n\}$. Note that in every interval $\Delta = [a \cdot p, a \cdot p + k]$, all factorials $x!$ with $x \in \Delta$ have the same $p$-adic valuation, denote it $T = \nu_p \bigl( (ap)! \bigr)$. We claim that at least $(1 - \varepsilon)(k + 1)$ valuations of $g(x)$, $x \in \Delta$, are equal to the same number $T$. Indeed, if $j = 0$ or $1 \le j \le k$ and $f(j)$ is not divisible by $p$, then $$\frac{1}{(ap)!} + \frac{1}{(ap+1)!} + \dots + \frac{1}{(ap+j)!} = \frac{1}{(ap)!} \cdot \frac{A}{B}$$ where $A \equiv f(j) \pmod p$, $B \equiv g(j) \pmod p$, so, this sum has the same $p$-adic valuation as $1/(ap)!$, which is strictly less than that of the sum $\sum_{i=0}^{ap-1} 1/i!$, that yields $\nu_p \bigl( g(ap + j) \bigr) = \nu_p \bigl( (ap)! \bigr)$. Using this for every segment $\Delta$, we get (1).

Now, using (1) for all non-special primes, we get $$A \cdot g(1) g(2) \dots g(n) \ge (1! \cdot 2! \cdot \dots \cdot n!)^{1 - \varepsilon},$$ where $A = \prod_{p,k} p^{\nu_p(g(k))}$, $p$ runs over non-special

primes, $k$ from 1 to $n$. Since $\nu_p(g(k)) \le \nu_p(k!) = \sum_{i=1}^{\infty} \lfloor k / p^i \rfloor \le k$, we get $$A \le \Bigl( \prod_p p \Bigr)^{1 + 2 + \dots + n} \le C^{n^2}$$ for some constant $C$. But if we had $g(n) \le n^{0.999 n} \le e^n n!^{0.999}$ for all $n$, then $$\log \bigl( A \cdot g(1) g(2) \dots g(n) \bigr) \le O(n^2) + 0.999 \log (1! \cdot 2! \cdot \dots \cdot n!) < (1 - \varepsilon) \log (1! \cdot 2! \cdot \dots \cdot n!)$$ for large $n$, a contradiction.