## Estimating the probability of co-occurrence of a set of positive integers

How to estimate the probability of co-occurrence of the positive integers $c_i$ and $d_i$, $1 \leq i \leq t$ drawn from the uniform range $1$ to $2^k-1$, such that $\Sigma^t_{i=1} c^2_i = \Sigma^t_{i=1} c_i\times d_i$ and $\forall i, c_i\neq d_i$ hold?

$\forall i, c_i$ and $d_i$'s are drawn from the same distribution, but each pair $(c_i, d_i, \forall i \neq j)$ is drawn from different distribution.

To simplify the problem for the case $t=2$, it is the probability of co-occurrence of four positive integers $c_1, c_2, d_1$ and $d_2$ such that $c^2_1 + c^2_2 = c_1\times d_1 + c_2\times d_2$ and $c_1\neq d_1$ and $c_2\neq d_2$ hold. The pairs $(c_1,d_1)$ and $(c_2,d_2)$ are chosen from two different distributions of the same range $1$ to $2^k-1$.

-
 Surely it will depend on the particular distributions that the numbers are drawn from -- what sort of answer are you looking for? – JBL Oct 14 2010 at 1:02 Let's say the values are uniformly distributed and k=32. I am trying to verify whether the probablity would be close to zero even for smaller values of t such as, 2,3,4,5,...,10. – Neil Oct 14 2010 at 2:45

An approach for the case $t=2$. There are $N^4$ ways of choosing $a,b,c,d$, all between 0 and $N-1$. You want to know how many of them result in $a^2+b^2=ac+bd$. Let's take the case where $\gcd(a,b)=1$ and $a\lt b$. Then you must have $c=a+br$ and $d=b-ar$ for some $r$. This $r$ can't exceed $b/a$, nor can it exceed $(N-a)/b$. So, given $a,b$, the number of pairs $c,d$ is just the smaller of $b/a$ and $(N-a)/b$, suitably rounded. Now you have to sum that over all pairs $a,b$ with $\gcd(a,b)=1$ and $a\lt b$. Then you have to work out what modifications you need to handle the case $\gcd(a,b)=e\gt1$.
EDIT: Fixing $t$ but letting $N$ go to infinity, the probability must go to zero, since, when you've picked all the variables but one, there's only one way to choose that last variable (unless its partner is zero), so the probability should never exceed $2/N$. But maybe I misunderstand the question.
 Thanks for your answer. That's right. If the values are allowed to be zero t can not be held constant. I modified the range in the question. It looks like the frequency of such an event happening is dependent on the number of factors in gcd(a,b) for all a,b. For example, say r = 1/k. When, a=12, b=6 we get, c=9, d=12 (k=2), c=10, d=10 (k=3), c=11, d=8 (k=6) Is there an intuitive way to find the frenquency of such event happening within a range? I need to estimate the probability within the range 1 to 2^32 -1 – Neil Oct 14 2010 at 14:03 I don't understand your comment. I don't understand "$t$ can not be held constant," but I agree that forbidding zero may be useful. I don't understand $r=1/k$; in my answer, $r$ is an integer. If $\gcd(a,b)=e$, then $c=a+(b/e)r,d=b-(a/e)r$ for some integer $r$ chosen so that $c$ and $d$ stay between 1 and whatever. I don't know what you mean by "such event". Another suggestion: calculate the number of solutions for top-of-range = 1, 2, 3, 4 (say) and then look up the resulting integer sequence in the Online Encyclopedia of Integer Sequences. – Gerry Myerson Oct 15 2010 at 5:25 Thanks again for your suggestion. It is clear now, from the relationships of the pairs $(a,c)$ and $(b,d)$, $r$ is bounded by the following: when \$a>b,0