Symmetric compatibility of theta structures, with applications to change of level and isogenies
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Symmetric compatibility of theta structures, with applications to change of level and isogenies".
Jane: Here's the gist of the paper. This paper presents a general framework for computing change of level and isogeny algorithms between marked abelian varieties over a field of odd characteristic, extending previous results to cases where the degree d is even or when d and the level m are not coprime.
Tom: The core theoretical machinery relies on defining and utilizing concepts related to symmetric compatibility for theta structures, which are crucial for extending a theta structure from level m to level n=md.
Jane: The paper introduces notions of symmetric compatibility for torsion points and level subgroups based on the action of the Theta group and specific conditions involving lifts in the group G(L).
Tom: This framework is central to establishing equivalences between different definitions of compatibility.
Paper summary: Tom: So we've covered the core idea of Aquino and Lubicz's paper, "Symmetric compatibility of theta structures, with applications to change of level and isogenies." They show how to compute these things even when the standard assumptions about d or m being coprime don't hold.
Jane: The main thing they claim is that by introducing symmetric compatibility for theta structures, they can build deterministic algorithms for changing the level and computing d-isogenies between marked abelian varieties >
Lu: It’s really a big theoretical step because it connects Mumford's theory with the practical computation of these structures, proving that Mumford compatibility is equivalent to f-compatibility >
Meng: For us on the engineering side, this means we can build more general tools for transformation algorithms without having to manually check every single constraint every time >
Tom: I think what matters most is that they provide concrete running times. They give us O of n squared g log d > for change of level and O of n g log d > for the isogeny computation >
Jane: In simple terms, this paper gives us a reliable way to move between different levels and perform these isogenies in a general setting, which used to be restricted to much simpler cases like when d was odd and coprime to m >
Lu: It opens up the door for applying these kinds of transformations in situations where we don't have those nice, simple number theoretic conditions satisfied >
Conclusion: Tom: So this paper is about finding a general way to handle change of level and isogeny calculations between marked abelian varieties, even when the usual rules about degrees or levels not sharing factors don't apply.
Jane: It’s tackling these problems by introducing this idea of symmetric compatibility for theta structures. It seems like they are building a bridge between different ways people define compatibility, which is a big theoretical hurdle in this field.
Lu: Yeah, the core mechanism is showing that Mumford compatibility and f-compatibility are actually the same thing when you look at these specific conditions involving torsion points and level subgroups. That equivalence is what makes their whole framework work.
Meng: If they can prove that Mumford compatibility means f-compatibility, then we have a solid foundation for building something deterministic instead of something heuristic. That's what I care about because we need things to run reliably on production systems.
Lalam: What this means practically is they’ve set up algorithms that are guaranteed to work, not just in theory but with specific running times like O of n squared g log d for changing the level.
Tom: The complexity numbers are what really grab my attention here; O of n squared g log d sounds like a lot, but it’s deterministic for this specific task. That’s a big win because usually these kinds of problems get messy with non-deterministic checks.
Jane: So, the main takeaway is that we don't have to worry as much about the specifics of d or the level m being coprime when we want to compute these transformations. It makes the toolbox much more versatile for us.
Lu: Exactly; it’s providing a robust framework that works generally, which means we can apply this to a wider variety of geometric situations than before, even if the underlying number theory is trickier.
Meng: For deployment, it suggests we can automate these complex transformations without needing custom code for every single edge case in the degree or level relationship. That could save us a ton of development time down the line.
Lalam: It’s a general method, and that means we can use it to solve problems we hadn't even thought possible with our current tools because they weren't restricted by those coprime conditions anymore.
Tom: So they’ve essentially unified two different ways of thinking about these structures—the Mumford way and the f-way—and shown how you can use that equivalence to get fast, reliable algorithms for level changes and isogenies.
Jane: It’s about making the abstract theory of theta structures concrete enough so we can actually build something functional for computation, which is what this paper really achieves.
Lu: The next step will be seeing how these algorithms perform on really large examples to confirm those time complexities hold up in practice, which is where the real validation happens.
Meng: I’m curious about the implementation details of Algorithm seven and eight; if we can actually map that abstract compatibility condition into a deployable code structure, then this moves from interesting theory to something useful for us.
cs.SC, math.NT
Submitted: 2025-04-29
Updated: 2026-11-12
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 92/100
The gist: This paper presents a general framework for computing change of level and isogeny algorithms between marked abelian varieties over a field of odd characteristic…
Key concepts
- Symmetric Compatibility
- This concept relates to how a theta structure behaves under certain group actions, specifically involving torsion points and level subgroups. It is crucial for extending a theta structure from one level (m) to another (n=md). The paper uses this compatibility to define necessary conditions for structures to be related.
- Mumford Compatibility
- This is a specific notion of compatibility derived from Mumford's theory. It serves as the benchmark condition against which other compatibility notions are measured. The paper proves that two partial theta structures are $f$-compatible if and only if they satisfy this Mumford compatibility condition.
- $f$-Compatibility
- This is a notion of compatibility specifically related to the isogeny $f$ between abelian varieties. It links the structure of the theta group action to the properties of the map $f$. The core result shows that this definition is equivalent to Mumford compatibility, simplifying algorithmic choices.
- Change of Level Algorithm
- This deterministic procedure allows one to compute a new theta structure (type K(n)) starting from an existing one (type K(m)). It achieves this in polynomial time, specifically O(n^2g log d), providing a practical method for modifying the level of the variety.
Terminology
Summary
This paper presents a general framework for computing change of level and isogeny algorithms between marked abelian varieties over a field of odd characteristic, extending previous results to cases where the degree d is even or when d and the level m are not coprime. p. 0 The core theoretical machinery relies on defining and utilizing concepts related to symmetric compatibility for theta structures, which are crucial for extending a theta structure from level m to level n=md. p. 1
The paper introduces notions of symmetric compatibility for torsion points and level subgroups based on the action of the Theta group and specific conditions involving lifts in the group G(L). p. 2 This framework is central to establishing equivalences between different definitions of compatibility. p. 2 Specifically, it proves that Mumford compatibility (a notion derived from Mumford's theory) is equivalent to f-compatibility (a notion related to the isogeny f). This equivalence is formalized in Theorem 8: two partial theta structures theta 1 M and theta 1 Md are f-compatible if and only if they are Mumford compatible. p. 4
The paper then presents deterministic algorithms based on these compatibility conditions. p. 4 For the change of level algorithm, Corollary 13 provides a deterministic procedure to compute the theta structure of type K(n) from a type K(m) structure in time O(n 2g d). p. 3 Similarly, for the isogeny computation algorithm, Corollary 14 offers a deterministic algorithm to compute the theta null point of the quotient abelian variety (A, L, theta L) from the input data of (B, M, theta M) and an isogeny f, achieving a time complexity of O(n g d). p. 4
The algorithms are detailed as Algorithm 7 (Change of level algorithm) and Algorithm 8 (Isogeny computation algorithm), which rely on the properties established for good lifts
and excellent lifts
of subgroups, defined by these compatibility conditions. The paper demonstrates that the non-uniqueness inherent in f-compatible structures is managed algorithmically through choices involving roots of unity in good lifts. p. 3 The overall contribution is providing a robust, general framework for these computations independent of restrictions on d or (d, m), leveraging the established connection between Mumford and f-compatibility. p. 0
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Algorithm 1 can be used to compute an excellent lift of a marked abelian variety from its affine theta null point and a symplectic matrix, providing (0ThetaM with ThetaM = ThetaM o gamma for gamma in Auts(G) such that Psi(gamma) = M).
-
The system can compute the decomposition of B[n] into G1 and G2, where G1 and G2 are isotropic for the Weil pairing eB,n; this decomposition is crucial for change of level algorithms.
-
Algorithm 4 can be used to compute a decomposition of B[n] = G1 x G2 symmetric compatible with 0ThetaM, providing bases for the new coordinates in the resulting theta structure.
-
The system can determine if a point x is symmetric compatible with ThetaM by checking if gf(e) is symmetric compatible with e0ThetaM for all generators e in a set of generators of G.
-
The system can compute the theta null point of an isog-f-compatible marked abelian variety (A, L, ThetaL) from the knowledge of its original theta null point (B, M, ThetaM) and the kernel K and basis B[n].
-
The system can compute a decomposition of B[n] = G1 x G2 symmetric compatible with 0ThetaM using a Gram-Schmit like algorithm to find a basis (w1,..., w2g) where eB,n(wi, wi) = 1 and eB,n(wi, wi+g) = zeta.
-
The system can recover an excellent lift of G from the knowledge of lifts egf(kappa) for kappa in B a chain basis of Z(d) using ScalarMult, ThreeWayAdd, Inv and ThetaAct operations with a running time of O(mg log d).
-
The system can compute the theta null point of a rigidified abelian variety (A, L, ThetaL) isog-f-compatible with (B, M, ThetaM) by computing lifts of egf(kappa) for kappa in B a chain basis of Z(d).
Sources
- Fast computation of 2-isogenies in dimension 4 and cryptographic applications
- Computing isogenies between abelian varieties
- Computing separable isogenies in quasi-optimal time