Jul 082020
 

​7月7日,Thomas F. Bloom, Olof Sisask 在 arXiv 上传了一篇论文 Breaking the logarithmic barrier in Roth’s theorem on arithmetic progressions( arxiv.org/abs/2007.03528), 该文的主要结果是证明了:

Theorem 1 如果 \(A\subset \{1, . . . , N\}\), 且 \(A\) 不含非平凡的三项等差数列,即 \(x+y=2z\) 的解, \(x\ne y\). 则

\[|A|\ll \frac{N}{(\log N)^{1+c}}\]

\(c\gt 0\) 是绝对常数.

Thomas F. Bloom, Olof Sisask 的这个结果改进了Roth 的一个关于整数不含三项等差数列的上界的定理。

如果 \(A\subset \{1, . . . , N\}\), 且 \(A\) 不含非平凡的三项等差数列,那么 \(A\) 的阶可以有多大?

在此之前的记录是:\(A\) 的元素个数可达 \(O\Big(\frac{N}{(\log N)^{1-o(1)}}\Big)\). 这个结果可以找到三个不同的证明,这些证明在 \(o(1)\) 这一项有一点差异。这几个证明来自Sanders, Thomas F. Bloom, Olof Sisask, 还有 Schoen.

要指出的是:常数 \(c\) 是 principle effective,但是计算它需要艰巨的工作。

数学家们的期待,是 Behrend​ 提出的猜想,这个最佳的上界是

\[|A|\ll Ne^{-O((\log N)^c)}\]

接下来,说一下 Thomas F. Bloom的Olof Sisask 定理的第一个副产品:

Erdos 的著名猜想

Erdos 有一个著名的猜测是:如果 \(A\subset\Bbb N\), 且  \(\sum\limits_{n\in A}\frac1n=\infty\),那么 \(A\) 包含任意长的等差数列。

由 Thomas F. Bloom, Olof Sisask  的定理,可以导出 Erdos 的这著名猜想的一个不平凡的特殊情况:

Corollary 2 如果 \(A\subset\Bbb N\), 且  \(\sum\limits_{n\in A}\frac1n=\infty\),那么 \(A\) 含无穷多非平凡的三项等差数列。

Proof.  若不然,假定 \(A\subset\Bbb N\), 且 \(A\) 仅仅含有有限个非平凡的三项等差数列。于是,对于任意的 \(N\)

\[F(N)\colon=|A\cap\{1, . . . , N\}|\ll\frac{N}{(\log N)^{1+c}}+1,\]

这里的 \(c\) 是定理 1 的常数。进而

\[\sum_{n\in A\atop n\leq N}\frac1n=\frac{F(N)}{N}+\int_1^N\frac{F(t)}{t^2}\mathrm dt\ll \int_1^N\frac{1}{t(\log t)^{1+c}}\mathrm dt+1\ll1.\]

令 \(N\to\infty\), 得 \(\sum\limits_{n\in A}\frac1n\) 收敛。

\(A\) 的阶的下界

最后,顺便提一下 \(A\) 的阶的下界, 1946年 Behrend的高维球面构造法给出了

\[|A|\geq Ne^{-c\sqrt{\log N } }\]

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