×
Shkredov, I. D.

On the multiplicative Chung-Diaconis-Graham process. (English. Russian original) Zbl 1534.60097

Sb. Math. 214, No. 6, 878-895 (2023); translation from Mat. Sb. 214, No. 6, 136-154 (2023).
Summary: We study the lazy Markov chain on \(\mathbb{F}_p\) defined as follows: \(X_{n+1}=X_n\) with probability \(1/2\) and \(X_{n+1}=f(X_n) \cdot \varepsilon_{n+1} \), where the \(\varepsilon_n\) are random variables distributed uniformly on the set \(\{\gamma, \gamma^{-1}\}\), \(\gamma\) is a primitive root and \(f(x)=x/(x-1)\) or \(f(x)=\text{ind}(x)\). Then we show that the mixing time of \(X_n\) is \(\exp(O(\log p \cdot \log \log \log p/ \log \log p))\). Also, we obtain an application to an additive-combinatorial question concerning a certain Sidon-type family of sets.

MSC:

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
11B13 Additive bases, including sumsets
60B15 Probability measures on groups or semigroups, Fourier transforms, factorization
60G50 Sums of independent random variables; random walks
05B10 Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.)

Keywords:

Markov chains; Chung-Diaconis-Graham process; mixing time; incidence geometry; Sidon sets
Cite Review PDF
Full Text: DOI arXiv MNR

References:

[1] C. Asci, “Generating uniform random vectors”, J. Theoret. Probab. 14:2 (2001), 333-356. · Zbl 1005.65007 · doi:10.1023/A:1011155412481
[2] J. Bourgain, “Multilinear exponential sums in prime fields under optimal entropy condition on the sources”, Geom. Funct. Anal. 18:5 (2009), 1477-1502. · Zbl 1162.11043 · doi:10.1007/s00039-008-0691-6
[3] J. Bourgain and A. Gamburd, “Uniform expansion bounds for Cayley graphs of SL2(Fp)”, Ann. of Math. (2) 167:2 (2008), 625-642. · Zbl 1216.20042 · doi:10.4007/annals.2008.167.625
[4] S. Chatterjee and P. Diaconis, “Speeding up Markov chains with deterministic jumps”, Probab. Theory Related Fields 178:3-4 (2020), 1193-1214. · Zbl 1468.60088 · doi:10.1007/s00440-020-01006-4
[5] Fan Chung, “Laplacians and the Cheeger inequality for directed graphs”, Ann. Comb. 9:1 (2005), 1-19. · Zbl 1059.05070 · doi:10.1007/s00026-005-0237-z
[6] F. R. K. Chung, P. Diaconis and R. L. Graham, “Random walks arising in random number generation”, Ann. Probab. 15:3 (1987), 1148-1165. · Zbl 0622.60016 · doi:10.1214/aop/1176992088
[7] S. Eberhard and P. P. Varjú, “Mixing time of the Chung-Diaconis-Graham random process”, Probab. Theory Related Fields 179:1-2 (2021), 317-344. · Zbl 1478.60201 · doi:10.1007/s00440-020-01009-1
[8] J. He, “Markov chains on finite fields with deterministic jumps”, Electron. J. Probab. 27 (2022), 28, 17 pp. · Zbl 1486.60092 · doi:10.1214/22-EJP757
[9] J. He, Huy Tuan Pham and Max Wenqiang Xu, “Mixing time of fractional random walk on finite fields”, Electron. J. Probab. 27 (2022), 133, 15 pp. · Zbl 1498.60305 · doi:10.1214/22-EJP858
[10] M. Hildebrand, “A lower bound for the Chung-Diaconis-Graham random process”, Proc. Amer. Math. Soc. 137:4 (2009), 1479-1487. · Zbl 1159.60008 · doi:10.1090/S0002-9939-08-09687-1
[11] M. Hildebrand, “Random processes of the form Xn+1 = anXn + bn (mod p) where bn takes on a single value”, Random discrete structures (Minneapolis, MN 1993), IMA Vol. Math. Appl., vol. 76, Springer, New York 1996, pp. 153-174. · Zbl 0840.60058 · doi:10.1007/978-1-4612-0719-1_10
[12] M. Hildebrand, “Random processes of the form Xn+1 = anXn + bn (mod p)”, Ann. Probab. 21:2 (1993), 710-720. · Zbl 0776.60012 · doi:10.1214/aop/1176989264
[13] C. Pohoata, Sidon sets and sum-product phenomena, https://pohoatza.wordpress. com/2021/01/23/sidon-sets-and-sum-product-phenomena/.
[14] J. Komlós, M. Sulyok and E. Szemerédi, “Linear problems in combinatorial number theory”, Acta Math. Acad. Sci. Hungar. 26:1-2 (1975), 113-121. · Zbl 0303.10058 · doi:10.1007/BF01895954
[15] I. A. Kruglov, “Random sequences of the form Xt+1 = atXt + bt modulo n with dependent coefficients at, bt”, Discrete Math. Appl. 15:2 (2005), 145-151. · Zbl 1106.60059
[16] D. A. Levin and Y. Peres, Markov chains and mixing times, 2nd ed., Amer. Math. Soc., Providence, RI 2017, xvi+447 pp. · Zbl 1390.60001 · doi:10.1090/mbk/107
[17] B. Murphy, “Upper and lower bounds for rich lines in grids”, Amer. J. Math. 143:2 (2021), 577-611. · Zbl 1475.52028 · doi:10.1353/ajm.2021.0013
[18] B. Murphy, G. Petridis, O. Roche-Newton, M. Rudnev and I. D. Shkredov, “New results on sum-product type growth over fields”, Mathematika 65:3 (2019), 588-642. · Zbl 1429.11027 · doi:10.1112/S0025579319000044
[19] K. O’Bryant, “A complete annotated bibliography of work related to Sidon sequences”, Electron. J. Combin., 2004, Dynamic Surveys, DS11, 39 pp. · Zbl 1142.11312 · doi:10.37236/32
[20] O. Roche-Newton and A. Warren, “Additive and multiplicative Sidon sets”, Acta Math. Hungar. 165:2 (2021), 326-336. · Zbl 1499.11039 · doi:10.1007/s10474-021-01160-8
[21] M. Rudnev, “On the number of incidences between points and planes in three dimensions”, Combinatorica 38:1 (2018), 219-254. · Zbl 1413.51001 · doi:10.1007/s00493-016-3329-6
[22] M. Rudnev and I. D. Shkredov, “On the growth rate in SL2(Fp), the affine group and sum-product type implications”, Mathematika 68:3 (2022), 738-783. · Zbl 1543.11014 · doi:10.1112/mtk.12120
[23] T. Schoen and I. D. Shkredov, “Higher moments of convolutions”, J. Number Theory 133:5 (2013), 1693-1737. · Zbl 1300.11018 · doi:10.1016/j.jnt.2012.10.010
[24] A. S. Semchenkov, “Maximal subsets free of arithmetic progressions in arbitrary sets”, Math. Notes 102:3 (2017), 396-402. · Zbl 1430.11018 · doi:10.1134/S0001434617090097
[25] I. D. Shkredov, “Some remarks on the asymmetric sum-product phenomenon”, Mosc. J. Comb. Number Theory 8:1 (2019), 15-41. · Zbl 1454.11029 · doi:10.2140/moscow.2019.8.15
[26] I. D. Shkredov, “On asymptotic formulae in some sum-product questions”, Trans. Moscow Math. Soc. 2018 (2018), 231-281. · Zbl 1473.11034 · doi:10.1090/mosc/283
[27] I. D. Shkredov, “Modular hyperbolas and bilinear forms of Kloosterman sums”, J. Number Theory 220 (2021), 182-211. · Zbl 1461.11030 · doi:10.1016/j.jnt.2020.06.014
[28] I. D. Shkredov, “On an application of higher energies to Sidon sets”, Combinatorica 43 (2023), 329-345. · Zbl 07745878 · doi:10.1007/s00493-023-00013-y
[29] S. Sidon, “Ein Satzüber trigonometrische Polynome und seine Anwendung in der Theorie der Fourier-Reihen”, Math. Ann. 106:1 (1932), 536-539. · JFM 58.0268.06 · doi:10.1007/BF01455900
[30] S. Stevens and F. de Zeeuw, “An improved point-line incidence bound over arbitrary fields”, Bull. Lond. Math. Soc. 49:5 (2017), 842-858. · Zbl 1388.51002 · doi:10.1112/blms.12077
[31] E. Szemerédi and W. T. Trotter, Jr., “Extremal problems in discrete geometry”, Combinatorica 3:3-4 (1983), 381-392. · Zbl 0541.05012 · doi:10.1007/BF02579194
[32] T. Tao and Van H. Vu, Additive combinatorics, Cambridge Stud. Adv. Math., vol. 105, Cambridge Univ. Press, Cambridge 2006, xviii+512 pp. · Zbl 1127.11002 · doi:10.1017/CBO9780511755149
[33] L. A. Vinh, “The Szemerédi-Trotter type theorem and the sum-product estimate in finite fields”, European J. Combin. 32:8 (2011), 1177-1181. · Zbl 1253.11015 · doi:10.1016/j.ejc.2011.06.008
[34] A. Warren, Additive and multiplicative Sidon sets, Report at CANT-2021, http://www.theoryofnumbers.com/cant/CANT2021-abstracts.pdf.
[35] Ilya D. Shkredov Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia E-mail: ilya.shkredov@gmail.com
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.