Erdős Problem #650

Erdős Problem 650: matching integers to distinct multiples

Statement and answer.

Let $f(m)$ be the largest universally guaranteed number of distinct elements of an $m$-element set $A\subseteq\{1,\ldots,N\}$ that can be matched to distinct divisible integers in any interval of length $2N$. Then \[ \boxed{f(m)=\min\{m,\lceil2\sqrt m\rceil\}.} \] We prove the lower bound even for open intervals, and give a matching upper construction whose endpoints are not multiples of any member of $A$. Thus endpoint conventions do not affect the answer. In particular the displayed question $f(m)\leq\sqrt m$ on the problem page is not the correct exact bound.

Attribution.

This reconstructs the corrected proof of van Doorn, Li, and Tang, Optimal bounds for an Erdős problem on matching integers to distinct multiples, https://arxiv.org/abs/2603.28636, Theorems 3.1 and 4.1. That paper attributes the original strategy to GPT-5.4 Pro and the repair of the exceptional injection to Aristotle. The present argument is an attributed reconstruction, not a new discovery or a claim of a new Lean verification. See https://www.erdosproblems.com/650.

The matching reduction.

Let the right vertices be the integers in an open interval $I=(x,x+2N)$, and join $a\in A$ to its multiples in $I$. For $S\subseteq A$, write $\Gamma(S)$ for its neighbourhood. If every nonempty $S$ satisfies \[ |\Gamma(S)|\geq2\sqrt{|S|}, \tag{1} \] Hall's theorem supplies a matching of size at least $\min(m,\lceil2\sqrt m\rceil)$. Indeed, set $\delta=\max_{S\subseteq A}(|S|-|\Gamma(S)|)\geq0$. Adding $\delta$ universal right vertices gives Hall's condition, and a matching of all $m$ left vertices loses at most $\delta$ edges when the added vertices are deleted. Since $s-2\sqrt s$ increases for integer $s\geq1$, $1$ yields $\delta\leq\max(0,m-2\sqrt m)$, proving the assertion.

It suffices to treat $N=\max A$: any longer interval contains an open subinterval of the required smaller length. If $x\notin N\mathbb Z$, split the interval at $b_0=x+N$, with the midpoint in the left half. For each $a\in S$, let $u_a$ be the largest multiple of $a$ at most $b_0$. Then \[ x<u_a\leq b_0<u_a+a<x+2N. \] The final inequality is strict: equality would require $a=N$ and $x\in N\mathbb Z$. The map $a\mapsto(u_a,u_a+a)$ into the two halves of $\Gamma(S)$ is injective because the difference recovers $a$. Their sizes therefore have product at least $|S|$, and the arithmetic--geometric mean inequality proves $1$.

The exceptional endpoint case.

Suppose $x\in N\mathbb Z$, so $b_0=x+N$ is an integer. Match $N$ to $b_0$, and delete these two vertices. Let $A'=A\setminus\{N\}$. For a subset $S\subseteq A'$ we construct an injection into its remaining left-half and right-half neighbours. Define $u_a$ as before, and set \[ \phi(a)= \begin{cases} (u_a,u_a+a),& a\nmid b_0 \quad\text{(type 1)},\\ (b_0-2a,b_0+2a),& a\mid b_0,\ 2a<N,\ 2a\nmid b_0 \quad\text{(type 2)},\\ (b_0-a,b_0+a),& a\mid b_0,\ [\,2a\geq N\ \text{or}\ 2a\mid b_0\,] \quad\text{(type 3)}. \end{cases} \tag{2} \] Every coordinate is a multiple of $a$, belongs to the correct open half, and differs from $b_0$. Within each type, the coordinate difference recovers $a$. For mixed types, suppose two images coincide. Their midpoint is then $b_0$. For types 1 and 2, with arguments $a,a'$, the difference gives $a=4a'$, whence $b_0=u_a+2a'$ is divisible by $2a'$, a contradiction. For types 1 and 3, the difference gives $a=2a'<N$. Type 3 therefore requires $2a'\mid b_0$, whereas $b_0=u_a+a'$ is an odd multiple of $a'$, again impossible. For types 2 and 3 the difference gives $a'=2a$; type 3 implies $a'\mid b_0$, contradicting the type 2 condition. Thus $2$ is injective.

It follows that $1$ holds in the reduced graph. For $m\geq2$, adding back the reserved edge gives at least \[ 1+\min(m-1,2\sqrt{m-1})\geq\min(m,2\sqrt m) \] matched vertices; integrality gives the desired ceiling. The case $m=1$ is immediate. This completes the lower bound, including the endpoint case where the simpler injection fails.

A rectangular upper construction.

We show that a set of $st$ integers can have all its multiples in an interval confined to just $s+t$ integers. Cases with $\min(s,t)=1$ satisfy the upper bound trivially, so assume $2\leq s\leq t$. Let $D=\operatorname{lcm}(1,\ldots,st)$, and let $\mathcal P$ consist of the primes $p>st$ dividing at least one nonzero integer \[ q+rD,\qquad 0<|q|<s,\quad |r|<t. \] This is a finite set. For each $p\in\mathcal P$, avoid the at most $st<p$ residue classes $-i-jD$, $1\leq i\leq s$, $1\leq j\leq t$. The ordinary Chinese remainder theorem lets us choose $M>2s+2tD$ avoiding all of them simultaneously. Set \[ a_{ij}=M+i+jD,\qquad A=\{a_{ij}:1\leq i\leq s,\ 1\leq j\leq t\}. \] These $st$ integers are distinct because $D>s$.

We claim \[ \gcd(a_{ij},a_{k\ell})\mid i-k. \tag{3} \] There is nothing to prove if $i=k$. Otherwise put $q=i-k\ne0$, $r=j-\ell$. Any common prime divisor larger than $st$ belongs to $\mathcal P$, contrary to the choice of $M$. For a common prime $p\leq st$, we have $v_p(D)>v_p(q)$: if $p\nmid q$, this follows from $p\mid D$; otherwise $q^2<s^2\leq st$ implies $q^2\mid D$. Thus $v_p(q+rD)=v_p(q)$. Since the gcd divides $q+rD$, $3$ follows prime by prime.

The generalized Chinese remainder theorem now supplies $x_0$ with $x_0\equiv i\pmod{a_{ij}}$ for every $i,j$. Adding a large common multiple makes $x=x_0-M>1$. Put $N=\max A=M+s+tD$ and $I=(x,x+2N)$. For each $a_{ij}$, $x_0-i$ is a multiple, and the preceding and second following multiples satisfy \[ (x_0-i)-a_{ij}=x-2i-jD<x, \] \[ (x_0-i)+2a_{ij}=x+3M+i+2jD>x+2N. \] Consequently the only possible multiples in $I$ are \[ x_0-i\quad\hbox{and}\quad x_0+M+jD. \] Both lie strictly inside $I$; the strict preceding and following inequalities also exclude multiples at its endpoints. There are at most $s+t$ integers in this union, so no divisibility matching can be larger.

All values of $m$.

Set $q=\lceil2\sqrt m\rceil$, $s=\lfloor q/2\rfloor$, $t=\lceil q/2\rceil$. Then $st=\lfloor q^2/4\rfloor\geq m$ and $s+t=q$. If $q\geq m$, the trivial upper bound $f(m)\leq m$ suffices. Otherwise $s,t\geq2$, and the rectangular construction applies. Keep any $m$ members of its set, including its largest member. The interval retains length $2\max A$, while its union of available multiples cannot grow. Hence $f(m)\leq q$. Together with the lower bound, this proves the exact formula.

Completion estimate.

COMPLETION: 100%

Problem 650 --- ROUND 2

1) ROUND-2 OBJECTIVE

Path (A): give a full proof of the target statement, and in fact of the stronger theorem \[ f(st)\le s+t \qquad (s,t\ge 1). \] This implies the desired bound \[ f(m)\le 2\lceil \sqrt m\rceil, \] so the original square-root upper-bound question is answered affirmatively.

2) Round-1 FOUNDATION USED

I use only one Round-1 item: the equivalent bipartite-matching reformulation. Namely, for a set $A\subseteq \{1,\dots,N\}$ and an interval $I$ of length $2N$, one considers the bipartite graph with left side $A$, right side $I\cap\mathbb Z$, and edges $(a,b)$ whenever $a\mid b$. Bounding the maximum matching is equivalent to bounding $f(m)$.

3) NEW INSIGHT / TOOL (ROUND-2)

The new ingredient is an explicit Chinese-remainder construction which forces all integers in the interval divisible by members of $A$ to lie in only $s+t$ prescribed locations. This is much stronger than the original target $f(m)\ll \sqrt m$.

4) ATTACK PLAN (ROUND-2)

To prove $f(st)\le s+t$, it suffices to construct, for each $s,t\ge 1$,

• an integer $N$,
• a set $A\subseteq \{1,\dots,N\}$ with $|A|=st$,
• an interval $I$ of length $2N$,

such that at most $s+t$ integers of $I$ are divisible by at least one element of $A$. Then any matching in the bipartite divisibility graph has size at most $s+t$.

The key steps are:

1. construct numbers $a_{i,j}$ whose pairwise gcd's are carefully controlled;
2. solve a compatible simultaneous congruence system so that each $a_{i,j}$ divides a prescribed integer $x_0+i$;
3. place the interval so that each $a_{i,j}$ has exactly two multiples inside it, and all such multiples lie in a fixed set of size $s+t$.

5) WORK (ROUND-2)

Theorem 650.1.

For all integers $s,t\ge 1$, \[ f(st)\le s+t. \] Consequently, for every $m\ge 1$, \[ f(m)\le 2\lceil\sqrt m\rceil. \]

Proof.

We first prove the stronger statement $f(st)\le s+t$. If $s=1$ or $t=1$, then any matching has size at most $|A|=st\le s+t$, so there is nothing to prove. Hence assume from now on that \[ s,t\ge 2. \]

Define \[ E:=\prod_{p\le st} p^{1+\lfloor \log_p(s-1)\rfloor}, \qquad D:=E\cdot \mathrm{lcm}(1,2,\dots,st). \] Then for every prime $p\le st$ and every integer $\delta$ with \[ 1\le |\delta|\le s-1, \] one has \[ v_p(D)>v_p(\delta). \] Indeed, $v_p(\delta)\le \lfloor \log_p(s-1)\rfloor$, while the exponent of $p$ in $E$ is exactly $1+\lfloor \log_p(s-1)\rfloor$.

Now let \[ \mathcal P:=\left\{p>st:\ p\text{ prime and } p\mid (qD+\delta) \text{ for some }1\le q\le t-1, 1\le |\delta|\le s-1\right\}. \] This is a finite set of primes. For each $p\in\mathcal P$, consider the residue classes \[ i-jD \pmod p \qquad (1\le i\le s,\ 0\le j\le t-1). \] There are at most $st$ such classes, and $p>st$, so they do not exhaust all residue classes modulo $p$. Hence we may choose a residue class $r_p\pmod p$ such that \[ r_p\not\equiv i-jD \pmod p \qquad (1\le i\le s,\ 0\le j\le t-1). \] By the Chinese remainder theorem, there exists an integer $a$ such that \[ a\equiv r_p \pmod p \qquad (\forall p\in\mathcal P), \] and also \[ a>2(t-1)D+4s. \]

For $1\le i\le s$ and $0\le j\le t-1$, define \[ a_{i,j}:=a+jD-i. \] These integers are pairwise distinct. Indeed, if \[ a+jD-i=a+\ell D-k, \] then \[ (j-\ell)D=i-k. \] Since \[ |i-k|<s\le st\le D, \] we must have $j=\ell$, and then $i=k$.

Set \[ A:=\{a_{i,j}:1\le i\le s,\ 0\le j\le t-1\}, \qquad N:=a+(t-1)D-1. \] Then $|A|=st$, and every element of $A$ lies in $\{1,\dots,N\}$ because \[ 1\le a-s\le a_{i,j}\le a+(t-1)D-1=N. \]

Claim 650.2.

For any two pairs $(i,j)$ and $(k,\ell)$, \[ \gcd(a_{i,j},a_{k,\ell})\mid (k-i). \]

Proof.

Let \[ d:=\gcd(a_{i,j},a_{k,\ell}). \] Since \[ a_{i,j}-a_{k,\ell}=(j-\ell)D+(k-i), \] we have \[ d\mid (j-\ell)D+(k-i). \] There are three cases.

If $i=k$, then trivially $d\mid 0=(k-i)$. If $i\ne k$ and $j=\ell$, then immediately $d\mid (k-i)$. So only the case \[ i\ne k, \qquad j\ne \ell \] remains. Let \[ q:=|j-\ell|\in\{1,\dots,t-1\}. \] Choose \[ \delta= \begin{cases} k-i,& j>\ell,\\ i-k,& j<\ell. \end{cases} \] Then \[ 1\le |\delta|=|k-i|\le s-1, \] and from the divisibility above we obtain \[ d\mid qD+\delta. \] We first show that every prime divisor of $d$ is at most $st$. Suppose, for contradiction, that some prime $p>st$ divides $d$. Because $p\mid qD+\delta$ with $1\le q\le t-1$ and $1\le |\delta|\le s-1$, the prime $p$ lies in $\mathcal P$ by definition. On the other hand, $p\mid d\mid a_{i,j}=a+jD-i$, so \[ a\equiv i-jD \pmod p, \] contradicting the choice of $a\equiv r_p\pmod p$ with $r_p$ avoiding all residues $i-jD$. Thus every prime divisor of $d$ is at most $st$.

Now let $p\le st$ be any prime divisor of $d$. Since $d\mid qD+\delta$, we have $p\mid qD+\delta$. Also, \[ v_p(qD)\ge v_p(D)>v_p(\delta). \] Therefore \[ v_p(qD+\delta)=v_p(\delta)=v_p(k-i). \] Since $d\mid qD+\delta$, it follows that \[ v_p(d)\le v_p(k-i). \] This holds for every prime divisor $p$ of $d$, hence indeed \[ d\mid (k-i). \]

$\square$

By Claim 650.2, the congruence system \[ x\equiv -i \pmod{a_{i,j}} \qquad (1\le i\le s,\ 0\le j\le t-1) \] is pairwise compatible, because the difference between the residues $-i$ and $-k$ is $k-i$, and Claim 650.2 says that this is divisible by $\gcd(a_{i,j},a_{k,\ell})$. By the generalized Chinese remainder theorem, there exists a solution $x_0$. Replacing $x_0$ by a sufficiently large positive integer in the same residue class if necessary, we may assume that the interval introduced below lies inside $[1,\infty)$.

Choose an integer $T$ such that \[ 2\left((t-1)D+s-1\right)<T\le a-2s. \] Such a choice is possible because \[ a>2(t-1)D+4s. \] Now define the interval \[ I:=(x_0-T,\ x_0-T+2N]. \] It has length exactly $2N$.

Fix $(i,j)$ with $1\le i\le s$ and $0\le j\le t-1$. From \[ x_0\equiv -i \pmod{a_{i,j}} \] we get \[ a_{i,j}\mid (x_0+i). \] Also, because $a_{i,j}=a+jD-i$, \[ x_0+a+jD=(x_0+i)+a_{i,j}, \] so $x_0+a+jD$ is another multiple of $a_{i,j}$. We claim that these are the only two multiples of $a_{i,j}$ in $I$.

First, both lie in $I$. The offset of $x_0+i$ from the left endpoint $x_0-T$ is $T+i$, which is positive and satisfies \[ T+i\le T+s\le a-s<2N. \] Hence $x_0+i\in I$. Likewise, the offset of $x_0+a+jD$ from the left endpoint is $T+a+jD$, and \[ T+a+jD \le T+a+(t-1)D \le (a-2s)+a+(t-1)D <2N, \] because \[ 2N=2a+2(t-1)D-2 \] and \[ 2N-\left((a-2s)+a+(t-1)D\right)=(t-1)D+2s-2>0. \] So $x_0+a+jD\in I$.

Next, the preceding multiple of $a_{i,j}$ is \[ (x_0+i)-a_{i,j}. \] Its offset from the left endpoint is \[ T+i-a_{i,j}. \] But \[ a_{i,j}=a+jD-i\ge a-s, \] while \[ T+i\le T+s\le a-s. \] Hence \[ T+i-a_{i,j}\le 0, \] so this preceding multiple is not in $I$.

Finally, the next multiple after $x_0+a+jD$ is \[ (x_0+i)+2a_{i,j}. \] Its offset from the left endpoint is \[ T+i+2a_{i,j} \ge T+1+2(a-s). \] Using \[ T>2\left((t-1)D+s-1\right)=2(t-1)D+2s-2, \] we obtain \[ T+i+2a_{i,j} >2(t-1)D+2s-2+1+2a-2s =2a+2(t-1)D-1 >2N, \] since $2N=2a+2(t-1)D-2$. Thus this next multiple also lies outside $I$. Therefore $a_{i,j}$ has exactly two multiples in $I$, namely \[ x_0+i \qquad\text{and}\qquad x_0+a+jD. \]

It follows that every integer in $I$ divisible by some element of $A$ lies in the set \[ B:=\{x_0+i:1\le i\le s\}\cup\{x_0+a+jD:0\le j\le t-1\}. \] The two parts of this union are disjoint, because an equality \[ x_0+i=x_0+a+jD \] would imply $i=a+jD$, impossible since $1\le i\le s<a\le a+jD$. Hence \[ |B|=s+t. \] So the interval $I$ contains at most $s+t$ integers divisible by members of $A$. Consequently the maximum matching size in the bipartite divisibility graph is at most $s+t$. Therefore \[ f(st)\le s+t. \] This proves the stronger theorem.

To deduce the original one-parameter bound, let \[ n:=\lceil\sqrt m\rceil. \] Then $m\le n^2$. Apply the stronger theorem with $s=t=n$ to obtain a set $A\subseteq\{1,\dots,N\}$ of size $n^2$ and an interval of length $2N$ for which at most $2n$ integers in the interval are divisible by elements of $A$. Choose any subset $A'\subseteq A$ of size exactly $m$. The same interval still contains at most $2n$ integers divisible by elements of $A'$, because $A'\subseteq A$. Hence \[ f(m)\le 2n=2\lceil\sqrt m\rceil. \] This completes the proof.

$\square$

6) ADVERSARIAL VERIFICATION

I checked the following potential failure points.

• Pairwise distinctness of the moduli $a_{i,j}$. This is guaranteed by the inequality $|i-k|<D$.
• Existence of $a$. The exceptional-prime set $\mathcal P$ is finite, so CRT applies; adding a common multiple of all primes in $\mathcal P$ makes $a$ arbitrarily large.
• Existence of $T$. The interval \[ \left(2((t-1)D+s-1),\ a-2s\right] \] is nonempty because $a>2(t-1)D+4s$.
• Generalized CRT step. Claim 650.2 gives exactly the compatibility condition required for a simultaneous solution of congruences with non-coprime moduli.
• Exactly two multiples in $I$. Both the previous multiple and the next multiple were checked explicitly by offsets from the left endpoint; the half-open interval notation avoids endpoint ambiguity.
• Passage from $n^2$ to $m$. Taking an $m$-element subset cannot create new divisible integers, so the one-parameter bound follows immediately.

No gap remains.

7) FINAL

FULL SOLUTION --- FULL PROOF.

The original question is answered affirmatively. In fact the stronger theorem \[ f(st)\le s+t \qquad (s,t\ge 1) \] holds, and therefore \[ f(m)\le 2\lceil\sqrt m\rceil \qquad (m\ge 1). \]

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 100%

9) REFERENCES

1. T. F. Bloom, Erdős Problem #650 and discussion thread, accessed 2026-03-07.
2. Q. Tang, ep-650.tex (GitHub proof source linked from the discussion thread), accessed 2026-03-07.

10) OUTPUT FORMAT

This section is part of the combined drop-in file 643_644_650_solutions.tex; no preamble is used.

Problem 650 (distinct multiples in any interval of length $2N$)

FORMAL RESTATEMENT

Let $m\ge 1$. Define $f(m)$ to be the largest integer with the following property:

For every integer $N\ge 1$ and every set $A\subseteq\{1,\dots,N\}$ with $|A|=m$, every interval $I\subseteq[1,\infty)$ of length $2N$ contains at least $f(m)$ distinct integers $b_1,\dots,b_{f(m)}\in I$ such that each $b_i$ is divisible by a different element $a_i\in A$.

Equivalently: for each such $(N,A,I)$, in the bipartite graph with left part $A$ and right part $I\cap\mathbb Z$, where $a\sim b$ iff $a\mid b$, the maximum matching has size at least $f(m)$.

The question is to estimate $f(m)$ as $m\to\infty$, and in particular whether \[ f(m)\ll m^{1/2}. \]

QUICK LITERATURE/CONTEXT CHECK (browsing)

The problem statement on the Erdős Problems website records that Erdős and Sárányi $1959$ proved a lower bound of order \[f(m)\gg m^{1/2}. \] I did not find, in a brief search, a matching $O(m^{1/2})$ upper bound or a resolution of the posed question.

ATTACK PLAN

1. (Definitions/normalization) Recast as a matching problem in a bipartite graph.
2. (Try small parameters) Compute/guess $f(m)$ for $m\le 4$ to see the behaviour.
3. (Known theorems) Consider Hall's theorem, Kőnig's theorem (for bipartite graphs), and divisor-counting bounds.
4. (Probabilistic attempt) Randomly sample integers in $I$ and estimate how many distinct divisors from $A$ one can "capture".
5. (Construction attempt for upper bounds) Try to build $(N,A,I)$ with small maximum matching, to show $f(m)$ cannot be too large.
6. (Contradiction attempt for lower bounds) Assume maximum matching $<r$ and use Hall to force a structured obstruction; attempt to rule this out beyond $r\approx c\sqrt m$.

WORK

Step 1: Trivial universal bounds (proved)

Step 2: Matching reformulation via Hall

Fix $(N,A,I)$. Let $B:=I\cap\mathbb Z$ so $|B|=2N$. A matching of size $r$ corresponds to choosing distinct $a_1,\dots,a_r\in A$ and distinct $b_1,\dots,b_r\in B$ with $a_i\mid b_i$.

By Hall's theorem, the maximum matching size is $<r$ if and only if there exists a subset $S\subseteq A$ with \[ |N(S)|<|S|, \] where $N(S)\subseteq B$ is the set of all integers in $B$ divisible by at least one element of $S$.

A route to proving $f(m)\gg \sqrt m$ would be to show that such a Hall obstruction cannot occur with $|S|$ much larger than $\sqrt m$.

Step 3: Incomplete attempts

I attempted two approaches:

• Divisor-multiplicity averaging: lower bound $|N(S)|$ in terms of $\sum_{a\in S} (2N/a)$, and upper bound the number of $a\in S$ that can divide a fixed $b\in B$. This runs into the difficulty that $b$ can be very large (the interval is not bounded above), so $b$ can have extremely many divisors $\le N$.

• Poset/chain--antichain ideas: try to find a large subfamily of $A$ with a controlled divisibility structure (e.g. a long chain), for which distinct representatives can be chosen. I did not obtain a clean universal guarantee from this method without invoking deeper results.

VERIFICATION

Only the trivial inequalities are proved here; they are straightforward.

FINAL

UNRESOLVED.

Strongest fully proved partial result in this write-up:

The universal bounds $1\le f(m)\le m$.

The nontrivial lower bound $f(m)\gg \sqrt m$ (Erdős--Sárányi, 1959) and the questioned upper bound $f(m)\ll \sqrt m$ remain outside what I was able to prove from scratch here.

COMPLETION ESTIMATE

$0.10$.