On Pascal's triangle modulo p²

DOI10.4064/CM-74-1-157-165MaRDI QIDQ4373029zbMATH OpenOpenAlexFDO

Authors James G. Huard, Blair K. Spearman, Kenneth S. Williams

Publication date 4 November 2002

Published in Colloquium Mathematicum (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/210498

number of binomial coefficients Pascal's triangle

Congruences; primitive roots; residue systems (11A07) Sequences (mod (m)) (11B50) Binomial coefficients; factorials; (q)-identities (11B65)

Review text

Let $n$ be a nonnegative integer. The $n$th row of Pascal's triangle consists of the $n+1$ binomial coefficients $\binom n0 \binom n1 \binom n2\dots \binom nn$. Let $N_n(t,m)$ denote the number of these binomial coefficients that are congruent to $t$ modulo $m$, where $t$ and $m$ $(\geq 1)$ are integers. If $p$ is a prime write the $p$-ary representation of the positive integer $n$ as \[ n= a_0+ a_1p+ a_2p^2+\cdots+ a_kp^k, \] where $k\geq 0$, each $a_i= 0,1,\dots, p-1$ and $a_k\neq 0$. Denote the number of $r$'s occurring among $a_0,a_1,\dots, a_k$ by $n_r$ $(r=0,1,\dots, p-1)$ and set $\omega= e^{2\pi i/(p-1)}$. Let $g$ denote a primitive root $(\operatorname {mod}p)$ and $\operatorname {ind}_g t$ the index of the integer $t\not\equiv 0\pmod p$ with respect to $g$; that is, $\operatorname {ind}_g t$ is the unique integer $j$ such that $t\equiv g^j\pmod p$. \textit{E. Hexel} and \textit{H. Sachs} [Indian J. Math. 20, 91-105 (1978; Zbl 0499.10005), Theorem 3] have shown that for $t=1,2,\dots, p-1$, \[ N_n(t,p)= \frac{1}{p-1} \sum_{s=0}^{p-2} \omega^{-s\operatorname {ind}_g t} \prod_{r=1}^{p-1} B(r,s)^{n_r}, \tag{1} \] where for any integer $r$ not exceeding $p-1$ and any integer $s$, \[ B(r,s)=\sum_{c=0}^r \omega^{s\operatorname {ind}_g \binom rc}. \tag{2} \] Here the authors make use of the Hexel-Sachs formula (1) to determine the analogous formula for $N_n(tp,p^2)$ for $t=1,2,\dots, p-1$. They prove: Theorem 1: For $t=1,2,\dots, p-1$, \[ \begin{aligned} N_n(tp,p^2)= &\frac{1}{p-1} \sum_{i=0}^{p-2} \sum_{j=1}^{p-1} n_{ij} \sum_{s=0}^{p-2} \omega^{-s(\operatorname {ind}_g t+\operatorname {ind}_g (i+1)- \operatorname {ind}_g j)} \tag{3}\\ &\times B(p-2-i,-s) B(j-1,2) \prod_{r=1}^{p-1} B(r,s)^{n_r- \delta(r-i)- \delta(r-j)}, \end{aligned} \] where $\delta(x)= 1$ if $x=0$, $=0$ if $x\neq 0$, and $n_{ij}$ denotes the number of occurrences of the pair $ij$ in the string $a_0 a_1\dots a_k$. The authors also consider the special cases $p=2$ and $p=3$ and give a shorter proof of the result by Hexel and Sachs.

Recommendations

Cited in

(15)

This page was built for publication: On Pascal's triangle modulo $p^2$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4373029)