Jul 112013
 

不存在无穷质数等差数列. 下面是几种证明:

设等差数列的首项为 \(a\), 公差为 \(d\).

证明 1

分两种情况:

  • a=1. 此时 \(1+(d+2)d=(d+1)^2\) 是合数;
  • \(a\geqslant2\). 此时 \(a+ad=a(d+1)\) 是合数.

证明 2

连续合数可以任意长, 这是熟知的. 不曾想,  一个副产品居然就是我们的目标.

\((m+1)!+2,(m+1)!+3,\dotsc,(m+1)!+m+1\) 是 \(m\) 个连续合数.

证明 3

稍强一点的结果 采用完全剩余系

取一个与公差 \(d\) 互质的正整数 \(m\),

\[a, a+d, a+2d, \dotsc, a+(m-1)d\]

将跑遍 \(\bmod  m\) 的完全剩余系, 于是必有一项 \(\equiv0\pmod m\).

证明 4

这个结论也是熟知的: 不存在多项式

\[f(x)=\sum\limits_{i=0}^ma_ix^i,\]

使得对于任意 \(n∈\Bbb N, f(n)\) 都是质数.

证明 5

这个高级一点点: 采用自然密率 (natural density 或 asymptotic density), 而不是更常见的 Schnirelmann 密率 (Schnirelmann density).

由质数组成的集合的 asymptotic density 是 \(0\), 而等差数列形成的集合的 asymptotic density 为正.

证明 6

使用中国剩余定理证明”连续合数可以任意长”的加强版. 这个证明来自 matrix67 在2015年5月30日的日志, 但这里一些改进.

任取 \(n\) 个两两互质的正整数 \(m_1\), \(m_2\), \(\dotsc\), \(m_n\). 存在正整数 \(a\), 使得

\[m_i|\left(a+i\right),  i=1, 2, \dotsc, n.\]

[证明 6 更新于 北京时间 2015 年 6 月 24 日]

Jun 072012
 

密率与无限算术级数

Szemerédi’s theorem 任意有正(上)密率的正整数的子集必定包含任意长的算术级数.

Van der Waerden’s theorem 把正整数集合任意划分成两个子集, 必有一个子集包含任意长的算术级数.

这里先要说明的是, Szemerédi’s theorem中的子集未必包含无限长的算术级数, Van der Waerden’s theorem 也未必有一个子集包含无限长的算术级数. 看下面的例子:

\[ \{1,2,3\}\bigcup \{n: 2^{2i} \leqslant n < 2^{2i+1}, i \in {\Bbb N}\}\]

问题:正整数集合的子集 \( A\) 的密率 \( \sigma (A)\) 满足什么条件的时候, 必定包含无限长的算术级数呢?

上面的例子说明,\( \sigma (A) > 0 \)不能保证包含无限长的算术级数. 那么, 是否存在一个正数 \( \gamma \), 使得只要 \( \sigma (A) \geqslant \gamma \), 就有 \( A\) 包含无限长的算术级数呢?[问题提出于10月9日, 写在 WordPress 的一个免费 blog 是10日]

很不幸.  没有这样的正数.  事实上, 任何正数 \( \gamma < 1 \), 有正整数集合的子集 \( A \) , 满足 \( \sigma (A) > \gamma\) ,但是 \( A\) 并不包含无限长的算术级数 . 比如,考虑下面的例子:

\( 1, 2, 3, \dotsc, 10\), 去掉最后\( 1\)个;
\( 11, 12, 13, \dotsc, 100\), 去掉最后\( 9\)个;
\( 101, 102, 103, \dotsc, 1000\), 去掉最后\( 90\)个;
如此下去,\(\dotsc\)

这样得到的正整数集合的子集的密率是\( 0.9\), 但是没有无限长的算术级数, 因为相邻两项的差可以任意大.

那么,进一步考虑[10月12日]:
\[ a_1 < a_2 < a_3 < \dotsb\]
是一正整数列, 并且存在 \(m\), 使得
\[ a_{i+1} – a_i < m\]
对所有的正整数 \( i\) 成立, 其密率很接近 \(1\), 则该数列包含无限长的算术级数.

很遗憾,答案也是否定的. 事实上, 无限长的算术级数必是以下三种形式之一:

  • 全部是奇数;
  • 全部是偶数;
  • 奇偶交替。

于是,很容易就做出反例来,而且这样的正整数的子列的密率可以任意接近 \( 1\).

Start from x1= 1

The first 101  increments are all 1: 2,…, 102
Followed by 1 2-increments: 104 (all even)
Then, 1001   1-increments, 105,… 1105
followed by 2 2-increments: 1107, 1109 (all odd)
Then 10001  1-increments
followed by 3 2-increments:  (all even)
Then 100001  1-increments
followed by 4 2-increments  (all odd)
….

The idea is to make the 2-increment blocks to be all even follwed by all odd
follwed by all even …..

看来, 要找出一个充要条件还真难! [ 11月1日1时24分]

[本文实际上,完成于 2009 年,是我在 mitbbs 的一个帖子密率与无穷项等差数列的讨论.]