Papers

Jump to:

• New
• To Appear
• Published
• Older preprints
• Pedagogical Articles
• Expositional Publications
• Ph.D. Thesis
• Unpublish(ed/able) Notes

The following articles are colour-coded to help you find certain topics:

Arithmetic of Kleinian groups      Arithmetic of Abelian varieties      Cryptography

New Preprints

• Prime and Thickened Prime Components in Apollonian Circle Packings
  With Elena Fuchs, Holley Friedlander, Piper Harris, Catherine Hsu, James Rickards, Katherine Sanden and Damaris Schindler.
  41 pages.
  [ arXiv:coming soon; email me  ]
  show abstract

  Inspired by a question of Sarnak, we introduce the notion of a prime component in an Apollonian circle packing: a maximal tangency-connected subset having all prime curvatures. We also consider thickened prime components, which are augmented by all circles immediately tangent to the prime component. In both cases, we ask about the curvatures which appear. We consider the residue classes attained by the set of curvatures, the number of circles in such components, the number of distinct integers occurring as curvatures, and the number of prime components in a packing. As part of our investigation, we computed and analysed example components up to around curvature $10^{13}$; software is available.
  
  .

• Reciprocity obstructions in semigroup orbits in $\text{SL}(2, \mathbb{Z})$
  With James Rickards.
  27 pages.
  [ arXiv:2401.01860 | github code ]
  show abstract

  We study orbits of semigroups of SL(2,ℤ), and demonstrate reciprocity obstructions: we show that certain such orbits avoid squares, but not as a consequence of such obstructions on the Zariski closure, and not as a consequence of congruence obstructions. This is in analogy to the reciprocity obstructions recently used to disprove the Apollonian local-global conjecture. We give an example of such an orbit which is known exactly, and misses all squares together with an explicit finite list of sporadic values: the corresponding semigroup is not thin, but its Zariski closure does not miss squares. We also demonstrate thin semigroups with reciprocity obstructions, including semigroups associated to continued fractions formed from finite alphabets. Zaremba’s conjecture states that for continued fractions with coefficients chosen from {1,…,5}, every positive integer appears as a denominator. Bourgain and Kontorovich proposed a generalization of Zaremba’s conjecture in the context of semigroups associated to finite alphabets. We disprove their conjecture. In particular, we demonstrate classes of finite continued fraction expansions which never represent rationals with square denominator, but not as a consequence of congruence obstructions, and for which the limit set has Hausdorff dimension exceeding 1/2. An example of such a class is continued fractions of the form [0;a₁,a₂,…,a_n,1,1,2], where the ai are chosen from the set {4,8,12,…,128}. The object at the heart of these results is a semigroup Ψ⊆Γ₁(4) which preserves Kronecker symbols.
  
  .

• The Local-Global Conjecture for Apollonian circle packings is False
  With Summer Haag, Clyde Kertzer and James Rickards.
  25 pages.
  [ arXiv:2307.02749 | github code | github data ]
  show abstract

  In a primitive integral Apollonian circle packing, curvatures that appear must fall into one of six or eight residue classes modulo 24. The Local-Global Conjecture states that every sufficiently large integer in one of these residue classes will appear as a curvature in the packing. We prove that this conjecture is false for many packings, by proving that certain quadratic and quartic families are missed. We then formulate a new conjecture, and give computational evidence in support of it.
  .

To appear

• Failing to hash into supersingular isogeny graphs
  With Jeremy Booher, Ross Bowden, Javad Doliskani, Tako Boris Fouotsa, Steven D. Galbraith, Sabrina Kunzweiler, Simon-Philipp Merz, Christophe Petit, Benjamin Smith, Yan Bo Ti, Christelle Vincent, José Felipe Voloch, Charlotte Weitkämper and Lukas Zobernig.
  To appear in The Computer Journal, CFAIL Issue, 31 pages (extended abstract accepted to CFAIL 2022).
  [ eprint:2022/518 | arXiv:2205.00135 | CFAIL presentation ]
  show abstract

  An important open problem in supersingular isogeny-based cryptography is to produce, without a trusted authority, concrete examples of ”hard supersingular curves,” that is, concrete supersingular curves for which computing the endomorphism ring is as difficult as it is for random supersingular curves. Or, even better, to produce a hash function to the vertices of the supersingular ℓ-isogeny graph which does not reveal the endomorphism ring, or a path to a curve of known endomorphism ring. Such a hash function would open up interesting cryptographic applications. In this paper, we document a number of (thus far) failed attempts to solve this problem, in the hopes that we may spur further research, and shed light on the challenges and obstacles to this endeavour. The mathematical approaches contained in this article include: (i) iterative root-finding for the supersingular polynomial; (ii) gcd’s of specialized modular polynomials; (iii) using division polynomials to create small systems of equations; (iv) taking random walks in the isogeny graph of abelian surfaces; and (v) using quantum random walks.

• Orientations and cycles in supersingular isogeny graphs
  With Sarah Arpin, Mingjie Chen, Kristin E. Lauter, Renate Scheidler, and Ha T. N. Tran.
  To appear in the Proceedings of Women in Number Theory 5, 39 pages.
  [ eprint:2022/562 | arXiv:2205.03976 ]
  show abstract

  The paper concerns several theoretical aspects of oriented supersingular l-isogeny volcanoes and their relationship to closed walks in the supersingular l-isogeny graph. Our main result is a bijection between the rims of the union of all oriented supersingular l-isogeny volcanoes over F_p-bar (up to conjugation of the orientations), and isogeny cycles (non-backtracking closed walks which are not powers of smaller walks) of the supersingular l-isogeny graph modulo p. The exact proof and statement of this bijection are made more intricate by special behaviours arising from extra automorphisms and the ramification of p in certain quadratic orders. We use the bijection to count isogeny cycles of given length in the supersingular l-isogeny graph exactly as a sum of class numbers, and also give an explicit upper bound by estimating the class numbers.

Published

• Factoring using multiplicative relations modulo n: a subexponential algorithm inspired by the index calculus
  Mathematical Cryptology, 3(2), 2–10 (issue for MathCrypt 2023).
  [ published | eprint:2022/1588 | arXiv:2211.06821 | github ]
  show abstract

  We demonstrate that a modification of the classical index calculus algorithm can be used to factor integers. More generally, we reduce the factoring problem to finding an overdetermined system of multiplicative relations in any factor base modulo n, where n is the integer whose factorization is sought. The algorithm has subexponential runtime exp(O( (log n)^1/2 (log log n)^1/2 )) (or exp(O( (log n)^2/3 (log log n)^2/3 )) with the addition of a number field sieve), but requires a rational linear algebra phase, which is more intensive than the linear algebra phase of the classical index calculus algorithm. The algorithm is certainly slower than the best known factoring algorithms, but is perhaps somewhat notable for its simplicity and its similarity to the index calculus.
  .

• Orienteering with one endomorphism
  With Sarah Arpin, Mingjie Chen, Kristin E. Lauter, Renate Scheidler, and Ha T. N. Tran.
  La Matematica (currently early online access)
  [ published | arXiv:2201.11079 | github ]
  show abstract

  In supersingular isogeny-based cryptography, the path-finding problem reduces to the endomorphism ring problem. Can path-finding be reduced to knowing just one endomorphism? It is known that a small endomorphism enables polynomial-time path-finding and endomorphism ring computation (Love-Boneh [36]). As this paper neared completion, it was shown that the endomorphism ring problem in the presence of one known endomorphism reduces to a vectorization problem (Wesolowski [54]). In this paper, we give explicit classical and quantum algorithms for path-finding to an initial curve using the knowledge of one endomorphism. An endomorphism gives an explicit orientation of a supersingular elliptic curve. We use the theory of oriented supersingular isogeny graphs and algorithms for taking ascending/descending/horizontal steps on such graphs. Although the most general runtimes are subexponential, we show that every supersingular elliptic curve has (potentially large) endomorphisms whose exposure would lead to a classical polynomial-time path-finding algorithm.

• Algebraic Number Starscapes
  With Edmund Harriss and Steve Trettel.
  Experimental Mathematics, 31:4, 1098-1149
  [ arXiv:2008.07655 | published | accompanying website ]
  show abstract

  We study the geometry of algebraic numbers in the complex plane, and their Diophantine approximation, aided by extensive computer visualization. Motivated by these images, called algebraic starscapes, we describe the geometry of the map from the coefficient space of polynomials to the root space, focussing on the quadratic and cubic cases. The geometry describes and explains notable features of the illustrations, and motivates a geometric-minded recasting of fundamental results in the Diophantine approximation of the complex plane. The images provide a case-study in the symbiosis of illustration and research, and an entry-point to geometry and number theory for a wider audience. The paper is written to provide an accessible introduction to the study of homogeneous geometry and Diophantine approximation.
  We investigate the homogeneous geometry of root and coefficient spaces under the natural PSL(2;C) action, especially in degrees 2 and 3. We rediscover the quadratic and cubic root formulas as isometries, and determine when the map sending certain families of polynomials to their complex roots (our starscape images) are embeddings.
  We consider complex Diophantine approximation by quadratic irrationals, in terms of hyperbolic distance and the discriminant as a measure of arithmetic height. We recover the quadratic case of results of Bugeaud and Evertse, and give some geometric explanation for the dichotomy they discovered (Bugeaud, Y. and Evertse, J.-H., Approximation of complex algebraic numbers by algebraic numbers of bounded degree, Ann. Sc. Norm. Super. Pisa Cl. Sci. (5) 8 (2009), no. 2, 333-368). Our statements go a little further in distinguishing approximability in terms of whether the target or approximations lie on rational geodesics.
  The paper comes with accompanying software, and finishes with a wide variety of open problems..
• Monogenic fields arising from trinomials
  With Ryan Ibarra, Henry Lembeck, Mohammad Ozaslan, and Hanson Smith.
  Accepted to Involve – A Journal of Mathematics.
  [ arXiv:1908.09793 | published ]
  show abstract

  We call a polynomial monogenic if a root θ has the property that Z[θ] is the full ring of integers in Q(θ). Using the Montes algorithm, we find sufficient conditions for xn+ax+b and xn+cxn−1+d to be monogenic (this was first studied by Jakhar, Khanduja, and Sangwan using other methods). Weaker conditions are given for n=5 and n=6. We also show that each of the families xn+bx+b and xn+cxn−1+cd are monogenic infinitely often and give some positive densities in terms of the coefficients.
• Improved torsion point attacks on SIDH variants
  With Victoria de Quehen, Péter Kutas, Chris Leonardi, Chloe Martindale, Lorenz Panny, and Christophe Petit.
  Advances in Cryptology — CRYPTO 2021, Springer LNCS 12827 (2021), 432-470.
  [ published | arXiv:2005.14681 | IACR eprint 2020/633 | video | code ]
  show abstract

  SIDH is a post-quantum key exchange algorithm based on the presumed difficulty of finding isogenies between supersingular elliptic curves. However, SIDH and related cryptosystems also reveal additional information: the restriction of a secret isogeny to a subgroup of the curve (torsion point information). Petit (2017) was the first to demonstrate that torsion point information could noticeably lower the difficulty of finding secret isogenies. In particular, Petit showed that “overstretched” parameterizations of SIDH could be broken in polynomial time. However, this did not impact the security of any cryptosystems proposed in the literature. The contribution of this paper is twofold: First, we strengthen the techniques of Petit by exploiting additional information coming from a dual and a Frobenius isogeny. This extends the impact of torsion point attacks considerably. In particular, our techniques yield a classical attack that completely breaks the n-party group key exchange of Azarderakhsh et al. (2019) for 6 parties or more, and a quantum attack for 3 parties or more that improves on the best known asymptotic complexity. We also provide a Magma implementation of our attack for 6 parties. We give the full range of parameters for which our attacks apply. Second, we construct SIDH variants designed to be weak against our attacks; this includes backdoor choices of starting curve, as well as backdoor choices of base field prime. We stress that our results do not degrade the security of, or reveal any weakness in the NIST submission SIKE of Jao et al.
• Algebraic aspects of solving Ring-LWE, including ring-based improvements in the Blum-Kalai-Wasserman algorithm
  SIAM Journal on Applied Algebra and Geometry, 5(2) (2021): pp. 366–387.
  [ published | arXiv:1902.07140 | IACR eprint 2019/183 | local pdf | code ]
  show abstract

  We provide several reductions of Ring-LWE problems to smaller Ring-LWE problems in the presence of samples of a restricted form (i.e. (a,b) such that a is restricted to a subring, or multiplicative coset of a subfield of one CRT factor). To create and exploit such restricted samples, we propose Ring-BKW, a version of the Blum-Kalai-Wasserman algorithm which respects the ring structure. It has several key advantages based on the ring structure, including smaller tables, reduced or eliminated back-substitution, and a new opportunity for parallelization. We focus on two-power cyclotomic Ring-LWE with parameters proposed for practical use, with the exception that many splitting types are considered. The orthogonality of the lattice for two-power cyclotomics is exploited. In general, higher residue degree is an advantage to attacks.
• Local-global principles in circle packings
  with Elena Fuchs and Xin Zhang
  Compositio Mathematica, 155:6 (2019): pp. 1118-1170.
  [ arXiv:1707.06708 | published ]
  show abstract

  We generalize work of Bourgain-Kontorovich and Zhang, proving an almost
  local-to-global property for the curvatures of certain circle packings, to a
  large class of Kleinian groups. Specifically, we associate in a natural way an
  infinite family of integral packings of circles to any Kleinian group A < PSL₂(K)
  satisfying certain conditions, where K is an
  imaginary quadratic field, and show that the curvatures of the circles in any
  such packing satisfy an almost local-to-global principle. A key ingredient in
  the proof of this is that A possesses a spectral gap property, which
  we prove for any infinite-covolume, geometrically finite, Zariski dense
  Kleinian group in PSL₂(O_K) containing a Zariski dense
  subgroup of PSL₂(Z).
  
  
• The dynamics of super-Apollonian continued fractions
  with Sneha Chaubey, Elena Fuchs and Robert Hines
  Transactions of the American Mathematical Society, 372 (2019), pp. 2287-2334.
  [ arXiv:1703.08616 | published ]
  show abstract

  We examine a pair of dynamical systems on the plane induced by a pair of spanning trees in the Cayley graph of the Super-Apollonian group of Graham, Lagarias, Mallows, Wilks and Yan. The dynamical systems compute Gaussian rational approximations to complex numbers and are ”reflective” versions of the complex continued fractions of A. L. Schmidt. They also describe a reduction algorithm for Lorentz quadruples, in analogy to work of Romik on Pythagorean triples. For these dynamical systems, we produce an invertible extension and an invariant measure, which we conjecture is ergodic. We consider some statistics of the related continued fraction expansions, and we also examine the restriction of these systems to the real line, which gives a reflective version of the usual continued fraction algorithm. Finally, we briefly consider an alternate setup corresponding to a tree of Lorentz quadruples ordered by arithmetic complexity.
  
  
• A family of monogenic S₄ quartic fields arising from elliptic curves
  with T. Alden Gassert and Hanson Smith
  Journal of Number Theory, 197 (2019): pp. 361-382.
  [ arXiv:1708.03953 | published ]
  show abstract

  We consider partial torsion fields (fields generated by a root of a division polynomial) for elliptic curves. By analysing the reduction properties of elliptic curves, and applying the Montes Algorithm, we obtain information about the ring of integers. In particular, for the partial 3-torsion fields for a certain one-parameter family of non-CM elliptic curves, we describe a power basis. As a result, we show that the one-parameter family of quartic S₄ fields given by T⁴ − 6T² − αT − 3 for α ϵ Z such that α ± 8 are squarefree, are monogenic.
  
• The Apollonian structure of Bianchi groups
  Transactions of the American Mathematical Society, 370 (2018), pp. 6169-6219.
  [ arXiv:1505.03121 | published ]
  show abstract

  We study the orbit of the extended real line under the Bianchi group PSL_2(OK), where K is an imaginary quadratic field. The orbit SK, called a Schmidt arrangement, is a geometric realisation, as an intricate circle packing, of the arithmetic of K. We define certain natural subgroups whose orbits generalise Apollonian circle packings, and show that SK, considered with orientations, is a disjoint union of all of these K-Apollonian packings. These packings define a new class of thin groups called K-Apollonian groups. We make a conjecture on the curvatures of these packings, generalizing the local-to-global conjecture of Apollonian circle packings.
  
• Attacks on the Search RLWE Problem with Small Errors
  with Hao Chen and Kristin Lauter
  SIAM Journal on Applied Algebra and Geometry, 1-1 (2017): pp. 665-682.
  [ IACR eprint 2015/971 | published ]
  show abstract

  We describe a new attack on the Search Ring Learning-With-Errors (RLWE) problem based on the chi-square statistical test, and give examples of RLWE instances in Galois number fields which are vulnerable to our attack. We prove a search-to-decision reduction for Galois fields which applies for any unramified prime modulus q, regardless of the residue degree f of q, and we use this in our attacks. The time complexity of our attack is O(q^{2f}), where f is the residue degree of q in K.We also show an attack on the RLWE problem in general cyclotomic rings (non 2-power cyclotomic rings) which works when the modulus is a ramified prime. We demonstrate the attacks in practice by finding many vulnerable instances and successfully attacking them. We include the code for all attacks.
  
• Visualizing the arithmetic of quadratic imaginary fields
  International Mathematics Research Notices (2017) (currently advance access).
  [ arXiv:1410.0417 | published | free access link ]
  show abstract

  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.
  
• Security Considerations for Galois Non-dual RLWE Families
  with Hao Chen and Kristin Lauter
  Selected Areas in Cryptography 2016 — SAC 2016, LNCS vol 10532, pp. 443-462.
  [ IACR eprint 2016/193 | published ]
  show abstract

  This paper makes several improvements to the number theoretical attacks on RLWE presented in recent papers of Chen-Lauter-Stange and Elias-Lauter-Ozman-Stange, including presenting an infinite family of Galois number fields vulnerable to attack, a substantial runtime improvement, and an analysis of the security of cyclotomic fields.
   
• Index divisibility in dynamical sequences and cyclic orbits modulo p
  with Annie S. Chen and T. Alden Gassert
  New York Journal of Mathematics, 23 (2017), pp. 1045-1063.
  [ arXiv:1608.02177 | published ]
  show abstract

  Let φ(x) =xd+c be an integral polynomial of degree at least 2, and consider the sequence (φⁿ(0))_n=0^∞, which is the orbit of 0 under iteration by φ. Let D_d,c denote the set of positive integers n for which n divides φⁿ(0). We give a characterization of D_d,c in terms of a directed graph and describe a number of its properties, including its cardinality and the primes contained therein. In particular, we study the question of which primes p have the property that the orbit of 0 is a single p-cycle modulo p. We show that the set of such primes is finite when d is even, and conjecture that it is infinite when d is odd.
• Arithmetic properties of the Frobenius traces defined by a rational abelian variety
  with Alina Carmen Cojocaru, Rachel Davis and Alice Silverberg, and with two appendices by J-P. Serre
  International Mathematics Research Notices, 12 (2017), 3557-3602.
  [ arXiv:1504.00902 | published | free access link ]
  show abstract

  Let A be an abelian variety over the rationals. Under suitable hypotheses, we formulate a conjecture about the asymptotic behaviour of the Frobenius traces a_(1,p) of A reduced modulo varying primes p. This generalizes a well-known conjecture of S. Lang and H. Trotter from 1976 about elliptic curves. We prove upper bounds for the counting function #{p <= x: a_(1,p) = t} and we investigate the normal order of the number of prime factors of a_(1,p).
• The sensual Apollonian circle packing
  Expositiones Mathematicae, 34-4 (2016), 364-395.
  [ arXiv:1208.4836 | published ]
  show abstract

  The curvatures of the circles in integral Apollonian circle packings, named for Apollonius of Perga (262-190 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]², inspired by, and intimately related to, the `sensual quadratic form’ of Conway.
• RLWE Cryptography for the Number Theorist
  with Yara Elias, Kristin E. Lauter, and Ekin Ozman
  Women in Numbers 3: Research Directions in Number Theory Springer AWM Series, Vol. 3 (2016), 271-290.
  [ IACR eprint 2015/758 | arXiv:1508.01375 | published ]
  show abstract

  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.
• Integral points on elliptic curves and explicit valuations of division polynomials
  Canadian Journal of Mathematics, 68 (2016), 1120-1158.
  [ arXiv:1108.3051 | published ]
  show abstract

  Assuming Lang’s conjectured lower bound on the heights of non-torsion points on an elliptic curve, we show that there exists an absolute constant C such that for any elliptic curve E/Q and non-torsion 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 non-singular 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.
• Provably weak instances of Ring-LWE
  with Yara Elias, Kristin E. Lauter, and Ekin Ozman.
  Advances in Cryptology — CRYPTO 2015, Springer LNCS 9215 (2015), 63-92.
  [ arXiv:1502.03708 | published ]
  show abstract

  The ring and polynomial learning with errors problems (Ring-LWE and Poly-LWE) 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 Ring-LWE problem for general number rings and demonstrate provably weak instances of Ring-LWE. 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 Poly-LWE which was presented in [Eisenträger-Hallgren-Lauter].
  We extend the attack EHL-attack to apply to a larger class of number fields, and show how it applies to attack Ring-LWE for a heuristically large class of fields. Certain Ring-LWE instances can be transformed into Poly-LWE instances without distorting the error too much, and thus provide the first weak instances of the Ring-LWE problem. We also provide additional examples of fields which are vulnerable to our attacks on Poly-LWE, including power-of-2 cyclotomic fields, presented using the minimal polynomial of ζ_2ⁿ +/- 1.
• A duality principle for selection games
  with Lionel Levine and Scott Sheffield
  Proceedings of the American Mathematical Society, 141 (2013), 4349-4356.
  [ arXiv:1110.2712 | published ]
  show abstract

  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, 119-7 (2012), 550-565.
  [ arXiv:1104.0961 | published | computer scripts ]
  show abstract

  If you are sharing a meal with a companion, how best to make sure you get your favourite fork-fulls? 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.
• Algebraic divisibility sequences over function fields
  with Patrick Ingram, Valery Mahe, Joseph H. Silverman, and Marco Streng
  In memory of Alf van der Poorten, mathematician, colleague, friend.
  Journal of the Australian Mathematical Society (special issue dedicated to Alf van der Poorten), 92-1 (2012), 99-126.
  [ arXiv:1105.5633 | published ]
  show abstract

  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), 850-857.
  [ arXiv:0912.5246 | published ]
  show abstract

  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, 20-3 (2011), 329-357.
  [ arXiv:0912.1831| published | related website ]
  show abstract

  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), 355-378.
  [ arXiv:1001.5303 | published ]
  show abstract

  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.
• Pairings on hyperelliptic curves
  with Jennifer Balakrishnan, Juliana Belding, Sarah Chisholm, Kirsten Eisenträger and Edlyn Teske.
  Dedicated to the memory of Isabelle Déchène (1974-2009)
  WIN — Women in Numbers: Research Directions in Number Theory, Fields Institute Communications, 60 (2011), 87-120.
  [ arXiv:0908.3731 | published ]
  show abstract

  We assemble and reorganize the recent work in the area of hyperelliptic pairings: We
  survey the research on constructing hyperelliptic curves suitable for pairing-based 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.
• Elliptic nets and elliptic curves
  Algebra and Number Theory, 5-2 (2011), 197-229.
  [ arXiv:0710.1316 | published | errata ]
  show abstract

  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 higher-dimensional analogue
  over arbitrary base fields. Suppose E is an elliptic curve over a field K, and
  P₁, …, P_n are points on E defined over K. To this information we associate
  an n-dimensional 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.
• 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), 309-327.
  [ IACR eprint 2008/099 | arXiv:0803.0728 | published ]
  show abstract

  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 sub-exponential time if and
  only if the elliptic curve discrete logarithm problem is solvable in
  sub-exponential time.  We also relate the problem of EDS
  Association to the Tate pairing and the MOV, Frey-Ruck and Shipsey EDS
  attacks on the elliptic curve discrete logarithm problem in the cases
  where these apply.
• The Tate pairing via elliptic nets
  Pairing-Based Cryptography — PAIRING 2007, Springer LNCS, 4575 (2007), 329-348.
  [ IACR eprint 2006/392 | published ]
  show abstract

  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ⁿ 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 pairing-based
  cryptography. The new algorithm has time complexity comparable to
  Miller’s algorithm, and is likely to yield to further optimisation.

Older Preprints

• An arborist’s guide to the rationals
  Under revision, 7 pages.
  [ arXiv:1403.2928 ]
  show abstract

  There are two well-known ways to enumerate the positive rational numbers in an infinite binary tree: the Farey/Stern-Brocot tree and the Calkin-Wilf 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.
  
  
• General Zelevinsky Algebras with Peter Hoffman and Chris WooffUnder revision, 23 pages.
  [ pdf ]
  show abstract

  Here we show that a fairly general notion of `Hopf algebra with positivity and self-adjointness’ 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.
  
  

Pedagogical Articles

• Standards Based Grading in an Introduction to Abstract Mathematics
  To appear in PRIMUS: Problems, Resources and Issues in Mathematics Undergraduate Studies, 27 pages plus appendices.
  [ pdf | published ]
  show abstract

  Standards-based grading, in which grading should be designed to communicate to students their current level of mastery with regards to well-articulated standards, is becoming popular at the K-12 level. As yet, the literature addressing standards-based grading at the university level is scarce. In this paper, I document my attempts to put into practice the principles of standards based grading in a lower-level undergraduate mathematics course which aims to introduce mathematical proof.
  
  

Expositional Publications

• On the importance of illustration in mathematical research
  With Rémi Coulon, Gabriel Dorfsman-Hopkins, Edmund Harriss, Martin Skrodzki, and Glen Whitney
  Preprint.
  [ arXiv:2307.04636 ]
  show abstract

  Mathematical understanding is built in many ways. Among these, illustration has been a companion and tool for research for as long as research has taken place. We use the term illustration to encompass any way one might bring a mathematical idea into physical form or experience, including hand-made diagrams or models, computer visualization, 3D printing, and virtual reality, among many others. The very process of illustration itself challenges our mathematical understanding and forces us to answer questions we may not have posed otherwise. It can even make mathematics an experimental science, in which immersive exploration of data and representations drive the cycle of problem, conjecture, and proof. Today, modern technology for the first time places the production of highly complicated models within the reach of many individual mathematicians. Here, we sketch the rich history of illustration, highlight important recent examples of its contribution to research, and examine how it can be viewed as a discipline in its own right.
• The ingenious physical factoring devices of D. N. Lehmer
  Math Horizons, 30:2 (2022), pp. 8-11.
  [ published ]
  show abstract

  A short article about factor stencils and other physical factoring devices.
• The Farey structure of the Gaussian integers
  Asia Pacific Math Newsletter, (6)2, 2016, pp. 10-14.
  [ published ]
  show abstract

  This is a short four-page general exposition of the analogy between the Gaussian Schmidt arrangement and the Farey fractions, and their connections to hyperbolic geometry.
  
  
• Visualizing imaginary quadratic fields
  Canadian Mathematical Society Notes September 2016, 2 pages.
  [ published ]
  show abstract

  This is a short two-page general exposition of Schmidt arrangements.
  
  
• An illustration in number theory (2019 Lecture Sampler)
  Notices of the American Mathematical Society, 66(03), 2019, pp. 411-413.
  [ published ]
  show abstract

  This is an overview of my invited talk at the AMS Joint Central/Western Sectional in March 2019.

Ph.D. Thesis

• Elliptic nets and elliptic curves
  Ph.D. Thesis, Brown University, 2008, 297 pages including computer code and errors.
  [ pdf | Brown library ]
  show abstract

  The sequence of division polynomials for an elliptic curve satisfies a non-linear 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 n-tuples of integers; for n=1, one obtains the division polynomials. This collection satisfies a certain non-linear recurrence relation. Any array satisfying this relation is called an elliptic net. The evaluation of the array of functions at a curve and n-tuple 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 Tate-Lichtenbaum 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.
  
  

Unpublish(ed/able) Notes

• Frobenius and the endomorphism ring of j=1728
  [ pdf ]
  show abstract

  We give the endomorphism ring of the supersingular elliptic curve with j=1728, and show that although the endomorphism ring is invariant under isomorphism of the curve, the placement of Frobenius in that endomorphism ring is not.
  
• Quadratic forms, lattices and ideal classes
  [ pdf ]
  show abstract

  A concise treatment of the bijection between imaginary quadratic ideal classes and positive definite integral binary quadratic forms.
  
  
• Formulary for elliptic divisibility sequences and elliptic nets
  [ pdf ]
  show abstract

  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
  [ pdf ]
  show abstract

  Expositional notes for Apollonian Circle Packings, 23–27 June, 2014, Mittag-Leffler.
  
  
• Notes on Bhargava’s composition laws
  [ pdf ]
  show abstract

  Expositional notes for a seminar.