1
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 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$
    – Henri Cohen
    Commented 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$
    – Josu Etxezarreta Martinez
    Commented 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$
    – Henri Cohen
    Commented Mar 1, 2019 at 10:04
  • $\begingroup$ Thank you, now I understand what you were saying there. $\endgroup$
    – Josu Etxezarreta Martinez
    Commented Mar 1, 2019 at 11:38

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .