I have reduced one of my problems to a seemingly simple number theoretic problem. I read a bit on diophantine equations in order to find a helpful technique, but my impression was that they always consider settings in the integers and usually polynomials of a variable, while in my case products of variables appear.

I need to know how many solutions in the natural numbers exist for \begin{equation} 2(r*s-u*v)=d \end{equation} with a fixed $d$, $0\leq r,s,u,v \leq d-1$ and $r,s,u,v,d \in \mathbb{N}$. The goal would be to find an function $f(d)$ that gives me the number of solutions for as many values of $d$ as possible. I suspect it will not be possible to find one function for all values, but any non finite subset might be interesting, the larger the better.

Does anyone know how to approach the question?

  • $\begingroup$ Interesting question, quite geometric. "Exact number" is too much to expect, but asymptotics may be accessible. $\endgroup$ – André Nicolas Sep 22 '15 at 15:26
  • $\begingroup$ If you just wanted $2rs - 2uv = 0 \mod d$, things would probably be much simpler. But you want the answer to be exactly $d$, not $2d$ or $3d$ etc. @AndréNicolas is really good on here and I'm inclined to agree with him that perhaps the best you might hope for is some algorithm that doesn't take WAY too long (at least for small enough $d$) that gives an exact answer, or, if you want formulas, then maybe you can get asymptotic formulas. $\endgroup$ – user2566092 Sep 22 '15 at 15:35
  • $\begingroup$ This is equivalent to counting integer matrices with entries in $[0,d)$ having determinant exactly $d/2$. If we decouple the bound on entries from the determinant, then there are asymptotics for a fixed determinant $D>0$ and entries in $[0,n)$ for large $n$, of the form $c_D n^2$ (even more generally, $c_{D,k} n^{k^2-k}$ for $k\times k$ matrices). This is due to Duke, Rudnick and Sarnak. I'm not aware of known asymptotics where the determinant varies with $n$. $\endgroup$ – Erick Wong Sep 23 '15 at 5:17

Suppose $d=2p$, with $p$ an odd prime.
Firstly, I find the number of solutions when the value is a multiple of $d$. Then, I assume these solutions are distributed normally, and use the continuous approximation to estimate the number of solutions when this sum is between $d/2$ and $3d/2$.
If $2rs$ is a multiple of $p$, then either $r=p$ or $s=p$; and $u=p$ or $u=0$ or $v=p$ or $v=0$. There are $d-1$ solutions with $r=u=p$ (as $s=v+1$); $d-1$ with $s=u=p$; $d-1$ with $r=v=p$; $d-1$ with $s=v=p$; but $2$ with $r=s=p$ and $2$ with $u=v=p$, so $4d-8$ altogether. If $r=p,u=0$ there are $d$ solutions $(s=1,v=$anything$)$, and $4d-2$ solutions of this type. So $$S_1=8d-10$$ solutions when the two terms are multiples of $p$.
Now for $2rs$ not a multiple of $p$, I find solutions where $rs=uv\pmod p$. If $u\neq0\pmod p$, then for any $r$ and $s$ there are two possible values of $v$; which gives $N=16p^2(p-1)=2d^2(d-2)$ solutions when $2rs$ and $2uv$ match $\mod p$ but are not multiples of $p$.
Since $r,s,u,v$ are not multiples of $p$, we have:$$\mu=\mathbb E(2rs-2uv)=0\\ \sigma^2=\mathbb{E}(2rs-2uv)^2=8((4d-1)d/12)^2$$
so I expect roughly $$S_2=Nd/\sigma=3\sqrt{2}(2d^2(d-2))/(4d-1)$$ solutions when $2rs$ is not a multiple of $p$.
We also need $rs$ to share no factor with $uv$. The chance they share a prime factor $q$ is $(2q-1)^2/q^4$, so the chance they don't is $\frac{q^4-4q^2+4q-1}{q^4}$. So $S_2$ must be reduced by the factor $$F = \prod_{q\text{ prime}}\frac{q^4-4q^2+4q-1}{q^4}$$ Altogether $S_1+FS_2$ solutions, if $d=2p$

  • $\begingroup$ thank you michael, i can follow your first part where you assume 2rs is a multiple of p. However i am not sure about the second part. In how far is the the assumption of a normal distribution justified? Also what do you mean to use the continous approximation? $\endgroup$ – ckrk Sep 22 '15 at 17:39
  • $\begingroup$ I meant the very rough approximation, that I just take the mean and standard deviation of a parameter; and suppose that the probability it is between two values equals the probability for a continuous normal random variable with the same mean and variance. Since I know the number is a multiple of $d$, I take the normal distribution between $d/2$ and $3d/2$ to estimate the probability it equals $d$. $\endgroup$ – Empy2 Sep 22 '15 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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