Recent Submissions

  • Geodesics and Bounded Harmonic Functions on Infinite Graphs

    Northshield, Sam (1991)
    It is shown there that an infinite connected planar graph with a uniform upper bound on vertex degree and rapidly decreasing Green's function (relative to the simple random walk) has infinitely many pairwise finitely-intersecting geodesic rays starting at each vertex. We then demonstrate the existence of nonconstant bounded harmonic functions on the graph.
  • Cogrowth of Regular Graphs

    Northshield, Sam (Proceedings of the American Mathematical Society, 1992)
    Let G be a d-regular graph and T the covering tree of G. We define a cogrowth constant of G in T and express it in terms of the first eigenvalue of the Laplacian on G. As a corollary, we show that the cogrowth constant is as large as possible if and only if the first eigenvalue of the Laplacian on G is zero. Grigorchuk's criterion for amenability of finitely generated groups follows.
  • Amenability and superharmonic functions

    Northshield, Sam (Proceedings of the American Mathematical Society, 1993)
    Let G be a countable group and u a symmetric and aperiodic probability measure on G . We show that G is amenable if and only if every positive superharmonic function is nearly constant on certain arbitrarily large subsets of G. We use this to show that if G is amenable, then the Martin boundary of G contains a fixed point. More generally, we show that G is amenable if and only if each member of a certain family of G-spaces contains a fixed point.
  • On the spectrum and Martin boundary of homogeneous spaces

    Northshield, Sam (Statistics and Probability Letters, 1995)
    Given a conservative, spatially homogeneous Markov process X on an homogeneous spaces χ, we show that if the bottom of the spectrum of the generator of X is zero then the Martin boundary of contains a unique point fixed by the isometry group of χ.
  • On the Commute Time of Random Walks on Graphs

    Northshield, Sam; Palacios, Jose Luis (Brazilian Journal of Probability and Statistics, 1995)
    Given a simple random walk on an undirected connected graph, the commute time of the vertices x and y is defined as C(x,y) = ExTy+EyTx. We give a new proof, based on the optional sampling theorem for martingales, of the formula C(x,y) = 1/(Π(y)e(y,x)) in terms of the escape probability e(y,x ) (the probability that once the random walk leaves x, it hits y before it returns to x) and the stationary distribution Π(·). We use this formula for C(x,y) to show that the maximum commute time among all barbell-type graphs in N vertices is attained for the lollipop graph and its value is O[(4N3)/27]
  • A note on the Zeta Function of a Graph

    Northshield, Sam (Journal of Combinatorial Theory Series B, 1998)
    The number of splanning trees in a finite graph is first expressed as the derivative (at 1) of a determinant and then in terms of a zeta function. This generalizes a result of Hashimoto to non-regular graphs.
  • On Iterates of Moebius transformations on fields

    Northshield, Sam (Mathematics of Computation, 1997)
    Let p be a quadratic polynomial over a splitting field K, and S be the set of zeros of p. We define an associative and commutative binary relation on G ≡ K ∪ {∞ } -S so that every Moebius transformation with fixed point set S is of the form x plus" c for some c. This permits an easy proof of Aitken acceleration as well as generalizations of known results concerning Newton's method, the secant method, Halley's method, and higher order methods. If K is equipped with a norm, then we give necessary and sufficient conditions for the iterates of a Moebius transformation m to converge (necessarily to one of its fixed points) in the norm topology. Finally, we show that if the fixed points of m are distinct and the iterates of m converge, then Newton's method converges with order 2, and higher order generalizations converge accordingly.
  • Associativity of the Secant Method

    Northshield, Sam (American Mathematical Monthly, 2002)
    Iterating a function like 1+1/x gives a sequence which converges to the Golden Mean but does so at a much slower rate than those sequences derived from Newton's method or the secant method. There is, however, a surprising relation between all these sequences. This relation, easily explained by the use of good notation, is generalized by means of Pascal's "Mysterium Hexagrammicum". Throughout, we make contact with many areas of mathematics and physics including abstract groups, calculus, continued fractions, differential equations, elliptic curves, Fibonacci numbers, functional equations, fundamental groups, Lie groups, matrices, Moebius transformations, pi, polynomial approximation, relativity, and resistors.
  • On integral Apollonian circle packings

    Northshield, Sam (Journal of Number Theory, 2006)
    The curvatures of four mutually tangent circles with disjoint interior form what is called a Descartes quadruple. The four smallest curvatures of circles in an Apollonian circle packing form what is called a root Descartes quadruple and, if the curvatures are relatively prime, we say that it is a primitive root quadruple. We prove a conjecture of Mallows by giving a closed formula for the number of primitive root quadruples with minimum curvature -n. An Apollonian circle packing is called strongly integral if every circle has curvature times center a Gaussian integer. The set of all such circle packings for which the center of the largest circle is in the unit square and for which curvature plus curvature times center is congruent to 1 modulo 2 is called the standard super-gasket. These centers are in oneto-one correspondence with the primitive root quadruples and exhibit certain symmetries first conjectured by Mallows. We prove these symmetries; in particular, the centers are symmetric around y = x if n is odd, around x = 1/2 if n is an odd multiple of 2, and around y = 1/2 if n is a multiple of 4.
  • Not mixing is just as cool

    Northshield, Sam (Mathematics Magazine, 2007)
    Newton's law of cooling, a staple of the Calculus curriculum, is an empirical law not meant for mathematical proof. However, we show it is mathematically equivalent to the intuitively appealing principle that the average temperature of two cooling objects is equal to the temperature of a single object with initial temperature the average of the other two.
  • On two types of exotic addition

    Northshield, Sam (Aequationes Mathematicae, 2009)
    We classify, under reasonable assumptions, all differentiable functions f for which the 'secant method' [xf(y)- yf(x)]/[f(y)- f(x)] is continuous and associative. Further, we classify all differentiable functions for which the similar type of addition xf(y) + yf(x) is associative.
  • Sums across Pascal's triangle modulo 2

    Northshield, Sam (Congressus Numerantium, 2010)
    We consider sums of the binomial coefficients C(i + j, i) modulo 2 over lines ai + bj = n. Many interesting sequences (old and new) arise this way.
  • On Stern's Diatomic Sequence 0,1,1,2,1,3,2,3,1,4,...

    Northshield, Sam (American Mathematical Monthly, 2010)
    We investigate several of the many interesting properties of the title sequence. In particular, we focus on the combinatorics of the sequence (e.g., what the numbers count), some parallels with the Fibonacci sequence, some connections with Minkowski's question-mark function, and some geometric aspects.
  • Square Roots of 2x2 Matrices

    Northshield, Sam (2010)
    This paper is designed to pique the interest of undergraduate students who are familiar with the concepts of linear algebra. We investigate five methods of computing square roots of two-by-two matrices. Each method gives rise to applications and examples. Topics touched upon include solutions to Abel's functional equation, Fibonacci numbers, Mobius transformations, systems of differential equations, Newton's method applied to matrices (including surprising pictures and open questions), continued fraction representations of matrices, quadratic number fields, and quadratic forms.
  • Integrating across Pascal's triangle

    Northshield, Sam (Mathematical Analysis and Applications, 2011)
    Sums across the rows of Pascal's triangle yield powers of 2 while certain diagonal sums yield the Fibonacci numbers which are asymptotic to powers of the golden ratio. Sums across other diagonals yield quantities asymptotic to powers of c where c depends on the direction of the diagonals. We generalize this to the continuous case. Using the gamma function, we generalize the binomial coefficients to real variables and thus form a generalization of Pascal's triangle. Integration of these generalized binomial coefficients over various families of lines and curves yield quantities asymptotic to powers of some c where c can be determined explicitly. Finally, we revisit the discrete case.
  • A short proof and generalization of Lagrange's theorem on continued fractions

    Northshield, Sam (American Mathematical Monthly, 2011)
    We present a short new proof that the continued fraction of a quadratic irrational eventually repeats. The proof easily generalizes; we construct a large class of functions which, when iterated, must eventually repeat when starting with a quadratic irrational.
  • A root-finding algorithm for cubics

    Northshield, Sam (Proceedings of the American Mathematical Society, 2013)
    Newton's method applied to a quadratic polynomial converges rapidly to a root for almost all starting points and almost all coefficients. This can be understood in terms of an associative binary operation arising from 2 x 2 matrices. Here we develop an analogous theory based on 3 x 3 matrices which yields a two-variable generally convergent algorithm for cubics.
  • A Lyness equation for graphs

    Northshield, Sam (Journal of Difference Equations and Applications, 2012)
    The Lyness equation, x(n+1)=(x(n)+k)/x(n-1), can be though of as an equation defined on the 2-regular tree T2: we can think of every vertex of T2 as a variable so that if x and z are the vertices adjacent to y, then x,y,z satisfy xz=y+k. This makes sense for any 2-regular graph. We generalize this to 3-regular graphs by considering xyz=w+k and xy+xz+yz=w+k where x,y,z are the three neighbors of w. In the special case where an auxiliary condition x+y+z=f(w) also hold, a solutions is determined by (any) two values and, in some cases, an invariant can be found.
  • A New Parameterization of Ford Circles

    Northshield, Sam; McGonagle, Annmarie (Pi Mu Epsilon Journal, 2014)
    Lester Ford introduced Ford Circles in 1938 in order to geometrically understand the approximation of an irrational number by rational numbers. We shall construct Ford circles by a recursive geometric procedure and by a (well-known) parameterization by rational numbers. We introduce a new parameterization in terms of relatively prime integer solutions of (a + b + c)² = a² + b² + c².
  • Complex Descartes Circle Theorem

    Northshield, Sam (American Mathematical Monthly, 2014)
    We present a short proof of Descartes Circle Theorem on the curvature-centers of four mutually tangent circles. Key to the proof is associating an octahedral configuration of spheres to four mutually tangent circles. We also prove an analogue for spheres.