Erdős Problem #796

Erdős Problem 796 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/796

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/796.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/796.tex.

FORMAL RESTATEMENT

Fix $k\ge 2$. Let $g_k(n)$ be the largest possible size of a set $A\subset\{1,2,\dots,n\}$ such that every integer $m$ has fewer than $k$ representations \[ m=a_1a_2 \] with $a_1<a_2$ and $a_1,a_2\in A$. The problem asks for the second order term of $g_k(n)$, in particular for $k=3$.

QUICK LITERATURE/CONTEXT CHECK

From the problem statement: Erdős determined the main term: if $r$ is defined by $2^{r-1}<k\le 2^r$, then \[ g_k(n) \sim \frac{(\log\log n)^{r-1}}{(r-1)!\,\log n}\,n. \] It is asked whether \[g_k(n)=\frac{(\log\log n)^{r-1}}{(r-1)!\,\log n}\,n + O\left(\frac{n}{\log n}\right) \] and, specifically for $k=3$ (so $r=2$), whether $g_3(n)=\frac{\log\log n}{\log n}n + C\frac{n}{\log n}+o\left(\frac{n}{\log n}\right)$ for a constant $C$.

Below I give an explicit $k=3$ construction with a complete verification of the "$<3$ representations" condition, and I compute exact $g_3(n)$ for $n\le 20$.

ATTACK PLAN

1) Provide a concrete family of sets $A$ where each element has a distinguished large prime factor $>\sqrt n$; show this forces at most two product representations.

2) Express the size of this construction in terms of prime-counting functions (no asymptotics claimed beyond what is in the statement).

3) Reality check: brute-force $g_3(n)$ for small $n$.

WORK

Lemma 796.1 (A $k=3$-valid construction using a unique large prime factor). Fix $n\ge 2$. Let \[ Q:=\{q\le n: q\text{ prime and }q>\sqrt n\}. \] Define \[ A:=\{pq: q\in Q,\ p\text{ prime},\ p<q,\ pq\le n\} \subset\{1,\dots,n\}. \] Then every integer $m$ has at most $2$ representations $m=a_1a_2$ with $a_1<a_2$ and $a_1,a_2\in A$. In particular $A$ is feasible for $g_3(n)$.

Proof. Each $a\in A$ has a prime factor $q>\sqrt n$ and, because $a\le n$, this factor is unique: if $q'\ne q$ were another prime $>\sqrt n$ dividing $a$, then $qq'>n$ would divide $a$, impossible. So every $a\in A$ can be written uniquely as $a=p(a)\,q(a)$ where $q(a)\in Q$ is its unique prime factor $>\sqrt n$ and $p(a)<\sqrt n$ is the remaining prime factor.

Now fix an integer $m$ and suppose we have a representation \[ m=a_1a_2 \] with distinct $a_1,a_2\in A$. Write $a_i=p_i q_i$ with $q_i>\sqrt n$ prime and $p_i$ prime $<\sqrt n$. Then \[ m = (p_1q_1)(p_2q_2) = (p_1p_2)(q_1q_2). \] In the prime factorization of $m$, the primes $>\sqrt n$ appearing are exactly $q_1$ and $q_2$ (counted with multiplicity; if $q_1=q_2$ then it appears twice). Therefore, in any other representation $m=b_1b_2$ with $b_j\in A$, the multiset $\{q(b_1),q(b_2)\}$ must equal $\{q_1,q_2\}$. There are only two assignments of these large primes to the two factors: either \[(q(b_1),q(b_2))=(q_1,q_2)\quad\text{or}\quad(q(b_1),q(b_2))=(q_2,q_1). \] Once this assignment is fixed, the remaining prime factors of $m$ below $\sqrt n$ must match as well. Since $p_1,p_2$ are primes, the only ways to split $p_1p_2$ into a product of two primes are $(p_1,p_2)$ or $(p_2,p_1)$. Thus, up to swapping the two factors, there is at most one representation when $q_1=q_2$ or $p_1=p_2$, and at most two representations when $p_1\ne p_2$ and $q_1\ne q_2$ (corresponding exactly to swapping the large primes). Counting only representations with $a_1<a_2$ removes the double-counting from swapping the two factors. Hence the number of such representations is at most $2$ for every $m$. $\square$

Lemma 796.2 (Size formula for the construction). With $A$ as in Lemma 796.1, \[ |A| = \sum_{\substack{q\in Q}} \pi\!\left(\left\lfloor \frac{n}{q}\right\rfloor\right), \] where $\pi(x)$ is the number of primes $\le x$.

Proof. Fix $q\in Q$. The elements of $A$ with distinguished large prime factor $q$ are exactly $pq$ with $p$ prime and $p\le n/q$. (The condition $p<q$ is automatic because $q>\sqrt n$ implies $n/q<\sqrt n<q$.) There are exactly $\pi(\lfloor n/q\rfloor)$ such primes $p$. Summing over all $q\in Q$ counts each element of $A$ exactly once by uniqueness of the factor $q$. $\square$

Fast reality check (exact computation of $g_3(n)$ for $n\le 20$). I brute-forced $g_3(n)$ exactly by checking all subsets $A\subset\{1,\dots,n\}$ for $n\le 20$. The exact values found are:

(For example, for $n=12$ one optimal set has size $11$; including all of $\{1,\dots,12\}$ fails because $12=1\cdot 12=2\cdot 6=3\cdot 4$ gives three representations.)

VERIFICATION

-- Lemma 796.1 hinges on the uniqueness of a prime factor $>\sqrt n$ for elements $\le n$. This uniqueness makes the "large prime" factors in any product representation identifiable from $m$ itself.

-- Lemma 796.2 is an exact counting identity (no asymptotics used).

-- The brute-force values for $g_3(n)$ confirm the basic obstruction already at $n=12$.

FINAL

UNRESOLVED

(i) Strongest proved partial result here: The explicit set $A$ from Lemma 796.1 is feasible for $g_3(n)$ and has size \[|A|=\sum_{\sqrt n<q\le n\atop q\ \mathrm{prime}} \pi(\lfloor n/q\rfloor). \] Moreover, exact values of $g_3(n)$ for $n\le 20$ are listed above.

(ii) First gap (crisp): Prove (or disprove) that for $k=3$ there exists a constant $C$ such that \[ g_3(n)=\frac{\log\log n}{\log n}n + C\frac{n}{\log n}+o\left(\frac{n}{\log n}\right). \] Even establishing an $O(n/\log n)$ error term without identifying $C$ would be a major step.

(iii) Top 3 next moves:

1. Analyze the construction in Lemma 796.1 asymptotically by estimating the sum $\sum_{q>\sqrt n} \pi(n/q)$ more precisely (and compare it to $\frac{\log\log n}{\log n}n$) to see whether it captures the conjectured second-order constant.
2. For computation: use integer programming / backtracking to compute $g_3(n)$ for larger $n$ (say up to $n=60$ or $100$) and fit the data to $\frac{\log\log n}{\log n}n + C\frac{n}{\log n}$ to guess $C$.
3. Structural: attempt a stability theorem: show that any near-extremal $A$ must consist mainly of integers with a distinguished "large prime" factor (or, more generally, a product of primes from disjoint blocks), reflecting the $2^r$ threshold in the main-term theorem.

(iv) Minimal counterexample structure to watch for: If the $O(n/\log n)$ conjecture is false for $k=3$, a minimal obstruction would be a family of sets $A$ of near-maximal size whose elements have many small prime factors arranged so that products admit unusually many near-collisions without producing three exact coincidences. Such a configuration would have to avoid the "distinguished large prime" structure that makes representation counts rigid.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT

Fix $k\ge 2$. Let $g_k(n)$ be the largest possible size of a set $A\subset\{1,2,\dots,n\}$ such that every integer $m$ has fewer than $k$ representations \[ m=a_1a_2 \] with $a_1<a_2$ and $a_1,a_2\in A$. The problem asks for the second order term of $g_k(n)$, in particular for $k=3$.

QUICK LITERATURE/CONTEXT CHECK

From the problem statement: Erdős determined the main term: if $r$ is defined by $2^{r-1}<k\le 2^r$, then \[ g_k(n) \sim \frac{(\log\log n)^{r-1}}{(r-1)!\,\log n}\,n. \] It is asked whether \[g_k(n)=\frac{(\log\log n)^{r-1}}{(r-1)!\,\log n}\,n + O\left(\frac{n}{\log n}\right) \] and, specifically for $k=3$ (so $r=2$), whether $g_3(n)=\frac{\log\log n}{\log n}n + C\frac{n}{\log n}+o\left(\frac{n}{\log n}\right)$ for a constant $C$.

Below I give an explicit $k=3$ construction with a complete verification of the "$<3$ representations" condition, and I compute exact $g_3(n)$ for $n\le 20$.

ATTACK PLAN

1) Provide a concrete family of sets $A$ where each element has a distinguished large prime factor $>\sqrt n$; show this forces at most two product representations.

2) Express the size of this construction in terms of prime-counting functions (no asymptotics claimed beyond what is in the statement).

3) Reality check: brute-force $g_3(n)$ for small $n$.

WORK

Lemma 796.1 (A $k=3$-valid construction using a unique large prime factor). Fix $n\ge 2$. Let \[ Q:=\{q\le n: q\text{ prime and }q>\sqrt n\}. \] Define \[ A:=\{pq: q\in Q,\ p\text{ prime},\ p<q,\ pq\le n\} \subset\{1,\dots,n\}. \] Then every integer $m$ has at most $2$ representations $m=a_1a_2$ with $a_1<a_2$ and $a_1,a_2\in A$. In particular $A$ is feasible for $g_3(n)$.

Proof. Each $a\in A$ has a prime factor $q>\sqrt n$ and, because $a\le n$, this factor is unique: if $q'\ne q$ were another prime $>\sqrt n$ dividing $a$, then $qq'>n$ would divide $a$, impossible. So every $a\in A$ can be written uniquely as $a=p(a)\,q(a)$ where $q(a)\in Q$ is its unique prime factor $>\sqrt n$ and $p(a)<\sqrt n$ is the remaining prime factor.

Now fix an integer $m$ and suppose we have a representation \[ m=a_1a_2 \] with distinct $a_1,a_2\in A$. Write $a_i=p_i q_i$ with $q_i>\sqrt n$ prime and $p_i$ prime $<\sqrt n$. Then \[ m = (p_1q_1)(p_2q_2) = (p_1p_2)(q_1q_2). \] In the prime factorization of $m$, the primes $>\sqrt n$ appearing are exactly $q_1$ and $q_2$ (counted with multiplicity; if $q_1=q_2$ then it appears twice). Therefore, in any other representation $m=b_1b_2$ with $b_j\in A$, the multiset $\{q(b_1),q(b_2)\}$ must equal $\{q_1,q_2\}$. There are only two assignments of these large primes to the two factors: either \[(q(b_1),q(b_2))=(q_1,q_2)\quad\text{or}\quad(q(b_1),q(b_2))=(q_2,q_1). \] Once this assignment is fixed, the remaining prime factors of $m$ below $\sqrt n$ must match as well. Since $p_1,p_2$ are primes, the only ways to split $p_1p_2$ into a product of two primes are $(p_1,p_2)$ or $(p_2,p_1)$. Thus, up to swapping the two factors, there is at most one representation when $q_1=q_2$ or $p_1=p_2$, and at most two representations when $p_1\ne p_2$ and $q_1\ne q_2$ (corresponding exactly to swapping the large primes). Counting only representations with $a_1<a_2$ removes the double-counting from swapping the two factors. Hence the number of such representations is at most $2$ for every $m$. $\square$

Lemma 796.2 (Size formula for the construction). With $A$ as in Lemma 796.1, \[ |A| = \sum_{\substack{q\in Q}} \pi\!\left(\left\lfloor \frac{n}{q}\right\rfloor\right), \] where $\pi(x)$ is the number of primes $\le x$.

Proof. Fix $q\in Q$. The elements of $A$ with distinguished large prime factor $q$ are exactly $pq$ with $p$ prime and $p\le n/q$. (The condition $p<q$ is automatic because $q>\sqrt n$ implies $n/q<\sqrt n<q$.) There are exactly $\pi(\lfloor n/q\rfloor)$ such primes $p$. Summing over all $q\in Q$ counts each element of $A$ exactly once by uniqueness of the factor $q$. $\square$

Fast reality check (exact computation of $g_3(n)$ for $n\le 20$). I brute-forced $g_3(n)$ exactly by checking all subsets $A\subset\{1,\dots,n\}$ for $n\le 20$. The exact values found are:

(For example, for $n=12$ one optimal set has size $11$; including all of $\{1,\dots,12\}$ fails because $12=1\cdot 12=2\cdot 6=3\cdot 4$ gives three representations.)

VERIFICATION

-- Lemma 796.1 hinges on the uniqueness of a prime factor $>\sqrt n$ for elements $\le n$. This uniqueness makes the "large prime" factors in any product representation identifiable from $m$ itself.

-- Lemma 796.2 is an exact counting identity (no asymptotics used).

-- The brute-force values for $g_3(n)$ confirm the basic obstruction already at $n=12$.

FINAL

UNRESOLVED

(i) Strongest proved partial result here: The explicit set $A$ from Lemma 796.1 is feasible for $g_3(n)$ and has size \[|A|=\sum_{\sqrt n<q\le n\atop q\ \mathrm{prime}} \pi(\lfloor n/q\rfloor). \] Moreover, exact values of $g_3(n)$ for $n\le 20$ are listed above.

(ii) First gap (crisp): Prove (or disprove) that for $k=3$ there exists a constant $C$ such that \[ g_3(n)=\frac{\log\log n}{\log n}n + C\frac{n}{\log n}+o\left(\frac{n}{\log n}\right). \] Even establishing an $O(n/\log n)$ error term without identifying $C$ would be a major step.

(iii) Top 3 next moves:

1. Analyze the construction in Lemma 796.1 asymptotically by estimating the sum $\sum_{q>\sqrt n} \pi(n/q)$ more precisely (and compare it to $\frac{\log\log n}{\log n}n$) to see whether it captures the conjectured second-order constant.
2. For computation: use integer programming / backtracking to compute $g_3(n)$ for larger $n$ (say up to $n=60$ or $100$) and fit the data to $\frac{\log\log n}{\log n}n + C\frac{n}{\log n}$ to guess $C$.
3. Structural: attempt a stability theorem: show that any near-extremal $A$ must consist mainly of integers with a distinguished "large prime" factor (or, more generally, a product of primes from disjoint blocks), reflecting the $2^r$ threshold in the main-term theorem.

(iv) Minimal counterexample structure to watch for: If the $O(n/\log n)$ conjecture is false for $k=3$, a minimal obstruction would be a family of sets $A$ of near-maximal size whose elements have many small prime factors arranged so that products admit unusually many near-collisions without producing three exact coincidences. Such a configuration would have to avoid the "distinguished large prime" structure that makes representation counts rigid.