Erdos problems

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.

rankproblemstatementsitethe angle
1124for D with sigma(D) >= 1 and gcd(D) = 1, is sum_i P(d_i, k) cofinite for every k >= 1?opena sumset of scaled {0, 1} designs across bases; the surplus sigma - 1 and a bitset certificate per level; attacked below
2817least N with an n-set in [1, N] whose subset sums hold no 3-term progression; is it >> 3^n?openthe 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
3406only finitely many powers of 2 lie in the base-3 design {0, 1}?openthe 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
4376infinitely many n with binomial(2n, n) prime to 105?opencarried: three designs at bases 3, 5, 7, Two bases Object T, not reopened
5271growth of the greedy sequences without 3-term progressionsopenA(1) is the base-3 design {0, 1}; which starts give a design, read as digit rules
6168density of the largest subset of [1, N] with no {n, 2n, 3n}opena problem on the lattice of 2^a 3^b, the two-base object of Two bases
71146is {2^m 3^n} an essential component?openthe same two-base lattice, against Schnirelmann density
8354is {floor(2^s alpha)} U {floor(2^t beta)} complete for alpha/beta irrational?opentwo binary digit streams of alpha and beta summed with carries
9396for every k an n with (n - k) ... n dividing binomial(2n, n)?openKummer: each divisibility is a carry count of n + n in each base, a finite carry automaton per prime
10377is the sum of 1/p over p <= n not dividing binomial(2n, n) bounded?openp 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
111145A + B cofinite and a_n/b_n -> 1 force an unbounded representation count?openthe page's own example is two binary designs, even and odd digit places, the first family to test
12349for which t, alpha is floor(t alpha^n) complete?openexpansions in the non-integer base alpha

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}. Burr, Erdos, Graham and Li 1996, read at source, state the conjecture for Pow(A; s), the nondecreasing sequence formed from all the powers a^k, a in A, k >= s >= 1, which, called nondecreasing, reads as the multiset M_s(A), though Claim 1 writes it strictly increasing; their Theorem 1 gives, for A of positive upper density with gcd = 1, a finite A' in A with Pow(A'; s) complete, through a gap bound 2 b_N^(s+1) for the sums of Pow(B; s) when sum 1/b_i > 2 and Szemeredi's theorem. Of {3, 4, 7} they state, without printing the argument, that the bound of Mignotte and Waldschmidt on abs(3^p - 4^q) lets them show it complete at s = 1, largest missing integer 581, and they print the largest missing integers 111, 16 and 78 for {3, 5, 7, 13}, {3, 6, 7, 13, 21} and {3, 4, 5} at s = 1. A plain knapsack to 2 10^6 reads 581 for {3, 4, 7}, as they do, but 112, 17 and 79 for the other three, and 111 = 81 + 27 + 3, 16 = 9 + 7, 78 = 64 + 9 + 5 are sums (verb set; 79 is also the certificate's F). 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 an argument at the one level k = 1 that the paper states but does not print; 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.
  • Proved (the wide certificate). Fix W, let B_n = P_n meet [0, W] and let H_n be the integers of (W, S_n/2] missing from P_n, so that B_n, H_n and the symmetry give all of P_n. Then B_(n+1) = B_n U ((B_n meet [0, W - a_(n+1)]) + a_(n+1)), and every integer of (W, S_(n+1)/2] missing from P_(n+1) lies in H_n, in S_n - H_n, in S_n - ([0, W] minus B_n) or above S_n, and such a candidate z is missing from P_(n+1) exactly when z - a_(n+1) is missing from P_n. Proof: P_(n+1) = P_n U (P_n + a_(n+1)), so z is missing from P_(n+1) exactly when z and z - a_(n+1) are missing from P_n; for z <= W both are read in B_n, and above W the four sets are, by symmetry, every integer missing from P_n. So the certificate runs on W bits and a sorted list of the middle holes, exact while the list stays below a cap, where the full array needs S_n bits.

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; the wide certificate certifies it below.
  • 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.
  • Verified (verb wcontrol 16, 6.8 s): on the 109 cells of minimal base sets in [3, 10] at k <= 4 that the full certificate settles within 2^30 bits, the wide certificate at W = 2^16 returns the same F, count of non-sums, index, S_n and takeover term in every cell, 59 of them with S_n > 2^17, where the list of middle holes carries the run.
  • Verified (verb deep 10 6 31 4, 21.3 s on 4 threads, W = 2^31 per cell): all 30 minimal base sets in [3, 10] are certified at k = 4, 23 at k = 5, and {3, 5, 6, 7} and {4, 5, 6, 7, 9} at k = 6. So every base set in [3, 10] with sigma > 1 and gcd = 1 is cofinite at k = 1, 2, 3, 4.
  • Verified (verb wcell, 3.6 to 14.7 s a cell): at k = 5, {3, 4, 8, 9}, {3, 5, 7, 9} and {3, 4, 9, 10} certify at W = 2^33, and {3, 5, 6, 9} and {3, 6, 8, 9, 10} at W = 2^34, so 28 of the 30 are certified at k = 5; {3, 4, 6} and {3, 5, 8, 9} at k = 5 and {3, 4, 5} at k = 6 are not certified within W = 2^34 and a list of 2^25 holes.
  • Verified (verbs deep 10 6 31 4 and split 3,4,5 5 31333640736 64, 0.3 s): F({3, 4, 5}, 5) = 31333640736, with 100335626 positive non-sums up to F, the certificate closing at a_n = 2^36 with S_n = 176844529807, the step holding until the surplus takes over at 5^17 = 762939453125; a meet in the middle over the 41 terms up to F + 63 finds F the only non-sum in [F, F + 63]. F({3, 4, 6}, 4) = 14059625243, with 21808124 non-sums.
  • Verified (verb deep 12 3 31 4, 2.8 s on 4 threads): the 103 minimal base sets in [3, 12] all certify at k = 2 in one run at W = 2^31, and 101 at k = 3; {3, 6, 8, 9, 12} and {3, 6, 9, 10, 12} are not certified at k = 3 within W = 2^33 (verb wcell).
  • 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, who state an argument at k = 1 alone without printing it; {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 31333640736 over five 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) but closes under the wide certificate at W = 2^31, at S_n = 176844529807.

The two routes

  • Proved (the two routes). An integer x with a_(n+1) <= x < a_(n+2) is no sum of M exactly when y = x - a_(n+1) and g = S_n - x are both missing from P_n, a negative g counting as missing; always g + y = S_n - a_(n+1). Proof: x uses only terms below a_(n+2), so it is a sum exactly when x or x - a_(n+1) lies in P_n, and for 0 <= x <= S_n the symmetry of P_n puts x in P_n exactly when S_n - x is. The window route is g < 0, the window lemma above; the pair route is g >= 0, the deficit S_n - a_(n+1) split into two integers of [0, S_n] missing from P_n, and it needs no window.
  • Refuted. The chain-excluded lemma: linear surplus, H_1(M) = {0}, and for all large m < n the upper window (S_m, a_(m+2)) disjoint from the lower window (S_n - a_(n+1), a_(n+2) - a_(n+1)), make a multiset complete. Witness: a_1, a_2, a_3 = 4, 5, 6 and a_(n+2) = S_n - y_n - y_(n+1) for n >= 2, y_n = 2 - (floor(n/2) mod 2), so E = 4, 5, 6, 7, 12, 18, 31, 50, 80, 129, .... No window: a_(n+2) < S_n for n >= 2, so every upper window from m = 2 on is empty and the chain condition holds. Spectrum: the recurrence at n + 1 minus the recurrence at n gives a_(n+3) - a_(n+2) - a_(n+1) = y_n - y_(n+2), which is 1 or -1, so theta in H_1(E) has norm(theta) <= norm(a_(n+3) theta) + norm(a_(n+2) theta) + norm(a_(n+1) theta) -> 0. Surplus: S_n - a_(n+1) = a_n + y_(n-1) + y_n >= a_n for n >= 3, and a_(n+1) <= 2 a_n + 1 by the last identity, so eps = 1/2 works with a constant. Incomplete: x_n = a_(n+1) + y_n is missing from P_(n+1) for every n >= 2, by induction: x_2 = 7 is no sum of {4, 5, 6}, and a sum of x_(n+1) = a_(n+2) + y_(n+1) in P_(n+2) either uses a_(n+2), leaving y_(n+1) below every term, or lies in P_(n+1), where x_(n+1) = S_n - y_n = S_(n+1) - x_n is missing with x_n by symmetry. For n >= 3, x_n < a_(n+2), so 8, 14, 20, 32, 51, 82, ... are no sums of E; each comes by the pair route, with g = x_(n-1) and y = y_n.
  • Verified (verb chainless 27, under 0.1 s, pinned by a crate test): its 38 terms up to 2^27 open no window at n >= 2, the least of 2 (S_n - a_(n+1)) - a_(n+1) over n >= 1 is -7, a_(n+3) - a_(n+2) - a_(n+1) takes only -1 and 1 for n >= 2, the 34 values a_(n+1) + y_n with 3 <= n <= 36, those below the last term, are non-sums, and of the 38 non-sums below the last term 3 lie below a_1 and 35 come by the pair route, none by the window route.
  • Verified (verbs deep 10 6 31 4, 21.3 s on 4 threads, and wcell): the power multisets make their largest non-sum by the pair route. Over the 30 minimal base sets in [3, 10], F(D, k) comes by the window route in 7 cells at k = 1, 1 at k = 2, 2 at k = 3 and by the pair route in every certified cell from k = 4 on, 30 at k = 4, 28 at k = 5, 2 at k = 6; at k = 4 the pair route carries 128689970 non-sums against 9859830 by the window route, and over the 23 cells deep certifies at k = 5, 1598272529 against 83741167. {3, 4, 6} makes F by the window route at k = 1, 2, 3 and by the pair route at k = 4.
  • So a criterion whose window clause a windowless multiset satisfies cannot reach {3, 4, 5}: the incompleteness proofs above run the window route for the Fibonacci set and floor(2 (5/3)^n) and the pair route for E, and the power multisets use both, the pair route for every F of the census from k = 4 on. Forcing windows into E heals it: E with a_(n+2) = S_n + 2 or S_n + 3 forced at n >= 6, n = 0 mod 6, 8 or 10, keeps its least 2 (S_n - a_(n+1)) - a_(n+1) at -7 and runs no chain, but in each of the six variants no non-sum lies in the last 12 term intervals up to 2^26 (verb forced 26, under 0.1 s); the lemma with windows required falls below to a multiset that sets its terms from the chain.

The windowed lemma

  • Proved (the chain). Let a be sorted and n_0 >= 1, with a_(n+2) = S_n - u_n - u_(n+1) for every n >= n_0, each u_(n+1) negative or a positive integer missing from P_(n+1), and x_n = a_(n+1) + u_n in [0, S_(n+1)]. If x_(n_0) is missing from P_(n_0 + 1), then every x_n, n >= n_0, is missing from P_(n+1), and is no sum whenever x_n < a_(n+2). Proof: x_(n+1) = a_(n+2) + u_(n+1) = S_n - u_n = S_(n+1) - x_n is missing from P_(n+1) with x_n, by symmetry, and x_(n+1) - a_(n+2) = u_(n+1) is negative or missing from P_(n+1), so x_(n+1) is missing from P_(n+2) = P_(n+1) U (P_(n+1) + a_(n+2)); an integer below a_(n+2) is a sum only of terms in P_(n+1). Along such a sequence a window opens at n exactly when u_n + u_(n+1) < 0, x_(n+1) comes by the pair route with g = x_n when u_(n+1) >= 0 and x_(n+1) < a_(n+3), and a_(j+3) - a_(j+2) - a_(j+1) = u_j - u_(j+2) for j >= n_0. The multiset E above is the case u_n = y_n.
  • Refuted. The windowed lemma: linear surplus, H_1(M) = {0}, windows a_(n+2) > S_n at infinitely many n, and for all large m < n the upper window (S_m, a_(m+2)) disjoint from the lower window (S_n - a_(n+1), a_(n+2) - a_(n+1)), make a multiset complete. Witness: V, with a_1, a_2, a_3 = 4, 5, 6 and a_(n+2) = S_n - u_n - u_(n+1) for n >= 2, where u_n = 2 at n = 0 mod 5 from n = 5, u_n = -x_(n-2) at n = 1 mod 5 from n = 6, u_n = x_(n-3) at n = 2 mod 5 from n = 7, and u_n = 1 otherwise, x_n = a_(n+1) + u_n; so V = 4, 5, 6, 7, 13, 19, 47, 54, 86, 153, 238, 546, ....
  • Shape: for n = 5q >= 5, x_(n-1) = a_n + 1, and the identity of the chain lemma reads a_(n+1) = a_n + a_(n-1) - 1, a_(n+2) = a_(n+1) + 2 a_n + 2, a_(n+3) = a_(n+2) + a_(n+1) - a_n + 1, a_(n+4) = a_(n+3) + a_(n+2) - a_n - 2, a_(n+5) = a_(n+4) + a_(n+3) + a_n. Every increment is positive, so V is sorted, and a_(j+1) <= 3 a_j + 2 for all j.
  • Windows: a_(n+2) - S_n = -(u_n + u_(n+1)) is a_n - 1 at n = 0 mod 5, n >= 5, and 0, -a_n - 2, -2, -3 at the next four, and negative at n = 2, 3, 4; so from n = 2 on a window opens exactly at the multiples of 5, of width a_n - 1 >= (a_(n+2) - 5)/4, since a_(n+2) <= 4 a_n + 1. No chain: for windows m < n, m <= n - 5, and the upper window of m ends at a_(m+2) <= a_(n-3) <= S_(n-2), below S_n - a_(n+1) = S_(n-2) + 1, where the lower window of n begins.
  • Surplus: S_j - a_(j+1) = a_j + u_(j-1) + u_j for j >= 3, which over a period is a_n + 3, a_(n-1), a_(n+2), a_(n+3) + a_n + 2, a_(n+4) + 2, and 8, 9 at j = 3, 4; with a_(n+2) <= 4 a_n + 1 <= 12 a_(n-1) + 1, since a_n = a_(n-1) + a_(n-2) + a_(n-5) < 3 a_(n-1) at n = 0 mod 5, n >= 10, by the last identity of the shape, and a_5 = 13 <= 21, this gives 12 (S_j - a_(j+1)) >= a_(j+1) - 2 for every j >= 3. Spectrum: a_(j+3) - a_(j+2) - a_(j+1) = u_j - u_(j+2) = -1 at every j = 3 mod 5, so theta in H_1(V) has norm(theta) <= norm(a_(j+3) theta) + norm(a_(j+2) theta) + norm(a_(j+1) theta) -> 0.
  • Incomplete: the chain lemma applies with n_0 = 2. The positive u_(n+1) are 1 and 2, below a_1, and x_(n-1) at n = 0 mod 5, which the induction has already put outside P_n, and x_(n-1) = a_n + 1 < a_(n+1), so it is missing from P_(n+2); x_2 = 7 is no sum of {4, 5, 6}; every x_i lies in [0, S_(i+1)], since x_i = S_(i-1) - 2 where u_i < 0 and 0 < u_i <= a_(i-2) + 1 <= S_i elsewhere; and a_(n+2) - x_n = a_n + u_(n-1) - u_n - u_(n+1) is positive for every n >= 3. So every x_n, n >= 3, is no sum of V, and x_(n+1) = S_n - 2 at n = 0 mod 5 grows without bound.
  • Verified (verb windowed 27, under 0.1 s, pinned by a crate test): the 37 terms of V up to 2^27 are sorted and open 7 windows from n = 2 on, exactly at n = 5, 10, ..., 35, the least of (a_(n+2) - S_n)/a_(n+2) over them 0.255, truncated, with no chained pair, and every one holding a non-sum; the least of 12 (S_n - a_(n+1)) - a_(n+1) over n >= 3 is 37, the largest a_(n+1) - 3 a_n is -7, a_(n+3) - a_(n+2) - a_(n+1) is -1 at every n = 3 mod 5 from 3; the 33 values x_n with n >= 3 below a_(n+2) are non-sums, the first 8, 14, 21, 33, 68, 87, 154, 240; of the 1352 non-sums below the last term, 3 lie below a_1, 494 come by the window route and 855 by the pair route.
  • So the windowed lemma falls like the chain-excluded lemma: V opens windows at a fifth of its steps, of width at least (a_(n+2) - 5)/4, where M_k({3, 4, 5}) opens them at 27 of 123 terms at each k = 1..4, keeps consecutive ratios at most 3 + 2/a_j, and makes non-sums by both routes, as the power multisets do. The forced variants of E heal because their terms ignore the chain; V sets each term from a chain hole. Both E and V live on the deficit S_n - a_(n+1) landing on a sum of two holes of P_n; the next section measures where the holes of P_n sit for the power multisets.

The deepest hole

  • G_n is the set of integers of [0, S_n/2] missing from P_n, so T_n = 1 + max G_n, and T_n = 0 when G_n is empty; R_n = S_n - a_(n+1) is the deficit; T rises at n when T_(n+1) > T_n. A missing integer x of P_(n+1) is born at n when S_n/2 < x <= S_(n+1)/2, and every positive integer has exactly one such n.
  • Proved (the birth law). An integer x with S_n/2 < x <= S_(n+1)/2 is missing from P_(n+1) exactly when x = S_n - g with g missing from P_n, R_n <= 2g < S_n, and R_n - g missing from P_n, a negative value counting as missing; every integer of [0, S_n/2] missing from P_(n+1) lies in G_n. Proof: P_(n+1) = P_n U (P_n + a_(n+1)), so x is missing exactly when x and x - a_(n+1) are missing from P_n; for x <= S_n/2 the first puts x in G_n; for x > S_n/2, write g = S_n - x < S_n/2, which by symmetry is missing from P_n exactly when x is, negative when x > S_n; then x - a_(n+1) = R_n - g, and x <= S_(n+1)/2 reads 2g >= R_n.
  • Proved (the jump). If T rises at n, then S_n - T_n + 2 <= T_(n+1) <= S_(n+1)/2 + 1 and R_n <= 2 T_n - 2. If R_n < T_n - 1 < S_n/2, then T rises at n. Proof: the missing integers of P_(n+1) up to S_n/2 lie in G_n, below T_n, so a rise is a birth T_(n+1) - 1 = S_n - g with g <= T_n - 1, negative or in G_n, and R_n <= 2g; conversely g = T_n - 1, in G_n or -1, is below S_n/2 and above R_n, so R_n - g < 0 and x = S_n - g is born, above S_n/2 > T_n - 1.
  • Proved (after a rise). If T rises at n, then R_(n+1) <= S_n <= 2 T_(n+1) - 2, so the interval step fails at n + 1; and the certificate at index N closes at least two steps after the last rise. Proof: R_(n+1) = S_n + a_(n+1) - a_(n+2) <= S_n, and 2 T_(n+1) - 2 >= 2 S_n - 2 T_n + 2 >= S_n since 2 T_n <= S_n + 2. The certificate needs R_N >= 2 T_N - 1, from its first step or, when the surplus clause is already empty at N, from the surplus lemma, and no rise follows N, since P_n contains [T_N, S_n - T_N] for every n >= N and T_N - 1 = F stays missing.
  • Proved (the route of F). Let M_k(D) be complete and b the step at which F = F(D, k) is born, S_b < 2F <= S_(b+1), so F = S_b - g with g as in the birth law. If F >= a_(b+1), then F comes by the pair route. If F comes by the window route, then F < a_(b+1), g > R_b and T_b - 1 > R_b. Proof: if F >= a_(b+1), its index j, with a_(j+1) <= F < a_(j+2), has j >= b, and g = S_b - F >= 0 since 2F <= S_b + a_(b+1) <= S_b + F, so S_j - F >= g >= 0, the pair route. If F < a_(b+1), then g = S_b - F > R_b, and either g >= 0 lies in G_b, so T_b - 1 >= g > R_b, or R_b < g < 0 <= T_b.
  • Verified (verb jumps 10 6 31 4, 20.1 s on 4 threads, W = 2^31): on every step of the 173 cells the run reaches, each minimal base set in [3, 10] from k = 1 up to its first level capped at W = 2^31, at most 6, no rise breaks the bounds of the jump, no step with R_n < T_n - 1 < S_n/2 fails to rise, and no step after a rise has R_(n+1) > 2 T_(n+1) - 2. Over the 145 certified cells, F >= a_(b+1) in 17, 27, 27, 26, 22, 2 at k = 1..6, and F comes by the window route in 7, 1, 2, 0, 0, 0, each with T_b - 1 > R_b; F is born at the last rise of T in 111; the certificate closes 2, 3, 4, 5, 6 steps after the last rise in 61, 52, 27, 3, 2 cells; T rises at every step from the entry of the last base max d^k to its last rise in 21, 23, 23, 24, 17, 2.
  • The falsification run: T_n / a_(n+1) after the last base enters peaks at 1.9430, at {3, 6, 7, 9, 10}, k = 5, and every certified cell with k >= 2 passes 1.1727 ({3, 5, 8, 10}, k = 3), so no bound T_n <= c a_(n+1) with c < 1.17 holds along the census from the entry of the last base, and a hole bound has to wait for the run of births to end. At the cut, each of the 28 capped cells the run reaches, {3, 4, 5} at k = 6 among them, has every rise of T in one run still open at the cap, of 28 to 37 rises; {3, 4, 5} at k = 6 stands at 30.
  • So the deepest hole never creeps: it stays, falls, which needs a_(n+1) <= T_n - 1 to fill T_n - 1, or jumps past the middle of P_n, and the step after a jump is never an interval step; the middle of P_n stays holed while the births run. The pair route makes F in the 26 cells at k = 4 and 22 at k = 5 where F >= a_(b+1) by the route lemma; the other 4 and 1 come by the pair route from an index below b, which the lemma does not explain. Completeness needs a step that ends the run: by the jump, one with T_n - 1 <= R_n or 2 T_n - 2 = S_n and no birth; when T_n - 1 <= R_n, the birth law says no birth exactly when R_n is no sum g + h of members of G_n with h <= g < S_n/2; then the certificate needs R_N >= 2 T_N - 1 at some later N. A proof uniform in k has to produce that step, and E and V are built so that it never comes.

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 <= 5 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.
  • Proved (the target as one inequality). If 1 < sigma(D) < 2, then M_k(D) is complete exactly when some n has 2 T_n - 1 <= (sigma(D) - 1) a_(n+1) - C_k(D), with T_n = 1 + max{x <= S_n/2 : x not in P_n}. Proof: at such an n, T_n < a_(n+1) since sigma - 1 < 1, and the surplus clause of the certificate is empty because a_(m+1) >= a_(n+1) for m >= n; conversely, along the steps of the gap proof T_n = F(D, k) + 1 while a_(n+1) grows without bound.
  • So a proof for {3, 4, 5}, where sigma - 1 = 1/12, is a bound uniform in k that brings the deepest hole of P_n below about a_(n+1)/24. A criterion whose window clause a windowless multiset satisfies cannot supply it: the chain-excluded lemma is refuted above by a multiset with no window, and the pair route makes every F of the census from k = 4 on; the windowed lemma is refuted by V, whose windows open at every fifth step. Such a bound cannot hold while the births run: the step after a rise has S_(n+1) - a_(n+2) <= 2 T_(n+1) - 2, so the one inequality fails there, every rise lands past S_n/2, and every certified cell with k >= 2 has T_n > 1.17 a_(n+1) after its last base enters. At sigma = 1 the surplus is -C and {3, 4, 7} stays apart.