# Periodicity of $a_n={n \choose z}\ mod \ y$?

If I have a integer sequence defined as $a_n={n \choose z}\ mod \ y$ for $n,\ x, \ y \in \mathbb Z$, I have found that it is periodic with length: $y\prod_{k=1}^z gcd(e^{\Lambda(k)},y)$, where $\Lambda(k)$ is the von Mangoldt function. (I have not proven this yet, but it seems related to Lucas's and Kummer's theorems.)

Then, if I have a function $f(x,y,z)$ that denotes the frequency of an integer $x$ in one period length of $a_n={n \choose z}\ mod \ y$, it appears that $f(0,2,z)=$ A073138 in OEIS and $f(0,y,2)=$ A034444 in OEIS.

I have this Mathematica code which I have been using to observe the patterns of this function:

f[x_, y_, z_] := Count[Table[Mod[Binomial[n, z], y], {n, 1, y*Product[GCD[E^MangoldtLambda[k], y], {k, 1, z}]}], x]

In addition, $\ f(0,p,z)$ where p is prime seems to have some interesting properties. $\ f(0,11,z)$ demonstrates an interesting repetition:

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 21, 31, 41, 51, 61, 71, 81, 91, 101, 111, 22, 31, 40, 49, 58, 67, 76, 85, 94, 103, 112, 33, 41, 49, 57, 65, 73, 81, 89, 97, 105, 113, 44, 51, 58, 65, 72, 79, 86, 93, 100, . . .}

Here's an image of the above.

My number theory knowledge is not sufficient to get much further with this problem, and I am currently uncertain how to proceed. Why is this pattern occurring? Can it be proven that this is true? Most importantly to me, how can I express $f(x,y,z)$ in a mathematical way? I have found some papers that talk about the periodicity of $a_n={n \choose z}\ mod \ y$ (like this one, for example), but they are beyond my current understanding. Any help would be appreciated! (This is also my first post, so sorry for any formatting errors.)

• Also posted on MO, mathoverflow.net/questions/291832/… – Joseph Quinsey Feb 1 '18 at 19:17
• Use \mod n to generate $\mod n$ for all $n$. Or, with parenthesis, since the word starts with $p$, then just add a $p$, i.e. \pmod n $\longrightarrow$ $\pmod n$. The same applies if you want to find the greatest comin divisor, such that \gcd(a, b) $\longrightarrow$ $\gcd(a, b)$ for all $a$ and $b$. – Feeds Feb 4 '18 at 6:52

OK, so, let's take this a bit at a time.

For $k>0$, the minimal period of the sequence $\binom{n}{k}$ modulo $m$ (where $n$ is what varies) is, as stated in the linked paper, equal to $$m\prod_{\substack{p|m \\ p\ \textrm{prime}}} p^{\lfloor \log_p k \rfloor}.$$

(Of course, rather than saying $p^{\lfloor \log_p k\rfloor}$, one could instead just say "the largest power of $p$ which is at most $k$", but there's no preexisting notation for that.)

The formula that you've given is, IMO, a somewhat more convoluted way of expressing this, but is ultimately equivalent. I'll leave it to you to check this, unless you really want a proof.

As for proving that this is the correct minimal period, it suffices, by the Chinese remainder theorem, to check it when $m$ is a prime power, since the period for a general $m$ will be the LCM of the periods for its prime power factors (and in this case the periods for those prime power factors will be relatively prime, so in fact it will be their product). So, reducing to the case of a prime power modulus, let's say $m=p^a$, $a\ge 1$. Then the formula we want to prove is that the minimal period is equal to $p^{a+\lfloor\log_p k\rfloor}$. (Where again I'm using the floor thing because that's what we have preexisting notation for, not because it's the best way of representing the concept!)

So, there are two things to check here: That this is indeed a period, and that it's minimal. Both can be done via Vandermonde's indentity and Kummer's theorem. Let's do the former first. Let's let $b=\lfloor \log_p k \rfloor$, so $p^b$ is the largest power of $p$ that's at most $k$, so the number we're claiming is the minimal period is $p^{a+b}$.

To verify that this is a period, take $\binom{n+p^{a+b}}{k}$ and expand it out via Vandermonde's identity; it's equal to $\sum_{i=0}^k\binom{p^{a+b}}{i}\binom{n}{k-i}$. The $i=0$ term is just $\binom{n}{k}$; we want to show that the other terms, with $i>1$, vanish modulo $p^a$. This is where Kummer's theorem comes in. Kummer's theorem tells us (assuming $i\le p^{a+b}$, which is true, since $i\le k<p^{b+1}\le p^{a+b}$) that $v_p(\binom{p^{a+b}}{i})$ is equal to the number of carries in the subtraction $p^{a+b}-i$; but it's easy to see that because we're subtracting from a power of $p$ this is actually just $a+b-v_p(i)$ (again, I can add in a proof if you really want). But, as noted previously, $i\le k<p^{b+1}$ (because $p^b$ is the largest power of $b$ that's at most $k$), and so we must have $v_p(i)\le b$ (since certainly $v_p(i)\le \lfloor\log_p i\rfloor$), and therefore $v_p(\binom{p^{a+b}}{i})\ge a$, i.e., $\binom{p^{a+b}}{i}$ vanishes modulo $p^a$. And so $\binom{n+p^{a+b}}{k}\equiv \binom{n}{k} \pmod{p^a}$.

Now we need to check that this period is minimal. Since this period is a power of $p$, and the minimal period must divide it, to check minimality we only need to check that $p^{a+b-1}$ is not a period. Again, we use Vandermonde's identity to expand $\binom{n+p^{a+b-1}}{k}$ as $\sum_{i=0}^k\binom{p^{a+b-1}}{i}\binom{n}{k-i}$; we want to show that, if we pick $n$ appropriately, this is not equal to $\binom{n}{k}$.

Again, obviously the $i=0$ term is just $\binom{n}{k}$. What we want to do is pick $n$ so that exactly one of the other terms is nonzero (modulo $p^a$); then we can be sure the overall sum is not equal to $\binom{n}{k}$. And indeed there is an $n$ that accomplishes this. Let $\ell=\lfloor \frac{k}{p^b}\rfloor$, so $\ell p^b$ is the largest multiple of $p^b$ that's at most $k$. We're going to pick $n=k-\ell p^b$. So our terms now look like $\binom{p^{a+b-1}}{i}\binom{k-\ell p^b}{k-i}$.

Most of the terms still vanish; as above, assuming $i\le p^{a+b-1}$, we have $v_p(\binom{p^{a+b-1}}{i})=a+b-1-v_p(i)$. So as long as $v_p(i)<b$, $\binom{p^{a+b-1}}{i}$ still vanishes modulo $p^a$. (What if $i>p^{a+b-1}$, which is now possible in the case that $a=1$, where $p^{a+b-1}=p^b$, which may be less than $k$? Well then $\binom{p^{a+b-1}}{i}=0$, so it certainly can't affect things.) However if $v_p(i)=b$ then it's not going to vanish! Let's say $i=jp^b$ (where $j$ is not divisible by $p$), so the terms we're now left looking at are $\binom{p^{a+b-1}}{jp^b}\binom{k-\ell p^b}{k-jp^b}$, where $1\le j\le \ell$.

Thing is most of these terms are going to be zero due to that second factor. If $j< \ell$, then $k-jp^>k-\ell p^b$, and thus $\binom{p^b}{k-jp^b}=0$, again vanishing.

This leaves the only remaining possible term that doesn't vanish (aside, of course, from $\binom{n}{k}$ itself) as $\binom{p^{a+b-1}}{p^b}\binom{k-\ell p^b}{k-\ell p^b}$. But this is just $\binom{p^{a+b-1}}{p^b}$, and we already know that $v_p(\binom{p^{a+b-1}}{p^b})=a-1$, i.e., it doesn't vanish modulo $p^a$.

Or, to sum up, we have that $$\binom{k-\ell p^b+p^{a+b-1}}{k}\equiv\binom{k-\ell p^b}{k}+\binom{p^{a+b-1}}{p^b}\not\equiv\binom{k-\ell p^b}{k}\pmod{p^a},$$ and so $p^{a+b-1}$ is not a period; this proves the theorem.

Hopefully you find that explanation understandable and satisfactory.

Now that all that's proven, I want to make a few additional notes to you:

With regard to the question "Most importantly to me, how can I express $f(x,y,z)$ in a mathematical way?" -- this question doesn't make a lot of sense. You've already given a definition of $f(x,y,z)$. (By the way, I'd use different variables if I were you... $x,y,z$ are typically used for continuous quantities, not discrete ones.) Don't make the mistake of thinking that writing things in terms of closed form and existing notation is writing things "mathematically", and defining things out in words isn't! This doesn't mean it's not useful to give things closed forms or relate them to existing concepts, but a number of people seem to think it's not mathematics if you don't, and of course it is. Like I said your expression at the beginning is overcomplicated; focus on describing what things are, not making sure you can do it in existing notation (there's no reason to involve the van Mangoldt function here, especially if you're just going to immediately get rid of the log).

I'll maybe return to some of the other questions you pose (like $f(0,2,k)$ (or more generally $f(0,p,k)$ for prime $p$) and $f(0,m,2)$ later... but yeah, there's a lot out there on this. You may want to sit down and give the papers you've already turned up another go. I'm pretty sure a lot of this can be done with just Vandermonde, Lucas, Kummer, and other such simple tools.

Edit: Here's a quick proof of your statement about $f(0,m,2)$. Again, by the Chinese remainder theorem, it suffices to consider $m$ a prime power. (Note that this sequence you've linked, A034444(m), is just $2$ raised to the number of distinct prime factors of $m$.) So let's consider $m=p^a$ once again; we want to show that $0$ occurs exactly twice. First suppose $p\ne 2$; then our period is just $p^a$. We want to solve $x(x-1)/2\equiv 0\pmod{p^a}$. Well, $2$ is a unit mod $p^a$, so this is just $x(x-1)\equiv 0\pmod{p^a}$. But the thing is, only one of $x$ or $x-1$ can be divisible by $p$, because they're adjacent numbers; so the other one (or both; at least one is the point) must be a unit mod $p^a$. Thus we conclude that $x$ must be either $0$ or $1$ mod $p^a$, and obviously both of these are solutions, so indeed we get exactly two solutions.

The other case is if $p=2$ (so $m=2^a$). In this case our period is $2^{a+1}$. Again we want to solve $x(x-1)/2\equiv 0\pmod{2^a}$, but now this turns into $x(x-1)\equiv 0\pmod{2^{a+1}}$. Still, we can onece again apply the same reasoning -- at least one of $x$ or $x-1$ must be a unit mod $2^{a+1}$ -- to conclude that there are exactly two solutions mod $2^{a+1}$, namely, $0$ and $1$. Since $2^{a+1}$ is our period in this case, this is exactly what we need.

(If you look, you'll notice this (well, OK, a slight variant of this, but which is by the above reasoning equivalent) is actually listed as a comment on the sequence page, added by Yuval Dekel.)

Edit again: Your remaining question, about $f(0,2,k)$ (or more generally $f(0,p,k)$, for prime $p$) can be answered using Lucas's theorem. I'll start out considering it for general $p$, then restrict to $p=2$ afterward.

First, our period here is $p^{1+\lfloor\log_p k\rfloor}$; note that $1+\lfloor\log_p k\rfloor$ is the number of digits of $k$ when written in base $p$. (Let's call this number $\ell$.) So we want to check numbers less than $p^\ell$, i.e., ones of $\ell$ or fewer digits. This is perfect for Lucas's theorem. Let's say $k$ has base-$p$ digits $k_\ell,\ldots,k_0$, and we want to see if some $n<p^\ell$ has $\binom{n}{k}\equiv0\bmod{p}$; let's say the base-$p$ digits of $n$ are $n_\ell,\ldots,n_0$ ($n$ might have fewer than $\ell$ digits, but that's OK, we can left-pad with zeroes.)

Now, by Lucas's theorem, $\binom{n}{k}\equiv\prod_{i]0}^\ell \binom{n_i}{k_i} \bmod{p}$. Since we're working modulo a prime, this product is $0$ if and only if some factor is $0$. As we'll shortly see, it's therefore easier to count the number of $n$ such that $\binom{n}{k}$ is not zero modulo $p$; let's count those instead, and then the answer will be $p^\ell$ minus that.

So, for $\binom{n}{k}$ to not be zero modulo $p$, we need that each $\binom{n_i}{k_i}$ is nonzero modulo $p$. This actually depends purely on whether or not $n_i$ is greater than $k_i$. Obviously if $n_i>k_i$, then $\binom{n_i}{k_i}=0$. While if $n_i\le k_i$, then since both are less than $p$, we can see (e.g. by Kummer's theorem -- there can't be a carry when you're subtracting one-digit numbers! -- or more directly, since the falling product $n(n-1)\cdots(n-k+1)$ obviously can't contain anything divisible by $p$) that $\binom{n_i}{k_i}$ is not divisible by $p$.

So, if we look at the base-$p$ digits of $k$, we see that for each $k_i$, the number of possible $n_i$ is equal to $p-k_i$. So the number of possible $n$ that make the result nonzero is equal to $\prod_{i=0}^\ell (p-k_i)$. But we were originally looking for $n$ that make the result equal to $0$, so we get that $f(0,p,k)=p^\ell-\prod_{i=0}^\ell (p-k_i)$.

Hopefully that answers your question! I think it should explain the behavior you're seeing.

Now let's see what happens when we restrict to $p=2$. In this case, the only possible $k_i$ are $0$ and $1$. Each $0$ contributes a factor of $2$ to the product above, while each $1$ contributes a factor of $1$, i.e., it doesn't contribute. So what we get in this case is $2^\ell-2^r$, where $r$ is the number of $0$s in the binary expansion of $k$. And it's pretty easy to see that that's the same thing as A073138(k). (Indeed, this is even mentioned in the formulas section, though that formula phrases it in terms of the number of $1$s instead.)

Anyway, I think that should answer all your questions! And give you a good base to work from if you have further such questions. :) Like I said above, I'm pretty sure a lot of this can be done with fairly simple tools.