Roth’s estimate of the discrepancy of integer sequences is nearly sharp
Roth’s estimate of the discrepancy of integer sequences is nearly sharp
复制标题
罗斯对整数序列差异的估计几乎是尖锐的
DOI：
10.1007/bf02579452
复制
发表时间：
1981
期刊：
影响因子：
1.1
通讯作者：
J. Beck
中科院分区：
文献类型：
--
作者：
J. Beck
Abstractletg是{1，...，n} = [1，n]的颜色。 A. letr（g）的蓝色成员是所有算术进程（thediscrepancy ofg ofg）的最大值
$$ r（n）= \ mathop {\ min} \ limits_g r（g）$$
在所有两个颜色的结果上Sárközy通过证明这一点（n）≪N1/3+介绍差异的概念超图并得出上述结果随之而来的上限。
AbstractLetg be a coloring of the set {1, ...,N} = [1,N] in red and blue. For each arithmetic progressionA in [1,N], consider the absolute value of the difference of the numbers of red and of blue members ofA. LetR(g) be the maximum of this number over all arithmetic progression (thediscrepancy ofg). Set
$$R(N) = \mathop {\min }\limits_g R(g)$$
over all two-coloringsg. A remarkable result of K. F. Roth gives*R(N)≫N1/4. On the other hand, Roth observed thatR(N)≪N1/3+ɛ and suggested that this bound was nearly sharp. A. Sárközy disproved this by provingR(N)≪N1/3+ɛ. We prove thatR(N)=N1/4+o(1) thus showing that Roth’s original lower bound was essentially best possible.Our result is more general. We introduce the notion ofdiscrepancy of hypergraphs and derive an upper bound from which the above result follows.