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

References:

@[expose] public sectionopen Filteropen scoped Pointwisenamespace Green65

An integer is a nonzero square if it is the square of a nonzero natural number.

def IsNonzeroSquare (d : ℤ) : Prop := ∃ n : ℕ, n ≠ 0 ∧ d = (n : ℤ) ^ 2

An integer is one less than a prime.

def IsPrimeMinusOne (d : ℤ) : Prop := ∃ p : ℕ, p.Prime ∧ d = (p : ℤ) - 1

There is a fixed density exponent $c > 0$ such that every sufficiently large subset $A \subseteq [N]$ with $|A| \geq N^{1-c}$ has a difference satisfying $P$.

We model $[N]$ as the integer interval ${1, \ldots, N}$ and use sufficiently large $N$, since the literal small-$N$ version is false for the nonzero-square question.

def LargeDifferencePattern (P : ℤ → Prop) : Prop := ∃ c : ℝ, 0 < c ∧ c < 1 ∧ ∀ᶠ N : ℕ in atTop, ∀ A : Finset ℤ, A ⊆ Finset.Icc 1 (N : ℤ) → (N : ℝ) ^ (1 - c) ≤ (A.card : ℝ) → ∃ d ∈ A - A, P d

Without "sufficiently large $N$" the question is false for every $c$: $A = {1} \subseteq [1]$ has $|A| = 1 = 1^{1-c}$ and $A - A = {0}$.

c:ℝh:∀ (N : ℕ), ∀ A ⊆ Finset.Icc 1 ↑N, ↑N ^ (1 - c) ≤ ↑A.card → ∃ d ∈ A - A, IsNonzeroSquare dd:ℤhd:d ∈ {1} - {1}n:ℕhn:n ≠ 0hdn:↑n ^ 2 = 0hd0:d = 0⊢ False c:ℝh:∀ (N : ℕ), ∀ A ⊆ Finset.Icc 1 ↑N, ↑N ^ (1 - c) ≤ ↑A.card → ∃ d ∈ A - A, IsNonzeroSquare dd:ℤhd:d ∈ {1} - {1}n:ℕhn:n ≠ 0hd0:d = 0hdn:n = 0⊢ False All goals completed! 🐙

Is there $c > 0$ such that every sufficiently large subset $A \subseteq [N]$ of size at least $N^{1-c}$ has a difference that is a nonzero square?

@[category research open, question, AMS 5 11] theorem green_65 : LargeDifferencePattern IsNonzeroSquare := ⊢ LargeDifferencePattern IsNonzeroSquare All goals completed! 🐙

Green asks the analogous question with a nonzero square replaced by $p - 1$ for a prime $p$. Green [Gr22, Theorem 1.1] solved this positively.

@[category research solved, question, AMS 5 11] theorem green_65.variants.prime_minus_one : LargeDifferencePattern IsPrimeMinusOne := ⊢ LargeDifferencePattern IsPrimeMinusOne All goals completed! 🐙end Green65