设 $c_1,c_2,c_3,\ldots$ 是一列数, $C(t)=\sum_{n\leq t}c_n$. $f(t)$ 是 $t$ 的任意一个函数. 则有
\[\sum_{n\leq x}c_n f(n)=\sum_{n\leq x-1}[f(n)-f(n+1)]+C(x)f([x])\tag{1}\]

此外, 若假设 $c_j=0$ 对于所有 $j<n_1$, 并且 $f(t)$ 对于 $t\geq n_1$ 有连续的导数, 则有

\[\sum_{n\leq x}c_n f(n)=C(x)f(x)-\int_{n_1}^{x}C(t)f^{'}(t)dt\tag{2}\]

References

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. Oxford Science Publications.

$\vartheta(x)$ 和 $\psi(x)$ 定义为

\[\vartheta(x)=\sum_{p\leq x}\log x=\log\prod_{p\leq x}p\]

\[\psi(x)=\sum_{p^m\leq x}\log x=\sum_{n\leq x}\Lambda(n)\]

其中 $\Lambda(n)$ 是 von Mangoldt 函数, 定义为

\[\Lambda(n)=\begin{cases}\log p, & n=p^m,\\ 0, & n\neq p^m,\end{cases}\]

则

(1) $\psi(x)=\vartheta(x)+O(x^{1/2}\log^2 x)$;

(2) $\psi(x)$ 和 $\vartheta(x)$ 均是 $x^1$ 阶的. 即存在 $A_1,A_2$, 使得

$A_1 x\leq\psi(x)\leq A_2 x$, $A_1 x\leq\vartheta(x)\leq A_2 x$.

黎曼假设(Riemann Hypothesis)[RH] 等价于

\[
\psi(x)=x+O(x^{\frac{1}{2}+\varepsilon}).
\]

对于 $k,n\in\mathbb{N}$, 定义

\[f(n,k):=\sum_{n<v\leq n+k, P(v)\leq k}1\]

其中 $P(v)$ 指正整数 $v$ 的最大素因子.

当 $k\geq n$ 时, 显然有

\[f(n,k)=k-\bigl(\pi(n+k)-\pi(k)\bigr)\]

这里 $\pi(k)$ 指不超过 $k$ 的素数个数.

References

P. Erdos and J. Turk, Products of integers in short intervals,

这个结论是 Erdõs 证明的, 参见[0].

对于连续的 $k$ 个正整数 $n, n+1,\ldots, n+k-1$, 人们早已猜测它们的乘积

\[A_k(n)=n(n+1)\cdots(n+k-1)\]

不可能是某个正整数的 $\ell$ 次幂. (这里 $k>1$, $\ell>1$).

对于 $k=2$ 和 $k=3$ 的情形, 这个结论是熟知的.

如对于 $k=2$, $n^2<n(n+1)<(n+1)^2$, 所以 $n(n+1)$ 不可能是某个整数的平方. 一般的, 注意到 $n$ 和 $n+1$ 是互素的, 除 1 之外没有公因子, $n=a_1 x_1^\ell$, $n+1=a_2 x_2^\ell$, 且$a_1 a_2=x_3^\ell$, 因此不存在 $\ell>1$,  使得 $n(n+1)=x^\ell$.

假设 $(n+1)(n+2)(n+3)=x^\ell$, 同样的, 可设 $n+i=a_i x_i^\ell$, $i=1,2,3$. 且 $a_1 a_2 a_3=x_0^\ell$. 要知道 $n+1$, $n+3$ 如果是奇数, 则一定互素, 如果是偶数, 则至多有公因子 2. 因此若 $2|x_0$, $\ell$ 必须为 2. 但是 $(n+1)(n+2)(n+3)=x^2$ 这是不可能的. 否则由于 $x>n+2$, 必有 $x|(n+1)(n+3)$.

Q. 两个相邻奇数 $2k-1$, $2k+1$ 是否互素?
A. 若有公因子 $d>1$, 设 $2k-1=ad$, $2k+1=bd$, 则 $bd-ad=2$, 这推出 $(b-a)d=2$. 又 $b-a>0$, 而 $d$ 不可能是 2, 故矛盾. 因此相邻两个奇数一定互素.

References

[0] P. Erdõs, Note on products of consecutive integers, Journal of the London Mathematical Society, Vol. 14, 1939.

设 $N\leq a^m<b^m$, 则这两个幂不可能同在区间 $[N,N+\sqrt{N}]$ 中. 其中 $a,b,m\in\mathbb{N}$.

J. Turk 考虑了所谓的 almost 幂, 也得到类似的结果. 所谓 almost 幂, 指形如 $ax^m$ 的数, 其中 $a$ 相对 $x^m$ 来说比较小. (这里 $a,x,m$ 也都是正整数, $a>1$. 一般的, 如果不另外申明, 所考虑的均是正整数, 至少是整数.) 若假设 $a$ 有界, 则得到了下面的结论.

(1) $[N,N+cN^{1/3-\varepsilon}]$ 中不可能同时有两个形如 $n_i=a_i x_i^m$ 的不同整数, 其中 $m\geq 3$, $a_i\leq A$, $i=1,2$. 这里 $\varepsilon>0$ 和 $A\geq 1$ 是任意的, $c=c(\varepsilon, A)$ 是仅依赖于 $\varepsilon$ 和 $A$ 的正数. 指数 $1/3$ 是最优的: 因为存在某个 $c_0>0$ 和无穷多的 $N\in\mathbb{N}$, 使得 $[N,N+c_0 N^{1/3}]$ 包含两个形如 $x_1^3$, $2x_2^3$ 的不同整数.

(2) $[N,N+cN^{1/4-\varepsilon}]$ 不可能同时含有三个形如 $n_i=a_i x_i^2$ 的整数, 其中对所有 $i=1,2,3$, $a_i\leq A$. 这里 $c=c(\varepsilon,A)>0$ 及指数 $1/4$ 是最优的: 因为存在某个 $c_1>0$ 和无穷多的 $N\in\mathbb{N}$ 使得 $[N,N+c_1N^{1/4}]$ 含有三个形如 $x_1^2,2x_2^2,3x_3^2$ 的不同整数.

(3) $[N,N+\Phi(N)]$ 不可能含有形如 $n_i=a_i x_i^m$ 的两个 almost powers. 这里 $m\geq 3$ 且 $a_i\leq\varphi(n_i)$, $i=1,2.$

Remark

1. (1) 中 $m$ 不能为 2, 因为两个不同的近平方数(almost squares)可以非常靠近. 如不定方程 $x_1^2-2x_2^2=1$ 存在无穷多组解.

2. (1) 中 $c=c(\varepsilon,A)$ 关于 $A$ 和 $\varepsilon$ 的依赖关系尚不清楚. 因此 (1) 并没有断言一个短区间永不包含两个具有相同指数(大于2)的 almost powers.

3. (1) 和 (2) 实际上是更一般结论的特殊情形. 详见

References

Jan Turk, Almost powers in short intervals, Arch. Math., Vol. 43, 157-166 (1984)

如: $\sqrt{3}<2<3$, $\sqrt{4}<3<4$, $\sqrt{5}<3<5$, $\sqrt{6}<3,5<6$, ...

此结论可以作为 Sylvester 定理的一个直接推论.

这里 $\pi(k)$ 指小于等于 $k$ 的所有素数个数. 注意一般的有

\[\pi(x)\sim\frac{x}{\ln x}\]

这就是所谓的素数定理.

Schur 指出: 当 $k>37$ 时, 有 $\pi(k)<\frac{1}{3}k$.

References

Paul Erdos, A theorem of Sylvester and Schur. Journal of the London Mathematical Society, Vol.9, Part 4.

引理. 若 $\binom{n}{k}$ 可被某个素数 $p$ 的幂 $p^\alpha$ 整除, 则 $p^\alpha\leq n$.

若 $\alpha$ 是最大的, 则有 $p^\alpha\leq n<p^{\alpha+1}$.

Erdős proved that for any positive integer k, there is a natural number N such that for all n > N, there are at least k primes between n and 2n. An equivalent statement had been proved earlier by Ramanujan (see Ramanujan prime).

Erdős [1] 对 Bertrand 假设给出了一个非常漂亮的初等证明.

Erdős 证明了对任意正整数 $k$, 存在 $N$, 使得对所有 $n>N$, 至少有 $k$ 个素数介于 $n$ 和 $2n$ 之间.

http://en.wikipedia.org/wiki/Bertrand\'s_postulate

[1] P. Erdős, Beweis eines Satzes von Tschebyschef, Acta Sci. Math. (Szeged) 5 (1930–1932), 194–198.

[2] David Galvin, Erd˝os\'s proof of Bertrand\'s postulate. [PDF]

Bertrand 假设的提出是为了置换群的应用的. Sylvester (1814–1897) 将它推广如下:

Sylvester 定理: $k$ 个连续正整数(均大于 $k$)的乘积可被某个大于 $k$ 的素数整除.

换个说法, 设 $n>k$, 则 $n,n+1,\ldots,n+k-1$ 这 $k$ 个数中存在一个数含有大于 $k$ 的素因子.

当 $n=k+1$ 时, 便得到著名的 Chebyshev 定理.

这个定理首先是由 Sylvester 大概于1889年提出并证明的. J. Schur[] 在1929年重新证明了该定理. 后来 Erdos []发现了更初等、更漂亮的证明. 其证明并不需要 Chebyshev 定理的结论.

由于 $n-k+1,n-k+2,\ldots,n-1,n$ 中含有大于 $k$ 的素数因子等价于 $\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 2\cdot 1}$ 中含有大于 $k$ 的素因子. 因此可以把 Sylvester 定理改写为如下形式:

若 $n\geq 2k$, 则 $\binom{n}{k}$ 含有大于 $k$ 的素数因子.

为此, 我们先证明下面的引理.

引理. 若 $\binom{n}{k}$ 可被某个素数 $p$ 的幂 $p^\alpha$ 整除, 则 $p^\alpha\leq n$.

证明参见问题667

若 $\binom{n}{k}$ 不含有大于 $k$ 的素数因子, 则 $\binom{n}{k}\leq n^{\frac{1}{2}k}$. 这是因为可将 $\binom{n}{k}$ 写成素数的乘积形式, 由于其不含有大于 $k$ 的素数, 因此素数分解式至多含有 $\pi(k)$ 项. 形如

\[p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_{\pi(k)}^{\alpha_{\pi(k)}}\]

根据上面的引理, 诸 $p_i^{\alpha_i}\leq n$, 因此 $\binom{n}{k}\leq n^{\frac{1}{2}k}$. 这里用到了 $\pi(k)<\frac{1}{2}k$, 对 $k\geq 8$.

另一方面,

\[\binom{n}{k}=\frac{n}{k}\cdot\frac{n-1}{k-1}\cdot\frac{n-2}{k-2}\cdots\frac{n-k+1}{1}>\Bigl(\frac{n}{k}\Bigr)^k\]

从而 $\Bigl(\frac{n}{k}\Bigr)^k<n^{\frac{1}{2}k}$, 即 $n^{\frac{1}{2}k}<k^k$. 显然, 当 $k\leq\sqrt{n}$ 时, 这不会成立. 因此对于 $8\leq k\leq\sqrt{n}$ 证明了定理.

作为一个直接推论, 得到:

推论: 若 $n>2$, 则 $\sqrt{n}$ 和 $n$ 之间必存在一素数. (见问题669)

Pf. 上面已经对于 $8\leq k\leq\sqrt{n}$ 证明了 Sylvester 定理. 在此假设下, 注意到 $f(x)=x-\sqrt{x}$ 在 $(1,+\infty)$ 上是单调递增的, 因此 $n-\sqrt{n}\geq k^2-k>k$, 由 Sylvester 定理即得此推论. 对于 $n<64$ 的情形可以简单验证.

由于 Schur 指出当 $k>37$ 时, 有 $\pi(k)<\frac{1}{3}k$. 因此类似于上面的论述, 对于

\[37<k\leq n^{\frac{2}{3}}\]

Sylvester 定理也成立.

http://en.wikipedia.org/wiki/Bertrand\'s_postulate

Paul Erdos, A theorem of Sylvester and Schur. Journal of the London Mathematical Society, Vol.9, Part 4.

J. Schur, Einige Sätze über Primzahlen mit Anwendung auf Irreduzibilitätsfragen. Sitzungsberichte der preussischen Akademie der Wissenschaften, Phys. Math. Klasse, 23 (1929), 1-24.