Finite-color reconstruction of groups and coherent configurations
Abstract
Every group has a canonical coloring of its unordered pairs by inverse pairs of differences. We prove that this coloring can be coarsened to four colors without changing its color-preserving permutation group, for groups of arbitrary cardinality. Four is the least uniform bound. A related construction applies to finite homogeneous coherent configurations: if every basic relation has valency at most $d$, where $d\geq 2$, a coarsening with at most $2d+1$ off-diagonal colors in the symmetric case, or $2d+3$ off-diagonal arc colors in general, has the original configuration as its coherent closure. Two-dimensional Weisfeiler-Leman refinement recovers that partition within $2\lceil\log_2 n\rceil$ rounds on $n$ points, with the specified atomic initialization. Affine-plane schemes show that linear dependence on valency is necessary. We apply the group realization to classify groups admitting naturalizing invariant metrics and show that, for a suitable such metric, naming the identity determines the compatible multiplication uniquely. Finally, using additional Cayley-realization and finite-classification inputs and explicit certificates, we determine the least number of metric values for every group. The direct universal construction and the finite coherent-reconstruction theorem do not depend on those computations.