Decomposing a factorial into large factors

1. INTRODUCTION

• t(N) is the largest threshold for which N! has an N-factor factorization whose every factor is at least t(N), equivalently allowing a relaxed admissible subfactorization formulation.The relaxed formulation permits at least N factors before deleting and enlarging factors to obtain exactly N factors.Source: §1 · pp. 1–2
• The factorial’s abundance of tiny prime factors makes this problem more tractable than arbitrary bin covering, enabling high-precision estimates of t(N).For arbitrary integers, the analogous problem is essentially NP-hard bin covering; here, factors 2 and 3 provide unusually flexible prime redistribution.Source: §1 · pp. 1, 6
• The paper answers prior questions by proving t(N) ≤ N/e except for N = 1, 2, 4, t(N) ≥ ⌊2N/7⌋ for N ≠ 56, and t(N) ≥ N/3 for N ≥ 43632, with the latter threshold best possible.The results address conjectures attributed to Guy and Selfridge and related earlier work.Source: §1 · p. 2
• The authors obtain a sharper upper bound and numerical evidence suggesting that the refined approximation in (1.8) may improve the asymptotic estimate.The improved upper bound is described as asymptotic to the expression in (1.5), while (1.8) is conjectured to become sharper.Source: §1 · pp. 3, 5, Figure 1 · p. 3
• The proof combines greedy algorithms, linear and integer programming, prime-factor rearrangements, an accounting equation, and modified approximate factorizations that become efficient as N grows.The modified factorization strategy uses 3-smooth factors and the density of powers of 2 and 3 on a logarithmic scale to correct prime surpluses and deficits.Source: §1 · pp. 5–6

1.1. Linear and integer programming solvers.

• The paper uses solver outputs with exact-arithmetic or direct-factorization checks, but upper bounds in Figures 6, 16, and 17 remain unverified and are not used in the results.The project was developed collaboratively with supporting code and data in a GitHub repository.Source: §1.1 · p. 6, §1.2 · pp. 6–7

2. NOTATION AND BASIC ESTIMATES

• A multiset is a subfactorization when it has nonnegative p-surplus for every prime, while a complete factorization is balanced at every prime.The p-deficit is the negative of the p-surplus, and zero surplus means p-balance.Source: §2 · p. 7
• t(N) ≥ t exactly when the maximal cardinality M(N, t) of a t-admissible subfactorization satisfies M(N, t) ≥ N.The relaxed subfactorization formulation supports the paper’s analysis of t(N).Source: §2 · p. 8

2.1. Approximation by 3-smooth numbers.

• 3-smooth numbers have the form 2^n3^m, and the smallest such number at least x is denoted ⌈x⌉⟨2,3⟩.The primes 2 and 3 serve as the paper’s tiny primes and provide a liquidity pool for factor exchanges.Source: §2.1 · p. 8
• For large L, the approximation error parameter κ_L satisfies κ_L ≪ log^-c L for an absolute c > 0.The associated estimates are described as asymptotically efficient, especially when x is a power of 12.Source: §2.1 · pp. 8–9

2.2. Sums over primes.

• The paper uses total and augmented total variation to control sums of bounded-variation functions over primes.The augmented variation includes endpoint jumps; for an interval indicator, it equals 2.Source: §2.2 · pp. 9–10
• The prime-sum estimates use an error term E(x) whose accuracy is comparable to what the Riemann hypothesis would provide for x ≤ 10^18.The simplified estimates suffice for the paper’s applications, while E(x) is non-decreasing and E(x)/x is non-increasing.Source: §2.2 · p. 11

3. GREEDY ALGORITHMS

• The greedy algorithm repeatedly uses surplus prime factors to build factors at least t, producing a verifiable lower bound on M(N,t) and hence on t(N).Its output is an explicit subfactorization that can be independently checked, although parameter-selection decisions make the algorithm imprecisely specified.Source: §3 · p. 11
• The basic greedy method computes exact t(N) for N≤79, while at N=3×10^5 it proves M(N,N/3)≥N+372 versus the exact N+455.Its bound quality declines as N grows, motivating faster variants and complementary methods.Source: §3 · p. 12

3.2. A fast variant of the greedy algorithm.

• The fast variant runs in O(N^3/4+ε) time and O(N^2/3+ε) space, with space reducible to O(N^1/2+ε), at the cost of slightly weaker bounds.It precomputes only M-smooth cofactors and handles remaining small-prime cases through cofactors for p_i or p_i^2.Source: §3.2 · pp. 13–14

3.3. Optimizing bounds produced by the greedy algorithm.

• The optimized search extends the greedy proof of t(N)≥N/3 to N∈[67425,10^14], while the heuristic search itself converges about twice as fast as standard bisection.Computing t_1(N) remains expensive, potentially requiring O(N) greedy calls and limiting practical computation to about N=10^9.Source: §3.3 · pp. 14–15

3.4. Proving Theorem 1.3(iii) for 67425≤N≤10^14.

• The remaining interval is handled by a staged procedure that uses exact t_1(N) computations through 10^6 and fast-variant certificates through 10^14, with repository data enabling verification.This leaves 43632≤N<67425 and N>10^14 for other methods, while N=43631 must be shown to fail the N/3 bound.Source: §3.4 · p. 15

• Proposition 4.1 expresses M(N,t) as an integer program over minimal t-admissible divisors of N!, making t(N) computationally accessible.The formulation uses multiplicity variables constrained by prime valuations of N!.Source: §4 · pp. 15, 17
• Relaxing the integer program gives the upper bound M(N,t)≤⌊M_R(N,t)⌋, while a dual linear program supplies prime weights for computing M_R(N,t).The dual description applies for t≤N/2, the relevant regime apart from small cases.Source: §4 · p. 17
• For N≤10^4, linear programming is tight except for eleven listed values requiring integer programming, and the resulting exact values are plotted in Figure 6.The integer program can compute M(N,t), and hence t(N), precisely at this scale, although faster methods are preferred first.Source: §4 · pp. 17, 19, Figure 6 · p. 19
• The linear-programming bound proves t(43631)<43631/3, while integer programming proves t(N)≥N/3 for every 43632≤N≤8×10^4.The exact upper certificate is M(43631,14544)≤43631−47/1257, establishing that 43632 is the best possible threshold.Source: §4 · p. 19
• The floor+residuals method is fast and highly accurate through N≤3×10^5, computing t(N) exactly for N≤600 except N=155 and proving the N/3 lower bound on 43632≤N≤4.5×10^4.It floors the linear-program solution, then greedily assembles factors from residual prime valuations.Source: §4 · p. 20
• For 10^4<N≤9×10^8, smooth factorization runs considerably faster than the full linear program while producing lower bounds close to the linear-programming upper bound and outperforming the greedy algorithm.Figure 7 compares the smooth-factorization lower bound with the linear-programming upper bound over a broad range.Source: §4 · p. 20, Figure 7 · p. 21

Upper-bound methods

• The weighted construction verifies the conditions needed to derive the general upper bound in Theorem 5.1.The weights are nonnegative, and the argument checks the required inequalities for the relevant integers and prime-factor cases.Source: §5 · p. 24
• Theorem 5.1 gives especially good upper bounds for large N, while linear programming is superior for medium N.The comparison is illustrated by Figures 1, 2, and 11.Source: §5 · p. 24

Numerical bounds

• The linear programming upper bound is exact throughout the displayed region except at N = 155, where it is off by one.Figure 11 compares this upper bound with the greedy lower bound and floor+residual bounds.Source: Figure 11 · p. 25

Asymptotic approximation

• The section’s analytic estimates support a numerically accurate approximation for medium-sized N, while the paper conjectures that the bound may hold more generally.Additional terms may improve the approximation further.Source: §5 · p. 25

Theorem 1.3(i)

• Theorem 1.3(i) is established by reducing the claim to a numerical inequality verified for 80 ≤ N ≤ 5000 and then using monotonicity for N ≥ 5000.The final verification at N = 5000 has ample margin.Source: §5 · pp. 27–28

Lower-bound criterion and implementation

• The method partitions integers using downsets, extracts selected small-prime factors from {1, …, N}, and reallocates them through weights satisfying balance and admissibility constraints.The resulting criteria are finite or asymptotic linear programs whose certificates can be checked in exact arithmetic.Source: §6 · pp. 28, 29, 32

Scope and limitation of the rearrangement approach

• Redistributing only powers of two and three cannot establish a bound of the form t(N) ≥ (1/4 + o(1))N, whereas the broader rearrangement framework reaches αN for every α < 1/e.The obstruction is proved using weighted inequalities over 3-smooth factors, with coefficients discovered by finite linear programming and verified exactly.Source: §6 · pp. 28, 34, 35, 36

Lower bounds from rearranging the standard factorization

• t(N) ≥ N/3 for sufficiently large N via a computer-assisted linear-programming certificate using rearrangements of prime factors up to 7.The weights are found numerically, converted to rational numbers, and verified in exact arithmetic; the proof does not provide an explicit threshold for N.Source: §6 · p. 33

Limit of rearranging powers of 2 and 3

• t_2,3(N) < N/4 for N > 26244, and the threshold is best possible.Exact computation gives t_2,3(26244) = N/4, after which integer- and linear-programming arguments establish the strict inequality.Source: §6 · pp. 34–35

Asymptotic lower bound

• For every fixed α < 1/e, t(N) ≥ αN for all sufficiently large N.This recovers a weak asymptotic form of the section’s target lower bound using the rearrangement method.Source: §6 · p. 36

Parameter and downset construction

• The proof selects nested parameters c_0, M, C_0, p_−, and p_+ with log p_+ ≍ log^2 log p_−, then defines a downset of numbers built from powers of 2 and primes in [p_−, p_+].The associated densities σ_d,D are stated to be explicitly computable.Source: §6 · p. 36

Verification of the required conditions

• The coefficient rules are verified against conditions (6.8) and (6.9), with (6.8) handled by direct computation, Mertens’ theorem, and the chosen parameters.For primes in the selected interval both sides equal μ_p, while the p = 2 case follows from the parameter choice.Source: §6 · pp. 37–38

Accounting equation

• The accounting equation measures the discrepancy between N! and an approximate factorization through prime-exponent surpluses, deficits, and t-excess.It is obtained by applying unique factorization to the rational number N!/∏B.Source: §7 · p. 40

Example

• Replacing a factor 5 by 2 in the 3-admissible example removes both a 2-surplus and a 5-deficit, producing a factorization of 5!.The example illustrates how local prime imbalances can be repaired while changing the t-excess.Source: §7 · p. 40

Equivalent formulation

• t(N) is equivalently the largest threshold admitting a t-admissible subfactorization of N! with the required cardinality condition.The relaxed formulation is convenient because subfactorizations can be converted into factorizations of cardinality N.Source: §7 · p. 40

Budget interpretation

• For t=N/e^(1+δ), the available logarithmic budget is δN+O(log N), which constrains the combined t-excess and prime surpluses.Non-negativity recovers the basic upper bound, while primes larger than t cannot appear in an admissible multiset.Source: §7 · p. 40

Repair proposition

• Proposition 8.1 gives conditions under which an approximate t-admissible multiset can be repaired into a subfactorization of N! balanced at non-tiny primes.The construction controls the remaining tiny-prime surpluses and the increase in t-excess through auxiliary parameters.Source: §8 · pp. 41, 46

Success criterion

• The algorithm’s success depends on sufficient tiny-prime supply and on keeping the non-negotiable δ2 contribution, as well as the other error terms, within the available budget.The stated secondary condition ensures enough tiny primes for the required adjustments.Source: §8 · p. 42

Large-prime repair

• The algorithm first removes factors containing large primes and replaces them with multiples of p⌈t/p⌉, making the multiset t-admissible and balanced at large primes.These changes alter t-excess and can affect surplus bounds at medium and tiny primes.Source: §8 · p. 43

Small and medium primes

• Small and medium prime imbalances are repaired by replacing deficient primes with 4.5-based factors and adding factors to eliminate medium and small-prime surpluses.The replacements reduce the targeted deficits or surpluses while incurring controlled increases in t-excess and the 2,3 norm.Source: §8 · pp. 43–44

Tiny-prime correction

• After these repairs, the remaining discrepancy is supported on powers of 2 and 3 and is corrected by adding suitable 3-smooth factors.The added factors preserve t-admissibility and yield balance at all non-tiny primes.Source: §8 · pp. 45–46

Initial construction

• The initial multiset B(0) consists of 3-rough integers in (t,t(1+σ)], each repeated A times, so it is t-admissible and has no tiny-prime contribution.This choice supplies the approximate factorization used in the later repair analysis.Source: §9 · p. 46

Parameter estimates

• The parameter estimates scale as δ1≈1/A, δ2≈1/log N, δ3≈A/(K log N), and δ7≈κL/log N, while several remaining terms are lower order.The estimates also give γ2,γ3≈log L/log N and α3≈A/K.Source: §9 · p. 46

Parameter selection

• These scalings suggest taking A moderately large, K only slightly larger than A, and L significantly smaller than N.The choices balance the competing contributions from the repair parameters and the asymptotic error terms.Source: §9 · p. 46

Auxiliary construction

• The auxiliary parameter L defines powers of 2 and 3 below t/L, which are used to construct γ2, γ3, κ*, and the associated 3-smooth correction factors.The resulting choices satisfy the admissibility and correction conditions needed by the repair proposition.Source: §9 · p. 47

Lower bound

• The asymptotic construction establishes t(N)≥t for sufficiently large N using the previously defined approximate factorization and parameter choices.The verification reduces to the conditions required by Theorem 8.1, together with estimates for the relevant δi and αi terms.Source: §10 · pp. 48–49

Asymptotic approximation

• The function fN/t(etx/N) is approximated by fe(x) outside an exceptional set of measure O(1/log N), enabling the asymptotic estimates used in the verification.This approximation is combined with the stated error estimates to control the repair conditions.Source: §10 · p. 50

Analytic estimates

• Prime-distribution estimates, including Mertens’ theorem, Brun–Titchmarsh, and the prime number theorem, bound the remaining surplus and variation terms.The function fN/t has O(K) monotonicity pieces and is bounded by 1 on the relevant interval, giving an augmented variation bound of O(K).Source: §10 · pp. 49–50

Numerical verification

• A remaining inequality is numerically verified for K′≤100, while positivity on suitable blocks and the triangle inequality extend the verification to larger K′.Figure 18 records the plotted quantities associated with this check.Source: §10 · p. 51, Figure 18 · p. 52

11. GUY–SELFRIDGE CONJECTURE

• The construction chooses parameters A and K numerically and exploits the absence of primes in a selected interval to simplify the estimates.The interval is K<p≤K(1+σ), with K=293 and upper endpoint approximately 306.952.Source: §11 · pp. 52, 54
• The proof reduces the required estimates to short prime ranges, allowing the bounds to be computed quickly even for very large N.Theorem 2.3 supplies bounds for sums over large ranges, leaving only ranges such as p≤K or p≤K(1+σ).Source: §11 · p. 52
• Monotone bounds can be checked at endpoint values, while non-monotone subtraction terms require separate treatment at N=N0, N≥10^70, and intermediate intervals.The intermediate range is handled by conservative interval estimates for the delicate quantities.Source: §11 · pp. 52, 55
• The estimates for δ5, δ7, α2, and α5 satisfy the needed conditions with room to spare for N≥10^70.Although the bound for δ5 is slightly worse, improved bounds for δ2 and δ7 compensate for it.Source: §11 · p. 55
• Theorem 1.3(ii), (iii) are verified for all N≥10^11, with the verification extendable to N≥6×10^10 with additional effort.Interval arithmetic covers intermediate ranges that are not handled directly by endpoint estimates.Source: §11 · pp. 55–56

APPENDIX A. DISTANCE TO THE NEXT 3-SMOOTH NUMBER

• Theorem A.1 is proved by bounding the distance to the next 3-smooth number through a lemma involving natural-number parameters n1, n2, m1, and m2.The proof considers the smallest 3-smooth number at least t and uses divisibility to establish the bound.Source: Appendix A · p. 56
• The parameter bounds are sharp in examples such as κ_4.5≤log 4/log 27=0.16989…, because the relevant next 3-smooth numbers are 6 and 48.These sharp examples establish part (i) of the theorem.Source: Appendix A · p. 57
• Table 4 organizes efficient parameter choices so that the number of rows in each group matches the continued-fraction coefficients 1, 1, 2, 2, 3, ….Boldface identifies the parameters attaining the minimum or maximum.Source: Table 4 · p. 57
• Continued-fraction convergents to log 3/log 2 provide effective rational approximants for selecting the parameters in the bound.The convergents obey the standard recurrence, and related approximants such as 5/3 and 11/7 can also be used.Source: Appendix A · p. 57
• The error exponent c could plausibly approach 1, but doing so is essentially equivalent to determining that log 3/log 2 has irrationality measure 2.This remains an open problem.Source: Appendix A · p. 58

APPENDIX B. ESTIMATING SUMS OVER PRIMES

• The appendix establishes Theorem 2.3 by combining explicit prime-sum estimates valid across several ranges of x.Different cited results cover ranges below and above 10^19, with additional coverage extending to e^55 and beyond.Source: Appendix B · pp. 58–59
• Integration by parts converts weighted sums into integrals involving a bounded-variation function, providing the analytic framework for the estimates.The lemma applies to a discrete function a and continuous function f under a summatory bound.Source: Appendix B · p. 58
• The appendix proves a sharper estimate with an absolute constant c and uses monotonicity of the error function to reduce the verification to a simpler bound.The resulting estimates support the prime-sum bounds used elsewhere in the paper.Source: Appendix B · pp. 58–59
• Assuming the Riemann hypothesis, the ε1, ε2, and ε3 terms in the definition of the error function can be deleted for x≥5000.This follows because the cited prime-sum bound then holds throughout that range.Source: Appendix B · p. 59

APPENDIX C. COMPUTATION OF 𝑐0 AND RELATED QUANTITIES

• The constant c0 is evaluated by changing variables to resolve an oscillatory singularity and expressing it as an improper integral.The transformed integrand lies between 0 and 1/y^3, giving a rigorous tail bound after truncation.Source: Appendix C · p. 60
• Slowly convergent sums are accelerated by subtracting an asymptotically similar sum, summing a finite partial sum, and rigorously bounding the remaining tail.The computation uses a partial sum through k=10^5 and interval arithmetic.Source: Appendix C · pp. 60–61
• The Erdős–Turán inequality controls normalized tails through weighted exponential sums, whose estimates follow from telescoping-series bounds.The exponential sum satisfies a bound proportional to 1/(K+1)^2 sin(πn/e).Source: Appendix C · p. 61
• Because e has irrationality measure 2, choosing K=10^6 and N=10^5 yields error terms of order O(log K/K^2) for the numerical computation.An interval arithmetic computation then supplies the resulting numerical bounds.Source: Appendix C · p. 62