Various neat stuff

[sniffnoy]

EDIT the day after: Made a trivial generalization, and rewrote a table to be clearer. Didn't change anything significant.

1 - Yay for p³

I figured out p³.[0] It was actually pretty nice. Then I tried to figure out just how badly p⁴ fails, but that proved a bit too hairy.

2 - Boo for hidden regularity

Thinking about that problem led me to thinking about another one. Recall my "research lab" from 3 years ago (not really research, I'm well aware). The main problem - well, rather, the only problem we weren't effectively given the answer to - was to find the minimal period of (x choose k) (mod m). By CRT this reduces to the case m a prime power, which we'll call pⁿ. (We'll require n≥1). In this case we get that the minimal period is itself a power of p, namely, p^n+h, where h=⌊log_pk⌋.

Now say that instead of (x choose k) (mod p^m), we take (p^sx choose k) (mod pⁿ). (By CRT and some other easy stuff the general case of (rx choose k) (mod m) reduces to this.) That is to say, say instead of looking at all the values of (x choose k) (mod pⁿ), we only look at the ones where x is a multiple of a given prime power, a given divisor of the minimal period.

Now certainly this will cause the minimal period to drop by a factor of at least p^s. But it's not obvious that it will cause it to drop by a factor of exactly p^s; there could be some extra, hidden regularity within the multiples of p that cause it to drop even further. What originally got me thinking about this problem in general was noticing that the p, p², p³ series of problems implied that in the special cases p^s|k, n=1,2, or 3, (well, for n=3 you need some extra condition - see footnote 0), you did in fact get a drop of a factor of exactly p^s, since this subsequence was the same as another sequence with minimal period smaller by a factor of exactly p^s.

So does this always occur? Well, after spending some time reconstructing it, I tried to take my original proof of the minimal period and adapt it to this case. Only I hit a few snags. Examining them, I found a counterexample:

p=2, k=3, n=3, s=1

x (mod 16)           0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
(x choose 3) (mod 8) 0 0 0 1 4 2 4 3 0 4  0  5  4  6  4  7
requiring 2|x        0   0   4   4   0    0     4     4

Looking at the multiples of 2, we get 0,0,4,4,0,0,4,4. That's not period 8, that's period 4.

I wrote down a big "Conjecture: FALSE!" on that sheet of paper. So things aren't as nice and irregular as I initially expected.

Now I need to figure out how to go about salvaging this...

3. I could swear there was a third thing, but can't remember it.

4. This doesn't really fit, but despite explicitly saying it was simple, my minicourse today on max-flow/min-cut got all of one person, Erick, so I didn't actually do it. It may be because the students are so busy now. Perhaps I should try again some other time. Also, there was a sparrow in Stone B50, but after opening the back door, it eventually figured out the way out. (Man, birds are dumb.)

-Harry

[0]For all the non-PROMYS people: Here's a series of problems that appear on the first-year problem sets. p prime, a,b≥0 integers. (Well, since (x choose k) mod m is periodic, I suppose you don't technically need a≥0. But it'll make things easier to assume it.)
Easy problem - (pa choose pb) ≡ (a choose b) (mod p)
Harder problem - (pa choose pb) ≡ (a choose b) (mod p²)
Problem that has stumped many - (pa choose pb) ≡ (a choose b) (mod p³)
(The last one is actually not quite always true, you may notice. Salvage it.)
While it fails slightly for p³, it apparently fails badly for p⁴; as I said above, I attempted to determine just how badly, but eventually decided it wasn't worth it. Perhaps I'll get back to that some other time.

Comments

[sniffnoy.livejournal.com]

No, I didn't use that at all. I suppose the ordinary proof for mod p is essentially a GF proof, but I didn't use that for p² or p³. I know of at least one first-year reading this so if we want to discuss solutions we should probably do so elsewhere...