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

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: S x S -> S in optimal time O(|S|^2), they left open the problem of finding any subcubic algorithm for verifying distributivity of given operations odot, oplus: S x S -> S. 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 4-term arithmetic progressions in a set X subseteq 1,...,N can be detected in time O(N^2-epsilon), then the 3-uniform 4-hyperclique hypothesis is true, and verifying certain identities requires running time |S|^3-o(1). A careful combination of our algorithmic and hardness ideas allows us to 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 verifiable in randomized time O(|S|^2), verifiable in randomized time O(|S|^omega) with a matching lower bound from triangle detection, or trivially verifiable in time O(|S|^3) with a matching lower bound from hardness of 4-term arithmetic progression detection. Finally, we obtain near-optimal algorithms for verifying whether a given algebraic structure forms a field or ring, and show that counting the number of distributive triples is conditionally harder than verifying distributivity.