# 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 '10 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 '10 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.
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 '10 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<r<(b/a)\times e$, otherwise $0<r<(a/b) \times e$. By "such event" I was referring to the count of such $r$s for all pairs of numbers within a range. It is a great idea to try to find a sequence formed with those counts. The example equation $a^2+b^2=a\times c+b\times d$ has $t=2$. If say $b$ is allowed to be zero, then $t$ becomes $1$. That's what I was trying to mean by "$t$ can not be held constant". – Neil Oct 16 '10 at 4:02