Elliptic Curves and Algebraic Divisibility Sequences
Integral points on elliptic curves and explicit valuations of division polynomials 


Submitted, 37 pages.
 Assuming Lang's conjectured lower bound on the heights of nontorsion points on an elliptic curve, we show that there exists an absolute constant C such that for any elliptic curve E/Q and nontorsion point P in E(Q), there is at most one integral multiple [n]P such that n > C. The proof is a modification of a proof of Ingram giving an unconditional but not uniform bound. The new ingredient is a collection of explicit formulae for the sequence of valuations of the division polynomials. For P of nonsingular reduction, such sequences are already well described in most cases, but for P of singular reduction, we are led to define a new class of sequences called elliptic troublemaker sequences, which measure the failure of the Néron local height to be quadratic. As a corollary in the spirit of a conjecture of Lang and Hall, we obtain a uniform upper bound on the height of integral points having two large integral multiples, in terms of the height of the curve.
Algebraic divisibility sequences over function fields 

Elliptic nets and elliptic curves 


Algebra and Number Theory, 52 (2011), 197229.
 An elliptic divisibility sequence is an integer recurrence sequence
associated to an elliptic curve over the rationals together with a rational
point on that curve. In this paper we present a higherdimensional analogue
over arbitrary base fields. Suppose E is an elliptic curve over a field K, and
P_{1}, ..., P_{n} are points on E defined over K. To this information we associate
an ndimensional array of values in K satisfying a nonlinear recurrence
relation. Arrays satisfying this relation are called elliptic nets. We
demonstrate an explicit bijection between the set of elliptic nets and the set
of elliptic curves with specified points. We also obtain
Laurentness/integrality results for elliptic nets.
Amicable pairs and aliquot cycles for elliptic curves 


With Joseph H. Silverman.
Experimental Mathematics, 203 (2011), 329357.
 An amicable pair for an elliptic curve E/Q is a pair of primes (p,q) of good reduction for E satisfying #E(F_{p}) = q and #E(F_{q}) = p. In this paper we study elliptic amicable pairs and analogously defined longer elliptic aliquot cycles. We show that there exist elliptic curves with arbitrarily long aliqout cycles, but that CM elliptic curves (with j not 0) have no aliqout cycles of length greater than two. We give conjectural formulas for the frequency of amicable pairs. For CM curves, the derivation of precise conjectural formulas involves a detailed analysis of the values of the Grossencharacter evaluated at a prime ideal P in End(E) having the property that #E(F_{p}) is prime. This is especially intricate for the family of curves with j = 0.
Character sums with division polynomials 


With Igor E. Shparlinski.
To appear in Canadian Mathematical Bulletin, 8 pages.
 We obtain nontrivial estimates of quadratic character sums of division polynomials ψ_{n}(P), n=1,2, ..., evaluated at a given point P on an elliptic curve over a finite field of q elements. Our bounds are nontrivial if the order of P is at least q^{1/2 + ε} for some fixed ε > 0. This work is motivated by an open question about statistical indistinguishability of some cryptographically relevant sequences which has recently been brought up by K. Lauter and the second author.
Terms in elliptic divisibility sequences divisible by their indices 


With Joseph H. Silverman.
Acta Arithmetica, 146 (2011), 355378.
 Let D = (D_{n})_{n ≥ 1} be an elliptic divisibility sequence. We study the set S(D) of indices n satisfying n  D_{n}. In particular, given an index n in S(D), we explain how to construct elements nd in S(D), where d is either a prime divisor of D_{n}, or d is the product of the primes in an aliquot cycle for D. We also give bounds for the exceptional indices that are not constructed in this way.
Elliptic Curve Cryptography
Pairings on hyperelliptic curves 

The elliptic curve discrete logarithm problem and equivalent hard problems for elliptic divisibility sequences 


With Kristin E. Lauter.
Selected Areas in Cryptography 2008, Springer LNCS, 5381 (2009), 309327.
 We define three hard problems in terms of the theory of elliptic
divisibility sequences (EDS Association, EDS Residue and EDS
Discrete Log), each of which is solvable in subexponential time if and
only if the elliptic curve discrete logarithm problem is solvable in
subexponential time. We also relate the problem of EDS
Association to the Tate pairing and the MOV, FreyRuck and Shipsey EDS
attacks on the elliptic curve discrete logarithm problem in the cases
where these apply.
The Tate pairing via elliptic nets 


PairingBased Cryptography  PAIRING 2007, Springer LNCS, 4575 (2007), 329348.
 We derive a new algorithm for computing the Tate
pairing on an elliptic curve over a finite field. The algorithm uses a
generalisation of elliptic divisibility sequences known as elliptic
nets, which are maps from Z^{n} to a ring that satisfy a certain
recurrence relation. We explain how an elliptic net is associated to an
elliptic curve and reflects its group structure. Then we give a formula
for the Tate pairing in terms of values of the net. Using the
recurrence relation we can calculate these values in linear time.
Software
the Tate pairing is the bottleneck to efficient pairingbased
cryptography. The new algorithm has time complexity comparable to
Miller's algorithm, and is likely to yield to further optimisation.
Circles (number theory and hyperbolic geometry)
Visualising the arithmetic of quadratic imaginary fields 


Preprint, 20 pages.

We study the orbit of the real line under the Bianchi group PSL_2(OK), where K is an imaginary quadratic field. The orbit, called a Schmidt arrangement, is a geometric realisation, as an intricate circle packing, of the arithmetic of K. This paper presents several examples of this phenomenon. First, we show that the curvatures of the circles are integer multiples of √Δ and describe the curvatures of tangent circles in terms of the norm form of OK. Second, we show that the circles themselves are in bijection with certain ideal classes in orders of OK, the conductor being a certain multiple of the curvature. This allows us to count circles with class numbers. Third, we show that the arrangement of circles is connected if and only if OK is Euclidean. These results are meant as foundational for a study of a new class of thin groups generalising Apollonian groups, in a companion paper.
The sensual Apollonian circle packing 


Preprint, 33 pages.

The curvatures of the circles in integral Apollonian circle packings, named for Apollonius of Perga (262190 BC), form an infinite collection of integers whose Diophantine properties have recently seen a surge in interest. Here, we give a new description of Apollonian circle packings built upon the study of the collection of bases of Z[i]^{2}, inspired by, and intimately related to, the `sensual quadratic form' of Conway.
Elementary Number Theory
An arborist's guide to the rationals 


Preprint, 7 pages.

There are two wellknown ways to enumerate the positive rational numbers in an infinite binary tree: the Farey/SternBrocot tree and the CalkinWilf tree. In this brief note, we describe these two trees as `transpose shadows' of a tree of matrices (a result due to Backhouse and Ferreira) via a new proof using yet another famous tree of rationals: the topograph of Conway and Fung.
Game Theory
A duality principle for selection games 


With Lionel Levine and Scott Sheffield.
Proceedings of the American Mathematical Society, 141 (2013), 43494356.

A dinner table seats k guests and holds n discrete morsels of food. Guests select morsels in turn until all are consumed. Each guest has a ranking of the morsels according to how much he would enjoy eating them; these rankings are commonly known.
A gallant knight always prefers one food division over another if it provides strictly more enjoyable collections of food to one or more other players (without giving a less enjoyable collection to any other player) even if it makes his own collection less enjoyable. A boorish lout always selects the morsel that gives him the most enjoyment on the current turn, regardless of future consumption by himself and others.
We show the way the food is divided when all guests are gallant knights is the same as when all guests are boorish louts but turn order is reversed. This implies and generalizes a classical result of Kohler and Chandrasekaran (1971) about two players strategically maximizing their own enjoyments. We also treat the case that the table contains a mixture of boorish louts and gallant knights.
Our main result can also be formulated in terms of games in which selections are made by groups. In this formulation, the surprising fact is that a group can always find a selection that is simultaneously optimal for each member of the group.
How to make the most of a shared meal: plan the last bite first 


With Lionel Levine.
American Mathematical Monthly, 1197 (2012), 550565.
 If you are sharing a meal with a companion, how best to make sure you get your favourite forkfulls? Ethiopian Dinner is a game in which two players take turns eating morsels from a common plate. Each morsel comes with a pair of utility values measuring its tastiness to the two players. Kohler and Chandrasekaharan discovered a good strategy  a subgame perfect equilibrium, to be exact  for this game. We give a new visual proof of their result. The players arrive at the equilibrium by figuring out their last move first and working backward. We conclude that it's never too early to start thinking about dessert.
Commutative Algebra
General Zelevinsky Algebras 


With Peter Hoffman and Chris Wooff.
Under revision, 23 pages.
 Here we show that a fairly general notion of `Hopf algebra with positivity and selfadjointness' admits a decomposition into a tensor product of `atomic' such objects. Then, for an infinite family of base rings, we classify the atomic objects. This generalizes both a theorem of Zelevinsky, which he applied to linear representations of various families of groups, and an analogous theorem of Bean and Hoffman, which had applications to projective representations of symmetric and alternating groups (and more generally to some covering groups of monomial groups). The sequence of examples for which the classification is complete starts with these two earlier results. The remaining terms of the sequence will apply to representations of covers of certain wreath product groups.
Ph.D. Thesis
Elliptic nets and elliptic curves 

 Ph.D. Thesis, Brown University, 2008, 297 pages including computer code.

The sequence of division polynomials for an elliptic curve satisfies a nonlinear recurrence relation. Specialising to a chosen elliptic curve and evaluating at a chosen point gives a recurrence sequence in the field over which curve and point are defined. In the field of rational numbers, Morgan Ward showed in 1948 that all sequences satisfying this particular recurrence relation arise from division polynomials. These are called elliptic divisibility sequences. In this thesis, we define a higher rank generalisation of elliptic divisibility sequences called elliptic nets. To do so, we define rational functions called net polynomials in analogy to division polynomials. For any integer n, we define a collection of such net polynomials in n variables indexed by ntuples of integers; for n=1, one obtains the division polynomials. This collection satisfies a certain nonlinear recurrence relation. Any array satisfying this relation is called an elliptic net. The evaluation of the array of functions at a curve and ntuple of points gives an elliptic net with values in K. Conversely, any elliptic net over K arises from the net polynomials evaluated at some elliptic curve and tuple of points. In this thesis, we make precise the correspondence between elliptic curves and elliptic nets, over arbitrary fields. We describe the Laurentness properties of elliptic nets, and generalise the `symmetry properties' observed by Morgan Ward and others. It is shown that the Poincaré biextension of an elliptic curve crossed with itself has a factor system given by the net polynomials. As a consequence, the TateLichtenbaum and Weil pairings for an elliptic curve have a description in terms of elliptic nets. This leads to a new algorithm for computing these pairings by computing terms of elliptic nets. The complexity of this algorithm is examined. Finally, some hard computational problems for elliptic nets are related to the elliptic curve discrete logarithm problem over finite fields, with a view toward cryptographic security.
Unpublished Notes
Formulary for elliptic divisibility sequences and elliptic nets 


Just the formulas. No warranty is expressed or implied. May cause side effects. Not to be taken internally. Remove label before using. Not to be used as a flotation device. May contain nuts. Please report any errors you may find.
Notes on the Spin Homomorphism 

 With Yongqi Feng.
 Expositional notes for Apollonian Circle Packings, 2327 June, 2014, MittagLeffler.
Notes on Bhargava's composition laws 


Expositional notes for a seminar.