Generating an equidistributed net on a sphere using random rotations. (English) Zbl 07457128

Summary: We develop a randomized algorithm (that succeeds with high probability) for generating an \(\varepsilon \)-net in a sphere of dimension \(n\). The basic scheme is to pick an alphabet consisting of \(O (n\ln (1/\varepsilon )+\ln (1/\delta ))\) random rotations, form all possible words of length \(O (n\ln (1/\varepsilon ))\) from this alphabet, and require these words act on a fixed point. We show the set of points so generated is equidistributed at a scale of \(\varepsilon \).


68W20 Randomized algorithms
52C10 Erdős problems and related topics of discrete geometry
Full Text: DOI arXiv


[1] Ahlswede, R., Winter, A.: Strong converse for identification via quantum channels. IEEE Trans. Inform. Theory 48(3), 569-579 (2002) · Zbl 1071.94530
[2] Alon, N.; Roichman, Y., Random Cayley graphs and expanders, Random Struct. Algorithms, 5, 2, 271-284 (1994) · Zbl 0798.05048
[3] Benoist, Y.; de Saxcé, N., A spectral gap theorem in simple Lie groups, Invent. Math., 205, 2, 337-361 (2016) · Zbl 1357.22003
[4] Bourgain, J.: On random walks in large compact Lie groups. In: Geometric Aspects of Functional Analysis. Lecture Notes in Mathematics, vol. 2169, pp. 55-63. Springer, Cham (2017) · Zbl 1370.60085
[5] Bourgain, J.; Gamburd, A., On the spectral gap for finitely-generated subgroups of SU(2), Invent. Math., 171, 1, 83-121 (2008) · Zbl 1135.22010
[6] Bourgain, J.; Gamburd, A., A spectral gap theorem in SU \((d)\), J. Eur. Math. Soc., 14, 5, 1455-1511 (2012) · Zbl 1254.43010
[7] Boyvalenkov, PG; Dragnev, PD; Hardin, DP; Saff, EB; Stoyanova, MM, Universal upper and lower bounds on energy of spherical designs, Dolomit. Res. Notes Approx., 8, special issue, 51-65 (2015) · Zbl 1370.31003
[8] Carne, T.K.: Brownian motion and stereographic projection. Ann. Inst. H. Poincaré Probab. Statist. 21(2), 187-196 (1985) · Zbl 0566.60080
[9] Gray, A.: The volume of a small geodesic ball of a Riemannian manifold. Michigan Math. J. 20(4), 329-344 (1974) · Zbl 0279.58003
[10] Hastings, MB; Harrow, AW, Classical and quantum tensor product expanders, Quantum Inf. Comput., 9, 3-4, 336-360 (2009) · Zbl 1171.81329
[11] Kantorovich, L.V., Rubinshtein, G.Sh.: On a space of completely additive functions. Vestnik Leningrad. Univ. 13(7), 52-59 (1958). (in Russian) · Zbl 0082.11001
[12] Landau, Z., Russell, A.: Random Cayley graphs are expanders: a simple proof of the Alon-Roichman theorem. Electron. J. Comb. 11(1), # R62 (2004) · Zbl 1053.05060
[13] Morimoto, M.: Analytic Functionals on the Sphere. Translations of Mathematical Monographs, vol. 178. American Mathematical Society, Providence (1998) · Zbl 0922.46040
[14] Narayanan, H.: On the distribution of random words in a compact Lie group. Sém. Lothar. Comb. 84B, # 9 (2020) · Zbl 1443.22011
[15] Nowak, A., Sjögren, P., Szarek, T.Z.: Sharp estimates of the spherical heat kernel. J. Math. Pures Appl. 129, 23-33 (2019) · Zbl 1428.35150
[16] Villani, C.: Optimal Transport. Grundlehren der Mathematischen Wissenschaften, vol. 338. Springer, Berlin (2009) · Zbl 1156.53003
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.