Character Orthogonality, Subgroup Degradation, and a Characteristic Dichotomy for Time-Space Simulation

Read full text Summarise with VIRAT
Authors: Xavier Aguiar
Cited by: 0

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Williams (STOC 2025) proved that TIME[t] ⊆ SPACE[O(√t log t)], using the Cook–Mertz tree evaluation algorithm over finite fields. We formalize the algebraic structure underlying this simulation in two ways. First, we define the path complexity PC(G) of the computation DAG and show that the Cook–Mertz algorithm “short-circuits” it: the simulation space depends on DAG depth and local parameters, not on PC(G), which can be exponential (Proposition 6). Second, we prove that the exact cancellation in the Cook–Mertz character sum depends essentially on the affine geometry of the computation: when the summation domain is replaced by a proper subgroup of F∗q of order less than the polynomial degree, the identity fails (Theorem 11). Third, we discover a characteristic dichotomy: replacing K∗ with rational points on an elliptic curve (under the standard x-coordinate map) produces zero error in characteristic 2 (because all fibers have even cardinality) but computationally observed nonzero error in odd characteristic (The- orem 14), showing that Cook–Mertz’s use of F2k is algebraically distinguished in a previously unrecognized sense. These results clarify the algebraic-geometric structure underlying Williams’ simulation and identify characteristic 2 as playing a distinguished role beyond computational convenience.

Fields of Study & Subjects

Complexity and Algorithms in Graphs Coding theory and cryptography Analytic Number Theory Research

Publication details

Journal / source
Zenodo (CERN European Organization for Nuclear Research)
Publication date
27 March 2026
Language
EN
Document type
Preprint