For $N\in\mathbb N$, let $$P_l(N)=\# \{(n,m)|0\le n\le N, 0\le m\le n,\binom{n}{m}\not\equiv 0 \mod l\}.$$ Suppose that $\binom{n}{0}=1$ for $n\ge 0$ and that $\# S$ represents the number of the elements of a set $S$.

Then, here are my questions.

Question 1 : Find $\lim_{N\to\infty}\log_N P_6(N)$.

Question 2 : Find $\lim_{N\to\infty}\log_N P_l(N)$ for $l={p_1}^{m_1}{p_2}^{m_2}\cdots {p_s}^{m_s}\ (p_1\lt p_2\lt \cdots\lt p_s)$.

Motivation : I've found that $\lim_{N\to\infty}\log_N P_p(N)=\log_p \frac{p(p+1)}{2}$ for any prime number $p$. However, I'm facing difficulty for non-prime-number cases. Can anyone help?

Remark : This question has been asked previously on math.SE without receiving any answers.

  • $\begingroup$ You may find something of interest in Granville's survey article on arithmetical properties of binomial coefficients, freely available at dms.umontreal.ca/~andrew/Binomial $\endgroup$ Oct 27 '13 at 22:41

${a \choose b} \not \equiv 0 \mod 6$ iff either ${a \choose b} \not \equiv 0 \mod 2$ or ${a \choose b } \not \equiv 0 \mod 3$. So, $$P_3(N) \le P_6(N) \le P_2(N) + P_3(N).$$

Since $P_2(N) = \Theta(N^{\log_2 3}) = \Theta(N^{1.585})$ is asymptotically negligible compared with $P_3(N) = \Theta(N^{\log_3 6}) = \Theta(N^{1.631})$,

$$P_6(N) \sim P_3(N).$$

In general, for square-free $\ell$ with largest prime factor $q$, $P_\ell(N) \sim P_q(N).$

I haven't checked the details, but I expect that if the largest prime power dividing $\ell$ is $q = p^k$, then $P_\ell(N) \sim P_q(N)$ and $\lim_{N\to\infty} \log_N P_\ell(N) = \log_p \frac{p(p+1)}{2}$. Edit: Actually, $q$ should be the power of the largest prime dividing $\ell$, not the largest prime power. If $\ell = 144 = 2^4 3^2$ then for large $N$, most of the binomial coefficients in the first $N$ rows of Pascal's triangle not divisible by $144$ should be divisible by $3$ and $16$ but not $9$.

  • $\begingroup$ I think I'll be able to prove that the answer for $(2)$ is $\log_{p_s}\frac{p_s(p_s+1)}{2}$ from your idea. Thank you so much! $\endgroup$
    – mathlove
    Oct 28 '13 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.