主题
Search

差异定理


s_1, s_2, ... 为介于 0 和 1 之间的实数无限序列。那么,对于任何任意大的 K,都存在一个正整数 n 和两个等长的子区间,使得 s_nu (其中 nu=1, 2, ..., n)在一个子区间中的数量与在另一个子区间中的数量之差大于 K (van der Corput 1935ab, van Aardenne-Ehrenfest 1945, 1949, Roth 1954)。

这个陈述可以如下改进。设 N 为一个大的整数,s_1, s_2, ..., s_NN 个介于 0 和 1 之间的实数序列。那么对于任何整数 1<=n<=N 和任何满足 0<alpha<1 的实数 alpha,设 D_n(alpha) 表示满足 0<=s_nu<alphas_nu (其中 nu=1, 2, ..., n)的数量。那么存在 nalpha 使得

 |D_n(alpha)-nalpha|>c_1(lnlnN)/(lnlnlnN)
(1)

其中 c_1 是一个正的常数。Schmidt (1972) 改进了这个结果,得到

 |D_n(alpha)-nalpha|>lnN/100,
(2)

这基本上是最优的。

DiscrepancyTheorem

这个结果可以进一步加强,最容易通过重新表述问题来完成。设 N>1 为一个整数,P_1, P_2, ..., P_N 为正方形 0<=x<=1, 0<=y<=1 中的 N 个(不必相异)点。那么

 int_0^1int_0^1[S(x,y)-Nxy]^2dxdy>c_2lnN,
(3)

其中 c_2 是一个正的常数,S(u,v) 是矩形 0<=x<u, 0<=y<v 中的点数 (Roth 1954)。因此,

 |S(x,y)-Nxy|>c_3sqrt(lnN),
(4)

并且最初的结果可以表述为存在 nalpha 使得

 |D_n(alpha)-nalpha|>c_4sqrt(lnN).
(5)

以上正方形中显示的随机分布的点分别具有 |S(x,y)-Nxy|^2=6.40 和 9.11 的 |S(x,y)-Nxy|^2=6.40 值。

类似地,单位 d-超立方体N 个点的差异满足

 |S(x,y)-Nxy|>c(lnN)^((d-1)/2)
(6)

(Roth 1954, 1976, 1979, 1980)。


另请参阅

18 点问题, 立方体点拾取, 差异

使用 探索

参考文献

Berlekamp, E. R. and Graham, R. L. "Irregularities in the Distributions of Finite Sequences." J. Number Th. 2, 152-161, 1970.Roth, K. F. "On Irregularities of Distribution." Mathematika 1, 73-79, 1954.Roth, K. F. "On Irregularities of Distribution. II." Comm. Pure Appl. Math. 29, 739-744, 1976.Roth, K. F. "On Irregularities of Distribution. III." Acta Arith. 35, 373-384, 1979.Roth, K. F. "On Irregularities of Distribution. IV." Acta Arith. 37, 67-75, 1980.Schmidt, W. M. "Irregularities of Distribution. VII." Acta Arith. 21, 45-50, 1972.van Aardenne-Ehrenfest, T. "Proof of the Impossibility of a Just Distribution of an Infinite Sequence Over an Interval." Proc. Kon. Ned. Akad. Wetensch. 48, 3-8, 1945.van Aardenne-Ehrenfest, T. Proc. Kon. Ned. Akad. Wetensch. 52, 734-739, 1949.van der Corput, J. G. Proc. Kon. Ned. Akad. Wetensch. 38, 813-821, 1935a.van der Corput, J. G. Proc. Kon. Ned. Akad. Wetensch. 38, 1058-1066, 1935b.

在 中被引用

差异定理

请引用为

Weisstein, Eric W. "差异定理。" 来自 Web 资源。 https://mathworld.net.cn/DiscrepancyTheorem.html

学科分类