# Occurrence of simultaneous small remainders?

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?

• $a < ... < a$ -- this must be a typo? – Włodzimierz Holsztyński Feb 13 '17 at 6:16
• In this version of the problem there is no relation among the $c_i$ anymore, as the $p_j$ can be chosen differently for different $j$. So the problem seems to become one-dimensional: Let $c, m$ be integers, $q>c^4$ a prime number, do there exist $p, p'\in[q/m, q-q/m]$ such that $pc\bmod q\in [0,q^r]]$, and $p'c\bmod q\in [kq^r+1, (k+1)q^r]$ for some $r<1$. Is this interpretation of the question correct? – Jan-Christoph Schlage-Puchta Feb 13 '17 at 18:11
• @Jan-ChristophSchlage-Puchta There could be relations among $c_i$ just as I have posted with summation $\neq0$ lines. A single $p_j,q_j$ has to work for all $c_i$s and I need $k+1$ such $p_j,q_j$. From analysis and for what I think the ETK bound is $q^r\approx q/n^{1/(2t)}$ is possible. If there is a way to remove the $2$ it will be really really hugely important (no exaggeration here) for me. – user94040 Feb 13 '17 at 23:37
• @Jan-ChristophSchlage-Puchta 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? Also is there a converse? – user94040 Feb 14 '17 at 19:34

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.

• In the first case you can still have $c_0=c_1+c_2$, namely if $b/a$ is a solution of $x^2+x=1$. If 5 is not a square modulo $n$, you can probably find other combinations which give contradictions for somewhat larger $k$. In the second case it is difficult to give an algebraic example, but since there are more degrees of freedom, it should be possible to find examples by a computer search. – Jan-Christoph Schlage-Puchta Feb 12 '17 at 18:34
• Is there an example using ETK inequality where people have studied this? The topic is new to me. What is the discrepancy at least for the case $(1)$ I provide here? – user94040 Feb 12 '17 at 18:43
• 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$? Is there a proof or good reference? Is there a converse? – user94040 Feb 13 '17 at 5:53
• I don't get it. I did some simulation. I took $a=22$, $b=27$ and $a^2+b^2 =1213$ is a prime. The sequence is $c_1=b^2-a^2=245$ and $c_2=2*a*b=1188$. Note because $gcd(245,1188)=1$ therefore if $Ac_1+Bc_2=0$ then $c_1|B$ and $c_2|A$ and so the discrepancy of the sequence is at most $\frac1{\min(c_1,c_2)}=\frac1{245}$. So there should be a common integer $m$ such that $m*245\bmod 1213$ and $m*1188\bmod 1213$ should be both in box $[0,\frac{1213}{245}]\times[0,\frac{1213}{245}]\subsetneq[0,5]\times[0,5]$. I could not find any. Is my understanding incorrect? – user94040 Feb 16 '17 at 2:08
• So in the example $$q=a^2+b^2, c_1=b^2−a^2, c_2=2ab$$ we have $y_1c_1+y_2c_2\equiv0\bmod q$ by $y_1=a$, $y_2=−b$ which gives $$a(b^2−a^2)+(−1)b\cdot2ab\equiv a(b^2+b^2)−2ab^2\equiv 2ab^2−2ab^2\equiv0\bmod q$$ and so $M=a=22$. We have $d=2$, $m=\min(c_1,c_2)=245$ and so $$D\ll\frac{1}{a}+\frac{\log^2a}{245}=\frac{1}{22}+\frac{\log^222}{245}\approx\frac{1}{22}+\frac{1}{25}\approx\frac{1}{11.84}.$$ So we can expect one $m$ such that $$(m245\bmod1213,m1188\bmod1213)\in[0,\frac{1213}{11.84}]\times[0,\frac{1213}{11.84}]\subsetneq[102.5,102.5].$$ Is this correct? – user94040 Feb 16 '17 at 22:12

(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$.

• @PatDevin How about just for the case when $n$ is prime. Is there a way to prove the heuristics I have? I do not get anything better than $1$. – user94040 Jan 31 '17 at 3:52
• What do you mean? – Pat Devlin Feb 1 '17 at 3:31
• I mean is it possible to make my estimate rigorous when $n$ is a prime? – user94040 Feb 1 '17 at 6:58