Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Asymptotic prime-power divisibility
of binomial, generalized binomial,
and multinomial coefficients

Author: John M. Holte
Journal: Trans. Amer. Math. Soc. 349 (1997), 3837-3873
MSC (1991): Primary 05A16; Secondary 11K16
MathSciNet review: 1389778
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper presents asymptotic formulas for the abundance of binomial, generalized binomial, multinomial, and generalized multinomial coefficients having any given degree of prime-power divisibility. In the case of binomial coefficients, for a fixed prime $p$, we consider the number of $(x, y)$ with $0 \leq x, y < p^n$ for which $\binom {x+y}{x}$ is divisible by $p^{zn}$ (but not $p^{zn+1}$) when $zn$ is an integer and $\alpha < z < \beta $, say. By means of a classical theorem of Kummer and the probabilistic theory of large deviations, we show that this number is approximately $p^{n D((\alpha , \beta ))}$, where $D((\alpha , \beta )) := \sup \{ D(z) : \alpha < z < \beta \}$ and $D$ is given by an explicit formula. We also develop a ``$p$-adic multifractal'' theory and show how $D$ may be interpreted as a multifractal spectrum of divisibility dimensions. We then prove that essentially the same results hold for a large class of the generalized binomial coefficients of Knuth and Wilf, including the $q$-binomial coefficients of Gauss and the Fibonomial coefficients of Lucas, and finally we extend our results to multinomial coefficients and generalized multinomial coefficients.

References [Enhancements On Off] (What's this?)

  • 1. W. A. Broomhead, Pascal (mod $p$), Math. Gaz. 56 (1972), No. 398, 267-271. MR 58:5250
  • 2. L. Carlitz, The number of binomial coefficients divisible by a fixed power of a prime, Rend. Circ. Mat. Palermo 16 (1967), 299-320. MR 40:2554
  • 3. G. J. Chaitin, Algorithmic Information Theory, Cambridge U. Press, Cambridge, 1987. MR 89g:68022
  • 4. K. L. Chung, Markov Chains with Stationary Transition Probabilities, second ed., Springer, Berlin, 1967. MR 36:961
  • 5. L. E. Dickson, Analytic representation of substitution, I, Annals of Math. 11 (1897), nos. 3-4, 65-120.
  • 6. L. E. Dickson, History of the Theory of Numbers, Volume I: Divisibility and Primality, Chelsea, New York, 1923; reprint, 1966. MR 39:6807a
  • 7. A. Dembo and O. Zeitouni, Large Deviation Techniques and Applications, Jones and Bartlett, Boston, 1993. MR 95a:60034
  • 8. M. D. Donsker and S. R. S. Varadhan, Asymptotic evaluation of certain Markov process expectations for large time, I, Commun. Pure Appl. Math. 28 (1975), 1-47. MR 52:6883
  • 9. R. S. Ellis, Large deviations for a general class of random vectors, Ann. Probab. 12 (1984), 1-12. MR 85e:60032
  • 10. R. S. Ellis, Entropy, Large Deviations and Statistical Mechanics, Springer-Verlag, New York, 1985. MR 87d:82008
  • 11. L. Euler, Institutiones calculi differentialis, Imperial Academy of Sciences, St. Petersburg, 1755.
  • 12. L. Euler, Opera Omnia (1) 10, Teubner, Leipzig and Berlin, 1913.
  • 13. C. J. G. Evertsz and B. B. Mandelbrot, Multifractal measures, in H.-O. Peitgen, H. Jürgens, and D. Saupe, Chaos and Fractals: New Frontiers of Science, Springer-Verlag, New York, 1992, 921-953. MR 93k:58157
  • 14. K. Falconer, Fractal Geometry: Mathematical Foundations and Applications, J. Wiley, Chichester, 1993. MR 92j:28008
  • 15. J. Feder, Fractals, Plenum Press, New York, 1988. MR 89i:76001
  • 16. W. Fenchel, On conjugate convex functions, Canad. J. Math., 1 (1949), 73-77. MR 10:435b
  • 17. D. Flath and R. Peele, Hausdorff dimension in Pascal's triangle, Applications of Fibonacci Numbers 5, G. E. Bergum et al., eds., Kluwer, Netherlands, 1993, 229-244. MR 95a:11068
  • 18. U. Frisch and G. Parisi, On the singularity structure of fully developed turbulence, in Turbulence and Predictability in Geophysical Fluid Dynamics and Climate Dynamics, M. Ghil, R. Benzi, and G. Parisi, eds., North-Holland, New York, 1985, 84-88.
  • 19. G. Frobenius, Über matrizen aus nicht-negativen elementen, Sitzber. Kgl. Preuss. Akad. Wiss., 1912, 456-477.
  • 20. C. F. Gauss, Summatio quarumdam serierum singularium. Comment. Soc. R. Scient. Gottingensis Rec. 1 (1811), reprinted in his Werke 2 (1863), 9-45.
  • 21. R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, second ed., Addison-Wesley, Reading, Mass., 1994. CMP 96:14; MR 91f:00001 (1st ed.)
  • 22. P. Grassberger, Generalized dimensions of strange attractors, Phys. Lett. A 97 (1983), 227-230. MR 84i:58075
  • 23. F. v. Haeseler, H.-O. Peitgen, and G. Skordev, Pascal's triangle, dynamical systems and attractors, Ergod. Th. & Dynam. Sys. 12 (1992), 479-486. MR 93k:28009
  • 24. J. H. Halton, On the divisibility properties of Fibonacci numbers, Fibonacci Quart. 4 (1966), 217-240. MR 34:1257
  • 25. K. Hensel, Zahlentheorie, Göschen, Berlin, 1913.
  • 26. H. G. E. Hentschel and I. Procaccia, The infinite number of generalized dimensions of fractals and strange attractors, Physica D 8 (1983), 435-444. MR 85a:58064
  • 27. R. Holley and E. C. Waymire, Multifractal dimensions and scaling exponents for strongly bounded random cascades, Ann. Appl. Probab. 2 (1992), 819-845. MR 93k:60122
  • 28. J. Holte, The dimension of the set of multinomial coefficients not divisible by n, Abstracts of the AMS 12, No. 1 (Jan. 1991), 21.
  • 29. J. M. Holte, Carries, combinatorics, and an amazing matrix, Amer. Math. Monthly 104 (1997), 138-149.
  • 30. M. H. Jensen, L. P. Kadanoff, A. Libchaber, I. Procaccia, and J. Stavans, Global universality at the onset of chaos: Results of a forced Rayleigh-Bénard experiment, Phys. Rev. Lett. 55 (1985), 2798-2801.
  • 31. D. E. Knuth, The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, Addison-Wesley, Reading, Mass., 1969, 1981. MR 44:3531; MR 83i:68003
  • 32. D. E. Knuth and H. S. Wilf, The power of a prime that divides a generalized binomial coefficient, J. Reine Angew. Math. 396 (1989), 212-219. MR 90d:11029
  • 33. N. Koblitz, p-adic Numbers, p-adic Analysis, and Zeta-Functions, second ed., Springer-Verlag, New York, 1984. MR 86c:11086
  • 34. E. E. Kummer, Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen, J. Reine Angew. Math. 44 (1852), 93-146.
  • 35. C. T. Long, Pascal's triangle modulo $p$, Fibonacci Quart. 19 (1981), 458-463. MR 83a:05013b
  • 36. E. Lucas, Théorie des fonctions numériques simplement périodiques, Amer. J. Math. 1 (1878), 184-240.
  • 37. B. B. Mandelbrot, Possible refinement of the lognormal hypothesis concerning the distribution of energy dissipation in intermittent turbulence, in Statistical Models and Turbulence, M. Rosenblatt and C. Van Atta, eds., Lecture Notes in Physics 12, Springer-Verlag, New York, 1972, 333-351.
  • 38. B. B. Mandelbrot, Intermittent turbulence in self-similar cascades: Divergence of high moments and dimension of the carrier, J. Fluid Mech. 62 (1974), 331-358.
  • 39. B. B. Mandelbrot, The Fractal Geometry of Nature, W. H. Freeman, New York, 1982, 1983. MR 84h:00021
  • 40. H. Miller, A convexity property in the theory of random variables defined on a finite Markov chain, Ann. Math. Statist. 32 (1961), 1260-1270. MR 23:A4180
  • 41. G. Paladin and A. Vulpiani, Characterization of strange attractors as inhomogeneous fractals, Lett. Nuovo Cimento 41 (1984), 82-86. MR 86b:58075
  • 42. O. Perron, Zur Theorie der Matrizen, Math. Ann. 64 (1907), 248-263.
  • 43. A. M. Reiter, Determining the dimension of fractals generated by Pascal's triangle, Westinghouse Science Talent Search 1990-1991 winning paper.
  • 44. A. M. Reiter, Determining the dimension of fractals generated by Pascal's triangle, Fibonacci Quart. 31 (1993), 112-120. MR 94b:05011
  • 45. A. Rényi, Probability Theory, North-Holland, Amsterdam, 1970. MR 47:4296
  • 46. J. B. Roberts, On binomial coefficient residues, Canadian J. of Math. 9 (1957), 363-370. MR 19:250e
  • 47. R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, 1970. MR 43:445
  • 48. E. Seneta, Non-negative Matrices and Markov Chains, second ed., Springer-Verlag, New York, 1981. MR 85i:60058
  • 49. M. Sved, Divisibility-with visibility, Math. Intelligencer 10 (1988), 56-64. MR 89b:11019
  • 50. W. Sierpi\'{n}ski, Sur une courbe dont tout point est un point de ramification, Comptes Rendus (Paris) 160 (1915), 302.
  • 51. J. Stoer and C. Witzgall, Convexity and Optimization in Finite Dimensions I, Springer-Verlag, Berlin, 1970. MR 44:3707
  • 52. J. R. Weaver, Centrosymmetric (cross-symmetric) matrices, their basic properties, eigenvalues, and eigenvectors, Amer. Math. Monthly 92 (1985), 711-717. MR 87b:15036
  • 53. W. A. Webb and D. L. Wells, Kummer's Theorem, Cantor Bases, and Generalized Binomial Coefficients, preprint.
  • 54. D. L. Wells, The Fibonacci and Lucas triangles modulo 2, Fibonacci Quart. 32 (1994), 111-123. MR 95d:11022
  • 55. H. Wielandt, Unzerlegbare, nicht negative Matrizen, Math. Z. 52 (1950), 642-648. MR 11:710g
  • 56. S. Wolfram, Geometry of binomial coefficients, Amer. Math. Monthly 91 (1984), 566-571. MR 86d:05007

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 05A16, 11K16

Retrieve articles in all journals with MSC (1991): 05A16, 11K16

Additional Information

John M. Holte
Affiliation: Department of Mathematics, Gustavus Adolphus College, St. Peter, Minnesota 56082

Keywords: Binomial coefficients, generalized binomial coefficients, multinomial coefficients, asymptotic enumeration, prime-power divisibility, large deviation principle, carries, Markov chains, multifractals, fractals, $p$-adic numbers
Received by editor(s): December 8, 1995
Received by editor(s) in revised form: March 26, 1996
Article copyright: © Copyright 1997 American Mathematical Society

American Mathematical Society