An algebraic resolution of the ELSP via group actions in directed Paley graphs

Zhour Oumazouz1
1FST Mohammedia, Hassan II University, Casablanca, Morocco

Abstract

We study the Equivalent Local Sequence Problem (ELSP), which consists in recovering an explicit sequence of local complementations that transforms a graph into a locally equivalent one. Focusing on directed Paley graphs, we establish that local complementations commute and induce a free action of an elementary abelian 2-group. The stabilizer condition is reformulated as a system of convolution equations and analyzed through Fourier techniques over finite fields, leading to a proof of stabilizer triviality. As a consequence, each graph in the orbit admits a unique subset encoding, and ELSP reduces to solving a linear inversion problem over š”½2. This characterization completely resolves ELSP for directed Paley graphs, provides a polynomial-time inversion algorithm and highlights structural features that may support future developments in cryptographic frameworks and quantum graph-state models.

Keywords: local complementation, graph equivalence, ELSP problem, Paley graphs, quadratic residues, complexity