Diameter of admissible k-tuples: is $A(k)\sim k\log k$? (and estimate the mean $B(k)$) (Erdős #1204)
Statement
Call a sequence of integers $0\leq a_1<a_2<\cdots<a_k$ admissible if it misses at least one congruence class modulo every prime $p$ (equivalently, for each prime $p$ the residues $a_1,\ldots,a_k$ do not cover all of $\mathbb{Z}/p\mathbb{Z}$). Let $A(k)=\min a_k$ be the least possible value of the largest element over all admissible $k$-term sequences — equivalently the minimal diameter of an admissible $k$-tuple based at $0$. Estimate $A(k)$; in particular, is it true that $$A(k)\sim k\log k?$$ Estimate also the minimal average $$B(k)=\min \frac{a_1+a_2+\cdots+a_k}{k}$$ over admissible $k$-term sequences.
Acceptance. FULLY RESOLVES: a proof (machine-checkable in Lean/Coq preferred, else a complete written proof) determining the asymptotics of $A(k)$ — in particular establishing or refuting $A(k)\sim k\log k$ — together with a corresponding asymptotic for $B(k)$. ADVANCES: (a) improve the multiplicative constant beyond the range stated in the background — prove $A(k)\geq(c-o(1))k\log k$ with $c$ strictly greater than $1/2$, or $A(k)\leq(c-o(1))k\log k$ with $c$ strictly less than $1$, with proof; (b) extend the exact values of $A(k)$ in OEIS A008407 to new $k$, supplying the search program and a reproducible certificate that each new value is minimal (no admissible $k$-tuple of smaller diameter exists); (c) prove an asymptotic or improved constant bound for $B(k)$ sharpening $B(k)\leq(1/2+o(1))k\log k$ or the matching lower bound; (d) determine the growth rate of the greedy admissible sequence, with proof. NEVER accept numerics alone as resolving the asymptotic. Deliver the proof file, or the search code plus certified new $A(k)$ values, or the improved-constant proof.
Background
Posed by Erdős [Er80, p.108], who attributes it to Elliott. Admissibility is exactly the local obstruction in the prime $k$-tuples conjecture, so $A(k)$ is the minimal diameter of an admissible $k$-tuple — the width of the narrowest possible prime constellation of $k$ primes, a quantity central to the bounded-gaps-between-primes program. Known frontier: $(1/2+o(1))k\log k \leq A(k)\leq (1+o(1))k\log k$. The upper bound is due to Davenport and follows by taking the $k$ smallest primes exceeding $k$. The lower bound is originally Elliott [El65] and was rediscovered by the Polymath8 project [Po14c]; its lower-order terms were sharpened by Hensley and Richards [HeRi73] (see Section 10 of [Po14c]). Combining the prime tuples conjecture with the (also open) inequality $\pi(x+y)\leq\pi(x)+(1+o(1))\pi(y)$ (Erdős #855, erdosproblems.com/855) would give $A(k)\geq(1+o(1))k\log k$, hence the conjectured $A(k)\sim k\log k$. For the average: trivially $B(k)<A(k)$; the first $k$ primes above $k$ give $B(k)\leq(1/2+o(1))k\log k$, and since $a_j\geq A(j)$ one gets $B(k)\geq\frac1k\sum_{j\leq k}A(j)$, so if $A(k)\geq(c-o(1))k\log k$ then $B(k)\geq(c/2-o(1))k\log k$ — making $B(k)\sim(1/2)k\log k$ likely. Erdős [Er80] also asks about the growth of the greedy admissible sequence ($a_1=0$, each $a_{i+1}$ the least integer keeping the tuple admissible). Exact values of $A(k)$ are tabulated in OEIS A008407 (minimal diameter of an admissible $k$-tuple). Listed as open on erdosproblems.com/1204 (fetched 2026-07-21, status 'open', tagged 'number theory'). No prize is recorded. Attacker's tool: exact computation of $A(k)$ via constrained search / integer programming over residue-class avoidance, extending OEIS A008407 and testing the ratio $A(k)/(k\log k)$ numerically, together with sieve-theoretic analysis to close the constant gap between $1/2$ and $1$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1204 (T. F. Bloom) | website |
| REF-02 | OEIS A008407 — minimal diameter of an admissible k-tuple, i.e. A(k) | website |
| REF-03 | OEIS A023193 — related admissible-tuple / prime-constellation counting function | website |
| REF-04 | OEIS A135311 — related sequence on admissible tuples (per erdosproblems.com/1204) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.