Number of solutions of $am \equiv bn \pmod{q}$

Question

Let $q$ be a (large) prime. Let $N$ be a positive integer of size${}\approx \sqrt{q}$. Let $\mathcal{M}$ be an arbitrary subset of $\{1, \dots, q\},$ such that $\mathcal{M}$ has cardinality $N$. Question: is there a non-trivial upper bound for the number of solutions of $$ a m \equiv b n \qquad \pmod q, $$ subject to $1 \leq a,b \leq N$ and $m,n \in \mathcal{M}$?

The trivial upper bound is $N^3$, since given $a,m,b$, there is at most one choice for $n$.

As a heuristics, for a "random" set $\mathcal{M}$, one would expect around $N^2$ many solutions (there are $N^2 \approx q$ possibilities for the value of $am$ as $a$ runs through $\{1, \dots, N\}$ and $m$ runs through $\mathcal{M}$, so typically each element of $\{1,\dots, q\}$ should be represented just a few times in the form $am$).

Is there a general upper bound of order $N^{2 + \varepsilon}$ for the number of solutions?

To me this seems to be related to sum-product problem from additive combinatorics and to the Erdös multiplication table problem.

(One could also imagine variants of the problem, where $a,b$ come from a general set of cardinality $N$, but not necessarily the set of the first $N$ integers. One could also consider the case when $N$ is not of order $\approx \sqrt{q}$, but significantly smaller/larger.)

Answer 1

I made a fatal mistake in my attempt at obtaining a simple asymptotic formula for the number $J$ of solutions to the congruence with the given restrictions. Undaunted, I come back with the proof of a general upper bound for $J$ which I learned from M. Z. Garaev back in the day.

Let us assume that $q \notin \mathcal{M}$. By the orthogonality relations for Dirichlet characters modulo $q$, it follows that

$$J = \frac{1}{p-1} \sum_{\chi} \sum_{\substack{m, \, n \in \mathcal{M}\\ 1 \leq a, \, b\leq N}} \chi(amb^{\ast}n^{\ast})$$

where $t^{\ast}$ denotes the multiplicative inverse of $t$ modulo $q$. By resorting to the multiplicativity of Dirichlet characters modulo $q$, we may rewrite the previous formula as

$$ J = \frac{1}{p-1} \sum_{\chi} \left|\sum_{m \in \mathcal{M}} \chi(m)\right|^{2} \left|\sum_{1 \leq a \leq N} \chi(a)\right|^{2}.$$

Then, if $n_{0} \in (1, \infty) \cap \mathbb{N}$, Hölder's inequality gives

$$ J \leq \left(\frac{1}{p-1}\sum_{\chi} \left|\sum_{m \in \mathcal{M}} \chi(m) \right|^{2\cdot \frac{n_{0}}{n_{0}-1}}\right)^{\frac{n_{0}-1}{n_{0}}} \left(\frac{1}{p-1} \sum_{\chi} \left|\sum_{1 \leq a \leq N} \chi(a)\right|^{2 \cdot n_{0} }\right)^{\frac{1}{n_{0}}}. \qquad (1)$$

We can obtain a nontrivial upper bound for the expression in the first pair of parentheses by resorting to the fact that

$$ \frac{1}{p-1} \sum_{\chi} \left|\sum_{m \in \mathcal{M}} \chi(m)\right|^{2} = |\mathcal{M}|$$

and proceeding thus:

\begin{eqnarray*} \frac{1}{p-1} \sum_{\chi} \left|\sum_{m \in \mathcal{M}} \chi(m)\right|^{2 \cdot \frac{n_{0}}{n_{0}-1}} &=& \frac{1}{p-1} \sum_{\chi} \left|\sum_{m \in \mathcal{M}} \chi(m)\right|^{2} \left|\sum_{m \in \mathcal{M}} \chi(m)\right|^{\frac{2}{n_{0}-1}}\\ &\leq& |\mathcal{M}| \left|\mathcal{M}\right|^{\frac{2}{n_{0}-1}}\\ &=& |\mathcal{M}|^{\frac{n_{0}+1}{n_{0}-1}}. \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad (2) \end{eqnarray*}

In order to estimate the expression in the second pair of parentheses in $(1)$, we note that

$$\frac{1}{p-1} \sum_{\chi} \left| \sum_{1 \leq a \leq N} \chi(a) \right|^{2n_{0}} = \frac{1}{p-1} \sum_{\chi} \sum_{1 \leq a_{1}, \ldots, a_{n_{0}}, u_{1}, \ldots, u_{n_{0}} \leq N} \chi(a_{1}\cdots a_{n_{0}}\cdot u_{1}^{\ast} \cdots u_{n_{0}}^{\ast});$$

therefore,

$$\frac{1}{p-1} \sum_{\chi} \left| \sum_{1 \leq a \leq N} \chi(a) \right|^{2n_{0}}$$

is equal to the number of solutions to the congruence

$$ a_{1}\cdots a_{n_{0}} \equiv u_{1} \cdots u_{n_{0}} \pmod{q}$$

where

$$1 \leq a_{1}, \ldots, a_{n_{0}}, u_{1}, \ldots, u_{n_{0}} \leq N.$$ The congruence can be expressed as the equation

$$a_{1} \cdots a_{n_{0}} = u_{1} \cdots u_{n_{0}} + qz$$

for some integer $z \in [-(N^{n_{0}}-1)/q, (N^{n_{0}}-1)/q]$. Hence, for any fixed selection of $u_{1}, \ldots, u_{n_{0}},$ and $z$, in their corresponding ranges, each of the $a_{1}, \ldots, a_{n_{0}}$ has to be a positive divisor of the product $u_{1} \cdots u_{n_{0}} + qz$. Since $1 \leq u_{1} \cdots u_{n_{0}} + qz < 2N^{n_{0}}$, the number of such $n_{0}$-tuples $(a_{1}, \ldots, a_{n_{0}})$ is $N^{o(1)}$. It follows that

$$\frac{1}{p-1} \sum_{\chi} \left| \sum_{1 \leq a \leq N} \chi(a) \right|^{2n_{0}} \leq \left(\frac{2N^{n_{0}}}{q}+1\right)N^{n_{0}}N^{o(1)}< \left(\frac{N^{n_{0}}}{q}+1\right) N^{n_{0}+o(1)}. \qquad (3).$$

From $(1)$, $(2)$, and $(3)$ we conclude that

$$ J \leq |\mathcal{M}|^{\frac{n_{0}+1}{n_{0}}} \left(\frac{N}{q^{1/n_{0}}}+1\right) N^{1+o(1)}= \left(\frac{N}{q^{1/n_{0}}}+1\right) N^{1/n_{0}}N^{2+o(1)}.$$

Answer 2

Really a comment, but I wanted to include a graph.

Can you figure out what happens if you take $\mathcal{M}$ to be $\{1,\cdots,N\}$? Then it does not matter what $q$ is as long as it is larger than $N^2.$ For each possible product $1 \leq r \leq N^2$ let $f(r)$ be the number of factors $a\mid r$ with $\frac{r}{N} \leq a \leq N$. Then the number you want is the sum of $f(r)^2$. It seems it might be possible to work that out. Of course it might be asymptotic to $N^2$. Here are the exponents for $20 \leq N \leq 100$