we-solve (beta)

Math-5893-A2 · revision r1 · on Math-5893

gpt pro 5.2 attempt on Math-5893

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: solved. Claims here do not change the source status.

Manuscript

Contents
  1. Problem #783 (Coprime set with bounded harmonic sum covering $[1,n]$)
  2. 1) FORMAL RESTATEMENT
  3. 2) QUICK LITERATURE/CONTEXT CHECK
  4. 3) ATTACK PLAN
  5. 4) WORK
  6. 4.1 A universal lower bound
  7. 4.2 A regime where the candidate is (asymptotically) optimal
  8. Interpretation.
  9. 4.3 What happens for larger $C$ (heuristics)
  10. 4.4 Small-$n$ exact optimization as a sanity check
  11. 5) VERIFICATION
  12. 6) FINAL
  13. LABEL: UNRESOLVED.
  14. What is proved here.
  15. What remains open.
  16. Main obstacle.
  17. Next concrete steps.
  18. COMPLETION: 55%.
  19. References

Problem #783 (Coprime set with bounded harmonic sum covering $[1,n]$)

1) FORMAL RESTATEMENT

Fix a constant $C>0$ and let $n$ be large. We choose a set $A\subseteq\{2,3,\dots,n\}$ subject to

  1. $\gcd(a,b)=1$ for all distinct $a,b\in A$ (pairwise coprime);
  2. $\displaystyle \sum_{a\in A} \frac1a \le C$.
Define the "uncovered" set \[ U(A) := \big\{ m\in\{1,2,\dots,n\}: \forall a\in A,\ a\nmid m\big\}. \] Equivalently, $U(A)$ are those integers $\le n$ not divisible by any element of $A$.

Goal. Choose $A$ (depending on $n$ and $C$) to minimize $|U(A)|$.

Candidate suggested in the problem. Let $q_1>q_2>\cdots$ be the primes in decreasing order starting at the largest prime $\le n$. Let $k$ be maximal such that $\sum_{i=1}^k 1/q_i \le C$, and take $A=\{q_1,\dots,q_k\}$. The question asks whether this choice minimizes $|U(A)|$.

2) QUICK LITERATURE/CONTEXT CHECK

This problem appears as Erdős problem #783 on erdosproblems.com. I did not find a definitive published solution.

3) ATTACK PLAN

View this as a weighted covering problem. Each $a\in A$ "covers" the multiples $\{a,2a,\dots,\lfloor n/a\rfloor a\}$. We want to cover as much of $[1,n]$ as possible under a harmonic-cost budget and a coprimality constraint.

Two guiding principles.

  • Upper bound by the budget: ignoring overlaps, $a$ covers about $n/a$ integers and costs $1/a$, so the naive "efficiency" is about $n$ covered per unit cost. Overlaps between different $a$ are the main source of inefficiency.
  • Avoid overlaps by making all $a$ large: if $a,b>\sqrt{n}$ and $\gcd(a,b)=1$, then $ab>n$ and hence no integer $\le n$ is divisible by both $a$ and $b$. Thus for such large $A$ the covered sets are disjoint.

4) WORK

4.1 A universal lower bound

Let \[ B(A):=\{m\le n:\exists a\in A\text{ with }a\mid m\} \] be the covered set, so $|U(A)| = n-|B(A)|$. By a union bound, \[ |B(A)|\le \sum_{a\in A} \left\lfloor\frac{n}{a}\right\rfloor \le n\sum_{a\in A} \frac1a \le Cn. \] Therefore \begin{equation} \label{wsref-0-65-71-3a-6c-62} |U(A)| \ge n - Cn = (1-C)n. \end{equation} This bound is nontrivial when $C\le 1$.

4.2 A regime where the candidate is (asymptotically) optimal

A key observation is that when all chosen moduli are $>\sqrt{n}$, there are no overlaps.
Lemma (Disjointness above $\sqrt{n}$): If $a,b>\sqrt{n}$ and $\gcd(a,b)=1$, then no $m\le n$ is divisible by both $a$ and $b$. Hence the sets of multiples of elements of $A$ are pairwise disjoint whenever every $a\in A$ satisfies $a>\sqrt{n}$.
Proof: If $a\mid m$ and $b\mid m$ with $\gcd(a,b)=1$, then $ab\mid m$. But $ab>n$, so $m\ge ab>n$, contradiction. ∎

Now consider the candidate choice $A$ consisting of all primes $p$ in an interval $[y,n]$, where $y$ is chosen so that $\sum_{p\in[y,n]}1/p\approx C$.

Theorem (Asymptotic optimality for $C<\log 2$): Fix $0<C<\log 2$. For all sufficiently large $n$ there exists a set $A\subseteq\{2,\dots,n\}$ of pairwise coprime integers with $\sum_{a\in A} 1/a\le C$ such that \[ |U(A)| = (1-C)n + o(n). \] In particular, the lower bound (eq:lb) is asymptotically tight. Moreover, choosing $A$ to be (essentially) all primes $p\in[n^{e^{-C}},n]$ achieves this.
Proof[Proof sketch]: Let $y:=n^{e^{-C}}$. Since $C<\log 2$, we have $e^{-C}>1/2$, so $y>\sqrt{n}$.

By Mertens' theorem for primes, \[ \sum_{p\le x} \frac1p = \log\log x + B_1 + o(1), \] so \[ \sum_{y\le p\le n} \frac1p = \big(\log\log n - \log\log y\big) + o(1) = \big(\log\log n - \log(e^{-C}\log n)\big) + o(1) = C + o(1). \] Thus for $n$ large we can select a subset of primes in $[y,n]$ whose reciprocal sum is $\le C$ but arbitrarily close to $C$. Call this set $A$.

Because every $p\in A$ satisfies $p\ge y>\sqrt{n}$, Lemma lem:disjoint gives that the sets of multiples are disjoint. Hence \[ |B(A)| = \sum_{p\in A} \left\lfloor\frac{n}{p}\right\rfloor = n\sum_{p\in A} \frac1p + O(|A|). \] Here $|A|\le \pi(n)=o(n)$, so $O(|A|)=o(n)$. Since $\sum_{p\in A}1/p = C+o(1)$, we get $|B(A)|=Cn+o(n)$. Therefore $|U(A)| = n-|B(A)| = (1-C)n+o(n)$, as claimed. ∎

Interpretation.
For $C<\log 2$, one can spend the harmonic budget entirely on primes $>\sqrt{n}$, achieving essentially no overlaps and hence the best-possible coverage up to lower-order terms.

4.3 What happens for larger $C$ (heuristics)

When $C\ge \log 2$, the threshold $y=n^{e^{-C}}$ drops below $\sqrt{n}$, so overlaps among multiples of chosen primes become unavoidable. A natural "all large primes" choice $A=\{p: p\ge y\}$ covers precisely the integers $m\le n$ having some prime factor $\ge y$. Thus the uncovered set becomes the set of $y$--smooth numbers, whose size is traditionally denoted $\psi(n,y)$. Heuristically (Dickman--de Bruijn), if $y=n^{1/u}$ then \[ \psi(n,y) \sim n\,\rho(u), \] where $\rho$ is the Dickman function. Here $y=n^{e^{-C}}$ corresponds to $u=e^{C}$, predicting \[ |U(A)| \approx n\,\rho(e^{C}). \] Proving optimality of this choice (or finding a better one) appears difficult.

4.4 Small-$n$ exact optimization as a sanity check

For small $n$ one can brute-force the optimization problem and compare to the "take the largest primes" candidate. For example, for $n=30$ and $C=1.0$:
  • Candidate (largest primes with reciprocal sum $\le 1$): $A=\{29,23,19,17,13,11,7,5\}$, which leaves $|U(A)|=12$ uncovered.
  • An optimal set (by exact search) achieves $|U(A)|=6$ (one optimal choice is $A=\{2,7,9,17,19,23,25,29\}$ with $\sum 1/a\approx 0.983$).
This illustrates that the "largest primes" rule is not literally optimal for small $n$, but it does not decide the asymptotic question for $n\to\infty$.

5) VERIFICATION

  • Inequality (eq:lb) is immediate and correct (union bound).
  • Lemma lem:disjoint is a direct divisibility argument.
  • Theorem thm:C<log2 hinges on two standard facts: Mertens' asymptotic for $\sum_{p\le x}1/p$ and the observation that $C<\log 2$ implies $n^{e^{-C}}>\sqrt{n}$.

6) FINAL

LABEL: UNRESOLVED.
What is proved here.
For $0<C<\log 2$, the minimum possible uncovered set size satisfies \[ \min_A |U(A)| = (1-C)n + o(n), \] and can be achieved by choosing an appropriate set of primes all exceeding $\sqrt{n}$.
What remains open.
For general fixed $C\ge \log 2$, overlaps become unavoidable and I do not have a proof that the "largest primes" choice is optimal. The natural heuristic connects $|U(A)|$ to counts of smooth numbers, predicting $\approx n\rho(e^{C})$ uncovered for the "all primes $\ge n^{e^{-C}}$" choice, but optimality is not established.
Main obstacle.
One needs a sharp upper bound on the size of the union of multiples under only the harmonic budget and coprimality constraints. Controlling overlaps in a best-possible way is essentially a sieve-optimization problem.
Next concrete steps.
  1. Formulate the optimization as a constrained sieve and attempt to prove that any $A$ with $\sum 1/a\le C$ leaves at least $\psi(n,n^{e^{-C}})$ numbers uncovered (up to lower-order terms).
  2. Investigate whether allowing prime powers (one per prime) can ever beat the "large primes" strategy for $C\ge \log 2$.
  3. Compute the exact optimum for larger $n$ using integer programming with coprimality constraints, to guess the true asymptotic structure.
COMPLETION: 55%.

References

  • [MaSp24] S. Malekshahian and G. Spiro, On a clique-building game of Erdős, arXiv:2410.18304 $2024$.
  • [CaPr25] S. Cambie and H. Provoost, On edge-colouring-games by Erdős, and Bensmail and McInerney, arXiv:2505.03497v2 $2025$.
  • [BEF90] T. C. Brown, P. Erdős, and D. Z. Freedman, Quasi-progressions and descending waves, J. Combin. Theory Ser. A 53 $1990$, 81--95.
  • [So07] J. Solymosi, Note on sumsets of integers, European J. Combin. 28 $2007$, no. 4, 1067--1071.
  • [CiGr07] J. Cilleruelo and A. Granville, Lattice points on circles, squares in arithmetic progressions and sumsets of squares, in Additive combinatorics, CRM Proc. Lecture Notes, vol. 43, Amer. Math. Soc., Providence, RI, 2007, pp. 241--262.
  • [DiEl15] R. Dietmann and C. Elsholtz, Hilbert cubes in arithmetic sets, arXiv:1510.05260 $2015$.