Erdős Problem 124

References:

• erdosproblems.com/124
• [BEGL96] Burr, S. A. and Erdős, P. and Graham, R. L. and Li, W. Wen-Ching, Complete sequences of sets of integer powers. Acta Arith. (1996), 133-138.

def Erdos124.sumsOfDistinctPowers (d k : ℕ) : Set ℕ

The set of integers which are the sum of distinct powers d ^ i with i ≥ k.

Equations

• Erdos124.sumsOfDistinctPowers d k = {x : ℕ | ∃ (s : Finset ℕ), (∀ i ∈ s, k ≤ i) ∧ ∑ i ∈ s, d ^ i = x}

theorem Erdos124.erdos124.zero : True ↔ ∀ (D : Finset ℕ), (∀ d ∈ D, 3 ≤ d) → 1 ≤ ∑ d ∈ D, (↑d - 1)⁻¹ → ∀ᶠ (n : ℕ) in Filter.atTop, n ∈ ∑ d ∈ D, sumsOfDistinctPowers d 0

Let $3 \le d_1 < d_2 < \dots < d_r$ be integers such that $$\sum_{1 \le i \le r}\frac 1{d_i - 1} \ge 1.$$ Can all sufficiently large integers be written as a sum of the shape $\sum_i c_ia_i$ where $c_i \in \{0, 1\}$ and $a_i$ has only the digits $0, 1$ when written in base $d_i$?

Conjectured by Erdős [Er97], solved by Boris Alexeev using Aristotle.

theorem Erdos124.erdos124.ne_zero : True ↔ ∀ (k : ℕ), k ≠ 0 → ∀ (D : Finset ℕ), (∀ d ∈ D, 3 ≤ d) → 1 ≤ ∑ d ∈ D, (↑d - 1)⁻¹ → D.gcd id = 1 → ∀ᶠ (n : ℕ) in Filter.atTop, n ∈ ∑ d ∈ D, sumsOfDistinctPowers d k

Let $k \ne 0$ and $3\leq d_1 < d_2 < \cdots < d_r$ be integers of gcd equal to $1$ such that $$\sum_{1 \le i \le r}\frac 1{d_i - 1} \ge 1.$$ Can all sufficiently large integers be written as a sum of the shape $\sum_i c_ia_i$ where $c_i \in \{0, 1\}$ and $a_i$ is divisible by $d_i ^ k$ and has only the digits $0, 1$ when written in base $d_i$?

Conjectured by Burr, Erdős, Graham, and Li [BEGL96]

theorem Erdos124.erdos124.ne_zero_three_four_seven {k : ℕ} (hk : k ≠ 0) : ∀ᶠ (n : ℕ) in Filter.atTop, n ∈ sumsOfDistinctPowers 3 k + sumsOfDistinctPowers 4 k + sumsOfDistinctPowers 7 k

All sufficiently large integers can be written as $a + b + c$ where $a$ has only the digits $0, 1$ in base $3$, $b$ only the digits $0, 1$ in base $4$, $c$ only the digits $0, 1$ in base $7$.

Provee by Burr, Erdős, Graham, and Li [BEGL96]

theorem Erdos124.erdos124.converse {D : Finset ℕ} (hD₃ : ∀ d ∈ D, 3 ≤ d) (h : ∀ᶠ (n : ℕ) in Filter.atTop, n ∈ ∑ d ∈ D, sumsOfDistinctPowers d 0) : 1 ≤ ∑ d ∈ D, (↑d - 1)⁻¹

Let $3\leq d_1 < d_2 < \cdots < d_r$ be integers such that all sufficiently large integers can be written as a sum of the shape $\sum_i c_ia_i$ where $c_i \in \{0, 1\}$ and $a_i$ has only the digits $0, 1$ when written in base $d_i$. Then $$\sum_{1 \le i \le r}\frac 1{d_i - 1} \ge 1.$$

Reported by Burr, Erdős, Graham, and Li [BEGL96] as an observation of Pomerance

theorem Erdos124.erdos124.melfi_construction {ε : ℝ} (hε : 0 < ε) : ∃ (d : ℕ → ℕ), StrictMono d ∧ ∑' (i : ℕ), (↑(d i) - 1)⁻¹ ≤ ε ∧ ∀ᶠ (n : ℕ) in Filter.atTop, ∃ (I : Finset ℕ) (a : ℕ → ℕ), (∀ i ∈ I, a i ∈ sumsOfDistinctPowers (d i) 0) ∧ ∑ i ∈ I, a i = n

For any $\varepsilon > 0$, there exists an infinite sequence $2 \le d_0 < d_1 < \dots$ such that all sufficiently large integer can be written as $\sum_{i \in I} a_i$ where $a_i$ has only the digits $0, 1$ when written in base $d_i$, but $\sum_{i \in I} \frac 1{d_i - 1} \le \varepsilon$.

Proved by Melfi [Me04]