ERDŐS/DAILY ▸

← back to the ledger

ERDőS #1204 · PARTIAL

Erdős problem #1204 — live audit, reduction, exact cases, and the Siegel-zero wall

Accessed 2026-07-29. All logarithms below are natural.

Claim labels

Status and bibliographic metadata are identified as source facts rather than mathematical claims.

0. Mandatory live-page audit

I fetched the live page through a Bright Data browser, not datacenter curl: erdosproblems.com/1204. I also fetched its “View the LaTeX source” endpoint. The page was last edited 07 April 2026 and displayed OPEN.

The current statement, copied verbatim from the page's LaTeX source, is:

We call a sequence of integers $0\leq a_1<\cdots <a_k$ admissible if it is missing at least one congruence class modulo every prime $p$. Let $A(k)=\min a_k$. Estimate $A(k)$ - in particular, is it true that \[A(k)\sim k\log k?\] Estimate \[B(k)=\min \frac{a_1+\cdots+a_k}{k}.\]

The live page reported all of the following:

Thus no claimed-proof/solved/falsified/current-worker skip condition was triggered.

Results listed on the live page

The following is a faithful mathematical summary of what the page lists. These are (b) where they invoke the named cited results.

  1. Erdős attributes the problem to Elliott. The bounds in Erdős's 1980 survey are misstated, but

\[ \left(\frac12+o(1)\right)k\log k \leq A(k)\leq (1+o(1))k\log k. \] The upper bound, attributed to Davenport, follows by taking the \(k\) smallest primes greater than \(k\). Elliott proved the lower bound. Hensley and Richards improved lower-order terms, and Section 10 of the Polymath paper gives details.

  1. The page says that the prime-tuples conjecture together with

\[ \pi(x+y)\leq \pi(x)+(1+o(1))\pi(y) \] would imply \(A(k)\geq(1+o(1))k\log k\).

  1. For the second objective, it records \(B(k)<A(k)\) (tacitly for \(k\geq2\), since both values are \(0\) at \(k=1\)), the prime construction

\[ B(k)\leq\left(\frac12+o(1)\right)k\log k, \] and \[ B(k)\geq \frac1k\sum_{j\leq k}A(j). \] Consequently, \(A(k)\geq(c-o(1))k\log k\) gives \(B(k)\geq(c/2-o(1))k\log k\). The page calls \(B(k)\sim\frac12k\log k\) likely.

  1. It also repeats Erdős's question about the greedy admissible sequence. The parenthetical definition on the live page says that \(a_{i+1}\) is the smallest integer \(>a_{i-1}\) for which \(a_1,\ldots,a_i\) is admissible. This has an apparent indexing omission. In the computation below, “greedy” means the natural intended rule: \(a_1=0\), and \(a_{i+1}\) is the least integer \(>a_i\) such that \(a_1,\ldots,a_i,a_{i+1}\) is admissible. This agrees with the initial terms in OEIS A135311.

1. Primary-source audit

I searched by the problem's definitions, \(A(k)\), \(B(k)\), “dense admissible sets/sequences,” “narrow admissible tuples,” and the cited authors. I inspected the following primary sources.

\[ H(k)\leq k\log k+k\log\log k-k+o(k), \] with the Hensley–Richards construction sharpening \(-k\) to \(-(1+\log 2)k\), and states that exact \(H(k)\) values were known through \(k=342\). (a) for \(H(k)=A(k)\); (b) for the quoted bounds and published computation.

\[ \pi(x)+(\log 2-o(1))\frac{x}{\log^2x} \leq \rho^*(x)\leq 2\pi(x), \] and gives exhaustive finite computations using two independently written programs. Clark and Jarvis, Dense admissible sequences, Math. Comp. 70 (2001), 1713–1718, DOI 10.1090/S0025-5718-01-01348-5, continues this finite-density line. (b)

\[ (2+o(1))\frac{y}{\log y} \] elements. Granville explicitly says such zeros are not believed to exist. (b)

Targeted searches did not locate a published exact table for the minimum-sum quantity \(B(k)\), nor a theorem that the natural greedy prefixes minimize it. This is only a search miss, not a claim that no such source exists. (c)

2. Two elementary reductions

2.1 Translation, reflection, and an exact inequality

Every admissible tuple can be translated by \(-a_1\). This preserves all occupied residue counts, keeps every coordinate nonnegative, and weakly decreases both objectives. Hence an optimum for either problem has \(a_1=0\), and \(A(k)\) is exactly the least possible diameter. (a)

If

\[ S=\{0=a_1<a_2<\cdots<a_k=d\} \]

is admissible, its reflection

\[ S^*=\{d-a_k,d-a_{k-1},\ldots,d-a_1\} \]

is also normalized and admissible. The two coordinate sums satisfy

\[ \sum_{a\in S}a+\sum_{a\in S^*}a=kd. \]

At least one orientation therefore has mean at most \(d/2\). Applying this to an \(A(k)\)-optimal tuple gives the exact strengthening

\[ \boxed{B(k)\leq \frac{A(k)}2.} \]

This inequality is not stated on the live page. (a)

2.2 Density inverse

Define

\[ R(y)=\max\{|S|:S\subseteq\{0,1,\ldots,y\},\ S\text{ admissible}\}. \]

Translation invariance and the definition of diameter give the exact generalized-inverse identity

\[ \boxed{A(k)=\min\{y:R(y)\geq k\}.} \]

Thus the unresolved constant in \(A(k)\) is precisely the unresolved leading density constant for the largest admissible subset of an interval. Standard monotone inversion shows that

\[ A(k)\sim k\log k \quad\Longleftrightarrow\quad R(y)\sim \frac{y}{\log y}. \]

(a)

3. A conditional consequence of Granville's theorem

This subsection is a deduction from Granville's Corollary 3; it does not assert that Siegel zeros exist.

Proposition

If there are infinitely many Siegel zeros, then

\[ \boxed{\liminf_{k\to\infty}\frac{A(k)}{k\log k}=\frac12} \qquad\text{and}\qquad \boxed{\liminf_{k\to\infty}\frac{B(k)}{k\log k}=\frac14.} \]

In particular, under that hypothesis, both asymptotic constants suggested on the live page are false. (b)

Proof

Granville supplies a sequence \(y\to\infty\) and admissible sets \(S_y\) of length at most \(y\) with

\[ k_y:=|S_y|\sim \frac{2y}{\log y}. \]

Consequently \(k_y\to\infty\), \(\log k_y\sim\log y\), and

\[ k_y\log k_y\sim 2y. \]

The density-inverse identity yields \(A(k_y)\leq y\), so

\[ \limsup_y\frac{A(k_y)}{k_y\log k_y}\leq\frac12. \]

Elliott's unconditional lower bound gives

\[ \liminf_{k\to\infty}\frac{A(k)}{k\log k}\geq\frac12, \]

which proves the first equality. (b)

For \(B\), translate \(S_y\) to have minimum zero and use whichever of it and its reflection has smaller mean. The reflection lemma gives

\[ B(k_y)\leq\frac y2, \]

and hence an upper subsequential ratio \(1/4\). On the other hand, every prefix of a normalized admissible tuple is admissible, so \(a_j\geq A(j)\), and

\[ B(k)\geq\frac1k\sum_{j\leq k}A(j) \geq\left(\frac14-o(1)\right)k\log k \]

by Elliott's lower bound and elementary summation. This proves the second equality. (a) for the prefix/reflection deductions; (b) for the conclusion using Elliott and Granville.

The quantifier here is only a liminf. Granville gives arbitrarily large exceptional lengths, not a uniform density asymptotic, so this argument makes no claim about either limsup. (b)

4. Exact finite reduction for both objectives

The supplied verifier uses the following exact reduction.

Residue-vector lemma

For fixed \(k\), let \(P_k=\{p:p\leq k,\ p\text{ prime}\}\). For every vector

\[ \mathbf r=(r_p)_{p\in P_k},\qquad 1\leq r_p<p, \]

write the nonnegative integers avoiding those residues as

\[ 0=u_1(\mathbf r)<u_2(\mathbf r)<\cdots,\qquad u_i(\mathbf r)\not\equiv r_p\pmod p. \]

Then

\[ \boxed{A(k)=\min_{\mathbf r}u_k(\mathbf r)} \]

and

\[ \boxed{kB(k)=\min_{\mathbf r}\sum_{i=1}^k u_i(\mathbf r).} \]

(a)

To prove it, normalize an arbitrary admissible tuple so that it contains \(0\). For each \(p\leq k\), choose a residue class it misses. That residue is nonzero because \(0\) is in the tuple. Its \(i\)-th coordinate is at least the \(i\)-th survivor \(u_i(\mathbf r)\), giving both lower comparisons.

Conversely, the first \(k\) survivors miss \(r_p\) for every \(p\leq k\). A prime \(p>k\) has more residue classes than the tuple has elements, so it too has a missing class. Thus those survivors form an admissible tuple and both displayed minima are attained. (a)

This lemma reduces an infinite search over integer tuples to exactly

\[ \prod_{p\leq k}(p-1) \]

finite residue assignments. It also explains why \(p=k\), when \(k\) is prime, must not be omitted from the search. (a)

5. Exhaustive computation for \(1\leq k\leq22\)

The standalone verifier is:

runs/erdos1204_wavew038_reverify.py

Run:

python3 runs/erdos1204_wavew038_reverify.py --max-k 22 --audit

It uses only the Python standard library. The completed audit on this VM reported:

reverse-prime-order bitset audit: MATCH
independent scalar audit through k=16: MATCH
canonical SHA256: b4f432ce4ba589017713f6466d3784bf005728c52d19713350ab58a7dd1129ee
elapsed seconds: 31.037
ALL CHECKS PASSED

The source file's SHA-256 after that run was d302d42fcb68d5af9c2e8659b8eb34f486b6cdab5ceca0a47d8c039f90f6b8c5. These are reproducibility records, not formal certificates. (d)

Audit design

The main engine intersects integer bitsets for every residue vector. Consecutive \(k\)'s with the same relevant prime frontier are handled together. The complete leaf counts were:

| targets \(k\) | residue assignments | |---:|---:| | 1 | 1 | | 2 | 1 | | 3–4 | 2 | | 5–6 | 8 | | 7–10 | 48 | | 11–12 | 480 | | 13–16 | 5,760 | | 17–18 | 92,160 | | 19–22 | 1,658,880 |

The finite bitset cutoff is rigorous: start with any valid incumbent. A tuple that strictly improves \(A(k)\) has its \(k\)-th coordinate below the incumbent diameter; a tuple that strictly improves the sum has every nonnegative coordinate below the incumbent sum. Taking the largest incumbent sum in the current group therefore cannot discard an improvement. (a)

The --audit option:

  1. repeats the full bitset enumeration with the prime order reversed;
  2. recomputes every case through \(k=16\) using a separately coded scalar itertools.product search and direct remainder tests;
  3. directly checks each saved tuple against every prime through its largest coordinate;
  4. regenerates its first \(k\) survivors from the saved omitted residues;
  5. checks reflection admissibility and the sum identity;
  6. constructs the greedy sequence independently by testing every skipped integer.

The two full bitset passes agree through \(k=22\), the structurally different scalar pass agrees through \(k=16\), and all direct witness checks pass. (d)

Exact table

The following values are the exhaustive output. The \(A(k)\) column is a control against the previously known narrow-tuple values; the \(B(k)\) column is the part not found in the targeted literature search. (d)

| \(k\) | \(A(k)\) | \(kB(k)\) | \(B(k)\) | |---:|---:|---:|---:| | 1 | 0 | 0 | 0 | | 2 | 2 | 2 | 1 | | 3 | 6 | 8 | \(8/3\) | | 4 | 8 | 16 | 4 | | 5 | 12 | 28 | \(28/5\) | | 6 | 16 | 46 | \(23/3\) | | 7 | 20 | 66 | \(66/7\) | | 8 | 26 | 92 | \(23/2\) | | 9 | 30 | 122 | \(122/9\) | | 10 | 32 | 154 | \(77/5\) | | 11 | 36 | 190 | \(190/11\) | | 12 | 42 | 232 | \(58/3\) | | 13 | 48 | 280 | \(280/13\) | | 14 | 50 | 330 | \(165/7\) | | 15 | 56 | 386 | \(386/15\) | | 16 | 60 | 448 | 28 | | 17 | 66 | 516 | \(516/17\) | | 18 | 70 | 588 | \(98/3\) | | 19 | 76 | 666 | \(666/19\) | | 20 | 80 | 752 | \(188/5\) | | 21 | 84 | 842 | \(842/21\) | | 22 | 90 | 938 | \(469/11\) |

For every \(1\leq k\leq22\), a \(B(k)\)-optimal tuple is the first \(k\) terms of

\[ \begin{split} G={}&(0,2,6,8,12,18,20,26,30,32,36,42,48,50,56,62,\\ &68,72,78,86,90,96). \end{split} \]

Thus the natural greedy prefix minimizes the sum through \(k=22\). This does not prove it for all \(k\), and it does not assert uniqueness of the minimizer. (d)

The objectives already diverge at \(k=6\):

\[ A(6)=16,\qquad 6B(6)=0+2+6+8+12+18=46. \]

The saved endpoint-optimal witness is \((0,4,6,10,12,16)\), whose sum is \(48\), while the saved sum-optimal witness is \((0,2,6,8,12,18)\), whose endpoint is \(18\). So an endpoint-optimal tuple need not be sum-optimal, and the greedy tuple is already not endpoint-optimal at \(k=6\). (d)

Passing --json prints full \(A\)- and \(B\)-witnesses. The hard-coded canonical digest covers the complete table and those witnesses, so accidental changes to the output fail loudly. (d)

6. Computation boundary

The factor introduced by the next prime is the obstruction to extending the plain exhaustive method:

\[ \begin{array}{c|r} \text{prime frontier}&\prod_{p\leq k}(p-1)\\ \hline 19&1,658,880\\ 23&36,495,360\\ 29&1,021,870,080 \end{array} \]

The \(1.66\)-million-assignment group took roughly 14–15 seconds per bitset pass inside the 31-second double audit, about \(1.1\times10^5\) assignments/second. A linear extrapolation gives approximately 5.5 minutes for one \(k=23\) pass, 11 minutes for its two-order audit, and 2.5–2.7 core-hours for one \(k=29\) pass. I did not run these because the task limits computation to a few CPU-minutes. A compiled implementation with symmetry breaking or branch-and-bound is the appropriate next finite-computation step. (d) for the measured rate; (c) for the linear cost projection.

7. Exact remaining wall

The asymptotic problem is not closed here.

In the density language, the exact missing analytic statement is

\[ \boxed{R(y)\leq(1+o(1))\frac{y}{\log y}.} \]

Together with the standard construction and monotone inversion, this would prove \(A(k)\sim k\log k\). The page's summation inequality would then also force \(B(k)\sim\frac12k\log k\). (a) for these implications.

The present unconditional sieve upper bound has leading constant \(2\), equivalent to Elliott's leading constant \(1/2\) after inversion. Granville's Corollary 3 shows why standard linear-sieve machinery cannot simply be sharpened uniformly: if infinitely many Siegel zeros exist, the constant \(2\) is attained along arbitrarily large lengths. Indeed, even any uniform improvement

\[ R(y)\leq(2-\eta)\frac{y}{\log y} \quad(\eta>0) \]

for all sufficiently large \(y\) would rule out infinitely many Siegel zeros. (b)

Therefore the exact wall is not a missing finite search or a routine optimization. It is a parity/exceptional-zero-sensitive density lemma improving the linear-sieve constant from \(2\) to \(1\). The finite computation supplies exact \(B\)-data and a testable greedy pattern, but it has no uniform mechanism for that analytic step. No unconditional proof of the requested asymptotics, and no counterexample absent the Siegel-zero hypothesis, is claimed. (b) for the obstruction furnished by Granville; (c) for the assessment that the finite pattern alone offers no uniform mechanism.

PARTIAL: proved the residue-vector and reflection reductions, exhaustively verified \(A(k)\), \(B(k)\), and greedy \(B\)-optimality for \(1\leq k\leq22\), and derived conditional liminf constants \(1/2\) and \(1/4\) from Granville; the unconditional asymptotics remain open.

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