we obtain

$$|\Delta_K| \geq \prod_{k=1}^{n} \|\alpha_k\|_{\infty}^2 \geq (\lambda_n^{\infty}(\mathcal{O}_K))^{n}.$$

It remains to prove that $C = ([\alpha_k \alpha_l]_n)$ is non-degenerate. Suppose it is not, and there exists $d_l$ for $l \in \{2, \dots, n-1\}$ (not all zero) such that

$$\left[ \sum_{\ell=2}^{n-1} d_{\ell} \alpha_{k} \alpha_{\ell} \right]_{n} = \sum_{\ell=2}^{n-1} d_{\ell} [\alpha_{k} \alpha_{\ell}]_{n} = 0 \text{ for all } k \in \{2, \dots, n-1\}$$

Writing $\beta = \sum_{\ell=2}^{n-1} d_\ell \alpha_\ell$, this means that, for all $k \in \{1, \dots, n-1\}$, $\alpha_k \beta$ lies in the span of $(\alpha_1, \dots, \alpha_{n-1})$. In other words, $L = \mathbb{Q}\alpha_1 + \dots + \mathbb{Q}\alpha_{n-1}$ is $\mathbb{Q}(\beta)$-invariant, i.e., a $\mathbb{Q}(\beta)$-vector (strict) subspace of $K$. That is, $\dim_{\mathbb{Q}(\beta)}(L) \leq \dim_{\mathbb{Q}(\beta)}(K) - 1$. But then

$$n-1 = \dim_{\mathbb{Q}}(L) = \dim_{\mathbb{Q}(\beta)}(L) \cdot [\mathbb{Q}(\beta) : \mathbb{Q}] \\ \leq (\dim_{\mathbb{Q}(\beta)}(K) - 1) \cdot [\mathbb{Q}(\beta) : \mathbb{Q}] = n - [\mathbb{Q}(\beta) : \mathbb{Q}],$$

yielding $[\mathbb{Q}(\beta) : \mathbb{Q}] = 1$, i.e., $\beta \in \mathbb{Q}$, which is impossible by the fact that $\beta = \sum_{\ell=2}^{n-1} d_\ell \alpha_\ell$ is assumed to be non-zero and has no $\alpha_1 = 1$ part.

We conclude that $C$ is non-degenerate, which finishes the proof. $\square$

<figure><img src="image_11.png" /></figure>

### A.4. UPPER BOUND ON A DEFINING POLYNOMIAL OF A NUMBER FIELD

The following two lemmas show together that for any number field $K$ there exists a polynomial $f \in \mathbb{Z}[x]$ such that $K = \mathbb{Q}[x]/(f(x))$ and so that $\text{size}(f) \leq O(\log^2 |\Delta_K| \cdot \log^2(\log |\Delta_K|))$. That is, each field has a 'small' defining polynomial. The first lemma is just a variant of the primitive element theorem [49, V.§4, Theorem 4.6], whereas the second lemma uses this primitive element theorem inductively to bound such a primitive element.

**Lemma A.4.1 (Primitive Element Theorem).** Let $K = \mathbb{Q}(\alpha, \beta)$ be a separable extension. Then there exist an integer $\lambda \in \{0, 1, \dots, d_\alpha \cdot d_\beta\}$ such that $K = \mathbb{Q}(\alpha + \lambda\beta)$, where $d_\alpha = [\mathbb{Q}(\alpha) : \mathbb{Q}]$ and $d_\beta = [\mathbb{Q}(\beta) : \mathbb{Q}]$.

*Proof.* We write $\gamma = \alpha + \lambda\beta$ with $\lambda \in \mathbb{Q}$. Our aim is to show that the number of $\lambda \in \mathbb{Q}$ for which $\mathbb{Q}(\alpha + \lambda\beta) \neq \mathbb{Q}(\alpha, \beta)$ is bounded above by $d_\alpha \cdot d_\beta$, hence, for a certain $\lambda \in \{0, 1, \dots, d_\alpha \cdot d_\beta\}$, it holds that $\mathbb{Q}(\alpha + \lambda\beta) = \mathbb{Q}(\alpha, \beta) = K$; by the pigeon-hole principle.

Write $f_\alpha, f_\beta$ for the minimum polynomial of $\alpha$ respectively $\beta$. Write $\gamma = \alpha + \lambda\beta$. Then we have $f_\alpha(\gamma - \lambda\beta) = 0$, hence $\beta$ is a zero of the polynomial $g = f_\alpha(\gamma - \lambda x) \in \mathbb{Q}(\gamma)[x]$.

So, the minimum polynomial $h_\beta^\gamma$ of $\beta$ over $\mathbb{Q}(\gamma)$ divides $g \in \mathbb{Q}(\gamma)[x]$, but also $f_\beta \in \mathbb{Q}[x]$. So,

$$h_{\beta}^{\gamma} | \gcd(g, f_{\beta}).$$

Suppose $\beta \notin \mathbb{Q}(\gamma)$, then the minimum polynomial $h_\beta^\gamma$ has degree $d \geq 2$, and divides both $g$ and $f_\beta$. By separability, the polynomial $h_\beta^\gamma$ has $d$ distinct roots (in the

<footnote>$n$, living in a real vector space of dimension $2n$ since our lattice is not full rank). To compute the volume of $B$, observe that $B$ consists in $n_\mathbb{R}$ orthogonal copies of $B_\mathbb{R} = \{x \in \mathbb{C} | x \in \mathbb{R}, |x| \leq 1\}$ and $n_\mathbb{C}$ orthogonal copies of $B_\mathbb{C} = \{(x, \bar{x}) \in \mathbb{C}^2 | |x| \leq 1\}$. One can check that $\text{Vol}(B_\mathbb{R}) = 2$ and $\text{Vol}(B_\mathbb{C}) = 2\pi$, leading to $\text{Vol}(B) = 2^{n_\mathbb{R}+n_\mathbb{C}} \cdot \pi^{n_\mathbb{C}}$. Minkowski's second theorem then implies that $\prod_{k=1}^n \lambda_k^\infty(\Lambda) \leq \text{Vol}(\Lambda)$ as desired.</footnote>
algebraic closure of $\mathbb{Q}(\gamma)$), so in particular, there exists $\beta_2 \neq \beta$ such that $h_{\beta}^{\gamma}(\beta_2) = 0$. This $\beta_2$ then satisfies $f_{\beta}(\beta_2) = g(\beta_2) = 0$. Putting $\alpha_2 = \gamma - \lambda\beta_2$ and using the definition of $g$, one can see that $\alpha_2$ is a root of $f_{\alpha}$.

Finally, combining the equations $\alpha = \gamma - \lambda\beta$ and $\alpha_2 = \gamma - \lambda\beta_2$ and using the fact that $\beta \neq \beta_2$, we obtain that $\lambda = \frac{\alpha - \alpha_2}{\beta_2 - \beta}$, where $\beta_2$ is a root of $f_{\beta}$ and $\alpha_2$ is a root of $f_{\alpha}$. There are at most $\deg(f_{\alpha}) \cdot \deg(f_{\beta}) = d_{\alpha}d_{\beta}$ possible $\lambda$ with this shape. Hence, $\mathbb{Q}(\gamma) = \mathbb{Q}(\alpha + \lambda\beta) = \mathbb{Q}(\alpha, \beta)$ for all but $d_{\alpha} \cdot d_{\beta}$ values $\lambda \in \mathbb{Q}$. This was what was remained to be proven. $\square$

**Lemma A.4.2.** Let $K$ be a number field of degree $n$. Then there exists a monic integral irreducible polynomial $g = \sum_{i=0}^{n} g_i x^i \in \mathbb{Z}[x]$ such that $K \simeq \mathbb{Q}[x]/g(x)$ with

$$ \max_i \log |g_i| = O(\log |\Delta_K| \cdot \log \log |\Delta_K|) $$

and hence

$$ \text{size}(g) := \sum_i \log |g_i| = O(\log^2 |\Delta_K| \cdot \log \log |\Delta_K|). $$

*Proof.* Let $O_K$ be the ring of integers of $K$. By definition of the last minimum of a lattice, we know that there exist $n$ linearly independent elements $\beta_1, \dots, \beta_n \in O_K$ satisfying $\|\beta_i\|_{\infty} \le \lambda_i^{(\infty)}(O_K) \le |\Delta_K|^{1/n}$, where we used Theorem A.3.1 for the last inequality.

Since $\beta_1, \dots, \beta_n$ span a $n$-dimensional space, then $K = \mathbb{Q}(\beta_1, \dots, \beta_n)$. Applying the primitive element theorem (in the shape of Lemma A.4.1) inductively, we can then deduce that there exists

$$ \beta = \sum_{i=1}^{n} n_i \beta_i $$

with $n_i \in \{0, 1, \dots, n^2\}$ for all $i$, and such that $K = \mathbb{Q}(\beta)$. Indeed, assume by induction that $K_j := \mathbb{Q}(\beta_1, \dots, \beta_j) = \mathbb{Q}(\gamma_j)$ for some $\gamma_j = \sum_{i=1}^j n_i \beta_i$ as above. Then by Lemma A.4.1, it holds that $K_{j+1} = \mathbb{Q}(\gamma_j, \beta_{j+1}) = \mathbb{Q}(\gamma_j + n_{j+1}\beta_{j+1})$ for some $n_{j+1} \le n^2$ (since all the intermediate fields appearing have degree at most $n$).

Therefore,

$$ \|\beta\|_{\infty} \le n^3 |\Delta_K|^{1/n}. $$

By definition of $\|\beta\|_{\infty}$, this implies that for all embeddings $\sigma_j : K \to \mathbb{C}$, it holds that $|\sigma_j(\beta)| \le n^3 |\Delta_K|^{1/n}$.

Let $g = \sum_{i=0}^{n} g_i x^i$ be the minimal polynomial of $\beta$. Since $\beta \in O_K$ (because the $\beta_i$'s are in $O_K$ and the $n_i$'s are in $\mathbb{Z}$), then $g$ has integer coefficients. Moreover, we have

$$ \begin{aligned} |g_j| &= \left| \sum_{\substack{J \subseteq \{1, \dots, n\} \\ |J| = n-j}} \prod_{i \in J} \sigma_i(\beta) \right| \le \binom{n}{j} (n^3 |\Delta_K|^{1/n})^{n-j} \\ &\le \sum_{j=0}^{n} \binom{n}{j} (n^3 |\Delta_K|^{1/n})^{n-j} = (1 + n^3 |\Delta_K|^{1/n})^n \\ &= n^{3n} |\Delta_K| \left(1 + \frac{1}{n^3 |\Delta_K|^{1/n}}\right)^n \le e \cdot n^{3n} |\Delta_K|, \end{aligned} $$

since $n^3 |\Delta_K|^{1/n} \ge n$.

Hence, $\max_i \log |g_i| = O(n \log(n) + \log |\Delta_K|)$. Using the fact that $n = O(\log |\Delta_K|)$ concludes the proof. $\square$