Erdos problems

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 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: 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.

Problem 125 is Object S of Two bases 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, 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, 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.