Character Orthogonality, Subgroup Degradation, and a Characteristic Dichotomy for Time-Space Simulation
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