Fractal Structures in Multidimensional Integer Arrays Generated by Multivariate Homogeneous Linear Recurrence Relations

The integer entries of Pascal’s triangle, when color-coded according to whether they are even or odd, produce a discrete version of the Sierpinski triangle fractal. We can think of this an example of a connection between a “local” phenomenon — the well-known recurrence relation for binomial coefficients, the entries of Pascal’s triangle, allows these entries to be described entirely in terms of nearby entries — and a “global” phenomenon, in which the color-coding modulo 2 produces patterns of arbitrarily large scale. The fractal nature of the global phenomenon mean that this pattern is particularly visually compelling, exhibiting a distinctive feature called “self-similarity” in which aspects of the pattern repeat across infinitely many scales.In this document we explain and explore the connection between these locally operating multidimensional recurrence relations and the global fractal patterns that result. Specifically, we show that for a certain class of multivariate homogeneous linear recurrence relations, their arrangement of nonzero residues modulo a prime always generates a fractal pattern. We call these functions “Delannoy-like” after the case of the Delannoy numbers, a two-dimensional array which modulo 3 produces another celebrated fractal, the Sierpinski carpet. Our approach is number-theoretic and combinatoric in nature, first by focusing on how these functions count lattice paths and thus obey a general formula, and then showing how this formula embodies the “Lucas property.” This property, which relates the value of a function modulo any prime p to the base-p expansions of its arguments turns out to be the key to establishing the correspondence between recurrence relations and fractals.We also explore compellingly similar phenomena beyond the strict premises of our main result, illustrating fractal-like behavior in the residues of such functions with respect to non-prime moduli or of functions which are not Delannoy-like.