Hamming Scheme¶

The association scheme on fixed-length words over a finite alphabet whose relation classes are indexed by Hamming distance.

Version: v2 · 2026-09-19 · History
Domain-specific #: 1975
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Association Schemes and Coding Theory → Mathematics
Aliases: Hamming association scheme, H(d,q)

Core Idea¶

Hamming Scheme is the association scheme on fixed-length words over a finite alphabet whose relation classes are indexed by Hamming distance.

Fix an alphabet A of size q and length d. The vertex set is A^d. For i from 0 to d, relation R_i contains ordered pairs of words at Hamming distance i. These relations partition A^d × A^d, with R_0 the diagonal, and their intersection numbers depend only on relation indices rather than on the particular word pair. This regularity makes H(d,q) a symmetric association scheme.

How would you explain it like I'm…

Spot-the-Difference Word Groups

Imagine all the words you can make with exactly three letters from a small set, like A and B. Take any two words and count how many spots have different letters: AAB and ABB differ in one spot. The Hamming scheme sorts every pair of words into groups by that number. The neat part is that every word sees the same pattern of near and far neighbors as every other word.

Sorting Words by Differences

Pick an alphabet with q letters and make every word of length d. The Hamming distance between two words is how many positions have different letters. The Hamming scheme groups all pairs of words by their distance: distance 0 (a word with itself), distance 1, up to distance d. What makes it special is how regular it is: for any two words at a certain distance, the number of words at distance i from the first and distance j from the second is always the same, no matter which two words you picked. Mathematicians call a structure this regular an association scheme.

Hamming-Distance Association Scheme

The Hamming scheme H(d, q) is built on all words of length d over an alphabet of q symbols. For each i from 0 to d, relation R_i is the set of ordered pairs of words at Hamming distance i, and R_0 is just each word paired with itself. Every pair of words falls into exactly one of these relations. The key property is regularity. For words x and y in relation R_k, the number of words z with (x, z) in R_i and (z, y) in R_j depends only on i, j and k. These counts are called intersection numbers. Together with the fact that distance is symmetric, this makes it a symmetric association scheme.

The Hamming scheme H(d, q) is the association scheme on the vertex set A^d, where A is an alphabet of size q and d is the word length. Its relations R_0, ..., R_d are defined by Hamming distance: (x, y) ∈ R_i iff x and y differ in exactly i coordinates. These relations partition A^d × A^d, with R_0 the diagonal, and each R_i is symmetric. The defining regularity is that for (x, y) ∈ R_k, the number of z with (x, z) ∈ R_i and (z, y) ∈ R_j is an intersection number p^k_{ij} depending only on i, j, k, not on the particular pair. This makes H(d, q) a symmetric association scheme; equivalently its relations correspond to distance classes of the Hamming graph. The identity is the distance-indexed scheme structure itself, not the general topic of coding theory or the bare notion of Hamming distance.

Scope of Application¶

The abstraction has a bounded but recurring habitat. These are literal applications of the same domain machinery, not cross-domain metaphors.

Coding theory. distance distributions and bounds are expressed in the scheme algebra.
Association-scheme theory. H(d,q) is a central metric and cometric example.
Design theory. subsets with regular inner distributions connect codes and designs.
Spectral combinatorics. adjacency matrices share eigenspaces described by Krawtchouk polynomials.
Finite probability. random word pairs yield distance classes with binomial structure.
Symmetry reduction. coordinate and alphabet automorphisms collapse pairwise calculations to d+1 relations.

Clarity¶

For words x and y, distance is a number, while R_i is the set of all pairs with that number. The Hamming graph H(d,q) is the graph with adjacency R_1; the Hamming scheme is the full family R_0 through R_d plus its regularity data.

Manages Complexity¶

The scheme replaces q^(2d) ordered word pairs with d+1 relation types. Intersection numbers and a commuting adjacency algebra make global coding questions accessible through low-dimensional linear algebra and orthogonal polynomials without discarding exact distance information.

The compression remains accountable because every simplification has a named validity condition. A user can ask which role is missing, which assumption fails, and which neighboring abstraction should replace the candidate instead of treating the label as an unanalyzed bundle.

Abstract Reasoning¶

R1. Declare both length d and alphabet size q.

R2. Distinguish the vertex set from pair relations.

R3. Verify that relation classes partition all ordered pairs.

R4. Use intersection numbers only after fixing their index convention.

R5. Separate properties of the ambient scheme from properties of a code subset.

Knowledge Transfer¶

The scheme transfers literally to finite word spaces with Hamming distance. Other association schemes share the regular-relation skeleton, but Johnson, Grassmann, and distance-regular schemes have different vertices and relations. Generic similarity or clustering should not inherit the Hamming-scheme name.

The transfer boundary follows from the classification test: The scheme recurs across coding theory and algebraic combinatorics, but word length, alphabet size, distance classes, intersection numbers, adjacency algebra, and eigenmatrices are indispensable.

Relationships to Other Abstractions¶

Current abstraction Hamming Scheme Domain-specific

Parents (1) — outgoing typed relations

Hamming Scheme presupposes Metric Prime

The accepted reference-grade review places Hamming Scheme under Metric because the child instantiates or depends on the parent's broader structure while retaining its own constitutive identity.

Hierarchy path (1) — routes to 1 parentless root

Hamming Scheme → presupposes Metric → is a kind of Function (Mapping)

Neighborhood in Abstraction Space¶

Hamming Scheme sits in a moderately populated region (49^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25