A New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond $N^{4/3}$

Bo Liu

Source-linked AI summary

A New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond $N^{4/3}$

Bo Liu

arXiv:2609.29881v1Sep 24, 2026cs.CCcs.DScs.LG

TL;DR

The paper addresses the lack of a concise, practically competitive Shellsort gap sequence with a sparse worst-case bound below N^4/3. It searches executable generators using learned proposals and exact costs, then tunes a finite prefix and completes the tail mathematically. The resulting sequence has the lowest equal-task average operation count among tested classical sequences on 25 large tasks, while its proof gives a matching polynomial exponent up to polylogarithmic factors.

Problem
The paper seeks a concise, sparse Shellsort gap sequence that is practically competitive and provably below the N^4/3 worst-case bound.
Source: §1.3 · p. 4
Method
The system searches valid gap-generator programs using learned proposals and exact execution costs, then freezes a generator and tunes only its finite prefix.
Source: §1.2 · p. 3, §2.2 · p. 5
Results
The sequence has the lowest equal-task average operation count among tested classical sequences on 25 large test tasks.
Source: §5 · p. 14
Takeaways & Limitations
Zero-density unit companions complete the learned tail’s proof below Sedgewick’s N^4/3 bound without changing reported runs.
Source: §5 · p. 14
Whether the sequence retains its advantage under a fixed hardware timing test remains open.
Source: §5 · p. 14

Abstract

from arXiv · show

Choosing Shellsort gaps is a well-known open problem. For over sixty years, successful sequences have relied on human-designed formulas, numerical searches, or number-theoretic constructions. Although stronger general bounds exist for dense or mainly theoretical families, the worst-case upper bound for a short, sparse, and practically competitive construction has not advanced beyond $N^{4/3}$ for decades. We ask whether the sequence itself can instead be learned from execution. We present an RL-driven, self-supervised system that searches over executable gap generators. Every proposal is valid by construction, and executed candidates return exact comparison and move counts; no classical sequence is used as a target. Across five independent searches, the system discovers a common rational-geometric family. A second self-supervised stage tunes only a finite prefix, producing the practical sequence $1,3,8,20,47,116,300,585,1416,3303,\ldots$. Once frozen, it obtains the lowest equal-task average operation count among seven classical baselines on 25 large tasks with $10^7<N\leq 10^8$. We complete the learned tail without changing its practical behavior: only beyond $10^{1000}$, a zero-density set of unit companions $h_s+1$ removes the remaining congruence barriers. The resulting sparse sequence has matching polynomial upper and lower exponents, up to polylogarithmic factors: $\Omega(N^{1.024296451657\ldots}) \leq T(N) \leq O(N^{1.024296451657\ldots}\operatorname{polylog} N)$. The lower bound follows from Zang's recent theorem for rational-geometric sequences; our contribution is the matching upper bound. Thus one exact sequence connects self-supervised discovery, large-scale practical performance, and a substantial step below the classical $N^{4/3}$ bound for sparse practical Shellsort sequences.

1 Introduction

Shellsort’s gap-sequence problem lacks a concise near-geometric rule that is both practically fast and provably below the sparse-sequence N^4/3 bound. The paper combines learned program search, exact execution, prefix tuning, and a mathematical completion to connect practical performance with a sub-N^4/3 result.

1.1 Theory, practice, and the 4/3 barrier

Sedgewick broke the sparse 3/2 exponent with an O(N4/3) sequence; going below 4/3 requires fewer unrepresentable multiples in every growing local window [Sed86].At realistic sizes, Tokuda’s ratio-9/4 sequence and Ciura’s tuned prefix remain stronger than the asymptotic constructions, but have no matching worst-case theorem [Tok92, Ciu01].Source: §1.1 · p. 2
Learning first finds an executable rational-geometric rule; a proof then completes its tail with zero-density unit companions to remove congruence obstructions.The first companion lies beyond 10^1000, so this completion does not change reported runs.Source: §1.1 · p. 2

1.2 From learned decisions to learned infinite algorithms

The search uses learned guidance to propose program edits, while execution and mathematics—not the model—check candidate costs and validity.Candidates must be generators that emit legal gaps for every input size, and the system uses no classical sequence as a target.Source: §1.2 · p. 3

1.3 Contributions

Five searches independently find compact geometric generators, each testing more than 7,000 programs and learning from exact comparison and move counts.The search does not copy a classical sequence.Source: §1.3 · p. 3
On 25 test tasks between 10^7 and 10^8, it has the best average operation count among all tested classical sequences in the reported comparison.Source: §1.3 · p. 4
Beyond 10^1000, zero-density unit companions complete the sequence’s proof without changing reported runs, yielding a tight exponent below 4/3.The paper combines this completion with the applicable rational-geometric lower bound.Source: §1.3 · p. 4

2 RL-driven Generator Discovery

The system searches complete programs that generate legal Shellsort gaps and evaluates them using exact sorting costs. A learned model guides edits and proposal selection, after which independent panels freeze a generator and tune only its finite prefix.

2.1 Search problem and program space

A candidate generator returns a decreasing legal gap list ending in 1; every program starts with gap 1 and emitted values are filtered and sorted.The program language supports formulas, recurrences, branches, unions, and multi-register state, with edits that preserve complete programs.Source: §2.1 · p. 4
Candidate cost is the sum of key comparisons and array writes, evaluated on a shared task panel and normalized by input size without a baseline sequence.The panel spans random, reversed, nearly sorted, duplicate-heavy, and permuted ordered-block inputs.Source: §2.1 · p. 4

2.2 Learning and search

A learned model proposes program edits and predicts costs and gap contributions, but every surviving candidate is executed and scored exactly.The search retains programs across comparisons, moves, pass count, and program size, and uses exact cost improvement as reward rather than a policy-gradient estimator.Source: §2.2 · p. 5
Five seeded runs search and validate generators, then a second search tunes only the first eight gaps while keeping the learned tail fixed.Search, Validation, and Test use disjoint seeds and size ranges; finite-prefix tuning leaves the later proof unchanged.Source: §2.2 · p. 5

3 Empirical Results

The learned rounded-geometric backbone was refined by tuning its finite prefix and then evaluated on a 25-task large-sorting test. The frozen sequence had the lowest equal-task average among tested baselines.

3.1 From program search to the final sequence

The five searches completed 120 rounds and evaluated 40,647 distinct program behaviors using measured execution feedback.Validation and Extrapolation were independent panels.Source: §3.1 · p. 5, Table 1 · p. 6
Across five searches, all winners reduced to rounded geometric rules, with ratios 2.3522, 2.3164, 2.3619, 2.2490, and 2.3318.The common form was found by search rather than built into the language.Source: §3.1 · p. 6
On 20 independent Validation tasks, prefix tuning lowered geometric-mean cost by 0.304% relative to the original backbone.The resulting sequence begins 1, 3, 8, 20, 47, 116, 300, 585, 1416, 3303.Source: §3.1 · pp. 6–7

3.2 Performance on large sorting tasks

The frozen sequence had the lowest equal-task average among every tested baseline on the 25-task broad Test.Table 2 reports equal-task geometric-mean operation counts in billions.Source: §3.2 · p. 7, Table 2 · p. 7

4 A Sub-N4/3 Bound

The proof analyzes the exact frozen sequence, completing its rational-geometric tail with sparse unit companions to remove congruence obstructions. It bounds every pass and matches the resulting polynomial upper exponent with a lower bound.

4.1 Completion and main theorem

The learned tail is completed by adding h_s + 1 companions whenever h_s occurs, beginning at s_0 = 2724.This exact infinite definition leaves every added gap beyond the range of experiments and realistic implementations.Source: §4.1 · p. 8

4.2 One pass as an exact representation problem

A pass at gap d is bounded using missing multipliers among nonnegative combinations of larger gaps, with direct insertion sorting providing a separate bound.The proof reduces the representation-side analysis to bounding the conductor, a threshold above which every multiplier is representable.Source: §4.2 · pp. 8–9

4.3 Denominator clearing, carries, and the unit direction

A unit companion in a growing future window corrects the integral rounding residual, removing residue classes without requiring a favorable greatest common divisor.The argument uses denominator clearing and carry representations before adjusting the remaining residual by the unit direction.Source: §4.3 · pp. 10–11

4.4 Sparse placement covers every window

Sparse placement ensures every complete future window contains a unit pair, while the companions remain zero-density.The proof also bounds incomplete-window passes at the sequence boundary and treats the finitely tuned prefix as an O(N) contribution.Source: §4.4 · pp. 11–12, §4.5 · p. 13

4.5 Balancing and summing all passes

O(N^β polylog N), with β = 1.02429645165747606869... bounds the total cost of backbone, companion, and tuned-prefix passes.The upper-bound exponent follows by balancing the pass-cost terms and summing four classes of passes.Source: §4.5 · pp. 12–13

4.6 A matching polynomial lower bound

Zang’s theorem [Zan26] gives an Ω(N^β) lower bound for this sequence, so its upper and lower bounds have the same polynomial exponent.The sequence stays within a fixed distance of a rational geometric progression, satisfying the theorem’s condition.Source: §4.6 · p. 13

5 Conclusion

The conclusion presents one sequence that combines a learned practical prefix with a mathematically completed tail. Its practical comparison is limited to operation counts on the tested task mixture, while its asymptotic bounds match in polynomial exponent.

5 Conclusion

The learned sequence has the lowest equal-task average comparison-and-move count among seven classical sequences on 25 large tasks.The comparison covers the full input mixture, not wall-clock time or separate wins on every input type.Source: §5 · p. 14
Beyond 10^1000, zero-density unit companions establish a worst-case bound below Sedgewick’s N^4/3 bound without changing runs below the guard threshold.Zang’s rational-geometric lower bound has the same exponent, leaving only a polylogarithmic factor between the bounds.Source: §5 · p. 14
Whether the pure geometric backbone needs companions, average-case theory explains the measured gain, or the advantage persists under fixed-hardware timing remains open.The conclusion assigns algorithm proposal to learning and validation to exact execution and mathematics.Source: §5 · p. 14

A Technical Details for the Main Bound

The appendix expands proof details already used in the main bound and adds no new hypothesis or proof step.

A Technical Details for the Main Bound

The appendix supplies expanded normal forms, uniform constant checks, kernel bookkeeping, and boundary cases without adding a hypothesis or proof step.As in the main proof, the frozen output is treated as an exact mathematical object, independent of the neural model and experimental distribution.Source: A Technical Details for the Main Bound · p. 15

A.1 Final sequence and main theorem

The completed sequence preserves the practical gap list through N ≤ 10^1000 while adding a zero-density set of unit companions in its infinite tail. Its worst-case operation count has matching polynomial upper and lower exponents, up to a polylogarithmic factor.

A.1 Final sequence and main theorem

The practical sequence is defined by equation (5), and Shellsort uses its distinct gaps below N in decreasing order.Source: §A.1 · p. 15
The sequence adds a zero-density set of unit companions to the practical generator’s asymptotic completion.The companions are added at selected indices s_r as h_s_r + 1.Source: §A.1 · p. 15
For every N ≤ 10^1000, the completed sequence emits exactly the practical sequence’s gap list, so passes, comparisons, moves, and memory accesses are identical.Source: §A.1 · pp. 15–16
The worst-case operation count has matching polynomial exponent 1.024296451657..., up to a polylogarithmic factor.The lower bound applies to the completed sequence; the upper bound is the paper’s contribution.Source: §A.1 · p. 15

A.2 Pass cost as a multiplier-semigroup problem

The analysis bounds the cost of a d-pass through the positive multipliers representable by combinations of previously executed larger gaps. Missing multipliers and insertion sorting within residue classes give complementary bounds.

A.2 Pass cost as a multiplier-semigroup problem

Incerpi and Sedgewick’s generalized Frobenius pass lemma supplies a bound from the number of missing multipliers [IS85, Lemma 1, pp. 212–213].Source: §A.2 · p. 16
Insertion sorting the d residue classes gives a separate elementary bound because each class has length at most ⌈N/d⌉.Source: §A.2 · p. 16
The d-pass analysis tracks missing positive multipliers in the semigroup generated by the previously executed larger gaps.If the least threshold after which all multipliers are represented is K, then the number missing is at most K − 1.Source: §A.2 · p. 16

A.3 The logarithmic future window

For a backbone gap, the proof uses an increasing window of future gaps to control the missing-multiplier count. A fixed-size window retains a growing congruence obstruction and is insufficient for the needed sublinear count.

A.3 The logarithmic future window

The proof considers a backbone gap h_t and its future backbone gaps to establish the window estimates.Source: §A.3 · p. 16
For backbone gaps, the proof establishes A_m = Θ(d), B_m = Θ(d^(1−κ)), and dB_m = R_m = Θ(d^κ).These estimates hold for either possible tail gap d ∈ {h_t, h_t + 1}, with constants independent of t, m, or d.Source: §A.3 · p. 16
A fixed number of rational-geometric future gaps leaves a denominator-induced congruence obstruction whose modulus grows with d.The resulting missing-multiplier count cannot be sublinear, so the proof requires an increasing window.Source: §A.3 · p. 16

A.4 Exact denominator clearing

The proof reformulates representability using two coordinates to separate rational-geometric scale from flooring error. The auxiliary gap h_t + 1 shifts the slopes without changing their width.

A.4 Exact denominator clearing

The construction first sets d = h_t and takes future backbone gaps before deriving the reformulation.Source: §A.4 · p. 17
Representability of the relevant combination is reformulated exactly using two coordinates, q and v, coupled by an integer D.The q-coordinate captures rational-geometric scale, while v captures flooring error.Source: §A.4 · p. 17
For the auxiliary gap d = h_t + 1, every slope shifts by −1, but the width is unchanged and |σ_i| < 2.The constants may depend on A and B, but not on t, m, or d.Source: §A.4 · p. 17

A.5 Compound coordinates and their complete carry kernel

The section develops the compound semigroup’s normal form and uses adjacent carries to describe integer coefficient changes and their exact effect on represented gap sums.

For the compound weights (B^(m−1), AB^(m−2), ..., A^(m−1)), the semigroup has a bounded-digit normal form, and every integer above F_m is representable.Source: §A.5 · pp. 17–18
The threshold F_m is O_A,B(A^(m−1)), since the largest weight is A^(m−1) and A,B are fixed.Source: §A.5 · p. 18
Adjacent carries form a basis for the full integer kernel, and each changes the actual gap sum by exactly −e_i.Source: §A.5 · p. 18

A.6 From a real interior point to integer coefficients

The appendix converts interior real representations into exact integer representations using carry rounding and a unit-pair correction, then places companions and sums pass costs to establish the exponent while preserving finite-prefix tuning.

A.6 From a real interior point to integer coefficients

With a fixed main coordinate, interior real representations can be rounded via adjacent carries, controlling coefficient error but potentially leaving an actual-value residual.Source: §A.6 · p. 19

A.7 The unit direction and a conductor bound

A future unit pair supplies an extra integer correction direction, yielding nonnegative integer representations of exact kd with coefficient margin S≥C_A,B m and a conductor bound.Source: §A.7 · pp. 20–21

A.8 Zero-density placement covers every window

Every sufficiently large complete future window contains an executed unit pair, while the number of companions remains zero-density.Source: §A.8 · p. 22

A.9 Summing all passes

The pass sum is O(N^β polylog N) with β=1.024296451657..., and the operation-count lower bound has the same polynomial exponent.Source: §A.9 · p. 23

A.10 Why finite-prefix tuning preserves the theorem

Finite-prefix replacements leave the exponent unchanged; the denser zero-density completion is chosen over an O(log log N) alternative with exponent 1.047440273015....Source: §A.10 · pp. 23–24