brgc_inverse
def
The inverse prefix-parity transform on n-bit binary words, computed as the exclusive-or of all right shifts by less than n.
Statement
def brgc_inverse : ℕ → ℕ → ℕ- Defined in
- Prefix-parity inverse and supporting arithmetic for OP-392, arXiv:2610.24758, Section 3 and Conjecture 1.
- Verified
- 24 Oct 2026
- Axioms
- none listed
- Used by 19
- alpha_lexical_odd_completion_iff_rotation_maxFor any length n at least three, a nonempty positive sequence of sum n−1 is lexical if and only if its odd-parity binary completion is…
- lexical_degree_seventeen_class_a_counterexampleThe lexical sequences a = (3,1,1,3,3,2,2,1) and b = (3,1,1,2,1,3,2,2,1) both have degree 16, are adjacent in the source lexical order…
- brgc_inverse_prefixThe inverse Gray rank of a high-bit prefix is the corresponding high-bit prefix of the inverse rank.
- brgc_inverse_flip_preserves_rotation_maxToggling the last bit of an aperiodic nonconstant word that maximizes its inverse Gray rank over all rotations again maximizes that rank,…
- brgc_inverse_concatThe inverse Gray rank of a concatenation has the prefix inverse rank followed by the suffix inverse rank, complemented exactly when the…
- alpha_binary_completion_inverseCompleting the prefix to even or odd Hamming parity gives the two consecutive inverse Gray ranks 2q and 2q+1.
- alpha_lexical_lt_iff_inverse_prefixOn equal-length positive encodings, lexical order is exactly inverse Gray-rank order.
- brgc_inverse_flip_preserves_cut_maxIf an n-bit word has strictly greater inverse Gray rank than every nontrivial cyclic cut, toggling its last bit has at least as great an…
- brgc_word_inverseEncoding the n-bit inverse prefix-parity transform recovers the word.
- brgc_inverse_lt_two_powThe inverse prefix-parity transform of an n-bit word has an n-bit rank.
- brgc_necklace_first_rank_exists_of_nonconstantEvery nonconstant binary word of length at least two has a first-occurrence Gray rank in its rotation class.
- brgc_necklace_first_rank_rotation_maxRotating a first-occurrence representative right once gives a representative of maximum inverse Gray rank in its rotation class; the…
- alpha_lexical_odd_completion_iff_rotation_max_of_primeThe proposed encoding bridge between positive lexical sequences and nonconstant odd-parity maximum-rank necklace representatives at odd…
- brgc_necklace_first_rank_min_rotationsEvery rotation of a first-occurrence representative has inverse Gray rank at least its first-occurrence rank.
- alpha_binary_prefix_inverse_parityThe inverse Gray rank of the prefix has the parity of the number of encoded one bits, namely the cell count.
- alpha_lexical_terminal_predecessor_simple_star_obstructionThe two displayed lexical sequences are adjacent among sequences of degree 19 and have meet f=(2,1,1). The later sequence has a lexical…
- brgc_inverse_wordThe n-bit inverse prefix-parity transform recovers an n-bit Gray rank from its encoded word.
- brgc_inverse_rotate_tent_formulaIn inverse Gray-rank coordinates, cyclic left rotation is the two-branch integer tent map, with the rank parity carried along.
- brgc_inverse_alpha_binary_prefix_consThe inverse Gray rank of x :: xs equals 2^xs.sum * (2^x - 1) + (2^xs.sum - 1 - brgc_inverse xs.sum (alpha_binary_prefix xs)).
Lean source view module on GitHub
def brgc_inverse : ℕ → ℕ → ℕ
| 0, _ => 0
| n + 1, x => x ^^^ brgc_inverse n (x / 2)