The Involution Conjecture
On Commutative Self-Reversing Binary Operations over Finite Sets

Peter Lablans

May 2025

Abstract

This paper introduces the Involution Conjecture, which concerns a novel class of commutative, self-reversing binary operations defined over finite sets of cardinality \(n = 2^k\). These operations, which generalize bitwise XOR, are constructed using self-reversing permutations ("inverters") and exhibit algebraic properties that may extend beyond known operations in finite fields. Experimental results suggest the existence of numerous such involutions for higher \(n\), which are not equivalent to finite field addition. This offers intriguing implications in number theory and cryptography, particularly as potential drop-in replacements for XOR in symmetric-key primitives.

Introduction

In classical algebra and cryptographic constructions, binary operations such as XOR play a critical role due to their algebraic simplicity and reversibility. XOR is a prototypical example of a commutative involution—a binary function \(f(a, b)\) satisfying:

\[f(a, b) = f(b, a), \quad \text{and} \quad f(f(a, b), b) = a\]

This paper aims to generalize this notion by studying commutative, self-reversing binary functions over finite \(n\)-state systems. Our focus is on functions that are not expressible as field additions over \(\text{GF}(2^k)\), yet still satisfy involutory and commutative properties.

Preliminaries and Definitions

Let \(S = \{0, 1, \dots, n-1\}\) where \(n = 2^k\). Define a function \(f: S \times S \rightarrow S\) to be a commutative involution if it satisfies:

  1. Commutativity: \(f(a, b) = f(b, a)\)
  2. Self-reversibility: \(f(f(a, b), b) = a\)

These properties imply that knowledge of any two among \(a, b, c = f(a, b)\) uniquely determines the third.

Inverter Permutations

Define a reversible \(n\)-state inverter inv as a permutation of \(S\):

inv: S \rightarrow S \quad \text{bijective}\]

A permutation inv is self-reversing if:

inv(inv(x))=x

Example: the permutation inv4=[2 3 0 1] is self-reversing over \(S = \{0, 1, 2, 3\}\).

The Involution Conjecture

We conjecture a vast class of such operations beyond XOR, constructed from rows/columns of self-reversing inverters and satisfying commutativity and reversibility.

Constructive Examples

The following table represents the classic XOR operation over \(\text{GF}(4)\):

\[\begin{bmatrix} 0 & 1 & 2 & 3 \\ 1 & 0 & 3 & 2 \\ 2 & 3 & 0 & 1 \\ 3 & 2 & 1 & 0 \\ \end{bmatrix}\]

We now construct a novel involution that is not equivalent to XOR:

\[\begin{bmatrix} 0 & 1 & 3 & 2 \\ 1 & 0 & 2 & 3 \\ 3 & 2 & 1 & 0 \\ 2 & 3 & 0 & 1 \\ \end{bmatrix}\]

All rows and columns in this table are self-reversing inverters. The operation is commutative and involutory but cannot be derived from addition in \(\text{GF}(4)\).

Enumeration and Computational Results

Using MATLAB, we enumerated 10 valid self-reversing inverters for \(n=4\). For \(n=8\), the count is significantly larger. By assembling operation tables and enforcing symmetry, we identified hundreds of involutions not reducible to field arithmetic.

Extensions and Cryptographic Relevance

While the primary thrust of this paper is mathematical, these structures naturally invite cryptographic interest:

These cryptographic applications are secondary to the core mathematical interest of characterizing the involution space.

Usage and Patent Notice

The Finite Lab-Transform (FLT) [1] and other concepts[2] discussed in this article are protected under issued USA patents. While this material may be freely used for educational, review, research, and testing purposes, any operational use—including commercial applications—requires compliance with the relevant patent protections. No license for operational use is provided by this publication. For further inquiries regarding licensing and implementation, please contact the author.

References