mythos_zeta
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 three 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 can fail (Theorem 11). Third, we analyze the effect of replacing K∗ with rational points on an elliptic curve (under the standard x-coordinate map). In characteristic 2, every fiber over F∗q has even cardinality, forcing all power sums Tj (E) = 0 and preserving exact cancellation (Theorem 14(a)). In odd characteristic, we give an exact formula for Tj (E) as a weighted character sum and prove that T1(E) = 0 for the j-invariant-0 family when q ≡ 1 (mod 3), via cube-root symmetry (Theorem 14(b–c)). Computational evidence (Section 6) suggests T1(E) ̸= 0 for curves with α ̸= 0;a complete classification of vanishing in odd characteristic remains open. 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
Analytic Number Theory Research
Coding theory and cryptography
Publication details
- Journal / source
- Zenodo (CERN European Organization for Nuclear Research)
- Publication date
- 28 March 2026
- Language
- EN