A New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond $N^{4/3}$
cs.CC · cs.DS · cs.LG
Quick verdict
RL-discovered Shellsort gap sequence narrowly beats Tokuda/Ciura on 25 large tasks; sub-4/3 proof is careful but its added gaps exist only past 10^1000.
Summary
The paper uses reinforcement-learning-guided program search to discover a Shellsort gap sequence. Candidates are executable generator programs evaluated by exact comparison and move counts over a fixed task panel; no classical sequence is used as a target. Five independent searches converge on rounded-geometric generators; tuning the eight-gap prefix yields 1, 3, 8, 20, 47, 116, 300, 585, 1416, 3303, ... with exact rational backbone h_t = floor(α(A/B)^t), A/B = 582942583375009/250000000000000. On 25 test tasks with 10^7 < N ≤ 10^8, the frozen sequence attains the lowest geometric-mean operation count among seven classical baselines, though the margins over Tokuda (0.079%) and Ciura (0.086%) are tiny, obtained from a single test seed with no variance reported. Theoretically, adding a zero-density set of unit companions h_s+1 — all beyond 10^1000, hence never executed in practice — enables a worst-case upper bound O(N^β polylog N) with β = 1.024296451657..., below Sedgewick's N^{4/3}; the matching Ω(N^β) lower bound is imported from an unrefereed 2026 preprint by Zang. The proof via compound numerical semigroups is detailed and internally consistent, but the asymptotic guarantee applies to a sequence that no practical run will ever execute.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 3
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Five independent RL-guided searches over executable gap-generator programs, trained only on exact Shellsort execution costs, converge on rounded-geometric generators (ratios 2.2490–2.3619) with no classical sequence as target.
- The frozen tuned sequence 1, 3, 8, 20, 47, 116, 300, 585, 1416, 3303, … with backbone h_t = ⌊α(A/B)^t⌋ achieves the lowest equal-task geometric-mean operation count among seven classical baselines on 25 tasks with 10^7 < N ≤ 10^8.
- Appending a zero-density set of unit companions h_s+1, all beyond 10^1000, yields worst-case T(N) = O(N^β polylog N) with β = 1.024296451657…, the first sub-N^{4/3} bound for a short sparse practical-style sequence.
- Zang's 2026 lower-bound theorem applies to the completed sequence and gives a matching Ω(N^β), so the polynomial exponent is tight up to polylogarithmic factors.
Strengths
Arithmetic core is internally consistent and machine-checkable
Independent recomputation confirms every constant: R = 2.33177033…, the tail h_t = ⌊αR^t⌋ reproduces 1, 3, 8, 20, 47, 111, 260, 607, 1416, 3303, 7703, 17963 exactly (§3.1, Eq. 4), κ = 0.02490146899… yields β = 2 − 1/(1+κ) = 1.02429645165747606869… (Eq. 28), and Zang's exponent 1 + (γ−1)/(2γ−1) with γ = 1/(1−κ) gives the identical value (§4.6).
Detailed, self-contained proof architecture (§4 + Appendix A)
Denominator clearing (A.4), complete carry-kernel proof (Prop. A.3, grounded in Kiers–O'Neill–Ponomarenko), unit-companion conductor theorem (A.8) whose exchange vector changes the represented sum by exactly one, and an explicit four-class pass sum (Prop. 4.4) handling incomplete top windows and the tuned prefix — no hidden hypotheses are waved at.
Honest disclosure of the theory/practice seam
Clean experimental design for the performance claim
Genuinely competitive practical sequence
Weaknesses
Statistically unsupported headline margins
The proven bound governs a sequence no run will execute
Matching lower bound rests entirely on an unrefereed source
No code, data, or artifact availability
Discovery-vs-imitation claim is under-argued
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper (arXiv 2609.29881) makes a three-part claim: (1) an RL-guided program search over executable gap generators, trained only on exact Shellsort execution costs, finds a rounded-geometric family in 5/5 independent runs (Table 1: 40,647 distinct executed programs); (2) prefix tuning yields the concrete sequence 1, 3, 8, 20, 47, 116, 300, 585, 1416, 3303, …, which attains the lowest equal-task geometric-mean operation count among seven classical baselines on 25 tasks with 10^7 < N ≤ 10^8 (Table 2); (3) after appending a zero-density set of unit companions h_s+1 — every one beyond the guard 10^1000 (exact check h_2723 ≤ 10^1000 < h_2724, §A.8) — the completed sequence admits worst-case T(N) = O(N^β polylog N) with β = 1.024296451657…, below Sedgewick's N^{4/3}, with a matching Ω(N^β) imported from Zang's 2026 preprint [Zan26].
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is the new Shellsort gap sequence from this paper?
The paper proposes 1, 3, 8, 20, 47, 116, 300, 585, 1416, 3303, 7703, 17963, 41887, 97670, … — a tuned eight-term prefix followed by the exact infinite rule h_t = ⌊α·(A/B)^t⌋ with A/B = 582942583375009/250000000000000 (≈2.3318) and α = 420574650882923/7668945023518835. For an array of length N you use every distinct gap below N in decreasing order, ending at 1.
Does the new sequence beat Ciura and Tokuda?
On the paper's 25 large test tasks (10^7 < N ≤ 10^8, five input types, exact comparison+move counts), it has the lowest geometric-mean total operations of the seven tested classical sequences — but the margins over Tokuda (0.079%) and Ciura (0.086%) are very small, come from a single test seed, and no statistical significance is reported. Gains are larger versus Sedgewick (1.79%) and much larger versus Hibbard/Knuth/Shell/Pratt.
Is the sub-N^{4/3} worst-case guarantee practically meaningful?
Only asymptotically. The proven bound O(N^1.0243·polylog N) requires adding a sparse set of 'companion' gaps of the form h+1, and every one of them exceeds 10^1000 — so for any real input the executed sequence is unchanged, and the bound's asymptotic regime technically begins only beyond that guard. The authors disclose this; the result is best read as: the practical sequence is not made slower, and its infinite completion provably beats the N^{4/3} barrier.
What does the exponent β = 1.024296451657 mean?
It is the polynomial part of the worst-case running time of the completed gap sequence: Ω(N^β) ≤ T(N) ≤ O(N^β·polylog N). It derives from κ = log_A(R) ≈ 0.024901 via β = 2 − 1/(1+κ), and matches the lower-bound exponent of a 2026 preprint by Zang for sequences near a rational geometric progression. It is far below Sedgewick's classic 4/3 ≈ 1.333 bound for sparse sequences.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The extracted text appears near-complete (abstract through Appendix A and references) and contains no figures; all quantitative claims analyzed come from the text alone.
- Table 2 was flattened into inline text; the baseline values and percentage arrows were parsed from that layout and could contain extraction artifacts.
- The matching lower bound relies on external preprint [Zan26] (arXiv 2607.08997), which could not be consulted, so the tightness claim is taken on trust.
- Appendix A's constant-level checks were not independently re-verified line by line; only the headline arithmetic chain (R, α, tail terms, κ, β, Zang exponent) was recomputed.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.