/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

Erdős Problem 709

References:

    erdosproblems.com/709

    [ErSu59] P. Erdős and J. Surányi, Bemerkungen zu einer Aufgabe eines mathematischen Wettbewerbs, Mat. Lapok 10 (1959), 39–48.

    [Er92c] P. Erdős, Some of my forgotten problems in number theory, Hardy–Ramanujan J. 15 (1992), 34–50.

    [vD26] W. van Doorn, On the length of an interval that contains distinct multiples of the first $n$ positive integers, Integers (2026), #A7.

@[expose] public sectionopen Filter Asymptoticsnamespace Erdos709

The block of length consecutive positive integers immediately after start.

def window (start length : ℕ) : Finset ℕ := Finset.Icc (start + 1) (start + length)

A block contains distinct multiples of all elements of A.

def HasDistinctMultiples (A : Finset ℕ) (start length : ℕ) : Prop := ∃ choice : ℕ → ℕ, Set.InjOn choice (A : Set ℕ) ∧ ∀ a ∈ A, choice a ∈ window start length ∧ a ∣ choice a

The multiplier k works for all n-element inputs and all starting points. M is required to be the largest element of A.

def Works (n k : ℕ) : Prop := ∀ (A : Finset ℕ) (M : ℕ), A.card = n → M ∈ A → (∀ a ∈ A, a ≤ M) → (∀ a ∈ A, 2 ≤ a) → ∀ start : ℕ, HasDistinctMultiples A start (k * M)

k is the least multiplier that works for inputs of size n.

def IsOptimal (n k : ℕ) : Prop := Works n k ∧ ∀ j < k, ¬ Works n j

A matching in a shorter block remains a matching in any longer block.

@[category API, AMS 5 11] theorem matching_mono_length (A : Finset ℕ) (start small large : ℕ) (hsmall : small ≤ large) (h : HasDistinctMultiples A start small) : HasDistinctMultiples A start large := A:Finset ℕstart:ℕsmall:ℕlarge:ℕhsmall:small ≤ largeh:HasDistinctMultiples A start small⊢ HasDistinctMultiples A start large A:Finset ℕstart:ℕsmall:ℕlarge:ℕhsmall:small ≤ largechoice:ℕ → ℕhinj:Set.InjOn choice ↑Ahchoice:∀ a ∈ A, choice a ∈ window start small ∧ a ∣ choice a⊢ HasDistinctMultiples A start large A:Finset ℕstart:ℕsmall:ℕlarge:ℕhsmall:small ≤ largechoice:ℕ → ℕhinj:Set.InjOn choice ↑Ahchoice:∀ a ∈ A, choice a ∈ window start small ∧ a ∣ choice a⊢ ∀ a ∈ A, choice a ∈ window start large ∧ a ∣ choice a A:Finset ℕstart:ℕsmall:ℕlarge:ℕhsmall:small ≤ largechoice:ℕ → ℕhinj:Set.InjOn choice ↑Ahchoice:∀ a ∈ A, choice a ∈ window start small ∧ a ∣ choice aa:ℕha:a ∈ A⊢ choice a ∈ window start large ∧ a ∣ choice a A:Finset ℕstart:ℕsmall:ℕlarge:ℕhsmall:small ≤ largechoice:ℕ → ℕhinj:Set.InjOn choice ↑Ahchoice:∀ a ∈ A, choice a ∈ window start small ∧ a ∣ choice aa:ℕha:a ∈ Ahmem:choice a ∈ window start smallhdvd:a ∣ choice a⊢ choice a ∈ window start large ∧ a ∣ choice a A:Finset ℕstart:ℕsmall:ℕlarge:ℕhsmall:small ≤ largechoice:ℕ → ℕhinj:Set.InjOn choice ↑Ahchoice:∀ a ∈ A, choice a ∈ window start small ∧ a ∣ choice aa:ℕha:a ∈ Ahmem:choice a ∈ window start smallhdvd:a ∣ choice a⊢ choice a ∈ window start large A:Finset ℕstart:ℕsmall:ℕlarge:ℕhsmall:small ≤ largechoice:ℕ → ℕhinj:Set.InjOn choice ↑Ahchoice:∀ a ∈ A, choice a ∈ window start small ∧ a ∣ choice aa:ℕha:a ∈ Ahdvd:a ∣ choice ahmem:start + 1 ≤ choice a ∧ choice a ≤ start + small⊢ start + 1 ≤ choice a ∧ choice a ≤ start + large A:Finset ℕstart:ℕsmall:ℕlarge:ℕhsmall:small ≤ largechoice:ℕ → ℕhinj:Set.InjOn choice ↑Ahchoice:∀ a ∈ A, choice a ∈ window start small ∧ a ∣ choice aa:ℕha:a ∈ Ahdvd:a ∣ choice ahmem:start + 1 ≤ choice a ∧ choice a ≤ start + small⊢ start + 1 ≤ choice aA:Finset ℕstart:ℕsmall:ℕlarge:ℕhsmall:small ≤ largechoice:ℕ → ℕhinj:Set.InjOn choice ↑Ahchoice:∀ a ∈ A, choice a ∈ window start small ∧ a ∣ choice aa:ℕha:a ∈ Ahdvd:a ∣ choice ahmem:start + 1 ≤ choice a ∧ choice a ≤ start + small⊢ choice a ≤ start + large A:Finset ℕstart:ℕsmall:ℕlarge:ℕhsmall:small ≤ largechoice:ℕ → ℕhinj:Set.InjOn choice ↑Ahchoice:∀ a ∈ A, choice a ∈ window start small ∧ a ∣ choice aa:ℕha:a ∈ Ahdvd:a ∣ choice ahmem:start + 1 ≤ choice a ∧ choice a ≤ start + small⊢ start + 1 ≤ choice a All goals completed! 🐙 A:Finset ℕstart:ℕsmall:ℕlarge:ℕhsmall:small ≤ largechoice:ℕ → ℕhinj:Set.InjOn choice ↑Ahchoice:∀ a ∈ A, choice a ∈ window start small ∧ a ∣ choice aa:ℕha:a ∈ Ahdvd:a ∣ choice ahmem:start + 1 ≤ choice a ∧ choice a ≤ start + small⊢ choice a ≤ start + large All goals completed! 🐙

If multiplier k works, every larger multiplier also works.

@[category API, AMS 5 11] theorem works_mono (n k l : ℕ) (hkl : k ≤ l) (h : Works n k) : Works n l := n:ℕk:ℕl:ℕhkl:k ≤ lh:Works n k⊢ Works n l n:ℕk:ℕl:ℕhkl:k ≤ lh:Works n kA:Finset ℕM:ℕhcard:A.card = nhmax:M ∈ Ahbound:∀ a ∈ A, a ≤ Mhtwo:∀ a ∈ A, 2 ≤ astart:ℕ⊢ HasDistinctMultiples A start (l * M) All goals completed! 🐙

Every interval of M consecutive positive integers contains a multiple of a when 0 < a ≤ M.

a:ℕM:ℕstart:ℕha:0 < ahaM:a ≤ Mr:ℕ := start % ab:ℕ := start + (a - r)hr:r < aheq:start % a + a * (start / a) = starthbdiv:b = a * (start / a + 1)⊢ ∃ b ∈ window start M, a ∣ b a:ℕM:ℕstart:ℕha:0 < ahaM:a ≤ Mr:ℕ := start % ab:ℕ := start + (a - r)hr:r < aheq:start % a + a * (start / a) = starthbdiv:b = a * (start / a + 1)⊢ b ∈ window start Ma:ℕM:ℕstart:ℕha:0 < ahaM:a ≤ Mr:ℕ := start % ab:ℕ := start + (a - r)hr:r < aheq:start % a + a * (start / a) = starthbdiv:b = a * (start / a + 1)⊢ a ∣ b a:ℕM:ℕstart:ℕha:0 < ahaM:a ≤ Mr:ℕ := start % ab:ℕ := start + (a - r)hr:r < aheq:start % a + a * (start / a) = starthbdiv:b = a * (start / a + 1)⊢ b ∈ window start M a:ℕM:ℕstart:ℕha:0 < ahaM:a ≤ Mr:ℕ := start % ab:ℕ := start + (a - r)hr:r < aheq:start % a + a * (start / a) = starthbdiv:b = a * (start / a + 1)⊢ start + 1 ≤ b ∧ b ≤ start + M a:ℕM:ℕstart:ℕha:0 < ahaM:a ≤ Mr:ℕ := start % ab:ℕ := start + (a - r)hr:r < aheq:start % a + a * (start / a) = starthbdiv:b = a * (start / a + 1)⊢ start + 1 ≤ ba:ℕM:ℕstart:ℕha:0 < ahaM:a ≤ Mr:ℕ := start % ab:ℕ := start + (a - r)hr:r < aheq:start % a + a * (start / a) = starthbdiv:b = a * (start / a + 1)⊢ b ≤ start + M a:ℕM:ℕstart:ℕha:0 < ahaM:a ≤ Mr:ℕ := start % ab:ℕ := start + (a - r)hr:r < aheq:start % a + a * (start / a) = starthbdiv:b = a * (start / a + 1)⊢ start + 1 ≤ b a:ℕM:ℕstart:ℕha:0 < ahaM:a ≤ Mr:ℕ := start % ab:ℕ := start + (a - r)hr:r < aheq:start % a + a * (start / a) = starthbdiv:b = a * (start / a + 1)⊢ start + 1 ≤ start + (a - r) All goals completed! 🐙 a:ℕM:ℕstart:ℕha:0 < ahaM:a ≤ Mr:ℕ := start % ab:ℕ := start + (a - r)hr:r < aheq:start % a + a * (start / a) = starthbdiv:b = a * (start / a + 1)⊢ b ≤ start + M a:ℕM:ℕstart:ℕha:0 < ahaM:a ≤ Mr:ℕ := start % ab:ℕ := start + (a - r)hr:r < aheq:start % a + a * (start / a) = starthbdiv:b = a * (start / a + 1)⊢ start + (a - r) ≤ start + M All goals completed! 🐙 a:ℕM:ℕstart:ℕha:0 < ahaM:a ≤ Mr:ℕ := start % ab:ℕ := start + (a - r)hr:r < aheq:start % a + a * (start / a) = starthbdiv:b = a * (start / a + 1)⊢ a ∣ b All goals completed! 🐙

Erdős Problem 709 holds for a singleton input: the multiplier 1 suffices.

A:Finset ℕM:ℕhcard:A.card = 1hM:M ∈ Ahbound:∀ a ∈ A, a ≤ Mhtwo:∀ a ∈ A, 2 ≤ astart:ℕhA:A = {M}b:ℕhb:b ∈ window start Mhd:M ∣ ba:ℕha:a ∈ {M}⊢ (fun x ↦ b) a ∈ window start (1 * M) ∧ a ∣ (fun x ↦ b) a A:Finset ℕM:ℕhcard:A.card = 1hM:M ∈ Ahbound:∀ a ∈ A, a ≤ Mhtwo:∀ a ∈ A, 2 ≤ astart:ℕhA:A = {M}b:ℕhb:b ∈ window start Mhd:M ∣ ba:ℕha:a ∈ {M}hEq:a = M⊢ (fun x ↦ b) a ∈ window start (1 * M) ∧ a ∣ (fun x ↦ b) a A:Finset ℕM:ℕhcard:A.card = 1hM:M ∈ Ahbound:∀ a ∈ A, a ≤ Mhtwo:∀ a ∈ A, 2 ≤ astart:ℕhA:A = {M}b:ℕhb:b ∈ window start Mhd:M ∣ bha:M ∈ {M}⊢ (fun x ↦ b) M ∈ window start (1 * M) ∧ M ∣ (fun x ↦ b) M All goals completed! 🐙

For singleton inputs, every multiplier at least 1 works.

@[category API, AMS 5 11] theorem works_one_of_one_le (k : ℕ) (hk : 1 ≤ k) : Works 1 k := works_mono 1 1 k hk erdos_709.variants.singleton

IsAdmissible n c says that for every set $A \subseteq [2,\infty)$ of $n$ natural numbers, every block of at least $c \max(A)$ consecutive positive integers contains distinct multiples of the elements of $A$. Restricting to positive integers loses nothing: translating a block by a multiple of $\operatorname{lcm}(A)$ does not change which of its elements each $a \in A$ divides. Works above is the same condition with an integer multiplier.

def IsAdmissible (n : ℕ) (c : ℝ) : Prop := ∀ A : Finset ℕ, A.card = n → (∀ a ∈ A, 2 ≤ a) → ∀ start length : ℕ, c * ((A.sup id : ℕ) : ℝ) ≤ (length : ℝ) → HasDistinctMultiples A start length

$f(n)$ is the infimum of the admissible $c$. Since $c\max(A)$ need not be an integer, "an interval of $c\max(A)$ consecutive integers" is read as "at least $c\max(A)$ consecutive integers" (a longer interval contains a shorter one). For $n \geq 1$ the set of admissible $c$ contains $n$ and is bounded below by $0$, so sInf is the true infimum. The value $f(0)=0$ is a junk value and plays no role.

noncomputable def f (n : ℕ) : ℝ := sInf {c : ℝ | IsAdmissible n c}

The integers $5, 6, 7$ contain no distinct multiples of $2$ and $3$, since $6$ is the only multiple of each. So three consecutive integers are not enough for $A={2,3}$.

x:ℕ → ℕhinj:Set.InjOn x ↑{2, 3}h:∀ a ∈ {2, 3}, x a ∈ window 4 3 ∧ a ∣ x ah2d:2 ∣ x 2h3d:3 ∣ x 3h2w:4 + 1 ≤ x 2 ∧ x 2 ≤ 4 + 3h3w:4 + 1 ≤ x 3 ∧ x 3 ≤ 4 + 3h23:x 2 = x 3this:2 = 3⊢ False All goals completed! 🐙def erdos_709.answer : ℕ → ℝ := sorry

Let $f(n)$ be minimal such that, for any $A={a_1,\ldots,a_n}\subseteq [2,\infty)\cap\mathbb{N}$ of size $n$, in any interval $I$ of $f(n)\max(A)$ consecutive integers there exist distinct $x_1,\ldots,x_n\in I$ such that $a_i\mid x_i$.

Obtain good bounds for $f(n)$, or even an asymptotic formula.

We read "good bounds" as determining the order of magnitude of $f(n)$.

@[category research open, question value, AMS 11] theorem erdos_709 : f =Θ[atTop] erdos_709.answer := ⊢ f =Θ[atTop] erdos_709.answer All goals completed! 🐙

A problem of Erdős and Surányi [ErSu59], who proved $$(\log n)^c \ll f(n) \ll n^{1/2}$$ for some constant $c>0$.

This is the lower bound.

@[category research solved, AMS 11] theorem erdos_709.variants.ersu_lower : ∃ c > (0 : ℝ), (fun n : ℕ ↦ Real.log n ^ c) =O[atTop] f := ⊢ ∃ c > 0, (fun n ↦ Real.log ↑n ^ c) =O[atTop] f All goals completed! 🐙

A problem of Erdős and Surányi [ErSu59], who proved $$(\log n)^c \ll f(n) \ll n^{1/2}$$ for some constant $c>0$.

This is the upper bound.

@[category research solved, AMS 11] theorem erdos_709.variants.ersu_upper : f =O[atTop] fun n : ℕ ↦ (n : ℝ) ^ (1 / 2 : ℝ) := ⊢ f =O[atTop] fun n ↦ ↑n ^ (1 / 2) All goals completed! 🐙

The lower bound here can be improved, using van Doorn's lower bound for [711] from [vD26], to $$\frac{\log n}{\log\log n}\ll f(n).$$

@[category research solved, AMS 11] theorem erdos_709.variants.van_doorn_lower : (fun n : ℕ ↦ Real.log n / Real.log (Real.log n)) =O[atTop] f := ⊢ (fun n ↦ Real.log ↑n / Real.log (Real.log ↑n)) =O[atTop] f All goals completed! 🐙end Erdos709