My research falls largely into three main categories. Jump to publications.

The Arithmetic of Kleinian groups

My most recent work was originally motivated by a connection between Apollonian circle packings and the structure of imaginary quadratic fields (in turn coming out of a connection to abelian sandpiles!). A Schmidt arrangement (named for Asmus Schmidt) is the orbit of the extended real line in the extended complex plane under the Mobius action of the Bianchi group PSL2(OK) (here, OK is the ring of integers of the imaginary quadratic field). The resulting fractal of nested circles is an analogue to the Farey subdivision of the real line into nested intervals. It has interesting connections to the arithmetic of the field: for example, it is connected if and only if OK is Euclidean. It turns out the Schmidt arrangement of the Gaussian integers is a union of all primitive integral Apollonian circle packings. In other fields, there are other new packings -- and associated thin groups -- that govern the picture. In this age of computer visualization, there are still new things to discover about topics as classical as imaginary quadratic fields, quadratic forms, hermitian forms, etc.

Students

  • Robert Hines (Ph.D. candidate)
  • Evan Oliver (B.A. Summa Cum Laude 2016)

Summer Research Groups

  • 2015: Andrew Jensen, Cherry Ng, Evan Oliver, Tyler Schrock
  • 2016: Cady Gebhart, Ruofan Li, Daniel Martin, Peter Rock

Arithmetic Geometry

The Fibonacci numbers are governed by a twisted multiplicative group -- for example, primes p appear in the (p2-1)-th term because this is the cardinality of the multiplicative group of Fp2. If you replace the multiplicative group with an elliptic curve, you obtain a recurrence sequence called an elliptic divisibility sequence (this is because the division polynomials satisfy a recurrence coming from the group law). Much of my interest in arithmetic geometry is connected to algebraic divisibility sequences such as these. The sequences carry all sorts of arithmetic information: for example, using a multi-dimensional generalization of elliptic divisibility sequences called elliptic nets, you can compute the Tate-Lichtenbaum pairing as a quotient of certain terms.

Cryptography

I learned from Kristin Lauter that cryptographic applications can give rise to interesting and totally new number theory problems. I've worked on elliptic curve cryptography, and more recently, lattice-based cryptography, which provides the promise of secure post-quantum crypto (quantum computers will be able to solve the elliptic curve discrete logarithm problem). My interest has often been in the security of hard problems. For example, lattice-based cryptography benefits from the extra structure of the ring of integers of a number field, but I'm interested in how that extra structure may provide needed tools to attack problems such as Ring Learning with Errors. I find it fascinating to see the interplay between theory and practice, and to work across disciplines.

Algebraic Number Theory and Arithmetic Dynamics

The core of all three topics above is, of course, algebraic number theory. I'm interested in quadratic forms, Hermitian forms, class field theory, Euclideanity, continued fractions and elementary number theory. I'm also interested in arithmetic dynamics, particularly in taking a dynamical viewpoint on the structure of number fields.

Students

  • Amy Feaver (Ph.D. 2014)
  • Annie S. Chen (Boulder High School)

Postdocs

Find me at:      arXiv      MathSciNet      CV (PDF)

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

Arithmetic of Kleinian groups      Arithmetic geometry      Cryptography

New Preprints

  • The dynamics of super-Apollonian continued fractions with Sneha Chaubey, Elena Fuchs and Robert Hines
    Available, 41 pages. [ show abstract | full text ] 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.

  • Index divisibility in dynamical sequences and cyclic orbits modulo p with Annie S. Chen and T. Alden Gassert
    Submitted, 20 pages. [ show abstract | arXiv:1608.02177 ] Let φ(x) =xd+c be an integral polynomial of degree at least 2, and consider the sequence (φn(0))n=0, which is the orbit of 0 under iteration by φ. Let Dd,c denote the set of positive integers n for which n divides φn(0). We give a characterization of Dd,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.

  • Attacks on Search RLWE with Hao Chen and Kristin Lauter
    Submitted, 16 pages. [ show abstract | IACR eprint 2015/971 ] 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.

To appear

  • The Apollonian structure of Bianchi groups
    To appear in Transactions of the American Mathematical Society, 43 pages. [ show abstract | arXiv:1505.03121 ] 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.

  • Vulnerable Galois RLWE Families and Improved Attacks with Hao Chen and Kristin Lauter
    To appear in Selected Areas in Cryptography 2016, 15 pages. [ show abstract | pdf ] 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.

Published

  • Visualizing the arithmetic of quadratic imaginary fields
    International Mathematics Research Notices (2017) (currently advance access).
    [ show abstract | arXiv:1410.0417 | published | free access link ] 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
    Expositiones Mathematicae, 34-4 (2016), 364-395.
    [ show abstract | arXiv:1208.4836 | published ] 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]2, 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.
    [ show abstract | IACR eprint 2015/758 | arXiv:1508.01375 | published ] 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.

  • 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, (2016), 34 pages.
    [ show abstract | arXiv:1504.00902 | published | free access link ] 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).

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


  • A duality principle for selection games with Lionel Levine and Scott Sheffield
    Proceedings of the American Mathematical Society, 141 (2013), 4349-4356.
    [ show abstract | arXiv:1110.2712 | published ] 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.
    [ show abstract | arXiv:1104.0961 | published | computer scripts ] 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.
    [ show abstract | arXiv:1105.5633 | published ] 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.
    [ show abstract | arXiv:0912.5246 | 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 q1/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.
    [ show abstract | arXiv:0912.1831| 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(Fp) = q and #E(Fq) = 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(Fp) 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.
    [ show abstract | arXiv:1001.5303 | pdf | published ]
    Let D = (Dn)n ≥ 1 be an elliptic divisibility sequence. We study the set S(D) of indices n satisfying n | Dn. 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 Dn, 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.
    [ show abstract | arXiv:0908.3731 | published ] 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.
    [ show abstract | arXiv:0710.1316 | 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 higher-dimensional analogue over arbitrary base fields. Suppose E is an elliptic curve over a field K, and P1, ..., Pn 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.
    [ show abstract | IACR eprint 2008/099 | arXiv:0803.0728 | 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 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.
    [ show abstract | IACR eprint 2006/392 | 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 Zn 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. [ show abstract | arXiv:1403.2928 ] 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 Wooff
    Under revision, 23 pages. [ show abstract | pdf ] 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 a First Proofs Course
    Preprint, 12 pages plus appendices.
    [ show abstract | pdf ] 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

  • The Farey structure of the Gaussian integers
    Asia Pacific Math Newsletter, (6)2, 2016, pp. 10-14.
    [ show abstract | published ] 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.
    [ show abstract | published ] This is a short two-page general exposition of Schmidt arrangements.

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 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

  • Formulary for elliptic divisibility sequences and elliptic nets
    [ show abstract | pdf ] 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
    [ show abstract | pdf ] Expositional notes for Apollonian Circle Packings, 23--27 June, 2014, Mittag-Leffler.

  • Notes on Bhargava's composition laws
    [ show abstract | pdf ] Expositional notes for a seminar.

Support

  • I am grateful to be currently supported in my research by the National Science Foundation of the United States, and to have been supported in past by the National Security Agency and National Science Foundation of the Unites States and the Natural Sciences and Engineering Research Council of Canada.

Collaborators