Forced counts When a symmetry group determines the discordance of a constructed ordering

We count the discordant pairs of an ordering against the binary order of the vertices of the n-cube, in the standard sense of rank correlation, and ask when that count is determined by the subgroup of the hyperoctahedral group B_n that the construction of the ordering respects.

The apparatus is an accounting over the orbits of that subgroup acting on pairs of positions. Each orbit is either forced, contributing exactly half its cardinality whatever else happens, or free, contributing one of two values. A group can therefore only ever force the midpoint of the range, never any other value; equivalently, it can only force Kendall's tau against the binary order to be exactly zero.

Two theorems remove the apparatus once it has been built. An orbit is forced precisely when it contains as many discordant pairs as concordant ones; and when the subgroup contains all translations, an ordering is forced precisely when every difference class splits exactly in two. A third result cuts the other way: if the subgroup contains the translations by a subspace of dimension at least two, every orbit has even cardinality, so the parity of the count is fixed by the structure, and when that parity differs from the parity of the midpoint the midpoint becomes impossible rather than merely unattained. The dimension hypothesis is necessary, by an exhibited witness.

The apparatus and its three theorems are the contribution; what follows is where they came from and what they first settled.

Applied to three constructed orderings of the 6-cube that have come down to us, with 2016 pairs and a midpoint of 1008, the three outcomes all occur. Two of the constructions force the count to 1008, and for one of them the demonstration is complete with no enumerative residue; a mechanism previously claimed for the other is refuted here, since the closure it rests on forces only 484 of the 2016 pairs and survives rearrangements that destroy the result, the midpoint coming out in 3836 of the 40320 of them. The third construction makes 1008 impossible by the parity obstruction: its structure leaves the interval [957, 1059] and exactly 52 compatible totals within it, 1008 is not among them, and the observed count is 1013.

That difference of 5 is decomposed completely over the 19 free orbits and has no culprit: every free orbit deviates, and the deviations nearly cancel. Against a list of candidate structures declared before measuring, one narrows the interval, namely the construction's own pairing involution, which is not affine and so was absent from a group that is exactly its centraliser; none explains the difference. We therefore declare the residue informative relative to that list, and stop.

A landscape of 14 rows over block systems in dimensions three to six populates the three outcomes away from the historical cases and records two refutations of shapes we tried to raise into theorems, one of them of an error of our own.

Every measurement was preceded, in an earlier commit of a public repository, by a written statement of what was going to be measured and, where predictions were made, of what would refute them, and that ordering is checkable.

Replication repository: https://github.com/Probatorium/forced-counts

The deposited bundle contains the full commit history; two third-party data files are filtered from it, as declared in the manifest dist/THIRD-PARTY.md.