Erdős Problem #768

Problem 768 (Round 2)

1. ROUND-2 OBJECTIVE

Path (C): isolate a genuine quantitative obstruction and strengthen the Round-1 result from mere density $0$ to an explicit subexponential upper bound. Round 1 only proved that \[ \frac{|A\cap[1,x]|}{x}\to 0. \] The exact Erdős asymptotic \[ \frac{|A\cap[1,x]|}{x}=\exp\!\left(-(c+o(1))\sqrt{\log x}\,\log\log x\right) \] remains out of reach, so the most promising Round-2 target is to close the first major gap: obtain a nontrivial upper bound on the natural scale \[ \exp\!\left(-c\sqrt{\log x\,\log\log x}\right). \]

2. Round-1 FOUNDATION USED

I use exactly two Round-1 ingredients.

1. The definition of \[ A=\left\{n\ge 1:\ \forall p\mid n \text{ prime},\ \exists d\mid n,\ d>1,\ d\equiv 1 \pmod p\right\}. \]
2. The Round-1 rough/smooth decomposition idea: if $p=P(n)$ is the largest prime factor of $n\in A$, then there is a divisor of the form $1+ap$ dividing $n$, and this can be counted by summing over $(p,a)$.

I do not reprove the Round-1 density-$0$ theorem; I strengthen it quantitatively.

3. NEW INSIGHT / TOOL (ROUND 2)

The new step is to let the smoothness threshold depend on $x$ and optimize it.

Write $\Psi(x,y)$ for the number of $y$-smooth integers $\le x$. Then the Round-1 argument actually gives, for every $2\le y\le x$, \[ |A\cap[1,x]| \le \Psi(x,y) + x\sum_{\substack{p>y\\ p\ \mathrm{prime}}}\ \sum_{1\le a\le x/p}\frac{1}{p(1+ap)}. \] Using a standard smooth-number estimate in the Canfield--Erdős--Pomerance range, and then optimizing $y$, yields a genuine subexponential decay.

4. ATTACK PLAN (ROUND 2)

The exact Round-1 gap was this: density $0$ is much too weak compared to the problem's conjectural scale. So I now prove the following explicit theorem.

Theorem. Let \[ A(x)=|A\cap[1,x]|. \] Then, as $x\to\infty$, \[ A(x)\le x\exp\!\left(-\left(\frac{1}{\sqrt 2}+o(1)\right)\sqrt{\log x\,\log\log x}\right). \]

This does not settle Erdős's conjectured $\sqrt{\log x}\,\log\log x$ scale, but it is a strict Round-2 advance beyond density $0$.

5. WORK (ROUND 2)

Let \[ L=\log x,\qquad L_2=\log\log x. \]

Step 1: a uniform counting inequality.

Fix $y$ with $2\le y\le x$. Split \[ A\cap[1,x] = A_{\le y}(x)\cup A_{>y}(x), \] where $A_{\le y}(x)$ consists of those $n\in A\cap[1,x]$ with largest prime factor at most $y$, and $A_{>y}(x)$ those with largest prime factor exceeding $y$.

Clearly, \[ |A_{\le y}(x)|\le \Psi(x,y). \]

Now let $n\in A_{>y}(x)$, and let $p=P(n)>y$ be the largest prime factor of $n$. By the defining property of $A$, applied to this prime $p$, there exists a divisor $d\mid n$ with $d>1$ and $d\equiv 1\pmod p$. Write \[ d=1+ap,\qquad a\ge 1. \] Because $d\equiv 1\pmod p$, we have $p\nmid d$, so $p\,d\mid n$. Hence $n$ is a multiple of \[ p(1+ap). \] Therefore, for fixed $(p,a)$, the number of such $n\le x$ is at most \[ \frac{x}{p(1+ap)}. \] Summing over all admissible $p$ and $a$ gives \[ |A_{>y}(x)| \le x\sum_{\substack{p>y\\ p\ \mathrm{prime}}}\ \sum_{1\le a\le x/p}\frac{1}{p(1+ap)}. \] Since \[ \frac{1}{p(1+ap)}\le \frac{1}{a p^2}, \] we obtain \[ |A_{>y}(x)| \le x\sum_{\substack{p>y\\ p\ \mathrm{prime}}}\frac{1}{p^2}\sum_{1\le a\le x/p}\frac{1}{a} \le x(1+\log x)\sum_{p>y}\frac{1}{p^2}. \] Finally, \[ \sum_{p>y}\frac{1}{p^2}\le \sum_{m>y}\frac{1}{m^2}\le \frac{1}{y-1}, \] so \[ |A_{>y}(x)|\le \frac{x(1+\log x)}{y-1}. \]

Combining the two pieces: \[ A(x)\le \Psi(x,y)+\frac{x(1+\log x)}{y-1}. \tag{5.1} \]

Step 2: choose the threshold.

Take \[ y=\exp\!\left(\frac{1}{\sqrt 2}\sqrt{L\,L_2}\right). \] Then \[ u:=\frac{\log x}{\log y}=\sqrt{\frac{2L}{L_2}}. \]

A standard smooth-number theorem of Canfield--Erdős--Pomerance (in the form quoted in Granville's survey) says that if $u\to\infty$ and $u\le y^{1-\varepsilon}$ for some fixed $\varepsilon>0$, then \[ \Psi(x,y)=x\,u^{-u+o(u)}=x\exp\left(-(1+o(1))u\log u\right). \] For the present choice of $y$, we have $u\to\infty$ and, for example, $u\le y^{1/2}$ for all large $x$, because \[ \log u=O(L_2)=o(\log y). \] Hence the theorem applies.

Now \[ u\log u = \sqrt{\frac{2L}{L_2}}\cdot \frac{1}{2}\log\!\left(\frac{2L}{L_2}\right) = \left(\frac{1}{\sqrt 2}+o(1)\right)\sqrt{L\,L_2}. \] Therefore \[ \Psi(x,y) \le x\exp\!\left(-\left(\frac{1}{\sqrt 2}+o(1)\right)\sqrt{L\,L_2}\right). \tag{5.2} \]

On the other hand, \[ \frac{x(1+\log x)}{y-1} = x\exp\!\left(-\frac{1}{\sqrt 2}\sqrt{L\,L_2}+O(L_2)\right) = x\exp\!\left(-\left(\frac{1}{\sqrt 2}+o(1)\right)\sqrt{L\,L_2}\right), \tag{5.3} \] since $L_2=o(\sqrt{L\,L_2})$.

Insert $5.2$ and $5.3$ into $5.1$: \[ A(x)\le x\exp\!\left(-\left(\frac{1}{\sqrt 2}+o(1)\right)\sqrt{L\,L_2}\right). \] This proves the theorem.

A simple structural check.

The proof above is consistent with the elementary fact that every $n\in A$ satisfies \[ P(n)\le \sqrt n. \] Indeed, if $p=P(n)>\sqrt n$, then $p^2>n$, so $p$ occurs only to the first power in $n$; any divisor $d\equiv 1\pmod p$ must be coprime to $p$, hence $d\mid n/p<p$, impossible because $d>1$ and $d\equiv 1\pmod p$ force $d\ge p+1$.

6. ADVERSARIAL VERIFICATION

There are three places where the new argument could fail.

1. Double counting of $n$. That is harmless: the bound for $A_{>y}(x)$ is an upper bound, so overcounting is allowed.

2. Range of the smooth-number theorem. For my choice \[ y=\exp\!\left(\frac{1}{\sqrt 2}\sqrt{L\,L_2}\right), \] we have $u=\sqrt{2L/L_2}\to\infty$ and \[ \log u=O(L_2)=o(\log y), \] hence $u\le y^{1/2}$ for large $x$. So the Canfield--Erdős--Pomerance estimate applies.

3. Possible loss in the rough part. The rough bound is extremely crude, but all I need is the exponent scale. The factor $1+\log x$ only contributes $O(L_2)$ in the exponent, which is negligible compared with $\sqrt{L\,L_2}$.

So the Round-2 theorem is gap-free.

7. FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 strengthens the Round-1 conclusion from \[ A(x)=o(x) \] to the explicit subexponential estimate \[ A(x)\le x\exp\!\left(-\left(\frac{1}{\sqrt 2}+o(1)\right)\sqrt{\log x\,\log\log x}\right). \] This is still weaker than the upper bound quoted on the problem page, and very far from the conjectured \[ \exp\!\left(-(c+o(1))\sqrt{\log x}\,\log\log x\right) \] law, but it is a real quantitative advance beyond Round 1.

8. COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 38%

9. REFERENCES

• T. F. Bloom, Erdős Problem #768, ErdosProblems.com, accessed 2026-03-07.
• A. Granville, Smooth numbers: computational number theory and beyond; used for the quoted Canfield--Erdős--Pomerance smooth-number estimate.

Problem 768 (Round 2)

1. ROUND-2 OBJECTIVE

Path (C): isolate a genuine quantitative obstruction and strengthen the Round-1 result from mere density $0$ to an explicit subexponential upper bound. Round 1 only proved that \[ \frac{|A\cap[1,x]|}{x}\to 0. \] The exact Erdős asymptotic \[ \frac{|A\cap[1,x]|}{x}=\exp\!\left(-(c+o(1))\sqrt{\log x}\,\log\log x\right) \] remains out of reach, so the most promising Round-2 target is to close the first major gap: obtain a nontrivial upper bound on the natural scale \[ \exp\!\left(-c\sqrt{\log x\,\log\log x}\right). \]

2. Round-1 FOUNDATION USED

I use exactly two Round-1 ingredients.

1. The definition of \[ A=\left\{n\ge 1:\ \forall p\mid n \text{ prime},\ \exists d\mid n,\ d>1,\ d\equiv 1 \pmod p\right\}. \]
2. The Round-1 rough/smooth decomposition idea: if $p=P(n)$ is the largest prime factor of $n\in A$, then there is a divisor of the form $1+ap$ dividing $n$, and this can be counted by summing over $(p,a)$.

I do not reprove the Round-1 density-$0$ theorem; I strengthen it quantitatively.

3. NEW INSIGHT / TOOL (ROUND 2)

The new step is to let the smoothness threshold depend on $x$ and optimize it.

Write $\Psi(x,y)$ for the number of $y$-smooth integers $\le x$. Then the Round-1 argument actually gives, for every $2\le y\le x$, \[ |A\cap[1,x]| \le \Psi(x,y) + x\sum_{\substack{p>y\\ p\ \mathrm{prime}}}\ \sum_{1\le a\le x/p}\frac{1}{p(1+ap)}. \] Using a standard smooth-number estimate in the Canfield--Erdős--Pomerance range, and then optimizing $y$, yields a genuine subexponential decay.

4. ATTACK PLAN (ROUND 2)

The exact Round-1 gap was this: density $0$ is much too weak compared to the problem's conjectural scale. So I now prove the following explicit theorem.

Theorem. Let \[ A(x)=|A\cap[1,x]|. \] Then, as $x\to\infty$, \[ A(x)\le x\exp\!\left(-\left(\frac{1}{\sqrt 2}+o(1)\right)\sqrt{\log x\,\log\log x}\right). \]

This does not settle Erdős's conjectured $\sqrt{\log x}\,\log\log x$ scale, but it is a strict Round-2 advance beyond density $0$.

5. WORK (ROUND 2)

Let \[ L=\log x,\qquad L_2=\log\log x. \]

Step 1: a uniform counting inequality.

Fix $y$ with $2\le y\le x$. Split \[ A\cap[1,x] = A_{\le y}(x)\cup A_{>y}(x), \] where $A_{\le y}(x)$ consists of those $n\in A\cap[1,x]$ with largest prime factor at most $y$, and $A_{>y}(x)$ those with largest prime factor exceeding $y$.

Clearly, \[ |A_{\le y}(x)|\le \Psi(x,y). \]

Now let $n\in A_{>y}(x)$, and let $p=P(n)>y$ be the largest prime factor of $n$. By the defining property of $A$, applied to this prime $p$, there exists a divisor $d\mid n$ with $d>1$ and $d\equiv 1\pmod p$. Write \[ d=1+ap,\qquad a\ge 1. \] Because $d\equiv 1\pmod p$, we have $p\nmid d$, so $p\,d\mid n$. Hence $n$ is a multiple of \[ p(1+ap). \] Therefore, for fixed $(p,a)$, the number of such $n\le x$ is at most \[ \frac{x}{p(1+ap)}. \] Summing over all admissible $p$ and $a$ gives \[ |A_{>y}(x)| \le x\sum_{\substack{p>y\\ p\ \mathrm{prime}}}\ \sum_{1\le a\le x/p}\frac{1}{p(1+ap)}. \] Since \[ \frac{1}{p(1+ap)}\le \frac{1}{a p^2}, \] we obtain \[ |A_{>y}(x)| \le x\sum_{\substack{p>y\\ p\ \mathrm{prime}}}\frac{1}{p^2}\sum_{1\le a\le x/p}\frac{1}{a} \le x(1+\log x)\sum_{p>y}\frac{1}{p^2}. \] Finally, \[ \sum_{p>y}\frac{1}{p^2}\le \sum_{m>y}\frac{1}{m^2}\le \frac{1}{y-1}, \] so \[ |A_{>y}(x)|\le \frac{x(1+\log x)}{y-1}. \]

Combining the two pieces: \[ A(x)\le \Psi(x,y)+\frac{x(1+\log x)}{y-1}. \tag{5.1} \]

Step 2: choose the threshold.

Take \[ y=\exp\!\left(\frac{1}{\sqrt 2}\sqrt{L\,L_2}\right). \] Then \[ u:=\frac{\log x}{\log y}=\sqrt{\frac{2L}{L_2}}. \]

A standard smooth-number theorem of Canfield--Erdős--Pomerance (in the form quoted in Granville's survey) says that if $u\to\infty$ and $u\le y^{1-\varepsilon}$ for some fixed $\varepsilon>0$, then \[ \Psi(x,y)=x\,u^{-u+o(u)}=x\exp\left(-(1+o(1))u\log u\right). \] For the present choice of $y$, we have $u\to\infty$ and, for example, $u\le y^{1/2}$ for all large $x$, because \[ \log u=O(L_2)=o(\log y). \] Hence the theorem applies.

Now \[ u\log u = \sqrt{\frac{2L}{L_2}}\cdot \frac{1}{2}\log\!\left(\frac{2L}{L_2}\right) = \left(\frac{1}{\sqrt 2}+o(1)\right)\sqrt{L\,L_2}. \] Therefore \[ \Psi(x,y) \le x\exp\!\left(-\left(\frac{1}{\sqrt 2}+o(1)\right)\sqrt{L\,L_2}\right). \tag{5.2} \]

On the other hand, \[ \frac{x(1+\log x)}{y-1} = x\exp\!\left(-\frac{1}{\sqrt 2}\sqrt{L\,L_2}+O(L_2)\right) = x\exp\!\left(-\left(\frac{1}{\sqrt 2}+o(1)\right)\sqrt{L\,L_2}\right), \tag{5.3} \] since $L_2=o(\sqrt{L\,L_2})$.

Insert $5.2$ and $5.3$ into $5.1$: \[ A(x)\le x\exp\!\left(-\left(\frac{1}{\sqrt 2}+o(1)\right)\sqrt{L\,L_2}\right). \] This proves the theorem.

A simple structural check.

The proof above is consistent with the elementary fact that every $n\in A$ satisfies \[ P(n)\le \sqrt n. \] Indeed, if $p=P(n)>\sqrt n$, then $p^2>n$, so $p$ occurs only to the first power in $n$; any divisor $d\equiv 1\pmod p$ must be coprime to $p$, hence $d\mid n/p<p$, impossible because $d>1$ and $d\equiv 1\pmod p$ force $d\ge p+1$.

6. ADVERSARIAL VERIFICATION

There are three places where the new argument could fail.

1. Double counting of $n$. That is harmless: the bound for $A_{>y}(x)$ is an upper bound, so overcounting is allowed.

2. Range of the smooth-number theorem. For my choice \[ y=\exp\!\left(\frac{1}{\sqrt 2}\sqrt{L\,L_2}\right), \] we have $u=\sqrt{2L/L_2}\to\infty$ and \[ \log u=O(L_2)=o(\log y), \] hence $u\le y^{1/2}$ for large $x$. So the Canfield--Erdős--Pomerance estimate applies.

3. Possible loss in the rough part. The rough bound is extremely crude, but all I need is the exponent scale. The factor $1+\log x$ only contributes $O(L_2)$ in the exponent, which is negligible compared with $\sqrt{L\,L_2}$.

So the Round-2 theorem is gap-free.

7. FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 strengthens the Round-1 conclusion from \[ A(x)=o(x) \] to the explicit subexponential estimate \[ A(x)\le x\exp\!\left(-\left(\frac{1}{\sqrt 2}+o(1)\right)\sqrt{\log x\,\log\log x}\right). \] This is still weaker than the upper bound quoted on the problem page, and very far from the conjectured \[ \exp\!\left(-(c+o(1))\sqrt{\log x}\,\log\log x\right) \] law, but it is a real quantitative advance beyond Round 1.

8. COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 38%

9. REFERENCES

• T. F. Bloom, Erdős Problem #768, ErdosProblems.com, accessed 2026-03-07.
• A. Granville, Smooth numbers: computational number theory and beyond; used for the quoted Canfield--Erdős--Pomerance smooth-number estimate.

Problem 768: exact membership on every two-prime support

1) OBJECTIVE AND SOURCE REVIEW

Attempt dated 2026-09-23. I read 768.tex and 768_v2.tex fully; their arguments coincide. They concern integers $n$ such that for every prime $p\mid n$ some divisor $d>1$ satisfies $d\equiv1\pmod p$, and seek the counting asymptotic on the proposed $\sqrt{\log x}\log\log x$ exponent scale. Their rough/smooth bound ignores the simultaneous conditions from different prime factors. I analyze those conditions exactly when there are two prime factors and preserve more information in the rough-counting reduction.

2) WORK

For distinct primes $p,q$, write $r=\operatorname{ord}_q(p)$ and $s=\operatorname{ord}_p(q)$, taking the order modulo two as one. Then, for $a,b\ge1$, \[ p^a q^b\in A\quad\Longleftrightarrow\quad a\ge r\ \text{ and }\ b\ge s. \] Indeed a divisor congruent to one modulo $p$ cannot contain $p$, so it must be $q^j$ for some $1\le j\le b$. Such a divisor exists exactly when $b\ge\operatorname{ord}_p(q)$. Interchanging the primes gives the other condition. Pure prime powers never belong to $A$, since every nontrivial divisor is zero modulo that prime.

For fixed $p,q$, this completely counts the eventual exponent region. If $N_{p,q}(x)$ counts these two-prime members up to $x$, set $T=\log x-r\log p-s\log q$. Lattice-point counting in a right triangle yields \[ N_{p,q}(x)=\frac{T^2}{2\log p\log q}+O_{p,q}(T+1) \qquad(T\to\infty). \] To verify this directly, sum $1+\lfloor(T-i\log p)/\log q\rfloor$ for $0\le i\le T/\log p$. Replacing floors by their arguments costs $O_{p,q}(T+1)$, and the arithmetic sum has the stated leading area. In particular, on support $\{2,3\}$ the exact condition is $a\ge2,b\ge1$.

The largest-prime decomposition can also retain both smoothness restrictions. If $p=P(n)>y$ and $d=1+ap\mid n$, then $p(1+ap)\mid n$, every prime factor of $d$ is at most $p$, and the quotient is $p$-smooth. Thus \[ A(x)\le\Psi(x,y)+ \sum_{\substack{y<p\le\sqrt x\\p\text{ prime}}} \sum_{\substack{1\le a\le (x-p)/p^2\\P(1+ap)\le p}} \Psi\left(\frac{x}{p(1+ap)},p\right). \] This exact upper bound is stronger than replacing each smooth count by its argument, but no improved asymptotic estimate for this double sum is established here.

3) ADVERSARIAL VERIFICATION

The two-prime asymptotic is only for a fixed pair; its constants and thresholds are not uniform when the primes grow with $x$. Summing it over all pairs without controlling their multiplicative orders would be invalid. Overcounting numbers with several qualifying divisors is harmless in the displayed upper bound. The source's smooth-number bound remains much weaker than the requested final scale.

4) FINAL

UNRESOLVED. Fixed two-prime supports are classified exactly, and a refined counting inequality is available. Controlling growing supports and interacting multiplicative orders strongly enough for the full asymptotic is the remaining gap.

5) SOURCES CHECKED

Both complete supplied versions, read 2026-09-23. The membership criterion, elementary lattice estimate, and refined inequality are proved here; no new smooth-number theorem or numerical asymptotic is asserted.

6) COMPLETION ESTIMATE

Subjective progress toward the complete counting asymptotic. COMPLETION: 15%