3
$\begingroup$

In Surprising Generalizations, it is mentioned that Chinese remainder theorem and Lagrange interpolation are specific instances of the same thing, my question is what is their common generalisation/abstraction ?

Thank you

PS : Should there be a Generalisation tag ? to be used when one knows a specific concept and is looking for it's generalisation/more-abstract forms?

  • 2
    Did you read the wikipedia article http://en.wikipedia.org/wiki/Chinese_remainder_theorem#Statement_for_principal_ideal_domains? I think it answers your question (at any rate, it's the answer I would give). Namely, both the classical CRT and Lagrange interpolation are special cases of a CRT in more general ring $R$. The most direct generalization is when $R$ is a PID: in particular then one still has an "explicit solution". A more general generalization is to any finite set of comaximal ideals in any commutative ring.2011-07-28
  • 1
    You know, you could have clicked on the names in the question you link to... You would have landed [here (Harry's name)](http://mathoverflow.net/questions/10014/applications-of-the-chinese-remainder-theorem/10017#10017) and [here (Qiaochu's name)](http://www.artofproblemsolving.com/Forum/blog.php?b=10595) - the latter because Q. linked to that thread in a comment to Harry's answer, in case you wonder...2011-07-28
  • 0
    @Theo : I assumed the names link to profiles and not the content that was being referred to, That's why I didn't click them, I did wonder why someone would give refrences to people for helping with an intresting result but not the result itself. Funy enogh I looked at other posts/replies to see if anyone would mention the original post.2011-07-28
  • 1
    Yeah, it is well-hidden :) It took me a moment to figure that out.2011-07-28

2 Answers 2

4

The connection between the two is explained in an old blog post of mine. The Wikipedia article has more details.

3

i would say, Lagrange interpolation is the extension of the CRT for polynomials. This paper gives some examples and tries to answer the question about the connection. I think it's quite understandable.

Greetings

  • 0
    The cited paper says "Moreover, it is still unknown to us if anybody has contemplated this idea [Lagrange interpolation via CRT] before the late 1960’s and early 1970’s when it occurred to Phil Kutzko, who at the time was a graduate student at the University of Wisconsin". I don't recall the precise history but I'm sure this was known long before 1960.2011-07-28
  • 1
    @Bill: None of the following mention it: Birkhoff–MacLane *Algebra* (1967), van der Waerden *Algebra* (1966 rev), Zariski–Samuel *Commutative Algebra* (1959), and Weber *Lehrbuch der Algebra* (1899). B–M seems the most telling, as it explicitly has Lagrange interpolation with the direct proof, then CRT for PIDs, then CRT for Z as a corollary, and asks the reader to give a direct proof. It mentions CRT with ideals in the exercises, etc. I also checked 4 or 5 old algebra textbooks from the 50s and 60s without any luck. It may have been known, but maybe it was not written down in a textbook.2011-07-28
  • 0
    @Bill: According to [this article](http://www.jstor.org/stable/2686805) by Schoenberg it seems to have occurred to Marcel Riesz in the 1950's. Two passages: **1.** *"Sometime in the 1950's the late Hungarian-Swedish mathematician Marcel Riesz visited the University of Pennsylvania and told us informally that the CRP (1) can be thought of as an analogue of the interpolation by polynomials"* **2.** *"My colleague Richard Askey tells me that Riesz' remark is well known to computer scientists, but apparently not to mathematicians."*2011-07-29
  • 0
    @Jack: see my comment to Bill. So the connection was there before. Interestingly, Schoenberg works at Wisconsin. I don't really know what to make of this.2011-07-29
  • 0
    @Theo Yes, I know the Schoenberg article. I'll post some others later.2011-07-29
  • 0
    @Bill: I'm looking forward to that. Just to make sure that you don't miss it: Schoenberg also mentions this article (I haven't looked, yet) I quote Schoenberg: "*Anwendungen des Chinesischen Restsatzes*, Expositiones Mathematicae (1985) 97-148, in which Ubrich Oberst shows that appropriate abstract formulations of the Chinese Remainder Problem can be made the basis of much of Modern Algebra including the main theorems of Galois theory." But probably you know that as well, if you know Schoenberg.2011-07-29
  • 0
    @Theo I once had a copy of Oberst's article. It's a very nice survey iirc. If anyone finds a copy I'd be indebted if they could forward it to my first.last at gmail.com. I'm sure this idea appears in print earlier than 1950, but searching the usual places hasn't turned up anything yet. It's mentioned in symbolic computation papers starting around 1970, since modular reduction techniques play a fundamental rule for computation. So I agree with Askey, though I would say more specifically that it's well known to those working in symbolic computation - not in general computer science.2011-07-29