Erdos论文中$A(p;(t+1)p^{r})$上界不等式的推导疑问
嘿，我来帮你理清这个不等式的推导逻辑！首先得明确$A(p;x)$的定义——在这篇讨论$\binom{2n}{n}$素因子的论文里，$A(p;x)$指的是不超过x的正整数n中，满足$p \nmid \binom{2n}{n}$的n的个数（也就是$\gcd(\binom{2n}{n},p)=1$的n的数量），这个定义是理解的核心。
下面一步步拆解这个上界的由来：
第一步：拆分区间
我们把$[1, (t+1)pr]$这个大区间拆成$t+1$个长度均为$pr$的子区间：$[1,p^r], [pr+1,2pr], ..., [tpr+1,(t+1)pr]$。每个子区间可以统一表示为$I_k = [kp^r + 1, (k+1)p^r]$，其中k从0到t。第二步：用Lucas定理分析单个区间
对于任意$n \in I_k$，可以写成$n = kp^r + m$（$m \in [1,p^r]$）。根据Lucas定理（Erdos处理这类组合数素因子问题的常用工具），$\binom{2n}{n}$不被p整除的充要条件是：在p进制下，n的每一位数字$d_i$都满足$\binom{2d_i}{d_i} \not\equiv 0 \pmod{p}$。而这个等价于$d_i \leq \frac{p-1}{2}$——如果$d_i > \frac{p-1}{2}$，那么$2d_i \geq p$，组合数$\binom{2d_i}{d_i}$里会直接包含因子p，导致整个$\binom{2n}{n}$被p整除。第三步：计算单个区间的最大满足数
对于子区间$I_k$里的n，它的p进制后r位是m的p进制表示，高位部分是k的p进制表示。不管高位k的情况如何，子区间里满足条件的n的数量最多等于满足$p \nmid \binom{2m}{m}$的m的数量。
而m是1到$pr$的数，满足条件的m的个数正好是$(\frac{p+1}{2})r$：因为m的p进制每一位可以取0到$\frac{p-1}{2}$（共$\frac{p+1}{2}$种选择），r位的组合数就是这个数的r次方（即使m从1开始，总数也不会超过这个值，不影响上界）。第四步：累加得到总上界
每个子区间里满足条件的n的数量都不超过$(\frac{p+1}{2})^r$，而我们一共有$t+1$个这样的子区间，把它们的上界累加起来，就得到：
$$A(p;(t+1)p^{r})\leq (t+1)\left(\frac{p+1}{2}\right)^{r}$$
备注：内容来源于stack exchange，提问作者RAHUL
