Optimal bounds for an Erdős problem on matching integers to distinct multiples
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908921349799936 |
|---|---|
| author | van Doorn, Wouter Li, Yanyang Tang, Quanyu |
| author_facet | van Doorn, Wouter Li, Yanyang Tang, Quanyu |
| contents | Let $f(m)$ be the largest integer such that for every set $A = \{a_1 < \cdots < a_m\}$ of $m$ positive integers and every open interval $I$ of length $2a_m$, there exist at least $f(m)$ disjoint pairs $(a, b)$ with $a \in A$ dividing $b \in I$. Solving a problem of Erdős, we determine $f(m)$ exactly, and show $$ f(m)=\min\bigl(m,\lceil 2\sqrt{m}\,\rceil\bigr) $$ for all $m$. The proof was obtained through an AI-assisted workflow: the proof strategy was first proposed by ChatGPT, and the detailed argument was subsequently made fully rigorous and formally verified in Lean by Aristotle. The exposition and final proofs presented here are entirely human-written. [This paper solves Problem #650 on Bloom's website "Erdős problems".] |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_28636 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Optimal bounds for an Erdős problem on matching integers to distinct multiples van Doorn, Wouter Li, Yanyang Tang, Quanyu Combinatorics Number Theory Primary 11B75, Secondary 05C70, 05C35 Let $f(m)$ be the largest integer such that for every set $A = \{a_1 < \cdots < a_m\}$ of $m$ positive integers and every open interval $I$ of length $2a_m$, there exist at least $f(m)$ disjoint pairs $(a, b)$ with $a \in A$ dividing $b \in I$. Solving a problem of Erdős, we determine $f(m)$ exactly, and show $$ f(m)=\min\bigl(m,\lceil 2\sqrt{m}\,\rceil\bigr) $$ for all $m$. The proof was obtained through an AI-assisted workflow: the proof strategy was first proposed by ChatGPT, and the detailed argument was subsequently made fully rigorous and formally verified in Lean by Aristotle. The exposition and final proofs presented here are entirely human-written. [This paper solves Problem #650 on Bloom's website "Erdős problems".] |
| title | Optimal bounds for an Erdős problem on matching integers to distinct multiples |
| topic | Combinatorics Number Theory Primary 11B75, Secondary 05C70, 05C35 |
| url | https://arxiv.org/abs/2603.28636 |