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.

up vote 4 down vote accepted

${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$.

  • 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! – mathlove Oct 28 '13 at 14:39

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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