MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 0 down vote accepted

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.

share|cite|improve this answer
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 '10 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 '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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.