On the multiplicative Chung-Diaconis-Graham process

I. D. Shkredov

Sbornik. Mathematics, Tome 214 (2023) no. 6, pp. 878-895

Résumé

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)=\mathrm{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. Bibliography: 34 titles.

Détail

Keywords: Chung-Diaconis-Graham process, mixing time, incidence geometry
Mots-clés : Markov chains, Sidon sets.

Bibliographie

[1] C. Asci, “Generating uniform random vectors”, J. Theoret. Probab., 14:2 (2001), 333–356 | DOI | MR | Zbl

[2] J. Bourgain, “Multilinear exponential sums in prime fields under optimal entropy condition on the sources”, Geom. Funct. Anal., 18:5 (2009), 1477–1502 | DOI | MR | Zbl

[3] J. Bourgain and A. Gamburd, “Uniform expansion bounds for Cayley graphs of $\mathrm{SL}_2(\mathbb {F}_p)$”, Ann. of Math. (2), 167:2 (2008), 625–642 | DOI | MR | Zbl

[4] S. Chatterjee and P. Diaconis, “Speeding up Markov chains with deterministic jumps”, Probab. Theory Related Fields, 178:3–4 (2020), 1193–1214 | DOI | MR | Zbl

[5] Fan Chung, “Laplacians and the Cheeger inequality for directed graphs”, Ann. Comb., 9:1 (2005), 1–19 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[8] J. He, “Markov chains on finite fields with deterministic jumps”, Electron. J. Probab., 27 (2022), 28, 17 pp. | DOI | MR | Zbl

[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. | DOI | MR | Zbl

[10] M. Hildebrand, “A lower bound for the Chung-Diaconis-Graham random process”, Proc. Amer. Math. Soc., 137:4 (2009), 1479–1487 | DOI | MR | Zbl

[11] M. Hildebrand, “Random processes of the form $X_{n+1}=a_n X_n+b_n \pmod p$ where $b_n$ takes on a single value”, Random discrete structures (Minneapolis, MN 1993), IMA Vol. Math. Appl., 76, Springer, New York, 1996, 153–174 | DOI | MR | Zbl

[12] M. Hildebrand, “Random processes of the form $X_{n+1}=a_n X_n+b_n \pmod p$”, Ann. Probab., 21:2 (1993), 710–720 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[15] I. A. Kruglov, “Random sequences of the form $X_{t+1}=a_t X_t+b_t$ modulo $n$ with dependent coefficients $a_t$, $b_t$”, Discrete Math. Appl., 15:2 (2005), 145–151

[16] D. A. Levin and Y. Peres, Markov chains and mixing times, 2nd ed., Amer. Math. Soc., Providence, RI, 2017, xvi+447 pp. | DOI | MR | Zbl

[17] B. Murphy, “Upper and lower bounds for rich lines in grids”, Amer. J. Math., 143:2 (2021), 577–611 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[19] K. O'Bryant, “A complete annotated bibliography of work related to Sidon sequences”, Electron. J. Combin., 2004, Dynamic Surveys, DS11, 39 pp. | DOI | MR | Zbl

[20] O. Roche-Newton and A. Warren, “Additive and multiplicative Sidon sets”, Acta Math. Hungar., 165:2 (2021), 326–336 | DOI | MR | Zbl

[21] M. Rudnev, “On the number of incidences between points and planes in three dimensions”, Combinatorica, 38:1 (2018), 219–254 | DOI | MR | Zbl

[22] M. Rudnev and I. D. Shkredov, “On the growth rate in $\mathrm{SL}_2(\mathbb {F}_p)$, the affine group and sum–product type implications”, Mathematika, 68:3 (2022), 738–783 | DOI | MR

[23] T. Schoen and I. D. Shkredov, “Higher moments of convolutions”, J. Number Theory, 133:5 (2013), 1693–1737 | DOI | MR | Zbl

[24] A. S. Semchenkov, “Maximal subsets free of arithmetic progressions in arbitrary sets”, Math. Notes, 102:3 (2017), 396–402 | DOI | DOI | MR | Zbl

[25] I. D. Shkredov, “Some remarks on the asymmetric sum–product phenomenon”, Mosc. J. Comb. Number Theory, 8:1 (2019), 15–41 | DOI | MR | Zbl

[26] I. D. Shkredov, “On asymptotic formulae in some sum–product questions”, Trans. Moscow Math. Soc., 2018 (2018), 231–281 | DOI | MR | Zbl

[27] I. D. Shkredov, “Modular hyperbolas and bilinear forms of Kloosterman sums”, J. Number Theory, 220 (2021), 182–211 | DOI | MR | Zbl

[28] I. D. Shkredov, “On an application of higher energies to Sidon sets”, Combinatorica, 43 (2023), 329–345 | DOI | MR | Zbl

[29] S. Sidon, “Ein Satz über trigonometrische Polynome und seine Anwendung in der Theorie der Fourier-Reihen”, Math. Ann., 106:1 (1932), 536–539 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[31] E. Szemerédi and W. T. Trotter, Jr., “Extremal problems in discrete geometry”, Combinatorica, 3:3–4 (1983), 381–392 | DOI | MR | Zbl

[32] T. Tao and Van H. Vu, Additive combinatorics, Cambridge Stud. Adv. Math., 105, Cambridge Univ. Press, Cambridge, 2006, xviii+512 pp. | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[34] A. Warren, Additive and multiplicative Sidon sets, Report at CANT–2021 http://www.theoryofnumbers.com/cant/CANT2021-abstracts.pdf