Jump to content

Talk:Schur's theorem

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Combinations of relatively prime integers

[edit]

A recent addition to this article said:

In combinatorics, Schur's theorem states that any sufficently large

integer can be obtained from a linear combination of a fixed set of relatively prime numbers. In other words, if the numbers are relatively prime (their greatest common divisor is 1), there exists a number such that every integer greater than is equal to for some integers . For example, since 2 and 5 are relatively prime, there exists a number such that any amount of money greater than this number can be changed exactly with coins of denomination 2 and 5 (see [[coin problem]]).

However, I think this might be mistaken. I believe this result is due to J. J. Sylvester, and is sometimes known as "Sylvester's theorem", although the Wikipedia entry for Sylvester's theorem is about something else. I have reverted the article pending confirmation one way or the other. If I am incorrect, my apologies. -- Dominus 20:27, 30 October 2005 (UTC)[reply]

For example, the page Sylver coinage says "A theorem of James Joseph Sylvester, after whom the game is named, shows that every game must eventually end, i.e. the players cannot avoid having to say 1 forever." And many sources agree that Sylvester did prove the result for n=2, and call this result "Sylvester's theorem". More investigation forthcoming, I hope. -- Dominus 20:30, 30 October 2005 (UTC)[reply]
In More Games of No Chance, John Horton Conway says "This game is played by two players who take turns in naming positive integers which cannot be made up from previously named numbers. The person who names 1 looses, otherwise the game is trivial. This game is finite, as can be shown by result of J. J. Sylvester." I think that's pretty authoritative. -- Dominus 20:34, 30 October 2005 (UTC)[reply]

I have based what I wrote on this document, which calls this result Schur's Theorem (page 33). It is however possible that the authors mean that this result can be proved using a theorem by Schur, not that the result is attributed to Schur (the references you gave are quite convincing). We can probably ask the authors about that for confirmation. Paolo Liberatore (Talk) 21:47, 30 October 2005 (UTC)[reply]

I have just realized that Sylvester's result and what I and the authors above call Schur's theorem may not be the same after all:

  1. Sylvester's theorem (at least as it is formulated above) says that there is no infinite set of positive integers such that every integer in the set is not a linear combination of the others;
  2. the theorem that I have found in that technical report is that every sufficently large integer can be obtained by a linear combination of a set of relatively prime numbers.

It looks like they are not trivially equivalent. In fact, the second condition may not imply the first because we could in theory keep using integers that are not relatively prime (the proof in that case would go that we can factor out the common prime factors, I think); the first condition does not imply the first because it does not specify that the game ends when the numbers already taken are relatively prime. Paolo Liberatore (Talk) 22:01, 30 October 2005 (UTC)[reply]

I assume that there is no problem with the reintroduction of the part to the article, since nobody has commented in three weeks (I also left a note at Dominus' talk page [1]). I will reintroduce the paragraph, then. Paolo Liberatore (Talk) 17:59, 18 November 2005 (UTC)[reply]

Another Schur's theorem

[edit]

There's one more known Schur's theorem (I found it in Spivak's book on Differential Geometry). It says that the sectional curvature of an isotropic Riemannian manifold is constant.

Thanks for the information. You can add it to the article, of course. Just a question: is it called Schur's theorem or Schur's lemma in the book? Paolo Liberatore (Talk) 19:03, 21 November 2005 (UTC)[reply]