On the multiplicative Chung–Diaconis–Graham process

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

We study the lazy Markov chain on Fp">Fp defined as follows: Xn+1=Xn">Xn+1=Xn with probability 1/2">1/2 and Xn+1=f(Xn)⋅εn+1">Xn+1=f(Xn)⋅εn+1, where the εn">εn are random variables distributed uniformly on the set {γ,γ−1}">{γ,γ−1}, γ">γ is a primitive root and f(x)=x/(x−1)">f(x)=x/(x−1) or f(x)=ind(x)">f(x)=ind(x). Then we show that the mixing time of Xn">Xn is exp⁡(O(log⁡p⋅log⁡log⁡log⁡p/log⁡log⁡p))">exp⁡(O(log⁡p⋅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.

About the authors

Ilya Dmitrievich Shkredov

Steklov Mathematical Institute of Russian Academy of Sciences

Author for correspondence.
Email: ilya.shkredov@gmail.com
Doctor of physico-mathematical sciences, Professor

References

  1. C. Asci, “Generating uniform random vectors”, J. Theoret. Probab., 14:2 (2001), 333–356
  2. J. Bourgain, “Multilinear exponential sums in prime fields under optimal entropy condition on the sources”, Geom. Funct. Anal., 18:5 (2009), 1477–1502
  3. J. Bourgain, A. Gamburd, “Uniform expansion bounds for Cayley graphs of $mathrm{SL}_2(mathbb {F}_p)$”, Ann. of Math. (2), 167:2 (2008), 625–642
  4. S. Chatterjee, P. Diaconis, “Speeding up Markov chains with deterministic jumps”, Probab. Theory Related Fields, 178:3-4 (2020), 1193–1214
  5. Fan Chung, “Laplacians and the Cheeger inequality for directed graphs”, Ann. Comb., 9:1 (2005), 1–19
  6. F. R. K. Chung, P. Diaconis, R. L. Graham, “Random walks arising in random number generation”, Ann. Probab., 15:3 (1987), 1148–1165
  7. S. Eberhard, P. P. Varju, “Mixing time of the Chung–Diaconis–Graham random process”, Probab. Theory Related Fields, 179:1-2 (2021), 317–344
  8. J. He, “Markov chains on finite fields with deterministic jumps”, Electron. J. Probab., 27 (2022), 28, 17 pp.
  9. J. He, Huy Tuan Pham, Max Wenqiang Xu, “Mixing time of fractional random walk on finite fields”, Electron. J. Probab., 27 (2022), 133, 15 pp.
  10. M. Hildebrand, “A lower bound for the Chung–Diaconis–Graham random process”, Proc. Amer. Math. Soc., 137:4 (2009), 1479–1487
  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
  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
  13. C. Pohoata, Sidon sets and sum–product phenomena
  14. J. Komlos, M. Sulyok, E. Szemeredi, “Linear problems in combinatorial number theory”, Acta Math. Acad. Sci. Hungar., 26:1-2 (1975), 113–121
  15. И. А. Круглов, “Случайные последовательности вида $X_{t+1}=a_t X_t+b_t pmod n$ с зависимыми коэффициентами $a_t$, $b_t$”, Дискрет. матем., 17:2 (2005), 49–55
  16. D. A. Levin, Y. Peres, Markov chains and mixing times, 2nd ed., Amer. Math. Soc., Providence, RI, 2017, xvi+447 pp.
  17. B. Murphy, “Upper and lower bounds for rich lines in grids”, Amer. J. Math., 143:2 (2021), 577–611
  18. B. Murphy, G. Petridis, O. Roche-Newton, M. Rudnev, I. D. Shkredov, “New results on sum–product type growth over fields”, Mathematika, 65:3 (2019), 588–642
  19. K. O'Bryant, “A complete annotated bibliography of work related to Sidon sequences”, Electron. J. Combin., 2004, Dynamic Surveys, DS11, 39 pp.
  20. O. Roche-Newton, A. Warren, “Additive and multiplicative Sidon sets”, Acta Math. Hungar., 165:2 (2021), 326–336
  21. M. Rudnev, “On the number of incidences between points and planes in three dimensions”, Combinatorica, 38:1 (2018), 219–254
  22. M. Rudnev, 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
  23. T. Schoen, I. D. Shkredov, “Higher moments of convolutions”, J. Number Theory, 133:5 (2013), 1693–1737
  24. А. С. Семченков, “Максимальные подмножества без арифметических прогрессий в произвольных множествах”, Матем. заметки, 102:3 (2017), 436–444
  25. I. D. Shkredov, “Some remarks on the asymmetric sum–product phenomenon”, Mosc. J. Comb. Number Theory, 8:1 (2019), 15–41
  26. И. Д. Шкредов, “Об асимптотических формулах в некоторых вопросах теории сумм произведений”, Тр. ММО, 79, № 2, МЦНМО, М., 2018, 271–334
  27. I. D. Shkredov, “Modular hyperbolas and bilinear forms of Kloosterman sums”, J. Number Theory, 220 (2021), 182–211
  28. I. D. Shkredov, “On an application of higher energies to Sidon sets”, Combinatorica, 2023, Publ. online
  29. S. Sidon, “Ein Satz über trigonometrische Polynome und seine Anwendung in der Theorie der Fourier-Reihen”, Math. Ann., 106:1 (1932), 536–539
  30. S. Stevens, F. de Zeeuw, “An improved point-line incidence bound over arbitrary fields”, Bull. Lond. Math. Soc., 49:5 (2017), 842–858
  31. E. Szemeredi, W. T. Trotter, Jr., “Extremal problems in discrete geometry”, Combinatorica, 3:3-4 (1983), 381–392
  32. T. Tao, Van H. Vu, Additive combinatorics, Cambridge Stud. Adv. Math., 105, Cambridge Univ. Press, Cambridge, 2006, xviii+512 pp.
  33. L. A. Vinh, “The Szemeredi–Trotter type theorem and the sum–product estimate in finite fields”, European J. Combin., 32:8 (2011), 1177–1181
  34. A. Warren, Additive and multiplicative Sidon sets, Report at CANT–2021

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2023 Shkredov I.D.

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».