# On multiplicative Chung–Diaconis–Graham process ††This work is supported by
the Russian Science Foundation under grant 19–11–00001.

Shkredov I.D

Annotation.

We study the lazy Markov chain on $\mathbb{F}_{p}$ defined as $X_{n+1}=X_{n}$
with probability $1/2$ and $X_{n+1}=f(X_{n})\cdot\varepsilon_{n+1}$, where
$\varepsilon_{n}$ are random variables distributed uniformly on
$\\{\gamma,\gamma^{-1}\\}$, $\gamma$ is a primitive root and
$f(x)=\frac{x}{x-1}$ or $f(x)=\mathrm{ind}(x)$. Then we show that the mixing
time of $X_{n}$ is $\exp(O(\log p/\log\log p))$. Also, we obtain an
application to an additive–combinatorial question concerning a certain
Sidon–type family of sets.

##  1 Introduction

The Chung–Diaconis–Graham process [5] is the random walk on $\mathbb{F}_{p}$
(or more generally on $\mathbb{Z}/n\mathbb{Z}$ for composite $n$) defined as

$X_{j+1}=aX_{j}+\varepsilon_{j+1}\,,$ (1)

where $a\in\mathbb{F}_{p}^{*}$ is a fixed residue and the random variables
$\varepsilon_{j}$ are independent and identically distributed (in the original
paper [5] the variables $\varepsilon_{j}$ were distributed uniformly on
$\\{-1,0,1\\}$ and $a=2$). This process was studied extensively, see papers
[3], [5]—[9] and so on. In our article we are interested in the following
characteristic of $X_{n}$, which is called the mixing time. The definition is

$t_{mix}(\varepsilon):=\inf\left\\{n~{}:~{}\max_{A\subseteq\mathbb{F}_{p}}\left|\mathrm{P}(X_{n}\in
A)-\frac{|A|}{p}\right|\leq\varepsilon\right\\}\,.$

Usually one takes a concrete value of the parameter $\varepsilon$, e.g.,
$\varepsilon=1/4$ and below we will say about $t_{mix}:=t_{mix}(1/4)$. Simple
random walk on $\mathbb{F}_{p}$ has the mixing time $t_{mix}$ of order
$p^{2}$, see [15] and it was shown in [5] (also, see recent paper [6]) that
the mixing time of process (1) is at most $O(\log p\cdot\log\log p)$. Hence
the Chung–Diaconis–Graham process gives an example of a speedup phenomenon,
i.e., a phenomenon of increasing the time of the convergence. In [7] it was
studied a more general non–linear version of the Chung–Diaconis–Graham
process, defined as

$X_{j+1}=f(X_{j})+\varepsilon_{j+1}\,,$ (2)

where $f$ is a bijection on $\mathbb{F}_{p}$. In particular, it was proved
that for rational functions of bounded degree (defined correctly at poles, see
[7]) the mixing time is

$t_{mix}(1/4)=O(p^{1+\varepsilon})\,,\quad\quad\quad\forall\varepsilon>0\,.$
(3)

Perhaps, the right answer for process (2) is $t_{mix}=O(\log p)$ but it was
obtained in the only case $f(x)=1/x$ for $x\neq 0$ and $f(0)=0$, see [8]. The
proof is based on ${\rm SL}_{2}(\mathbb{F}_{p})$–actions methods from paper
[2]. In [3] it was asked whether other explicit examples of Markov chains with
low mixing time could be provided.

Our paper is devoted to a multiplicative form of Chung–Diaconis–Graham
process. Multiplicative variants of the process were studied in [1], [10],
[11], [14] and in other papers. Consider the family of functions

$f^{\alpha,\beta}_{*}(x)=\frac{x}{\alpha x+\beta}\,,$ (4)

where $\alpha,\beta\neq 0$. Most of our results below do not depend on
$\alpha,\beta$, so we will not write these parameters in such cases. In
Theorems 1, 12 we need $f^{\alpha,\beta}_{*}(x)$ be a bijection, so we put
$f^{\alpha,\beta}_{*}(-\beta/\alpha):=1/\alpha$. In turn Theorems 1, 12 not
depend on a particular choice of $(\alpha,\beta)$ and one can consider
$\alpha=1$, $\beta=-1$, say, and write $f_{*}(x):=f^{1,-1}_{*}(x)$. Let us
formulate a particular case of our main result.

###### Theorem 1

Let $p$ be a prime number and $\gamma\in\mathbb{F}_{p}^{*}$ be a primitive
root. Also, let $\varepsilon_{j}$ be the random variables distributed
uniformly on $\\{\gamma,\gamma^{-1}\\}$. Consider the lazy Markov chain $0\neq
X_{0},X_{1},\dots,X_{n},\dots$ defined by

$X_{j+1}=\left\\{\begin{array}[]{ll}f_{*}\left(X_{j}\right)\cdot\varepsilon_{j+1}&\text{
with probability }1/2\,,\\\ X_{j}&\text{ with probability
}1/2\,.\end{array}\right.$

Then for any $c>0$ and any $n=c\exp(\log p/\log\log p)$ one has

$\|P_{n}-U\|:=\frac{1}{2}\max_{A\subseteq\mathbb{F}^{*}_{p}}\left|\mathrm{P}(X_{n}\in
A)-\frac{|A|}{p-1}\right|\leqslant e^{-O(c)}\,.$

The same is true for the chain
$X_{j+1}=f_{*}\left(X_{j}\right)\cdot\varepsilon_{j+1}$, where
$\varepsilon_{j}$ denote the random variables distributed uniformly on
$\\{1,\gamma^{-1},\gamma\\}$.

In other words, the mixing time of our Markov chain is $\exp(O(\log p/\log\log
p))$. By a similar method we obtain the same bound for another chain with
$f_{*}(x)=\mathrm{ind}(x)$ and for the chain of form (2) with $f(x)=\exp(x)$,
see Theorem 15 and formulae (27), (28) below. As a byproduct we show that in
the case $f(x)=x^{2}$ and $p\equiv 3\pmod{4}$ the mixing time of (2) is,
actually, $O(p\log p)$, see Remark 14.

Our approach is not analytical as in [7] but it uses some methods from
Additive Combinatorics and Incidence Geometry. In particular, we apply some
results on growth in the affine group ${\rm Aff}(\mathbb{F}_{p})$. The core of
our article has much more in common with papers [2], [25] than with [7] but we
extensively use the general line of the proof from this paper. From
additive–combinatorial point of view the main innovation is a series of
asymptotic formulae for the incidences of points and lines, which were
obtained via the action of ${\rm Aff}(\mathbb{F}_{p})$, see the beginning of
section 3. The author hopes that such formulae are interesting in its own
right. It is well–known see, e.g., [2], [17], [18], [21], [24], [25], [26],
[28] that Incidence Geometry and the sum–product phenomenon sometimes work
better than classical analytical methods and that is why it is possible to
break the square–root barrier, which corresponds to natural bound (3) (for
details see Theorem 13 and the proofs of Theorems 12, 15).

It turns out that the same method is applicable to a purely
additive–combinatorial question on Sidon sets. Sidon sets is a classical
subject of Combinatorial Number Theory, see, e.g., survey [19]. Recall that a
subset $S$ of an abelian group ${\mathbf{G}}$ with the group operation $*$ is
called $g$–Sidon set if for any $z\neq 1$ the equation $z=x*y^{-1}$, where
$x,y\in S$ has at most $g$ solutions. If $g=1$, then we arrive to the
classical definition of Sidon sets [27]. Having an arbitrary set
$A\subseteq{\mathbf{G}}$, we write $\mathsf{Sid}^{*}(A)$ for size of the
maximal (by cardinality) Sidon subset of the set $A$. It is known [13] (also,
see [22]) that for any subset $A$ of our abelian group ${\mathbf{G}}$ the
following estimate takes place

$\mathsf{Sid}^{*}(A)\gg\sqrt{|A|}$

and Klurman and Pohoata [12] asked about possibility to improve the last
bound, having two different operations on a ring ${\mathbf{G}}$. In [26] the
author obtains

###### Theorem 2

Let $A\subseteq\mathbb{F}$ be a set, where $\mathbb{F}={\mathbb{R}}$ or
$\mathbb{F}=\mathbb{F}_{p}$ (in the prime field case suppose, in addition,
that $|A|<\sqrt{p}$, say). Then there are some absolute constants $c>0$,
$K\geqslant 1$ such that

$\max\\{\mathsf{Sid}^{+}_{K}(A),\mathsf{Sid}_{K}^{\times}(A)\\}\gg|A|^{1/2+c}\,.$
(5)

On upper bounds for (5), see [20] and [26]. Notice that
$\mathsf{Sid}_{K}^{\times}(A)=\mathsf{Sid}_{K}^{+}(\log(A))$ and
$\mathsf{Sid}_{K}^{+}(A)=\mathsf{Sid}_{K}^{\times}(\exp(A))$ for
$A\subseteq{\mathbb{R}}^{+}$, say. Hence it is possible to rewrite bound (5)
in terms of the only operation. We now consider a general question, which was
mentioned by A. Warren during CANT–2021 conference [32].

Problem. Let $f,g$ be some ‘nice’ (say, convex or concave) functions. Is it
true that for any set $A\subset{\mathbb{R}}^{+}$, say, one has

$\max\\{\mathsf{Sid}^{+}_{K}(A),\mathsf{Sid}_{K}^{+}(f(A))\\}\,,\quad\quad\max\\{\mathsf{Sid}^{\times}_{K}(A),\mathsf{Sid}_{K}^{\times}(g(A))\\}\gg|A|^{1/2+c}\,?$

Here $c>0$, $K\geqslant 1$ are some absolute constants. What can be said for
$K$ exactly equals one and for a certain $c>0$?

In this paper we obtain an affirmative answer in the case of $g(x)=x+1$ and
$f(x)=\exp(x)$, where in the case of $\mathbb{F}_{p}$ the latter function is
defined as $\exp(x):=g^{x}$ and $g$ is a fixed primitive root.

###### Theorem 3

Let $A\subseteq\mathbb{F}$ be a set, where $\mathbb{F}={\mathbb{R}}$ or
$\mathbb{F}=\mathbb{F}_{p}$ (in the prime field case suppose, in addition,
that $|A|<\sqrt{p}$). Then there are some absolute constants $c>0$,
$K\geqslant 1$ such that

$\max\\{\mathsf{Sid}^{\times}_{K}(A),\mathsf{Sid}_{K}^{\times}(A+1)\\}\gg|A|^{1/2+c}\,,$
(6)

and

$\max\\{\mathsf{Sid}^{+}_{K}(A),\mathsf{Sid}_{K}^{+}(\exp(A))\\}\gg|A|^{1/2+c}\,,$
(7)

On the other hand, for any integer $k\geqslant 1$ there is
$A\subseteq\mathbb{F}$ with

$\max\\{\mathsf{Sid}^{\times}_{k}(A),\mathsf{Sid}^{\times}_{k}(A+1)\\}\ll
k^{1/2}|A|^{3/4}\,.$ (8)

We thank Jimmy He for very useful discussions and valuable suggestions.

##  2 Definitions and preliminaries

By ${\mathbf{G}}$ we denote an abelian group. Sometimes we underline the group
operation writing $+$ or $\times$ in the considered quantities (as the energy,
the representation function and so on, see below). Let $\mathbb{F}$ be the
field ${\mathbb{R}}$ or $\mathbb{F}=\mathbb{F}_{p}=\mathbb{Z}/p\mathbb{Z}$ for
a prime $p$. Let $\mathbb{F}^{*}=\mathbb{F}\setminus\\{0\\}$.

We use the same capital letter to denote set $A\subseteq\mathbb{F}$ and its
characteristic function $A:\mathbb{F}\to\\{0,1\\}$. Given two sets
$A,B\subset{\mathbf{G}}$, define the sumset of $A$ and $B$ as

$A+B:=\\{a+b~{}:~{}a\in{A},\,b\in{B}\\}\,.$

In a similar way we define the difference sets and higher sumsets, e.g.,
$2A-A$ is $A+A-A$. We write $\dotplus$ for a direct sum, i.e., $|A\dotplus
B|=|A||B|$. For an abelian group ${\mathbf{G}}$ the Plünnecke–Ruzsa inequality
(see, e.g., [30]) holds stating

$|nA-mA|\leqslant\left(\frac{|A+A|}{|A|}\right)^{n+m}\cdot|A|\,,$ (9)

where $n,m$ are any positive integers. It follows from a more general
inequality contained in [16] that for arbitrary sets
$A,B,C\subseteq{\mathbf{G}}$ one has

$|B+C+X|\leqslant\frac{|B+X|}{|X|}\cdot|C+X|\,,$ (10)

where $X\subseteq A$ minimize the quantity $|B+X|/|X|$. We use representation
function notations like $r_{A+B}(x)$ or $r_{A-B}(x)$ and so on, which counts
the number of ways $x\in{\mathbf{G}}$ can be expressed as a sum $a+b$ or $a-b$
with $a\in A$, $b\in B$, respectively. For example, $|A|=r_{A-A}(0)$.

For any two sets $A,B\subseteq{\mathbf{G}}$ the additive energy of $A$ and $B$
is defined by

$\mathsf{E}(A,B)=\mathsf{E}^{+}(A,B)=|\\{(a_{1},a_{2},b_{1},b_{2})\in A\times
A\times B\times B~{}:~{}a_{1}-b_{1}=a_{2}-b_{2}\\}|\,.$

If $A=B$, then we simply write $\mathsf{E}(A)$ for $\mathsf{E}(A,A)$. More
generally, for sets (functions) $A_{1},\dots,A_{2k}$ belonging an arbitrary
(noncommutative) group ${\mathbf{G}}$ and $k\geqslant 2$ define the energy
$\mathsf{T}_{k}(A_{1},\dots,A_{2k})$ as

$\mathsf{T}_{k}(A_{1},\dots,A_{2k})=$ $=|\\{(a_{1},\dots,a_{2k})\in
A_{1}\times\dots\times A_{2k}~{}:~{}a_{1}a^{-1}_{2}\dots
a_{k-1}a^{-1}_{k}=a_{k+1}a^{-1}_{k+2}\dots a_{2k-1}a^{-1}_{2k}\\}|\,.$ (11)

In the abelian case put for $k\geqslant 2$

$\mathsf{E}^{+}_{k}(A)=\sum_{x}r^{k}_{A-A}(x)=\sum_{\alpha_{1},\dots,\alpha_{k-1}}|A\cap(A+\alpha_{1})\cap\dots\cap(A+\alpha_{k-1})|^{2}\,.$
(12)

Clearly, $|A|^{k}\leqslant\mathsf{E}^{+}_{k}(A)\leqslant|A|^{k+1}$. Also, we
write $\hat{\mathsf{E}}^{+}_{k}(A)=\sum_{x}r^{k}_{A+A}(x)$.

By $\mathrm{ord}(x)$ denote the multiplicative order of an element of
$x\in\mathbb{F}^{*}_{p}$ and let $\mathrm{ind}(x)$ is defined as
$x=g^{\mathrm{ind}(x)}$, where $g$ is a fixed primitive root of
$\mathbb{F}_{p}^{*}$. It is convenient for us to think that the function
$\mathrm{ind}(x)$ takes values from $1$ to $p-1$ and hence $\mathrm{ind}(x)$
is defined on $\mathbb{F}_{p}^{*}$. In a similar way, we denote by
$\exp(x):\mathbb{F}^{*}_{p}\to\mathbb{F}_{p}^{*}$ the function
$\exp(x)=g^{x}$, where $x\in\mathbb{F}^{*}_{p}$. Let ${\rm Aff}(\mathbb{F})$
be the group of transformations $x\to ax+b$, where $a\in\mathbb{F}^{*}$,
$b\in\mathbb{F}$. Sometimes we write $(a,b)\in{\rm Aff}(\mathbb{F})$ for the
map $x\to ax+b$.

The signs $\ll$ and $\gg$ are the usual Vinogradov symbols. When the constants
in the signs depend on a parameter $M$, we write $\ll_{M}$ and $\gg_{M}$. All
logarithms are to base $2$. If we have a set $A$, then we will write
$a\lesssim b$ or $b\gtrsim a$ if $a=O(b\cdot\log^{c}|A|)$, $c>0$. Let us
denote by $[n]$ the set $\\{1,2,\dots,n\\}$.

We now mention several useful results, which we will appeal in the text. We
start with a result from [25].

###### Lemma 4

Let $f_{1},\dots,f_{2k}:{\mathbf{G}}\to\mathbb{C}$ be any functions. Then

$\mathsf{T}^{2k}_{k}(f_{1},\dots,f_{2k})\leqslant\prod_{j=1}^{2k}\mathsf{T}_{k}(f_{j})\,,$
(13)

and $\|f\|:=\mathsf{T}_{k}(f)^{1/2k}\geqslant\|f\|_{2k}$, $k\geqslant 2$ is a
norm of a function $f:{\mathbf{G}}\to\mathbb{C}$.

The next result on collinear quadruples $\mathsf{Q}(A)$ was proved in [18]. We
rewrite the asymptotic formula for $\mathsf{Q}(A)$ in the following convenient
form.

###### Lemma 5

Let $A\subseteq\mathbb{F}_{p}$ be a set and $f_{A}(x)=A(x)-|A|/p$. Then

$\sum_{l\in{\rm
Aff}(\mathbb{F}_{p})}\left|\sum_{x}f_{A}(x)f_{A}(lx)\right|^{4}\ll|A|^{5}\log|A|\,,$

where the summation over $l$ in the last formula is taken over all affine
transformations.

Finally, we need a simplified version of [23, Theorem 5].

###### Theorem 6

Let $A,B\subseteq\mathbb{F}_{p}$ be sets, $|AB|\leqslant M|A|$, $k\geqslant
2$, and $|B|\gtrsim_{k}M^{2^{k+1}}$. Then

$\mathsf{T}^{+}_{2^{k}}(A)\lesssim_{k}M^{2^{k+1}}\left(\frac{|A|^{2^{k+1}}}{p}+|A|^{2^{k+1}-1}\cdot|B|^{-\frac{k-1}{2}}\right)\,.$
(14)

##  3 The proof of the main result

We start with our counting Proposition 16. Let
$\mathcal{P},\mathcal{L}\subseteq\mathbb{F}_{p}\times\mathbb{F}_{p}$ be a set
of points and a set of lines, correspondingly. The number of incidences
between $\mathcal{P}$ and $\mathcal{L}$ is

$\mathcal{I}(\mathcal{P},\mathcal{L}):=|\\{(q,l)\in\mathcal{P}\times\mathcal{L}:\,q\in
l\\}|\,.$ (15)

###### Proposition 7

Let $A,B\subseteq\mathbb{F}_{p}$ be sets and $\mathcal{L}$ be a set of affine
transformations. Then for any positive integer $k$ one has

${\cal I}(A\times
B,\mathcal{L})-\frac{|A||B||\mathcal{L}|}{p}\ll\sqrt{|A||B||\mathcal{L}|}\cdot(\mathsf{T}_{2^{k}}(\mathcal{L})|A|\log|A|)^{1/2^{k+2}}\,.$
(16)

P r o o f. We have

${\cal I}(A\times B,\mathcal{L})=\frac{|A||B||\mathcal{L}|}{p}+\sum_{x\in
B}\sum_{l\in\mathcal{L}}f_{A}(lx)=\frac{|A||B||\mathcal{L}|}{p}+\sigma\,.$

To estimate the error term $\sigma$ we use the Hölder inequality several times
as in [17], [21] and obtain

$\sigma^{2}\leqslant|B|\sum_{h}r_{\mathcal{L}^{-1}\mathcal{L}}(h)\sum_{x}f_{A}(x)f_{A}(hx)\,,$

and further

$\sigma^{2^{k}}\leqslant|B|^{2^{k-1}}|A|^{2^{k-1}-1}\sum_{h}r_{(\mathcal{L}^{-1}\mathcal{L})^{2^{k-1}}}(h)\sum_{x}f_{A}(x)f_{A}(hx)\,.$

Finally, applying Lemma 5 and the Hölder inequality one more time, we derive

$\sigma^{2^{k+2}}\ll|B|^{2^{k+1}}|A|^{2^{k+1}-4}\left(\sum_{h}r^{4/3}_{(\mathcal{L}^{-1}\mathcal{L})^{2^{k-1}}}(h)\right)^{3}\cdot|A|^{5}\log|A|\ll$
$\ll|B|^{2^{k+1}}|A|^{2^{k+1}-4}\mathsf{T}_{2^{k}}(\mathcal{L})|\mathcal{L}|^{2^{k+1}}\cdot|A|^{5}\log|A|$

as required. $\hfill\Box$

The main advantage of bound (16) of Proposition 16 is that we have an
asymptotic formula for the number of incidences ${\cal I}(A\times
B,\mathcal{L})$ (and the set $\mathcal{L}$ can be rather small) but not just
upper bounds for ${\cal I}(\mathcal{P},\mathcal{L})$ as in [28]. An asymptotic
formula for the quantity ${\cal I}(\mathcal{P},\mathcal{L})$ was known before
in the specific case of large sets (see [31] or estimate (26) below) and in
the case of Cartesian products but with large sets of lines, see [24] and
[28].

In the next lemma we estimate the energy $\mathsf{T}_{k}(\mathcal{L})$ for a
concrete family of lines which will appear in the proofs of the results of our
paper.

###### Lemma 8

Let $A,B\subseteq\mathbb{F}^{*}_{p}$ be sets, and
$\mathcal{L}=\\{(a,b)~{}:~{}a\in A,\,b\in B\\}\subseteq{\rm
Aff}(\mathbb{F}_{p})$. Then for any $k\geqslant 2$ one has

$\mathsf{T}_{k}(\mathcal{L})\leqslant|A|^{2k-1}\mathsf{T}^{+}_{k}(B)\,.$ (17)

P r o o f. Let us consider the case of even $k$ and for odd $k$ the arguments
are similar. One has
$\mathcal{L}^{-1}\mathcal{L}=\\{(a/c,(b-d)/c)~{}:~{}a,c\in A,\,b,d\in B\\}$.
Considering $\mathsf{T}_{2k}(\mathcal{L})$, we arrive to two equations. The
first one is

$\frac{a_{1}\dots a_{k}}{c_{1}\dots c_{k}}=\frac{a^{\prime}_{1}\dots
a^{\prime}_{k}}{c^{\prime}_{1}\dots c^{\prime}_{k}}\,.$ (18)

If we fix all variables $a_{1}\dots a_{k},a^{\prime}_{1}\dots a^{\prime}_{k}$,
$c_{1}\dots c_{k},c^{\prime}_{1}\dots c^{\prime}_{k}\in A$, then the number of
the solutions to the second equation is
$\mathsf{T}^{+}_{2k}(\alpha_{1}B,\dots,\alpha_{2k}B)$, where
$\alpha_{1},\dots,\alpha_{2k}\in\mathbb{F}_{p}^{*}$ are some elements of $A$
depending on the fixed variables. The last quantity is at most
$\mathsf{T}^{+}_{2k}(B)$ by Lemma 4. Returning to (18), we obtain the required
inequality. $\hfill\Box$

Now we can obtain our first driving result.

###### Theorem 9

Let $A,B,X_{1},Y_{1},Z_{1}\subseteq\mathbb{F}^{*}_{p}$ be sets, $A=XY_{1}$,
$B=XY_{2}$, $|A|=|X||Y_{1}|/K_{*}$, $|B|=|X||Y_{2}|/K_{*}$, and $|XZ|\leqslant
K|X|$, $|ZZ|\leqslant\tilde{K}|Z|$. Suppose that $|Z|\geqslant p^{\delta}$ for
a certain $\delta\gg\log^{-1}\left(\frac{\log p}{\log\tilde{K}}\right)$. Then
for a certain $k\ll\delta^{-1}$ the following holds

$|\\{(a,b)\in A\times
B~{}:~{}a:=f_{*}(b)\\}|-\frac{K^{2}K_{*}^{2}|A||B|}{p}\ll
K^{2}K^{2}_{*}\tilde{K}\sqrt{|A||B|}\cdot p^{-\frac{1}{16^{k}}}\,.$ (19)

P r o o f. Let $\sigma$ be the quantity from the left–hand side of (19). Also,
let $Q_{1}=AZ$, $Q_{2}=BZ$. Then $|Q_{1}|\leqslant|XZ||Y_{1}|\leqslant
K|X||Y_{1}|=KK_{*}|A|$ and, similarly, for $Q_{2}$. We have

$|Z|^{2}\sigma\leqslant|\\{(q_{1},q_{2},z_{1},z_{2})\in Q_{1}\times
Q_{2}\times Z^{2}~{}:~{}q_{1}/z_{1}:=f_{*}(q_{2}/z_{2})\\}|\,.$

Using the definition of the function $f_{*}$, we arrive to the equation

$\frac{q_{1}}{z_{1}}=\frac{q_{2}}{\alpha q_{2}+\beta
z_{2}}\quad\quad\implies\quad\quad\frac{z_{1}}{q_{1}}-\frac{\beta
z_{2}}{q_{2}}=\alpha\,.$ (20)

The last equation can be interpreted as points/lines incidences with the set
of lines $\mathcal{L}=Z\times Z$, any $l\in\mathcal{L}$ has the form
$l:z_{1}X-\beta z_{2}Y=\alpha$ and the set of points
$\mathcal{P}=Q^{-1}_{1}\times Q^{-1}_{2}$. Applying Proposition 16, we obtain
for any $k$

$\sigma-\frac{|Q_{1}||Q_{2}|}{p}\ll|Z|^{-1}\sqrt{|Q_{1}||Q_{2}|}\cdot(\mathsf{T}_{2^{k}}(\mathcal{L})|Q_{1}|\log|Q_{1}|)^{1/2^{k+2}}\,.$

Using our bounds for sizes of the sets $Q_{1},Q_{2}$, combining with Lemma 17
and Theorem 14, we get

$\sigma-\frac{K^{2}K^{2}_{*}|A||B|}{p}\lesssim
KK_{*}\tilde{K}\sqrt{|A||B|}\cdot\left(KK_{*}|A||Z|^{-\frac{k+1}{2}}\right)^{1/2^{k+2}}$

provided $|Z|\gtrsim_{k}\tilde{K}^{2^{k+1}}$ and $|Z|^{k+1}\ll p^{2}$. Taking
$|Z|^{k}\sim p$, we satisfy the second condition and obtain

$\sigma-\frac{K^{2}K^{2}_{*}|A||B|}{p}\ll
K^{2}K^{2}_{*}\tilde{K}\sqrt{|A||B|}\cdot p^{-\frac{1}{16^{k}}}\,.$

Choosing $k\sim 1/\delta$, we have the condition $|Z|^{k}\sim p$ and the
assumption $\delta\gg\log^{-1}\left(\frac{\log p}{\log\tilde{K}}\right)$
implies that the inequality $|Z|\gtrsim_{k}\tilde{K}^{2^{k+1}}$ takes place.
$\hfill\Box$

###### Remark 10

One can increase the generality of Theorem 19 considering different sets
$X_{1},X_{2},Z_{1},Z_{2}$ such that $|X_{1}Z_{1}|\leqslant K_{1}|X_{1}|$,
$|X_{2}Z_{2}|\leqslant K_{2}|X_{2}|$ and so on. We leave the proof of this
generalization to the interested reader.

###### Corollary 11

Let $g$ be a primitive root and $I,J\subseteq\mathbb{F}^{*}_{p}$ be two
geometric progressions with the same base $g$ such that

$\exp(C\log p/\log\log p)\ll|I|=|J|\leqslant p/2\,,$ (21)

where $C>0$ is an absolute constant. Then

$|\\{(a,b)\in I\times J~{}:~{}a:=f_{*}(b)\\}|\leqslant(1-\kappa)|I|\,,$ (22)

where $\kappa>0$ is an absolute constant.

P r o o f. Let $I=a\cdot\\{1,g,\dots,g^{n}\\}$,
$J=b\cdot\\{1,g,\dots,g^{n}\\}$, where $n=|I|=|J|$. We apply Theorem 19 with
$A=I$, $B=J$, $Y_{1}=\\{a\\}$, $Y_{2}=\\{b\\}$, $X=\\{1,g,\dots,g^{n}\\}$,
$K_{*}=1$ and $Z=\\{1,g,\dots,g^{m}\\}$, where $m=[cn]$, $c=1/4$. Then
$K\leqslant 1+c$ and $\tilde{K}<2$. By formula (19), we obtain

$|\\{(a,b)\in I\times
J~{}:~{}a:=f_{*}(b)\\}|-\frac{(1+c)^{2}|I||J|}{p}\ll|I|\cdot
p^{-\frac{1}{16^{k}}}\,.$

We have $\frac{(1+c)^{2}|I||J|}{p}\leqslant\frac{25}{32}|I|$ because
$n\leqslant p/2$. Recalling that $k\sim 1/\delta$ and $\delta\gg(\log\log
p)^{-1}$, we derive estimate (22) thanks to our condition (21). This completes
the proof. $\hfill\Box$

Now we are ready to prove Theorem 1 from the introduction, which we formulate
in a slightly general form. In our arguments we use some parts of the proof
from [7].

###### Theorem 12

Let $p$ be a prime number and $\gamma\in\mathbb{F}_{p}^{*}$ be an element of
order at least

$\exp(\Omega(\log p/\log\log p))\,.$

Also, let $\varepsilon_{j}$ be the random variables distributed uniformly on
$\\{\gamma^{-1},\gamma\\}$. Consider the lazy Markov chain $0\neq
X_{0},X_{1},\dots,X_{n},\dots$ defined by

$X_{j+1}=\left\\{\begin{array}[]{ll}f_{*}\left(X_{j}\right)\cdot\varepsilon_{j+1}&\text{
with probability }1/2\,,\\\ X_{j}&\text{ with probability
}1/2\,.\end{array}\right.$

Then for an arbitrary $c>0$ and for any $n=c\exp(\log p/\log\log p)$ one has

$\|P_{n}-U\|:=\frac{1}{2}\max_{A\subseteq\mathbb{F}^{*}_{p}}\left|\mathrm{P}(X_{n}\in
A)-\frac{|A|}{p-1}\right|\leqslant e^{-O(c)}\,.$

The same is true for the chain
$X_{j+1}=f_{*}\left(X_{j}\right)\cdot\varepsilon_{j+1}$, where
$\varepsilon_{j}$ denote the random variables distributed uniformly on
$\\{1,\gamma^{-1},\gamma\\}$.

Let $P$ be an ergodic Markov chain on a $k$–regular directed graph $G=G(V,E)$.
Let $h(G)$ be the Cheeger constant

$h(G)=\min_{|S|\leqslant|V|/2}\frac{e(S,S^{c})}{k|S|}\,,$ (23)

where $e(S,S^{c})$ is the number of edges between $S$ and the complement of
$S$. We need a result from [4] (a more compact version is [7, Theorem 4.1]).

###### Theorem 13

Let $P$ be an ergodic Markov chain on a graph $G=G(V,E)$. Consider the lazy
chain $X_{0},X_{1},\dots,X_{n},\dots$ with transition matrix $(I+P)/2$, and
starting from a certain deterministic $X_{0}$. Then for any $c>0$ and any
$n=ch(G)^{-2}\log|V|$ one has

$\max_{A\subseteq V}\left|\mathrm{P}(X_{n}\in
A)-\frac{|A|}{|V|}\right|\leqslant e^{-O(c)}\,.$

In our case $G=G(V,E)$ with $V=\mathbb{F}_{p}^{*}$ and $x\to y$ iff
$y=f_{*}(x)\gamma^{\pm 1}$. Thus our task is to estimate the Cheeger constant
of $G$. Take any $S$, $|S|\leqslant p/2$ and write $S$ as the disjoint union
$S=\bigsqcup_{j\in J}G_{j}$, where $G_{j}$ are geometric progressions with
step $\gamma^{2}$. Here and below we use the fact that $\mathbb{F}_{p}^{*}$ is
cyclic, isomorphic to $\mathbb{Z}/(p-1)\mathbb{Z}$ and generated by a fixed
primitive root $g$. Consider $z,z\gamma,z\gamma^{2}$, where $z\in S$ is a
right endpoint (if it exists) of some $G_{j}$. Then $z\gamma^{2}\in S^{c}$ and
$z,z\gamma^{2}$ are connected with $f^{-1}_{*}(z\gamma)$. The point
$f^{-1}_{*}(z\gamma)$ belongs either $S$ or $S^{c}$ but in any case we have an
edge between $S$ and $S^{c}$. Let $J=J_{0}\bigsqcup J_{1}$, where for $j\in
J_{0}$ the set $G_{j}$ has no the right endpoint and $J_{1}=J\setminus J_{0}$.
Clearly, $|J_{0}|\leqslant 2|S|/\mathrm{ord}(\gamma)$. By the argument above

$2h(G)\geqslant\frac{|J_{1}|}{|S|}\geqslant\frac{|J|}{|S|}-\frac{2}{\mathrm{ord}(\gamma)}\,.$
(24)

We want to obtain another lower bound for $h(G)$, which works better in the
case when $J$ is small. Put $L=|S|/|J|$ and let $\omega\in(0,1)$ be a small
parameter, which we will choose later. One has $\sum_{j\in J}|G_{j}|=|S|$ and
hence $\sum_{j~{}:~{}|G_{j}|\geqslant\omega L}|G_{j}|\geqslant(1-\omega)|S|$.
Splitting $G_{j}$ up into intervals of length exactly $L_{\omega}:=\omega
L/2$, we see that the rest is at most $(1-2\omega)|S|$. Hence we have obtained
some geometric progressions $G^{\prime}_{i}$, $i\in I$, having lengths
$L_{\omega}$ and step $\gamma^{2}$ and such that $\sum_{i\in
I}|G^{\prime}_{i}|\geqslant(1-2\omega)|S|$. Put $S^{\prime}=\bigsqcup_{i\in
I}G^{\prime}_{j}$ and let $\Omega=S\setminus S^{\prime}$, $|\Omega|\leqslant
2\omega|S|$. In other words, we have $S^{\prime}=XY$,
$|S^{\prime}|=|X||Y|\geqslant(1-2\omega)|S|$, where
$X=[1,\gamma^{2},\dots,\gamma^{2(L_{\omega}-1)}]$ and $Y$ is a certain set of
multiplicative shifts. Clearly,

$2h(G)\geqslant\frac{e(S,S^{c})}{|S|}\geqslant 1-\frac{e(S,S)}{|S|}\geqslant
1-8\omega-\frac{e(S^{\prime},S^{\prime})}{|S|}\,.$ (25)

Put $Z=[1,\gamma^{2},\dots,\gamma^{2(L^{\prime}_{\omega}-1)}]$, where
$L^{\prime}_{\omega}=[cL_{\omega}]$, where $c=1/4$. We have $|ZZ|<2|Z|$. Also,
by the assumption the element $\gamma$ has order at least $\exp(\Omega(\log
p/\log\log p))$. Using Theorem 19 with $K=1+c$, $\tilde{K}=2$, $k\sim
1/\delta$ and taking $\delta\geqslant C(\log\log p)^{-1}$ for sufficiently
large constant $C>0$, we get

$\frac{e(S^{\prime},S^{\prime})}{|S|}-\frac{25|S^{\prime}|}{16p}\ll
p^{-\frac{1}{16^{k}}}\leqslant\frac{1}{32}\,.$

Recalling that $|S^{\prime}|\leqslant|S|\leqslant p/2$, we derive

$\frac{e(S^{\prime},S^{\prime})}{|S|}\leqslant\frac{25}{32}+\frac{1}{32}=\frac{13}{16}\,.$

Substituting the last formula into (25), taking sufficiently large $p$ and
choosing $\omega=2^{-8}$, say, we have $h(G)\geqslant 1/32$. We need to check
the only condition of Theorem 19, namely, $|Z|\geqslant p^{\delta}$. If not,
then

$|S|/|J|=L\ll L_{\omega}\ll|Z|<p^{\delta}\sim\exp(O(\log p/\log\log p))\,,$

and hence $|J|\gg|S|\exp(-O(\log p/\log\log p))$. But then by (24) and our
assumption $\mathrm{ord}(\gamma)=\exp(\Omega(\log p/\log\log p))$, we see that
in any case $h(G)\gg\exp(-O(\log p/\log\log p))$. Combining the last bound for
the Cheeger constant and Theorem 13, we derive $n\leqslant\exp(O(\log
p/\log\log p))$.

The last part of Theorem 12 follows by the same method, combining with the
arguments from [3] and [7, Section 4.3]. We need to ensure that the bijection
$f_{*}(f^{-1}_{*}(\cdot)\gamma):\mathbb{F}_{p}^{*}\to\mathbb{F}_{p}^{*}$ has
the same form as in (4) (with our usual convention that
$f_{*}(-\beta/\alpha)=1/\alpha$ of course). It can be check via a direct
calculation or thanks to the fact that $f_{*}$ corresponds to the standard
action of a lower–triangular matrix in $\mathrm{GL}_{2}(\mathbb{F}_{p})$. This
completes the proof of Theorem 12. $\hfill\Box$

###### Remark 14

Consider lazy Markov chain (2) with $f(x)=x^{2}$ and $p\equiv 3\pmod{4}$.
Using the same argument as in the proof of Theorem 12, we need to have deal
with the equation $y+a=f(x+b)=x^{2}+2bx+b^{2}$, where $a,b$ belong to some
arithmetic progression $P$ and $x,y$ are from a disjoint union of $J$
arithmetic progressions, see details in [7] (strictly speaking, now the
stationary distribution is not uniform and, moreover, our graph is not regular
which requires to have a modification of definition (23)). Then last equation
can be interpreted as points/lines incidences with the set of lines
$\mathcal{L}$ of the form $Y=2bX+(b^{2}-a)$ and the set of points
$\mathcal{P}=(y-x^{2},x)$. Using the main result from [31] (also, see [24]),
we obtain

$\left|\mathcal{I}(\mathcal{P},\mathcal{L})-\frac{|\mathcal{P}||\mathcal{L}|}{p}\right|\leqslant\sqrt{|\mathcal{P}||\mathcal{L}|p}\,.$
(26)

By formula (26) and the calculations as above (see details in [7, Section
4.2]) we have an expander if $|S|/J\sim|P|\gg\sqrt{p}$. If the last inequality
does not holds, then $J\gg|S|/\sqrt{p}$ and by an analogue of formula (24), we
obtain $h(G)\gg 1/\sqrt{p}$. Hence in view of Theorem 13, we see that the
mixing time is $O(p\log p)$.

The method of the proof of Theorem 12 (and see Remark 14) allows us to produce
easily some lazy Markov chains on $\mathbb{F}^{*}_{p}$ with the mixing time
$O(p\log p)$, e.g.,

$X_{j+1}=\left\\{\begin{array}[]{ll}\mathrm{ind}\left(X_{j}\right)\cdot\varepsilon_{j+1}&\text{
with probability }1/2\,,\\\ X_{j}&\text{ with probability
}1/2\end{array}\right.$ (27)

($X_{0}\neq 0$) or as in (2) with $f(x)=\exp(x)$, namely,

$X_{j+1}=\left\\{\begin{array}[]{ll}\exp\left(X_{j}\right)+\varepsilon_{j+1}&\text{
with probability }1/2\,,\\\ X_{j}&\text{ with probability
}1/2\,.\end{array}\right.$ (28)

Indeed, in the first chain we arrive to the equation
$ya=\mathrm{ind}(x)+\mathrm{ind}(b)$ and in the second one to
$y+b=\exp(x)\cdot\exp(a)$. Both equations correspond to points/lines
incidences. Let us underline one more time that our functions
$\mathrm{ind}(x),\exp(x)$ are defined on $\mathbb{F}_{p}^{*}$ but not on
$\mathbb{F}_{p}$. In reality, one has much better bound for the mixing time of
two Markov chains above.

###### Theorem 15

Let $p$ be a prime number and $\gamma\in\mathbb{F}^{*}_{p}$. Then the mixing
time of Markov chain (28) is $\exp(O(\log p/\log\log p))$. If, in addition,
the order of $\gamma$ is $\exp(\Omega(\log p/\log\log p))$, then the mixing
time of Markov chain (27) is $\exp(O(\log p/\log\log p))$.

P r o o f. Our arguments follow the same scheme as the proofs of Theorem 19
and Theorem 12. In both cases we need to estimate the energy
$\mathsf{T}_{2^{k}}$ of the set of affine transformations $L$ of the form
$x\to gx+r$, where coefficients $g\in\Gamma$ and $r\in P$ belongs to a
geometric and an arithmetic progression of size $\sqrt{|L|}$, respectively. An
application of Lemma 17 is useless because $\mathsf{T}^{+}_{2^{k}}(P)$ is
maximal. Nevertheless, we consider the set $L^{-1}L$ and notice that any
element of $L^{-1}L$ has the form $x\to g_{2}/g_{1}x+(r_{2}-r_{1})/g_{1}$,
where $g_{1},g_{2}\in\Gamma$, $r_{1},r_{2}\in P$. Now in view of the arguments
of Lemma 17 our task is to estimate
$|\Gamma|^{2^{k+1}-1}|P|^{2^{k+1}}\mathsf{T}^{+}_{2^{k}}(Q/\Gamma)$, where
$Q=P-P$. Write $W=Q/\Gamma$ and notice that $|Q|<2|P|$. Taking
$X\subseteq\Gamma^{-1}$ as in inequality (10) and applying this inequality
with $A=\Gamma^{-1}$, $B=\Gamma^{-1}$ and $C=Q$, we see that

$|WX|=|Q/\Gamma\cdot X|\leqslant 2|Q/\Gamma|=2|W|\,.$

Increasing the constant $2$ to $O(1)$ in the formula above, one can easily
assume (or see [30]) that for a certain $Y$ the following holds
$|Y|\geqslant|\Gamma|/2$. Applying Theorem 14 with $A=W$ and $B=Y$, we obtain

$\mathsf{T}^{+}_{2^{k}}(W)\lesssim_{k}\frac{|W|^{2^{k+1}}}{p}+|W|^{2^{k+1}-1}\cdot|\Gamma|^{-\frac{k-1}{2}}\,.$

Here we need to assume that $|\Gamma|\gtrsim_{k}1$. Hence arguing as in Lemma
17 and using the trivial bound $|W|\leqslant|L|$, we get

$\mathsf{T}_{2^{k+1}}(L)\lesssim_{k}|\Gamma|^{2^{k+1}-1}|P|^{2^{k+1}}\left(\frac{|L|^{2^{k+1}}}{p}+|L|^{2^{k+1}-1}\cdot|\Gamma|^{-\frac{k-1}{2}}\right)\ll|L|^{2^{k+2}}\cdot|\Gamma|^{-\frac{k+5}{2}}\,,$

provided $|L|\gtrsim_{k}1$ and $|\Gamma|^{k+3}\ll p^{2}$. After that we apply
the same argument as in the proof of Theorem 12. $\hfill\Box$

##  4 Combinatorial applications

We now obtain an application of the developed technique to Sidon sets and we
follow the arguments from [26]. We need Lemma 3, Lemma 7 and Theorem 4 from
this paper.

###### Lemma 16

Let $A\subseteq{\mathbf{G}}$ be a set. Then for any $k\geqslant 2$ one has

$\mathsf{Sid}_{3k-3}(A)\gg\left(\frac{|A|^{2k}}{\mathsf{E}_{k}(A)}\right)^{1/(2k-1)}\,,\quad\quad\mbox{
and
}\quad\quad\mathsf{Sid}_{2k-2}(A)\gg\left(\frac{|A|^{2k}}{\hat{\mathsf{E}}_{k}(A)}\right)^{1/(2k-1)}\,.$
(29)

###### Lemma 17

Let $A\subseteq{\mathbf{G}}$ be a set, $A=B+C$, and $k\geqslant 1$ be an
integer. Then

$\mathsf{Sid}_{k}(A)\leqslant\min\\{|C|\sqrt{k|B|}+|B|,|B|\sqrt{k|C|}+|C|\\}\,.$

###### Theorem 18

Let $A\subseteq{\mathbf{G}}$ be a set, $\delta,\varepsilon\in(0,1]$ be
parameters, $\varepsilon\leqslant\delta$.
$1)~{}$ Then there is
$k=k(\delta,\varepsilon)=\exp(O(\varepsilon^{-1}\log(1/\delta)))$ such that
either $\mathsf{E}_{k}(A)\leqslant|A|^{k+\delta}$ or there is
$H\subseteq{\mathbf{G}}$, $|H|\gtrsim|A|^{\delta(1-\varepsilon)}$,
$|H+H|\ll|A|^{\varepsilon}|H|$ and there exists $Z\subseteq{\mathbf{G}}$,
$|Z||H|\ll|A|^{1+\varepsilon}$ with

$|(H\dotplus Z)\cap A|\gg|A|^{1-\varepsilon}\,.$

$2)~{}$ Similarly, either there is a set $A^{\prime}\subseteq A$,
$|A^{\prime}|\gg|A|^{1-\varepsilon}$ and $P\subseteq{\mathbf{G}}$,
$|P|\gtrsim|A|^{\delta}$ such that for all $x\in A^{\prime}$ one has
$r_{A-P}(x)\gg|P||A|^{-\varepsilon}$ or
$\mathsf{E}_{k}(A)\leqslant|A|^{k+\delta}$ with $k\ll 1/\varepsilon$.

To have deal with the real setting we need the famous Szemerédi–Trotter
Theorem [29].

###### Theorem 19

Let $\mathcal{P}$, $\mathcal{L}$ be finite sets of points and lines in
${\mathbb{R}}^{2}$. Then

$\mathcal{I}(\mathcal{P},\mathcal{L})\ll(|\mathcal{P}||\mathcal{L}|)^{2/3}+|\mathcal{P}|+|\mathcal{L}|\,.$

Now we are ready to prove Theorem 5. Take any $\delta<1/2$, e.g., $\delta=1/4$
and let $\varepsilon\leqslant\delta/4$ be a parameter, which we will choose
later. In view of Lemma 29 we see that
$\mathsf{E}^{\times}_{k}(A)\leqslant|A|^{k+\delta}$ implies

$\mathsf{Sid}^{\times}_{3k-3}(A)\gg|A|^{\frac{1}{2}+\frac{1-2\delta}{2(2k-1)}}=|A|^{\frac{1}{2}+\frac{1}{4(2k-1)}}$
(30)

and we are done. Here $k=k(\varepsilon)$. Otherwise there is
$H\subseteq\mathbb{F}$,
$|H|\gtrsim|A|^{\delta(1-\varepsilon)}\geqslant|A|^{\delta/2}$,
$|HH|\ll|A|^{\varepsilon}|H|$ and there exists $Z\subseteq\mathbb{F}$,
$|Z||H|\ll|A|^{1+\varepsilon}$ with $|(H\cdot Z)\cap
A|\gg|A|^{1-\varepsilon}\,.$ Here the product of $H$ and $Z$ is direct. Put
$A_{*}=(H\cdot Z)\cap A$, $|A_{*}|\gg|A|^{1-\varepsilon}$ and we want to
estimate $\mathsf{E}^{\times}_{l+1}(A_{*}+1)$ or
$\hat{\mathsf{E}}_{l+1}^{\times}(A_{*}+1)$ for large $l$. After that having a
good upper bound for $\mathsf{E}^{\times}_{l+1}(A_{*}+1)$ or
$\hat{\mathsf{E}}_{l+1}^{\times}(A_{*}+1)$, we apply Lemma 29 again to find
large multiplicative Sidon subset of $A_{*}$.

First of all, notice that in view of (9), one has

$|HA^{-1}_{*}|\leqslant|HH^{-1}||Z|\ll|A|^{2\varepsilon}|H||Z|\ll|A|^{1+3\varepsilon}\,.$

In other words, the set $A^{-1}_{*}$ almost does not grow after the
multiplication with $H$. Let $Q=HA^{-1}_{*}$, $|Q|\ll|A|^{1+3\varepsilon}$ and
also let $M=|A|^{\varepsilon}$. Secondly, fix any $\lambda\neq 0,1$. The
number of the solutions to the equation $a_{1}/a_{2}=\lambda$, where
$a_{1},a_{2}\in A_{*}+1$ does not exceed

$\sigma_{\lambda}:=|H|^{-2}|\\{h_{1},h_{2}\in H,\,q_{1},q_{2}\in
Q~{}:~{}(h_{1}/q_{1}+1)/(h_{2}/q_{2}+1)=\lambda\\}|\,.$

The last equation has form (20), namely,

$\frac{h_{1}}{q_{1}}-\frac{\lambda h_{2}}{q_{2}}=\lambda-1$

and can be interpreted as a question about the number of incidences between
points and lines. For each $\lambda\neq 0,1$ the quantity $\sigma_{\lambda}$
can be estimated as

$\sigma_{\lambda}\ll|H|^{-2}\cdot|Q||H|^{2-\kappa}\ll|A|^{1+3\varepsilon}|H|^{-\kappa}$
(31)

similarly to the proof of Theorem 19 above (in the case
$\mathbb{F}={\mathbb{R}}$ the same is true thanks to Theorem 19). Here
$\kappa=\kappa(\delta)>0$. Indeed, by our assumption $|A|<\sqrt{p}$, Theorem
14, Proposition 16 and Lemma 17, we have

$\sigma_{\lambda}-\frac{|Q|^{2}}{p}\lesssim|Q||H|^{-1/2}(|Q|\mathsf{T}^{+}_{2^{r}}(H))^{1/2^{r+2}}\lesssim|Q|\sqrt{M}\left(M^{3}|A||H|^{-\frac{r+1}{2}}\right)^{1/2^{r+2}}$
(32)

provided $|H|\gtrsim_{r}M^{2^{r+1}}$ and $|H|^{r+1}\ll p$. Here $r$ is a
parameter and we take $r\sim 1/\delta$ to satisfy the second condition. To
have the first condition just take $\varepsilon{2^{r+1}}\ll\delta$ (in other
words, $\varepsilon\leqslant\exp(-\Omega(1/\delta))$) and we are done because
$|H|\gg|A|^{\delta/2}$.

Further using $|H|\gg|A|^{\delta/2}$, $|A_{*}|\gg|A|^{1-\varepsilon}$ and
choosing any $\varepsilon\leqslant\delta\kappa/100$, we obtain after some
calculations and formula (31) that
$\sigma_{\lambda}\ll|A_{*}|^{1-\delta\kappa/4}$. Hence taking sufficiently
large $l\gg(\delta\kappa)^{-1}$, we derive

$\hat{\mathsf{E}}_{l+1}^{\times}(A_{*})=\sum_{\lambda}r^{l+1}_{A_{*}A_{*}}(\lambda)\ll|A_{*}|^{l+1}+(|A_{*}|^{1-\delta\kappa/2})^{l}|A_{*}|^{2}\ll|A_{*}|^{l+1}+|A|^{l+2-\delta\kappa
l/2}\ll|A_{*}|^{l+1}\,.$

Applying Lemma 29 and choosing $\varepsilon\ll l^{-1}$, we see that

$\mathsf{Sid}^{\times}_{2l}(A)\geqslant\mathsf{Sid}^{\times}_{2l}(A_{*})\gg|A_{*}|^{\frac{l+1}{2l+1}}\gg|A|^{\frac{(1-\varepsilon)(l+1)}{2l+1}}=|A|^{\frac{1}{2}+\frac{1-2\varepsilon(l+1)}{2(2l+1)}}\gg|A|^{\frac{1}{2}+c}\,,$

where $c=c(\delta)>0$ is an absolute constant. We have obtained bound (5) of
Theorem 5.

As for estimate (7), we use the same argument as above but now our analogue of
the quantity $\sigma_{\lambda}$ is
$\exp(q_{1})\exp(h_{1})-\exp(q_{2})\exp(h_{2})=\lambda$, where $q_{1},q_{2}\in
Q=A_{*}+H$, $h_{1},h_{2}\in H$ (we use the notation above). The last equation
can be treated as points/lines incidences with the set of lines
$x\exp(h_{1})-y\exp(h_{2})=\lambda$, $|\mathcal{L}|=|H|^{2}$ and the
correspondent set of points $\mathcal{P}$ of size $|Q|^{2}$. Then analogues of
bounds (31), (32) take place and we are done.

It remains to obtain estimate (8) of the theorem. For any sets
$X_{1},X_{2},X_{3}$ consider the set $R[X_{1},X_{2},X_{3}]$

$R[X_{1},X_{2},X_{3}]=\left\\{\frac{x_{1}-x_{3}}{x_{2}-x_{3}}~{}:~{}x_{1},x_{2},x_{3}\in
X,\,x_{2}\neq x_{3}\right\\}\,.$

If $X_{1}=X_{2}=X_{3}=X$, then we put $R[X_{1},X_{2},X_{3}]=R[X]$. One can
check that $1-R[X_{1},X_{2},X_{3}]=R[X_{1},X_{3},X_{2}]$. For
$\mathbb{F}={\mathbb{R}}$ or $\mathbb{F}=\mathbb{F}_{p}$ we put $X=P$,
$A=R[X]$, where $P=\\{1,\dots,n\\}$, $\bar{P}=\\{-n,\dots,n\\}$ and let
$n<\sqrt{p}$ in the case of $\mathbb{F}_{p}$. Then $A$ is contained in
$\bar{P}/\bar{P}:=B\cdot C$ and in view of Lemma 17 any multiplicative
$k$–Sidon subset of $A$ has size at most $O(\sqrt{k}|A|^{3/4})$ because as one
can check $|A|\gg|P|^{2}$. Further $1-A=A$ and hence the same argument is
applicable for the set $1-A$. It remains to notice that
$\mathsf{Sid}^{\times}(X)=\mathsf{Sid}^{\times}(-X)$ for any set $X$. Finally,
let us make a remark that there is an alternative (but may be a little bit
harder) way to obtain estimate (8). Indeed, consider $R[\Gamma]$, where
$\Gamma\subseteq\mathbb{F}_{p}^{*}$, $|\Gamma|<\sqrt{p}$ is a multiplicative
subgroup (we consider the case $\mathbb{F}=\mathbb{F}_{p}$, say). One can
notice that $R[\Gamma]=(\Gamma-1)/(\Gamma-1)$ and repeat the argument above.

## References

  * [1] C. Asci,  Generating uniform random vectors. J. Theor. Probab. 14, 333–356 (2001).
  * [2] J. Bourgain, A. Gamburd,  Uniform expansion bounds for Cayley graphs of $SL_{2}(\mathbb{F}_{p})$,  Ann. of Math., 167(2):625–642, 2008.
  * [3] S. Chatterjee, P. Diaconis,  Speeding up Markov chains with deterministic jumps,  Probab. Theory Related Fields, 178(3-4):1193–1214, 2020.
  * [4] F.R.K. Chung,  Laplacians and the Cheeger inequality for directed graphs,  Ann. Comb. 9 (2005), no. 1, 1–19.
  * [5] F.R.K. Chung, P. Diaconis, R. L. Graham,  Random walks arising in random number generation,  Ann. Probab., 15(3):1148–1165, 1987.
  * [6] S. Eberhard, P. P. Varjú,  Mixing time of the Chung–Diaconis–Graham random process,  Probability Theory and Related Fields 179.1 (2021): 317–344.
  * [7] J. He,  Markov chains on finite fields with deterministic jumps,  arXiv:2010.10668
  * [8] J. He, H.T. Pham, M.W. Xu,  Mixing time of fractional random walk on finite fields,  arXiv:2102.02781 (2021).
  * [9] M. Hildebrand,  A lower bound for the Chung–Diaconis–Graham random process,  Proc. Am. Math. Soc. 137(4), 1479–1487 (2009).
  * [10] 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,  In: Aldous D., Pemantle R. (eds) Random Discrete Structures. The IMA Volumes in Mathematics and its Applications, vol 76. Springer, New York, NY.
  * [11] M. Hildebrand,  Random Processes of the Form $X_{n+1}=a_{n}X_{n}+b_{n}\pmod{p}$,  The Annals of Probability (1993): 710–720.
  * [12] https://pohoatza.wordpress.com/2021/01/23/sidon-sets-and-sum-product-phenomena/
  * [13] J. Komlós, M. Sulyok, E. Szemerédi,  Linear problems in combinatorial number theory,  Acta Mathematica Academiae Scientiarum Hungarica 26.1–2 (1975): 113–121.
  * [14] I. A. Kruglov,  Random sequences of the form $X_{t}+1=a_{t}X_{t}+b_{t}\pmod{n}$ with dependent coefficients $a_{t}$, $b_{t}$,  Diskr. Mat., 17:2 (2005), 49–55; Discrete Math. Appl., 15:2 (2005), 145–151.
  * [15] D. A. Levin, Y. Peres,  Markov chains and mixing times,  AMS, Providence, RI, 2017. Second edition, with contributions by Elizabeth L. Wilmer, with a chapter on “Coupling from the past” by James G. Propp and David B. Wilson.
  * [16] G. Petridis,  New proofs of Plünnecke-type estimates for product sets in groups,  Combinatorica, 32:6 (2012), 721–733.
  * [17] B. Murphy,  Upper and lower bounds for rich lines in grids,  arXiv:1709.10438v1 [math.CO] 29 Sep 2017.
  * [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,  arXiv preprint math/0407117 (2004).
  * [20] O. Roche–Newton, A. Warren,  Additive and multiplicative Sidon sets,  arxiv.org/abs/2103.13066
  * [21] M. Rudnev, I.D. Shkredov,  On growth rate in ${\rm SL}_{2}(\mathbb{F}_{p})$, the affine group and sum-product type implications,  arXiv:1812.01671v3 [math.CO] 26 Feb 2019.
  * [22] A. S. Semchankau,  Maximal Subsets Free of Arithmetic Progressions in Arbitrary Sets,  Math. Notes, 102:3 (2017), 396–402.
  * [23] I.D. Shkredov,  Some remarks on the asymmetric sum–product phenomenon,  MJCNT, (2018), 101–126, dx.doi.org/10.2140/moscow.2018..101
  * [24] I.D. Shkredov,  On asymptotic formulae in some sum–product questions,  Tran. Moscow Math. Soc, 79:2 (2018), 271–334; English transl. Trans. Moscow Math. Society 2018, pp.231–281.
  * [25] I.D. Shkredov,  Modular hyperbolas and bilinear forms of Kloosterman sums,  JNT, 20 (2021) 182–211.
  * [26] I.D. Shkredov,  On an application of higher energies to Sidon sets,  arXiv:2103.14670 (2021).
  * [27] S. Sidon,  Ein Satz über trigonomietrische Polynome und seine Anwendungen in der Theorie der Fourier–Reihen,  Math. Annalen 106 (1932), 536–539.
  * [28] S. Stevens, F. de Zeeuw, An improved point-line incidence bound over arbitrary fields, Bull. LMS 49: 842–858, 2017.
  * [29] E. Szemerédi, W.T. Trotter,  Extremal problems in discrete geometry, Combinatorica 3(3-4):381–392, 1983.
  * [30] T. Tao, V. Vu, Additive combinatorics, Cambridge University Press 2006.
  * [31] L. A. Vinh, The Szemerédi-Trotter type theorem and the sum-product estimate in finite fields, European J. Combin. 32(8): 1177–1181, 2011.
  * [32] A. Warren,  Additive and multiplicative Sidon sets,  report at CANT–2021; http://www.theoryofnumbers.com/cant/

I.D. Shkredov
Steklov Mathematical Institute,
ul. Gubkina, 8, Moscow, Russia, 119991
and
IITP RAS,
Bolshoy Karetny per. 19, Moscow, Russia, 127994
and
MIPT,
Institutskii per. 9, Dolgoprudnii, Russia, 141701
<EMAIL_ADDRESS>