
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 powersd^jwithj >= k, which isd^ktimes the base-ddesign{0, 1}.- A base set is a finite
D = {d_1 < ... < d_r}of integers>= 3;M_k(D)is the multiset of the powersd_i^j,j >= k, one copy per base, sosum_i P(d_i, k)is the setFS(M_k(D))of sums of distinct terms ofM_k(D). sigma(D) = sum_i 1/(d_i - 1)andC_k(D) = sum_i d_i^k/(d_i - 1).M_k(D)is complete whenFS(M_k(D))contains every large integer;F(D, k)is then the largest integer outside it.a_1 <= a_2 <= ...isM_k(D)sorted,S_n = a_1 + ... + a_n, andP_nthe set of sums of distinct terms among the firstn, a subset of[0, S_n]symmetric underx -> 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 | 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 | 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 | 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 | infinitely many n with binomial(2n, n) prime to 105? | open | carried: three designs at bases 3, 5, 7, Two bases Object T, not reopened |
| 5 | 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 | 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 |
| 7 | 1146 | is {2^m 3^n} an essential component? | open | the same two-base lattice, against Schnirelmann density |
| 8 | 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 | 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 | 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 | 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 | 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 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 forPow(A; s), the nondecreasing sequence formed from all the powersa^k,ainA,k >= s >= 1, which, called nondecreasing, reads as the multisetM_s(A), though Claim 1 writes it strictly increasing; their Theorem 1 gives, forAof positive upper density withgcd = 1, a finiteA'inAwithPow(A'; s)complete, through a gap bound2 b_N^(s+1)for the sums ofPow(B; s)whensum 1/b_i > 2and Szemeredi's theorem. Of{3, 4, 7}they state, without printing the argument, that the bound of Mignotte and Waldschmidt onabs(3^p - 4^q)lets them show it complete ats = 1, largest missing integer581, and they print the largest missing integers111,16and78for{3, 5, 7, 13},{3, 6, 7, 13, 21}and{3, 4, 5}ats = 1. A plain knapsack to2 10^6reads581for{3, 4, 7}, as they do, but112,17and79for the other three, and111 = 81 + 27 + 3,16 = 9 + 7,78 = 64 + 9 + 5are sums (verbset;79is also the certificate'sF). The levelk = 0, where every powerd^0 = 1is allowed, is settled on the discussion thread by a Lean-checked proof through Brown's criteriona_(n+1) <= S_n + 1, read at source. - The site records that
sigma(D) >= 1is necessary, after Pomerance; the thread reconstructs the argument: by Dirichlet's simultaneous approximation, infinitely often every base has its least power>= Nin[N, beta N), and whensigma(D) < 1the terms belowNthen sum to less thansigma(D) beta N < N, soN - 1is no sum. - Bergelson and Simmons 2017, Theorem 1.23, read at source: the set of powers of
Dis strongly complete, complete after deleting any finite set, whenDsplits into four disjoint parts, three withsigma >= 1and one withgcd = 1; they write that they can neither prove nor disprove the conjecture. Strongly complete is complete at everyk. - Fan 2026, Theorem 1.5, read at source: the same with two parts of
sigma >= 1and one ofgcd = 1, for finiteDwith 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) withDelta(B) = sup_(b in B) (b - sum_(b' in B, b' < b) b')finite, plus one more partCwithsum_(c in C) norm(c theta) = infinity, for everythetanot inZwithDelta(C)finite or a countableH_2(C)(Fan), or for every irrationalthetawithFS(C) + qZ = Zfor everyq(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: atD = {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 mostx^(log_5 2 + log_6 2) < x^0.82up tox; 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)^nanda^(2n)are one term, and exclude two elements powers of one integer; the site's question, a sum of one element of eachP(d_i, k), is the multisetM_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}atk = 1hasF = 22as a multiset, while as a set649is no sum and every integer from650to2 10^4is (verbscell 3,5,6,9 1 20andset 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 withsigma(D) < 2; the site's credit of{3, 4, 7}, wheresigma = 1, rests on an argument at the one levelk = 1that the paper states but does not print; the103base sets in[3, 12]minimal forsigma > 1andgcd = 1havesigmabetween2311/2310and8/7(verbcensus 12 5 32 4).
The surplus certificate
- Proved (the interval step). If
P_ncontains[T, S_n - T]anda_(m+1) <= S_m - 2T + 1for everym >= n, thenFS(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 whenT + a_(m+1) <= S_m - T + 1, andS_m -> infinity. Atk = 0,T = 0is 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_nholds every term belowX = a_(n+1), and for each base those ared^jwithk <= j < J,d^J >= Xthe least power>= XwithJ >= k, summing to(d^J - d^k)/(d - 1) >= (X - d^k)/(d - 1). - Proved (the certificate). Let
sigma(D) > 1andk >= 1. If for somenthe integerT = 1 + max{x <= S_n/2 : x not in P_n}satisfiesT <= a_(n+1), anda_(m+1) <= S_m - 2T + 1holds for everym >= nwith(sigma(D) - 1) a_(m+1) < C_k(D) + 2T - 1, thenM_k(D)is complete andF(D, k) = T - 1exactly. Proof: past that finite range the surplus gives the step, so the interval step applies; andT - 1 < a_(n+1)is a sum of distinct terms only of terms belowa_(n+1), all inP_n, where it is missing. The check is finite and exact: integer arithmetic withsigmaandC_kover the common denominator of thed_i - 1. - Proved (exact in the gap). If
1 < sigma(D) < 2, thenM_k(D)is complete if and only if the certificate exists at somen, so the search halts exactly on the complete levels and a level left open is open only for the cap. Proof: fixbeta > 1withsigma(D) beta < 2; Dirichlet's simultaneous approximation gives arbitrarily large exponents with one power of every base, all within a factorbeta < 3of one another, and withNthe least of them (Fan, footnote 1)Nis a term and the least power>= Nof every base lies in[N, beta N); at the first copya_(n+1) = Nthe terms belowNsum toS_n < sigma(D) beta N < 2 a_(n+1); then everyx <= S_n/2is a sum of distinct terms belowa_(n+1)or of none, soP_nandFS(M_k(D))agree on[0, S_n/2], the certificate readsT = F(D, k) + 1, and forNlarge the surplus clause is empty. - Proved (monotone). Completeness at
(D, k)gives completeness at(D', k')for every base setD'containingDand everyk' <= k, sinceM_k'(D')containsM_k(D)as a multiset. So the census below needs only the base sets that are minimal forsigma > 1andgcd = 1, each at its deepest certified level. - Proved (the wide certificate). Fix
W, letB_n = P_n meet [0, W]and letH_nbe the integers of(W, S_n/2]missing fromP_n, so thatB_n,H_nand the symmetry give all ofP_n. ThenB_(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 fromP_(n+1)lies inH_n, inS_n - H_n, inS_n - ([0, W] minus B_n)or aboveS_n, and such a candidatezis missing fromP_(n+1)exactly whenz - a_(n+1)is missing fromP_n. Proof:P_(n+1) = P_n U (P_n + a_(n+1)), sozis missing fromP_(n+1)exactly whenzandz - a_(n+1)are missing fromP_n; forz <= Wboth are read inB_n, and aboveWthe four sets are, by symmetry, every integer missing fromP_n. So the certificate runs onWbits and a sorted list of the middle holes, exact while the list stays below a cap, where the full array needsS_nbits.
The two-part route is dead below two
- Proved. Let
Dbe finite withsigma(D) < 2andk >= 0. Then no two disjoint infinite sub-multisetsB_1, B_2ofM_k(D)have bothDelta(B_1)andDelta(B_2)finite, whatever becomes of the other terms. Proof: takeNas in the gap proof above, so the terms belowNsum to less thansigma(D) beta N, and letb_ibe the least term ofB_ithat is>= N; the terms ofB_ibelowb_iare those belowN, soDelta(B_1) + Delta(B_2) >= b_1 + b_2 - sigma(D) beta N >= (2 - sigma(D) beta) N, unbounded inN. - 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)withsigma(D) < 2under any partition of the terms, not only the partitions by bases; the whole ofM_k(D)hasDeltafinite oncesigma(D) >= 1, and the obstruction is the second part. The syndetic-pair method cannot enter the gap1 <= sigma(D) < 2at all. - Verified (verb
route 10 12, under0.01s): for each of the30minimal base sets below11, the least value ofsum(M_1(D) below N)/Nover termsNin[10^12, 10^30]lies in[1.105953, 1.537469], truncated, so at thatNany two disjoint parts of the terms have one withDelta >= 0.23 N: the clusters the proof uses are already visible at twelve digits.
The census
- Verified (verb
census 10 5 32 4,2.9s on4threads, a2^32-bit array per cell): there are30base sets in[3, 10]minimal forsigma > 1andgcd = 1, and each is certified, as the multisetM_k(D), atk = 1, 2, 3, twenty-one also atk = 4and five of those atk = 5. By the monotone lemma, every base setDin[3, 10]withsigma(D) > 1andgcd(D) = 1hassum_i P(d_i, k)cofinite fork = 1, 2, 3. - Verified (verbs
census 12 5 32 4,8.7s, andcell 3,6,9,10,12 2 34,1.3s): the103minimal base sets in[3, 12]are all certified atk = 1, 2; the last one,{3, 6, 9, 10, 12}, whose only base prime to3is10, needs a2^34-bit array atk = 2and hasF = 1473914231. So every base set in[3, 12]withsigma > 1andgcd = 1is cofinite atk = 1, 2. - Verified (verbs
census 10 5 32 4andcell 3,4,5 4 34,1.0s):F({3, 4, 5}, k)reads79, 77613, 4330731, 1075364603atk = 1..4, with11, 1128, 45704, 1785062positive integers up toFthat are no sum;F({3, 4, 6}, k)reads986, 242113, 58941162atk = 1..3, andk = 4is not certified within a2^34-bit array; the wide certificate certifies it below. - Verified (verb
control,0.9s): on nine cells,{3, 4, 5}atk = 1, 2, 3among them, a plain knapsack over every term up to4 Freturns the sameFand the same count of missing integers as the certificate, and{3, 6, 9, 12, 15, 21}, withsigma > 1andgcd = 3, never certifies below2^24. - Verified (verb
wcontrol 16,6.8s): on the109cells of minimal base sets in[3, 10]atk <= 4that the full certificate settles within2^30bits, the wide certificate atW = 2^16returns the sameF, count of non-sums, index,S_nand takeover term in every cell,59of them withS_n > 2^17, where the list of middle holes carries the run. - Verified (verb
deep 10 6 31 4,21.3s on4threads,W = 2^31per cell): all30minimal base sets in[3, 10]are certified atk = 4,23atk = 5, and{3, 5, 6, 7}and{4, 5, 6, 7, 9}atk = 6. So every base set in[3, 10]withsigma > 1andgcd = 1is cofinite atk = 1, 2, 3, 4. - Verified (verb
wcell,3.6to14.7s a cell): atk = 5,{3, 4, 8, 9},{3, 5, 7, 9}and{3, 4, 9, 10}certify atW = 2^33, and{3, 5, 6, 9}and{3, 6, 8, 9, 10}atW = 2^34, so28of the30are certified atk = 5;{3, 4, 6}and{3, 5, 8, 9}atk = 5and{3, 4, 5}atk = 6are not certified withinW = 2^34and a list of2^25holes. - Verified (verbs
deep 10 6 31 4andsplit 3,4,5 5 31333640736 64,0.3s):F({3, 4, 5}, 5) = 31333640736, with100335626positive non-sums up toF, the certificate closing ata_n = 2^36withS_n = 176844529807, the step holding until the surplus takes over at5^17 = 762939453125; a meet in the middle over the41terms up toF + 63findsFthe only non-sum in[F, F + 63].F({3, 4, 6}, 4) = 14059625243, with21808124non-sums. - Verified (verb
deep 12 3 31 4,2.8s on4threads): the103minimal base sets in[3, 12]all certify atk = 2in one run atW = 2^31, and101atk = 3;{3, 6, 8, 9, 12}and{3, 6, 9, 10, 12}are not certified atk = 3withinW = 2^33(verbwcell). - The one base set in
[3, 12]withsigma = 1andgcd = 1is{3, 4, 7}, the case the site credits to Burr, Erdos, Graham and Li, who state an argument atk = 1alone without printing it;{3, 5, 7, 13}is the next. There the surplus is zero, the step at a termXholds only if the other bases keep their next powers far fromX, and the surplus clause of the certificate never empties, so the census does not reach that tail; the discussion thread names a lower bound onabs(d^a - e^b)of Baker type as the least it needs. - The thresholds climb steeply with
k, from79to31333640736over 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) - Cfor alln, someeps > 0and a constantC;H_1(M)is the set ofthetainR/Zwithsum_(a in M) norm(a theta) < infinity, Fan'sH_1-spectrum. EveryM_k(D)withsigma(D) > 1andgcd(D) = 1has both properties,eps = sigma(D) - 1by the surplus lemma andH_1 = {0}by Fan's Section 7 argument applied base by base, so the lemma L, that linear surplus andH_1(M) = {0}make a multiset complete, would settle problem 124 abovesigma = 1. - Refuted. L is false. Witness:
A = {2 F_m - 1 : m >= 2} = 1, 3, 5, 9, 15, 25, 41, ...,F_mthe Fibonacci numbers, soa_(n+1) = a_n + a_(n-1) + 1. Surplus:S_n = 2 F_(n+3) - 4 - n, soS_n - a_(n+1) = a_n - n - 2 >= a_(n+1)/2 - n - 5/2, anda_ngrows geometrically, soeps = 1/4works with a constantC. Spectrum: ifthetais inH_1(A), thennorm(a_n theta) -> 0andnorm(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 + 3opens a window at everyn, anda_(m+1) >= a_m + a_(m-1)puts the upper window(S_(n-2), a_n)inside the lower window of stepn, so the non-sum2, in the upper windows(0, 3)and(1, 5), recurs in every window. - Verified (verb
refute 27, under0.1s, pinned by a crate test): the38terms ofAup to2^27open36windows, every one holding a non-sum; the least of2 (S_n - a_(n+1)) - a_(n+1)is-9; the25non-sums below10^6are the two chains2, 7, 22, 63, 172, ...and2, 11, 36, 103, 280, .... - Proved (the window). If
a_(n+2) > S_n, the sums in(S_n, a_(n+2))are exactlya_(n+1) + (P_n meet (S_n - a_(n+1), a_(n+2) - a_(n+1))): such anxuses only terms belowa_(n+2), and exceeds the sum of all terms beforea_(n+1), so it usesa_(n+1). An integer of the lower window missing fromP_nis 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, hasS_n - a_(n+1) >= a_(n+1)/2 - n - 5, which is linear surplus sincea_(n+1)grows geometrically, and is incomplete. Proof:a_(n+2) >= (50/9)(5/3)^n - 1 > 5 (5/3)^n - 5 >= S_nopens a window at everyn;a_(m+1) - a_m - a_(m-1) >= (2/9)(5/3)^(m-1) - 1 > 0form >= 4puts the upper window(S_(n-2), a_n)inside the lower window of stepn; a non-sumhthere is missing fromP_n, sinceh < a_n, soa_(n+1) + his a non-sum, and one seed recurs in every other window. This is Graham's incompleteness fort > 1,alpha >= max(2/t, phi)as Fan quotes it, reproved at one point; whether itsH_1is{0}is open, of the kind the site's problem 349 names when it asks whetherfloor((3/2)^n)is odd or even infinitely often. - Verified (verb
graham 2 5 3 26, under0.1s): the33terms offloor(2 (5/3)^n)up to2^26open31windows and every one holds a non-sum; the largest non-sum up to2^25is23559582. - Verified (verb
windows, under0.01s each): the power multisets run no chain. Over the terms in[10^6, 10^30],M_k({3, 4, 5})opens a window at27of123terms at eachk = 1..4,M_1({3, 4, 6})at41of120,M_1({3, 5, 6, 7})at5of142, 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 - 1alone, so Baker, Matveev or Laurent can only serve thesigma = 1cells. What changes withkis the base interval[T, S_n - T], whose scale climbs froma_n = 243atk = 1to3486784401atk = 4for{3, 4, 5}, andk = 5passes a2^34-bit array (verbcell 3,4,5 5 34) but closes under the wide certificate atW = 2^31, atS_n = 176844529807.
The two routes
- Proved (the two routes). An integer
xwitha_(n+1) <= x < a_(n+2)is no sum ofMexactly wheny = x - a_(n+1)andg = S_n - xare both missing fromP_n, a negativegcounting as missing; alwaysg + y = S_n - a_(n+1). Proof:xuses only terms belowa_(n+2), so it is a sum exactly whenxorx - a_(n+1)lies inP_n, and for0 <= x <= S_nthe symmetry ofP_nputsxinP_nexactly whenS_n - xis. The window route isg < 0, the window lemma above; the pair route isg >= 0, the deficitS_n - a_(n+1)split into two integers of[0, S_n]missing fromP_n, and it needs no window. - Refuted. The chain-excluded lemma: linear surplus,
H_1(M) = {0}, and for all largem < nthe 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, 6anda_(n+2) = S_n - y_n - y_(n+1)forn >= 2,y_n = 2 - (floor(n/2) mod 2), soE = 4, 5, 6, 7, 12, 18, 31, 50, 80, 129, .... No window:a_(n+2) < S_nforn >= 2, so every upper window fromm = 2on is empty and the chain condition holds. Spectrum: the recurrence atn + 1minus the recurrence atngivesa_(n+3) - a_(n+2) - a_(n+1) = y_n - y_(n+2), which is1or-1, sothetainH_1(E)hasnorm(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_nforn >= 3, anda_(n+1) <= 2 a_n + 1by the last identity, soeps = 1/2works with a constant. Incomplete:x_n = a_(n+1) + y_nis missing fromP_(n+1)for everyn >= 2, by induction:x_2 = 7is no sum of{4, 5, 6}, and a sum ofx_(n+1) = a_(n+2) + y_(n+1)inP_(n+2)either usesa_(n+2), leavingy_(n+1)below every term, or lies inP_(n+1), wherex_(n+1) = S_n - y_n = S_(n+1) - x_nis missing withx_nby symmetry. Forn >= 3,x_n < a_(n+2), so8, 14, 20, 32, 51, 82, ...are no sums ofE; each comes by the pair route, withg = x_(n-1)andy = y_n. - Verified (verb
chainless 27, under0.1s, pinned by a crate test): its38terms up to2^27open no window atn >= 2, the least of2 (S_n - a_(n+1)) - a_(n+1)overn >= 1is-7,a_(n+3) - a_(n+2) - a_(n+1)takes only-1and1forn >= 2, the34valuesa_(n+1) + y_nwith3 <= n <= 36, those below the last term, are non-sums, and of the38non-sums below the last term3lie belowa_1and35come by the pair route, none by the window route. - Verified (verbs
deep 10 6 31 4,21.3s on4threads, andwcell): the power multisets make their largest non-sum by the pair route. Over the30minimal base sets in[3, 10],F(D, k)comes by the window route in7cells atk = 1,1atk = 2,2atk = 3and by the pair route in every certified cell fromk = 4on,30atk = 4,28atk = 5,2atk = 6; atk = 4the pair route carries128689970non-sums against9859830by the window route, and over the23cellsdeepcertifies atk = 5,1598272529against83741167.{3, 4, 6}makesFby the window route atk = 1, 2, 3and by the pair route atk = 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 andfloor(2 (5/3)^n)and the pair route forE, and the power multisets use both, the pair route for everyFof the census fromk = 4on. Forcing windows intoEheals it:Ewitha_(n+2) = S_n + 2orS_n + 3forced atn >= 6,n = 0 mod 6, 8or10, keeps its least2 (S_n - a_(n+1)) - a_(n+1)at-7and runs no chain, but in each of the six variants no non-sum lies in the last12term intervals up to2^26(verbforced 26, under0.1s); the lemma with windows required falls below to a multiset that sets its terms from the chain.
The windowed lemma
- Proved (the chain). Let
abe sorted andn_0 >= 1, witha_(n+2) = S_n - u_n - u_(n+1)for everyn >= n_0, eachu_(n+1)negative or a positive integer missing fromP_(n+1), andx_n = a_(n+1) + u_nin[0, S_(n+1)]. Ifx_(n_0)is missing fromP_(n_0 + 1), then everyx_n,n >= n_0, is missing fromP_(n+1), and is no sum wheneverx_n < a_(n+2). Proof:x_(n+1) = a_(n+2) + u_(n+1) = S_n - u_n = S_(n+1) - x_nis missing fromP_(n+1)withx_n, by symmetry, andx_(n+1) - a_(n+2) = u_(n+1)is negative or missing fromP_(n+1), sox_(n+1)is missing fromP_(n+2) = P_(n+1) U (P_(n+1) + a_(n+2)); an integer belowa_(n+2)is a sum only of terms inP_(n+1). Along such a sequence a window opens atnexactly whenu_n + u_(n+1) < 0,x_(n+1)comes by the pair route withg = x_nwhenu_(n+1) >= 0andx_(n+1) < a_(n+3), anda_(j+3) - a_(j+2) - a_(j+1) = u_j - u_(j+2)forj >= n_0. The multisetEabove is the caseu_n = y_n. - Refuted. The windowed lemma: linear surplus,
H_1(M) = {0}, windowsa_(n+2) > S_nat infinitely manyn, and for all largem < nthe 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, witha_1, a_2, a_3 = 4, 5, 6anda_(n+2) = S_n - u_n - u_(n+1)forn >= 2, whereu_n = 2atn = 0 mod 5fromn = 5,u_n = -x_(n-2)atn = 1 mod 5fromn = 6,u_n = x_(n-3)atn = 2 mod 5fromn = 7, andu_n = 1otherwise,x_n = a_(n+1) + u_n; soV = 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 readsa_(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, soVis sorted, anda_(j+1) <= 3 a_j + 2for allj. - Windows:
a_(n+2) - S_n = -(u_n + u_(n+1))isa_n - 1atn = 0 mod 5,n >= 5, and0, -a_n - 2, -2, -3at the next four, and negative atn = 2, 3, 4; so fromn = 2on a window opens exactly at the multiples of5, of widtha_n - 1 >= (a_(n+2) - 5)/4, sincea_(n+2) <= 4 a_n + 1. No chain: for windowsm < n,m <= n - 5, and the upper window ofmends ata_(m+2) <= a_(n-3) <= S_(n-2), belowS_n - a_(n+1) = S_(n-2) + 1, where the lower window ofnbegins. - Surplus:
S_j - a_(j+1) = a_j + u_(j-1) + u_jforj >= 3, which over a period isa_n + 3, a_(n-1), a_(n+2), a_(n+3) + a_n + 2, a_(n+4) + 2, and8, 9atj = 3, 4; witha_(n+2) <= 4 a_n + 1 <= 12 a_(n-1) + 1, sincea_n = a_(n-1) + a_(n-2) + a_(n-5) < 3 a_(n-1)atn = 0 mod 5,n >= 10, by the last identity of the shape, anda_5 = 13 <= 21, this gives12 (S_j - a_(j+1)) >= a_(j+1) - 2for everyj >= 3. Spectrum:a_(j+3) - a_(j+2) - a_(j+1) = u_j - u_(j+2) = -1at everyj = 3 mod 5, sothetainH_1(V)hasnorm(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 positiveu_(n+1)are1and2, belowa_1, andx_(n-1)atn = 0 mod 5, which the induction has already put outsideP_n, andx_(n-1) = a_n + 1 < a_(n+1), so it is missing fromP_(n+2);x_2 = 7is no sum of{4, 5, 6}; everyx_ilies in[0, S_(i+1)], sincex_i = S_(i-1) - 2whereu_i < 0and0 < u_i <= a_(i-2) + 1 <= S_ielsewhere; anda_(n+2) - x_n = a_n + u_(n-1) - u_n - u_(n+1)is positive for everyn >= 3. So everyx_n,n >= 3, is no sum ofV, andx_(n+1) = S_n - 2atn = 0 mod 5grows without bound. - Verified (verb
windowed 27, under0.1s, pinned by a crate test): the37terms ofVup to2^27are sorted and open7windows fromn = 2on, exactly atn = 5, 10, ..., 35, the least of(a_(n+2) - S_n)/a_(n+2)over them0.255, truncated, with no chained pair, and every one holding a non-sum; the least of12 (S_n - a_(n+1)) - a_(n+1)overn >= 3is37, the largesta_(n+1) - 3 a_nis-7,a_(n+3) - a_(n+2) - a_(n+1)is-1at everyn = 3 mod 5from3; the33valuesx_nwithn >= 3belowa_(n+2)are non-sums, the first8, 14, 21, 33, 68, 87, 154, 240; of the1352non-sums below the last term,3lie belowa_1,494come by the window route and855by the pair route. - So the windowed lemma falls like the chain-excluded lemma:
Vopens windows at a fifth of its steps, of width at least(a_(n+2) - 5)/4, whereM_k({3, 4, 5})opens them at27of123terms at eachk = 1..4, keeps consecutive ratios at most3 + 2/a_j, and makes non-sums by both routes, as the power multisets do. The forced variants ofEheal because their terms ignore the chain;Vsets each term from a chain hole. BothEandVlive on the deficitS_n - a_(n+1)landing on a sum of two holes ofP_n; the next section measures where the holes ofP_nsit for the power multisets.
The deepest hole
G_nis the set of integers of[0, S_n/2]missing fromP_n, soT_n = 1 + max G_n, andT_n = 0whenG_nis empty;R_n = S_n - a_(n+1)is the deficit;Trises atnwhenT_(n+1) > T_n. A missing integerxofP_(n+1)is born atnwhenS_n/2 < x <= S_(n+1)/2, and every positive integer has exactly one suchn.- Proved (the birth law). An integer
xwithS_n/2 < x <= S_(n+1)/2is missing fromP_(n+1)exactly whenx = S_n - gwithgmissing fromP_n,R_n <= 2g < S_n, andR_n - gmissing fromP_n, a negative value counting as missing; every integer of[0, S_n/2]missing fromP_(n+1)lies inG_n. Proof:P_(n+1) = P_n U (P_n + a_(n+1)), soxis missing exactly whenxandx - a_(n+1)are missing fromP_n; forx <= S_n/2the first putsxinG_n; forx > S_n/2, writeg = S_n - x < S_n/2, which by symmetry is missing fromP_nexactly whenxis, negative whenx > S_n; thenx - a_(n+1) = R_n - g, andx <= S_(n+1)/2reads2g >= R_n. - Proved (the jump). If
Trises atn, thenS_n - T_n + 2 <= T_(n+1) <= S_(n+1)/2 + 1andR_n <= 2 T_n - 2. IfR_n < T_n - 1 < S_n/2, thenTrises atn. Proof: the missing integers ofP_(n+1)up toS_n/2lie inG_n, belowT_n, so a rise is a birthT_(n+1) - 1 = S_n - gwithg <= T_n - 1, negative or inG_n, andR_n <= 2g; converselyg = T_n - 1, inG_nor-1, is belowS_n/2and aboveR_n, soR_n - g < 0andx = S_n - gis born, aboveS_n/2 > T_n - 1. - Proved (after a rise). If
Trises atn, thenR_(n+1) <= S_n <= 2 T_(n+1) - 2, so the interval step fails atn + 1; and the certificate at indexNcloses at least two steps after the last rise. Proof:R_(n+1) = S_n + a_(n+1) - a_(n+2) <= S_n, and2 T_(n+1) - 2 >= 2 S_n - 2 T_n + 2 >= S_nsince2 T_n <= S_n + 2. The certificate needsR_N >= 2 T_N - 1, from its first step or, when the surplus clause is already empty atN, from the surplus lemma, and no rise followsN, sinceP_ncontains[T_N, S_n - T_N]for everyn >= NandT_N - 1 = Fstays missing. - Proved (the route of
F). LetM_k(D)be complete andbthe step at whichF = F(D, k)is born,S_b < 2F <= S_(b+1), soF = S_b - gwithgas in the birth law. IfF >= a_(b+1), thenFcomes by the pair route. IfFcomes by the window route, thenF < a_(b+1),g > R_bandT_b - 1 > R_b. Proof: ifF >= a_(b+1), its indexj, witha_(j+1) <= F < a_(j+2), hasj >= b, andg = S_b - F >= 0since2F <= S_b + a_(b+1) <= S_b + F, soS_j - F >= g >= 0, the pair route. IfF < a_(b+1), theng = S_b - F > R_b, and eitherg >= 0lies inG_b, soT_b - 1 >= g > R_b, orR_b < g < 0 <= T_b. - Verified (verb
jumps 10 6 31 4,20.1s on4threads,W = 2^31): on every step of the173cells the run reaches, each minimal base set in[3, 10]fromk = 1up to its first level capped atW = 2^31, at most6, no rise breaks the bounds of the jump, no step withR_n < T_n - 1 < S_n/2fails to rise, and no step after a rise hasR_(n+1) > 2 T_(n+1) - 2. Over the145certified cells,F >= a_(b+1)in17, 27, 27, 26, 22, 2atk = 1..6, andFcomes by the window route in7, 1, 2, 0, 0, 0, each withT_b - 1 > R_b;Fis born at the last rise ofTin111; the certificate closes2, 3, 4, 5, 6steps after the last rise in61, 52, 27, 3, 2cells;Trises at every step from the entry of the last basemax d^kto its last rise in21, 23, 23, 24, 17, 2. - The falsification run:
T_n / a_(n+1)after the last base enters peaks at1.9430, at{3, 6, 7, 9, 10},k = 5, and every certified cell withk >= 2passes1.1727({3, 5, 8, 10},k = 3), so no boundT_n <= c a_(n+1)withc < 1.17holds 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 the28capped cells the run reaches,{3, 4, 5}atk = 6among them, has every rise ofTin one run still open at the cap, of28to37rises;{3, 4, 5}atk = 6stands at30. - So the deepest hole never creeps: it stays, falls, which needs
a_(n+1) <= T_n - 1to fillT_n - 1, or jumps past the middle ofP_n, and the step after a jump is never an interval step; the middle ofP_nstays holed while the births run. The pair route makesFin the26cells atk = 4and22atk = 5whereF >= a_(b+1)by the route lemma; the other4and1come by the pair route from an index belowb, which the lemma does not explain. Completeness needs a step that ends the run: by the jump, one withT_n - 1 <= R_nor2 T_n - 2 = S_nand no birth; whenT_n - 1 <= R_n, the birth law says no birth exactly whenR_nis no sumg + hof members ofG_nwithh <= g < S_n/2; then the certificate needsR_N >= 2 T_N - 1at some laterN. A proof uniform inkhas to produce that step, andEandVare built so that it never comes.
Problem 817 at n = 7
g_3(n)is the leastNsuch that[1, N]holds ann-setAwhose subset sums<A>,0included, contain no non-trivial 3-term progression; on the discussion thread, read at source, Korsky proves this equivalent to the3^nsumssum c_i a_i,c_iin{0, 1, 2}, being distinct, an admissible set, and the lower bound(T_n - 1)/2 + sum_(j < n) T_j,T_jthe central trinomial coefficient,419atn = 7; a later post givesg_3(n + 1) <= 3 g_3(n)throughA -> {1} U 3A, exact values1, 3, 8, 22, 60, 168ton = 6by exhaustive search, and419 <= g_3(7) <= 504. The powers of3are the base-3 design{0, 1}, admissible at everynand optimal only ton = 2.- The search picks the elements from the top down with the ternary sums as one bit array:
aextends a setHexactly whenaand2aavoid the differences of its sums, therelements still owed lie below the least chosen one, which must exceedg_3(r), and the variance(2/3) sum a_i^2of a uniform ternary sum is at least that of3^ndistinct integers,sum a_i^2 >= (9^n - 1)/8. - Verified (verb
ternary 6 200 8,5.9s on8threads, exhaustive):g_3(n) = 1, 3, 8, 22, 60, 168atn = 1..6, the thread's values, eachg_3(r)of the pruning computed by the run before it; the witness atn = 6is{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.8s):A = {302, 409, 447, 459, 465, 466, 474}is admissible, its2187ternary sums distinct and its128subset sums free of 3-term progressions, checked from the definition; sog_3(7) <= 474, past the thread's504, and with the thread's stepg_3(n) <= 474 3^(n - 7)forn >= 7,g_3(n)/3^n < 0.216736against the thread's0.2305. - Verified (verb
band 419 473 100 8,114s): no admissible 7-set with largest elementNin[419, 473]has its six largest elements in[N - 100, N], so a set beating474has a second-smallest element belowN - 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 reach477and475at best (verboffsets 420 504). - The exact value is a wall at this budget: the unrestricted search costs
36s atN = 380alone (verbprobe 7 380 8) and grows about fourfold per20, 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 everyk, the least base set outside every theorem whose proof is read here; checked atk <= 5with no derivation. A proof has to hold uniformly ink, while the only uniform tool read here, the two-part criterion, is dead belowsigma = 2. - Proved (the target as one inequality). If
1 < sigma(D) < 2, thenM_k(D)is complete exactly when somenhas2 T_n - 1 <= (sigma(D) - 1) a_(n+1) - C_k(D), withT_n = 1 + max{x <= S_n/2 : x not in P_n}. Proof: at such ann,T_n < a_(n+1)sincesigma - 1 < 1, and the surplus clause of the certificate is empty becausea_(m+1) >= a_(n+1)form >= n; conversely, along the steps of the gap proofT_n = F(D, k) + 1whilea_(n+1)grows without bound. - So a proof for
{3, 4, 5}, wheresigma - 1 = 1/12, is a bound uniform inkthat brings the deepest hole ofP_nbelow abouta_(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 everyFof the census fromk = 4on; the windowed lemma is refuted byV, whose windows open at every fifth step. Such a bound cannot hold while the births run: the step after a rise hasS_(n+1) - a_(n+2) <= 2 T_(n+1) - 2, so the one inequality fails there, every rise lands pastS_n/2, and every certified cell withk >= 2hasT_n > 1.17 a_(n+1)after its last base enters. Atsigma = 1the surplus is-Cand{3, 4, 7}stays apart.