2
$\begingroup$

Let $(x)_0=1$ and $(x)_n=x(x-1)\cdots(x-n+1)$ for $n=1,2,3,\ldots$. The signed Stirling numbers of the first kind, $s(n,k)$ with $n\ge k\ge0$, are defined by $$(x)_n=\sum_{k=0}^ns(n,k)x^k.$$

Question. Whether for each integer $k\ge12$ and any prime $p$ the set $$\{s(n,k):\ n=k,k+1,\ldots\}$$ contains a complete system of residues modulo $p$?

I conjecture that this question has a positive answer. For $12\le k\le 100$ and any prime $p<300$, I have verified that the set $\{s(n,k):\ n=k,k+1,\ldots\}$ contains a complete system of residues modulo $p$. It seems that the set $\{s(n,11):\ n\ge11\}$ contains no number congruent to $6$ modulo $19$.

A similar problem with $s(n,k)$ replaced by the binomial coefficient $\binom{n}{k}$ was studied in the following paper: Zhi-Wei Sun and Wei Zhang, Binomial coefficients and the ring of $p$-adic integers, Proc. Amer. Math. Soc. 139 (2011), no. 5, 1569-1577.

Your comments are welcome!

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Note that I require $k\ge 12$ in the question. $\endgroup$
    – Zhi-Wei Sun
    Commented Oct 1 at 4:13
  • $\begingroup$ If $n\geqslant 12\cdot 19$, then every set consisting of $n-11$ elements of $\{0,1,\dots n-1\}$ contains a number divisible by 19, thus the sum of products of such subsets ($=(-1)^{n-11}s(n,11)$) is divisible by 19. This should allow to verify on computer the claim that $s(n, 11)$ is never congruent to 6 modulo 19 $\endgroup$
    – Fedor Petrov
    Commented Oct 1 at 4:33
  • $\begingroup$ Naive heuristic suggests that for fixed $k$ and $p$ a specific remainder modulo $p$ is missed by $s(\cdot, k) $ with probability like $(1-1/p)^{pk}\approx e^{-k}$, thus, for primes of order of magnitude $e^k$ and larger some remainder should be missed. $\endgroup$
    – Fedor Petrov
    Commented Oct 1 at 4:47
  • 1
    $\begingroup$ $s(70,11)$ is negative, it is congruent to $-6$ modulo $19$. $\endgroup$
    – Zhi-Wei Sun
    Commented Oct 2 at 0:38
  • 1
    $\begingroup$ $k=12$, $p=509$ appears to lack residue $150$ (tested for $n$ up to $10^6$). $\endgroup$
    – Peter Taylor
    Commented Oct 2 at 11:21

1 Answer 1

Reset to default
3
$\begingroup$

There is some $N(k, p)$ such that $n \ge N(k, p) \implies s(n, k) \equiv 0 \pmod p$. Proof is straightforward by fixing $p$ and using induction on $k$ via the recurrence $$s(n, k) = s(n-1, k-1) - (n-1)s(n-1, k).$$ In fact, the same proof idea shows that $N(k, p) \le kp+1$ so this allows for effective testing of $(k, p)$. Fedor Petrov's first comment on the question hints at this.

Fedor's second comment argues heuristically that counterexamples should exist in primes of the order of $e^k$. In practice, the smallest counterexamples seem to be much smaller than that.

$$\begin{array}{ccc} k & p & \textrm{Uncovered residues} \\ 12 & 509 & \{150\} \\ 13 & 2243 & \{1761\} \\ 14 & 5233 & \{1128\} \\ 15 & 5233 & \{4105\} \\ 16 & 5233 & \{1128\} \\ 17 & 5233 & \{4105\} \\ 18 & 5233 & \{1128\} \\ 19 & 73681 & \{926\} \\ 20 & 153611 & \{108851\} \\ 21 & 212671 & \{50455\} \\ 22 & 232129 & \{169472\} \\ \end{array}$$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .