Admissible sets with no prime translate

TheoremSparse admissible sets without prime translates (Erdős Problem 429)#●ready to prove

For every function \(f : \mathbb{N} \to \mathbb{N}\) with \(f(N) \to \infty\) as \(N \to \infty\), there is an infinite set \(A\) of natural numbers such that \(|A \cap \{1, \ldots, N\}| \le f(N)\) for every natural number \(N\), for every prime \(p\) some residue class modulo \(p\) contains no element of \(A\), and for every integer \(n\) some \(a \in A\) makes \(n + a\) not a positive prime.

Resolved false: Disproved by Weisenberg (2024); ported as a formal statement. Source: D. Weisenberg, Sparse Admissible Sets and a Problem of Erdős and Graham, Integers (2024). Moved from OpenConjectures/NumberTheory/ErdosProblem429.

public theorem_wanted erdos429_refuted : ¬ erdos429

TheoremSparse subsets of powers with no prime translate#●ready to prove

Let \(a\) be a natural number that is a primitive root modulo infinitely many primes, and let \(S = \{a^k : k \ge 1\}\). For every non-decreasing unbounded function \(f : \mathbb{N} \to \mathbb{N}\) there is an infinite set \(A \subseteq S\) such that \(|A \cap \{1, \dots, N\}| \le f(N)\) for every natural number \(N\), and such that no translate \(A + n\) with \(n \in \mathbb{Z}\) consists entirely of (positive) primes.

The hypothesis forces \(a \ge 2\). The exponent range \(k \ge 1\) is the reading in which the paper's remark "\(S\) is admissible" holds: with \(k = 0\) and \(a\) even, \(S\) contains \(1\) and \(a\), which meet both residue classes modulo \(2\).

public theorem_wanted exists_sparse_subset_pow_no_prime_translate {a : ℕ}
    (hprim : {p : ℕ | p.Prime ∧ IsPrimitiveRoot (a : ZMod p) (p - 1)}.Infinite)
    {f : ℕ → ℕ} (hmono : Monotone f) (hunb : ∀ M : ℕ, ∃ N : ℕ, M ≤ f N) :
    ∃ A : Set ℕ, A.Infinite ∧ A ⊆ {m | ∃ k : ℕ, 1 ≤ k ∧ m = a ^ k} ∧
      (∀ N : ℕ, (A ∩ Set.Icc 1 N).ncard ≤ f N) ∧
      ¬ ∃ n : ℤ, ∀ m ∈ A, ∃ p : ℕ, p.Prime ∧ (p : ℤ) = m + n

Sources

• Desmond Weisenberg, Sparse Admissible Sets and a Problem of Erdős and Graham, INTEGERS 24 (2024), Article A89, Theorem 1.

2 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.