\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Arithmetic Progressions on Edwards Curves } \vskip 1cm \large Dustin Moody\\ Computer Security Division \\ National Institute of Standards and Technology (NIST)\\ 100 Bureau Drive \\ Gaithersburg, MD, 20899-8930 \\ USA \\ \href{mailto:dbmoody25@gmail.com}{\tt dbmoody25@gmail.com}\\ \end{center} \vskip .2 in \begin{abstract} We look at arithmetic progressions on elliptic curves known as Edwards curves. By an arithmetic progression on an elliptic curve, we mean that the $x$-coordinates of a sequence of rational points on the curve form an arithmetic progression. Previous work has found arithmetic progressions on Weierstrass curves, quartic curves, and genus 2 curves. We find an infinite number of Edwards curves with an arithmetic progression of length 9. \end{abstract} \section{Introduction} Recently, several researchers have looked at arithmetic progressions on elliptic curves. Bremner \cite{B}, Campbell \cite{C}, Garcia-Selfa and Tornero \cite{GT} used elliptic curves given by a Weierstrass equation, while Campbell \cite{C}, MacLeod \cite{M}, and Ulas \cite{U} have looked at quartic models. Alvarado \cite{A}, and Ulas \cite{U2} have extended similar results to genus 2 curves. The historical motivation for this problem is discussed in \cite{GT}. Weierstrass equations and quartic curves are only two of several possible models for elliptic curves. H. Edwards recently proposed a new parameterization for elliptic curves \cite{Edw}. These Edwards curves are of the form $$E_d:x^2+y^2=1+dx^2y^2,$$ with $d \neq 1$. In this work, we look at \emph{arithmetic progressions on Edwards curves}. By this we mean a sequence of rational points $(x_1,y_1), \ldots , (x_n,y_n)$ on $E_d$ with the $x_i$ forming an arithmetic progression. \section{Arithmetic Progressions} Unlike other models for elliptic curves, the Edwards curve $E_d$ has only one parameter we can modify. Still, we are able to prove the following result: \begin{theorem} There are infinitely many choices for $d$ such that the Edwards curve $$E_d: x^2+y^2=1+dx^2y^2,$$ has (at least) 9 points in an arithmetic progression. \end{theorem} \begin{proof} The curve $E_d$ clearly has the points $(-1,0), (0,1), $ and $(1,0)$ for any choice of $d$. We seek to find $d$ to extend this arithmetic progression. In order for the curve to have a point with $x$-coordinate $x=\pm 2$, then we must have $4+y^2=1+4dy^2$, or equivalently $$y^2=\frac{3}{4d-1}.$$ For $y$ to be rational, we need $4d-1=3j^2$, for some rational $j$. Solving this for $d$, this is \begin{equation} \label{eq1} d=\frac{1+3j^2}{4}. \end{equation} For the same reason, if we require that $E_d$ has a point with $x$-coordinate $\pm 3$, then we must have $$y^2=\frac{8}{9d-1}.$$ For $y$ to be rational, we need $9d-1=2k^2$ for some rational $k$, or \begin{equation}\label{eq2} d=\frac{1+2k^2}{9}. \end{equation} Equating $(\ref{eq1})$ and $(\ref{eq2})$ yields the conic $$C_d: 27j^2-8k^2+5=0.$$ By inspection, the point $(1,2)$ lies on the conic. We can use this point to parameterize all rational points on the curve $C_d$: $$(j,k)=\left(\frac{8m^2-32m+27}{8m^2-27}, \frac{-2(8m^2-27m+27)}{8m^2-27} \right),$$ where $m$ is any rational number. By equation \eqref{eq1} (or \eqref{eq2}), \begin{equation} \label{dm} d=\frac{64m^4-384m^3+984m^2-1296m+729}{(8m^2-27)^2}. \end{equation} For any rational $m$, we have found an Edwards curve $E_d$ which has rational points with $x$-coordinates $-3,-2,-1,0,1,2,$ and 3. We now use this to obtain an infinite family of Edwards curves with arithmetic progressions of length (at least) 9. For a rational point to satisfy $x= \pm 4$, then we seek a rational $y$ such that $y^2=\frac{15}{16d-1}$. Substituting in the value of $d$ from equation \eqref{dm}, this is $$y^2=\frac{5(8m^2-27)^2}{(320m^4-2048m^3+5392m^2-6912m+3645)}.$$ Then $y$ will be rational provided that \begin{equation} \label{ec} \frac{1}{5}(320m^4-2048m^3+5392m^2-6912m+3645)=t^2, \end{equation} for some rational $t$. As the discriminant of $320m^4-2048m^3+5392m^2-6912m+3645$ is non-zero, then \eqref{ec} is the equation of an elliptic curve. Using MAGMA \cite{Magma}, this curve is found to be isomorphic to the elliptic curve with Weierstrass equation $$E:y^2=x^3-x^2-19633x-762863.$$ The curve $E$ has rank 2, with generators $(-99,448)$ and $(-93,500)$. There are thus an infinite number of rational points on the curve \eqref{ec}. For each such rational point $(m,t)$, if we substitute this value of $m$ into \eqref{dm}, then we obtain a value of $d$ for which the curve $E_d$ has an arithmetic progression of length 9. Namely, the progression is -4, -3, -2, -1, 0, 1, 2, 3, and 4. \end{proof} \section{Future Work} It is possible that the family of curves given in the proof of Theorem 1 lead to longer arithmetic progressions. We performed a computer search to find a rational point $(m,t)$ on the curve \eqref{ec}, leading to an $E_d$ with points having $x$-coordinates $\pm 5$. Our search has not found such a rational point, thus it is an open problem to find an Edwards curve with an arithmetic progression of length 10 or longer. We remark that it would be interesting to examine other models for elliptic curves for arithmetic progressions. For example, this could include Jacobi intersections \cite{CC} , Hessian curves \cite{JQ}, or Huff curves \cite{Huff}. \begin{thebibliography}{99} \bibitem{A} A. Alvarado, An arithmetic progression on quintic curves, \emph{J. Integer Seq.} {\bf 12} (2009), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL12/Alvarado/alvarado2.html}{Paper 09.7.3}. \bibitem{Magma} W. Bosma, J. Cannon, and C. Playoust, MAGMA 2.14-1, available at \url{http://magma.maths.usyd.edu.au/}. \bibitem{B} A. Bremner, On arithmetic progressions on elliptic curves, \emph{Experiment. Math.} \textbf{8} (1999), 409--413. \bibitem{C} G. Campbell, A note on arithmetic progressions on elliptic curves, \emph{J. Integer Seq.} {\bf 6} (2003), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Campbell/campbell4.html}{Paper 03.1.3}. \bibitem{CC} D. Chudnovsky and G. Chudnovsky, Sequences of numbers generated by addition in formal groups and new primality and factorization tests, \emph{Adv. App. Math.} \textbf{7} (1986), 385--434. \bibitem{Edw} H. Edwards, A normal form for elliptic curves, \emph{Bull. Amer. Math. Soc.} \textbf{44} (2007), 393--422. \bibitem{GT} I. Garc\'{i}a-Selfa and J. Tornero, Searching for simultaneous arithmetic progressions on elliptic curves, \emph{Bull. Austral. Math. Soc.} \textbf{71} (2005), 417--424. \bibitem{Huff} G. Huff, Diophantine problems in geometry and elliptic ternary forms, \emph{Duke Math. J.} \textbf{15} (1948), 443--453. \bibitem{JQ} M. Joye and J. Quisquater, Hessian elliptic curves and side-channel attacks, in \c{C}.K. Ko\c{c}, D. Naccache, and C. Paar, eds., \emph{Proceedings of Cryptographic Hardware and Embedded Systems b CHES 2001}, Springer-Verlag, 2001, pp.\ 402--410. \bibitem{M} A. MacLeod, 14-term arithmetic progressions on quartic elliptic curves, \emph{J. Integer Seq.} {\bf 9} (2006), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL9/MacLeod/macleod11.html}{Paper 06.1.2}. \bibitem{U} M. Ulas, A note on arithmetic progressions on quartic elliptic curves, \emph{J. Integer Seq.} {\bf 8} (2005), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Ulas/ulas7.html}{Paper 05.3.1}. \bibitem{U2} M. Ulas, On arithmetic progressions on genus two curves, \emph{Rocky Mountain J. Math.} \textbf{39} (2009), 971--980. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 11G05; Secondary 11B25. \noindent {\it Keywords}: arithmetic progression, elliptic curve, Edwards curve. \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received December 13 2010; revised version received January 25 2011. Published in {\it Journal of Integer Sequences}, February 8 2011. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}