[ Arithmetic Geometry | Cryptography ]
[ Circles (number theory and hyperbolic geometry) | Elementary number theory ]
[ Game theory | Commutative algebra | Thesis | Unpublished notes ]


Arithmetic Geometry

Arithmetic properties of the Frobenius traces defined by a rational abelian variety

  • With Alina Carmen Cojocaru, Rachel Davis and Alice Silverberg.
    Preprint.
    [
    Show Abstract
    | arXiv: 1504.00902 | pdf ]

    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

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

    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), 92-1 (2012), 99-126.
    [
    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), 850-857.
    [
    Show Abstract
    | arXiv: 0912.5246pdf | 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 | 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(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.

    Elliptic nets and elliptic curves

    Algebra and Number Theory, 5-2 (2011), 197-229.
    [
    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 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.

    Cryptography

    Provably weak instances of Ring-LWE

    With Yara Elias, Kristin E. Lauter, and Ekin Ozman.
    Submitted.
    [
    Show Abstract
    | arXiv:pending | pdf ]

    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.

    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 (1974-2009)
    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), 87-120.
    [
    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 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.

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

    Circles (number theory and hyperbolic geometry)

    The Apollonian structure of Bianchi groups

    Preprint, 43 pages.
    [
    Show Abstract
    | arXiv: 1505.03121 | pdf ]

    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.

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


    Elementary Number Theory

    An arborist's guide to the rationals

    Submitted, 7 pages.
    [
    Show Abstract
    | arXiv:1403.2928 | pdf ]

    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.


    Game Theory

    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 | 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, 119-7 (2012), 550-565.
    [
    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 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.

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

    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.

    Unpublished Notes

    Formulary for elliptic divisibility sequences and elliptic nets            

    [ pdf ]

    Notes on the Spin Homomorphism            

    [ pdf ]

    Notes on Bhargava's composition laws            

    [ pdf ]