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 Free Access

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. Antony Broomhead, Pascal (𝑚𝑜𝑑𝑝), Math. Gaz. 56 (1972), no. 398, 267–271. MR 0485410
  • 2. L. Carlitz, The number of binomial coefficients divisible by a fixed power of a prime, Rend. Circ. Mat. Palermo (2) 16 (1967), 299–320. MR 0249308
  • 3. Gregory J. Chaitin, Algorithmic information theory, Cambridge Tracts in Theoretical Computer Science, vol. 1, Cambridge University Press, Cambridge, 1987. With a foreword by J. T. Schwartz. MR 917482
  • 4. Kai Lai Chung, Markov chains with stationary transition probabilities, Second edition. Die Grundlehren der mathematischen Wissenschaften, Band 104, Springer-Verlag New York, Inc., New York, 1967. MR 0217872
  • 5. L. E. Dickson, Analytic representation of substitution, I, Annals of Math. 11 (1897), nos. 3-4, 65-120.
  • 6. Leonard Eugene Dickson, History of the theory of numbers. Vol. I: Divisibility and primality., Chelsea Publishing Co., New York, 1966. MR 0245499
  • 7. Amir Dembo and Ofer Zeitouni, Large deviations techniques and applications, Jones and Bartlett Publishers, Boston, MA, 1993. MR 1202429
  • 8. M. D. Donsker and S. R. S. Varadhan, Asymptotic evaluation of certain Markov process expectations for large time. I. II, Comm. Pure Appl. Math. 28 (1975), 1–47; ibid. 28 (1975), 279–301. MR 0386024
  • 9. Richard S. Ellis, Large deviations for a general class of random vectors, Ann. Probab. 12 (1984), no. 1, 1–12. MR 723726
  • 10. Richard S. Ellis, Entropy, large deviations, and statistical mechanics, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 271, Springer-Verlag, New York, 1985. MR 793553
  • 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. Heinz-Otto Peitgen, Hartmut Jürgens, and Dietmar Saupe, Chaos and fractals, Springer-Verlag, New York, 1992. New frontiers of science; With a foreword by Mitchell J. Feigenbaum; Appendix A by Yuval Fisher; Appendix B by Carl J. G. Evertsz and Benoit B. Mandelbrot. MR 1185709
  • 14. Kenneth Falconer, Fractal geometry, John Wiley & Sons, Ltd., Chichester, 1990. Mathematical foundations and applications. MR 1102677
  • 15. Jens Feder, Fractals, Physics of Solids and Liquids, Plenum Press, New York, 1988. With a foreword by Benoit B. Mandelbrot. MR 949210
  • 16. W. Fenchel, On conjugate convex functions, Canadian J. Math. 1 (1949), 73–77. MR 0028365
  • 17. Dan Flath and Rhodes Peele, Hausdorff dimension in Pascal’s triangle, Applications of Fibonacci numbers, Vol. 5 (St. Andrews, 1992) Kluwer Acad. Publ., Dordrecht, 1993, pp. 229–244. MR 1271363
  • 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. Peter Grassberger, Generalized dimensions of strange attractors, Phys. Lett. A 97 (1983), no. 6, 227–230. MR 718442, 10.1016/0375-9601(83)90753-3
  • 23. Fritz von Haeseler, Heinz-Otto Peitgen, and Gencho Skordev, Pascal’s triangle, dynamical systems and attractors, Ergodic Theory Dynam. Systems 12 (1992), no. 3, 479–486. MR 1182659
  • 24. John H. Halton, On the divisibility properties of Fibonacci numbers, Fibonacci Quart. 4 (1966), 217–240. MR 0201373
  • 25. K. Hensel, Zahlentheorie, Göschen, Berlin, 1913.
  • 26. H. G. E. Hentschel and Itamar Procaccia, The infinite number of generalized dimensions of fractals and strange attractors, Phys. D 8 (1983), no. 3, 435–444. MR 719636, 10.1016/0167-2789(83)90235-X
  • 27. Richard Holley and Edward C. Waymire, Multifractal dimensions and scaling exponents for strongly bounded random cascades, Ann. Appl. Probab. 2 (1992), no. 4, 819–845. MR 1189419
  • 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. Donald E. Knuth, The art of computer programming. Vol. 2: Seminumerical algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont, 1969. MR 0286318
    Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 633878
  • 32. Donald E. Knuth and Herbert S. Wilf, The power of a prime that divides a generalized binomial coefficient, J. Reine Angew. Math. 396 (1989), 212–219. MR 988552, 10.1515/crll.1989.396.212
  • 33. Neal Koblitz, 𝑝-adic numbers, 𝑝-adic analysis, and zeta-functions, 2nd ed., Graduate Texts in Mathematics, vol. 58, Springer-Verlag, New York, 1984. MR 754003
  • 34. E. E. Kummer, Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen, J. Reine Angew. Math. 44 (1852), 93-146.
  • 35. Calvin T. Long, Pascal’s triangle modulo 𝑝, Fibonacci Quart. 19 (1981), no. 5, 458–463. MR 644709
  • 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. Benoit B. Mandelbrot, The fractal geometry of nature, W. H. Freeman and Co., San Francisco, Calif., 1982. Schriftenreihe für den Referenten. [Series for the Referee]. MR 665254
  • 40. H. D. Miller, A convexity property in the theory of random variables defined on a finite Markov chain, Ann. Math. Statist. 32 (1961), 1260–1270. MR 0126886
  • 41. G. Paladin and A. Vulpiani, Characterization of strange attractors as inhomogeneous fractals, Lett. Nuovo Cimento (2) 41 (1984), no. 3, 82–86. MR 770897
  • 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. Ashley Melia Reiter, Determining the dimension of fractals generated by Pascal’s triangle, Fibonacci Quart. 31 (1993), no. 2, 112–120. MR 1214677
  • 45. A. Rényi, Probability theory, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1970. Translated by László Vekerdi; North-Holland Series in Applied Mathematics and Mechanics, Vol. 10. MR 0315747
  • 46. J. B. Roberts, On binomial coefficient residues, Canad. J. Math. 9 (1957), 363–370. MR 0086828
  • 47. R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR 0274683
  • 48. E. Seneta, Nonnegative matrices and Markov chains, 2nd ed., Springer Series in Statistics, Springer-Verlag, New York, 1981. MR 719544
  • 49. Marta Sved, Divisibility—with visibility, Math. Intelligencer 10 (1988), no. 2, 56–64. MR 932163, 10.1007/BF03028359
  • 50. W. Sierpi\'{n}ski, Sur une courbe dont tout point est un point de ramification, Comptes Rendus (Paris) 160 (1915), 302.
  • 51. Josef Stoer and Christoph Witzgall, Convexity and optimization in finite dimensions. I, Die Grundlehren der mathematischen Wissenschaften, Band 163, Springer-Verlag, New York-Berlin, 1970. MR 0286498
  • 52. James R. Weaver, Centrosymmetric (cross-symmetric) matrices, their basic properties, eigenvalues, and eigenvectors, Amer. Math. Monthly 92 (1985), no. 10, 711–717. MR 820054, 10.2307/2323222
  • 53. W. A. Webb and D. L. Wells, Kummer's Theorem, Cantor Bases, and Generalized Binomial Coefficients, preprint.
  • 54. Diana L. Wells, The Fibonacci and Lucas triangles modulo 2, Fibonacci Quart. 32 (1994), no. 2, 111–123. MR 1276376
  • 55. Helmut Wielandt, Unzerlegbare, nicht negative Matrizen, Math. Z. 52 (1950), 642–648 (German). MR 0035265
  • 56. Stephen Wolfram, Geometry of binomial coefficients, Amer. Math. Monthly 91 (1984), no. 9, 566–571. MR 764797, 10.2307/2323743

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
Email: holte@gac.edu

DOI: https://doi.org/10.1090/S0002-9947-97-01794-7
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