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 的一个帖子密率与无穷项等差数列的讨论.]

 Leave a Reply

(required)

(required)

This site uses Akismet to reduce spam. Learn how your comment data is processed.