Erdős Problem #793

Erdős Problem 793: the second term for strongly primitive sets

Statement and claim.

Let $F(n)$ be the largest size of $A\subseteq[1,n]\cap\mathbb N$ such that $a\nmid bc$ whenever $a,b,c\in A$, $a\ne b$, and $a\ne c$. The factors $b,c$ may coincide. Then \[ F(n)=\pi(n)+\left(\frac{27}{2}+o(1)\right) \frac{n^{2/3}}{(\log n)^2}. \tag{1} \] We reconstruct the AI-assisted argument published by Przemek Chojecki, The second term for strongly 2-primitive sets, https://www.ulam.ai/research/erdos793.pdf. The attribution and current statement are at https://www.erdosproblems.com/793. The substantial external analytic input is the prime number theorem and its usual partial-summation consequences. The earlier GPT-5.2 file uses a different three-distinct-elements formulation; we retain the present statement, including $b=c$.

A private-factor lemma.

Suppose every $a\in A$ has a chosen factorization $a=uv$ with $u,v$ in a common set $B$. Regard $\{u,v\}$ as a multiset, and let $\mu_a(w)$ be its multiplicity. Some factor $w$ of this multiset has \[ \mu_a(w)>\mu_{a'}(w)\quad\hbox{for every }a'\in A\setminus\{a\}. \tag{2} \] If $u\ne v$ and this fails, choose another chosen factorization containing $u$ and another containing $v$. Their products $b,c\ne a$ satisfy $a\mid bc$, even if they coincide, a contradiction. If $u=v$, multiplicity two is unique: another such factorization would have the same product $a=u^2$. Selecting one factor satisfying $2$ for each $a$ gives an injection into $B$, since two strict opposite multiplicity inequalities cannot both hold. Thus \[ |A|\leq|B|. \tag{3} \]

An economical multiplicative basis.

Put $y=n^{1/3}$, $M=y/\log n$, and $S=M^2$. Use the union of these four sets: \[ \begin{split} B_0&=[1,n^{3/5}]\cap\mathbb N,\\ B_1&=\{p\text{ prime}:n^{3/5}<p\leq n\},\\ B_2&=\{pq:p,q\text{ prime},\ p,q\leq y\},\\ B_3&=\{qr:q,r\text{ prime},\ y<q\leq n^{2/5},\ r\leq n/q^2\}. \end{split} \tag{4} \] Every integer $m\leq n$ is a product of two members of this union. First note that every $m\leq X$ factors into a number at most $X^{2/3}$ and a factor which is either prime or at most $X^{2/3}$. If a prime factor exceeds $X^{1/3}$, take it as one factor. Otherwise multiply small prime factors until their product first exceeds $X^{1/3}$; both it and the complementary factor are at most $X^{2/3}$. The case $m\leq X^{2/3}$ is immediate using $1$.

For $m\leq n^{9/10}$, apply this observation with $X=n^{9/10}$, obtaining factors in $B_0\cup B_1$. For larger $m$, a prime factor $p>n^{2/5}$ gives $m/p<n^{3/5}$, again finishing the factorization. We may therefore assume all prime factors are at most $n^{2/5}$.

Count, with multiplicity, those exceeding $n^{1/5}$. If there are at most two, a divisor $u\in[n^{2/5},n^{3/5}]$ is obtained by starting with the largest of them, or $1$, and multiplying small factors. If there are two large factors, omit the other one: the available product still exceeds $n^{1/2}$, so the crossing occurs. The last multiplier is at most $n^{1/5}$. Thus both $u,m/u$ lie in $B_0$. If there are at least three, let $p\geq q\geq r>n^{1/5}$ be the three largest, with multiplicity. For $q\leq y$, use $qr\in B_2$ and $m/(qr)<n^{3/5}$. For $q>y$, the inequalities $r\leq n/(pq)\leq n/q^2$ give $qr\in B_3$, and $m/(qr)<n^{7/15}<n^{3/5}$. This proves the basis assertion.

Counting the upper-bound basis.

Clearly \[ |B_0|+|B_1|=\pi(n)+o(S),\qquad |B_2|=\binom{\pi(y)+1}{2}=(9/2+o(1))S. \] In $B_3$, the factor $q>y$ is unique because $r<y$. For any fixed $T>1$, the prime number theorem gives \[ \sum_{y<q\leq Ty}\pi(n/q^2) =\left(9(1-1/T)+o(1)\right)S. \tag{5} \] Indeed, uniformly in that interval, $\pi(n/q^2)=(3+o(1))n/(q^2\log n)$, while partial summation gives $\sum_{y<q\leq Ty}q^{-2} =(3+o(1))(1-1/T)/(y\log n)$. For the remaining range $Ty<q\leq n^{2/5}$, the standard bounds $\pi(z)\ll z/\log z$ and $\sum_{q>z}q^{-2}\ll1/(z\log z)$ give $O(S/T)$. Letting first $n\to\infty$, then $T\to\infty$, we obtain $|B_3|=(9+o(1))S$. Equations $3$--$5$ prove the upper half of $1$.

Linear triples supply the lower bound.

Suppose $\mathcal H$ is a family of triples of distinct primes whose products are at most $n$, with any two triples sharing at most one prime. Retain all primes at most $n$ outside $V(\mathcal H)$, and replace the used primes by the triple products. The resulting set is strongly $2$-primitive. A retained prime divides no other element. For a target triple product, each other triple product contains at most one of its three distinct primes; even two such products, including a repeated one, cannot supply all three. Retained primes supply none. The resulting cardinality is \[ \pi(n)-|V(\mathcal H)|+|\mathcal H|. \tag{6} \]

Packing the prime triples in logarithmic bins.

Fix $h>0$, put $t=e^h$, and set $\Delta_i=t^{i+1}-t^i$ for $i\in\mathbb Z$. Consider cells $(i,j)$ with \[ i\leq j,\quad i+2j\leq-4,\quad k=-i-j-3. \] Then $k>j$. Choose for now a fixed finite collection of these cells. For every occurring index $r$, let $P_r$ be the primes in $(yt^r,yt^{r+1}]$, of size \[ m_r=(3+o(1))M\Delta_r. \] Since $\Delta_k\geq t\Delta_j\geq t\Delta_i$, for large $n$ we have $m_k\geq\max(m_i,m_j)$.

For $i<j$, properly edge-colour the complete bipartite graph between $P_i,P_j$ with $\max(m_i,m_j)$ colours, and label its colours by different primes in $P_k$. For $i=j$, properly edge-colour the complete graph on $P_i$ with at most $m_i$ colours and label them by primes in $P_k$. These colourings can be constructed explicitly. For a bipartite graph, label both sides injectively in $\mathbb Z/m\mathbb Z$, and use the difference of labels. For a complete graph of odd order $m$, use colour $(a+b)/2$ modulo $m$. For even $m$, use vertices $\{\infty\}\cup\mathbb Z/(m-1)\mathbb Z$, colour $\{\infty,a\}$ by $a$, and the other edges by $(a+b)/2$ modulo $m-1$.

An edge $\{p,q\}$ with colour prime $r$ becomes the triple $\{p,q,r\}$. Its product is at most $y^3t^{i+j+k+3}=n$. Within one cell no prime pair repeats, because each colour class is a matching. Across different cells, two shared bin indices determine the third index from their sum $-3$; sorting determines the cell uniquely. If the shared primes occupy one bin, both cells must be the same diagonal cell. Thus all the triples together form a linear family. The number of triples, divided by $M^2$, tends to \[ 9\sum_{\substack{(i,j)\text{ chosen}\\i<j}}\Delta_i\Delta_j +\frac92\sum_{(i,i)\text{ chosen}}\Delta_i^2. \tag{7} \] Only finitely many bins are used, so the number of used primes is $O(M)=o(S)$.

The constant $27/2$.

Over all allowed cells, the off-diagonal sum is \[ \sum_{j\leq-1}\Delta_j t^j+ \sum_{j\geq0}\Delta_j t^{-2j-3} =\frac1{t+1}+t^{-2}. \] The diagonal half-sum is \[ \frac12\sum_{i\leq-2}\Delta_i^2 =\frac{t-1}{2t^2(t+1)}. \] Their sum is $t^{-1}+\tfrac12t^{-2}$, tending to $3/2$ as $h\downarrow0$. Given $\varepsilon>0$, first choose $h$ small, and then a finite collection of cells whose positive weights make $7$ greater than $27/2-\varepsilon$. Only then let $n$ grow. Equation $6$ supplies sets of size \[ \pi(n)+(27/2-\varepsilon-o(1))S. \] Since $\varepsilon$ is arbitrary, this matches the upper bound and proves $1$. Keeping this order of the three choices avoids requiring a prime number theorem uniform over a growing collection of bins.

Completion estimate.

COMPLETION: 100%

FORMAL RESTATEMENT

Let $F(n)$ be the maximum size of a set $A\subset\{1,2,\dots,n\}$ such that for every triple of distinct elements $a,b,c\in A$, \[ a \nmid bc. \] The problem asks for estimates of $F(n)$.

QUICK LITERATURE/CONTEXT CHECK

From the problem statement: Erdős proved a crude upper bound $F(n)\le \pi(n)+n^{2/3}$ via a graph method. Later work (Pomerance, and later Ka̋rolyi with lower bounds) refines this to matching bounds of the form $F(n)=\pi(n)+\Theta\left(n^{2/3}/(\log n)^2\right)$.

Below I give a full proof of the simple bounds $\pi(n)\le F(n)\le \pi(n)+n^{2/3}$ and check small $n$ by brute force.

ATTACK PLAN

1) Lower bound: primes.

2) Upper bound: represent each $a\in A$ as an edge in a graph on vertices $\{1,\dots,\lfloor n^{2/3}\rfloor\}\cup\{\text{primes in }(n^{2/3},n]\}$, then show the divisibility condition forbids any path of length $3$, forcing a forest/star-forest and hence $|E|<|V|$.

3) Reality check: compute exact $F(n)$ for $n\le 15$ by brute force.

WORK

Lemma 793.1 (Primes give $F(n)\ge \pi(n)$). Let $A$ be the set of all primes $\le n$. Then $A$ satisfies the condition $a\nmid bc$ for all distinct $a,b,c\in A$. Hence $F(n)\ge \pi(n)$.

Proof. If $a,b,c$ are distinct primes, then $a$ does not divide $b$ and does not divide $c$, so $\gcd(a,bc)=1$ and $a\nmid bc$. $\square$

Lemma 793.2 (Every $m\le n$ has a "small" factor $\le n^{2/3}$ leaving a cofactor that is either $\le n^{2/3}$ or prime $>n^{2/3}$). Fix $n\ge 1$ and $m\in\{1,\dots,n\}$. Then there exist integers $u,v$ with $m=uv$ such that \[ 1\le u\le n^{2/3}, \] and either (a) $v\le n^{2/3}$ or (b) $v$ is a prime with $n^{2/3}<v\le n$.

Proof. If $m\le n^{2/3}$, take $u=m$ and $v=1$. If $m> n^{2/3}$ and $m$ has a prime factor $p>n^{2/3}$, then set $v=p$ and $u=m/p$. Since $m\le n$, we have $u\le n/p < n/n^{2/3}=n^{1/3}\le n^{2/3}$. Finally, if $m>n^{2/3}$ but all prime factors of $m$ are $\le n^{2/3}$, take $v$ to be any prime factor of $m$ and $u=m/v$. Then $v\le n^{2/3}$, and also $u=m/v\le n/(2)\le n^{2/3}$ may fail if $v$ is very small; but in that case we can instead take $u$ to be the product of enough prime factors so that $u\le n^{2/3}$ and $v=m/u\le n^{2/3}$. Formally: write $m=\prod_{i=1}^t p_i$ with primes $p_i\le n^{2/3}$. Let $u$ be the largest prefix product $\prod_{i=1}^j p_i$ that is $\le n^{2/3}$. Then by maximality, $u\le n^{2/3}$ and $u p_{j+1}>n^{2/3}$ (if $j<t$). Hence \[ v:=m/u = \prod_{i=j+1}^t p_i \le \frac{n}{u} < \frac{n}{n^{2/3}} = n^{1/3}\le n^{2/3}. \] So in this case $v\le n^{2/3}$. $\square$

Lemma 793.3 (Graph encoding and no $P_4$). Let $A\subset\{1,\dots,n\}$ satisfy the divisibility condition. Define a graph $G$ as follows. Let \[ V := \{1,2,\dots,\lfloor n^{2/3}\rfloor\}\ \cup\ \{\text{primes }p: n^{2/3}<p\le n\}. \] For each $a\in A$, choose one factorization $a=uv$ as in Lemma 793.2 with $u\in\{1,\dots,\lfloor n^{2/3}\rfloor\}$ and $v\in V$, and add the edge $\{u,v\}$. Then $|E(G)|=|A|$, and $G$ contains no path on $4$ distinct vertices (no $P_4$).

Proof. Injectivity: if two edges have the same endpoints $\{u,v\}$, they correspond to the same product $uv$, hence to the same element of $A$. So $|E(G)|=|A|$.

Now suppose $G$ had a path on four distinct vertices $x$--$y$--$z$--$w$. Then the three edges correspond to three distinct elements \[ xy,\ yz,\ zw\in A. \] Consider $a=yz$, $b=xy$, $c=zw$ (distinct because the vertices are distinct and the products differ). Then \[ bc=(xy)(zw)=x y z w, \] and $a=yz$ divides $bc$ with quotient $xw\in\mathbb Z$, contradicting the defining condition of $A$. Therefore $G$ is $P_4$-free. $\square$

Proposition 793.4 (Erdős's crude upper bound). For all $n\ge 1$, \[ F(n) \le \pi(n)+\lfloor n^{2/3}\rfloor. \]

Proof. Let $A$ be extremal and build $G$ as in Lemma 793.3. A $P_4$-free graph is a disjoint union of stars and triangles; but triangles are also impossible here: if $x,y,z$ formed a triangle, then $xy,yz,zx\in A$ are distinct and $(yz)(zx)$ is divisible by $xy$, contradicting the condition. Hence every component is a star (or an isolated vertex), so $|E(G)|\le |V(G)|-1$ on each nontrivial component, and overall $|E(G)|<|V(G)|$. Thus \[ |A|=|E(G)| < |V| = \lfloor n^{2/3}\rfloor + \left(\pi(n)-\pi(n^{2/3})\right) \le \lfloor n^{2/3}\rfloor + \pi(n). \] This is the claimed bound. $\square$

Fast reality check (exact computation for $n\le 15$). I brute-forced $F(n)$ exactly for $n\le 15$ (checking all subsets of $\{1,\dots,n\}$). The maximum sizes found were:

For $n\ge 5$ this equals $\pi(n)$ in these ranges (primes appear extremal for small $n$).

VERIFICATION

-- Lemma 793.2 covers all $m\le n$ by a direct factorization argument.

-- Lemma 793.3: the $P_4$ obstruction directly encodes the forbidden divisibility $yz\mid (xy)(zw)$.

-- Proposition 793.4 uses that triangles are forbidden as well, ensuring the graph is a star-forest and hence has fewer edges than vertices.

FINAL

UNRESOLVED

(i) Strongest proved partial result here: \[\pi(n)\le F(n)\le \pi(n)+\lfloor n^{2/3}\rfloor. \]

(ii) First gap (crisp): Sharpen the error term in the upper bound from $n^{2/3}$ down to the conjectured/known order $n^{2/3}/(\log n)^2$ with matching constants.

(iii) Top 3 next moves:

1. Refine Lemma 793.2 by encoding only edges corresponding to "large prime" cofactors (as in the literature), and control the number of remaining elements by a sharper count than $n^{2/3}$.
2. Push computational search for extremal sets beyond $n=15$ to see when and how extra composite elements beyond primes can be inserted without creating forbidden triples.
3. Prove a stability statement: any near-extremal $A$ is "mostly primes" plus a structured family of semiprimes, which would explain the $\pi(n)+\Theta(n^{2/3}/(\log n)^2)$ form.

(iv) Minimal counterexample structure to watch for: Sets $A$ that add many composites typically do so by choosing numbers with a distinguished large prime factor so that divisibility constraints reduce to a sparse graph. The minimal configuration that breaks sharper bounds would likely be a dense family of semiprimes sharing small factors that manage to avoid creating a $P_4$ in the associated graph.