Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
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

2 Answers 2

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.

share|improve this answer

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

See also

  1. Fan Chung's summary on graph diameter http://math.ucsd.edu/~fan/research/diad.pdf
  2. Béla Bollobás. The Diameter of Random Graphs. Transactions of the American Mathematical Society, Vol. 267, No. 1 (Sep., 1981), pp. 41-52 Published by: American Mathematical Society Stable URL: http://www.jstor.org/stable/1998567
  3. Edgar Palmer's book Graphical Evolution
share|improve this answer

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.