Arithmetic based fractals associated with Pascal's triangle

Publ. Mat. 49 (2005), 329–349 ARITHMETIC BASED FRACTALS ASSOCIATED WITH PASCAL’S TRIANGLE T. W. Gamelin and Mamikon A. Mnatsakanian Abstract Our goal is to study Pascal-Sierpinski gaskets, which are certain fractal sets defined in terms of divisibility of entries in Pascal’s triangle. The principal tool is a “carry rule” for the addition of the base-qrepresentation of coordinates of points in the unit square. In the case that q=pis prime, we connect the carry rule to the power of pappearing in the prime factorization of binomial coefficients. We use the carry rule to define a family of fractal subsets Bqr of the unit square, and we show that when q=p is prime, Bqr coincides with the Pascal-Sierpinski gasket corresponding to N=pr. We go on to describe Bqr as the limit of an iterated function system of “partial similarities”, and we determine its Hausdorff dimension. We consider also the corresponding fractal sets in higher-dimensional Euclidean space. 1. Introduction Just as the Cantor set is obtained from an interval by excising “middle thirds”, so is the Sierpinski gasket (or Sierpinski triangle) obtained from a triangle by excising “middle triangles”. Starting with a triangle T, we excise the open triangle U1with vertices at the midpoints of the three sides of T. This yields T1=T\U1, which is a union of three congruent triangles each similar to T. Performing the same procedure on each of the three triangles in T1, we excise the union U2of the three middle triangles. This yields T2=T1\U2, which consists now of nine congruent triangles each similar to T. Iterating the procedure, we obtain in the limit the Sierpinski gasket Xas a decreasing limit of the Tn’s as n→ ∞. If φ1,φ2,φ3are the affine maps of Tonto the three triangles in T1, then Tn+1 =∪φj(Tn), and in the limit, X=∪φj(X). This relation expresses the self-similarity of X. 2000 Mathematics Subject Classification. Primary: 39B12. Key words. Sierpinski gasket, Pascal triangle, carry rule, iterated function system, fractal, Hausdorff dimension. 330 T. W. Gamelin, M. A. Mnatsakanian It is well known (cf. [Man]) that the Sierpinski gasket can also be obtained by operations on Pascal’s triangle. We view Pascal’s triangle as a quarter-plane suspended from its vertex and tiled by unit squares, so that each square cell of the tiling contains an entry of Pascal’s triangle. We color black the cells with odd entries, and we color white those with even entries. If we scale the triangular figure consisting of the top 2nrows of Pascal’s triangle to fit a fixed triangle, and we let Enbe the image of the black squares, we see visually and verify easily that the En’s decrease to a Sierpinski gasket. In [H], Holter, Lakhtakia, Varadan, Varadan, and Messier extend this idea by performing the following experiment. For a fixed integer N≥2, they color black the cells of Pascal’s triangle whose labels are not divisible by N, the other cells white, they truncate the triangle, and they look for patterns. They observe that when N=pis prime, the truncated and rescaled sets have a limit set that is self-similar and has Hausdorff dimension (1) βp= 1 + log((p+ 1)/2) log p. They report that when N=pris a power of a prime, “visual inspection alone suffices to show that the resulting gaskets are self-similar”, and they raise the problem of determining their dimensions. For N= 6 they report that “visual inspection extended up to n= 198 rows does not reveal any self-similarity in these gaskets”. (These sets can be viewed on the interactive web site at http://www.its.caltech.edu/ ~mamikon/PasFastC.html.) Our goal is to introduce and investigate a family of “fractal” subsets Bqr of the plane, defined for integers q≥2 and r≥1, which coincide with the Pascal-Sierpinski gaskets of [H] in the case that q=pis prime and N=pr. We refer to Bqr as the (q, r)-basket, since in some sense it is a basket of gaskets. We study the self-similarity properties of Bqr, and we determine its Hausdorff dimension. The paper is organized as follows. In Section 2 we derive the “carry rule”, which gives a condition equivalent to a multinomial coefficient being divisible by a fixed prime power pr. In Section 3 we define for each q≥2 the Sierpinski q-gasket Bq, we show how it is obtained from a triangle by an iterative process of excising subtriangles, and we collect some basic facts for later use. In Section 4 we define for each q≥2 and r≥1 the (q, r)-basket Bqr. The (q, 1)-basket Bq1coincides with the Sierpinski q-gasket Bq, and Bqr ⊂Bq,r+1 for r≥1. Arithmetic Based Fractals 331 The carry rule shows that in the case that q=pis prime, Bqr coincides with the Pascal-Sierpinski gasket treated in [H] for N=pr. In Section 5 we describe in more detail the dynamics of the (q, r)-basket by showing that Bqr can be viewed as a limit of an iterated function system of certain “partial self-similarities”. If r > 1, we show that Bqr is obtained from Bqby plugging scaled copies of lower order gaskets Bqt, 1 ≤t < r, into the triangles forming the complementary components of Bq. In Sections 6 and 7 we show that for fixed q, the (q, r)-baskets have Hausdorff dimension β=βqdetermined by the identity qβ=q(q+ 1)/2, which is equivalent to the formula (1) with p replaced by q. In Section 8 we indicate how the analysis can be extended to the corresponding fractal sets in higher dimensions and higher order multinomial coefficients. This collaboration began in connection with a project for professional development of K-12 mathematics teachers. We hope that various of the ideas that appear here can be reformulated to be useful for professional development. 2. The carry rule We are interested in the prime decompositions of multinomial coefficients. For a given prime number p, we would like to specify the prime power prappearing in the prime decomposition of a multinomial coefficient. We begin with the following. Lemma 2.1. Let pbe a prime number, and let n≥0. Suppose nhas the base-prepresentation n=akpk+ak−1pk−1+···+a1p+a0, where 0≤aj≤p−1for 0≤j≤k. Then the power prof pappearing in the prime decomposition of n!has exponent rgiven by r=1 p−1[n−(ak+ak−1+···+a1+a0)] . Proof: We may assume n≥1. We express n! = n(n−1)(n−2) ... . The factors that are divisible by pare the multiples p, 2p, 3p, . . . , (akpk−1+ ak−1pk−2+···+a1)pof p. Thus the number of factors divisible by pis akpk−1+ak−1pk−2+···+a1. Similarly, the number of factors divisible by p2is akpk−2+ak−1pk−3+···+a2. We count in this fashion, until we reach the number of factors divisible by pk, which is ak. The exponent r 332 T. W. Gamelin, M. A. Mnatsakanian is the sum of these numbers, r= (akpk−1+ak−1pk−2+···+a1) + (akpk−2+ak−1pk−3+···+a2) + ···+ak =ak(pk−1+pk−2+···+ 1) +ak−1(pk−2+pk−3+···+ 1) + ···+a2(p+ 1) + a1. Summing geometric series, we obtain r=akpk+ak−1pk−1+···+a1p−(ak+ak−1+···+a1) p−1. Substituting n−a0for akpk+ak−1pk−1+···+a1p, we obtain the desired identity. Lemma 2.2. Let pbe a prime number, and let m1,...,m`≥0,N= m1+···+m`. Suppose that the mi’s and Nhave base-prepresentations mi=Pjaij pj,1≤i≤`, and N=Pjbjpj. Then the power pr of pappearing in the prime decomposition of the multinomial coefficient (2) N! m1!...m`! has exponent rgiven by (3) r=1 p−1 X i,j aij −X j bj . Proof: Apply the preceding lemma to each of the factorials, and use N=m1+···+m`. Now we consider the addition algorithm for adding numbers of the form mi=Pjaij pjin base-prepresentation, by adding successively digits in each place and carrying if the sum is ≥p. We count the carries according to multiplicity. The number of carries in the jth place is the integer κj≥0 defined inductively, starting with κ−1= 0, by (4) a1j+a2j+···+a`j +κj−1=bj+pκj, j ≥0, where 0 ≤bj≤p−1. In the case that `= 2, we are adding only two mi’s, and there is never more than one carry, that is, each κjis either 0 or 1. Arithmetic Based Fractals 333 Theorem 2.3 (Carry Rule).Let pbe a prime number, and let m1,...,m`≥0,N=m1+···+m`. Suppose that the mi’s and Nhave base-prepresentations mi=Pjaij pj,1≤i≤`, and N=Pjbjpj. Then the exponent rin the power prof pappearing in the prime decomposition of the multinomial coefficient (2) is equal to the number of carries in adding the base-prepresentations of mi’s. Proof: From (4) we have X i,j aij −X j bj=Xpκj−Xκj−1= (p−1) Xκj. Thus from (3) we obtain r=Pκj, as required. Corollary 2.4. Let pbe a prime number, and let m1,...,m`≥0, N=m1+···+m`. Let the mi’s have base-prepresentations mi=Pjaij pj as above. Then pdoes not divide the multinomial coefficient (2) if and only if there are no carries in adding the base-prepresentations of the mi’s, that is, if and only if a1j+a2j+···+a`j < p for j≥0. 3. The Sierpinski q-gasket We fix q≥2. For n≥0, let Gnbe the grid of subsquares of the unit square of sidelength 1/qn. We label the squares according to their lower left corners (x, y), and we represent xand yin their base-qexpansions x= 0.xnxn−1...x1=1 qn(x1+x2q+···+xnqn−1), y= 0.ynyn−1...y1=1 qn(y1+y2q+···+ynqn−1), where 0 ≤xj, yj≤q−1. Let Enbe the squares in Gnwhose labels (x, y) satisfy (5) xj+yj≤q−1,1≤j≤n. We refer to the squares in Enas the “black squares”, and to the other squares in Gnas the “white squares”. Let Enbe the union of the (closed) black squares in Gn, En=∪{S:S∈ En}. 334 T. W. Gamelin, M. A. Mnatsakanian 1.0 0.1 0.0 1.00 0.11 0.10 0.01 0.00 0.00.11.00.00 0.010.100.11 1.00 Figure 1. Three stages E1,E2,E3in construction of Sierpinski gasket. Now consider the corresponding grid Gn+1 and black squares En+1. The union of the squares in Gn+1 with labels (0.xn+1xn...x2x1, 0.yn+1yn...y2y1), taken over 1 ≤x1, y1≤q−1, is the square in Gn with label (0.xn+1xn...x2,0.yn+1yn. . . y2). From (5) we see that if a square in Gnis white, then each of the constituent squares in Gn+1 is also white. Thus {En}is a decreasing sequence of nonempty compact sets. Definition 3.1. The Sierpinski q-gasket Bqis the decreasing limit of the En’s, Bq= lim n→∞ En=∩∞ n=0En. Evidently Bqis a nonempty compact set. When q= 2, we obtain the usual Sierpinski gasket B2. Figure 1 indicates the first three stages E1,E2,E3in the construction of B2. Figure 2 depicts two stages in the construction of B3. In this figure, the shaded squares (both light and dark) represent E1, and the darkly shaded squares represent E2. Arithmetic Based Fractals 335 1.00 0.22 0.21 0.20 0.12 0.11 0.10 0.02 0.01 0.00 0.00 0.01 0.02 0.10 0.11 0.12 0.20 0.21 0.22 1.00 Figure 2. Two stages E1,E2in construction of B3. We refer to a square in Gnas diagonal if its center lies on the diagonal line {x+y= 1}. Otherwise the square is subdiagonal or superdiagonal depending on whether it lies below-left or above-right of the diagonal squares. Note that the diagonal and subdiagonal squares in G1are black (the squares in E1), and the superdiagonal squares in G1are white. For each square S∈ E1, we define an affine map φSof the unit square onto S by scaling by 1/q and translating. If the square Shas label (0.a, 0.b), where 0 ≤a, b ≤q−1, then φS(x, y) = a+x q,b+y q=1 q(a+x, b +y). Note that φSmaps the square Uin Gnwith label (0.xn...x1,0.yn...y1) onto the square Vin Gn+1 with label (0.axn...x1,0.byn...y1). If Uis black, then xj+yj≤q−1 for 1 ≤j≤n, so since a+b≤q−1, the square Vis also black. Further, if Vis a black square in Gn+1, say with label (0.xn+1xn...x1,0.yn+1yn. . . y1), then V=φS(U) for the black square Uwith label (0.xn...x1,0.yn...y1) and Swith label (0.xn+1,0.yn+1). Thus En+1 =∪{φS(En) : S∈ E1}, 336 T. W. Gamelin, M. A. Mnatsakanian and in the limit Bq=∪{φS(Bq) : S∈ E1}. The maps {φS}S∈E1form an iterated function system (see [B], [Men]). The limit Bqis the unique fixed point of the set-mapping E7→ ∪φS(E), which is a contraction of the space of nonempty compact subsets of the unit square, endowed with the usual Hausdorff metric. The Sierpinski q-gasket can also be obtained through an iterative process of excising triangles. We start with the triangle T={(x, y) : x≥0, y ≥0, x +y≤1}. Let W={(x, y) : x < 1, y < 1, x +y > 1}, which is an open triangle disjoint from T. Lemma 3.2. The triangle Tcontains Bq. The boundary ∂T of Tis contained in Bq. The triangle Wis disjoint from Bq. Proof: The squares in Enhave labels in T, so points of Enhave distance at most 1/2qnfrom T. Passing to the limit, we obtain Bq⊂T, and Bqis disjoint from W. The squares in Gnbordering on the x-axis or the y-axis have labels with one coordinate equal to 0, hence belong to En. Thus the unit intervals on the two coordinate axes are contained in each En hence in Bq. Also the diagonal squares in Gnhave labels (x, y) satisfying xj+yj=q−1, for all j, so the diagonal squares in Gnare all black. Thus the diagonal edge of Tis contained in each En, hence in Bq. We consider the q(q−1)/2 open triangles φS(W), where Sis subdiagonal. We refer to these as the first-generation triangles. They play the role of the first middle triangle in the construction of the Sierpinski triangle. Let U1be the union of the first-generation triangles, and set T1=T\U1. Since Wis disjoint from Bq, each φS(W) is disjoint from Bq, U1is disjoint from Bq, and Bq⊂T1. In each black square S∈ E1we define q(q+1)/2 second-generation triangles to be the triangles in φS(U1). Thus there are [q(q+1)/2]q(q−1)/2 second-generation triangles. Let U2be the union of the second-generation triangles, and let T2=T1\U2. Again U2is disjoint from Bq, and Bq⊂T2. Proceeding by induction, we define the nth-generation triangles to be the images of the (n−1)th generation triangles under the maps φSfor S∈ E1. There are [q(q+ 1)/2]n−1q(q−1)/2 triangles in the nth-generation. The union Unof the nth-generation triangles is disjoint from Bq, so that Tn=Tn−1\Uncontains Bq. Passing to the limit, we have Bq⊂lim Tn=T\(∪∞ n=1Un). On the other hand, Tnis contained in the black squares in Gn−1, so that lim Tn⊂Bq. We have established the following. Arithmetic Based Fractals 337 Theorem 3.3. The Sierpinski q-gasket Bqis obtained from the triangle Tby excising the nth-generation triangles, 1≤n < ∞, Bq= lim Tn=T\(∪∞ n=1Un). Now we focus on the case when q=pis prime. We consider the quarter-plane tiled by cells that are unit squares containing the entries of Pascal’s triangle, and we rotate the quarter-plane so that it fills the first quadrant. With this representation, the entry in the cell whose lower left corner has coordinates (k, m) is the binomial coefficient k+m k, 0≤k, m < ∞. We color the cell white if k+m kis divisible by p, and we color the cell black if k+m kis not divisible by p. Fix n≥0, and consider the square [0, pn]×[0, pn]. The scaling by the factor 1/pnmaps this square onto the unit square, and it maps the cells corresponding to the binomial coefficients onto squares in Gn. Theorem 3.4. Let pbe a prime number. Fix n≥1, and 0≤k, m < pn. The binomial coefficient k+m kis not divisible by pif and only if the corresponding square in Gnbelongs to En. In other words, the cell in Pascal’s triangle corresponding to k+m kis black if and only if the corresponding square in Gnis black. Proof: Let k=an−1pn−1+an−2pn−2+···+a1p+a0and m=bn−1pn−1+ bn−2pn−2+···+b1p+b0be the base-prepresentations of kand m. By the carry rule, k+m mis not divisible by pif and only if there are no carries when we add these representations. This occurs if and only if aj+bj≤q−1 for 0 ≤j≤n−1, and this occurs if and only if the square with label (0.an−1...a0,0.bn−1. . . b0) = 1 pn(k, m) belongs to En. 4. The (q, r)-basket Again we fix q≥2, and we let r≥1. Let Ern be the set of squares in Gnwith labels (x, y) such that when we add the base-qrepresentations of qn−1xand qn−1y, there are fewer than rcarries. In other words, the squares in Ern are the squares with labels (0.xnxn−1...x1,0.ynyn−1...y1) such that when we add x1+x2q+···+xnqn−1and y1+y2q+···+ynqn−1, there are fewer than rcarries. Occasionally we refer to the squares in Ern as the “black squares”, and we refer to the other squares in Gnas the “white squares”. Again, if a square in Gnis white, then the squares in Gn+1 it contains are white. 344 T. W. Gamelin, M. A. Mnatsakanian Now consider q(q+ 1) 2−n Sr(n) = r−1 X t=1 qt(q−1) 2q(q+ 1) 2−n+t Rr−t(n−t). By our induction hypothesis, the right-hand side is a polynomial in nof order r−2. Only the summand t= 1 contributes to the nr−2term, and we find using (8) with k=r−1 that (13) q(q+ 1) 2−n Sr(n) = q(q−1) 2q(q+ 1) 2−1 ar−1nr−2+O(nr−3). Substituting n−1 for nin (13), and dividing by q(q+1)/2, we also have (14) q(q+ 1) 2−n Sr(n−1)= q(q−1) 2q(q+ 1) 2−2 ar−1nr−2 +O(nr−3). Multiplying (12) by [q(q+ 1)/2]−n, using (6), (8), (13), and (14), and doing some algebra, we obtain the recursion relation Pr(n) = Pr(n−1) + (q−1)2 (q+ 1)2ar−1nr−2+O(nr−3). Thus Pr(n) is a polynomial in nof degree r−1, unique up to an additive constant, and in fact we obtain (essentially by integrating) that Pr(n) = 1 r−1 (q−1)2 (q+ 1)2ar−1nr−1+O(nr−2). Thus ar=1 r−1 (q−1)2 (q+ 1)2ar−1. Since a1= 1, this recursion relation has a unique solution, which is given by the leading coefficient in (7). 7. Hausdorff dimension Let Ebe a subset of Rd, and let s > 0. For each δ > 0, let Λ(δ) s(E) denote the infimum of the sums Prs j, taken over all covers of Eby balls with radii rjsatisfying rj≤δ. As δdecreases, the infimum is taken over fewer covers, and Λ(δ) s(E) increases. Its limit Λs(E) = limδ→0Λ(δ) s(E) is the s-dimensional Hausdorff measure of E. The Hausdorff dimension of Eis the infimum of ssuch that Λs(E) = 0. For background information on Hausdorff measures, see [R]. Theorem 7.1. Fix q≥2and r≥1. If qs> q(q+1)/2, then Λs(Bqr )=0. Arithmetic Based Fractals 345 Proof: Let δ= 1/qn. Each square in Ern is contained in a disk of radius δ. Using Theorem 6.1, we obtain Λ(δ) s(Bqr)≤Rr(n)1 qns ∼q(q+ 1) 2qsn nr−1. Since this tends to 0 as n→ ∞, Λ(δ) s(Bqr)→0 as δ→0, and Λs(Bqr) = 0. Fix q≥2 and associated grids Gn. For Ea subset of the unit square [0,1]2in R2, define λ(δ) s(E) = inf X(sidelength Gj)s, where the infimum is taken over all finite covers of Eby sets Gj∈ ∪Gn. It is easy to see that there are constants c, C > 0 such that cλ(δ) s(E)≤Λ(δ) s(E)≤Cλ(δ) s(E), for all compact subsets Eof the unit square (though not for arbitrary subsets). We aim to compute λ(δ) s(Bqr) explicitly. First we prove two lemmas. Lemma 7.2. If Uis a (closed) square in Ern, then Bqr contains interior points of U. Proof: If U∈Ern has label (0.an...a2a1,0.bn. . . b2b1), then (0.an. . . a2a1 10, 0.bn. . . b2b101) is an interior point of U. From the definition of Ern, we see that it labels a square in Erk for all k≥n+ 2, hence it belongs to Bqr. Lemma 7.3. Let U∈ Er,n−1. Then either all q2subsquares of Uin Gn are contained in Ern, or exactly q(q+ 1)/2of the subsquares of Uin Gn are contained in Ern. Proof: Let Uhave label (0.an. . . a2,0.bn. . . b2). Subsquares U0of Uthen have labels of the form (0.an...a2a1,0.bn...b2b1). Since U∈ Er,n−1, there are at most r−1 carries when we add the coordinates of U. Define k, 0 ≤k≤q−1, so that k= 1 if a2+b26=q−1, and otherwise kis the largest integer such that aj+bj=q−1 for 2 ≤j≤k. For a subsquare U0with label as above, there are no new carries if a1+b1≤q−1, while there are kmore carries for U0if a1+b1≥q. If now the number of carries for Uis < r −k, then all subsquares U0have < r carries, and all q2subsquares belong to Ern. If on the other hand the number of carries for Uis ≥r−k, then the subsquares U0with < r carries are precisely the subsquares for which a1+b1≤q−1, and there are exactly q(q+1)/2 such subsquares, namely the diagonal and subdiagonal subsquares. 346 T. W. Gamelin, M. A. Mnatsakanian Theorem 7.4. Fix q≥2and r≥1. Define βby qβ=q(q+ 1)/2. Let δ= 1/qn. Then the infimum defining λ(δ) s(E)is attained for the cover Ern of Bqr by black squares in Gn. Thus λ(δ) s(Bqr) = Pr(n), δ = 1/qn, n ≥r, where Pr(n)is the polynomial of Theorem 6.1. In particular, λ(δ) β(Bq) = 1,0< δ < 1. If r≥2, then as δ→0, λ(δ) β(Bqr)∼log 1 δr−1 . Proof: Let {G1,...,G`}be a finite cover of Bqr by (closed) squares in ∪∞ k=nGk, so the sidelength of each Gjis ≤1/qn. By discarding Gj’s that are contained in a larger Gk, we can assume that no Gjis a subsquare of another. Then the interior of each Giis disjoint from the other Gj’s. Suppose that Giis a white square, that is, Gidoes not belong to one of the Erk’s. If p∈Gi∩Bqr, then plies on a boundary segment of Gi. Let 1/qmbe the minimal sidelength of the Gj’s, and let Ube a black square of sidelength 1/qmthat contains p. By Lemma 7.2, Ucontains points of Bqr in its interior, and any such point belongs to one of the Gj’s, hence Umust be contained in one of the Gj’s, and consequently pis in one of the Gj’s other than Gi. Thus the Gj’s, for j6=ialready cover Bqr. By discarding one by one the Gi’s that are white, we can then assume that each Giis black, that is, each Gibelongs to Erk for some k,n≤k≤m. Let Gibe a square in the cover of minimal sidelength 1/qm. Suppose Giis a subsquare of V∈ Gm−1. Then Vis black, that is, V∈ Er,m−1, and by Lemma 7.3, at least q(q+ 1)/2 subsquares of Vare black. Since Gihas minimal sidelength, and since the Gj’s are disjoint, each of these black subsquares of Vmust be among the Gj’s. If we replace these squares by the parent square V, and we note that X Gj⊂U (sidelength Gj)β≥q(q+ 1) 21 qmβ =1 qm−1β =(sidelength U)β, we obtain a cover by fewer squares for which the sum defining the minimum is at least as small. By successively replacing smaller squares by their parent squares, we eventually arrive at the situation where all the squares among the Gj’s are in Ern. Since no subset of Ern covers Arithmetic Based Fractals 347 Brq, we conclude that the infimum defining λ(δ) β(Bqr) is attained for the cover Ern. The remaining assertions of the theorem follow from the definitions of Rr(n) and Pr(n) and Theorem 6.1. Theorem 7.5. Fix q≥2and r≥1. Define βby qβ=q(q+ 1)/2. The Sierpinski q-gasket Bqhas finite positive β-dimensional Hausdorff measure. For r≥2, the (q, r)-basket Bqr has infinite though σ-finite β-dimensional Hausdorff measure. Proof: The first statement follows from Theorem 7.4 and the comparability of λ(δ) sand Λ(δ) s. For the second statement, suppose first that r= 2. By Theorem 5.6, Bq2is obtained from Bqby plugging scaled copies of Bq into the complementary triangles of Bq. In this construction, there are q(q−1)/2 triangles with scaling factor 1/q, and at the nth stage there are [q(q+ 1)/2]n−1q(q−1)/2 triangles with scaling factor 1/qn. Thus the β-dimensional Hausdorff measure of the copy of Bqplugged in to the triangles at the nth stage is ∼1/qnβ, and Λβ(Bq2)≥c ∞ X n=1 q(q+ 1) 2nq(q−1) 2 1 qnβ =cq(q−1) 2X1 = +∞. Thus Bq2has infinite though σ-finite β-dimensional Hausdorff measure. If now r > 2, Bqr is the union of Bqand a countable number of scaled copies of Bqt for t < r. By induction on r, we see that Bqr has infinite though σ-finite β-dimensional Hausdorff measure. Note that the fact that Bqr has σ-finite β-dimensional Hausdorff measure already implies that Λs(Bqr) = 0 for s > β. This provides another route to Theorem 7.1, which depends only on the (easy) case r= 1 of Theorem 6.1. In any event, we have the following corollary to Theorem 7.5. Corollary 7.6. Fix q≥2and r≥1, and define βby qβ=q(q+ 1)/2. Then the (q, r)-basket Bqr has Hausdorff dimension β. 8. Baskets in higher dimensions We can define baskets in d-dimensional Euclidean space for any d≥2 in the same way as in the two-dimensional case. Carrying over the same notation, we let Gnbe the grid of subcubes of the unit cube [0,1]dof sidelength 1/qn, and we label a cube in Gnby the d-tuple of coordinates of its lower left corner. We express the coordinates in base-q, and we define Ern to be the subset of Gnof cubes with the property that when 348 T. W. Gamelin, M. A. Mnatsakanian we add the coordinates of the label, there are fewer than rcarries. Again we define Ern be the union of the (closed) cubes in Ern. The Ern’s form a decreasing sequence of nonempty compact sets. We define their limit to be the (q, r)-basket in Rd, and we denote it by Bqr. If r= 1, we obtain the analogue Bq=Bq1in Rdof the Sierpinski q-gasket. It is the limit of the iterated function system consisting of functions of the form φk(x) = 1 q(k+x),x∈[0,1]d, where k= (k1,...,kd), and the kj’s are nonnegative integers satisfying k1+···+kd≤q−1. Each k/q is the label of a diagonal or subdiagonal cube in G1. In this case there are qd−1(q+ 1)/2 cubes in E1, hence [qd−1(q+ 1)/2]ncubes in En. Consequently X{(sidelength U)β:U∈ En}=qd−1(q+ 1) 2n ·1 qnβ =qd−1(q+ 1) 2q−βn . This has a finite nonzero limit as n→ ∞ when qβ=qd−1(q+ 1) 2, that is, for β=βqdefined by βq=d−1 + log((q+ 1)/2) log q. It is straightforward to verify that βqis the Hausdorff dimension of Bq. Again Bqhas finite positive βq-dimensional Hausdorff measure, and for r≥2, Bqr has infinite though σ-finite βq-dimensional Hausdorff measure. In the case that q=pris a prime power, there is a connection between the (q, r)-basket and the d-dimensional analogue of Pascal’s triangle consisting of multinomial coefficients. The connection can be made through the following theorem, which is a direct consequence of the carry rule. Theorem 8.1. Let pbe a prime number, and let r≥1. For n≥1 and 0≤k1,...,kd< pn, the multinomial coefficient (k1+···kd)! k1!. . . kd! is not divisible by prif and only if the cube in Gnwith label q−n(k1,...,kd) belongs to Ern. Arithmetic Based Fractals 349 References [B] M. Barnsley,“Fractals everywhere”, Academic Press, Inc., Boston, MA, 1988. [C] L. Carleson,“Selected problems on exceptional sets”, Van Nostrand Mathematical Studies 13, D. Van Nostrand Co., Inc., Princeton, N.J.-Toronto, Ont.-London, 1967. [F] K. J. Falconer,“The geometry of fractal sets”, Cambridge Tracts in Mathematics 85, Cambridge University Press, Cambridge, 1986. [H] N. S. Holter, A. Lakhtakia, V. K. Varadan, V. V. Varadan and R. Messier, On a new class of planar fractals: the Pascal-Sierpi´nski gaskets, J. Phys. A 19(9) (1986), 1753–1759. [Man] B. B. Mandelbrot,“The fractal geometry of nature”, Schriftenreihe f¨ur den Referenten. [Series for the Referee], W. H. Freeman and Co., San Francisco, Calif., 1982. [Mat] P. Mattila,“Geometry of sets and measures in Euclidean spaces. Fractals and rectifiability”, Cambridge Studies in Advanced Mathematics 44, Cambridge University Press, Cambridge, 1995. [Men] F. Mendivil, Fractals, graphs, and fields, Amer. Math. Monthly 110(6) (2003), 503–515. [R] C. A. Rogers,“Hausdorff measures”, Cambridge University Press, London-New York, 1970. T. W. Gamelin: Department of Mathematics UCLA Los Angeles, CA 90095-1555 USA E-mail address:[email protected] Mamikon A. Mnatsakanian: Project mathematics! Caltech Pasadena, CA 91106 USA E-mail address:[email protected] Primera versi´o rebuda el 13 de setembre de 2004, darrera versi´o rebuda el 17 de gener de 2005.