Arithmetic Geometry
Integral points on elliptic curves and explicit valuations of division polynomials
To appear in the Canadian Journal of Mathematics, 41 pages.
[ Show Abstract
 arXiv: 1108.3051  published  pdf ]
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
In memory of Alf van der Poorten, mathematician, colleague, friend.
With
Patrick Ingram,
Valery Mahe,
Joseph H. Silverman, and
Marco Streng.
Journal of the Australian Mathematical Society (special issue dedicated to Alf van der Poorten), 921 (2012), 99126.
[ Show Abstract
 arXiv: 1105.5633  published  pdf ]
In this note we study the existence of primes and of primitive divisors in classical divisibility sequences defined over function fields.
Under various hypotheses, we prove that Lucas sequences and elliptic
divisibility sequences over function fields defined over number fields contain infinitely many irreducible elements. We also prove that an elliptic
divisibility sequence over a function field has only finitely many terms
lacking a primitive divisor.
Character sums with division polynomials
With
Igor E. Shparlinski.
Canadian Mathematical Bulletin, 55 (2012), 850857.
[
Show Abstract

arXiv:
0912.5246

pdf 
published ]
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.
Amicable pairs and aliquot cycles for elliptic curves
With
Joseph H. Silverman.
Experimental Mathematics, 203 (2011), 329357.
[
Show Abstract

arXiv:0912.1831 
pdf

ps 
published 
related website ]
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.
Terms in elliptic divisibility sequences divisible by their indices
With
Joseph H. Silverman.
Acta Arithmetica, 146 (2011), 355378.
[
Show Abstract

arXiv:1001.5303 
pdf 
published ]
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 nets and elliptic curves
Algebra and Number Theory, 52 (2011), 197229.
[
Show Abstract

arXiv: 0710.1316 
pdf 
ps 
published 
errata ]
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.
Cryptography
Provably weak instances of RingLWE
With
Yara Elias,
Kristin E. Lauter, and
Ekin Ozman.
Submitted.
[
Show Abstract

arXiv:pending 
pdf ]
The ring and polynomial learning with errors problems (RingLWE and PolyLWE) have been proposed as hard problems to form the basis for cryptosystems, and various security reductions to hard lattice problems have been presented. So far these problems have been stated for general (number) rings but have only been closely examined for cyclotomic number rings. In this paper, we state and examine the RingLWE problem for general number rings and demonstrate provably weak instances of RingLWE. We construct an explicit family of number fields for which we have an efficient attack. We demonstrate the attack in both theory and practice, providing code and running times for the attack. The attack runs in time linear in q, where q is the modulus.
Our attack is based on the attack on PolyLWE which was presented in [EisenträgerHallgrenLauter].
We extend the attack EHLattack to apply to a larger class of number fields, and show how it applies to attack RingLWE for a heuristically large class of fields. Certain RingLWE instances can be transformed into PolyLWE instances without distorting the error too much, and thus provide the first weak instances of the RingLWE problem.
We also provide additional examples of fields which are vulnerable to our attacks on PolyLWE, including powerof2 cyclotomic fields, presented using the minimal polynomial of ζ_{2n} +/ 1.
RLWE Cryptography for the Number Theorist
With
Yara Elias,
Kristin E. Lauter, and
Ekin Ozman.
Submitted.
[
Show Abstract

arXiv:pending 
pdf ]
In this paper, we survey the status of attacks on the ring and polynomial learning with errors problems (RLWE and PLWE). Recent work on the security of these problems [EHL,
ELOS] gives rise to interesting questions about number fields. We extend these attacks and survey related open problems in number theory, including spectral distortion of an algebraic number and its relationship to Mahler measure, the monogenic property for the ring of integers of a number field, and the size of elements of small order modulo q.
Pairings on hyperelliptic curves
Dedicated to the memory of Isabelle Déchène (19742009)
With
Jennifer Balakrishnan,
Juliana Belding,
Sarah Chisholm,
Kirsten Eisenträger and
Edlyn Teske.
WIN  Women in Numbers: Research Directions in Number Theory, Fields Institute Communications, 60 (2011), 87120.
[
Show Abstract

arXiv:0908.3731 
pdf 
published ]
We assemble and reorganize the recent work in the area of hyperelliptic pairings: We
survey the research on constructing hyperelliptic curves suitable for pairingbased cryptography.
We also showcase the hyperelliptic pairings proposed to date, and develop a unifying framework.
We discuss the techniques used to optimize the pairing computation on hyperelliptic curves, and
present many directions for further research.
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.
[
Show Abstract

IACR eprint 2008/099 
arXiv: 0803.0728 
pdf 
ps 
published ]
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.
[
Show Abstract

IACR eprint 2006/392 
pdf 
ps 
published ]
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
Submitted, 20 pages.
[
Show Abstract

arXiv: 1410.0417 
pdf ]
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
Submitted, 33 pages.
[
Show Abstract

arXiv: 1208.4836 
pdf ]
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
Submitted, 7 pages.
[
Show Abstract

arXiv:1403.2928 
pdf ]
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.
[
Show Abstract

arXiv: 1110.2712 
published 
pdf ]
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.
[
Show Abstract

arXiv: 1104.0961 
pdf 
published 
computer scripts ]
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.
[
Show Abstract


pdf ]
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 and errors.
[
Show Abstract

pdf ]
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.