Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection

arXiv:2603.28843v1 Announce Type: new
Abstract: We revisit the complexity of verifying basic identities, such as associativity and distributivity, on a given finite algebraic structure. In particular, while Rajagopalan and Schulman (FOCS’96, SICOMP’00) gave a surprising randomized algorithm to verify associativity of an operation $odot: Stimes Sto S$ in optimal time $O(|S|^2)$, they left the open problem of finding any subcubic algorithm for verifying distributivity of given operations $odot,oplus: Stimes Sto S$.
Our results are as follows:
* We resolve the open problem by Rajagopalan and Schulman by devising an algorithm verifying distributivity in strongly subcubic time $O(|S|^omega)$, together with a matching conditional lower bound based on the Triangle Detection Hypothesis.
* We propose arithmetic progression detection in small universes as a consequential algorithmic challenge: We show that unless we can detect $4$-term arithmetic progressions in a set $Xsubseteq{1,dots, N}$ in time $O(N^{2-epsilon})$, then (a) the 3-uniform 4-hyperclique hypothesis is true, and (b) verifying certain identities requires running time~$|S|^{3-o(1)}$.
* A careful combination of our algorithmic and hardness ideas allows us to emph{fully classify} a natural subclass of identities: Specifically, any 3-variable identity over binary operations in which no side is a subexpression of the other is either: (1) verifiable in randomized time $O(|S|^2)$, (2) verifiable in randomized time $O(|S|^omega)$ with a matching lower bound from triangle detection, or (3) trivially verifiable in time $O(|S|^3)$ with a matching lower bound from hardness of 4-term arithmetic progression detection.
* We obtain near-optimal algorithms for verifying whether a given algebraic structure forms a field or ring, and show that emph{counting} the number of distributive triples is conditionally harder than verifying distributivity.