Skip to content
Preprint

Finite-valued invariant metrics and a classification of natural groups

Sep 2026 · 0 citations · 21 references
Mathematics

Abstract

For every group $G$, of arbitrary cardinality, we construct a right-invariant metric with at most $32$ values whose isometries are exactly the permutations preserving every right-invariant metric on $G$. The proof combines subgroup-entry ranks and sign-variation colorings with a short-word rigidity theorem of Leemann and de la Salle. Their nonabelian orientation-rigidity theorem and direct regular-subgroup arguments yield the complete classification of natural groups in the right-translation sense: an abelian group $A$ is natural if and only if $2A=A$ or $2A=\{0\}$, and a nonabelian group is natural if and only if it is not generalized dicyclic. In particular, the additive group of every field is natural. The bound improves to $17$ for abelian groups and $5$ for Boolean groups, and the Boolean bound is sharp: $C_2^3$ admits no such metric with fewer than five values. Complementary constructions give one countable-valued hull metric realizing precisely the affine sign isometries simultaneously on all subgroups containing fixed coordinate markers, and signed-basis metrics with at most $p+5$ values over $\mathbb{F}_p$ for odd $p$. No other bound is claimed optimal, and no uncolored graphical regular representation is asserted.

View source

Similar papers

Preprint Oct 2026

Watkins's conjecture holds for all infinite groups

We prove that at every infinite cardinality, every group which is neither abelian of exponent greater than two nor generalized dicyclic admits a graphical regular representation, settling the infinite-group part of Watkins's conjecture. We also determine the Cayley index of every infinite group: it is $1$, $2$, or $8$,...

A. J. Sutherland · 0 citations
Preprint Nov 2026

Colorings breaking prescribed families of graph automorphisms

We prove that for every continuous action of a compact group on a discrete set, each finite-color template admits a coloring from arbitrary lists of the same size whose stabilizer is contained in a conjugate of the template stabilizer. Consequently, the ordinary and list parameters coincide whenever the ordinary parame...

Hui Lei, Yu Wang, Yue-Yue Zhao · 0 citations
Preprint Oct 2026

On Gallai $d$-colored circulants

A $d$-graph is a complete graph whose edges are colored with colors from $[d]$. It is Gallai if it contains no triangle whose three edges have distinct colors. We prove that every Gallai $d$-circulant is an iterated lexicographic product of circulants using at most two colors. The proof uses the compatibility of the kn...

V. Gurvich, M. Naumova · 0 citations
Sep 2026

Flip-packability: uniform characterisations of tame graph classes

A class of graphs is monadically dependent if one cannot encode all graphs in coloured graphs from the class using a fixed first-order formula, and monadically stable if one cannot even encode arbitrarily long linear orders. Bonnet et al. (ICALP 2025) characterised monadic dependence by flip-separability: for every ver...

Ioannis Eleftheriadis · 0 citations
Review Oct 2026

Sparse coloring for isosceles-free grids: an AI-assisted proof case study

We study the largest size $C(n)$ of a subset of the $n\times n$ integer grid containing no isosceles triple, including equally spaced collinear triples. We prove $C(n)=\Omega\left(n\sqrt{\log\log n/\log n}\right)$ by applying the sparse hypergraph coloring theorem of Cooper and Mubayi. Elementary geometry and primitive...

Yu-Kai Song · 0 citations
Preprint Oct 2026

Two-coloring the points of a projective plane

Let us color the points of a projective plane of odd order $n$ with two colors, say red and blue. Erd\H{o}s asked the question of determining the maximum number of balanced lines (that have the same number of red and blue points). The answer is $n^2$, and in the corresponding trivial coloring the unbalanced lines go th...

A. Blokhuis, Ádám Markó, T. Szonyi et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.