Lower bound for a formula containing binomial coefficient

234 Views Asked by At

I have the following function $$ f(s,p) = \binom{s}{\left\lceil \frac{p-1}{p}s \right\rceil} (p-1)^{\left\lceil \frac{p-1}{p}s \right\rceil}$$

which describes the number of $p$-ary words of length $s$ and Hamming weight $r= \left\lceil \frac{p-1}{p}s \right\rceil$ (number of non-zero positions). I use the Hamming weight $r= \left\lceil \frac{p-1}{p}s \right\rceil$ since it maximizes the number of the words of length $s$. Here, $s\geq1$ and $p\geq2$.

Now I am interested in a valid lower bound for that number $f(s,p)$.

I would be happy, of someone could help me by finding a lower bound.

Thank You!

1

There are 1 best solutions below

7
On BEST ANSWER

By Striling formula, for each $n$ there exists a number $0<\theta_n<1$ such that $n!=\sqrt{2\pi n}\left(\frac ne\right)^n e^{\frac{\theta_n}{12n}}$. So for $s>r$ we have

$$\ln f(s,p)= s\ln s -r\ln r- (s-r)\ln (s-r)+ r\ln (p-1)+ \frac 12\left(\ln s-\ln r-\ln (s-r)-\ln 2\pi\right)+\frac{1}{12}\left(\frac{\Theta_s}{s}-\frac{\Theta_r}{r}+\frac{\Theta_{s-r}}{s-r}\right)>$$ $$\left(s+\frac 12\right)\ln s -\left(r+\frac 12\right)\ln r- \left(s-r+\frac 12\right)\ln (s-r)+ r\ln (p-1)-\frac{\ln 2\pi}2-\frac{1}{12(s-r)}.$$

In particular, if $r=\frac {p-1}{p}s$ then we have

$$\ln f(s,p)>\frac12\left((2s+2)\ln p-\ln s- \ln (p-1)- \ln 2\pi-\frac{p}{6s}\right).$$

Update. If $f(s,p)$ non-decreases with respect to $s$ and we allowed to lost terms of order $O(p)$ then we may assume that $s$ is divisible by $p$ and so the second lower bound is applicable. It shows that it suffices to have

$$ (2s+2)\ln p-\ln s- \ln (p-1)- \ln 2\pi-\frac{p}{6s}\ge 2\ln X.$$

Since $\ln (p-1)\le \ln p$, $s\ge p$, and $\ln s \le s-1$, it suffices to have

$$ s \ge \frac{2\ln X-\ln p +\ln 2\pi-\frac{5}{6}}{2\ln p-1}.$$

I expect that the smallest required $s$ is not essentially smaller than that.