we-solve (beta)

Math-786-A2 · revision r1 · on Math-786

gpt pro 5.2 attempt on Math-786

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Problem 374. Growth of $D_k$ for products of factorials that are squares
  2. FORMAL RESTATEMENT
  3. QUICK LITERATURE / CONTEXT CHECK
  4. ATTACK PLAN
  5. WORK
  6. 1. Two algebraic identities that power many inclusions
  7. 2. A uniform $\Omega(\sqrt{n})$ lower bound for $D_3(n)$
  8. 3. Known upper bounds for $D_3(n)$
  9. 4. $D_4(n)$ has linear growth (positive density)
  10. 5. A $\gg n/\log n$ lower bound for $D_5(n)$
  11. 6. A $\gg n/\log n$ lower bound for $D_6(n)$
  12. 7. What this does (and does not) say about the original question
  13. VERIFICATION
  14. FINAL
  15. COMPLETION ESTIMATE

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

Lemma (Square-factor and two-factor identities): Let $x,y\in\mathbb{N}$.
  1. If $x\ge 1$ then \[ x!\,(x-1)!\;=\;\frac{(x!)^2}{x}. \]
  2. If $x,y\ge 1$ then \[ x!\,(x-1)!\,y!\,(y-1)!\;=\;\frac{(x!\,y!)^2}{xy}. \]
  3. More generally, for any $x_1,\dots,x_t\ge 1$, \[ \prod_{i=1}^t \left(x_i!\,(x_i-1)!\right) =\;\frac{\left(\prod_{i=1}^t x_i!\right)^2}{\prod_{i=1}^t x_i}. \]
Proof: $1$ is immediate from $(x-1)!=x!/x$. Multiplying $1$ for $x$ and $y$ yields $2$. Statement $3$ is the same calculation iterated $t$ times. ∎

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)).
Lemma (An explicit infinite family in $D_3$): Fix any integer $b>1$ and let $Q(b!)$ be the squarefree part of $b!$, i.e. write $b!=Q(b!)\,s^2$ with $Q(b!)$ squarefree. For each integer $a>1$, set \[ n\;:=\;a^2\,Q(b!). \] Then $n\in D_3$.
Proof: Let $A:=\{n,\ n-1,\ b\}$. Then $|A|=3$ and $M(A)=n$. Using Lemma Lemma (Square-factor and two-factor identities)$1$, \[ m(A)=n!\,(n-1)!\,b!\;=\;\frac{(n!)^2}{n}\,b! =\;\frac{(n!)^2}{a^2Q(b!)}\,Q(b!)s^2 =\;\left(\frac{n!\,s}{a}\right)^2, \] so $m(A)$ is a perfect square and hence $n\in F_3$.

Also $n$ is not a perfect square because $Q(b!)$ is squarefree and $Q(b!)>1$ for $b>1$, hence $n\notin D_2=F_2$. Therefore $n\in D_3=F_3\setminus F_2$. ∎

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

Corollary (A quantitative lower bound for $D_3(n)$): There is an absolute constant $c>0$ such that for all $n$, \[ D_3(n)\ge c\,\sqrt{n}. \] In particular $D_3$ is infinite.
Proof: From Lemma lem:D3-family with $b=2$, every integer of the form $2a^2$ with $a\ge 2$ lies in $D_3$. The count of such integers $\le n$ is $\lfloor\sqrt{n/2}\rfloor-1\ge c\sqrt{n}$ for a suitable absolute $c$ and all $n$. ∎

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$.
Lemma (Non-squarefree integers lie in $F_4$): If $n=m^2 r$ with $m>1$, then $n\in F_4$.
Proof: Let $A:=\{n,n-1,r,r-1\}$. Then $|A|\le 4$ and $M(A)=n$. By Lemma Lemma (Square-factor and two-factor identities)$2$, \[ m(A)=n!\,(n-1)!\,r!\,(r-1)! =\;\frac{(n!\,r!)^2}{nr}. \] Since $nr=(m^2r)r=(mr)^2$ is a perfect square, the right-hand side is a perfect square. ∎

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)$.

Proposition ($D_4$ has positive density): We have \[ D_4(n)\ge \left(1-\frac{6}{\pi^2}\right)n - o(n) \] and in particular $D_4(n)\gg n$.
Proof: By Lemma lem:non-squarefree-in-F4, every non-squarefree $\le n$ belongs to $F_4$. Among these, the squares belong to $D_2$ and contribute $o(n)$. Also $D_3(n)=o(n)$. Hence all but $o(n)$ of the non-squarefree integers $\le n$ are in $F_4\setminus F_3=D_4$. ∎

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$.

Proposition (Many semiprimes are in $D_5$): Let $S(X):=\{2p\le X: p\text{ prime},\ p>5\}$. Then, as $X\to\infty$, all but $o(|S(X)|)$ elements of $S(X)$ lie in $D_5$. Consequently \[ D_5(X)\ge (1-o(1))\pi(X/2)\ \ \text{and hence}\ \ D_5(X)\gg \frac{X}{\log X}. \]
Proof: Fix $n=2p$ with $p$ an odd prime.

Step 1: $n\in F_5$. Since $2$ is a proper divisor of $n$, Erdős--Graham's Fact 7 implies $n\in F_5$.

Step 2: $n\notin F_3$ for $p>5$. If $n\in F_3$, then $n\in D_3$ (because $n$ is not a square). But Erdős--Graham show that if a number of the form $2P$ with odd prime $P$ lies in $D_3$, then it must be $6$ or $10$. Thus for $p>5$ we have $2p\notin F_3$.

Step 3: for almost all primes $p$, $2p\notin F_4$. Erdős--Graham state that for any fixed prime $q$, almost all numbers of the form $Pq$ (with $P$ prime) do not belong to $F_4$. Applying this with $q=2$ gives that for all but $o(\pi(X))$ primes $p\le X$, the number $2p$ is not in $F_4$.

Now combine: for such primes $p>5$ with $2p\notin F_4$, we have \[ 2p\in F_5\setminus F_4 = D_5. \] Counting these primes gives the claimed bound. ∎

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$.
Proposition (Many semiprimes are in $D_6$): Let $T(X):=\{13p\le X: p\text{ prime},\ p\ne 13\}$. Then, as $X\to\infty$, all but $o(|T(X)|)$ elements of $T(X)$ lie in $D_6$. Consequently \[ D_6(X)\ge (1-o(1))\pi(X/13)\ \ \text{and hence}\ \ D_6(X)\gg \frac{X}{\log X}. \]
Proof: Fix $n=13p$ with $p$ prime and $p\ne 13$.

Step 1: $n\in F_6$. Write $n=ab$ with $a=13$, $b=p$, so $a,b>1$ and $a\ne b$. Erdős--Graham's construction gives $n\in F_6$.

Step 2: $n\notin F_4$ for almost all primes $p$. Apply the Erdős--Graham statement "for any fixed prime $q$, almost all $Pq$ are not in $F_4$" with $q=13$.

Step 3: $n\notin F_5$ for almost all primes $p$. Erdős--Graham's Theorem 3 states that for almost all primes $p$, $13p\notin F_5$.

For primes $p$ satisfying both Step 2 and Step 3, we have $13p\notin F_5$, but $13p\in F_6$, hence $13p\in D_6=F_6\setminus F_5$.

Counting such primes gives the result. ∎

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.