Lionel Levine's Papers

• My thesis is made up primarily of the papers
  
  
  • Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile; and
    
    
  • Scaling limits for internal aggregation models with multiple sources.
    
    
  Both papers are joint with Yuval Peres. In the first paper, we show that the asymptotic shape of rotor-router aggregation started from a point source in Z^d is a ball, and give bounds on the error (logarithmic inner error, and power-law outer error). Jim Propp first simulated the rotor-router in 2001, and over the next few years widely publicized this problem. Our methods also show that the divisible sandpile model is a ball (with constant error in the radius, independent of the number of particles) and improve on the best known bounds for the classical abelian sandpile.
  
  In the second paper, we study the case of multiple point sources and prove the existence of a scaling limit as the lattice spacing goes to zero. We study three different models: rotor-router, divisible sandpile, and internal DLA. All three have the same deterministic scaling limit, which we characterize as the solution to a certain free boundary obstacle problem. This allows us to define a "smash sum" operation which given two domains A and B in R^d produces a domain whose volume is the sum of the volumes of A and B. The smash sum is the scaling limit of the Diaconis-Fulton addition operation on domains in the lattice Z^d. Smash sums turn out to be examples of quadrature domains, which arise in the solution to many problems in fluid dynamics and electrostatics.
  
  
• In the preprint The sandpile group of a tree, I give a short exact sequence relating the sandpile group of a tree to the sandpile group of its principal subtrees, and find the full decomposition of the sandpile group of a regular tree into cyclic subgroups. This resolved a conjecture of Toumpakari. For the 3-regular tree of height n, for example, the sandpile group is isomorphic to (Z_3)^(2^{n-3}) x (Z_7)^(2^{n-4}) x ... x Z_{2^{n-1}-1} x Z_{2^n-1}.
  
  
• In the preprint The rotor-router model on regular trees, joint with Itamar Landau, we prove that rotor-router aggregation on a regular tree starting from an acyclic rotor-configuration gives a perfect ball. This result uses the structure of the sandpile group from the previous paper. We also investigate what happens if we run a sequence of rotor-router walks starting from the origin in the 3-regular tree, and for each walk record a 0 if it returns to the origin and a 1 if it escapes to infinity. We characterize exactly which binary sequences can arise in this way. There are two extreme cases: the all 0's sequence and the periodic sequence 0,1,0,1,... In particular, it is possible to give an initial rotor setup in the 3-regular tree which makes the rotor-router walk recurrent.
  
  
• Spherical asymptotics for the rotor-router model in Z^d, joint with Yuval Peres, to appear in the Indiana Univ. Math. Journal, was our first result on the circularity of the rotor-router shape. We show that as the number n of particles goes to infinity, almost all the volume of the occupied shape is concentrated in a ball of volume n. The main tool is an isoperimetric inequality for the expected exit time of random walk from a domain in Z^d: among all domains A of a given cardinality, the expected time for a simple random walk started at the origin to exit A is asymptotically maximized when A is a ball.
  
  A summary of this paper, The rotor-router shape is spherical, appeared in the Mathematical Intelligencer 27 (2005), no. 3, 9--11.
  
  
• In Polynomial recurrences and cyclic resultants, joint with Chris Hillar, Proceedings of the AMS 135 (2007), 1607--1618, we show that a sequence a_n obeying a linear recurrence a_{m+n} + c_1 a_{m+n-1} + ... + c_n a_m = 0 satisfies a polynomial recurrence of length r+2, where r is the rank of the subgroup of C^* generated by the roots of the polynomial t^n + c_1 t^{n-1} + ... + c_n. We also show that a certain Toeplitz determinant gives a polynomial recurrence which "detects" if a sequence obeys a linear recurrence of a given length. Using these results, we show that a generic monic polynomial of degree d over an algebraically closed field is determined by its first 2^{d+1} cyclic resultants, i.e. its resultants with x^m-1 for m=1,...,2^{d+1}. Recovering a polynomial from its cyclic resultants has applications in topological dynamics, computational number theory and quantum computing.
  
  
• In Fractal sequences and restricted Nim, Ars Combinatoria 80 (2006), 113--127, I analyze the game of "restricted Nim" using the Sprague-Grundy theory of impartial games, and find that under certain conditions, the Grundy numbers form a sequence which is "fractal" in the sense that deleting the first term equal to n for each nonnegative integer n yields a sequence identical to the original. Restricted Nim is played with a pile of n stones. On her turn, if there are m stones remaining, a player may remove up to f(m) stones from the pile, where the function f is fixed in advance. Fractal sequences arise when f is weakly increasing in m. I also extend work of Clark Kimberling on fractal sequences by giving a new combinatorial characterization.