×

Positive-definite functions, exponential sums and the greedy algorithm: a curious phenomenon. (English) Zbl 1456.11138

Summary: We describe a curious dynamical system that results in sequences of real numbers in \([0,1]\) with seemingly remarkable properties. Let the even function \(f:\mathbb{T}\to\mathbb{R}\) satisfy \(\hat{f}(k)\geq c|k|^{-2}\) and define a sequence via \[ x_n =\arg\min\limits_x\sum\limits_{k=1}^{n-1}f(x-x_k). \] Such sequences \((x_n)_{n=1}^\infty\) seem to be astonishingly regularly distributed in various ways (satisfying favorable exponential sum estimates; every interval \(J\subset[0,1]\) contains \(\sim|J|n\) elements). We prove \[ W_2(\mu,\nu)\leq\frac{c}{\sqrt{n}},\text{ where }\mu=\frac{1}{n}\sum_{k=1}^n\delta_{x_k} \] is the empirical distribution, \(\nu=dx\) is the Lebesgue measure and \(W_2(\mu,\nu)\) is the 2-Wasserstein distance between these two. Much stronger results seem to be true and it is an interesting problem to understand this dynamical system better. We obtain optimal results in dimension \(d\geq 3\): using \(G(x,y)\) to denote the Green’s function of the Laplacian on a compact manifold, we show that \[ x_n=\arg\min\limits_{x\in M}\sum_{k=1}^{n-1}G(x,x_k )\text{ satisfies }W_2\left(\frac{1}{n}\sum\limits_{k=1}^n\delta_{x_k},dx\right)\lesssim\frac{1}{n^{1/d}}. \]

MSC:

11K38 Irregularities of distribution, discrepancy
37E05 Dynamical systems involving maps of the interval
42A16 Fourier coefficients, Fourier series of functions with special properties, special Fourier series

References:

[1] Beck, J., A two-dimensional van Aardenne-Ehrenfest theorem in irregularities of distribution, Compos. Math., 72, 3, 269-339 (1989) · Zbl 0691.10041
[2] Beck, J.; Chen, W., Irregularities of Distribution, Cambridge Tracts in Mathematics (1987), Cambridge University Press · Zbl 0617.10039
[3] Beltran, C., A facility location formulation for stable polynomials and elliptic Fekete points, Found. Comput. Math., 15, 1, 125-157 (2015) · Zbl 1315.65051
[4] Beltran, C.; Corral, N.; Criado del Rey, J., Discrete and continuous green energy on compact manifolds, J. Approx. Theory, 237, 160-185 (2019) · Zbl 1402.31005
[5] Betermin, L.; Sandier, E., Renormalized energy and asymptotic expansion of optimal logarithmic energy on the sphere, Constr. Approx., 47, 39-74 (2018) · Zbl 1391.82002
[6] Bilyk, D., Roth’s orthogonal function method in discrepancy theory and some new connections, (Panorama of Discrepancy Theory. Panorama of Discrepancy Theory, Lecture Notes in Math 2107 Springer Verlag (2014)), 71-158 · Zbl 1358.11083
[7] Bilyk, D.; Dai, F.; Steinerberger, S., General and refined montgomery lemmata, Math. Ann. (2020), in press · Zbl 1419.42005
[8] Bilyk, D.; Lacey, M., On the small ball inequality in three dimensions, Duke Math. J., 143, 1, 81-115 (2008) · Zbl 1202.42007
[9] Bilyk, D.; Lacey, M.; Vagharshakyan, A., On the small ball inequality in all dimensions, J. Funct. Anal., 254, 9, 2470-2502 (2008) · Zbl 1214.42024
[10] Chafaï, D.; Hardy, A.; Maïda, M., Concentration for Coulomb gases and Coulomb transport inequalities, J. Funct. Anal., 275, 1447-1483 (2018) · Zbl 1407.82045
[11] Chazelle, B., The Discrepancy Method. Randomness and Complexity (2000), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0960.65149
[12] J. Criado del Rey, On the separation distance of minimal Green energy points on compact Riemannian manifolds, arXiv:1901.00779.
[13] DeVore, R.; Temlyakov, V., Some remarks on greedy algorithms, Adv. Comput. Math., 5, 2-3, 173-187 (1996) · Zbl 0857.65016
[14] Dick, J.; Pillichshammer, F., Digital Nets and Sequences. Discrepancy Theory and Quasi-Monte Carlo Integration (2010), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1282.65012
[15] Drmota, M.; Tichy, R., (Sequences, Discrepancies and Applications. Sequences, Discrepancies and Applications, Lecture Notes in Mathematics, vol. 1651 (1997), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0877.11043
[16] Erdős, P.; Turán, P., On a problem in the theory of uniform distribution, I. Nederl. Akad. Wetensch., 51, 1146-1154 (1948) · Zbl 0031.25402
[17] Erdös, P.; Turán, P., On a problem in the theory of uniform distribution, II. Nederl. Akad. Wetensch., 51, 1262-1269 (1948) · Zbl 0032.01601
[18] García-Zelada, D., Concentration for coulomb gases on compact manifolds 24 (12), 18 (2019) · Zbl 1412.60011
[19] C. Graham, Irregularity of distribution in Wasserstein distance, arXiv:1910.14181.
[20] Hlawka, E., Funktionen von beschränkter Variation in der Theorie der Gleichverteilung, Ann. Mat. Pura Appl. (4), 54, 325-333 (1961) · Zbl 0103.27604
[21] S. Kakutani, A problem of equidistribution on the unit interval \([ 0 , 1 ]\), in: Measure Theory: Proceedings of the Conference held at Oberwolfach 15-21 June 1975, pp. 369-375. · Zbl 0363.60023
[22] Kuipers, L.; Niederreiter, H., (Uniform Distribution of Sequences. Uniform Distribution of Sequences, Pure and Applied Mathematics (1974), Wiley-Interscience: Wiley-Interscience New York-London-Sydney) · Zbl 0281.10001
[23] Larcher, G., On the star discrepancy of sequences in the unit interval, J. Complexity, 31, 474-485 (2015) · Zbl 1387.11066
[24] Larcher, G.; Puchhammer, F., An improved bound for the star discrepancy of sequences in the unit interval, Unif. Distrib. Theory, 11, 1, 1-14 (2016) · Zbl 1455.11110
[25] Lev, N.; Ortega-Cerdà, J., Equidistribution estimates for Fekete points on complex manifolds, J. Eur. Math. Soc., 18, 2, 425-464 (2016) · Zbl 1359.32028
[26] J. Marzo, A. Mas, Discrepancy of minimal Riesz energy points, arXiv:1907.04814.
[27] F. Pausinger, Greedy energy minimization can count in binary: point charges and the van der Corput sequence, arXiv:1905.09641.
[28] Peyre, R., Comparison between \(W_2\) distance and \(\dot{H}^{- 1}\) norm, and Localization of Wasserstein distance, ESAIM Control Optim. Calc. Var., 24, 1489-1501 (2018), in press · Zbl 1415.49031
[29] Proinov, P. D., On irregularities of distribution, C. R. Acad. Bulg. Sci., 39, 9, 31-34 (1986) · Zbl 0616.10042
[30] Proinov, P. D.; Grozdanov, V., On the diaphony of the van der Corput-Halton sequence, J. Number Theory, 30, 1, 94-104 (1988) · Zbl 0654.10050
[31] Roth, K. F., On irregularities of distribution, Mathematika, 1, 73-79 (1954) · Zbl 0057.28604
[32] Santambrogio, F., Optimal Transport for Applied Mathematicians. Calculus of Variations, PDEs, and Modeling, Progress in Nonlinear Differential Equations and their Applications (2015), Birkhauser/Springer: Birkhauser/Springer Cham · Zbl 1401.49002
[33] Schmidt, W., Irregularities of distribution. VII, Acta Arith., 21, 45-50 (1972) · Zbl 0244.10035
[34] S. Steinerberger, Dynamically Defined Sequences with Small Discrepancy, arXiv:1902.03269. · Zbl 1471.11222
[35] S. Steinerberger, Wasserstein Distance, Fourier Series and Applications, arXiv:1803.08011.
[36] S. Steinerberger, A Wasserstein Inequality and Minimal Green Energy on Compact Manifolds, arXiv:1907.09023.
[37] Steinerberger, S., A nonlocal functional promoting low-discrepancy point sets, J. Complexity (2020), in press
[38] V. Temlyakov, Numerical integration without smoothness assumption, arXiv:2003.14331.
[39] Temlyakov, V., Cubature formulas, discrepancy, and nonlinear approximation, J. Complexity, 19, 352-391 (2003) · Zbl 1031.41016
[40] Temlyakov, V., Greedy approximation, Acta Numer., 17, 235-409 (2008) · Zbl 1178.65050
[41] Temlyakov, V., (Greedy Approximation. Greedy Approximation, Cambridge Monographs on Applied and Computational Mathematics, vol. 20 (2011), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 1279.41001
[42] Temlyakov, V., Connections between numerical integration, discrepancy, dispersion, and universal discretization, SMAI J. Comput. Math., S5, 185-209 (2019) · Zbl 1516.65019
[43] 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) · Zbl 0060.13002
[44] Vasershtein, L. N., Markov processes on a countable product space, describing large systems of automata, Problemy Peredachi Informatsii, 5, 3, 64-73 (1969)
[45] Villani, C., Topics in Optimal Transportation, Graduate Studies in Mathematics (2003), American Mathematical Society · Zbl 1106.90001
[46] Weyl, H., Ueber die Gleichverteilung von Zahlen mod. Eins, Math. Ann., 77, 3, 313-352 (1916) · JFM 46.0278.06
[47] Zinterhof, P., Über einige Abschätzungen bei der Approximation von Funktionen mit Gleichverteilungsmethoden, Österreich. Akad. Wiss. Math.-Naturwiss. Kl. S.-B. II, 185, 121-132 (1976) · Zbl 0356.65007
[48] Zinterhof, P.; Stegbuchner, H., Trigonometrische Approximation mit Gleichverteilungsmethoden, Stud. Sci. Math. Hung., 13, 273-289 (1978) · Zbl 0421.42001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.