Erdoes #341 - working report - Erdős Problem a Day

Erdős problem 341 — finite periodicity certificates and an exact small-seed boundary

Date: 2026-07-28 (UTC)

Outcome

The general problem is not solved here. The verified progress is:

1. [a] An elementary finite certificate is proved below. For a proposed

indicator period $q$ beginning at $N$, it is enough to check the greedy

recurrence through $2N+q-2$ and one identity in

$\mathbb Z/q\mathbb Z$. This converts a detected period into an

all-future proof.

2. [d] For the page's example $A=\{1,4,9,16,25\}$, the comment posted

in July 2026 is correct for the stated rule. More precisely, the indicator

has minimal period $1176$ from the minimal integer onset $426$.

There are $224$ selected residues, and

\[ a_{n+224}=a_n+1176\qquad(n\geq 87), \]

with $a_{87}=440$. Thus periodicity starts after 86 terms, not after

thousands of terms, under the rule which allows $i=j$.

3. [d] Every nonempty seed contained in $[12]$, except

\[ E=\{1,4,8,10,11,12\}, \]

has an all-future finite certificate. This is $4094$ certified seeds out

of $4095$, including all $2047$ nonempty seeds contained in $[11]$.

4. [d] One seed that initially looked exceptional,

$\{1,2,7,8,10,11,12\}$, has minimal indicator period $2039$, but only

from integer $95787$. Its certificate checks through $193611$.

5. [d] For the sole remaining seed $E$, exact computation through

$500000$ proves that no modulus $q\leq 20000$ can have onset at or

before $479993$. This is not a proof of aperiodicity.

Claim labels used throughout:

[a] elementary-rigorous;
[b] rigorous modulo a named published theorem;
[c] plausible/structural-unverified;
[d] computational-only (but exactly reproducible and, where stated,

coupled to the proved finite certificate).

Step 0: live-page audit (performed before mathematics)

I fetched both the live problem page and its discussion thread through the

Bright Data browser, not datacenter curl.

Live page: Erdős problem 341, accessed

2026-07-28.

Status: OPEN.
Last edited: 20 January 2026.
Claimed proofs: 0.
Comments: 1.
“Currently working on this problem”: None.
“Interested in collaborating”: None.
The other displayed markers (“likes”, “looks difficult”, “looks

tractable”, “could be formalisable”, and “working on formalising”) all say

None.

“Formalised statement?” says Yes.

Therefore neither mandatory stop condition (claimed proof/solved/falsified,

or a current worker) applied.

The one live comment is by

KentaKitamura, timestamped 13:15 on 8 July 2026.

It reports that for $\{1,4,9,16,25\}$ the periodic term relation starts at

$a_{87}=440$, with 224 terms and translation 1176:

\[ a_{n+224}=a_n+1176\quad(n\geq87). \]

It gives the two six-term samples

$[440,443,445,448,453,471]$ and

$[1616,1619,1621,1624,1629,1647]$, plus a Colab link. The forum explicitly

warns that comments are unverified. The computation below independently

reconstructs and certifies this claim; it does not use the Colab.

Verbatim live statement

> Let \(A=\{a_1<\cdots

The live page's accompanying note says:

> An old problem of Dickson. Even a starting set as small as $\{1,4,9,16,25\}$ requires thousands of terms before periodicity occurs.

It also points to Problem 7 of Green's open-problems list.

Literature check

I searched by the exact recurrence, “Dickson”, “0-additive”, “greedy

sum-free”, the named example, and the candidate bases below. I verified these

primary sources:

1. Erdős and Graham,

Old and New Problems and Results in Combinatorial Number Theory,

p. 53, gives the same Dickson question and the

$\{1,4,9,16,25\}$ remark.

2. The current copy of Ben Green's

100 Open Problems,

Problem 7, says that both the Dickson rule ($i,j\leq n$) and Queneau's

distinct-index variant still appear open.

3. Calkin and Finch,

“Conditions on Periodicity for Sum-Free Sets”,

Experimental Mathematics 5 (1996), 131–137, gives finite sufficient

conditions for periodicity and computationally screens 76,080 sum-free

bases with largest element at most 27, as well as bases of at most three

elements up to 35. It lists apparently aperiodic complete examples such as

$\{8,18,30\}$, $\{8,27,32\}$, $\{9,16,29\}$, and

$\{9,26,32\}$, checked through $10^7$, without proving

aperiodicity.

4. Calkin, Finch, and Flowers,

“Difference Density and Aperiodic Sum-Free Sets”,

Integers 5(2) (2005), A03, pushes three related periodic-decision

examples through 50 million and explicitly says the finite evidence still

does not prove aperiodicity. Those examples concern Cameron's broader

binary-decision correspondence and are not themselves finite-seed

counterexamples to problem 341.

5. Calkin and Erdős,

“On a Class of Aperiodic Sum-Free Sets”,

Math. Proc. Cambridge Philos. Soc. 120 (1996), 1–5, proves that a

natural class of already-known aperiodic sum-free sets is incomplete, so

that route does not manufacture a greedy-complete counterexample.

The Calkin–Finch literature normally starts with a sum-free base. The live

problem, however, permits an arbitrary finite set. For example,

$\{1,4,9,16,25\}$ is not sum-free because $9+16=25$. The certificate

below deliberately handles arbitrary seeds and imposes the greedy

equivalence only after the largest prescribed seed element.

I found no primary source claiming a resolution after the 2005 work; the

current Green list and the live page both retain open status. This is a

reported search miss, not a claim of a complete bibliography.

Reformulation

For a seed $A$, let $S$ be the final selected set and let

$b(x)=1_S(x)$. Put $M=\max A$. Positivity implies that, for every

$x>M$,

\[ b(x)=1 \quad\Longleftrightarrow\quad x\notin S+S. \tag{1} \]

Indeed, when $x$ is considered, all positive summands of $x$ are smaller

than $x$, and no later selection can create a new representation of $x$.

The values at or below $M$ are prescribed and need not obey (1).

Eventual periodicity of the membership indicator and eventual periodicity of

the consecutive gaps are equivalent. If a membership block of length $q$

contains $h$ selected integers, then

\[ a_{n+h}=a_n+q \]

throughout the corresponding tail, so the gap word has period $h$.

Finite all-future certificate

Lemma [a]

Let $N>M$, $q\geq1$, and let $T\subset\mathbb N$ have the proposed

form

\[ T=P\ \cup\ \{x\geq N:x\bmod q\in R\},\qquad P\subset[1,N-1],\quad R\subset\mathbb Z/q\mathbb Z. \]

Let

\[ E=(P\bmod q)\cup R. \]

Suppose:

1. $T\cap[1,M]=A$;

2. (1) holds for $T$ for every

\(M

3. in $\mathbb Z/q\mathbb Z$,

\[ E+R=(\mathbb Z/q\mathbb Z)\setminus R. \tag{2} \]

Then $T$ is exactly the infinite greedy extension of $A$, and its

indicator is $q$-periodic from $N$.

Proof

Take $x\geq2N+q-1$. Two elements of $P$ sum to at most $2N-2$, so

every representation $x=u+v$ with $u,v\in T$ has a tail summand. Its

residue lies in $R$, while the other summand's residue lies in $E$.

Thus

\[ x\in T+T\quad\Longrightarrow\quad x\bmod q\in E+R. \]

Conversely, suppose $x\bmod q=e+r$, where $e\in E$ and $r\in R$.

If $e$ is represented by some $p\in P$, then $x-p\geq N$ and

$(x-p)\bmod q=r$, so $x=p+(x-p)\in T+T$. Otherwise $e\in R$;

choose the representative $u\in[N,N+q-1]$ of residue $e$. Then

$x-u\geq N$, has residue $r$, and again $x\in T+T$. Therefore

\[ x\in T+T\quad\Longleftrightarrow\quad x\bmod q\in E+R \qquad(x\geq2N+q-1). \]

Condition (2) is exactly (1) in this range. Condition 2 handles every

smaller value after the seed. Finally, (1) determines membership

successively for $x=M+1,M+2,\ldots$, so $T$ is the unique greedy

extension. $\square$

The cutoff $2N+q-2$ is conservative but explicit. The search for a repeated

suffix is only a way to propose $(N,q)$; it is never accepted as proof.

Exact closed form for $\{1,4,9,16,25\}$

Let $S$ be its greedy extension under the live statement. The certified

closed form is

\[ S=P\ \cup\ \{n\geq426:n\bmod1176\in R\}, \tag{3} \]

where

P = {1,4,9,16,25,27,30,33,35,38,40,45,48,53,59,74,77,79,82,87,
     100,105,108,111,113,123,126,128,131,134,152,157,160,162,165,
     175,180,183,186,194,201,204,206,209,212,214,235,238,240,243,
     248,255,258,261,266,269,272,279,284,287,292,313,316,318,321,
     326,333,336,339,344,347,357,362,365,367,370,391,396,399,401,
     404,409,411,414,419,422}

and, using residues $0,\ldots,1175$,

R = {1,4,9,30,33,35,38,43,45,48,53,56,74,77,79,82,87,105,108,111,
     113,116,123,126,128,131,134,152,157,160,162,165,180,183,186,
     191,194,201,204,206,209,212,214,235,238,240,243,248,258,261,
     266,269,272,279,284,287,292,313,316,318,321,326,333,336,339,
     344,347,350,357,362,365,367,370,391,396,399,401,404,411,414,
     419,422,425,440,443,445,448,453,471,474,477,479,482,489,492,
     494,497,500,518,523,526,531,546,549,552,557,560,567,570,572,
     575,578,580,601,604,606,609,614,624,627,635,638,645,648,650,
     653,658,679,682,684,687,692,699,702,705,710,713,716,723,728,
     731,733,736,757,762,765,767,770,777,780,785,788,791,806,809,
     811,814,819,837,840,843,845,848,855,858,863,866,884,887,889,
     892,897,915,918,921,923,926,933,936,938,941,944,962,967,970,
     972,975,990,993,996,1001,1004,1011,1014,1016,1019,1024,1045,
     1048,1050,1053,1058,1065,1068,1071,1076,1079,1082,1089,1094,
     1097,1102,1123,1128,1131,1136,1143,1146,1149,1151,1154,1157,
     1172,1175}.

Here $|P|=86$, $|R|=224$, and

\[ |E|=233,\qquad |E+R|=952,\qquad (E+R)\cap R=\varnothing. \]

Thus $E+R$ is exactly the 952-element complement of $R$.

The finite recurrence was independently recomputed through

\[ 2(426)+1176-2=2026. \]

The indicator onset is minimal because

\[ 1_S(425)=0,\qquad 1_S(425+1176)=1. \]

The script tests every divisor of $1176=2^3\cdot3\cdot7^2$; no proper

divisor preserves the periodic block, so 1176 is the minimal eventual

membership period. This divisor test is sufficient because the gcd of two

eventual periods of a binary sequence is again an eventual period; hence the

minimal eventual period divides every accepted period. Consequently the

224-term gap period is also minimal.

The first tail member is $a_{87}=440$, and

\[ \begin{aligned} (a_{87},\ldots,a_{92})&=(440,443,445,448,453,471),\\ (a_{311},\ldots,a_{316})&=(1616,1619,1621,1624,1629,1647). \end{aligned} \]

The translation fails one term earlier:

$a_{86}=422$, $a_{310}=1601$, and $1601\neq422+1176$.

This proves that the term relation begins exactly at index 87.

Packed membership bits through 2026 have SHA-256

8be3f4662a10f1761cd8f0562dc73ee63d1972c96673523ecfaab600c069bbfc

Exhaustive certified computation for seeds in $[12]$

For every bit mask from 1 through $2^{12}-1$, the checker constructs the

corresponding nonempty seed. Candidate suffixes are accepted only after the

lemma's finite recurrence and residue identity both pass. It then reduces the

period by checking all divisors and scans backward to obtain the minimal

indicator onset.

Rows below are grouped by the exact value $m=\max A$, so there are

$2^{m-1}$ seeds in a full row. “Maximum check end” is the largest

$2N+q-2$ used by any accepted certificate in that row.

|---:|---:|---|---|---:|

| 1 | 1 / 1 | 2, $\{1\}$ | 1, $\{1\}$ | 4 |

| 2 | 2 / 2 | 5, $\{2\}$ | 2, $\{1,2\}$ | 9 |

| 3 | 4 / 4 | 8, $\{3\}$ | 3, $\{1,2,3\}$ | 14 |

| 4 | 8 / 8 | 12, $\{1,3,4\}$ | 4, $\{1,3,4\}$ | 20 |

| 5 | 16 / 16 | 14, $\{5\}$ | 9, $\{1,2,4,5\}$ | 24 |

| 6 | 32 / 32 | 23, $\{1,6\}$ | 10, $\{1,2,3,5,6\}$ | 35 |

| 7 | 64 / 64 | 28, $\{2,5,7\}$ | 15, $\{1,4,6,7\}$ | 42 |

| 8 | 128 / 128 | 87, $\{1,4,6,7,8\}$ | 21, $\{3,8\}$ | 103 |

| 9 | 256 / 256 | 75, $\{2,6,7,9\}$ | 39, $\{1,3,4,6,8,9\}$ | 98 |

| 10 | 512 / 512 | 179, $\{3,7,10\}$ | 49, $\{4,6,7,8,10\}$ | 199 |

| 11 | 1024 / 1024 | 602, $\{2,3,8,9,10,11\}$ | 160, same seed | 920 |

| 12 | 2047 / 2048 | 2039, $\{1,2,7,8,10,11,12\}$ | 95787, same seed | 193611 |

The slow row-12 certificate has 204 selected residues, so its consecutive-gap

word has period 204. This example is a useful control against treating a long

transient as aperiodicity.

The deterministic ledger contains, for each of the 4094 certified seeds,

seed | minimal indicator onset | minimal modulus | terms per period |
proof onset | finite check end

Its SHA-256 is

3300f14718889d6d153642a55218862d408185c561d949e0aa6c2e67fc34eca8

Exact bounded wall for the last seed

For

\[ E=\{1,4,8,10,11,12\}, \]

the exact greedy indicator through $500000$ contains 77,579 selected

integers and has largest observed gap 23. For each

$1\leq q\leq20000$, the checker computes the final

$n\leq500000-q$ with $b(n)\neq b(n+q)$. The minimum of these final

mismatches is

\[ \min_{1\leq q\leq20000} \max\{n\leq500000-q:b(n)\neq b(n+q)\}=479993, \]

attained at $q=19990$. Therefore:

> [d] No modulus $q\leq20000$ is a period beginning at any

> $N\leq479993$.

The packed membership bits through 500000 have SHA-256

3a045efefd9edd5c74813c40d09c592abb8bea461daba7da9f4f156a94d60aa9

This finite statement does not imply that $E$ is aperiodic: its period

could exceed 20000, or a smaller period could begin after 479993.

Calling it a counterexample would be invalid.

Exact missing step

For this one seed, a positive resolution now requires a pair $(N,q)$ whose

finite certificate passes. A negative resolution requires the genuinely

uniform assertion

\[ \forall q\geq1\ \forall N\ \exists n\geq N: b(n)\neq b(n+q). \]

The bounded computation supplies neither quantifier over all $q$ nor all

$N$.

For the original problem, even certifying all seeds in every fixed box would

not give the required uniformity over arbitrary finite seeds. A positive

solution needs an a priori mechanism bounding or producing $N,q$ from the

seed. The finite-certificate lemma is a semidecision procedure for periodic

instances, but supplies no such bound.

On this VM the exceptional seed through 500000 took about 3.75 seconds on one

core. The present big-integer algorithm is empirically quadratic in the

range. A naive extrapolation to $10^7$ is about 0.4–1 core-hour

(roughly \$0.02–\$0.05 at \$0.05/core-hour), and to $10^8$ about

40–100 core-hours (\$2–\$5). I did not run either: without a detected

certificate, more finite terms would still not settle the quantifiers above.

Reverification code

Standalone checker:

erdos341_wave8u_reverify.py

Run from the repository root:

PYTHONHASHSEED=1 python3 -m py_compile runs/erdos341_wave8u_reverify.py
PYTHONHASHSEED=1 python3 runs/erdos341_wave8u_reverify.py

It uses only the Python standard library and completed in 16.17 seconds in

the final run. It performs all of the following from scratch:

1. cross-checks the bit-parallel generator against an independent set-based

generator for all 255 nonempty seeds in $[8]$ through 128;

2. reconstructs the square-seed closed form;

3. recomputes all pair sums for every certificate;

4. checks the finite greedy equivalence and the residue identity;

5. checks minimal periods and minimal onsets;

6. exhausts all 4095 nonempty seeds in $[12]$;

7. runs the bounded mismatch scan for the one remaining seed.

The key generator update is:

chosen = sum(1 << a for a in seed)
for a in seed:
    forbidden |= chosen << a
for n in range(max(seed) + 1, limit + 1):
    if (forbidden & (1 << n)) == 0:
        chosen |= 1 << n
        forbidden |= chosen << n

After choosing $n$, shifting chosen by $n$ marks every sum $n+s$,

including $n+n$. The separate certificate routine constructs the proposed

periodic set, recomputes its pair-sum bitset, checks through

$2N+q-2$, and verifies $E+R=(\mathbb Z/q\mathbb Z)\setminus R$.

Final checker source SHA-256:

a86ae12f06b203a69b8cd1e6ceec6615b5a7977510c8c03af9c7dc17003470ed

PARTIAL: proved an elementary all-future certificate, certified the exact 1176/224 square-seed tail and 4094 of 4095 seeds in [12], with one precisely bounded unresolved seed.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger