Talk:Lagrange's four-square theorem

Problem with Jacobi's Combinations

I can't seem to find information on this elsewhere, but this seems to fail on very simple cases, such as the number 5. Since 5 is odd, and has only itself as a divisor (or do we count the trivial divisor 1?) We should have 8(5) = 40 possible combinations of sums of squares. But there exists only one: 2² + 1² + 2(0²) = 5 Assuming we allow all permutations of order, that only gives us 4!, and this is not unique to this decomposition either. Allowing squares of negative numbers naively seems to be an unnecessary complication, but I still don't see how this works. Explanation someone please? --71.11.128.29 01:36, 4 January 2007 (UTC)

Actually "allowing all permutations of order" gave you 4!/2 = 12, because 2 of the 4 numbers being permuted are identical(0 and 0). But then allowing pluses and minuses on 1 and 2 multiplies the 12 by 4, giving 48 in all. Since 8 times (1 + 5) = 48, Jacobi's theorem is verified for this example. Hope this helps. Thanks for the thoughtful question.Rich 01:50, 4 January 2007 (UTC)

The article should very clearly explain that Jacobi's formula counts integer (as opposed to natural) solutions. To the best of my knowledge, there is no useful formula for the number of the natural solutions, although Emil Grosswald wrote a book on the subject of counting natural solutions for the case of representations of an integer as a sum of $k$ squares. 129.15.11.123 06:56, 7 March 2007 (UTC)

Question

Why does it matter if the integers are negative?

negative integers can't be represented as the sum of squares. Horndude77 19:02, 16 July 2005 (UTC)

He was referring to "More formally, for every positive integer n there exist non-negative integers x1, x2, x3, x4". Since negatives square always square up to positives I don't see any reason why the should be non-negative. I've edited accordingly. --poorsod^talk 16:53, 23 May 2007 (UTC)

Hurwitz quaternions is a non commutative ring. unique factorization domain is used in case of commutative rings. Why that is used here? I want to point out that unique factorization domain, called UFD for short, is any integral domain in which every nonzero noninvertible element has a unique factorization. Hurwitz quaternions is not UFD. — Preceding unsigned comment added by 110.234.113.82 (talk) 08:36, 4 May 2012 (UTC)

Removal

I removed the following:

"In 2005, Zhi-Wei Sun proved that any natural number can be represented as the sum of a square, an even square and a triangular number."

This may or may not be true but why does it have to be here? -- Taku 01:11, July 19, 2005 (UTC)

Word kevinbocking 22:18, 3 July 2007 (UTC)

Proof

The proof appears in ja article. I might translate it to here if I have time. Anyone interested to see it? -- Taku 07:40, 18 July 2007 (UTC)

Fermat's proof?

The article says (uncited) "An earlier proof by Fermat was never published." Does this proof definitely exist, or is it another of those marginal notes like the one about his last theorem? AndrewWTaylor 17:20, 24 October 2007 (UTC)

It does indeed exist. According to Wolfram's MathWorld: "Although the theorem was proved by Fermat using infinite descent, the proof was suppressed. Euler was unable to prove the theorem. " —Preceding unsigned comment added by 71.88.108.163 (talk) 03:18, 8 July 2008 (UTC)

Ramanujan's General Solution

By symmetry, the statement "if we assume, without loss of generality, that a ≤ b ≤ c ≤ d then there are exactly 54 possible choices for a, b, c and d such that (*) is solvable in integers x1, x2, x3, x4 for all n" is meaningless. Each x_n is a square.

Borat fan (talk) 23:36, 17 July 2008 (UTC)

I don't understand what you were trying to say. Eric Kvaalen (talk) 18:51, 14 October 2013 (UTC)

Jacobi's Four Square Theorem

In the article currently, it says that the total number of ways a given positive integer n can be represented as the sum of four squares is eight times the sum of the divisors of n if n is odd and 24 times the sum of the odd divisors of n if n is even. Other sources, e.g. this one say it is eight times the sum of all its divisors which are not divisible by 4. These are equivalent (although not immediately obvious in some cases). It might be helpful to give both formulas. MSGJ (talk) 13:38, 11 August 2008 (UTC)

On reflection I have moved the stuff on Jacobi's theorem to a new article Jacobi's four-square theorem because although related to the Lagrange theorem, it seems not to belong here. MSGJ (talk) 13:38, 11 August 2008 (UTC)

There are some gaps in this 'proof' !

I think I have found some gaps in this pseudo-proof. First of all: where do we use the fact that 'The generalized Euclidean algorithm' works ? The second one: I am not sure but I think that Hurwitz integers haven't got a property of unique factorization. Because: 2 = (1+i)(1-i) = (1-j)(1+j) = (1-k)(1+k) The last one: even if this proof is correct, we only show that 'p' is a sum of four square of integers or four square of half-integer. — Preceding unsigned comment added by 89.231.20.14 (talk) 08:29, 9 July 2011 (UTC)

Also the norm link is wrong, it goes to the metric space definition instead of the group theory one. — Preceding unsigned comment added by 46.64.84.54 (talk) 12:12, 31 October 2011 (UTC)

The proof is flawed. Hurwitz integers do have a kind of unique factorization, but it's not the kind associated with commutative rings. In particular, it's unique up to unit migration, meta-commutation, and recombination. More information can be found here [1]. Conway and Smith also covered this here [2]. — Preceding unsigned comment added by 71.232.22.170 (talk) 03:31, 3 October 2013 (UTC)

I have rewritten parts of the proof to avoid invalid references to unique factorization, and I believe it is correct now. However, I wonder whether it’s a good idea to use fancy abstract algebra like (not quite) Euclidean domains and irreducible elements at all. The relevant part of the proof can be framed as a quite elementary infinite descent argument, and one can do it with Lipschitz quaternions instead of Hurwitz. It does not seem to me to be significantly longer than the current proof, and it might be more accessible.—Emil J. 20:03, 7 October 2013 (UTC)

It ought to be unnecessary to debate how to write a correct proof: simply use what is given in the independent reliable source that you are using, and cite it. Otherwise, it's original research, and it gets taken out. Deltahedron (talk) 21:33, 22 March 2014 (UTC)

Norm

A few months ago I changed the "norms" mentioned to be norms according to the definitions given in both Norm (mathematics) and Quaternion. But User:EmilJ reverted all that to the "norms" that were there before, which are actually the squares of the norms, with the comment "Calling this a norm is a perfectly standard terminology, and the extra square roots only serve to obfuscate the proof." It's true that the square of the usual norm is a "field norm", but I don't think it's standard simply to call this "the norm" of a quaternion. Eric Kvaalen (talk) 18:51, 14 October 2013 (UTC)

There are any number of sources that call it exactly that: the first page of a Google search gave [3][4][5][6][7]. It is obvious from your contribution list that your background is in analysis and continuous structures. Here you are in a different universe, this article is about quite discrete algebra (or rather, algebraic number theory). Different fields of mathematics use different terminological conventions, for good reasons. Face it. Now I noticed that you made the same misguided edit to other articles on integer quaternions, I’m going to revert that as well.—Emil J. 11:49, 15 October 2013 (UTC)

I only changed the article on Hurwitz quaternions. Are you going to change the quaternion article as well? I had nothing to do with that. Eric Kvaalen (talk) 12:52, 15 October 2013 (UTC)

The quaternion article does not deal with algebraic integers, so there would be no point in introducing this concept of a norm there. (I wrote “other articles” before I realized that Lipschitz quaternion and Hurwitz quaternion are the same article. Sorry for the confusion.)—Emil J. 14:38, 15 October 2013 (UTC)

Algorithms

Is there a reference to an independent reliable source for the Python and Lisp code, or is this original research? Deltahedron (talk) 21:30, 22 March 2014 (UTC)

For the Python code that I added, the pseudo code came from [link] which is a stack exchange thread. It is not a published result (as far as I know) and doing an hour of research just now makes me believe that one is not easily locatable for it. However, stackexchange is a self-regulated base of users and the code came from the user on the computer science stackexchange with highest rating on "gives good answer" (reputation). Feel free to remove it if you must. BeaumontTaz (talk) 22:27, 22 March 2014 (UTC)

This is a good question, but I honestly don't know the answer. The CL code I inserted can be viewed as a simple translation of the definition into Common Lisp. It iterates over all (ordered) 4-tuples of non-negative integers at or below square root of n, and checks if squares add up to n for each one. Specifically because the algorithm is so literal, I think it cannot be viewed as any kind of research, let alone original. This is akin to rewriting a mathematical formula in a slightly different, but obviously equivalent way.

The python code, on the other hand, implements a slightly more advanced algorithm. This is more of a grey area. I would still be inclined to say it's not research, but may be readers with less math or CS experience will disagree. So I think it would be great if something could be cited, but probably not necessary.

Lastly, I'd like to note that the python code does not work upon copy-pasting it into a freshly started interpreter, which is a huge use case for these code snippets. I think it has to do with math library functions not being visible by default. If that could be amended, it'd be great. melikamp (talk) 16:57, 27 March 2014 (UTC)

I think "your" LISP implementation is so trivial as to not being worthy of inclusion. Pseudocode would probably be better; something like (correcting to produce only sorted lists — Arthur Rubin (talk) 17:12, 30 March 2014 (UTC))

for each i in 0..sqrt(N)

for each j in i..sqrt(N)

for each k in j..sqrt(N)

for each l in k..sqrt(N)

if (i^2 + j^2 + k^2 + l^2 = N)

output (i,j,k,l)

end if

end for

end for

end for

end for

And, rather than the Python code, I would probably include simplified C++ code (the stackexchange answer, simplified and converted to modern C++); for example, List<List<int[]>> would be replaced by forward_list<pair<int,int>>[N+1] . — Arthur Rubin (talk) 00:10, 30 March 2014 (UTC)

Arthur, I don't understand why triviality of the code has anything to do with what we are discussing here, or why indeed trivial code cannot be included here. On the contrary, it is non-trivial code that is worse, since it is has to be cited, is more likely to have bugs, and few readers can understand it. I personally stumbled upon this page because I wanted to see a piece of code (not pseudo-code, but something I could run) to decompose n as discussed. I added LISP code because (a) for the use case I myself represent, it's nice to have options and (b) python code is a program fragment which doesn't really work on its own.

I don't understand why you think C (or C++!) or pseudo-code would be better. Neither can be copy-pasted and run, which is what many people want to do when they look up these topics. melikamp (talk) 00:20, 30 March 2014 (UTC)

Or, if you want to avoid original research, and stackexchange has the appropriate copyleft, then we could include the stackexchange code verbatim. — Arthur Rubin (talk) 00:14, 30 March 2014 (UTC)

Please, give us one good reason why LISP snippet does not belong here. Please also explain why you thought it was a good idea to go ahead and start deleting before contributing to already started discussion. I thoroughly rebutted your argument at your talk page: the argument which was factually incorrect, and contradicted itself. If you cannot state your rationale, then please stop deleting. melikamp (talk) 00:24, 30 March 2014 (UTC)

MOS:MATH#Algorithms. "If source code is used always choose a programming language that expresses the algorithm as clearly as possible." And you didn't touch my argument on my talk page. Technically, "rebut" X means to make a statement contradicting X, even if the statement has no basis in fact or (here) policies and guidelines. Personally, I do not think any implementations are necessary, although the claim that the Python/C++ algorithm is O(N) (even though incorrect) might make it significant, once the algorithm is properly filtered so we don't need to test whether a generated example is already in the list. — Arthur Rubin (talk) 02:18, 30 March 2014 (UTC)

Normally, I would say that LISP is never "a programming language that expresses the algorithm as clearly as possible.", but I could be wrong. — Arthur Rubin (talk) 02:20, 30 March 2014 (UTC)

The CL snippet is, arguably, clearer, since it's a simpler algorithm. Unless you explain your position concerning LISP in more detail, we have no choice but to regard it as irrational.

I indeed rebutted, i.e. "repulsed" your arguments, but you seem to be coming up with new ones all the time. First you said the CL code returned all tuples, not just sorted ones, which was factually incorrect. Then you said two implementations of the same algorithm should not be given, right after saying that CL and Python gave different algorithms (which is true), contradicting yourself. Then you claimed the CL code was too trivial, but did not explain why that matters. Now you seem to be saying that the most straightforward algorithm on the page was "unclear" because ... all LISP is unclear? So it was trivial and unclear at the same time? All the while, you advocate using C, which is probably the worst language to describe algorithms in, besides Assembly. In general, higher level languages should be used. The MOS tacitly agrees by suggesting pseudo-code. Also, you never addressed my claim that snippets in different languages are indeed useful here, because at least some of the people reading these pages would like to copy-paste code into interpreters. I know I do; this is how I found this page in the first place: I wanted to decompose numbers into a sum of 4 squares. I tried the Python code, and it didn't work out of the box (although it did after I fixed it). I also noticed it was a tad too fancy for a general reader to understand. Am I really alone here? melikamp (talk) 15:38, 30 March 2014 (UTC)

My mistake as to it not producing only sorted entries. However,most people have difficulty in reading LISP. Anyone who thinks

if (= n (+ (* a a) (* b b) (* c c) (* d d)))

is not more confusing than

if (n == a*a + b*b + c*c + d*d)

needs a reality check. MOS:MATH#Algorithms seems to suggest that, in the absence of a reason to use a particular language, pseudocode should be used. That is certainly the case, here. The most recent discussion that I can find is at Wikipedia talk:WikiProject Mathematics/Archive/2012/May#Article as code repository?. Suggestions there include

(1) code or pseudocode is an appropriate way of describing algorithms, when that algorithm is relevant for the content of the article; (2) pseudocode is generally preferable to code, but code may be clearer in some cases when using language-specific features that are difficult to describe in pseudocode such as the yield keyword and regular expressions of the example you link to;

Even if you wanted to include the trivial algorithm you've programmed in LISP, this seems to violate the independent clause of (1); the algorithm is not relevant to the content of the article. Point (4) would allow me to reprogram the stackoverflow code in modern C++, and it might be relevant to the article as the algorithm is claimed to be O(N). — Arthur Rubin (talk) 17:08, 30 March 2014 (UTC)

As an aside, the translation from C++ into Python seems to be WP:OR, since it wasn't done correctly.... — Arthur Rubin (talk) 02:21, 30 March 2014 (UTC)

By the way, stackexchange does have the correct copyleft, so we could copy the program to Wikipedia, if we provide the correct attribution. — Arthur Rubin (talk) 02:24, 30 March 2014 (UTC)

The test

if X not in P

is not O(1), but the (now Python) algorithm could be patched so as not to need it. — Arthur Rubin (talk) 02:28, 30 March 2014 (UTC)

I've patched the Python algorithm, using https://docs.python.org/ as s reference manual. Further changes which would help:

1. The "b" loop now (almost) always breaks, so using an arbitrary endpoint >= sqrt(int(N-a)) + 1 would work; there's no need to compute the sqrt at each "a" iteration
2. If the "k" loop is reversed, a similar break could be used
3. The "j" and "k" loops could be replaced by enumeration loops
4. What does "range" do if the endpoint is not an integer?
5. Modern "range(x)" seems to be old "range(0,x)", but I could be wrong.

— Arthur Rubin (talk) 08:37, 4 April 2014 (UTC)

The code no longer works. Your removal of the "is in" no longer allows the code to function correctly. For instance where N = 6 there should be the point 2,1,1,0 however it no longer finds it. Yes, "is in" is not in O(n) time, however, it's in O(len(P)) time where len(P) is usually much less than n. Either revert to the old code or remove this code from the article, please.

BeaumontTaz (talk) 02:56, 31 May 2014 (UTC)

Removal of the "is in" code can only result in duplications; it cannot result in any loss of information. — Arthur Rubin (talk) 15:23, 13 June 2014 (UTC)

It was more-so the inequality check that you used to replace it that caused the issues. But it's a null point now. BeaumontTaz (talk) 05:44, 15 June 2014 (UTC)

• This arguing over whether the code works or not should be capable of being resolved by finding an independent reliable source that tells us what to write. A blog post on stackexchange is not usually a reliable source: in this case it quotes no references, except for Wikipedia, which leads to circular referencing. In the absence of any reliable source, I think it best to remove the code. If it's important to include it, then there should be an independent reference to cite. Deltahedron (talk) 06:32, 31 May 2014 (UTC)

Proposed C++ algorithm (using C+11 standard)

 // the largest integer whose square is less than or equal to N
    public int SquRt(int N)
    {
        return (int)std::sqrt((double)N);
    }

#typedef pair<int,int> pairint; 
#typedef pair<pairint, pairint> quadint; // so, I'm lazy
#typedef forward_list<pairint> list2;
#typedef list<quadint> list4;
using std;

// Return a list of all integer quads (a,b,c,d), where:
    //      a^2 + b^2 + c^2 + d^2 = N,
    // and  a >= b >= c >= d,
    // and  a,b,c,d >= 0
    public list4 FindAllFourSquares(int N)
    {

        list2[] Sqr2s = new list2[N+1];

// Sqr2s[i], for 0 <= i <= N
// will be a list of all pairs (a,b) such that a^2 + b^2 = i,
// in increasing order

        list4 Sqr4s;
 
        for (int i = SquRt(N); i >= 0; i--)
        {
            for (int j = 0; j <= i; j++)
            {
                int sum = (i * i) + (j * j);
                if (sum > N)
                {
                    break;
                } else {
                    Sqr2s[sum].push_front(pair(i,j));
                }
            }
        }


        for (   int i=N, int j=0;
                i>=j;
                i--, j++ )
        {
            if (Sqr2s[i].empty() || Sqr2s[j].empty() )
            {
                continue;
            }

            for (pairint & p1 : Sqr2s[i])
            {
                for (pairint & p2 : Sqr2s[j])
                {
                    if (p1.second >= p2.first)
                    {
                        Sqr4s.push_back(pair(p1,p2));
                } else {
                        break;
                }
            }
        }
    }
    return Sqr4s;
}

No "lang="c++"? Anyway, this is adapted from the stackexchange code. Being lazy, I left the sequence (a,b,c,d) as pair(pair(a,b),pair(c,d)). If you want to translate that into tuple<int, int, int, int> or another representation of a sequence of 4 integers, go ahead.

— Arthur Rubin (talk) 21:23, 30 March 2014 (UTC)

• I still see no reason why we should include any kind of code for the trivial algorithm being discussed here. Deltahedron (talk) 06:37, 31 March 2014 (UTC)

OK, OK, I am being slowly convinced that Wikipedia is probably not the best place for code snippets which are not relevant to the content of the article, and it seems to be the case here. But then I would be against adding any more algorithms here. The python code seems just interesting enough to be included. And I am entirely against adding anything in C++, which is almost as far from pseudo-code as one can imagine. melikamp (talk) 15:17, 1 April 2014 (UTC)

Use of Euler's 4-square identity in proof

The proof (at Lagrange's four-square theorem#The classical proof) is unsourced (and originally incompletely translated from, apparently, French), and the use of Euler's four-square identity doesn't work. — Arthur Rubin (talk) 18:47, 28 June 2014 (UTC)

Yes, sorry, it's a translation of the french page I wrote a few hours before. z₁ is congruent to the sum of the y_i², which is mr, and the other z_i are congruent to 0 modulo m for a similar reason. I will mention this in the proof. I have to recall my sources. This is a short version of a proof in a master's course in number theory that has been given for years by myself and other people … (see below) Sapphorain (talk) 21:41, 28 June 2014 (UTC)

There is indeed more needed in the argument at this point, and it uses the precise formulation of Euler's four-square identity to show that each of the z is divisible by m: details are at page 400 of Hardy, G. H.; Wright, E. M. (2008) [1938]. An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921986-5. MR 2445243. Zbl 1159.11001.. Deltahedron (talk) 20:31, 28 June 2014 (UTC)

… It is evidently very similar to the Hardy and Wright version of Lagrange theorem, but is somehow different. And simpler I think: no need to consider separately the cases m even, m odd (m₀ in HW).Sapphorain (talk) 21:41, 28 June 2014 (UTC)

I'm sorry; our (Wikipedia's) present example formula for Euler's 4-square identity is odd in that there is exactly one minus sign in each of the 4 squares. I'll change it to a more standard version there, to make it more clear here. — Arthur Rubin (talk) 00:03, 29 June 2014 (UTC)

Yes, it didn't work with the former sign convention, thanks for changing them! However we still read below "The sign convention used above corresponds to the signs obtained by multiplying two quaternions": I guess it's not true anymore(?) [By the way, since a proof of Lagrange theorem by using quaternions is anachronical, I think it is justified (at least here) only if it becomes simpler compared with the original proof: it appears far from being the case here, I find the proof as presented in the article long and clumsy. Maybe it should be moved to the article on quaternions?].

I recalled my original source, it's Landau (1927), which is probably very close to Lagrange original proof (unfortunately I don't have access to this one). I will add the reference. The proofs by HW and Niven-Zuckerman are very similar. But all three of them consider separately the cases m even, m odd, which is not necessary.Sapphorain (talk) 08:56, 29 June 2014 (UTC)

I think perhaps the sign convention now corresponds to $b{\bar {a}},$ as quaternions. I probably should change it to $a{\bar {b}}.$ — Arthur Rubin (talk) 02:40, 2 July 2014 (UTC)

Use of Euclidean algorithm in proof?

The current lead of the Euclidean algorithm article includes, "Finally, [the algorithm] is a basic tool for proving theorems in number theory such as Lagrange's four-square theorem and the uniqueness of prime factorizations." When I followed the link to this article, I didn't see the Euclidean algorithm mentioned anywhere. There is the statement that the Hurwitz quaternions have some properties of a Euclidean domain, but nothing about the Euclidean algorithm.

The Euclidian algorithm article is a featured article. Surely it has passed multiple levels of review. Any ideas why that statement was added to the lead?

Thanks, 24.240.67.157 (talk) 23:11, 10 February 2016 (UTC)

Thanks for this remark. I indeed don't see that there is any use of the Euclidean algorithm in any proof of the four-square theorem. In case I am mistaken, I put a "citation needed" tag on this assertion. Unless somebody provides reference to a proof using the algorithm, I will delete the assertion. Sapphorain (talk) 15:51, 19 February 2016 (UTC)

Quaternions are not commutative by multiplication

There's a problem with a proof in the section "Proof using the Hurwitz integers"

Since quaternion multiplication is associative, and real numbers commute with other quaternions, the norm of a product of quaternions equals the product of the norms:

$\mathrm {N} (\alpha \beta )=\alpha \beta ({\overline {\alpha \beta }})=\alpha \beta {\bar {\beta }}{\bar {\alpha }}=\alpha \mathrm {N} (\beta ){\bar {\alpha }}=\alpha {\bar {\alpha }}\mathrm {N} (\beta )=\mathrm {N} (\alpha )\mathrm {N} (\beta ).$

Since quaternions are not commutative by multiplication, one cannot simply take $\mathrm {N} (\beta ){\bar {\alpha }}=\alpha {\bar {\alpha }}\mathrm {N} (\beta ).$

LAGRANGE'S FOUR SQUARE THEOREM

THIS THEOREM HAS SOME CONTRADICTION. LIKE IN NUMBER 96 = 9² + 3² + 2² + 1² + 1²

    = 81 + 9 + 5 + 1 + 1

IT NEEDS 5 SQUARES TO MAKE THE NUMBER 96 Ishan Shekhar (talk) 14:56, 15 June 2021 (UTC)

96 = 64 + 16 + 16 + 0 --Sapphorain (talk) 17:49, 15 June 2021 (UTC)

Subscripts

The subscripts in $$p=a_{0}^{2}+a_{1}^{2}+a_{2}^{2}+a_{3}^{2}$$ are too hard to read with the exponents, so I think it best to rewrite this as $$p=a^{2}+b^{2}+c^{2}+d^{2}$$. 47.211.220.38 (talk) 16:22, 7 April 2023 (UTC)