Lionel Levine's Papers
- My thesis is made up primarily of the papers
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.
Back to Lionel Levine's Home Page