# A property of primes congruent to $7\pmod 8$ expressed as sums of four squares.

This question is motivated by question Enumerating representations of an integer as a sum of squares . Consider a prime number $p$ congruent to $7$ modulo $8$. It can thus be written in exactly $(p+1)/2$ ways as a sum of squares of four strictly positive integers.

One way of trying to generate all solutions of $p=a^2+b^2+c^2+d^2$ with $(a,b,c,d)\in\mathbb N^4$ is to start with an arbitrary solution (obtained eg by crystal-ball gazing) $(a,b,c,d)$, to fix one of the parameters, say $a$, and to decompose $b^2+c^2+d^2$ differently as a sum of three squares, if possible.

This works seemingly always. Otherwise stated, associate to a prime $p\equiv 7\pmod 8$ a graph with $(p+1)/2$ vertices indexed by all different decompositions $p=a^2+b^2+c^2+d^2$ with $a,b,c,d\in \mathbb N$ and draw an edge between two vertices $(a,b,c,d),(a',b',c',d')$ if the intersection of $\lbrace a,b,c,d\rbrace$ and $\lbrace a',b',c',d'\rbrace$ is non-empty. Is this graph is always connected? If yes, what is typically the diameter of this graph?

-
Roland, note that in the earlier question $(p+1)/2$ was counted over $\mathbb Z$, not $\mathbb N$ as you have now. So, there are less $(p+1)/2$ vertices! Do you have some computational evidence that the graph is connected? (I really doubt it's true, but I won't run a program myself.) –  Wadim Zudilin Jun 3 '10 at 12:54
Wadim, over $\mathbb{Z}$ the number is $8(p+1)$, so I assume Roland is correct (since these primes cannot be represented by less than 4 squares, for positive solutions we have to divide by 16)... –  Vladimir Dotsenko Jun 3 '10 at 13:13
Thanks, Vladimir! My wireless at home is too slow to check with the previous answer. But still: is there some computational evidence to have the graph connected? –  Wadim Zudilin Jun 3 '10 at 13:33
Yes, I checked for all primes less than 500 and connectedness becomes much easier for larger primes since all coefficients are smaller than $\sqrt p$. If the graph is not connected, then there exists a partition of $\lbrace 1,\dots,\lfloor \sqrt{p}\rfloor\rbrace$ into two disjoint subsets $A\cup B$ with one connected component having only coefficients in $A$ and all other components only coefficients in $B$. Since the number of vertices is much larger than $\sqrt{p}$ this is very unlikely. –  Roland Bacher Jun 3 '10 at 15:05
You could also try drawing an edge only if the quadruples have two entries in common, some interpretation required in the presence of repeated entries, for example if $p \equiv 1 \pmod 3$ we are guaranteed $p = u^2 + 3 v^2.$ Come to mind, any odd number $n$ is represented as $n=x^2 + y^2 + 2 z^2.$ –  Will Jagy Jun 3 '10 at 18:38

Too long for a comment. Your problem reminds me of this. If anything directly helpful comes to mind on your problem I will let you know of course.

Please allow me to draw your attention to the fascinating Markov-Hurwitz Diophantine equation $$x_1^2 + x_2^2 + \cdots + x_n^2 = a \; x_1 x_2 \ldots x_n$$ in positive integers, with $$1 \leq a \leq n$$ as shown by Hurwitz (1907).

See my answer to Numbers characterized by extremal properties especially the Markov tree, Markov (1880) http://en.wikipedia.org/wiki/Markov_number

If, for example, $x_1$ is fairly large , it can be replaced by $a x_2 x_3 \ldots x_n - x_1$ to give another solution with smaller values. This process can be repeated until one arrives at a "fundamental solution" which satisfies a certain inequality: ordered so that $x_1$ is indeed the largest, a fundamental solution has $$2 x_1 \leq a x_2 x_3 \ldots x_n .$$

So a fundamental solution is the root of a tree of solutions for fixed pair $(n,a).$ The first time that a pair $(n,a)$ requires a disconnected forest is $(n=14, a=1)$ one tree with (decreasingly ordered) root $(6,4,3,1,1,\ldots)$ and another tree with ordered root $(3,3,2,2,1,1,\ldots).$

So many things...my conjecture that, for a fundamental solution in nonincreasing order, $5 x_1^2 \leq 9 ( n+6) .$ Finally the right hand side $a \; x_1 x_2 \ldots x_n$ can be replaced by any of those symmetric polynomials where all exponents are at most one, as we still get trees.

-

I won't get into the question of graph connectedness but (assuming it is connected!) I may be able to offer some intuition on the graph diameter problem. You could employ probabilistic methods to get a good bound. You already know the number of vertices (p+1)/2. You need to compute the probability of edge connectivity.

If $R_3(n)$ is the number of ways 'n' can be represented as the sum of 3 squares, then the degree of any vertex, after iterating through all four coefficients, should be $[sum_{i=1}^ {4}(R_3(p- coeff_i) - 1) ]$.

The number of total edges in the graph is upper bounded by $[sum_{i=1}^ {\sqrt{p}} (R_3(i)(R_3(i) - 1))/2 ]$

I can't visualize the distribution of this sum-of-squares graph but you could adapt the methods which were applied in http://www1.cs.columbia.edu/~coms6998/Notes/lecture3.pdf