Date: Apr 22, 1995 2:57 AM Author: Ted Alper Subject: Re: where's the math? Susan,

Of course, just because I don't see the connection, doesn't mean

there isn't one. I should have phrased my post more temperately.

(On the other hand, the existence of a construction on Pascal's

triangle that has something in common with a construction on the real

line that leads to the Cantor set, doesn't mean that Pascal's triangle

is "connected" to the Cantor set, only that both admit a certain type

of construction.)

"Dr. Susan Addington" <addington@gallium.csusb.edu> writes:

>Here's a homework problem for you:

>

>Write out a large section of Pascal's triangle.

>Pick a prime (say, 7).

>Highlight all the entries of Pascal's triangle that are

>divisible by 7.

>Find a pattern.

>Explain why it happens.

>What would you get if you used a really big section of P's triangle,

>say, 100 rows or more?

>What would happen if you used *all* of Pascal's triangle?

I hope it's ok to do my homework on the net. (And I'd as soon skip to

the general pattern. I make no claims for efficiency of my proof -- I

just put the baby to bed and I sort of want to join him -- but I'll

edit out any major false starts):

Actually, rather than do it in complete generality, let me leave

7 in. We can go back later and replace it by an arbitrary prime.

using nCm for n!/(m!(n-m)!) and

[x] for greatest integer less than or equal to x.

the number of powers of 7 dividing n! is

[n/7] + [n/7^2] + [n/7^3] + ....

similarly, the number of powers of 7 dividing m! is

[m/7] + [m/7^2] + [m/7^3] + ...

and, for (n-m), it's

[(n-m)/7] + [(n-m)/7^2] + [(n-m)/7^3] + ...

Now, since [a] + [b] is always less than or equal to [a+b],

[n/7^k] is greater than or equal to [m/7^k] + [(n-m)/7^k]

for all k. If equality holds for all k, then nCm will not be

divisible by 7. So the question becomes: For what (n,m) is there

a k for which

[n/7^k] > [m/7^k] + [(n-m)/7^k] ?

OH! I think I see where this is going. The digits of

an integer n in base 7 are also given by these terms.

I guess the units digit is n - 7*[n/7], the "7"s digit is

given by [n/7] - 7*[n/7^2] and so forth. If for k=1,...,j

we have [n/7^k] = [m/7^k] + [(n-m)/7^k], then

[n/7^(k-1)] - 7*[n/7^k]

will equal

[m/7^(k-1)] - 7*[m/7^k] + [(n-m)/7^(k-1)] - 7*[(n-m)/7^k]

for k=1...j. That is, the base 7

representation of n,m, and n-m will be such that the sum

n = m + (n-m) adds without any "carries" for the smallest

j digits. (I guess another way to say it is that the smallest j

digits of m will be less than or equal to the smallest j digits of n.)

However, for the first value of k (if there is one) for which

[n/7^k] > [m/7^k] + [(n-m)/7^k]

this will fail!

[n/7^(k-1)] - 7*[n/7^k]

will be less than

[m/7^(k-1)] - 7*[m/7^k] + [(n-m)/7^(k-1)] - 7*[(n-m)/7^k],

so there will have had to be a "carry".

So, my solution is that nCm is divisible by 7 precisely when the base

7 representation of m has at least one digit larger than the

corresponding digit in the base 7 representation of n. Equivalently,

nCm will NOT be divisible by 7 if every digit of the base 7 rep. of n

is at least as big as the corresponding digit in the base 7 rep. of m.

OK. I see why I have to use a prime for 7 (the very first step,

counting powers of 7 that divide n! relies on it).

It's probably easier to generate the pairs (n,m) for which nCm

is NOT divisible by 7... That is, write the base 7 expansion of n,

then look at all the numbers which can be written using only the same

or smaller digit in each corresponding location.

I suppose one can also start by fixing an m and then see which numbers

can be written using only the same or LARGER digit in each

corresponding location (including extra digits in places larger than

those that occur in m). Obviously, if a given nCm is not divisible by 7,

then replacing n with n + any multiple of any power of 7 larger than m

will still yield a term not divisible by 7.

For values of n of the form 7^k - 1, nCm will not be divisible by 7 for

any m. For values of n of the form 7^k, nCm will be divisible by 7

for all m except m=0 and m=n. For most others, the values for which

nCm is divisible by 7 will occur in big clumps, since if one

digit in m is bigger than the corresponding digit, all the other digits

can be anything at all (this is a bit imprecise, as how much of a "clump"

it is will depend on which place the larger digit is in -- if it's the unit

digit, there's no clumping at all -- that is, for n = 7^k + 5,

nCm will be divisible by 7 only when m is congruent to 6 mod 7. But for

n=7^100 + 5*7^3, say any m with a 6 in the 7^3 place will work, no matter

what the other digits are -- so in this case, you can have up to

7^3 consecutive values of m for which nCm is divisible by 7).

The values for which nCm is NOT divisible by 7 will occur in smaller

clumps, since they must satisfy a condition on every digit (though

again this is imprecise: if n=k*7^6 + 7^5 - 1, than values of m for

which nCm is not divisible by 7 will occur in clumps of size 7^5).

I apologize for the imprecision of these last two paragraphs --

but as a first statement of the clumpiness, I hope it's reasonably clear.

Obviously, there's at least some analogy between these numbers and the

Cantor set construction, as we're avoiding specific digits in specific

places (One characterization of the Cantor set is all numbers between

0 and 1 whose trinary expansion contains no "1"s.). These numbers

(n,m) are only integers, with finitely many places in their base 7

expansion -- but perhaps the comparison is to the finite steps in the

Cantor-set construction. Then, too, they aren't quite as disconnected

(this is the clumpiness issue alluded to above) -- though if one tried

to push this off into the 7-adics, say (in what sense? look at pairs

of 7-adic integers (n,m) for which every digit of m was less than or

equal to the corresponding digit of m?), it looks a lot more similar.

In particular, for most (7-adic) values of n, the set of m that work

will be closed and totally disconnected and the set of points (n,m) in

the (7-adic) plane that work will be closed and totally disconnected.

This is a little different than what you see on Pascal's triangle,

though, since points are close in the p-adics precieely when their

difference is divisible by ENORMOUS powers of 7.

Ted Alper

alper@epgy.stanford.edu