Representation of a residue modulo prime as a specific product

Question

Let $p$ be a prime number. For every integer $m$, there are integers $u_1$, $u_2$, such that $\lvert u_1\rvert, \lvert u_2\rvert < \sqrt{p}$ and $$m \equiv u_1u_2^{-1} \pmod{p}.$$

Proof of this statement is at the end. I'm interested in generalizing this statement. For example,

Let $p$ be a prime number, $f = \sqrt[3]{p}$. For every integer $m$, there are integers $u_1$, $u_2$, $u_3$, such that $\lvert u_1\rvert, \lvert u_2\rvert, \lvert u_3\rvert < f$ and $$m \equiv u_1^{\pm 1}u_2^{\pm 1}u_3^{\pm 1} \pmod{p}.$$

But this is false. The question is, how large should $f$ be to make the statement true? Can we choose $f = c\sqrt[3]{p}$ for some constant $c$? Probably, no. I think, something like $f = \log(p)\sqrt[3]{p}$ should work. The same question for the products of the form $u_1^{\pm 1}u_2^{\pm 1}\dotsm u_n^{\pm 1}$.

Proof.

Consider the pairs $(a, b)$ such that $0 \le a, b < \sqrt{p}$. There are $(\lfloor\sqrt{p}\rfloor + 1)^2 > p$ such pairs. Hence, we can choose two distinct pairs $(a_1, b_1)$, $(a_2, b_2)$ such that $$a_1m + b_1 \equiv a_2m + b_2 \pmod{p}.$$ Let $u_2 = a_1 - a_2$, $u_1 = b_2 - b_1$. Then $$m \equiv u_1u_2^{-1} \pmod{p}.$$ I tried to generalize this proof, but did not succeed.

Update

This article deals with a similar problem. Theorem 1 implies that $f = p^{\beta + o(1)}$ works if $n \ge 14$, where $\beta = \frac{1}{4}e^{-1/2} \approx 0.1516$. This result is the best possible (in term of $\beta$) until at least the Burgess bound on the smallest quadratic nonresidue is improved.

Answer 1

$\newcommand{\Z}{\mathbb{Z}}$Let $U$ be a subset of the integers $u$ that are nonzero mod $p$ and satisfy $|u|<f$. Consider $V$ the space of functions on $(\Z/p\Z)^\times$, and the following operator on $V$ $$ T \colon F \mapsto \frac{1}{|U|}\sum_{u\in U,\, e=\pm 1}F(u^ex), $$ which is self-adjoint for the natural inner product on $V$.

The eigenvalues of $T$ are the $$ \lambda_\chi = \frac{2}{|U|}\sum_{u\in U}\Re(\chi(u)), $$ where $\chi$ ranges over complex characters of $(\Z/p\Z)^\times$.

Let $\Lambda$ be an upper bound on $|\lambda_\chi|$ for nontrivial $\chi$.

By considering the action on $T$ on the indicator function of two singletons, and decomposing orthogonally to the constant function in $V$, you see that if $\Lambda^n < \frac{1}{p-1}$, then every $m$ is a product of $n$ values $u^{\pm 1}$ for $u\in U$. In other words, your problem is directly related to short sums of Dirichlet characters.

For instance, if you take $U$ the set of primes up to $f$, and assume the Generalised Riemann Hypothesis, then you get $\Lambda = O((\log p)/\sqrt{f})$ (maybe up to some log factors, or after replacing $T$ by a sum with smoothing factors) and therefore you can take $f = O(p^{2/n}(\log p)^2)$.

You should ask someone more knowledgeable about character sums for more bounds.

Answer 2

$\newcommand{\Z}{\mathbb{Z}}$Let me add more detail and precision to Aurel's nice answer. First, the characters of $(\Z/p\Z)^\times$ form an eigenbasis of $V$ with respect to $T$. Indeed, $T\chi=\lambda_\chi \chi$. Now if $I_m$ denotes the indicator function of an arbitrary element $m\in(\Z/p\Z)^\times$, then $(T^n I_m)(1)$ equals $|U|^{-n}$ times the number of representations $m=u_1^\pm\dotsb u_n^\pm$ with $u_1,\dotsc,u_n\in U$. On the other hand, the decomposition $$I_m=\frac{1}{p-1}\sum_\chi\overline{\chi(m)}\chi$$ shows that $$(T^n I_m)(1)=\frac{1}{p-1}\sum_\chi\overline{\chi(m)}\lambda_\chi^n.$$ As $\lambda_{\chi_0}=2$, there exists a representation $m=u_1^\pm\dotsb u_n^\pm$ with $u_1,\dotsc,u_n\in U$ as long as $$(p-2)\Lambda^n<2^n.$$ In other words, $U$ is a good set as long as $$\max_{\chi\neq\chi_0}\left|\sum_{u\in U}\Re(\chi(u))\right|<\frac{|U|}{(p-2)^{1/n}}.$$