The greedy superstring ratio at small string lengths: ρ₈, ρ₉, ρ₁₁ > 2 and ρ₄, ρ₅ > 15/8

A common superstring of n distinct strings of length k has length at least n + k - 1

rho₄ > 7/4: an explicit 4-SCS instance on 40 strings whose optimum is exactly 43 and on which a legal greedy execution outputs 76, refuting the Cazaux-Rivals conjecture rho₄ = 2 - 1/4

rho₅ > 9/5: an explicit 5-SCS instance on 65 strings whose optimum is exactly 69 and on which a legal greedy execution outputs 125, refuting the Cazaux-Rivals conjecture rho₅ = 2 - 1/5

The source's own two constructions machine-checked: its printed k=6 numbers (9 strings, optimum 14, greedy pieces of length 11 and 8 overlapping in 1, output 18), its k=3 block (5 strings, optimum 7, greedy 9), and both of its refutations as finite instances (rho₃ > 5/3 at t=6, rho₆ > 11/6 at t=7)

Negative controls: the counting bound is false without distinctness; one block alone misses 7/4; a non-maximal merge makes the greedy checker return none; the superstring checker is not constant-true; greedy on the source's k=6 instance can also hit the optimum 14

rho₄ > 9/5 = rho₃ (114/63 at 6 blocks) and rho₄ > 15/8 (437/233 at 23 blocks): greedy is strictly worse on strings of length 4 than on strings of length 3, whose ratio the source pins at exactly 9/5

rho₅ > 11/6 = 2 - 1/6 (175/95 at 7 blocks) and rho₅ > 15/8 (325/173 at 13 blocks): the Cazaux-Rivals value 2 - 1/5 is wrong at k = 5 by more than one step of their own sequence

rho₄ >= 19/10: the t-block family of the cyclic 4-spectrum of AAXABAXBAX has 10t strings, optimum 10t+3 and a legal greedy output of length 19t for every t >= 1

rho₅ >= 25/13: the t-block family of the cyclic 5-spectrum of AAABXAABXBXBX has 13t strings, optimum 13t+4 and a legal greedy output of length 25t for every t >= 1

Structure of the greedy maximum-overlap phase: on a balanced instance it can only stop once every live string is a CLOSED trail of G(S) with pairwise distinct base vertices; hence a legal greedy output has length n + c(k-1) - O, and maximising the ratio is minimising the average closed-trail length

Measured: no block pattern over at most 3 shared + 1 fresh or 2 shared + 2 fresh letters, with b up to 11-16 depending on the sweep, beats 19/10 at k=4, 25/13 at k=5, or the source's 2 at k=6

Shibata's disproof of the greedy superstring conjecture as a kernel-checked finite instance: 198 strings of length 10 whose optimum is exactly 207 and on which a legal greedy execution outputs 415, so rho₁0 > 2; plus his formulas at t = 1 (22 strings, optimum 31, greedy 47)

rho₈ > 2: Shibata's construction at the even cell just below the range his Theorem 14 states, as 252 strings of length 8 whose optimum is exactly 259 and on which a legal greedy execution outputs 519 – so the greedy superstring conjecture already fails at string length 8, not 10

The k = 8 boundary: the same construction at 13 blocks gives 234 strings, optimum exactly 241, and a legal greedy execution of output length exactly 482 = 2*241, so 14 blocks is the minimum, for this construction, that refutes the conjecture at k = 8

Negative controls for the two even-k modules: one block reaches only 47/31 at k = 10 and 38/25 at k = 8; replacing the first merge by a pair of overlap 8 (resp. 6) instead of the maximum 9 (resp. 7) makes the greedy checker reject the whole 197-step (resp. 251-step) certificate; the Eulerian superstring stops being a superstring when one letter is dropped

rho₈ >= 37/18 = 2.0555...: Shibata's construction and its whole analysis hold at k = 8 for every t, after a two-line repair of the proof of Table 1 entries (f) and (h) which his printed argument gives only for k >= 10

Measured: the three starting offsets (U:4, V:2, W:6) that arXiv:2609.01365 fixes without comment are the UNIQUE minimiser of the asymptotic per-block overlap loss at every s = 4..8 – lambda = s-2 exactly, which is what makes the ratio (9s+1)/(4s+2) – and no offset triple makes the three closed strings pairwise overlap-free, which is what a ratio of 1 + 3(k-1)/(4s+2) -> 5/2, above the paper's 9/4, would require

Measured: the smallest instance in Shibata's family whose greedy ratio exceeds 2 is k = 10 with t = 9 – 198 strings of length 10 – since tₘin(s) = floor((4s-3)/(s-3)) + 1 and n = tₘin*(4s+2) is minimised at s = 5

Measured: over every block of arXiv:2609.01365's shape with three shared letters, the best value found is exactly (referee 2026-09-03: the sweep pre-filters with lambda loss(2)/2 – a strong filter, not a proof of optimality) 37/18 at k = 8 (22,200 blocks; the 24 offset choices that beat ratio 2 all give 37/18, on twelve blocks that are Shibata's up to relabelling and rotation) and exactly 43/21 at k = 9 (87,162 blocks; all 96 offset choices that beat ratio 2 give 43/21), while at k = 7 nothing reaches ratio 2 at all (5,340 blocks); the restricted k = 11 sweep (5,442 blocks, |V| in 6,7, |W| in 8,9) tops out at 52/25

rho₉ > 2: the greedy superstring conjecture fails at an ODD string length – 336 strings of length 9 whose optimum is exactly 344 and on which a legal greedy execution outputs 689. arXiv:2609.01365's construction is written for k = 2s throughout and cannot reach any odd k

The k = 9 boundary: the same block at 15 blocks gives 315 strings, optimum exactly 323, and a legal greedy execution of output length exactly 646 = 2*323, so 16 blocks is the minimum, for this construction, that refutes the conjecture at k = 9

Negative controls for the k = 9 module: one block reaches only 44/29; replacing the first merge by a pair of overlap 7 instead of the maximum 8 makes the greedy checker reject the whole 335-step certificate; the Eulerian superstring stops being a superstring when one letter is dropped

rho₉ >= 43/21 = 2.0476...: for every t the k = 9 block gives n = 21t, OPT = 21t+8 and a legal greedy output of length 43t+1

rho₁1 > 2: a second ODD cell – 250 strings of length 11 whose optimum is exactly 260 and on which a legal greedy execution outputs 521. Like k = 9 this is outside the reach of arXiv:2609.01365's k = 2s construction, and at 250 strings it is the smallest refuting instance this dispatch contributes

The k = 11 near-miss: the same block at 9 blocks gives 225 strings, optimum exactly 235, and a legal greedy execution of output length exactly 469 = 2*235 - 1 – one letter short, so 10 blocks is the minimum, for this construction, that refutes the conjecture at k = 11

Negative controls for the k = 11 module: one block reaches only 53/35; replacing the first merge by a pair of overlap 9 instead of the maximum 10 makes the greedy checker reject the whole 249-step certificate; the Eulerian superstring stops being a superstring when one letter is dropped

rho₁1 >= 52/25 = 2.08: for every t the k = 11 block gives n = 25t, OPT = 25t+10 and a legal greedy output of length 52t+1