Erdős Problem #374

Problem 374. Growth of $D_k$ for products of factorials that are squares --- Round 2

1) ROUND-2 OBJECTIVE

Path (C): obstruction/correction via a genuine strengthening of the Round-1 lower bounds.

Round 1 already established \[ D_3(X)\gg \sqrt{X},\qquad D_4(X)\gg X,\qquad D_5(X)\gg \frac{X}{\log X},\qquad D_6(X)\gg \frac{X}{\log X}, \] but left the original question "is $D_6(X)\gg X$?" unresolved. In this round I will not restart from scratch. Instead, I will use the Round-1 semiprime strategy and strengthen it in two ways:

• obtain an explicit leading constant for the $D_5(X)$ lower bound, and
• prove the genuinely stronger statement \[ D_6(X)=\omega\!\left(\frac{X}{\log X}\right). \]

This does not settle the original linear-growth question for $D_6$, but it is a strict advance over Round 1.

2) Round-1 FOUNDATION USED

I use the following Round-1 results without reproving them.

• The factorial identities \[ x!(x-1)!=\frac{(x!)^2}{x}, \qquad x!(x-1)!y!(y-1)!=\frac{(x!y!)^2}{xy}. \]
• The Round-1 consequence that if $n=ab$ with $a,b>1$ and $a\neq b$, then $n\in F_6$.
• The Round-1 use of Erdős--Graham's statements that:
  • if a proper divisor of $n$ belongs to $\{2,3,5,7,11\}$, then $n\in F_5$;
  • for any fixed prime $q$, almost all numbers of the form $pq$ (with $p$ prime) do not belong to $F_4$.

3) NEW INSIGHT / TOOL (ROUND-2)

The new ingredient is that Erdős--Graham's Theorem 3 is not really special to $13$: their proof is explicitly said to work for $13$ and all larger primes. Therefore, for every fixed prime $q\ge 13$, almost all numbers of the form $pq$ fail to lie in $F_5$.

Once this is combined with the Round-1 observation $pq\in F_6$, one can union over arbitrarily many fixed primes $q\ge 13$. Because the reciprocal sum of the primes diverges, this forces \[ D_6(X)=\omega\!\left(\frac{X}{\log X}\right). \]

4) ATTACK PLAN (ROUND-2)

Round 1 left two concrete gaps:

• the $D_5(X)\gg X/\log X$ lower bound used only one semiprime family;
• the $D_6(X)\gg X/\log X$ lower bound used only the family $13p$.

To improve these, I will:

1. union the five $D_5$-families $qp$ with $q\in\{2,3,5,7,11\}$ and show the overlaps are only $O(1)$;
2. union any fixed finite collection of $D_6$-families $qp$ with $q\ge 13$ prime, again with only $O(1)$ overlap;
3. let the finite collection grow after $X\to\infty$ to force an arbitrarily large constant in front of $X/\log X$.

5) WORK (ROUND-2)

Lemma 5.1 (semiprimes with a small fixed factor give many elements of $D_5$)

Let \[ S_5:=\{2,3,5,7,11\}. \] Then \[ D_5(X)\ge \left(\sum_{q\in S_5}\frac1q+o(1)\right)\frac{X}{\log X}. \]

Proof.

Fix $q\in S_5$, and define \[ A_q(X):=\{qp\le X:\ p \text{ prime},\ p\neq q,\ qp\notin F_4\}. \] Because $q$ is a proper divisor of $qp$ and $q\in\{2,3,5,7,11\}$, Erdős--Graham's Fact 7 gives \[ qp\in F_5. \] Since by definition $qp\notin F_4$, every element of $A_q(X)$ lies in \[ F_5\setminus F_4=D_5. \] Hence \[ A_q(X)\subseteq D_5. \]

Now Erdős--Graham also prove that for any fixed prime $q$, almost all numbers of the form $pq$ do not belong to $F_4$. Therefore \[ |A_q(X)|=\pi(X/q)-o(\pi(X/q)) =\left(\frac1q+o(1)\right)\frac{X}{\log X} \] by the prime number theorem.

Next, if $q_1\neq q_2$ belong to $S_5$ and \[ q_1p_1=q_2p_2 \] with $p_1,p_2$ prime, then primality forces \[ p_1=q_2,\qquad p_2=q_1. \] So for each ordered pair $(q_1,q_2)$ there is at most one overlap, and therefore \[ \sum_{\substack{q_1,q_2\in S_5\\ q_1\neq q_2}} |A_{q_1}(X)\cap A_{q_2}(X)| = O(1). \] Hence \[ D_5(X)\ge \left|\bigcup_{q\in S_5} A_q(X)\right| = \sum_{q\in S_5}|A_q(X)| - O(1) = \left(\sum_{q\in S_5}\frac1q+o(1)\right)\frac{X}{\log X}. \] This proves the lemma. $\square$

Lemma 5.2 (fixed semiprime families in $D_6$)

Let $q\ge 13$ be a fixed prime. Then, for almost all primes $p\neq q$, \[ qp\in D_6. \]

Proof.

Fix such a prime $q$.

First, $qp\in F_6$ for every prime $p\neq q$. Indeed, taking the six-term set \[ \{qp,\ qp-1,\ q,\ q-1,\ p,\ p-1\}, \] we have \[ (qp)!(qp-1)!q!(q-1)!p!(p-1)! = \frac{\big((qp)!q!p!\big)^2}{(qp)\,q\,p} = \frac{\big((qp)!q!p!\big)^2}{q^2p^2}, \] which is a perfect square. Thus $qp\in F_6$.

Second, Erdős--Graham's Theorem 3 proves that for almost all primes $p$, one has $13p\notin F_5$; and immediately after the proof they explain that the same proof works for $13$ and all larger primes. Therefore, for our fixed $q\ge 13$, almost all primes $p$ satisfy \[ qp\notin F_5. \]

Combining the two statements, for almost all primes $p\neq q$, \[ qp\in F_6\setminus F_5=D_6. \] This proves the lemma. $\square$

Lemma 5.3 (finite unions of $D_6$-families)

Let $S$ be any fixed finite set of primes, all at least $13$. Then \[ D_6(X)\ge \left(\sum_{q\in S}\frac1q+o(1)\right)\frac{X}{\log X}. \]

Proof.

For each $q\in S$, define \[ B_q(X):=\{qp\le X:\ p \text{ prime},\ p\neq q,\ qp\notin F_5\}. \] By Lemma 5.2, for each fixed $q\in S$, \[ |B_q(X)|=\pi(X/q)-o(\pi(X/q)) = \left(\frac1q+o(1)\right)\frac{X}{\log X}, \] and every element of $B_q(X)$ belongs to $D_6$.

As in Lemma 5.1, if $q_1\neq q_2$ and \[ q_1p_1=q_2p_2 \] with $p_1,p_2$ prime, then necessarily \[ p_1=q_2,\qquad p_2=q_1. \] Hence the total overlap among the finitely many families $\{B_q(X)\}_{q\in S}$ is only $O_S(1)$. Therefore \[ D_6(X)\ge \left|\bigcup_{q\in S} B_q(X)\right| = \sum_{q\in S}|B_q(X)| - O_S(1) = \left(\sum_{q\in S}\frac1q+o(1)\right)\frac{X}{\log X}. \] This proves the lemma. $\square$

Corollary 5.4 (strict Round-2 advance)

One has \[ D_6(X)=\omega\!\left(\frac{X}{\log X}\right). \]

Proof.

Let $A>0$ be arbitrary. Because the reciprocal sum of the primes diverges, there exists a finite set $S$ of primes $q\ge 13$ such that \[ \sum_{q\in S}\frac1q > 2A. \] Now $S$ is fixed, so Lemma 5.3 applies: \[ D_6(X)\ge \left(\sum_{q\in S}\frac1q+o(1)\right)\frac{X}{\log X}. \] For all sufficiently large $X$ the parenthesis is at least $A$, and thus \[ D_6(X)\ge A\frac{X}{\log X}. \] Since $A>0$ was arbitrary, this is exactly \[ D_6(X)=\omega\!\left(\frac{X}{\log X}\right). \] $\square$

6) ADVERSARIAL VERIFICATION

Potential weak points and checks:

• Overlap problem. Two different semiprime families $q_1p$ and $q_2p'$ can coincide only in the trivial swapped-factor case; for a fixed finite set of $q$ this contributes only $O(1)$ points. So no density is lost here.

• Uniformity in $q$. I never need an error term uniform in $q$ over all large primes. In Lemma 5.3 the set $S$ is fixed before letting $X\to\infty$, so the individual $o(1)$ terms may depend on $q$.

• Could some $qp$ lie in $F_5$ and still belong to $D_6$? Yes, and I do not use them. The lower bound counts only the subfamily explicitly known to be outside $F_5$.

• Does this prove $D_6(X)\gg X$? No. The argument only yields arbitrarily large multiples of $X/\log X$, not a positive proportion of all integers. So the original question from Round 1 remains open.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Relative to Round 1, the new unconditional statements are: \[ D_5(X)\ge \left(\frac12+\frac13+\frac15+\frac17+\frac1{11}+o(1)\right)\frac{X}{\log X}, \] and \[ D_6(X)=\omega\!\left(\frac{X}{\log X}\right). \] The original question "is $D_6(X)\gg X$?" remains open.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 68%

9) REFERENCES

[EG76] P. Erdős and R. L. Graham, On products of factorials, Bull. Inst. Math. Acad. Sinica 4 $1976$, 337--355.

[DNSS14] A. Dujella, F. Najman, N. Saradha, and T. N. Shorey, Products of three factorials, Publ. Math. Debrecen 85 $2014$, 3--13.

Erdős Problem #374: independent continuation

Date: 2026-09-23. Research attempt; no claim of a new published result.

1) TARGET AND SOURCE AUDIT

Let $F(m)$ be the least number of distinct factorials, including $m!$, whose product is a square, and $D_k=\{m:F(m)=k\}$. Determine their growth for $3\le k\le6$, especially whether $D_6(X)\gg X$.

All supplied versions considered: 374.tex. The source enlarges fixed-prime semiprime families and obtains an unbounded multiple of $X/\log X$. I show why even complete success on every semiprime cannot yield the requested positive density.

2) WORK

An elementary density barrier.

Let $\mathcal P_y$ be the primes at most $y$, and write $w_y(n)=\#\{p\in\mathcal P_y:p\mid n\}$. Every semiprime $n=pq$ has $w_y(n)\le2$. Pointwise, \[ \mathbf1_{w_y(n)\le2}\le e^2e^{-w_y(n)}. \] The right-hand side is periodic modulo $\prod_{p\le y}p$. By CRT its mean is \[ e^2\prod_{p\le y}\left(1-{1-e^{-1}\over p}\right). \] As $y\to\infty$ this tends to zero, using the divergence of $\sum_p1/p$ and $1-u\le e^{-u}$. For every fixed $y$ it bounds the upper density of all semiprimes. Therefore the semiprimes have natural density zero.

The same proof works for integers with at most any fixed number $r$ of distinct prime factors, replacing $e^2$ by $e^r$. Thus no construction restricted to a fixed bound on the number of prime factors can establish $D_6(X)\gg X$, even if it settles every integer in its selected class. This is stronger than simply observing that one fixed semiprime family has size about $X/\log X$.

3) ADVERSARIAL VERIFICATION

The auxiliary parameter $y$ is fixed before taking the density limit; only afterward is it sent to infinity. This avoids any unjustified uniform error estimate. The result is a barrier for restricted constructions, not an upper bound on $D_6$ itself. The square-product identity only proves $F(m)\le6$; excluding smaller representations is a separate requirement.

4) FINAL

UNRESOLVED. Positive-density membership in $D_6$, and the requested orders for the other $D_k$, remain unproved. One needs families with unbounded prime-factor complexity together with control of minimal representation length.

5) SOURCES CHECKED

Full 374.tex read. Indexed official statement https://www.erdosproblems.com/374 checked on 2026-09-23; the absent GitHub formalization was not used. The source's imported Erdős--Graham semiprime theorem is not required by the density-barrier proof.

6) COMPLETION ESTIMATE

This is a conservative subjective measure of progress toward the original question, not a probability of correctness or a claim that the remaining work is routine. COMPLETION: 6%

Problem 374. Growth of $D_k$ for products of factorials that are squares

FORMAL RESTATEMENT

For a finite set $A\subset \mathbb{N}$ let \[ m(A)\;:=\;\prod_{a\in A} a!,\qquad M(A)\;:=\;\max A. \] For $k\ge 1$ define \[ F_k\;:=\;\left\{n\in\mathbb{N}:\exists A\subset\mathbb{N}\text{ with }|A|\le k,\ M(A)=n,\ m(A)\text{ a perfect square}\right\}, \] with the convention $F_0:=\varnothing$, and define \[ D_k:=F_k\setminus F_{k-1}. \] Equivalently, for $m\in\mathbb{N}$ define $F(m)$ as the minimal $k\ge 2$ (if it exists) for which there are $a_1<\cdots<a_k=m$ with $\prod_{i=1}^k a_i!$ a square; then $m\in D_k$ iff $F(m)=k$.

The question asks for the order of growth of \[ D_k(n):=|D_k\cap\{1,2,\dots,n\}| \] for $3\le k\le 6$. In particular, is $D_6(n)\gg n$?

QUICK LITERATURE / CONTEXT CHECK

The problem is recorded as open on the Erdős problems database, together with several basic facts (no primes in any $D_k$; $D_2=\{a^2:a>1\}$; $D_6$ has least element $527$; and $D_k=\varnothing$ for $k>6$).(See the summary on the Erdős problems page.)

Erdős--Graham $1976$ introduced/analysed the sets $F_k,D_k$ and proved, among other things:

• $D_k=\varnothing$ for $k>6$ (so every $n\in\mathbb{N}$ that ever occurs occurs with $k\le 6$);
• $D_3(n)=o(D_4(n))$ (in particular $D_3(n)=o(n)$);
• $D_4$ has positive density, using the explicit inclusion "non-squarefree $\subset F_4$".

Dujella--Najman--Saradha--Shorey $2014$ give a clean list of standard constructions producing many elements of $D_3$, and record the best known upper bounds for $D_3(n)$.

ATTACK PLAN

1. Use the explicit constructions of Erdős--Graham to give unconditional lower bounds for $D_k(n)$.
2. Combine these with known upper bounds (mainly for $D_3(n)$) to bracket the possible growth.
3. For $k\in\{5,6\}$, use the semiprime families $2p$ and $13p$ together with Erdős--Graham's "almost all $pq$ are not in $F_4$" and "almost all $13p$ are not in $F_5$" to get explicit $\gg n/\log n$ lower bounds.
4. Explain why the remaining gaps (e.g. whether $D_6(n)\gg n$) look genuinely open: proving linear growth would require control on how often $n$ belongs to $F_5$ (or $F_4$) among squarefree integers.

WORK

1. Two algebraic identities that power many inclusions

2. A uniform $\Omega(\sqrt{n})$ lower bound for $D_3(n)$

We recall the standard "$D_3$ construction" (Dujella--Najman--Saradha--Shorey, property (iv)).

Taking $b=2$ gives $Q(2!)=2$ and hence the explicit infinite subsequence $\{2a^2:a\ge 2\}\subset D_3$. Counting these yields:

3. Known upper bounds for $D_3(n)$

Erdős--Graham proved $D_3(n)=o(D_4(n))$ (in particular $D_3(n)=o(n)$). Dujella--Najman--Saradha--Shorey record a sharper bound due to Saradha--Shorey: \[ D_3(X)=O\!\left(\frac{X\,\log_3 X}{\log X\,\log_2 X}\right) \] (where $\log_j$ denotes iterated logarithms). We will treat this as a black-box literature input.

4. $D_4(n)$ has linear growth (positive density)

Erdős--Graham observed that if $n$ has a nontrivial square factor then $n\in F_4$. The proof is a one-line application of Lemma Lemma (Square-factor and two-factor identities)$2$.

Let $\mathsf{NSF}(n)$ be the set of integers $\le n$ that are not squarefree. It is classical that $|\mathsf{NSF}(n)|=(1-6/\pi^2)n+o(n)$. Combining this with Lemma lem:non-squarefree-in-F4 and the fact that $D_3(n)=o(n)$ gives a linear lower bound for $D_4(n)$.

5. A $\gg n/\log n$ lower bound for $D_5(n)$

Erdős--Graham prove (i) if $p\in\{2,3,5,7,11\}$ is a proper divisor of $n$ then $n\in F_5$, and (ii) for any fixed prime $q$, almost all semiprimes of the form $pq$ (with $p$ prime) do not lie in $F_4$. They also show that if $a_1\in D_3$ and $a_1=2P$ with $P$ an odd prime, then $a_1\in\{6,10\}$.

From these inputs one can extract a clean lower bound using the family $n=2p$.

6. A $\gg n/\log n$ lower bound for $D_6(n)$

Erdős--Graham also prove:

• If $n=ab$ with $a,b>1$ and $a\ne b$ then $n\in F_6$ (by Lemma Lemma (Square-factor and two-factor identities)$3$ with $t=3$ and $(x_1,x_2,x_3)=(n,a,b)$).
• (Their Theorem 3) For almost all primes $p$, the number $13p$ does not lie in $F_5$.

Together with the "almost all $pq\notin F_4$" statement, this yields a semiprime lower bound for $D_6$.

7. What this does (and does not) say about the original question

Collecting the proven bounds:

• $D_3(n)$ satisfies $c\sqrt{n}\le D_3(n)=o(n)$, and in fact one has the sharper upper bound $D_3(n)=O\left(n\log_3 n/(\log n\log_2 n)\right)$.
• $D_4(n)\gg n$ (indeed, $D_4(n)\ge (1-6/\pi^2)n-o(n)$).
• $D_5(n)\gg n/\log n$ and $D_6(n)\gg n/\log n$.

The question "is $D_6(n)\gg n$?" remains open: Proposition prop:D6-lower only gives $\gg n/\log n$, and no mechanism above forces a positive proportion of integers to avoid $F_5$.

VERIFICATION

All identities reduce to Lemma Lemma (Square-factor and two-factor identities), whose proof is just $(x-1)!=x!/x$. The only nontrivial inputs are the cited literature facts from Erdős--Graham $1976$ and Dujella--Najman--Saradha--Shorey $2014$; the deductions of Propositions prop:D5-lower and prop:D6-lower from those facts are straightforward.

FINAL

LABEL: UNRESOLVED.
SUB-LABEL: N/A.
We obtained unconditional lower bounds $D_4(n)\gg n$,$D_5(n)\gg n/\log n$,$D_6(n)\gg n/\log n$, and the bracket $c\sqrt{n}\le D_3(n)\le n\log_3 n/(\log n\log_2 n)$, but the precise order of growth (e.g. whether $D_6(n)\gg n$) is not resolved.

COMPLETION ESTIMATE

To reach a full solution one would need, for each $k\in\{3,4,5,6\}$, matching upper and lower bounds (ideally asymptotics) for $D_k(n)$. The main missing ingredient is structural control of how often a squarefree integer lies in $F_4$ or $F_5$ (especially among semiprimes), beyond the current "almost all $pq\notin F_4$" type statements.