Welcome to MathOverflow

Question

10

2

This question is motivated by question http://mathoverflow.net/questions/26838/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?

flag	asked Jun 3 2010 at 12:32 Roland Bacher 6,916●10●37

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 2010 at 12:54

1

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 2010 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 2010 at 13:33

2

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 2010 at 15:05

1

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 2010 at 18:38

show 3 more comments

Will Jagy · Answer 1 · 2010-06-03 18:22:53Z UTC

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 http://mathoverflow.net/questions/22552/ 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.

SandeepJ · Answer 2 · 2010-06-17 22:50:52Z UTC

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

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.