/-
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 FormalConjecturesUtilErdős Problem 709
References:
[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 jA 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
refine ⟨b, ?_, ?_⟩ refine_1 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 Mrefine_2 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
· refine_1 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 simp only [window, Finset.mem_Icc] refine_1 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
constructor refine_1.left 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 ≤ brefine_1.right 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
· refine_1.left 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 dsimp [b] refine_1.left 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)
omega All goals completed! 🐙
· refine_1.right 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 dsimp [b] refine_1.right 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
omega All goals completed! 🐙
· refine_2 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 exact ⟨start / a + 1, hbdiv⟩ All goals completed! 🐙
Erdős Problem 709 holds for a singleton input: the multiplier 1 suffices.
@[category textbook, AMS 5 11]
theorem erdos_709.variants.singleton : Works 1 1 := by ⊢ Works 1 1
intro A M hcard hM hbound htwo start A:Finset ℕM:ℕhcard:A.card = 1hM:M ∈ Ahbound:∀ a ∈ A, a ≤ Mhtwo:∀ a ∈ A, 2 ≤ astart:ℕ⊢ HasDistinctMultiples A start (1 * M)
have hA : A = {M} := by ⊢ Works 1 1 A:Finset ℕM:ℕhcard:A.card = 1hM:M ∈ Ahbound:∀ a ∈ A, a ≤ Mhtwo:∀ a ∈ A, 2 ≤ astart:ℕhA:A = {M}⊢ HasDistinctMultiples A start (1 * M)
obtain ⟨z, hz⟩ := Finset.card_eq_one.mp hcard A:Finset ℕM:ℕhcard:A.card = 1hM:M ∈ Ahbound:∀ a ∈ A, a ≤ Mhtwo:∀ a ∈ A, 2 ≤ astart:ℕz:ℕhz:A = {z}⊢ A = {M} A:Finset ℕM:ℕhcard:A.card = 1hM:M ∈ Ahbound:∀ a ∈ A, a ≤ Mhtwo:∀ a ∈ A, 2 ≤ astart:ℕhA:A = {M}⊢ HasDistinctMultiples A start (1 * M)
have hMz : M = z := Finset.mem_singleton.mp (hz ▸ hM) A:Finset ℕM:ℕhcard:A.card = 1hM:M ∈ Ahbound:∀ a ∈ A, a ≤ Mhtwo:∀ a ∈ A, 2 ≤ astart:ℕz:ℕhz:A = {z}hMz:M = z⊢ A = {M} A:Finset ℕM:ℕhcard:A.card = 1hM:M ∈ Ahbound:∀ a ∈ A, a ≤ Mhtwo:∀ a ∈ A, 2 ≤ astart:ℕhA:A = {M}⊢ HasDistinctMultiples A start (1 * M)
simpa [hMz] using hz A:Finset ℕM:ℕhcard:A.card = 1hM:M ∈ Ahbound:∀ a ∈ A, a ≤ Mhtwo:∀ a ∈ A, 2 ≤ astart:ℕhA:A = {M}⊢ HasDistinctMultiples A start (1 * M) A:Finset ℕM:ℕhcard:A.card = 1hM:M ∈ Ahbound:∀ a ∈ A, a ≤ Mhtwo:∀ a ∈ A, 2 ≤ astart:ℕhA:A = {M}⊢ HasDistinctMultiples A start (1 * M)
obtain ⟨b, hb, hd⟩ :=
exists_multiple_in_window M M start (by A:Finset ℕM:ℕhcard:A.card = 1hM:M ∈ Ahbound:∀ a ∈ A, a ≤ Mhtwo:∀ a ∈ A, 2 ≤ astart:ℕhA:A = {M}⊢ 0 < M 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 ∣ b⊢ HasDistinctMultiples A start (1 * M) have := htwo M hM A:Finset ℕM:ℕhcard:A.card = 1hM:M ∈ Ahbound:∀ a ∈ A, a ≤ Mhtwo:∀ a ∈ A, 2 ≤ astart:ℕhA:A = {M}this:2 ≤ M⊢ 0 < M 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 ∣ b⊢ HasDistinctMultiples A start (1 * M); omega All goals completed! 🐙 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 ∣ b⊢ HasDistinctMultiples A start (1 * M)) le_rfl 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 ∣ b⊢ HasDistinctMultiples A start (1 * M)
refine ⟨fun _ => b, ?_, ?_⟩ refine_1 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 ∣ b⊢ Set.InjOn (fun x ↦ b) ↑Arefine_2 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 ∣ b⊢ ∀ a ∈ A, (fun x ↦ b) a ∈ window start (1 * M) ∧ a ∣ (fun x ↦ b) a
· refine_1 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 ∣ b⊢ Set.InjOn (fun x ↦ b) ↑A intro u hu v hv _ refine_1 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 ∣ bu:ℕhu:u ∈ ↑Av:ℕhv:v ∈ ↑Aa✝:(fun x ↦ b) u = (fun x ↦ b) v⊢ u = v
rw [hA refine_1 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 ∣ bu:ℕhu:u ∈ ↑{M}v:ℕhv:v ∈ ↑{M}a✝:(fun x ↦ b) u = (fun x ↦ b) v⊢ u = v refine_1 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 ∣ bu:ℕhu:u ∈ ↑{M}v:ℕhv:v ∈ ↑{M}a✝:(fun x ↦ b) u = (fun x ↦ b) v⊢ u = v] at hu hvrefine_1 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 ∣ bu:ℕhu:u ∈ ↑{M}v:ℕhv:v ∈ ↑{M}a✝:(fun x ↦ b) u = (fun x ↦ b) v⊢ u = v
simp only [Finset.coe_singleton, Set.mem_singleton_iff] at hu hv refine_1 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 ∣ bu:ℕv:ℕa✝:(fun x ↦ b) u = (fun x ↦ b) vhu:u = Mhv:v = M⊢ u = v
exact hu.trans hv.symm All goals completed! 🐙
· refine_2 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 ∣ b⊢ ∀ a ∈ A, (fun x ↦ b) a ∈ window start (1 * M) ∧ a ∣ (fun x ↦ b) a intro a ha refine_2 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 ∈ A⊢ (fun x ↦ b) a ∈ window start (1 * M) ∧ a ∣ (fun x ↦ b) a
rw [hA refine_2 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 refine_2 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] at harefine_2 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
have hEq : a = M := Finset.mem_singleton.mp ha refine_2 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
subst a refine_2 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
simpa using And.intro hb hd 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}$.
@[category test, AMS 11]
theorem not_hasDistinctMultiples_two_three : ¬ HasDistinctMultiples {2, 3} 4 3 := by ⊢ ¬HasDistinctMultiples {2, 3} 4 3
rintro ⟨x, hinj, h⟩ x:ℕ → ℕhinj:Set.InjOn x ↑{2, 3}h:∀ a ∈ {2, 3}, x a ∈ window 4 3 ∧ a ∣ x a⊢ False
obtain ⟨h2w, h2d⟩ := h 2 (by x:ℕ → ℕhinj:Set.InjOn x ↑{2, 3}h:∀ a ∈ {2, 3}, x a ∈ window 4 3 ∧ a ∣ x a⊢ 2 ∈ {2, 3} x:ℕ → ℕhinj:Set.InjOn x ↑{2, 3}h:∀ a ∈ {2, 3}, x a ∈ window 4 3 ∧ a ∣ x ah2w:x 2 ∈ window 4 3h2d:2 ∣ x 2⊢ False simp All goals completed! 🐙 x:ℕ → ℕhinj:Set.InjOn x ↑{2, 3}h:∀ a ∈ {2, 3}, x a ∈ window 4 3 ∧ a ∣ x ah2w:x 2 ∈ window 4 3h2d:2 ∣ x 2⊢ False) x:ℕ → ℕhinj:Set.InjOn x ↑{2, 3}h:∀ a ∈ {2, 3}, x a ∈ window 4 3 ∧ a ∣ x ah2w:x 2 ∈ window 4 3h2d:2 ∣ x 2⊢ False
obtain ⟨h3w, h3d⟩ := h 3 (by x:ℕ → ℕhinj:Set.InjOn x ↑{2, 3}h:∀ a ∈ {2, 3}, x a ∈ window 4 3 ∧ a ∣ x ah2w:x 2 ∈ window 4 3h2d:2 ∣ x 2⊢ 3 ∈ {2, 3} x:ℕ → ℕhinj:Set.InjOn x ↑{2, 3}h:∀ a ∈ {2, 3}, x a ∈ window 4 3 ∧ a ∣ x ah2w:x 2 ∈ window 4 3h2d:2 ∣ x 2h3w:x 3 ∈ window 4 3h3d:3 ∣ x 3⊢ False simp All goals completed! 🐙 x:ℕ → ℕhinj:Set.InjOn x ↑{2, 3}h:∀ a ∈ {2, 3}, x a ∈ window 4 3 ∧ a ∣ x ah2w:x 2 ∈ window 4 3h2d:2 ∣ x 2h3w:x 3 ∈ window 4 3h3d:3 ∣ x 3⊢ False) x:ℕ → ℕhinj:Set.InjOn x ↑{2, 3}h:∀ a ∈ {2, 3}, x a ∈ window 4 3 ∧ a ∣ x ah2w:x 2 ∈ window 4 3h2d:2 ∣ x 2h3w:x 3 ∈ window 4 3h3d:3 ∣ x 3⊢ False
simp only [window, Finset.mem_Icc] at h2w h3w 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 + 3⊢ False
have h23 : x 2 = x 3 := by ⊢ ¬HasDistinctMultiples {2, 3} 4 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 3⊢ False omega 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 3⊢ False 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 3⊢ False
have := hinj (by 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 3⊢ 2 ∈ ↑{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 simp All goals completed! 🐙 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) (by 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 3⊢ 3 ∈ ↑{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 simp All goals completed! 🐙 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) h23 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
omega All goals completed! 🐙def erdos_709.answer : ℕ → ℝ := sorryLet $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 := by ⊢ f =Θ[atTop] erdos_709.answer
sorry 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 := by ⊢ ∃ c > 0, (fun n ↦ Real.log ↑n ^ c) =O[atTop] f
sorry 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 : ℝ) := by ⊢ f =O[atTop] fun n ↦ ↑n ^ (1 / 2)
sorry 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 := by ⊢ (fun n ↦ Real.log ↑n / Real.log (Real.log ↑n)) =O[atTop] f
sorry All goals completed! 🐙end Erdos709