Let $a$ and $p$ be positive integers, and consider the polynomial $$(1+x+\cdots+x^{p-1})^a = \sum_{i=0}^{a(p-1)} a_ix^i.$$ I'm looking for an asymptotic estimate of $\sum_{i=0}^{b} a_i$. If $p=2$, this is just the sum of the binomial coefficients $ {a \choose i} $ from $0$ to $b$, and there is an asymptotic estimate for this bound (see Exercise $9.42$ from the book R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics).
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Asymptotic under what conditions on $p,a,b$? $\endgroup$Iosif Pinelis– Iosif Pinelis2025-05-13 12:20:03 +00:00Commented May 13 at 12:20
-
$\begingroup$ $p$ and $a/b$ are constant, and $a$ goes to infinity. $\endgroup$FABIO MASTROGIACOMO– FABIO MASTROGIACOMO2025-05-13 13:26:48 +00:00Commented May 13 at 13:26
-
$\begingroup$ Let $X_1, X_2, \dots, X_a$ be iid and drawn uniformly at random from $\{0,1,\dots, p-1\}$. What is the probability that $\sum X_i\le Ca$? In the $a\to \infty$ limit you get a normal distribution, and so theorems like the Berry-Esseen theorem will give you a precise asymptotic. $\endgroup$TheBestMagician– TheBestMagician2025-05-13 13:33:27 +00:00Commented May 13 at 13:33
-
1$\begingroup$ Btw, $$a_i = \sum_{k=0}^{\lfloor i/p\rfloor} (-1)^{i+k(p+1)} \binom{a}{k}\binom{-a}{i-pk}.$$ $\endgroup$Max Alekseyev– Max Alekseyev2025-05-13 15:49:18 +00:00Commented May 13 at 15:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
As mentioned in my comment, the situation is equivalent to the following: We have $X_1, \dots, X_a$ drawn iid uniformly from $\{0,1,\dots, p-1\}$, and we wish to estimate $\mathbb{P}(\sum X_i\le Ca)$ for a constant $C$.
Let $Y_a$ be the average of all the $X_i$. The Berry-Esseen theorem tells us with $Z_a(x)$ being the cumulative distribution function of $$\frac{Y_a-a\mu}{\sigma\sqrt{a}}$$ that $$|Z_a(x)-\Phi(x)|\le K\frac{\rho}{\sigma^3\sqrt{a}},$$ where $\mu=\mathbb{E}(X_1)$, $\sigma^2=Var(X_1)$, $\rho=\mathbb{E}(|X_1-\mu|^3)$, and $\Phi(x)$ is the cumulative distribution function of the standard normal, for some constant $K$. All of these quantities are not hard to calculate and the bound we wish for naturally follows.
-
3$\begingroup$ If $C>\mu$, then the limit of the probability is $1$, by the law of large numbers. If $C=\mu$, then the limit is $1/2$, by the central limit theorem. If $C<\mu$, then the asymptotic of the probability is best described, not by the Berry--Esseen theorem, but by Petrov's extension of the Cramér theorem (see Theorem 6 in Petrov's paper). $\endgroup$Iosif Pinelis– Iosif Pinelis2025-05-13 14:17:49 +00:00Commented May 13 at 14:17