Occurrence of simultaneous small remainders?

Question

Fix $(a,b)=1$, $a<b<2a$ and $a,b>n^{1/(2t)}$ and fix a prime $T\approx n^{\tau+\frac1k}$ where $\tau\geq1$ and $k=2(t-1)$. We can show using exponential sums there is an $m_{_T}$ such that $T/a^{2(t-1)}<m_{_T}<T-T/a^{2(t-1)}$ such that each of $c_{i,T}=m_{_T}a^{2(t-1)-i}b^i\bmod T$ is bound by $T^{\frac{2t-2+\kappa}{2t-1}}$ for some $\kappa=\frac{k(\tau-1)+2}{k\tau+1}>0$. Example if $t=2$ and $\tau=1$ we can get $\kappa=2/3$ and $T^{\frac{2t-2+\kappa}{2t-1}}=T^{8/9}$.

$\underline{\mbox{Problem} 1}$: Assume we have such $c_{0,T},...c_{k,T}$ that are proved to exist using exponential sums. Fix distinct primes $q_j>T^4>\max(c_{i,T})$ for $j\in\{0,\dots,k\}$. Are there integers $p_j$ such that $q_j/\min(c_{i,T})<p_j<q_j-q_j/\min(c_{i,T})$ such that each of $p_jc_{i,T}\bmod q_j$ at $i\neq j$ is bound in interval $[0,q_j^{r+\epsilon}]$ while $p_jc_{j,T}\bmod q_j$ is bound in $[k\cdot q_j^{r+\epsilon}+1,(k+1)\cdot q_j^{r+\epsilon}]$ for some $r\in(0,1)$?

Can we get $r<\frac{k^\alpha}{k^\alpha+1}$ for any fixed $\alpha\geq1$ in this case? If $c_{i,T}$s were uniform then $\alpha=1$ is possible.

---

Note that for every $\alpha_i\in\Bbb Z$ with $|\alpha_i|<n^\frac1{2t}$ and $(\alpha_1,\dots,\alpha_k)\neq(\underbrace{0,\dots,0}_{k\mbox{ times}})$ we have $$|\sum_{i=0}^k\alpha_ia^{2(t-1)-i}b^i|\leq(k+1)n^{\frac{2t-1}{2t}}$$ and if $(k+1)<n^{\frac1{2t}+\tau}$ then $$|\sum_{i=0}^k\alpha_ia^{2(t-1)-i}b^i|<T$$ holds. Moreover since $|\alpha_i|<\min(a,b)$ and $(\alpha_1,\dots,\alpha_k)\neq(\underbrace{0,\dots,0}_{k\mbox{ times}})$ $$0<|\sum_{i=0}^k\alpha_ia^{2(t-1)-i}b^i|<T$$ holds.

This implies $$\sum_{i=0}^k\alpha_i[m_{_T}a^{2(t-1)-i}b^i\bmod T]=\sum_{i=0}^k\alpha_ic_{i,T}\neq0\bmod T$$ as well. It means the discrepancy of the derived sequence $(c_{0,T},\dots,c_{k,T})\bmod T$ is at most $n^{-\frac1{2t}}$.

$\underline{\mbox{Problem} 2}$: Is it possible to get a prime $q>T^4$ such that discrepancy of $(c_{0,T},\dots,c_{k,T})\bmod q$ is at most $n^{-\frac1{t}}$? If so there is an $m'$ such that $$(m'c_{0,T},\dots,m'c_{k,T})\bmod q\in\underbrace{[0,n^{-\frac1{t}}q]\times\dots\times[0,n^{-\frac1{t}}q]}_{k+1\mbox{ times}}$$ holds?

---

Is it always true that if for a given sequence we can exclude a linear relation with coefficients $<n^\delta$ then we can always achieve $r=1-\delta$ for that sequence? Is there a proof or good reference? Is there a converse?

Answer 1

This is not always true. Suppose that $c_1+c_2=c_0$. Then $pc_1+pc_2\equiv pc_0\pmod{n}$. Hence if $pc_1\bmod n$, $pc_2\bmod n$ are in $[0, n^r]$, then $pc_0\bmod n$ is in $[0, 2n^r]$, which falls outside the desired target range provided that $k\geq 3$ and $2kn^r<n$.

If on the other hand there are no linear relations among the $c_i$ with relatively small coefficient, you can use the Erdos-Turan-Koksma inequality to give a bound for the discrepancy of the set of $(k+1)$-tuples $(pc_0\bmod n, pc_1 \bmod n, \ldots, pc_k \bmod n)$ in $[0,n]^{k+1}$. Problem is that to get your statement you would need a discrepancy of size $<n^{-\delta}$, which means that you have to exclude the existence of a linear relation with coefficients $<n^\delta$, which in general is difficult. However, at least you would get quantitative bounds for the number of tuples for which your assertion fails. One should be able to prove that for every $\epsilon>0$ there is some $\delta>0$, such that the probability that a random tuple does not satisfy your assertion for $r=1-\delta$ is $<n^{-1+\epsilon}$.

In more details: The Erdos-Turan-Koksma inequality states that for a sequence $(\vec{x}_i)_{i=1}^N$, $\vec{x}_i\in[0,1]^d$, the discrepancy is up to a constant bounded by $$ \frac{1}{M} + \underset{\vec{y}\neq\vec{0}}{\underset{i=1, \ldots, d}{\sum_{|y_i|\leq M}}}\prod_{i=1}^d\frac{1}{\max(1, |y_i|)}\left|\frac{1}{N}\sum_{k=1}^Ne(\langle \vec{x}_i, \vec{y}\rangle)\right|, $$ where $e(t)=e^{2\pi i t}$. Put $m=\min(c_i)$. We can estimate the exponential sums as $$ \sum_{p=q/m}^{q-q/m} e\left(\sum_{j=1}^d x_{ij}y_j\right) = \sum_{p=q/m}^{q-q/m} e\left(\sum_{j=1}^d pc_jy_j/q\right) = -\sum_{p=-q/m}^{q/m} e\left(\sum_{j=1}^d pc_jy_j/q\right)\ll \min\left(\frac{q}{m}, \frac{1}{\|\sum c_j y_j/q\|}\right), $$ where $\|t\|$ denotes the distance to the nearest integer, and we assumed that $\sum c_j y_j\not\equiv 0\pmod{q}$. Using only the first term in the $\min$-expression, we get for the discrepancy the bound $$ D\ll\frac{1}{M} + \underset{\vec{y}\neq\vec{0}}{\underset{i=1, \ldots, d}{\sum_{|y_i|\leq M}}}\prod_{i=1}^d\frac{1}{\max(1, |y_i|)}\frac{1}{m} \ll \frac{1}{M}+\frac{\log^d M}{m}, $$ where $M$ has to be chosen so small that there are no integers $y_i$, $1\leq i\leq d$, $|y_i|\leq M$, $\vec{y}\neq \vec{0}$.

The implied constants are reasonable, as long as $d$ is rather small. There is one factor $(3/2)^d$ coming from the Erdos-Turan-Koksma inequality itself, and a factor $2^d$ in front of the second summand of the final result coming from the fact that we actually add up 2 harmonic series.

Answer 2

(Too long for a comment.)

Your heuristic seems good to me at first blush, though it's not literally correct as is for a few reasons. The first thing to perhaps worry about is that for fixed $p$, the random variable $p c_i$ need not be uniform. For instance, if $n=2k$ and $p=k$, then half the values of $p c_i$ will be too big. But if $n$ is prime, and $p\neq 0$ then $p c_i$ is literally distributed uniformly (if $c_i$ is). Then your argument seems reasonable, and you'd get exactly the $r$ you mention (namely anything larger than $k/(k+1)$) for the expected value to go to infinity. If you want to take $k$ points, you'd get anything larger than $1 - 1/k$. Second issue: Some work needs to be done here in that if $X$ is the number of values $p$ that work, then you need to estimate the variance of $X$. But I'd guess this is probably much smaller than the mean squared, so a simple second-moment method would likely suffice to get the bound on the probability that $X=0$.