A near-density-1 set whose equal products of distinct elements have equally many factors (Erdős #786)
Statement
Fix $\epsilon>0$. Call $A\subseteq\mathbb{N}$ product-untangled if a product equation $a_1\cdots a_r=b_1\cdots b_s$ with all $a_i,b_j\in A$ can hold only when $r=s$. Erdős asked: (1) is there a product-untangled set $A\subseteq\mathbb{N}$ of lower density $>1-\epsilon$; and (2) is there, for every $N$, a product-untangled $A\subseteq\{1,\ldots,N\}$ of size $\ge(1-o(1))N$? The intended reading (per Erdős's later formulation) requires the factors $a_1,\ldots,a_r$ (and $b_1,\ldots,b_s$) to be distinct; under this distinct-element reading both questions are open.
Acceptance. FULLY RESOLVES (distinct-element version): a complete proof (Lean/Coq preferred, else full written). For (1): a proof that a product-untangled distinct-element $A$ can have lower density $>1-\epsilon$ for every $\epsilon>0$ (exhibiting the construction), or a proof that some fixed $c>0$ caps the density at $1-c$. For (2): a proof deciding whether $\{1,\ldots,N\}$ contains product-untangled sets of size $(1-o(1))N$, i.e. whether the maximal size is $(1-o(1))N$ or $\le(1-c)N$ for a fixed $c>0$. ADVANCES: improve, with proof, the best density/size bounds for the distinct-element version beyond those stated in the background (the density-$1/e$ Selfridge lower bound, or any proven upper bound below $1$); a construction beating density $1/e$; or a reproducible computation of the maximal product-untangled subset size of $\{1,\ldots,N\}$ over a certified range (extending OEIS A143301) with the optimisation code and an empirical density estimate. Deliver the proof, the improved construction/bound with proof, or the search code plus certified extremal sizes.
Background
Asked repeatedly by Erdős [Er65; Er69, p.81; Er73, p.132; Er80, p.114]; listed as open on erdosproblems.com/786 (fetched 2026-07-21, status 'open'). Constructions: the integers $\equiv 2\ (\mathrm{mod}\ 4)$ give density $1/4$; Selfridge reached density $1/e-\epsilon$ (integers divisible by exactly one of consecutive primes $p_1<\cdots<p_k$ with $\sum 1/p_i<1<\sum_{i\le k+1}1/p_i$). For (2), integers with a prime factor $>N^{1/2}$ give size $\ge(\log 2)N$; Tao improved this to $\approx 0.8285N$ (integers with exactly one prime factor $>N^{1/(1+\sqrt e)}$). CAUTION for the vetter: under the reading where repetitions among the $a_i,b_j$ ARE allowed (a stronger property), the questions are essentially settled — Erdős–Ruzsa–Sárközy [ERS73] gives $\lvert A\rvert\le(1-c)N$, Tao (via Granville–Soundararajan [GrSo01]) obtained the best-possible $\lvert A\rvert\le(1-c+o(1))N$ with $c\approx 0.1715$, and Theorem 2 of [ERS73] forces density $\le 1/2$, answering (1) negatively. The OPEN problem is the distinct-element (weaker) version; Erdős [Er80] reported Ruzsa had claimed both answers are 'no' there with upper density $<1/e$, but this appears unpublished and possibly conflated with the repetitions-allowed results. Related OEIS A143301; Erdős #421 and #795 (erdosproblems.com/421, erdosproblems.com/795). No prize. Attacker's tool: computer search for the densest product-untangled subsets of $\{1,\ldots,N\}$ under the distinct-element rule (an extremal-set / integer program over the multiplicative-collision structure), extending A143301 and the empirical maximal density, paired with the multiplicative-function machinery of [ERS73]/[GrSo01] adapted to distinct factors.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #786 (T. F. Bloom) | website |
| REF-02 | OEIS A143301 — related multiplicative-independence counting sequence | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.