← All problems

Erdős Problem #400 — Factorial divisibility and additive excess

46 years old · traced to

Fix an integer k≥2k\ge 2. For each positive integer nn, let gk(n)g_k(n) be the maximum of a1+⋯+ak−na_1+\cdots+a_k-n over nonnegative integers a1,…,aka_1,\ldots,a_k satisfying a1!⋯ak!∣n!a_1!\cdots a_k!\mid n!:

gk(n)=max⁡{a1+⋯+ak−n:ai∈Z≥0, a1!⋯ak!∣n!}.g_k(n)=\max\left\{a_1+\cdots+a_k-n: a_i\in\mathbb Z_{\ge 0},\ a_1!\cdots a_k!\mid n!\right\}.

The maximum exists: each admissible aia_i is at most nn, and the admissible set is nonempty. Allowing zero rather than requiring positive aia_i does not change the maximum, since replacing any zero by one leaves the factorial product unchanged and increases the sum. Erdős Problems #400 Prime-Power Rarefaction and a Density-One Lower Bound for Erdős Problem 400, arXiv:2606.23661v2

For this fixed kk, the question is whether there is a constant ckc_k such that both

∑1≤n≤xgk(n)∼ckxlog⁡x\sum_{1\le n\le x}g_k(n)\sim c_kx\log x

and, for every ε>0\varepsilon>0,

#{1≤n≤x:∣gk(n)−cklog⁡x∣>εlog⁡x}=o(x)(x→∞).\#\left\{1\le n\le x:|g_k(n)-c_k\log x|>\varepsilon\log x\right\}=o(x) \qquad (x\to\infty).

The second condition expresses the proposed almost-all asymptotic, with an exceptional set of density zero. Erdős Problems #400 Prime-Power Rarefaction and a Density-One Lower Bound for Erdős Problem 400, arXiv:2606.23661v2

Background

Erdős and Graham recorded the problem in Old and New Problems and Results in Combinatorial Number Theory (1980, p. 77). Its central tension is that factorial divisibility imposes simultaneous constraints at every prime, while the quantity being maximized is the excess of the sum of the factorial arguments over nn. In particular, admissibility is equivalent to the inequalities ∑ivp(ai!)≤vp(n!)\sum_i v_p(a_i!)\le v_p(n!) for every prime pp, where vp(m!)v_p(m!) is the exponent of pp in m!m!. Erdős and Graham, ErGr80, p. 77 Prime-Power Rarefaction and a Density-One Lower Bound for Erdős Problem 400, arXiv:2606.23661v2

The original account notes the elementary pointwise estimate gk(n)≪klog⁡ng_k(n)\ll_k\log n, while observing that the best possible constant was unknown. The later bounds below sharpen this order estimate and address the average and density-one questions quantitatively. Erdős Problems #400 Prime-Power Rarefaction and a Density-One Lower Bound for Erdős Problem 400, arXiv:2606.23661v2

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.