2
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – Kevin Buzzard
    Jan 10, 2017 at 22:19
  • $\begingroup$ @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. $\endgroup$
    – Turbo
    Jan 10, 2017 at 22:36
  • $\begingroup$ @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). $\endgroup$
    – Turbo
    Jan 10, 2017 at 22:36
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kevin Buzzard
    Jan 10, 2017 at 22:47
  • $\begingroup$ @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')$? $\endgroup$
    – Turbo
    Jan 10, 2017 at 22:59

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ So the right notion here is indeed $|u-u'|$ ok thank you. I also just noticed it in comment above). $\endgroup$
    – Turbo
    Jan 10, 2017 at 23:11
  • $\begingroup$ 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$. $\endgroup$
    – Turbo
    Jan 10, 2017 at 23:14
  • $\begingroup$ I am looking for an efficient algotithm. $\endgroup$
    – Turbo
    Jan 11, 2017 at 14:10
1
$\begingroup$

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

Improve this answer
$\endgroup$
8
  • $\begingroup$ $n\leq C(u,u^\prime) + 2uu^\prime - u - u^\prime\implies n\leq 3uu'-2u-2u'$? $\endgroup$
    – Turbo
    Jan 11, 2017 at 8:24
  • $\begingroup$ what is the explicit algorithm that overcomes exhaustive search? $\endgroup$
    – Turbo
    Jan 11, 2017 at 14:10
  • $\begingroup$ 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. $\endgroup$
    – ARupinski
    Jan 13, 2017 at 3:06
  • $\begingroup$ 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. $\endgroup$
    – Turbo
    Jun 9, 2017 at 6:03
  • $\begingroup$ 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$. $\endgroup$
    – Turbo
    Jun 9, 2017 at 6:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.