Compute the kernel of multiplication of algebraic numbers

Question

Let $\lambda_1, \dots, \lambda_n$ be the roots of a polynomial $g(x)$ of $n$-degree with rational coefficients and such that $g(0) \neq 0$. (Hence obviously they are non-zero algebraic numbers.)

Consider the function $f: \mathbb{Z}^n\rightarrow A^{\ast}$ defined by $f(z_1, z_2, \dots,z_n)=\lambda_1^{z_1}\lambda_2^{z_2}\cdots\lambda_n^{z_n}$, where $A$ is the field of algebraic numbers. I am interested in computing the kernel of $f$. Specifically, I would like to exhibit generators of this kernel.

Is there an efficient algorithm? Moreover, is there any estimate of the cardinality of the generators?

Answer 1

The rank of $\ker f$ is $n - k$ where $k$ is the free rank of $f(\mathbb{Z}^n)$. The following remark splits the computation of $k$ into two parts; the first can be effectively carried out provided that each norm $N_{K/\mathbb{Q}}(\lambda_i)$ is known:

Let $\lambda_1, \dots, \lambda_n$ be non-zero elements of an algebraic number field $K$. Let $f: \mathbb{Z}^n \rightarrow K^{\ast}$ be the group homomorphism defined by $f(z_1, z_2, \dots, z_n) = \lambda_1^{z_1}\lambda_2^{z_2} \cdots \lambda_n^{z_n}$. Here $K^{\ast}$ stands for the unit group of $K$, i.e., $K^{\ast}$ is $K \setminus \{0\}$ endowed with multiplication. Let $R$ be the ring of integers of $K$ and denote by $F(R)$ the group of its non-zero fractional ideals. Then the free rank of $f(\mathbb{Z}^n)$ is $r + r'$ where $r$ is the rank of the free abelian subgroup of $F(R)$ generated by the principal fractional ideals $(\lambda_i)$, $r'$ is the free rank of $f(\mathbb{Z}^n) \cap R^{\ast}$ and $R^{\ast}$ is the unit group of $R$.

Proof: Consider the group homomorphism $\lambda \mapsto (\lambda)$ from $K^{\ast}$ to $F(R)$.

The computation of $r$ is essentially the same if we suppose $K = \mathbb{Q}$ and consider how many of the vectors $(\nu_p(\lambda_i))_i$ are $\mathbb{Q}$-linearily independent for $p \in \mathbb{N}$ prime and $\nu_p$ the $p$-adic valuation. In this case $r' = 0$ and the generators of $\ker f$ can be computed in polynomial time if you leave aside the problem of factorizing the numerator and denominator of $\lambda_i$ as products of primes.

For the general case, observe indeed that $r$ is the free rank of the image of $N_{K/\mathbb{Q}} \circ f: \mathbb{Z}^n \rightarrow \mathbb{Q}^{\ast}$, $(z_1, z_2, \dots, z_n) \mapsto N_1^{z_1}N_2^{z_2} \cdots N_n^{z_n}$ where $N_i = N_{K/\mathbb{Q}}(\lambda_i) \in \mathbb{Q}$ is the norm of $\lambda_i$ over $\mathbb{Q}$.

How to compute $r'$ in general is unclear to me. Still, Dirichlet's unit theorem provides us with an upper bound and computational results should exist.

My naive impression is that the complexity of your problem is exactly the complexity of the prime decomposition in $\mathbb{Z}$. More instructed readers may prove or disprove this assertion.

Answer 2

This is basically a re-writing of the answer of Luc Guyot. I would like to present not only the calculation of the rank, but also the algorithm for calculating a basis.

Let $K$ be a number field, and let $\lambda_1, \cdots, \lambda_n$ be elements in $K^\times$. Let $f$ be the morphism $\mathbb{Z}^n \rightarrow K^\times$ sending $(z_1, \cdots, z_n)$ to $\lambda_1^{z_1} \cdots \lambda_n^{z_n}$. We want to establish an algorithm for calculating a basis of the kernel $\ker(f)$.

Let $\mathcal{O}$ be the ring of integers of $K$. Write $\mathcal{I}$ for the group of fractional ideals, which is a free abelian group generated by prime ideals of $\mathcal{O}$.

Denote by $\iota$ the canonical map $K^\times \rightarrow \mathcal{I}$ sending $\lambda$ to the principle ideal $\lambda\mathcal{O}$. The map $f$ induces a map $\tilde{f}: \ker(\iota \circ f) \rightarrow \ker(\iota) = \mathcal{O}^\times$, and it is clear that $\ker(f) = \ker(\tilde{f})$.

The algorithm then goes in two steps:

Step 1. Compute a basis of $\ker(\iota \circ f)$, i.e. an isomorphism $\tau:\mathbb{Z}^d \rightarrow \ker(\iota \circ f)$.

This is done by decomposing every $\lambda_i$ into prime ideals, hence reducing to a morphism between $\mathbb{Z}^n$ and $\mathbb{Z}^m$, where $m$ is the number of prime ideals involved.

Step 2. Compute a basis of the kernel of the composition $\tilde{f} \circ \tau:\mathbb{Z}^d \rightarrow \mathcal{O}^\times$, so that $\ker(\tilde{f})$ can be determined via $\ker(\tilde{f}) = \tau(\ker(\tilde{f} \circ \tau))$.

Similarly, this only requires a basis of $\mathcal{O}^\times$. Note that the group $\mathcal{O}^\times$ also has a torsion part, which should be taken into account.

If we assume that the field extension $K/\mathbb{Q}$ is "small", then there are efficient algorithms for both the ideal decomposition and the unit group computation.

---

In the case of the original problem, one should take $K$ to be the splitting field of the polynomial $g(x)$, which (when $g(x)$ is irreducible) typically has degree $n!$ over $\mathbb{Q}$, hence not quite "small". But it should work well in some special cases (e.g. $g(x)$ only have roots in $\mathbb{Q}$).

Answer 3

This answer does not address the question of providing generators for the kernel.

I simply give a rough idea of how to get an upper bound for the kernel dimension. I'll rather give a lower bound for the dimension of the image. I welcome others critical reading of this in case my ideas are shaky.

You do not insist on irreducibility of the polynomial $g(x)$. So all of the $\lambda_j$'s being rational is also an admissible choice. For example take them to be distinct prime numbers. Now unique factorization theorem, can be reformulated as the map $f$ being injective. That is to say, the maximum number of of mutually 'co-prime' rational roots of $g(x)$ gives a lower bound for the rank of the image of $f$.

Next let us consider the case of $g(x)$ being irreducible. Let $K$ be a field of class number 1 containing the roots of $g$.

Then again we can imitate the above statement for rational case.

Now finally the case of $g(x)$ factorising into, say, $k$ irreducible factors. Let $r_1,r_2,\ldots, r_k$ be the lower bound attained in the in each irreducible case. Find the maximum number of mutually linearly disjoint extension fields generated by the roots of these irreducible factors; the sum of $r_j$'s corresponding to the linear disjoint collection will be a lower bound for the rank of the map.