6
$\begingroup$

Suppose we are given three algebraic numbers $\alpha,\beta,\gamma$ by presenting their minimal polynomial (degree less than $m$), the goal is to compute all positive integers $n$ such that $\alpha^n$ lies in the rational combination of $\beta,\gamma$.

Does there exist polynomial time algorithm for this problem?

$\endgroup$
4
  • $\begingroup$ How do you define "compute all" if there are infinitely many? $\endgroup$ Nov 28, 2014 at 16:23
  • 7
    $\begingroup$ This appears to be a special case of the effective Skolem-Mahler-Lech problem, which remains unsolved in general: terrytao.wordpress.com/2007/05/25/… . It may be though that this special case has some additional structure that avoids the problems of the general case. Certainly the SML theorem tells us that the set of n here is eventually periodic, but there is no known effective algorithm (polynomial time or non-polynomial time) to describe it in general. $\endgroup$
    – Terry Tao
    Nov 28, 2014 at 18:13
  • 3
    $\begingroup$ This paper of Blondel and Portier shows that determining whether a general integer linear recurrence contains a zero is NP hard: ams.org/mathscinet-getitem?mr=1917474 . The problem here can be reformulated in terms of such decision problems, but it has a special structure, so it is unclear whether the Blondel-Portier obstruction applies here. Nevertheless this is reason for pessimism regarding a polynomial time algorithm here. $\endgroup$
    – Terry Tao
    Nov 28, 2014 at 18:23
  • $\begingroup$ @Robert The normal way is to give a "description", according to SML theorem,the set of $n$ here is eventually periodic(see Terry Tao's comments). $\endgroup$
    – gondolf
    Nov 30, 2014 at 3:05

1 Answer 1

2
$\begingroup$

Here are some thoughts based on exploiting "special structure" (as alluded to in Terry Tao's comments).

Firstly, here is an argument without reference to Skolem-Mahler-Lech for why there is unlikely to be a polynomial-time algorithm, by considering a very special case: if $\beta, \gamma \in \mathbf{Q}^{\times}$ then the problem amounts to the question of whether $\alpha^n$ is rational for some $n>0$. Once we have integrally scaled $\alpha$ to be an algebraic integer and have factored the constant term of the minimal polynomial of $\alpha$ into prime powers up to a sign, which admittedly is not something known in polynomial time, then prime ideal factorization of rational primes in number fields would take care of this special case. Do you know a way to handle this special case by good use of algebraic number theory avoiding non-polynomial time algorithms?

Back to the original problem. Assume for specificity that a finite extension $K$ of $\mathbf{Q}$ has been given (say by presenting the minimal polynomial of a primitive element for it), and let $\alpha, \beta, \gamma$ be three given elements of $K$ for which the question is posed. (As noted in my comment above, one cannot pin down the question by merely specifying the minimal polynomials of these three elements over $\mathbf{Q}$.) We may as well assume $\alpha \ne 0$ and at least one of $\beta$ or $\gamma$ is nonzero. If $\beta$ and $\gamma$ are $\mathbf{Q}$-linearly dependent then you are just picking a $\mathbf{Q}$-line $L$ in $F$ and asking for which $n > 0$ the power $\alpha^n$ lies in $L$. A necessary and checkable condition is that $L \subset \mathbf{Q}(\alpha)$. Assume this holds, you're just picking a rational line $L$ in $\mathbf{Q}(\alpha)$ and asking for which $n > 0$ the power $\alpha^n$ lies in $L$. Likewise, the case when $\beta$ and $\gamma$ are $\mathbf{Q}$-linearly independent amounts to picking a plane $P$ in $F$ and asking which powers $\alpha^n$ with $n > 0$ lie in $P$. A necessary and checkable condition is that $P \cap \mathbf{Q}(\alpha)$ is nonzero. Assuming this holds, if that (computable) intersection is a line then it becomes the previous question. Otherwise the intersection exhausts the plane $P$ and one instead is faced with the analogous question for $\mathbf{Q}$-planes inside $\mathbf{Q}(\alpha)$.

So, finally, $\beta$ and $\gamma$ are sort of red herrings. The problem is really about $\alpha \ne 0$ and its associated finite extension $\mathbf{Q}(\alpha)$: given a proper $\mathbf{Q}$-linear subspace $V \subset \mathbf{Q}(\alpha)$ of dimension 1 or 2, how do we find those $n > 0$ such that $\alpha^n \in V$? A cruder question is to determine if there is even one such $n$. It is easy to figure out if $\alpha$ is a root of unity, and when so then the entire problem is simple, so we assume $\alpha$ is not a root of unity.

Let's make the following hypothesis (informally stated; experts in algorithms can add precision):

H: There is a "reasonable algorithm" to determine if there is even one such $n$.

If some $\alpha^n$ is rational with $n>0$ (which we can figure out using the "reasonable algorithm" from Hypothesis H for $\mathbf{Q} \subset \mathbf{Q}(\alpha)$) then everything is clear, so we may assume none of these are rational. In particular, if $\dim V = 1$ then there is at most one such $n$, and whether there is one is something we can determine via Hypothesis $H$. So we now focus on the more interesting case $\dim V = 2$.

The problem of whether there are infinitely many such $n$ or not, and the determination of all of them in the "infinite" case, can be carried out as follows. First, run the "reasonable algorithm" from Hypothesis H. If it comes up empty then we're done. So assume we find such an $n_0>0$, and take it to be minimal. We can replace $V$ with $\alpha^{-n_0}V$, so now $1\in V$.

Run the algorithm from Hypothesis H for this new $V$. If it comes up empty then we're done (just the initial $n_0$ works). Suppose it comes up positive, so we may find $n_1 > 0$ such that $\alpha^{n_1} \in V$. Together with 1 this must give a $\mathbf{Q}$-basis of $V$; take $n_1$ to be minimal. If $\alpha^{n_1}$ is quadratic over $\mathbf{Q}$ (easy to figure out) then the possible $n$'s are $n_0 + mn_1$ for $m \ge 0$.

Thus, we now may assume the $\mathbf{Q}$-degree of $\alpha^{n_1}$ is larger than 2, so $V$ is not a subspace of $\mathbf{Q}(\alpha)$ over any nontrivial extension of $\mathbf{Q}$. We claim that there are at most finitely many $n>0$ for which $\alpha^n \in V$. This will be proved by contradiction. Suppose that $V$ were to contain $\alpha^n$ for infinitely many $n>0$. By the non-effective Skolem-Mahler-Lech theorem there would then have to be integers $a > 0$ and $b$ such that $\alpha^n \in V$ for $n = am+b$ with all sufficiently large $m$. But the condition that $\alpha^{am+b} \in V$ for all large $m$ implies that $\alpha^{-b}V$ contains the $\mathbf{Q}$-span of all powers $(\alpha^a)^m$ for sufficiently large $m$, and that span is exactly the field $\mathbf{Q}(\alpha^a) \ne \mathbf{Q}$ (regardless of the lower bound imposed on $m$). Hence, $V$ would have to contain a line over this subfield $\mathbf{Q}(\alpha^a) \subset \mathbf{Q}(\alpha)$, but $V$ is only 2-dimensional over $\mathbf{Q}$ and we have already arranged that it is not a subspace of $\mathbf{Q}(\alpha)$ over any subfield larger than $\mathbf{Q}$, so we have reached a contradiction.

So granting Hypothesis H, at least determining whether there are infinitely many such $n$ or not, and the complete determination of all $n$ in the "infinite" case (always exactly an arithmetic progression) can be handled.


But actually for "generic" $\alpha$ only finitely many such $n$ can exist for each proper subspace $V$ of $K := \mathbf{Q}(\alpha)$. More specifically, if $|\cdot|_1, \dots, |\cdot|_{r_1+r_2}$ are the absolute values on $K$ arising from its $r_1+r_2$ embeddings into $\mathbf{C}$ taken up to complex conjugation then (for fixed but arbitrary $V$) there are only finitely many such $n$ whenever some $|\alpha|_{i_0}$ is strictly larger than $|\alpha|_i$ for all $i \ne i_0$.

To see this, we may increase $V$ to be a hyperplane, so it is the kernel of a nonzero rational linear form $\ell$ on $K$. We may write $\ell(x) = {\rm{Tr}}_{K/\mathbf{Q}}(bx)$ for some $b \in K^{\times}$. Via the $\mathbf{R}$-algebra decomposition $K \otimes_{\mathbf{Q}} \mathbf{R} \simeq \mathbf{R}^{r_1} \times \mathbf{C}^{r_2}$, $\ell_{\mathbf{R}}$ becomes $$(x_1,\dots,x_{r_1+r_2}) \mapsto \sum_{i=1}^{r_1} b_i x_i + \sum_{i=r_1+1}^{r_1+r_2} (b_i x_i + \overline{b}_i \overline{x}_i)$$ where $\{b_i\}$ are the nonzero images of $b$ under the $r_1+r_2$ embeddings (taken up to complex conjugation). If $\alpha^n \in V$ with $n > 0$ then $$0 = \ell(\alpha^n) = \ell_{\mathbf{R}}(\alpha_1^n, \dots, \alpha_{r_1+r_2}^n).$$ If $i_0$ as above corresponds to a real embedding then $|b|_{i_0} |\alpha|_{i_0}^n \le \sum_{i \ne i_0} 2|b|_j |\alpha|_i^n$, so $$|b|_{i_0} \le \sum_{i \ne i_0} 2 |b|_j (|\alpha|_i/|\alpha|_{i_0})^n.$$ But $|b|_{i_0} \ne 0$ and $|\alpha|_i/|\alpha|_{i_0} < 1$, so this gives an upper bound on such $n$'s when $i_0$ is real.

Assume $i_0$ corresponds to a non-real embedding, so instead $$|b_{i_0} + \overline{b}_{i_0} (\overline{\alpha}_{i_0}/\alpha_{i_0})^n)| \le \sum_{i \ne i_0} 2|b|_i (|\alpha|_i/|\alpha|_{i_0})^n$$ with $|\alpha|_i/|\alpha|_{i_0} < 1$ for $i \ne i_0$ and $\overline{\alpha}_{i_0}/\alpha_{i_0}$ is a point on the unit circle distinct from 1. Thus, if arbitrarily large $n$ occur then the right side of this inequality gets arbitrarily close to 0 and so the points $(\overline{\alpha}_{i_0}/\alpha_{i_0})^n$ on the unit circle for such $n$ become arbitrarily close to $-b_{i_0}/\overline{b}_{i_0}$. But Skolem-Mahler-Lech implies that such $n$'s could be taken from all large members of some arithmetic progression, and this would force $\overline{\alpha}_{i_0}/\alpha_{i_0}$ to be a root of unity. Yet if that ratio is indeed a root of unity (something easy to determine algorithmically) then a suitable positive power of $\alpha$ would be real at the $i_0$-embedding, so by replacing $\alpha$ with that power (harmless to do for the purpose of proving the finiteness property) we could also pass to the necessarily proper subfield generated by that power and use degree-induction to conclude.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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