Ranking from counterexamples: the exact query complexity for at most seven items, and the failure of the sorting pattern at seven

Q(n) = 1, 2, 3, 5 for n = 1, 2, 3, 4: the exact number of proposals a worst-case-optimal learner needs to identify an unknown ranking of n items from truthful pair counterexamples, proved in both directions (a strategy table and an adversary table) against a model in which the learner may propose ANY ranking and the oracle may return ANY pair on which some consistent target disagrees

Q(5) = 7, from an 18-entry strategy table and a 12-entry adversary table, both up to isomorphism

Q(6) = 10, from a 61-entry strategy table and a 13-entry adversary table, both up to isomorphism

Q(7) >= 12: no learner identifies an unknown ranking of seven items within eleven proposals. The adversary certificate is 36 entries up to isomorphism – a perfect binary tree of 4095 states when labels are carried, each state offering a pair whose two answers both keep the value: exact halving, twelve times over

Negative controls: a genuine ranking is accepted and a list with a repeat is rejected; with one candidate left the learner still needs one proposal and zero never suffice (the convention that separates Q(n) from Moshkov's decision-tree depth); six proposals do not suffice on five items; eight do suffice, so an exact value is a two-sided claim

Q(7) = 12 exactly, kernel-checked in both directions: the coincidence Q(n) = floor(log2 n!) + 1 – true for every n <= 6, i.e. the counterexample oracle is worth exactly one bit a round – FAILS at n = 7, where the information-theoretic count gives 13 and the true value is 12. This is the first value of the sequence 1, 2, 3, 5, 7, 10, 12 that is not the sorting bound, and it answers the source's 'optimal constants' question in the direction the constant is smaller than 1

The model identity: the value of Alon-Moran-Moran's ranking-from-counterexamples game at k = 0 on n items equals h⁴(Sₙ) + 1, the minimum depth of a decision tree with proper hypotheses for the sorting decision table, plus one for the confirming proposal. The two literatures – exact learning with proper equivalence queries (2026) and decision trees with hypotheses (2021-2022) – do not cite each other

First exact values of Q(n,k), the same game with at most k untruthful counterexamples and a learner that knows k: Q(2,k) = 2, 4, 6 for k = 0, 1, 2; Q(3,k) = 3, 6, 9, 12 for k = 0..3; Q(4,k) = 5, 8, 12 for k = 0, 1, 2; Q(5,1) = 10. The per-lie increment is 2 at n = 2, 3 at n = 3, 3 then 4 at n = 4 – data on the second constant the source leaves open, the one in front of nk

The method: two certificate formats for this game and their soundness theorems – a strategy table (ubₛound) and an adversary table of balanced-pair cycles (lbₛound), both proved against the unreduced model with no native_decide – together with relabelling invariance (winsₚermMask and winsₚermMaskᵣev: permuting the items carries a winning strategy to a winning strategy and back), which lets both tables store one entry per isomorphism class. Measured at n = 7: the strategy table falls from 514,456 entries to 229 and the adversary table from 4,095 to 36, and the module checks in 4.8 s instead of an extrapolated hour

Properness is free in the truthful game through seven items: dropping the requirement that every query be a linear order (Moshkov's type-2 hypotheses, an arbitrary orientation of the pairs) leaves the value unchanged at n = 7, where both are 12. For n <= 6 this is the published fact that the h² and h⁴ columns of the sorting table agree; n = 7 is new. It sits next to the source's headline that properness is what turns the lie term from O(k) into Theta(nk)

The exact value is not a function of the number of linear extensions L and the width x: two posets on six points, both with L = 8 and x = 2, need 3 and 4 proposals respectively, both kernel-checked in both directions. The source's open-questions section asks whether the complexity for a starting poset 'is determined by L and x alone, or whether additional structural parameters of the poset are needed'; this settles the exact-value form of that question in the negative, and NOT the up-to-constant-factors form the source actually asks