# On a number theoretic problem coming from multiuser coding?

Can Chinese remainder theorem be used to solve this problem in multiuser coding?

We have two transmitters sending integers $q,q'>0$ to a common receiver. The duty of the receiver is to recover both $q,q'$. Assume the integers below are sufficiently large.

The received integer is $uq+u'q'+n$ where every letter is an integer above $0$. Suppose we know $u,u'$ and the unknowns are $q,q',n$. We know $0\leq q\leq (u'-1)$ and $0\leq q'\leq(u-1)$ and $gcd(u,u')=1$ (along with $|u-u'|>\beta\min(u,u')$ for some $\beta\in(0,1)$).

Assuming $C(u,u')=uu'-u-u'$ and the received signal satisfies $$uq+u'q'+n< \gamma C(u,u')+\gamma'(u+u')$$ then what is the largest $\gamma,\gamma'$ we can have so that we can have recover $q,q'$ uniquely if $0\leq q\leq(u'-1)$ and $0\leq q'\leq(u-1)$ and $gcd(u,u')=1$ holds?

• I don't understand the order of the quantifiers. The receiver receives some positive integer $X$, they know $u$ and $u'$, so there is some finite number of choices for $(q,q',n)$. Now what? If $n=X-u-u'$ then the receiver can recover $q$ and $q'$ uniquely because they must both be 1. But this can't be what you mean. Can you rephrase "what is the largest $n$ so that we can have recover $q,q'$ uniquely"? What does $n$ depend on here? Who is doing the recovering and what do they know? – Kevin Buzzard Jan 10 '17 at 22:19
• @KevinBuzzard I am trying find an analog with a particular information theory model which sort of gives the bound in the first query. Yes. $q=q'=1$ (if unique works and) will hold. $n$ is kind of noise . There is a capacity above which we cannot decode (that is implicitly in the bound) and I want to see if analogy transfers here. That is if there is an effective polynomial time procedure to find $q,q'$ uniquely if the bounds hold. – 1.. Jan 10 '17 at 22:36
• @KevinBuzzard For second query it is inspired by number theory and coding theory to see if more noise can be tolerated under special correlations (always difficult and important in coding theory but in this special case I want to see existence of special polynomials which may act as inducing correlations in noise). – 1.. Jan 10 '17 at 22:36
• So is the answer to the question "the largest $n$ is $X-u-u'$"? I am not yet interested in motivation, I am simply saying that the question does not yet make sense to me. – Kevin Buzzard Jan 10 '17 at 22:47
• @KevinBuzzard Say if I give you $X=2^{12}q+3^8q'+ 5000$ can you get $q,q'$ uniquely? How about $X=2^{12}q+3^8q'+ 500$? what is the largest $n$ I can use as a function of $u,u'$ such that you can still get $q,q'$ no matter what $X$ I give you based on the function? Fix $X'(q,q')=2^{12}q+3^8q'$. No matter what $X=X'(q,q')+n$ I give you can you tell what $q,q'$ are if $n<B(2^{12},3^8)$ for some $B>0$? What is this bound $B(u,u')$? – 1.. Jan 10 '17 at 22:59

Suppose for example $u' = u + 1$. Even if you restrict $1 \le q, q', n \le 2$, you can't recover $q$ and $q'$, because $u \cdot 1 + u' \cdot 2 + 1 = u \cdot 2 + u' \cdot 1 + 2 = 3u+3$.

• So the right notion here is indeed $|u-u'|$ ok thank you. I also just noticed it in comment above). – 1.. Jan 10 '17 at 23:11
• thank you clarified a bit (in information theory we deal with generic $u,u'$ typically they do not fall close to each other) and we think of asymptotically at large enough integers $u,u'>0$. – 1.. Jan 10 '17 at 23:14
• I am looking for an efficient algotithm. – 1.. Jan 11 '17 at 14:10

Let $C(u,u^\prime) := uu^\prime - u - u^\prime$. By Sylvester's solution to the Frobenius coin problem, every $c > C(u,u^\prime)$ can be represented as $uq + u^\prime q^\prime$ for some $q,q^\prime \geq 0$. It follows that every $c > C(u,u^\prime) + uu^\prime$ has at least one such representation with $q,q^\prime$ strictly positive and every $c > C(u,u^\prime) + 2uu^\prime$ has at least 2 such representations with $q,q^\prime$ strictly positive.

Therefore, if the received integer is greater than $C(u,u^\prime) + 2uu^\prime$ we definitely cannot uniquely recover $q,q^\prime$. If the received integer is below this upper bound then $q,q^\prime$ should be uniquely determined and the noise is thus bounded by $n <= C(u,u^\prime) + 2uu^\prime - u - u^\prime$.

• $n\leq C(u,u^\prime) + 2uu^\prime - u - u^\prime\implies n\leq 3uu'-2u-2u'$? – 1.. Jan 11 '17 at 8:24
• what is the explicit algorithm that overcomes exhaustive search? – 1.. Jan 11 '17 at 14:10
• I don't know if one can come up with an algorithm for $q,q^\prime$ without also having some further information about them and/or $n$ since each $n$ below the bound will give rise to (at most) one solution, but clearly the solution will depend on $n$ itself. – ARupinski Jan 13 '17 at 3:06
• I think there could be a flaw in your analysis. Consider $$uq+u'q'+n$$ where $u,u'$ are $N^{\frac12+\epsilon}$ and $0\leq q,q'<N^{\frac12-\epsilon}$ and $0\leq n<N^{1-2\epsilon}$ holds. Then $C(u,u')\approx N^{\frac1+2\epsilon}$. You say if $$uq+u'q'+n<C(u,u')+2uu'\approx 3N^{1+2\epsilon}$$ then $q,q'$ are unique. – 1.. Jun 9 '17 at 6:03
• But if we want to decode uniquely then for every $n$ the value of $$uq+u'q'+n$$ has to be distinct for every choice of $q,q'$. This means for every $n$ we need that $$uq+u'q'+n$$ has to take $qq'\approx N^{1-2\epsilon}$ different values. Now there are about $N^{1-2\epsilon}$ choices for $n$. For decoding $q,q'$ uniquely at every choice of $n$ then we need $$uq+u'q'+n$$ to be distinct for every choice of $q,q'$ and every choice of $n$. – 1.. Jun 9 '17 at 6:03