Difference sets of sparse sets

DefinitionErdős Problem 899 on difference sets of sparse sets#✓fully proved

The proposition asserts the following for every infinite set \(A\) of natural numbers. Write \(A(N) = |A \cap \{1, \dots, N\}|\) for its counting function and \(D(N)\) for the number of integers \(d \in \{1, \dots, N\}\) of the form \(d = a - b\) with \(a, b \in A\). If \(A(N)/N \to 0\) as \(N \to \infty\), then \(\limsup_{N \to \infty} D(N)/A(N) = +\infty\).

The ratio \(D(N)/A(N)\) is computed in the extended reals and taken to be \(0\) when \(A(N) = 0\).

def conjecture : Prop :=
  ∀ (A : Set ℕ), A.Infinite →
    Tendsto (fun N => ((A ∩ Set.Icc 1 N).ncard : ℝ) / N) atTop (𝓝 0) →
    Filter.atTop.limsup (fun N => (((A - A : Set ℕ) ∩ Set.Icc 1 N).ncard : EReal) /
      ((A ∩ Set.Icc 1 N).ncard : EReal)) = ⊤

Used by 1

Used byRuzsa's theorem on difference sets of sparse sets

TheoremRuzsa's theorem on difference sets of sparse sets#●ready to prove

Let \(A\) be an infinite set of natural numbers whose counting function \(A(N) = |A \cap \{1, \dots, N\}|\) satisfies \(A(N)/N \to 0\) as \(N \to \infty\), and let \(D(N)\) be the number of integers \(d \in \{1, \dots, N\}\) of the form \(d = a - b\) with \(a, b \in A\). Then \(\limsup_{N \to \infty} D(N)/A(N) = +\infty\), where the ratio is computed in the extended reals and taken to be \(0\) when \(A(N) = 0\).

This answers Erdős Problem 899 affirmatively.

public theorem_wanted conjecture_holds : conjecture

Sources

• I. Z. Ruzsa, On the cardinality of A+A and A-A (1978), 933–938, https://mathscinet.ams.org/mathscinet-getitem?mr=519317.

Uses 1

Statement usesErdős Problem 899 on difference sets of sparse sets

1 fully proved1 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.