3
$\begingroup$

I asked this earlier on math.stackexchange but I think this is a better place for this question.

Computing the intersection of ideals belonging to the same maximal order of a number field $K$ can be reduced to computing the intersection of lattices of the same dimension.

How can I compute the intersection of an ideal with a maximal order of a subfield, where the underlying lattices no longer have the same dimension?

More concretely, given an ideal $\mathfrak{I} \subset \mathcal{O}_K$ and a subfield $L \subset K$, how can I compute a basis for $\mathfrak{I}\cap\mathcal{O}_L$?

This is relevant, but only leads me to intersection of lattices of equal rank: https://math.stackexchange.com/questions/1560411/basis-for-the-intersection-of-two-integer-lattices

$\endgroup$
1
  • $\begingroup$ Thanks for the comment @David that's exactly what I needed $\endgroup$
    – wyoumans
    May 16 at 13:47
3
$\begingroup$

This reduces easily to computing the intersection of two $\mathbf{Z}$-lattices (not necessarily of full rank) inside $\mathbf{Q}^n$ for some $n$. If you have two lattices $L, M$ of ranks $r$ and $s$, and you let $A$, $B$ be the $r \times n$, resp. $s \times n$, matrices whose rows are bases of $L$ and $M$ respectively, then you can compute the intersection $L \cap M$ by computing the kernel of the $(r + s) \times n$ integer matrix given by stacking $A$ on top of $B$.

(Mathematically, this is relying on the fact that the map from the abstract direct sum $L \oplus M$, to the sum of $L$ and $M$ as submodules of $\mathbf{Q}^n$, has kernel $\{ (v, -v): v \in L \cap M\}$.)

See the Sage library code for the "intersection" method of free modules.

$\endgroup$
2
  • $\begingroup$ There is one additional step here: (assume $r < s$) if the kernel is the $p \times (r+s)$ matrix $U$ for some $p$, the intersection is given by $U'L$ where $U'$ is the $p \times r$ matrix given by the first $r$ columns of $U$. $\endgroup$
    – wyoumans
    May 16 at 15:39
  • $\begingroup$ Also, this can be found in H. Cohen's A Course in Computational Number Theory, algorithm 2.3.9. $\endgroup$
    – wyoumans
    May 16 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.