---
title: Erdos problems
lead: The open Erdos problems that are questions about digit designs, ranked by the odds of a checked result and by who reads them, and problem 124 attacked: sums of powers of several bases, where a bitset certificate makes each complete level a finite computation, every base set up to `10` with `sum 1/(d-1) > 1` and `gcd = 1` is certified at the first three levels, and the two-part route of the literature is proved unable to reach any base set below `sum 1/(d-1) = 2`.
figure: research-erdos
slug: erdos
---

A digit design is a set of integers whose base-`d` digits lie in a set `F`, and a surprising share of the open problems at [erdosproblems.com](https://www.erdosproblems.com) are statements about one, about a sumset of two in different bases, or about the carries that Kummer's theorem turns into divisibility. This page ranks those problems, then attacks the top one, problem 124, with the machinery of [Two bases](cobham.md): the sumset of designs across bases held as one bit array.

`lab/rs/mixed-powers` is the generator behind every number below.

## The objects

- `P(d, k)` is the set of sums of distinct powers `d^j` with `j >= k`, which is `d^k` times the base-`d` design `{0, 1}`.
- A base set is a finite `D = {d_1 < ... < d_r}` of integers `>= 3`; `M_k(D)` is the multiset of the powers `d_i^j`, `j >= k`, one copy per base, so `sum_i P(d_i, k)` is the set `FS(M_k(D))` of sums of distinct terms of `M_k(D)`.
- `sigma(D) = sum_i 1/(d_i - 1)` and `C_k(D) = sum_i d_i^k/(d_i - 1)`.
- `M_k(D)` is complete when `FS(M_k(D))` contains every large integer; `F(D, k)` is then the largest integer outside it.
- `a_1 <= a_2 <= ...` is `M_k(D)` sorted, `S_n = a_1 + ... + a_n`, and `P_n` the set of sums of distinct terms among the first `n`, a subset of `[0, S_n]` symmetric under `x -> S_n - x`.

## The ranked scouting table

Rank is the odds of a checked result in one sitting times the readership; status is the site's own; a problem this tree already carries is marked and not reopened.

| rank | problem | statement | site | the angle |
|---|---|---|---|---|
| 1 | [124](https://www.erdosproblems.com/124) | for `D` with `sigma(D) >= 1` and `gcd(D) = 1`, is `sum_i P(d_i, k)` cofinite for every `k >= 1`? | open | a sumset of scaled `{0, 1}` designs across bases; the surplus `sigma - 1` and a bitset certificate per level; attacked below |
| 2 | [817](https://www.erdosproblems.com/817) | least `N` with an `n`-set in `[1, N]` whose subset sums hold no 3-term progression; is it `>> 3^n`? | open | the powers of `3` give the base-3 design `{0, 1}`; admissible means the `{0, 1, 2}` digit sums are distinct, a base-3 numeration; the discussion thread reports `o(3^n)` and exact values to `n = 6`; `g_3(7) <= 474` below |
| 3 | [406](https://www.erdosproblems.com/406) | only finitely many powers of `2` lie in the base-3 design `{0, 1}`? | open | the orbit of `x -> 2x` against a base-3 design, a 3-adic carry automaton; the site records every digit present for `16 <= n <= 5.9 10^21`, past any census here |
| 4 | [376](https://www.erdosproblems.com/376) | infinitely many `n` with `binomial(2n, n)` prime to `105`? | open | carried: three designs at bases `3, 5, 7`, [Two bases](cobham.md) Object T, not reopened |
| 5 | [271](https://www.erdosproblems.com/271) | growth of the greedy sequences without 3-term progressions | open | `A(1)` is the base-3 design `{0, 1}`; which starts give a design, read as digit rules |
| 6 | [168](https://www.erdosproblems.com/168) | density of the largest subset of `[1, N]` with no `{n, 2n, 3n}` | open | a problem on the lattice of `2^a 3^b`, the two-base object of [Two bases](cobham.md) |
| 7 | [1146](https://www.erdosproblems.com/1146) | is `{2^m 3^n}` an essential component? | open | the same two-base lattice, against Schnirelmann density |
| 8 | [354](https://www.erdosproblems.com/354) | is `{floor(2^s alpha)} U {floor(2^t beta)}` complete for `alpha/beta` irrational? | open | two binary digit streams of `alpha` and `beta` summed with carries |
| 9 | [396](https://www.erdosproblems.com/396) | for every `k` an `n` with `(n - k) ... n` dividing `binomial(2n, n)`? | open | Kummer: each divisibility is a carry count of `n + n` in each base, a finite carry automaton per prime |
| 10 | [377](https://www.erdosproblems.com/377) | is the sum of `1/p` over `p <= n` not dividing `binomial(2n, n)` bounded? | open | `p` does not divide exactly when `n` lies in the base-`p` design of digits below `p/2`; a bound is a transversality of many designs |
| 11 | [1145](https://www.erdosproblems.com/1145) | `A + B` cofinite and `a_n/b_n -> 1` force an unbounded representation count? | open | the page's own example is two binary designs, even and odd digit places, the first family to test |
| 12 | [349](https://www.erdosproblems.com/349) | for which `t, alpha` is `floor(t alpha^n)` complete? | open | expansions in the non-integer base `alpha` |

Problem 125 is Object S of [Two bases](cobham.md) and stays there.

## Problem 124: what is in print

- The site states the question as above and credits Burr, Erdos, Graham and Li with the case `D = {3, 4, 7}`; their paper is not read here. The level `k = 0`, where every power `d^0 = 1` is allowed, is settled on the discussion thread by a Lean-checked proof through Brown's criterion `a_(n+1) <= S_n + 1`, read at source.
- The site records that `sigma(D) >= 1` is necessary, after Pomerance; the thread reconstructs the argument: by Dirichlet's simultaneous approximation, infinitely often every base has its least power `>= N` in `[N, beta N)`, and when `sigma(D) < 1` the terms below `N` then sum to less than `sigma(D) beta N < N`, so `N - 1` is no sum.
- [Bergelson and Simmons 2017](https://arxiv.org/abs/1507.02208), Theorem 1.23, read at source: the set of powers of `D` is strongly complete, complete after deleting any finite set, when `D` splits into four disjoint parts, three with `sigma >= 1` and one with `gcd = 1`; they write that they can neither prove nor disprove the conjecture. Strongly complete is complete at every `k`.
- [Fan 2026](https://arxiv.org/abs/2607.14071), Theorem 1.5, read at source: the same with two parts of `sigma >= 1` and one of `gcd = 1`, for finite `D` with no two elements powers of one integer. Both run through a criterion on disjoint infinite parts of the terms: two parts (Fan, Theorem 2.2) or three (Bergelson and Simmons, Main Theorem 2.1) with `Delta(B) = sup_(b in B) (b - sum_(b' in B, b' < b) b')` finite, plus one more part `C` with `sum_(c in C) norm(c theta) = infinity`, for every `theta` not in `Z` with `Delta(C)` finite or a countable `H_2(C)` (Fan), or for every irrational `theta` with `FS(C) + qZ = Z` for every `q` (Bergelson and Simmons), make the union complete. Main Theorem 2.1 as printed does not say its three parts are infinite, and read literally it fails: at `D = {5, 6}`, `k = 1`, the parts `{5}, {6}, {25}` meet (I), the rest of the powers meets (II) and (III), yet the sums of distinct powers number at most `x^(log_5 2 + log_6 2) < x^0.82` up to `x`; its proof and Fan's restatement use infinite parts, and so does this page.
- Both theorems are stated for the set of powers, where `(a^2)^n` and `a^(2n)` are one term, and exclude two elements powers of one integer; the site's question, a sum of one element of each `P(d_i, k)`, is the multiset `M_k(D)`, and this page certifies the multiset. The two differ on the cells where two bases are powers of one integer: `{3, 5, 6, 9}` at `k = 1` has `F = 22` as a multiset, while as a set `649` is no sum and every integer from `650` to `2 10^4` is (verbs `cell 3,5,6,9 1 20` and `set 3,5,6,9 1 20000`).
- The site page predates Fan's paper and records neither theorem. Fan's needs `sigma(D) > 2`, its third part being nonempty, and Bergelson and Simmons' `sigma(D) > 3`, so no theorem whose proof is read here settles a base set with `sigma(D) < 2`; the site's credit of `{3, 4, 7}`, where `sigma = 1`, rests on a paper not read here; the `103` base sets in `[3, 12]` minimal for `sigma > 1` and `gcd = 1` have `sigma` between `2311/2310` and `8/7` (verb `census 12 5 32 4`).

## The surplus certificate

- **Proved (the interval step).** If `P_n` contains `[T, S_n - T]` and `a_(m+1) <= S_m - 2T + 1` for every `m >= n`, then `FS(M_k(D))` contains every integer `>= T`. Proof: `P_(m+1) = P_m U (P_m + a_(m+1))` contains `[T, S_m - T] U [T + a_(m+1), S_(m+1) - T]`, one interval exactly when `T + a_(m+1) <= S_m - T + 1`, and `S_m -> infinity`. At `k = 0`, `T = 0` is Brown's criterion.
- **Proved (the surplus**, the per-part computation of Bergelson and Simmons' Section 2.7, repeated in Fan's Section 7**).** For every `n`, `S_n - a_(n+1) >= (sigma(D) - 1) a_(n+1) - C_k(D)`. Proof: `P_n` holds every term below `X = a_(n+1)`, and for each base those are `d^j` with `k <= j < J`, `d^J >= X` the least power `>= X` with `J >= k`, summing to `(d^J - d^k)/(d - 1) >= (X - d^k)/(d - 1)`.
- **Proved (the certificate).** Let `sigma(D) > 1` and `k >= 1`. If for some `n` the integer `T = 1 + max{x <= S_n/2 : x not in P_n}` satisfies `T <= a_(n+1)`, and `a_(m+1) <= S_m - 2T + 1` holds for every `m >= n` with `(sigma(D) - 1) a_(m+1) < C_k(D) + 2T - 1`, then `M_k(D)` is complete and `F(D, k) = T - 1` exactly. Proof: past that finite range the surplus gives the step, so the interval step applies; and `T - 1 < a_(n+1)` is a sum of distinct terms only of terms below `a_(n+1)`, all in `P_n`, where it is missing. The check is finite and exact: integer arithmetic with `sigma` and `C_k` over the common denominator of the `d_i - 1`.
- **Proved (exact in the gap).** If `1 < sigma(D) < 2`, then `M_k(D)` is complete if and only if the certificate exists at some `n`, so the search halts exactly on the complete levels and a level left open is open only for the cap. Proof: fix `beta > 1` with `sigma(D) beta < 2`; Dirichlet's simultaneous approximation gives arbitrarily large exponents with one power of every base, all within a factor `beta < 3` of one another, and with `N` the least of them (Fan, footnote 1) `N` is a term and the least power `>= N` of every base lies in `[N, beta N)`; at the first copy `a_(n+1) = N` the terms below `N` sum to `S_n < sigma(D) beta N < 2 a_(n+1)`; then every `x <= S_n/2` is a sum of distinct terms below `a_(n+1)` or of none, so `P_n` and `FS(M_k(D))` agree on `[0, S_n/2]`, the certificate reads `T = F(D, k) + 1`, and for `N` large the surplus clause is empty.
- **Proved (monotone).** Completeness at `(D, k)` gives completeness at `(D', k')` for every base set `D'` containing `D` and every `k' <= k`, since `M_k'(D')` contains `M_k(D)` as a multiset. So the census below needs only the base sets that are minimal for `sigma > 1` and `gcd = 1`, each at its deepest certified level.

## The two-part route is dead below two

- **Proved.** Let `D` be finite with `sigma(D) < 2` and `k >= 0`. Then no two disjoint infinite sub-multisets `B_1, B_2` of `M_k(D)` have both `Delta(B_1)` and `Delta(B_2)` finite, whatever becomes of the other terms. Proof: take `N` as in the gap proof above, so the terms below `N` sum to less than `sigma(D) beta N`, and let `b_i` be the least term of `B_i` that is `>= N`; the terms of `B_i` below `b_i` are those below `N`, so `Delta(B_1) + Delta(B_2) >= b_1 + b_2 - sigma(D) beta N >= (2 - sigma(D) beta) N`, unbounded in `N`.
- So Fan's Theorem 2.2, which needs two such parts, and Bergelson and Simmons' Main Theorem 2.1, which needs three, apply to no `M_k(D)` with `sigma(D) < 2` under any partition of the terms, not only the partitions by bases; the whole of `M_k(D)` has `Delta` finite once `sigma(D) >= 1`, and the obstruction is the second part. The syndetic-pair method cannot enter the gap `1 <= sigma(D) < 2` at all.
- **Verified** (verb `route 10 12`, under `0.01` s): for each of the `30` minimal base sets below `11`, the least value of `sum(M_1(D) below N)/N` over terms `N` in `[10^12, 10^30]` lies in `[1.105953, 1.537469]`, truncated, so at that `N` any two disjoint parts of the terms have one with `Delta >= 0.23 N`: the clusters the proof uses are already visible at twelve digits.

## The census

- **Verified** (verb `census 10 5 32 4`, `2.9` s on `4` threads, a `2^32`-bit array per cell): there are `30` base sets in `[3, 10]` minimal for `sigma > 1` and `gcd = 1`, and each is certified, as the multiset `M_k(D)`, at `k = 1, 2, 3`, twenty-one also at `k = 4` and five of those at `k = 5`. By the monotone lemma, every base set `D` in `[3, 10]` with `sigma(D) > 1` and `gcd(D) = 1` has `sum_i P(d_i, k)` cofinite for `k = 1, 2, 3`.
- **Verified** (verbs `census 12 5 32 4`, `8.7` s, and `cell 3,6,9,10,12 2 34`, `1.3` s): the `103` minimal base sets in `[3, 12]` are all certified at `k = 1, 2`; the last one, `{3, 6, 9, 10, 12}`, whose only base prime to `3` is `10`, needs a `2^34`-bit array at `k = 2` and has `F = 1473914231`. So every base set in `[3, 12]` with `sigma > 1` and `gcd = 1` is cofinite at `k = 1, 2`.
- **Verified** (verbs `census 10 5 32 4` and `cell 3,4,5 4 34`, `1.0` s): `F({3, 4, 5}, k)` reads `79, 77613, 4330731, 1075364603` at `k = 1..4`, with `11, 1128, 45704, 1785062` positive integers up to `F` that are no sum; `F({3, 4, 6}, k)` reads `986, 242113, 58941162` at `k = 1..3`, and `k = 4` is not certified within a `2^34`-bit array.
- **Verified** (verb `control`, `0.9` s): on nine cells, `{3, 4, 5}` at `k = 1, 2, 3` among them, a plain knapsack over every term up to `4 F` returns the same `F` and the same count of missing integers as the certificate, and `{3, 6, 9, 12, 15, 21}`, with `sigma > 1` and `gcd = 3`, never certifies below `2^24`.
- The one base set in `[3, 12]` with `sigma = 1` and `gcd = 1` is `{3, 4, 7}`, the case the site credits to Burr, Erdos, Graham and Li; `{3, 5, 7, 13}` is the next. There the surplus is zero, the step at a term `X` holds only if the other bases keep their next powers far from `X`, and the surplus clause of the certificate never empties, so the census does not reach that tail; the discussion thread names a lower bound on `abs(d^a - e^b)` of Baker type as the least it needs.
- The thresholds climb steeply with `k`, from `79` to `1075364603` over four levels at `{3, 4, 5}`, which is why no finite census reaches strong completeness: the certificate proves one level at a time.

## The missing lemma

- Linear surplus means `S_n - a_(n+1) >= eps a_(n+1) - C` for all `n`, some `eps > 0` and a constant `C`; `H_1(M)` is the set of `theta` in `R/Z` with `sum_(a in M) norm(a theta) < infinity`, Fan's `H_1`-spectrum. Every `M_k(D)` with `sigma(D) > 1` and `gcd(D) = 1` has both properties, `eps = sigma(D) - 1` by the surplus lemma and `H_1 = {0}` by Fan's Section 7 argument applied base by base, so the lemma L, that linear surplus and `H_1(M) = {0}` make a multiset complete, would settle problem 124 above `sigma = 1`.
- **Refuted.** L is false. Witness: `A = {2 F_m - 1 : m >= 2} = 1, 3, 5, 9, 15, 25, 41, ...`, `F_m` the Fibonacci numbers, so `a_(n+1) = a_n + a_(n-1) + 1`. Surplus: `S_n = 2 F_(n+3) - 4 - n`, so `S_n - a_(n+1) = a_n - n - 2 >= a_(n+1)/2 - n - 5/2`, and `a_n` grows geometrically, so `eps = 1/4` works with a constant `C`. Spectrum: if `theta` is in `H_1(A)`, then `norm(a_n theta) -> 0` and `norm(theta) <= norm(a_(n+1) theta) + norm(a_n theta) + norm(a_(n-1) theta) -> 0`. Incomplete: by the window below, `a_(n+2) - S_n = n + 3` opens a window at every `n`, and `a_(m+1) >= a_m + a_(m-1)` puts the upper window `(S_(n-2), a_n)` inside the lower window of step `n`, so the non-sum `2`, in the upper windows `(0, 3)` and `(1, 5)`, recurs in every window.
- **Verified** (verb `refute 27`, under `0.1` s, pinned by a crate test): the `38` terms of `A` up to `2^27` open `36` windows, every one holding a non-sum; the least of `2 (S_n - a_(n+1)) - a_(n+1)` is `-9`; the `25` non-sums below `10^6` are the two chains `2, 7, 22, 63, 172, ...` and `2, 11, 36, 103, 280, ...`.
- **Proved (the window).** If `a_(n+2) > S_n`, the sums in `(S_n, a_(n+2))` are exactly `a_(n+1) + (P_n meet (S_n - a_(n+1), a_(n+2) - a_(n+1)))`: such an `x` uses only terms below `a_(n+2)`, and exceeds the sum of all terms before `a_(n+1)`, so it uses `a_(n+1)`. An integer of the lower window missing from `P_n` is carried to a non-sum in the upper one.
- **Proved (surplus does not heal).** The set `a_n = floor(2 (5/3)^n)`, `n >= 1`, has `S_n - a_(n+1) >= a_(n+1)/2 - n - 5`, which is linear surplus since `a_(n+1)` grows geometrically, and is incomplete. Proof: `a_(n+2) >= (50/9)(5/3)^n - 1 > 5 (5/3)^n - 5 >= S_n` opens a window at every `n`; `a_(m+1) - a_m - a_(m-1) >= (2/9)(5/3)^(m-1) - 1 > 0` for `m >= 4` puts the upper window `(S_(n-2), a_n)` inside the lower window of step `n`; a non-sum `h` there is missing from `P_n`, since `h < a_n`, so `a_(n+1) + h` is a non-sum, and one seed recurs in every other window. This is Graham's incompleteness for `t > 1`, `alpha >= max(2/t, phi)` as Fan quotes it, reproved at one point; whether its `H_1` is `{0}` is open, of the kind the site's problem 349 names when it asks whether `floor((3/2)^n)` is odd or even infinitely often.
- **Verified** (verb `graham 2 5 3 26`, under `0.1` s): the `33` terms of `floor(2 (5/3)^n)` up to `2^26` open `31` windows and every one holds a non-sum; the largest non-sum up to `2^25` is `23559582`.
- **Verified** (verb `windows`, under `0.01` s each): the power multisets run no chain. Over the terms in `[10^6, 10^30]`, `M_k({3, 4, 5})` opens a window at `27` of `123` terms at each `k = 1..4`, `M_1({3, 4, 6})` at `41` of `120`, `M_1({3, 5, 6, 7})` at `5` of `142`, and in all six no upper window `(S_m, a_(m+2))` meets the lower window `(S_n - a_(n+1), a_(n+2) - a_(n+1))` of a later open window.
- No linear-forms bound enters at `sigma > 1`: the surplus clause of the certificate closes by `(sigma - 1) a_(m+1) >= C_k + 2T - 1` alone, so Baker, Matveev or Laurent can only serve the `sigma = 1` cells. What changes with `k` is the base interval `[T, S_n - T]`, whose scale climbs from `a_n = 243` at `k = 1` to `3486784401` at `k = 4` for `{3, 4, 5}`, and `k = 5` passes a `2^34`-bit array (verb `cell 3,4,5 5 34`).

## Problem 817 at n = 7

- `g_3(n)` is the least `N` such that `[1, N]` holds an `n`-set `A` whose subset sums `<A>`, `0` included, contain no non-trivial 3-term progression; on the discussion thread, read at source, Korsky proves this equivalent to the `3^n` sums `sum c_i a_i`, `c_i` in `{0, 1, 2}`, being distinct, an admissible set, and the lower bound `(T_n - 1)/2 + sum_(j < n) T_j`, `T_j` the central trinomial coefficient, `419` at `n = 7`; a later post gives `g_3(n + 1) <= 3 g_3(n)` through `A -> {1} U 3A`, exact values `1, 3, 8, 22, 60, 168` to `n = 6` by exhaustive search, and `419 <= g_3(7) <= 504`. The powers of `3` are the base-3 design `{0, 1}`, admissible at every `n` and optimal only to `n = 2`.
- The search picks the elements from the top down with the ternary sums as one bit array: `a` extends a set `H` exactly when `a` and `2a` avoid the differences of its sums, the `r` elements still owed lie below the least chosen one, which must exceed `g_3(r)`, and the variance `(2/3) sum a_i^2` of a uniform ternary sum is at least that of `3^n` distinct integers, `sum a_i^2 >= (9^n - 1)/8`.
- **Verified** (verb `ternary 6 200 8`, `5.9` s on `8` threads, exhaustive): `g_3(n) = 1, 3, 8, 22, 60, 168` at `n = 1..6`, the thread's values, each `g_3(r)` of the pruning computed by the run before it; the witness at `n = 6` is `{107, 145, 159, 162, 164, 168}`, a second extremal set beside the thread's `{107, 145, 159, 162, 166, 168}`.
- **Verified** (verb `band 419 475 70 8`, `2.8` s): `A = {302, 409, 447, 459, 465, 466, 474}` is admissible, its `2187` ternary sums distinct and its `128` subset sums free of 3-term progressions, checked from the definition; so `g_3(7) <= 474`, past the thread's `504`, and with the thread's step `g_3(n) <= 474 3^(n - 7)` for `n >= 7`, `g_3(n)/3^n < 0.216736` against the thread's `0.2305`.
- **Verified** (verb `band 419 473 100 8`, `114` s): no admissible 7-set with largest element `N` in `[419, 473]` has its six largest elements in `[N - 100, N]`, so a set beating `474` has a second-smallest element below `N - 100`, unlike every extremal set printed on the thread or here; the families `{0, 1, 3, 8, 22, 60}` and `{0, 2, 6, 9, 23, 61}` of offsets from the top plus one free offset reach `477` and `475` at best (verb `offsets 420 504`).
- The exact value is a wall at this budget: the unrestricted search costs `36` s at `N = 380` alone (verb `probe 7 380 8`) and grows about fourfold per `20`, so `[419, 473]` wants hours on eight cores; it needs Korsky's bandwidth bound or a window-density bound inside the search, not a solver install.

## What stays open

- **Conjecture.** `M_k({3, 4, 5})` is complete at every `k`, the least base set outside every theorem whose proof is read here; checked at `k <= 4` with no derivation. A proof has to hold uniformly in `k`, while the only uniform tool read here, the two-part criterion, is dead below `sigma = 2`.
- The live target is L with the window chain excluded: linear surplus, `H_1(M) = {0}`, and for all large `m < n` the upper window of `m` missing the lower window of `n`. Both witnesses against L run a chain at every step, and the power multisets run none in the range read; at `sigma = 1` the surplus is `-C` and `{3, 4, 7}` stays apart.