In this post, I will show how to check whether an ideal lattice is well-rounded (WR) using SageMath. We will review the necessary mathematical background, the relevant theory, and provide practical SageMath code examples to illustrate the process.
Most of what I write here is based on (Stewart and Tall 2001), which was also the first book on algebraic number theory that I read.
Let \(B=\{e_1,\cdots,e_m\}\) be a set of linear independent vectors in \(\mathbb{R}^n\) (\(m\le n\)). The set \[ \begin{align} L = \left\{\sum_{i=1}^m a_ie_i\Bigg| a_i\in \mathbb{Z} \right\} \end{align} \] is called the lattice of \(\mathbb{R}^n\) of rank \(m\). The set \(B\) is called the basis of \(L\). Furthermore, we say \(L\) is a full rank lattice if \(m=n\).
The minimal length of \(L\) is defined by \[ \lambda_1(L) = \min\{\|x\|^2: x\in L\setminus \{0\}\} \] where \(\|\cdot\|\) denotes the Euclidean norm on \(\mathbb{R}^n\). The set of shortest vectors of \(L\) is \[S(L):= \{x\in L:\|x\|^2 = \lambda_1(L)\} \]
A lattice \(L\) of dimension \(n\) is said to be well-rounded (WR) if the set \(S(L)\) contains \(n\) linearly independence vectors.
Furthermore, two lattices \(L_1\) and \(L_2\) are called similar if there exist an \(n\times n\) real orthogonal matrix \(O\) and a non real zero constant \(\alpha\) so that \(L_1 = \alpha O L_2\).
Let \(K\) be a number field, i.e., a finite extension of \(\mathbb{Q}\). Since \(\mathbb{Q}\) is perfect, the extension \(K/\mathbb{Q}\) is separable. Thus, every number field is a finite separable extension of \(\mathbb{Q}\). By the Primitive Element Theorem, \(K\) is a simple extension, so there exists \(\alpha \in K\) such that \(K = \mathbb{Q}(\alpha)\). Since \(K/\mathbb{Q}\) is finite, \(\alpha\) is algebraic over \(\mathbb{Q}\).
Moreover, there exists a non-zero \(c \in \mathbb{Z}\) such that \(c\alpha = \theta\), where \(\theta\) is an algebraic integer. Hence, \[K = \mathbb{Q}(\alpha) = \mathbb{Q}(\theta). \]
Let \(m_{\theta,\mathbb{Q}}(x)\) be the minimal polynomial of \(\theta\) over \(\mathbb{Q}\) of degree \(n\), and let \(\theta_1, \dots, \theta_n\) (with \(\theta = \theta_1\)) denote its distinct roots in \(\mathbb{C}\) (all roots are distinct because of the separability of \(K\)). Then there are exactly \(n\) distinct field embeddings (monomorphisms) \(\sigma_i: K \to \mathbb{C}\) \((i = 1, \dots, n)\) such that \(\sigma_i(\theta) = \theta_i\).
We observe that \(\sigma_i(K) \subseteq \mathbb{R}\) if and only if \(\sigma_i(\theta) \in \mathbb{R}\). In this case, \(\sigma_i\) is said to be real; otherwise, it is called complex.
Since complex conjugation \(\tau: \mathbb{C} \to \mathbb{C}\) is a field automorphism, the composition \[ \overline{\sigma}_i := \tau \circ \sigma_i: K \to \mathbb{C} \to \mathbb{C} \] defined by \(\overline{\sigma}_i(\theta) = \overline{\sigma_i(\theta)}\), is also a field embedding. Thus, \(\overline{\sigma}_i = \sigma_j\) for some \(1 \leq j \leq n\).
Moreover, since \(\tau(x) = x\) if and only if \(x \in \mathbb{R}\) and \(\overline{\overline{\sigma}_i} = \sigma_i\), we have that \(\sigma_i\) is real if and only if \(\sigma_i = \overline{\sigma}_i\). In particular, the complex embeddings always occur in conjugate pairs.
Therefore, if \(r_1\) is the number of real embeddings and \(2r_2\) is the number of complex embeddings (which come in pairs), then the total number of embeddings is \(n = r_1 + 2r_2\). Let’s denote \[ \sigma_1\cdots, \sigma_{r_1},\tau_{1},\overline{\tau}_1,\cdots, \tau_{r_2},\overline{\tau}_{r_2} \] are all monomorphisms from \(K\to \mathbb{C}\).
Furthermore, the direct product \(\mathbb{R}^{r_1} \times \mathbb{C}^{r_2}\) is a vector space over \(\mathbb{R}\) of dimension \(r_1 + 2r_2 = n\) (this is also a ring with componentwise operations i.e., \(\mathbb{R}^{r_1} \times \mathbb{C}^{r_2}\) is an \(\mathbb R\)-algebra). We define a map: \[ \begin{align} \sigma:&\ K\to \mathbb{R}^{r_1}\times \mathbb{C}^{r_2}\\ &x\mapsto (\sigma_1(x),\cdots,\sigma_{r_1}(x),\tau_1(x),\cdots,\tau_{r_2}(x)) \end{align} \]
This is a \(\mathbb Q\)-algebra homomorphism, so \(\sigma\) is either the zero map or injective. Since \(\sigma(1) = (1, \dots, 1) \neq 0\), \(\sigma\) must be injective. In other words, this map embeds \(K\) into \(\mathbb{R}^{r_1} \times \mathbb{C}^{r_2}\) as a subring.
Now suppose we view \(\mathbb{R}^{r_1} \times \mathbb{C}^{r_2}\cong \mathbb R^n\) as a vector space over \(\mathbb R\). Since each \(\tau_i(x) \in \mathbb{C}\) can be written as \(\operatorname{Re}(\tau_i(x)) + i\,\operatorname{Im}(\tau_i(x))\), we can write the map above as \[ \begin{align} \sigma:&\ K\to \mathbb{R}^{n}\\ &x\mapsto (\sigma_1(x),\cdots,\sigma_{r_1}(x),\operatorname{Re}(\tau_1(x)),\operatorname{Im}(\tau_1(x)),\cdots,\operatorname{Re}(\tau_{r_2}(x)),\operatorname{Im}(\tau_{r_2}(x))) \end{align} \]
Note that this \(\sigma\) is an \(\mathbb{R}\)-vector space homomorphism. The following results still hold even when we view \(\sigma\) as an \(\mathbb{R}\)-vector space homomorphism.
Theorem: The image of finite generated subgroup of \((K,+)\) under \(\sigma\) is a lattice in \(\mathbb{R}^n\). In particular, if \(G = \langle\omega_1,\cdots,\omega_m\rangle_{\mathbb{Z}}\subseteq (K,+)\), then \(\sigma(G)\) is a lattice with generators \(\{\sigma(\omega_1),\cdots,\sigma(\omega_m)\}\).
Using the above theorem, we have that if \(I\) is an fractional ideal of \(K\), then \(\sigma(I)\) is a full rank lattice of \(\mathbb{R}^n\). And if \(I\) is an integral ideal of \(\mathcal{O}_K\) then \(\sigma(I)\) is a sublattice of \(\sigma(\mathcal{O}_K)\) of finite index . In particular, this index equals to \[ [ \sigma(\mathcal{O}_K): \sigma(I)] = [\mathcal{O}_K : I] = N(I) \] where \(N(\cdot)\) denotes the norm of the ideal \(I\) in \(\mathcal{O}_K\).
These \(\sigma(I)\) are called ideal lattices. Since \(\sigma\) is an embedding, we often identify the ideal \(I\) with its image \(\sigma(I)\) and thus refer to \(I\) itself as an ideal lattice.
from sage.all import *
x = polygen(ZZ, 'x')
K = NumberField(x**Integer(4) - Integer(420)*x**Integer(2) + Integer(40000), names=('y',)); (y,) = K._first_ngens(1)
z = y**Integer(5)/Integer(11); z
R = PolynomialRing(K, names=('y',)); (y,) = R._first_ngens(1)
f = y**Integer(2) + y + Integer(1)
L = K.extension(f, names=('a',)); (a,) = L._first_ngens(1); L
KL = NumberField([x**Integer(4) - Integer(420)*x**Integer(2) + Integer(40000), x**Integer(2) + x + Integer(1)], names=('b',)); (b,) = KL._first_ngens(1); KLimport matplotlib.pyplot as plt
import numpy as np
data = {'a': np.arange(50),
'c': np.random.randint(0, 50, 50),
'd': np.random.randn(50)}
data['b'] = data['a'] + 10 * np.random.randn(50)
data['d'] = np.abs(data['d']) * 100
plt.scatter('a', 'b', c='c', s='d', data=data)
plt.xlabel('entry a')
plt.ylabel('entry b')
plt.show()
flowchart TD
A[Input: number field K and ideal I] --> B[Compute embeddings]
B --> C[Build lattice basis from I]
C --> D[Compute shortest vectors]
D --> E{Do shortest vectors span full rank?}
E -->|Yes| F[The ideal lattice is well-rounded]
E -->|No| G[Not well-rounded]
D --> H[Plot shortest vectors]
H --> I[Use figure in blog]
flowchart LR
subgraph Input
A[Ideal I]
B[Field K]
end
subgraph Computation
C[Minkowski embedding]
D[Lattice basis]
E[Shortest vectors]
end
subgraph Decision
F{Full-rank span?}
G[Well-rounded]
H[Not well-rounded]
end
A --> C
B --> C
C --> D
D --> E
E --> F
F -->|Yes| G
F -->|No| H
sequenceDiagram
participant P as Prover
participant V as Verifier
Note over P: Knows witness w
Note over V: Knows public statement x
P->>V: commitment a
V->>P: random challenge c
P->>V: response z
V->>V: Check Verify(x, a, c, z) = 1
alt Accept
V-->>P: accept
else Reject
V-->>P: reject
end
sequenceDiagram
participant P as Prover P(x,w)
participant V as Verifier V(x)
Note over P,V: Public input: statement x
Note over P: Private input: witness w
P->>P: Sample randomness r
P->>V: a = Commit(x,w,r)
V->>V: Sample challenge c
V->>P: c
P->>P: Compute response z
P->>V: z
V->>V: Accept iff Verify(x,a,c,z)=1
sequenceDiagram
participant P as Prover
participant H as Random Oracle / Hash
participant V as Verifier
P->>P: Compute commitment a
P->>H: Query H(x,a)
H-->>P: challenge c
P->>P: Compute response z
P->>V: proof pi = (a,z)
V->>H: Query H(x,a)
H-->>V: challenge c
V->>V: Check Verify(x,a,c,z)=1