6
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ Which kind of kernel do you mean? Certainly not $f^{-1}(0)$. Maybe $f^{-1}(1)$? $\endgroup$ – Wolfgang Jul 29 '16 at 16:54
  • $\begingroup$ $f^{-1}(1)$ would quite often be trivial, and not "obviously infinite". $\endgroup$ – Jan-Christoph Schlage-Puchta Jul 29 '16 at 17:02
  • $\begingroup$ @Jan-ChristophSchlage-Puchta Yes, my guess is that it can only be non trivial if the Galois group is non trivial, and probably not even "iff". $\endgroup$ – Wolfgang Jul 29 '16 at 17:16
  • $\begingroup$ @Wolfgang $(x-2)(x-1/2)$ has trivial Galois group but nontrivial kernel. $\endgroup$ – Robert Israel Jul 29 '16 at 17:27
  • 1
    $\begingroup$ What is true is that the kernel is invariant under permutations of indices corresponding to automorphisms of the field extension of $\mathbb Q$ for the polynomial. $\endgroup$ – Robert Israel Jul 29 '16 at 17:42
3
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ many thanks, where can I find more info about the statement? $\endgroup$ – maomao Jul 30 '16 at 8:34
  • $\begingroup$ moreover, can I ask what is $K^*$ here? it is a shame of being a layman :-) $\endgroup$ – maomao Jul 30 '16 at 8:39
  • $\begingroup$ @maomao: I added the definition of $K^{\ast}$, the unit group of the field $K$, to my answer. I don't know of any reference for my above claim. I invite you to scrutinize the case $K = \mathbb{Q}$ and then write a proof of the general case with an introduction to algebraic number theory at hand. $\endgroup$ – Luc Guyot Jul 30 '16 at 11:32
  • $\begingroup$ "the complexity of your problem is exactly the complexity of the prime decomposition in $\mathbb{Z}$" This is true only when you assume $n$ is $O(1)$. The complexity may depend super-exponentially on $n$. $\endgroup$ – WhatsUp Jul 31 '16 at 3:03
  • 2
    $\begingroup$ $n$ is the number of $\lambda_i$. In general the degree of the extension $K/\mathbb{Q}$ can be of order $n!$, making your method super-exponential w.r.t. $n$. Moreover, we will probably need to do arithmetic in the extension $K$, rather than playing with the galois group and reducing to some subfield. This is of course vague, but what I have in mind is the example $g(x) = (x^3 - 2)(x^2 + x + 1)$. $\endgroup$ – WhatsUp Jul 31 '16 at 12:36
2
$\begingroup$

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}$).

$\endgroup$
2
  • $\begingroup$ In step 2, how do you decompose $\tilde{f} \circ \tau(z)\, (z \in \mathbb{Z^d})$ with respect to a basis of $\mathcal{O}^{\times}$? Under which form is a basis $B$ of $\mathcal{O}^{\times} / \text{torsion}$ given? Let us assume we have on hand a primitive element $\alpha$ of $K$ and we know how to write each $\lambda_i$ and each element of $B$ as polynomials in $\alpha$ with coefficients in $\mathbb{Q}$. How to proceed then? $\endgroup$ – Luc Guyot Jul 31 '16 at 17:36
  • 1
    $\begingroup$ @LucGuyot Here again I'm assuming that $K$ is "small". Then we can identify $\mathcal{O}^\times / \textrm{torsion}$ with a lattice in $\mathbb{R}^s$ via the real and imaginary embeddings composed with logarithms, as in Dirichlet's unit theorem. We are then led to solving a linear equation $Mx = y$ with real coefficients, while we know that the solution has integral coefficients. $\endgroup$ – WhatsUp Jul 31 '16 at 18:21
0
$\begingroup$

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.

$\endgroup$

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.