Let $(U_n)_{n \in \mathbb{N}}$ be a Lucas sequences given by $$U_0 = 0,\quad U_1 = 1,\quad U_n = P U_{n - 1} - Q U_{n-2},$$ where $P,Q$ are integers with $P^2 - 4Q \neq 0$. It is well known that the following product formula holds $$U_n = \prod_{d \mid n} \Phi_d(\alpha, \beta) ,$$ where $\Phi_d(\alpha, \beta) \in \mathbb{Z}$, $$\Phi_k(X,Y) := \prod_{\zeta \,\text{ $k$th primitive root of $1$}}(X - \zeta Y)$$ denotes the $k$th homogenous cyclotomic polynomial, and $\alpha,\beta$ are the two roots of $X^2 - PX + Q = 0$.

Let $(D_n)_{n \in \mathbb{N}}$ be an elliptic divisibility sequence, that is, there exists an elliptic curve $E$ over the rationals with a point $P$ of infinite order, and $D_n$ is determined by $$nP = \left(\frac{A_n}{D_n^2}, \frac{B_n}{D_n^3}\right) ,$$ where $A_n, B_n$ are integers with $\gcd(A_n, D_n) = \gcd(B_n, D_n) = 1$.

As far as I understand, elliptic divisibility sequences have many properties in common with Lucas sequences. For example, like Lucas sequences, they are strong divisibility sequences and (under certain condition) satisfy a primitive divisor theorem.

My question is if there exists a counterpart of cyclotomic polynomials for elliptic divisibility sequences, that is, some quantities $\Psi_d \in \mathbb{Z}$ such that a product formula $$D_n = \prod_{d \mid n} \Psi_d ,$$ holds; and, if so, what is known about $\Psi_d$.


2 Answers 2


The counterpart of the cyclotomic polynomials are elliptic division polynomials, which can be defined recursively by a non-linear recursion (usually presented as a pair of recursions, one for odd indices and one for even). They are classical, dating back to the 19th century, and you can find them in many sources, including for example Exercise 3.7 of my Arithmetic of Elliptic Curves. However, if you take an point $P$ on $E(\mathbb Q)$ and write $\,x(nP)=A_n/D_n^2$, then you generally don't quite get $D_1^{(n^2-1)/2}\Psi_n(x(P))$. The issue is that the generic numerator and denominator of $\,x(nP)\,$ can have some cancellation at primes of bad reduction. So assuming that you've taken a minimal Weierstrass equation you should get something like $$ D_n = \pm D_1^{(n^2-1)/2}\Psi_n(x(P)) \cdot\! \prod_{p\mid \Delta_E} p^{k_{n,p}}, $$ Okay, here $\Psi_n$ is the analogue of $x^n-1$, so now instead of taking $\Psi_n$, which contains the $x$-coordinates of all of the points of order $n$, you can just use only the points whose order is exactly $n$, just as for primitive $n$th roots of unity. Let's call that $\Psi_n^*$, and then $$ \Psi_n = \prod_{d\mid n} \Psi_n^*. $$ Evaluating this at $P$ and multiplying by $D_1$ to the appropriate power will give a decomposition of the sort you want for $D_n$ except that the primes dividing $\Delta_E$ may not work quite right. There's likely some way to adjust them so that everything works, but I don't know a reference offhand.

Addendum: Let $$ E[n] = \{P\in E\!: nP = 0\} \quad\text{and}\quad E[n]^* = \{P\in E\!: \text{$nP=0$ and $mP\ne0$ for $m<n$}\}. $$ Then $$ \Psi_n(X) = \prod_{P\in (E[n]\setminus 0)/\pm1} \bigl(X-x(P)\bigr) $$ and $$ \Psi_n^*(X) = \prod_{P\in (E[n]^*\setminus 0)/\pm1} \bigl(X-x(P)\bigr). $$

  • $\begingroup$ Thanks. Could you please expand a bit on "Okay, here $\Psi_n$ is the analogue ... just as for primitive $n$th roots of unity" ? It seems to me that you are essentially saying that $\Psi_n^* = \prod_{d | n} \Psi_d^{\mu(n/d)}$ (as a previous answer from another user said), but I wonder if instead more is known about $\Psi_n^*$. Feel free to ignore the primes divising $\Delta_E$. $\endgroup$
    – Melania
    Nov 11, 2019 at 8:04
  • $\begingroup$ Hello, I suppose that this polynomials generate abelian extensions of the corresponding quadratic field, it is so?. Do you know if there is some reference/book where these field extensions are developped? $\endgroup$ Nov 11, 2019 at 15:07
  • $\begingroup$ @EstebanCrespi The roots generate abelian extensions if the elliptic curve has CM, I expect that's what you mean. This is all covered in the basic theory of CM that you can find in a standard textbook that covers the theory of CM (Lang, Shimura, my Advanced Topics book, ...). $\endgroup$ Nov 11, 2019 at 15:15

The Wikipedia article Elliptic divisibility sequence uses $\, m | n \implies W_m | W_n.\, $ The article states

... the subsequence $(\pm D_{nk})_{n\ge 1}$ (with an appropriate choice of signs) is an EDS in the earlier sense.

Thus essentially $\,W_n\,$ and $\,D_n\,$ are the same up to a sign, with the advantage that $\,W_n\,$ has addition and duplication formulas as given in the article.

Using the inversion formula we get $\, W_n = \prod_{d|n} \Psi_d $ and $ \Psi_n = \prod_{d|n} W_{n/d}^{\mu(d)}. $

The question is if the $\,\Psi_n\,$ are integers. We have for any prime $\,p\,$ then $\,W_{p^n} = W_{p^{n-1}} \Psi_{p^n}\,$ and by divisibility of the $\,W\,$ sequence, since $\,p^{n-1}|p^n,\,$ then also $\,W_{p^{n-1}}|W_{p^n}\,$ which implies that $\,\Psi_{p^n} = W_{p^n}/W_{p^{n-1}}\,$ is an integer.

We need a theorem that depends on strong divisibility. Working with rational numbers, define $\, a|b \,$ iff $\, b/a \,$ is an integer.

Theorem 1: Let $\, \{W_1,W_2,\dots\}\,$ be any integer divisibility sequence (but also, for simplicity, we assume that $\,W_n = 0\,$ iff $\,n = 0\,$). Let $\,1|n\,$ and $\,1|m.\,$ Define $\, i:=\gcd(n,m),\, j:=\text{lcm}(n,m).\,$ Now $\,i|n|j\,$ and $\,i|m|j\,$ by definition of $\,i\,$ and $\,j.\,$ Define $$ U_n:=W_n/W_i,\quad U_m:=W_m/W_i,\quad U_j:=W_iW_j/(W_nW_m). $$ Then $\,1|U_n, 1|U_m,\,$ and if the sequence has the strong divisibility property then also $\,1|U_j.\,$

Proof: Using the divisibility property, $\,W_i|W_n|W_j\,$ and $\,W_i|W_m|W_j.\,$ This implies $\,W_i|\gcd(W_n,W_m)\,$ and $\, \text{lcm}(W_n,W_m)|W_j.\,$ It also implies $\,1|U_n, 1|U_m\,$ but does not imply $\,1|U_j.\,$ For example, $\,W_i<W_n=W_m=W_j\,$ in which case $\,U_n=U_m\,$ and $\,U_j=W_i/W_n=1/U_n<1,\,$ thus $\,1\!\nmid\!U_j.\,$

Now assuming the strong divisibility property, which is, $\,W_i=\gcd(W_n,W_m),\,$ then it implies that $\,1=\gcd(U_n,U_m).\,$ Since $\,xy=\text{lcm}(x,y)\gcd(x,y)\,$ for all $\,x,y,\,$ we now know that $\, W_nW_m=\text{lcm}(W_n,W_m)W_i.\,$ This implies $\,U_j=W_j/\text{lcm}(W_n,W_m)\,$ and since $\,\text{lcm}(W_n,W_m)|W_j\,$ we now know that $\,1|U_j.\,$ QED

Combining this with unique factorization of integers into powers of primes proves the result that the counterpart of cyclotomic polynomials are integers.

  • 1
    $\begingroup$ I have several concerns about your answer: 1) I don't understand what do you mean with the first sentence; 2) The definition of $W_n$ is not the same of $D_n$; 3) I agree that Mobius inversion formula gives $\Psi_n = \prod_{d | n} D_d^{\mu(n/d)}$, but how can we be sure that $\Psi_n \in \mathbb{Z}$ ? 4) "The question is if the $\Psi_n$ are polynomials" -> polynomials of which quantities? 5) "This follows..." I don't see how. $\endgroup$
    – Melania
    Nov 10, 2019 at 18:21
  • $\begingroup$ I'm not sure how the argument in the last paragraph of your answer works, but the fact that strong divisibility sequences have this $\prod_{d\mid n}$ decompositions appears, e.g., in Theorem 3.1 of Andrzej Nowicki, Strong divisibility and lcm-sequences. $\endgroup$ Nov 10, 2019 at 20:06
  • $\begingroup$ @darijgrinberg I have reworked a more detailed proof. I hope it is correct now. $\endgroup$
    – Somos
    Nov 11, 2019 at 17:04
  • $\begingroup$ The proof is now correct (and nice!), with the minor caveat that you are tacitly assuming that all $W_m$ are nonzero (but this is already used to define $\Psi_m$, unless you start with the $\Psi_m$). $\endgroup$ Nov 11, 2019 at 20:00
  • $\begingroup$ @darijgrinberg Yes, I thought about the zero problem, but all you need is to assume that all $W_n$ are nonzero to begin with. The zero problem is interesting, but I didn't want to complicate things. The EDS article assumes that $W_1W_2W_3\ne 0$ but you could still have some $W_n=0$ further along. $\endgroup$
    – Somos
    Nov 11, 2019 at 22:15

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.