TY - JOUR
T1 - Fibonacci sets and symmetrization in discrepancy theory
AU - Bilyk, Dmitriy
AU - Temlyakov, V. N.
AU - Yu, Rui
PY - 2012/2
Y1 - 2012/2
N2 - We study the Fibonacci sets from the point of view of their quality with respect to discrepancy and numerical integration. Let {bn} n=0 ∞ be the sequence of Fibonacci numbers. The bn-point Fibonacci set Fn⊂[ 0,1]2 is defined as Fn:=(μbn,μbn-1b n)μ=1bn, where x is the fractional part of a number x∈ℝ. It is known that cubature formulas based on the Fibonacci set Fn give optimal rate of error of numerical integration for certain classes of functions with mixed smoothness. We give a Fourier analytic proof of the fact that the symmetrized Fibonacci set Fn′=F n∪(p1,1-p2):(p1,p 2)∈Fn has asymptotically minimal L2 discrepancy. This approach also yields an exact formula for this quantity, which allows us to evaluate the constant in the discrepancy estimates. Numerical computations indicate that these sets have the smallest currently known L 2 discrepancy among two-dimensional point sets. We also introduce quartered Lp discrepancy, which is a modification of the L p discrepancy symmetrized with respect to the center of the unit square. We prove that the Fibonacci set Fn has minimal in the sense of order quartered Lp discrepancy for all p∈(1,∞). This in turn implies that certain two-fold symmetrizations of the Fibonacci set F n are optimal with respect to the standard Lp discrepancy.
AB - We study the Fibonacci sets from the point of view of their quality with respect to discrepancy and numerical integration. Let {bn} n=0 ∞ be the sequence of Fibonacci numbers. The bn-point Fibonacci set Fn⊂[ 0,1]2 is defined as Fn:=(μbn,μbn-1b n)μ=1bn, where x is the fractional part of a number x∈ℝ. It is known that cubature formulas based on the Fibonacci set Fn give optimal rate of error of numerical integration for certain classes of functions with mixed smoothness. We give a Fourier analytic proof of the fact that the symmetrized Fibonacci set Fn′=F n∪(p1,1-p2):(p1,p 2)∈Fn has asymptotically minimal L2 discrepancy. This approach also yields an exact formula for this quantity, which allows us to evaluate the constant in the discrepancy estimates. Numerical computations indicate that these sets have the smallest currently known L 2 discrepancy among two-dimensional point sets. We also introduce quartered Lp discrepancy, which is a modification of the L p discrepancy symmetrized with respect to the center of the unit square. We prove that the Fibonacci set Fn has minimal in the sense of order quartered Lp discrepancy for all p∈(1,∞). This in turn implies that certain two-fold symmetrizations of the Fibonacci set F n are optimal with respect to the standard Lp discrepancy.
KW - Cubature formulas
KW - Discrepancy
KW - Fibonacci numbers
KW - Fourier coefficients
KW - Numerical integration
UR - http://www.scopus.com/inward/record.url?scp=82555164924&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=82555164924&partnerID=8YFLogxK
U2 - 10.1016/j.jco.2011.07.001
DO - 10.1016/j.jco.2011.07.001
M3 - Article
AN - SCOPUS:82555164924
SN - 0885-064X
VL - 28
SP - 18
EP - 36
JO - Journal of Complexity
JF - Journal of Complexity
IS - 1
ER -