Decomposing a Factorial into Large Factors

Source | HN Comments

文章研究了将阶乘分解为大因子的最大值问题，即 ![{t$N$}](https://s0.wp.com/latex.php?latex=%7Bt%28N%29%7D&bg=ffffff&fg=000000&s=0&c=20201002)，定义为将 ![{N!}](https://s0.wp.com/latex.php?latex=%7BN%21%7D&bg=ffffff&fg=000000&s=0&c=20201002) 分解成 ![{N}](https://s0.wp.com/latex.php?latex=%7BN%7D&bg=ffffff&fg=000000&s=0&c=20201002) 个因子，每个因子都至少为 ![{t$N$}](https://s0.wp.com/latex.php?latex=%7Bt%28N%29%7D&bg=ffffff&fg=000000&s=0&c=20201002) 的最大值。文章给出了 ![{t$N$}](https://s0.wp.com/latex.php?latex=%7Bt%28N%29%7D&bg=ffffff&fg=000000&s=0&c=20201002) 的上下界，并改进了之前的结果，证明了 ![{t$N$}](https://s0.wp.com/latex.php?latex=%7Bt%28N%29%7D&bg=ffffff&fg=000000&s=0&c=20201002) 与 N/e 之间的关系。文章还讨论了与此问题相关的其他猜想，并提出了验证这些猜想的思路。

将阶乘分解为大因子：关于 Factorial Decomposition 的研究

我最近上传到 arXiv 的一篇论文 "Decomposing a factorial into large factors"，研究了量 ${t(N)}$ ，它被定义为可能将 ${N!}$ 分解成 ${N}$ 个因子 ${a_1, \dots, a_N}$ 的最大值，其中每个因子都至少为 ${t(N)}$ 。该序列的前几个值是：

$\displaystyle 1,1,1,2,2,2,2,2,3,3,3,3,3,4, \dots$

(OEIS A034258)。例如，我们有 ${t(9)=3}$ ，因为一方面我们可以分解：

$\displaystyle 9! = 3 \times 3 \times 3 \times 3 \times 4 \times 4 \times 5 \times 7 \times 8$

但另一方面，不可能将 ${9!}$ 分解为九个因子，每个因子都大于等于 ${4}$ 。

Erdős 引入了量 ${t(N)}$ ，并提出了关于 ${t(N)}$ 的上下界问题；非正式地说，它询问了将 ${N!}$ 分解为 ${N}$ 个因子，能达到多么平均的程度。当分解任意数字时，这本质上是臭名昭著的 knapsack problem 的变体（在取对数后），但人们可以希望阶乘 ${N!}$ 的特定结构可以使这种特殊的背包类型问题更易于处理。由于对于任何假定的分解，都有：

$\displaystyle N! = a_1 \dots a_N \geq t(N)^N$

我们根据 Stirling 近似得到一个上界：

$\displaystyle t(N) \leq (N!)^{1/N} = \frac{N}{e} + O(\log N) \ \ \ \ \ (1)$

在某个时刻，Erdös、Selfridge 和 Straus 声称这个上界是渐近尖锐的，即：

$\displaystyle t(N) = \frac{N}{e} + o(N) \ \ \ \ \ (2)$

当 ${N \rightarrow \infty}$ 时；非正式地说，这意味着当 ${N}$ 很大时，我们可以将 ${N!}$ 分解成 ${N}$ 个大小（主要）大致相同的因子。然而，正如这篇后来的论文中报道的那样，Erdös “认为 Straus 已经写下了我们的证明……不幸的是，Straus 突然去世，他的笔记也无处可寻。此外，我们再也无法重建我们的证明，所以我们的断言现在只能被称为一个猜想”。

Guy 和 Selfridge 对 ${t(N)}$ 进行了一些进一步的探索。有一个简单的构造给出了下界：

$\displaystyle t(N) \geq \frac{3}{16} N - o(N)$

它来自于从标准分解 ${N! = 1 \times 2 \times \dots \times N}$ 开始，并将一些 ${2}$ 的幂从序列的后面部分转移到前面部分，以在某种程度上重新平衡这些项。更准确地说，如果从 ${\frac{3}{8}N}$ 和 ${N}$ 之间的偶数中移除一个 2 的幂，并从 ${\frac{3}{4}N}$ 到 ${N}$ 之间的 4 的倍数中移除一个额外的 2 的幂，这将释放 ${\frac{3}{8}N + o(N)}$ 个 2 的幂，然后可以将这些幂分配到 up to ${\frac{3}{16} N}$ 的数字中，以使它们的大小都至少为 ${\frac{3}{16} N - o(N)}$ 。一个更复杂的过程，涉及转移 ${2}$ 和 ${3}$ 的幂，然后给出了改进： ${t(N) \geq \frac{1}{4} N - o(N)}$ 。然而，在这一点上，事情变得更加复杂，Guy 和 Selfridge 提出了以下猜想：

(i) 对于所有 ${N \neq 1,2,4}$ ，是否 ${\frac{t(N)}{N} \leq \frac{1}{e}}$ 成立？
(ii) 对于所有 ${N \neq 56}$ ，是否 ${t(N) \geq \lfloor 2N/7 \rfloor}$ 成立？（在 ${N=56}$ 处，这个猜想几乎失败了： ${t(56) = 15 < 16 = \lfloor 2 \times 56/7 \rfloor}$ 。）
(iii) 对于所有 ${N \geq 300000}$ ，是否 ${\frac{t(N)}{N} \geq \frac{1}{3}}$ 成立？

在这篇文章中，我们建立了界限：

$\displaystyle \frac{1}{e} - \frac{O(1)}{\log N} \leq \frac{t(N)}{N} \leq \frac{1}{e} - \frac{c_0+o(1)}{\log N} \ \ \ \ \ (3)$

当 ${N \rightarrow \infty}$ 时，其中 ${c_0}$ 是显式常数：

$\displaystyle c_0 := \frac{1}{e} \int_0^1 \left \lfloor \frac{1}{x} \right\rfloor \log \left( ex \left \lceil \frac{1}{ex} \right\rceil \right)\ dx \approx 0.3044.$

特别是，这恢复了丢失的结果 (2)。先前 Erdös 和 Graham (Erdös 问题 #391) 猜想存在某个 ${c>0}$ 使得上界的形式为：

$\displaystyle t(N) \leq \frac{1}{e} - \frac{c+o(1)}{\log N} \ \ \ \ \ (4)$

我们推测 (3) 中的上界是尖锐的，因此：

$\displaystyle \frac{t(N)}{N} = \frac{1}{e} - \frac{c_0+o(1)}{\log N}, \ \ \ \ \ (5)$

这与 Guy 和 Selfridge 的上述猜想 (i)、(ii)、(iii) 是一致的，尽管在数值上收敛速度有些慢。

(3) 的上界论证非常简单，可以修改它来建立 Guy 和 Selfridge 的第一个猜想 (i)；原则上，(ii) 和 (iii) 现在也可以简化为有限的计算，但不幸的是，(3) 的下界中的隐含常数太弱，无法直接实现这一点。但是，现在有可能通过提供一套合适的分解来涵盖中等大小的 ${N}$ ，再加上一些有效版本的下界论证，来众包对 (ii) 和 (iii) 的验证，该论证可以建立 ${\frac{t(N)}{N} \geq \frac{1}{3}}$ 对于超过某个阈值的所有 ${N}$ 成立。Guy 和 Selfridge 挑选出的值 ${N=300000}$ 似乎是一个非常合适的测试用例：我尝试的构造略低于 ${100000}$ 的猜想阈值，但似乎勉强可以达到，只要对因子进行足够有效的重新排列就可以在这里工作。

我们现在描述 (3) 中上下界的证明。为了改进平凡的上界 (1)，可以使用 ${N!}$ 的大素数因子。事实上，!{[{N/e}](https://s0.wp.com/latex.php?latex=%7BN%2Fe%7D&bg=ffffff&fg=000000&s=0&c=20201002) 和 ${N}$ 之间的每个素数 ${p}$ 至少一次整除 ${N!}$ （并且 !{[{N/e}](https://s0.wp.com/latex.php?latex=%7BN%2Fe%7D&bg=ffffff&fg=000000&s=0&c=20201002) 和 ${N/2}$ 之间的那些整除两次），并且包含这样一个因子的任何因子 ${a_i}$ 因此必须显着大于基准值 !{[{N/e}](https://s0.wp.com/latex.php?latex=%7BN%2Fe%7D&bg=ffffff&fg=000000&s=0&c=20201002)。这个观察结果已经很容易导致 (4) 形式的某些上界，对于某个 ${c>0}$ ；如果还使用略小于 !{[{N/e}](https://s0.wp.com/latex.php?latex=%7BN%2Fe%7D&bg=ffffff&fg=000000&s=0&c=20201002) 的素数 ${p}$ （注意 ${p}$ 的任何超过 !{[{N/e}](https://s0.wp.com/latex.php?latex=%7BN%2Fe%7D&bg=ffffff&fg=000000&s=0&c=20201002) 的倍数实际上必须超过 ${\lceil N/ep \rceil p}$ ），就会得到精确的常数 ${c_0}$ 。

对于先前的下界构造，首先从初始分解 ${N! = 1 \times \dots \times N}$ 开始，然后试图通过移动一些素数因子来“改进”这个分解。对于 (3) 中的下界，我们改为从大致为以下形状的近似分解开始：

$\displaystyle N! \approx (\prod_{t \leq n < t + 2N/A, \hbox{ odd}} n)^A$

其中 ${t}$ 是目标下界（因此，略小于 !{[{N/e}](https://s0.wp.com/latex.php?latex=%7BN%2Fe%7D&bg=ffffff&fg=000000&s=0&c=20201002)），并且 ${A}$ 是一个适度大小的自然数参数（我们将取 ![{A \asymp \log^3 N}](https://s0.wp.com/latex.php?latex=%7BA+%5Casymp+%5Clog%5E3+N%7D&bg=ffffff&