The Euler binary partition function and subdivision schemes

Protasov, Vladimir

doi:10.1090/mcom/3128

The Euler binary partition function and subdivision schemes
HTML articles powered by AMS MathViewer

by Vladimir Yu. Protasov PDF

Math. Comp. 86 (2017), 1499-1524 Request permission

Abstract:

For an arbitrary set $D$ of nonnegative integers, we consider the Euler binary partition function $b(k)$ which equals the total number of binary expansions of an integer $k$ with “digits” from $D$. By applying the theory of subdivision schemes and refinement equations, the asymptotic behaviour of $b(k)$ as $k \to \infty$ is characterized. For all finite $D$, we compute the lower and upper exponents of growth of $b(k)$, find when they coincide, and present a sharp asymptotic formula for $b(k)$ in that case, which is done in terms of the corresponding refinable function. It is shown that $b(k)$ always has a constant exponent of growth on a set of integers of density one. The sets $D$ for which $b(k)$ has a regular power growth are classified in terms of cyclotomic polynomials.

References

Katherine Anders, Melissa Dennison, Jennifer Weber Lansing, and Bruce Reznick, Congruence properties of binary partition functions, Ann. Comb. 17 (2013), no. 1, 15–26. MR 3027571, DOI 10.1007/s00026-013-0188-3
Lothar Berg and Gerlind Plonka, Spectral properties of two-slanted matrices, Results Math. 35 (1999), no. 3-4, 201–215. MR 1694902, DOI 10.1007/BF03322813
Marc A. Berger and Yang Wang, Bounded semigroups of matrices, Linear Algebra Appl. 166 (1992), 21–27. MR 1152485, DOI 10.1016/0024-3795(92)90267-E
Peter Borwein and Kwok-Kwong Stephen Choi, On cyclotomic polynomials with $\pm 1$ coefficients, Experiment. Math. 8 (1999), no. 4, 399–407. MR 1737235
N. G. de Bruijn, On Mahler’s partition problem, Nederl. Akad. Wetensch., Proc. 51 (1948), 659–669 = Indagationes Math. 10, 210–220 (1948). MR 25502
L. Carlitz, Generating functions and partition problems, Proc. Sympos. Pure Math., Vol. VIII, Amer. Math. Soc., Providence, R.I., 1965, pp. 144–169. MR 0175796
Alfred S. Cavaretta, Wolfgang Dahmen, and Charles A. Micchelli, Stationary subdivision, Mem. Amer. Math. Soc. 93 (1991), no. 453, vi+186. MR 1079033, DOI 10.1090/memo/0453
G. M. Chaikin, An algorithm for high speed curve generation, Comp. Graphics and Image. Proc. 3 (1974), 346–349.
R. F. Churchhouse, Congruence properties of the binary partition function, Proc. Cambridge Philos. Soc. 66 (1969), 371–376. MR 248102, DOI 10.1017/s0305004100045072
Ingrid Daubechies and Jeffrey C. Lagarias, Two-scale difference equations. II. Local regularity, infinite products of matrices and fractals, SIAM J. Math. Anal. 23 (1992), no. 4, 1031–1079. MR 1166574, DOI 10.1137/0523059
Georges de Rham, Sur une courbe plane, J. Math. Pures Appl. (9) 35 (1956), 25–42 (French). MR 90628
Georges de Rham, Sur les courbes limites de polygones obtenus par trisection, Enseign. Math. (2) 5 (1959), 29–43 (French). MR 108796
G. Derfel, N. Dyn, and D. Levin, Generalized refinement equations and subdivision processes, J. Approx. Theory 80 (1995), no. 2, 272–297. MR 1315413, DOI 10.1006/jath.1995.1019
Artūras Dubickas, The divisors of Newman polynomials, Fiz. Mat. Fak. Moksl. Semin. Darb. 6 (2003), 25–28 (English, with English and Lithuanian summaries). MR 2025528
Jean Marie Dumont, Nikita Sidorov, and Alain Thomas, Number of representations related to a linear recurrent basis, Acta Arith. 88 (1999), no. 4, 371–396. MR 1690457, DOI 10.4064/aa-88-4-371-396
Nira Dyn, John A. Gregory, and David Levin, Analysis of uniform binary subdivision schemes for curve design, Constr. Approx. 7 (1991), no. 2, 127–147. MR 1101059, DOI 10.1007/BF01888150
Nira Dyn and David Levin, Subdivision schemes in geometric modelling, Acta Numer. 11 (2002), 73–144. MR 2008967, DOI 10.1017/S0962492902000028
L. Euler, Introductio in analysin infinitorum, Lausanne, 1798, in Opera Omnia Series Prima Opera Math., Vol. 8, B. G. Teubner, Leipzig, 1922.
De-Jun Feng, Pierre Liardet, and Alain Thomas, Partition functions in numeration systems with bounded multiplicity, Unif. Distrib. Theory 9 (2014), no. 1, 43–77. MR 3237075
De-Jun Feng and Nikita Sidorov, Growth rate for beta-expansions, Monatsh. Math. 162 (2011), no. 1, 41–60. MR 2747343, DOI 10.1007/s00605-010-0192-1
Carl-Erik Fröberg, Accurate estimation of the number of binary partitions, Nordisk Tidskr. Informationsbehandling (BIT) 17 (1977), no. 4, 386–391. MR 466010, DOI 10.1007/bf01933448
Kevin G. Hare, Base-$d$ expansions with digits $0$ to $q-1$, Exp. Math. 24 (2015), no. 3, 295–303. MR 3359217, DOI 10.1080/10586458.2014.990119
Matthew J. Hirn, The refinability of step functions, Proc. Amer. Math. Soc. 136 (2008), no. 3, 899–908. MR 2361862, DOI 10.1090/S0002-9939-07-08963-0
H. Hennion, Limit theorems for products of positive random matrices, Ann. Probab. 25 (1997), no. 4, 1545–1587. MR 1487428, DOI 10.1214/aop/1023481103
Raphaël Jungers, The joint spectral radius, Lecture Notes in Control and Information Sciences, vol. 385, Springer-Verlag, Berlin, 2009. Theory and applications. MR 2507938, DOI 10.1007/978-3-540-95980-9
Raphaël M. Jungers, Vladimir Protasov, and Vincent D. Blondel, Efficient algorithms for deciding the type of growth of products of integer matrices, Linear Algebra Appl. 428 (2008), no. 10, 2296–2311. MR 2405246, DOI 10.1016/j.laa.2007.08.001
Daniel E. Gonsor, Subdivision algorithms with nonnegative masks generally converge, Adv. Comput. Math. 1 (1993), no. 2, 215–221. MR 1230258, DOI 10.1007/BF02071386
Nicola Guglielmi and Vladimir Protasov, Exact computation of joint spectral characteristics of linear operators, Found. Comput. Math. 13 (2013), no. 1, 37–97. MR 3009529, DOI 10.1007/s10208-012-9121-0
Donald E. Knuth, An almost linear recurrence, Fibonacci Quart. 4 (1966), 117–128. MR 199168
L. F. Klosinski, G. L. Alexanderson, and A. P. Hillman, The William Lowell Putnam Mathematical Competition, Amer. Math. Monthly 91 (1984), no. 8, 487–495. MR 1540495, DOI 10.2307/2322570
Wayne Lawton, S. L. Lee, and Zuowei Shen, Characterization of compactly supported refinable splines, Adv. Comput. Math. 3 (1995), no. 1-2, 137–145. MR 1314906, DOI 10.1007/BF03028364
Matthieu Latapy, Partitions of an integer into powers, Discrete models: combinatorics, computation, and geometry (Paris, 2001) Discrete Math. Theor. Comput. Sci. Proc., AA, Maison Inform. Math. Discrèt. (MIMD), Paris, 2001, pp. 215–227. MR 1888775
Kurt Mahler, On a special functional equation, J. London Math. Soc. 15 (1940), 115–123. MR 2921, DOI 10.1112/jlms/s1-15.2.115
Avraham A. Melkman, Subdivision schemes with non-negative masks converge always—unless they obviously cannot?, Ann. Numer. Math. 4 (1997), no. 1-4, 451–460. The heritage of P. L. Chebyshev: a Festschrift in honor of the 70th birthday of T. J. Rivlin. MR 1422696
Charles A. Micchelli and Allan Pinkus, Descartes systems from corner cutting, Constr. Approx. 7 (1991), no. 2, 161–194. MR 1101061, DOI 10.1007/BF01888152
Charles A. Micchelli and Hartmut Prautzsch, Uniform refinement of curves, Linear Algebra Appl. 114/115 (1989), 841–870. MR 986909, DOI 10.1016/0024-3795(89)90495-3
G. Molteni, Representation of a 2-power as sum of $k$ 2-powers: the asymptotic behavior, Int. J. Number Theory 8 (2012), no. 8, 1923–1963. MR 2978848, DOI 10.1142/S1793042112501096
I. Ya. Novikov, V. Yu. Protasov, and M. A. Skopina, Wavelet theory, Translations of Mathematical Monographs, vol. 239, American Mathematical Society, Providence, RI, 2011. Translated from the 2005 Russian original by Evgenia Sorokina. MR 2779330, DOI 10.1090/mmono/239
Marian Neamtu, Convergence of subdivision versus solvability of refinement equations, East J. Approx. 5 (1999), no. 2, 183–210. MR 1705396
W. B. Pennington, On Mahler’s partition problem, Ann. of Math. (2) 57 (1953), 531–546. MR 53959, DOI 10.2307/1969735
John L. Pfaltz, Evaluating the binary partition function when $N=2^n$, Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995), 1995, pp. 3–12. MR 1369291
Mark Pollicott, Maximal Lyapunov exponents for random matrix products, Invent. Math. 181 (2010), no. 1, 209–226. MR 2651384, DOI 10.1007/s00222-010-0246-y
V. Yu. Protasov, Asymptotics of the partition function, Mat. Sb. 191 (2000), no. 3, 65–98 (Russian, with Russian summary); English transl., Sb. Math. 191 (2000), no. 3-4, 381–414. MR 1773255, DOI 10.1070/SM2000v191n03ABEH000464
Vladimir Protasov, Refinement equations with nonnegative coefficients, J. Fourier Anal. Appl. 6 (2000), no. 1, 55–78. MR 1756136, DOI 10.1007/BF02510118
V. Yu. Protasov, On the problem of the asymptotics of the partition function, Mat. Zametki 76 (2004), no. 1, 151–156 (Russian); English transl., Math. Notes 76 (2004), no. 1-2, 144–149. MR 2099853, DOI 10.1023/B:MATN.0000036752.47140.98
V. Yu. Protasov, Piecewise-smooth refinable functions, Algebra i Analiz 16 (2004), no. 5, 101–123 (Russian, with Russian summary); English transl., St. Petersburg Math. J. 16 (2005), no. 5, 821–835. MR 2106669, DOI 10.1090/S1061-0022-05-00881-2
V. Yu. Protasov, Spectral decomposition of 2-block Toeplitz matrices and refinement equations, Algebra i Analiz 18 (2006), no. 4, 127–184 (Russian, with Russian summary); English transl., St. Petersburg Math. J. 18 (2007), no. 4, 607–646. MR 2262586, DOI 10.1090/S1061-0022-07-00963-6
V. Yu. Protasov, Asymptotics of products of nonnegative random matrices, Funktsional. Anal. i Prilozhen. 47 (2013), no. 2, 68–79 (Russian, with Russian summary); English transl., Funct. Anal. Appl. 47 (2013), no. 2, 138–147. MR 3113870, DOI 10.1007/s10688-013-0018-8
V. Yu. Protasov and R. M. Jungers, Lower and upper bounds for the largest Lyapunov exponent of matrices, Linear Algebra Appl. 438 (2013), no. 11, 4448–4468. MR 3034543, DOI 10.1016/j.laa.2013.01.027
Bruce Reznick, Some binary partition functions, Analytic number theory (Allerton Park, IL, 1989) Progr. Math., vol. 85, Birkhäuser Boston, Boston, MA, 1990, pp. 451–477. MR 1084197
Gian-Carlo Rota and Gilbert Strang, A note on the joint spectral radius, Nederl. Akad. Wetensch. Proc. Ser. A 63 = Indag. Math. 22 (1960), 379–381. MR 0147922
M. Stern, Ueber eine zahlentheoretische Funktion, J. Reine Angew. Math. 55 (1858), 193–220 (German). MR 1579066, DOI 10.1515/crll.1858.55.193
A. Tanturri, Sul numero delle partizioni d’un numero in potenze di 2, Att. Accad. Naz. Lincey 27 (1918), 399–403.
A. Thomas, Sofic measures and densities of level sets, preprint, arXiv:1310.0993, 2013.
Yang Wang, Two-scale dilation equations and the cascade algorithm, Random Comput. Dynam. 3 (1995), no. 4, 289–307. MR 1362775
Yang Wang, Subdivision schemes and refinement equations with nonnegative masks, J. Approx. Theory 113 (2001), no. 2, 207–220. MR 1876323, DOI 10.1006/jath.2001.3623
Joseph C. Watkins, Limit theorems for products of random matrices: a comparison of two points of view, Random matrices and their applications (Brunswick, Maine, 1984) Contemp. Math., vol. 50, Amer. Math. Soc., Providence, RI, 1986, pp. 5–22. MR 841078, DOI 10.1090/conm/050/841078
Xinlong Zhou, Subdivision schemes with nonnegative masks, Math. Comp. 74 (2005), no. 250, 819–839. MR 2114650, DOI 10.1090/S0025-5718-04-01712-0
Xinlong Zhou, Positivity of refinable functions defined by nonnegative finite masks, Appl. Comput. Harmon. Anal. 27 (2009), no. 2, 133–156. MR 2543190, DOI 10.1016/j.acha.2009.01.001