主題
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.tw/DiscrepancyTheorem.html

學科分類