I am working with so-called Ramanujan graphs which have the property that a lower bound on their girth can be stated. I am reading about those in paper On the Construction of Turbo Code Interleavers Based on Graphs with Large Girth where such graphs are used in order to construct good Turbo code interleavers.

While going through the construction of those graphs, they speak about having to solve the diophantine equation

$a^2+b^2+c^2+d^2=p \quad(in\quad \mathbb{Z})$

where $p$ is an odd prime and $a,b,c,d\in\mathbb{Z}$ are integers that fullfil

  • if $p\equiv1\mod{4}$ then $a>0$ odd and $b,c,d$ are even.
  • if $p\equiv 3 \mod{4}$ then $a>0$ odd; $b,c$ odd and $d$ even

It is stated that such a diophantine equation has several answers and so by using them you can construct the associated Ramanujan graph. However, as I am not an expert in diophantine equations I do not know if such an equation has to have solutions under such assumptions, and if it has, how many solutions should it have. Consequently, I am interested in knowing when does such diophantine equation have solutions, and how can I know (if possible) how many possible answers to such are possible under the conditions given by $p$.

  • 3
    $\begingroup$ The conditions (apart from $a>0$) are automatically satisfied up to permutation. The total number (Lagrange Jacobi) is $8(p+1)$, so since one of $a$ $b$ $c$ $d$ is specified, divide by $4$, and since you ask $a>0$, divide again by $2$, so in every case the answer is that there are $p+1$ solutions. $\endgroup$ Feb 28, 2019 at 15:05
  • $\begingroup$ Thanks for the insight, I had the intuition that there are $p+1$ solutions to the equation. One last thing, what do you mean by Lagrange-Jacobi in the parenthesis? $\endgroup$ Mar 1, 2019 at 9:59
  • 2
    $\begingroup$ Lagrange showed that any $n$ is a sum of 4 squares, and if I am not mistaken, Jacobi showed that the number of such representations is $8(\sigma_1(n)-\sigma_1(n/4))$. $\endgroup$ Mar 1, 2019 at 10:04
  • $\begingroup$ Thank you, now I understand what you were saying there. $\endgroup$ Mar 1, 2019 at 11:38

1 Answer 1


You can find a little bit more about this question in the following famous paper: "Ramanujan Graphs" by Lubotzky, Phillips and Sarnak, Combinatorica,8(3), 261-277, 1988. The discussion is on the second page of the paper.


Your Answer

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

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