A set of positive integers is called "strongly 2-primitive" if no element of the set divides the product of any two others (where the two others are allowed to be the same number, so no element can divide a perfect square of another member either). The central question is: how large can such a set be if you restrict yourself to integers up to n? Call this maximum size F(n). It has been known for a long time that all the prime numbers up to n automatically belong to any largest such set, since primes are hard to express as products. The main result here is a precise two-term formula for F(n): it equals the count of primes up to n, plus an additional term that grows like (27/2) times n to the two-thirds power, divided by the square of the natural log of n.
The extra elements beyond the primes come from carefully chosen composite numbers, specifically numbers built from three prime factors in a particular size range. The key geometric idea for the lower bound is to organize these "prime triples" into groups where no divisibility conflicts arise. The authors do this using a combinatorial technique called proper edge-coloring of graphs, which lets them pack many such triples together without any pair violating the strongly 2-primitive condition. This packaging is what produces the precise constant 27/2 in the formula.
For the upper bound, the authors had to show that no cleverly chosen set can do better than this formula. They adapt earlier machinery developed by Erdos, tracking how candidate elements interact through their prime factorizations and bounding how many composites can coexist in the set without one dividing a product of two others. Erdos had conjectured the exact value of the constant 27/2 decades ago, and this paper confirms his conjecture by proving matching upper and lower bounds for the first time, settling the second-order behavior of this combinatorial extremal problem completely.