/-
Copyright 2025 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 319
Reference: erdosproblems.com/319
@[expose] public sectionopen Filteropen scoped Topology Finset Realnamespace Erdos319def erdos_319.answer : ℕ := sorryWhat is the size of the largest $A\subseteq{1, \dots, N}$ such that there is a function $\delta : A \to {-1, 1}$ such that $$ \sum_{n\in A} \frac{\delta n}{n} = 0 $$ and $$ \sum_{n\in A'}\frac{\delta n}{n} \neq 0 $$ for all non-empty $A'\subsetneq A$.
@[category research open, question value, AMS 5]
theorem erdos_319 (N : ℕ) : IsGreatest
{ #A | (A) (_ : A ⊆ Finset.Icc 1 N)
(_ : ∃ δ : ℕ → ℤˣ, ∑ n ∈ A, (δ n : ℚ) / n = 0 ∧
∀ A' ⊂ A, A'.Nonempty → ∑ n ∈ A', (δ n : ℚ) / n ≠ 0) }
erdos_319.answer := N:ℕ⊢ IsGreatest
{x |
∃ A,
∃ (_ : A ⊆ Finset.Icc 1 N) (_ :
∃ δ, ∑ n ∈ A, ↑↑(δ n) / ↑n = 0 ∧ ∀ A' ⊂ A, A'.Nonempty → ∑ n ∈ A', ↑↑(δ n) / ↑n ≠ 0), #A = x}
erdos_319.answer
All goals completed! 🐙-- Formalisation note: it's possible that solution to `erdos_319` needs to be
-- expressed asymptotically. To handle this we include an `IsTheta` variant below.
def erdos_319.variants.isTheta.answer : ℕ → ℝ := fun N ↦ (N : ℝ)Let $c(N)$ be the size of the largest $A\subseteq{1, \dots, N}$ such that there is a function $\delta : A \to {-1, 1}$ such that $$ \sum_{n\in A} \frac{\delta n}{n} = 0 $$ and $$ \sum_{n\in A'}\frac{\delta n}{n} \neq 0 $$ for all non-empty $A'\subsetneq A$. What is $\Theta(c(N))$?
Trivially $c(N) \leq N$, and erdos_319.variants.lb gives $c(N) \geq (1 - \frac{1}{e} + o(1))N$,
so $c(N) = \Theta(N)$.
@[category research solved, question value, AMS 5]
theorem erdos_319.variants.isTheta (N : ℕ) (c : ℕ → ℝ)
(h : ∀ N, IsGreatest
{ (#A : ℝ) | (A) (_ : A ⊆ Finset.Icc 1 N)
(_ : ∃ δ : ℕ → ℤˣ, ∑ n ∈ A, (δ n : ℚ) / n = 0 ∧
∀ A' ⊂ A, A'.Nonempty → ∑ n ∈ A', (δ n : ℚ) / n ≠ 0) } (c N)) :
c =Θ[atTop] erdos_319.variants.isTheta.answer := N:ℕc:ℕ → ℝh:∀ (N : ℕ),
IsGreatest
{x |
∃ A,
∃ (_ : A ⊆ Finset.Icc 1 N) (_ :
∃ δ, ∑ n ∈ A, ↑↑(δ n) / ↑n = 0 ∧ ∀ A' ⊂ A, A'.Nonempty → ∑ n ∈ A', ↑↑(δ n) / ↑n ≠ 0), ↑(#A) = x}
(c N)⊢ c =Θ[atTop] isTheta.answer
All goals completed! 🐙Adenwalla has observed that a lower bound (on the maximum size of $A$) of $$ |A| \geq (1 - \frac{1}{e} + o(1))N $$ follows from the main result of Croot [Cr01].
[Cr01] Croot, III, Ernest S., On unit fractions with denominators in short intervals. Acta Arith. (2001), 99-114.
@[category research solved, AMS 5]
theorem erdos_319.variants.lb : ∃ (o : ℕ → ℝ), (o =o[atTop] (1 : ℕ → ℝ)) ∧
∀ᶠ N in atTop, (1 - 1 / rexp 1 + o N) * N ≤ sSup { (#A : ℝ) | (A) (_ : A ⊆ Finset.Icc 1 N)
(_ : ∃ δ : ℕ → ℤˣ, ∑ n ∈ A, (δ n : ℚ) / n = 0 ∧
∀ A' ⊂ A, A'.Nonempty → ∑ n ∈ A', (δ n : ℚ) / n ≠ 0) } := ⊢ ∃ o,
o =o[atTop] 1 ∧
∀ᶠ (N : ℕ) in atTop,
(1 - 1 / rexp 1 + o N) * ↑N ≤
sSup
{x |
∃ A,
∃ (_ : A ⊆ Finset.Icc 1 N) (_ :
∃ δ, ∑ n ∈ A, ↑↑(δ n) / ↑n = 0 ∧ ∀ A' ⊂ A, A'.Nonempty → ∑ n ∈ A', ↑↑(δ n) / ↑n ≠ 0), ↑(#A) = x}
All goals completed! 🐙end Erdos319