pith. sign in
module module high

IndisputableMonolith.Patterns.GrayCycleBRGC

show as:
view Lean formalization →

GrayCycleBRGC supplies the Binary Reflected Gray Code construction that realizes an explicit adjacent Hamiltonian cycle on the hypercube of dimension d. Researchers building general-dimension Gray covers cite it when they need the standard BRGC formula turned into a concrete path. The module consists of supporting definitions for bit-append operations together with lemmas that establish the required adjacency and injectivity properties.

claimThe BRGC path given by the map $nmapsto noplus(n>>1)$ induces a Hamiltonian cycle on the hypercube whose vertices are all functions from a $d$-element set to the two-element set, with edges between functions differing in exactly one coordinate.

background

The Patterns module introduces the state space Pattern d consisting of all maps from Fin d to Bool. The GrayCycle module upgrades counting facts to an explicit adjacent cycle: a closed walk of length 2^d that visits every pattern once, where adjacency requires that the two patterns differ in precisely one coordinate. GrayCycleBRGC imports both modules and adds the concrete BRGC realization that uses recursive bit appending to build the path.

proof idea

This is a definition module, no proofs.

why it matters in Recognition Science

The module feeds GrayCycleGeneral, which applies the BRGC construction to obtain a GrayCover d (2^d) and a GrayCycle d for arbitrary d. It supplies the explicit path needed for the Workstream A generalization that replaces abstract existence arguments with the standard formula gray(n) = n XOR (n >>> 1).

scope and limits

used by (1)

From the project-wide theorem graph. These declarations reference this one in their body.

depends on (2)

Lean names referenced from this declaration's body.

declarations in this module (14)