/- 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

Ben Green's Open Problem 37

What is the smallest subset of ℕ containing, for each d = 1, …, N, an arithmetic progression of length k with common difference d?

References:

@[expose] public sectionnamespace Green37open Set Filteropen scoped Asymptotics

A contains an arithmetic progression of length k and common difference d for every d ∈ {1, …, N}.

def IsAPCover (A : Set ℕ) (N k : ℕ) : Prop := ∀ d, 1 ≤ d ∧ d ≤ N → Set.ContainsAP A k d

The minimum size of a subset of ℕ that contains, for each d = 1, …, N, an arithmetic progression of length k with common difference d.

noncomputable def m (N k : ℕ) : ℕ := sInf { m | ∃ A : Finset ℕ, A.card = m ∧ IsAPCover (A : Set ℕ) N k }def green_37.answer : ℕ → ℕ → ℕ := sorry

Given a natural number N, what is the smallest size of a subset of ℕ that contains, for each d = 1, …, N, an arithmetic progression of length k with common difference d.

@[category research open, question value, AMS 5 11] theorem green_37 (N k : ℕ) : IsLeast { m | ∃ A : Finset ℕ, A.card = m ∧ IsAPCover (A : Set ℕ) N k } (green_37.answer N k) := N:ℕk:ℕ⊢ IsLeast {m | ∃ A, A.card = m ∧ IsAPCover (↑A) N k} (green_37.answer N k) All goals completed! 🐙def green_37_asymptotic.answer : ℕ → ℕ → ℝ := sorry

Asymptotic version: determine the asymptotic behavior of m(N, k) as N grows. The solver should determine a function f : ℕ → ℕ → ℝ such that, for each k, f k eventually equals (fun N ↦ (m N k : ℝ)).

@[category research open, question value, AMS 5 11] theorem green_37_asymptotic (k : ℕ) : ∀ᶠ N in atTop, (m N k : ℝ) = green_37_asymptotic.answer k N := k:ℕ⊢ ∀ᶠ (N : ℕ) in atTop, ↑(m N k) = green_37_asymptotic.answer k N All goals completed! 🐙def green_37_theta.answer : ℕ → ℕ → ℝ := sorry

Determine, for each k, the asymptotic equivalence class (theta) of m(N, k) as N grows.

@[category research open, question value, AMS 5 11] theorem green_37_theta (k : ℕ) : (fun N ↦ (m N k : ℝ)) =Θ[atTop] green_37_theta.answer k := k:ℕ⊢ (fun N ↦ ↑(m N k)) =Θ[atTop] green_37_theta.answer k All goals completed! 🐙

The interval {0, …, kN} contains, for each d = 1, …, N, the arithmetic progression {0, d, …, (k - 1)d}, so m(N, k) ≤ kN + 1.

All goals completed! 🐙 N:ℕk:ℕd:ℕhd:1 ≤ d ∧ d ≤ N⊢ ↑(Finset.image (fun i ↦ i * d) (Finset.range k)) = {x | ∃ n, ∃ (_ : ↑n < ↑k), 0 + n • d = x} N:ℕk:ℕd:ℕhd:1 ≤ d ∧ d ≤ Nx:ℕ⊢ x ∈ ↑(Finset.image (fun i ↦ i * d) (Finset.range k)) ↔ x ∈ {x | ∃ n, ∃ (_ : ↑n < ↑k), 0 + n • d = x}; All goals completed! 🐙

Writing F_k(N) for m(N, k), Green conjectures that F_k(N) ≫_k N^(1 - c_k) for some sequence c_k with c_k → 0 as k → ∞. The restriction to 0 < k excludes the degenerate case m(N, 0) = 0.

@[category research open, AMS 5 11] theorem green_37_lower_bound : ∃ c : ℕ → ℝ, Tendsto c atTop (nhds 0) ∧ ∀ k, 0 < k → (fun N : ℕ ↦ (N : ℝ) ^ (1 - c k)) =O[atTop] fun N ↦ (m N k : ℝ) := ⊢ ∃ c, Tendsto c atTop (nhds 0) ∧ ∀ (k : ℕ), 0 < k → (fun N ↦ ↑N ^ (1 - c k)) =O[atTop] fun N ↦ ↑(m N k) All goals completed! 🐙end Green37