polynomial with rational coefficients and integer values
in [Math]
|
Prev: a second patch onto the square-root patch?? #654 Correcting Math
Next: Alright, resolved, this method is only good for a Twin Prime proof #655 Correcting Math
From: christian.bau on 13 Jul 2010 16:31 On Jul 13, 8:45 pm, Axel Vogt <&nore...(a)axelvogt.de> wrote: > christian.bau wrote: > > On Jul 12, 8:22 pm, Axel Vogt <&nore...(a)axelvogt.de> wrote: > >> Let be P(x) = Sum(a(k)*x^k, k=0 .. N) a polynomial function, > >> where the a(k) are rational numbers. > > >> I am looking for a 'handy' criterion when P maps integers > >> to integers - say 'true for enough integers or large primes > >> then yes' or so (sorry for being vague). > ... > > > If the degree of the polynomial is n, and p (x) is an integer for n+1 > > consecutive integers, then p (x) is an integer for all integers x. > > Does it follow from the answers given or is there some direct > proof as well? It seems to be a quite handy criterion. > > PS: Thanks to all (I hope it is ok that lame & general way)! Proof by induction: Let p be a polynomial of degree n, and p (x) = integer for x = m to m+n for some integer m. If n = 0 then p (x) is constant with one integer value, so it maps all integers to integers. Let n > 0. Consider the polynomial q (x) = p (x+1) - p (x) of degree n-1. It has integer values for x = m to m+n-1. By induction q (x) is an integer for every integer x, so p (x+1) - p (x) is an integer for every integer x. p (x) can always be calculated by starting with the integer p (m), and adding or subtracting values of p (x+1) - p (x) which are all integers, so p (x) is an integer for every integer x.
From: Bill Dubuque on 13 Jul 2010 18:12 "christian.bau" <christian.bau(a)cbau.wanadoo.co.uk> wrote: > On Jul 13, 8:45 pm, Axel Vogt <&nore...(a)axelvogt.de> wrote: >> christian.bau wrote: >>> On Jul 12, 8:22 pm, Axel Vogt <&nore...(a)axelvogt.de> wrote: >>>> >>>> Let be P(x) = Sum(a(k)*x^k, k=0 .. N) a polynomial function, >>>> where the a(k) are rational numbers. >> >>>> I am looking for a 'handy' criterion when P maps integers >>>> to integers - say 'true for enough integers or large primes >>>> then yes' or so (sorry for being vague). >> >>> If the degree of the polynomial is n, and p (x) is an integer for n+1 >>> consecutive integers, then p (x) is an integer for all integers x. >> >> Does it follow from the answers given or is there some direct >> proof as well? It seems to be a quite handy criterion. > > Proof by induction: Let p be a polynomial of degree n, and p (x) = > integer for x = m to m+n for some integer m. If n = 0 then p (x) is > constant with one integer value, so it maps all integers to integers. > > Let n > 0. Consider the polynomial q (x) = p (x+1) - p (x) of degree > n-1. It has integer values for x = m to m+n-1. By induction q (x) is > an integer for every integer x, so p (x+1) - p (x) is an integer for > every integer x. p (x) can always be calculated by starting with the > integer p (m), and adding or subtracting values of p (x+1) - p (x) > which are all integers, so p (x) is an integer for every integer x. More generally: exploit the obvious recurrence - as I did below: Date: 24 Oct 2002; Message-ID: <y8zvg3r7kq8.fsf(a)nestle.ai.mit.edu> r.e.s <r...(a)mindspring.com> wrote: (paraphrased) > > CONJECTURE Let F(N) = c1 b1^N + c2 b2^N +...+ ck bk^N, > where ci are complex numbers, and bi are integers. > If F(N) is integral at k consecutive integers, > then F stays integral after (at all larger integers N) The conjecture is in fact true, and the proof is quite easy. HINT: F(N) satisfies a monic integer coef recurrence of degree k (S - b1) (S - b2) ... (S - bk) F(N) = 0, where S is the linear N-shift: S b^N = b^(N+1), S c = c, for c complex. Note: the linear operators S - bi commute, having constant coefs. This recurrence is simply the characteristic polynomial of the linear shift operator S on the vector space C[bi^N]. Here S has diagonal matrix since S bi^N = bi bi^N. Since the matrix has all integer entries, its characteristic poly too has all integer coefs (which is immediate in this special case: multiply the S - bi ). Note: The conjecture was posed by Mark J. Tilford in the original thread in rec.puzzles, see http://google.com/groups?threadm=slrnarc0go.oj7.tilford%40ralph.earthlink.net --Bill Dubuque
From: Rob Johnson on 15 Jul 2010 15:45 In article <8a3u32Fvs9U1(a)mid.individual.net>, Axel Vogt <&noreply(a)axelvogt.de> wrote: >christian.bau wrote: >> On Jul 12, 8:22 pm, Axel Vogt <&nore...(a)axelvogt.de> wrote: >>> Let be P(x) = Sum(a(k)*x^k, k=0 .. N) a polynomial function, >>> where the a(k) are rational numbers. >>> >>> I am looking for a 'handy' criterion when P maps integers >>> to integers - say 'true for enough integers or large primes >>> then yes' or so (sorry for being vague). >... >> >> If the degree of the polynomial is n, and p (x) is an integer for n+1 >> consecutive integers, then p (x) is an integer for all integers x. > >Does it follow from the answers given or is there some direct >proof as well? It seems to be a quite handy criterion. The condition about consecutive values being integers Define the finite difference operator D by Df(x) = f(x+1) - f(x) [1] It follows from the recursive definition of Pascal's triangle that for integer x, D C(x,k) = C(x+1,k) - C(x,k) = C(x,k-1) [2] Fortunately, to prove it for polynomials is not much harder; it's just a matter of collecting common factors and simplifying: C(x+1,k) - C(x,k) = (x+1)x(x-1)...(x-k+2)/k! - x(x-1)(x-2)...(x-k+1)/k! = ((x+1) - (x-k+1)) x(x-1)...(x-k+2)/k! = k x(x-1)...(x-k+2)/k! = x(x-1)...(x-k+2)/(k-1)! = C(x,k-1) Furthermore, we also have C(0,0) = 1 [3a] C(0,k) = 0 for k != 0 [3b] We can use [2] and [3] to prove the following Theorem: For any polynomial, P, of degree n, n --- k P(x) = > D P(0) C(x,k) [4] --- k=0 Proof: Since C(x,k) is a polynomial of degree k, it is obvious that we can write P(x) as a linear combination of the C(x,k): n --- P(x) = > a C(x,k) --- k k=0 All that is left is to determine { a_k }. This is simple because [2] and [3] assure us that n m --- D P(0) = > a C(0,k-m) --- k k=0 = a m QED By translating the argument to P, we get the following Corollary: For any polynomial, P, of degree n, n --- k P(x) = > D P(m) C(x-m,k) [5] --- k=0 Proof: Q(x) = P(x+m) is also a polynomial of degree n, so by [4], we get n --- k Q(x) = > D Q(0) C(x,k) --- k=0 Substituting x -> x-m, and writing Q in terms of P, we get [5]. QED The Theorem and Lemma above not only provide a proof that if a polynomial of degree n takes n+1 consecutive integers to integers, then it can be written as an integral linear combination of combinatorial polynomials, and therefore, takes all integers to integers, but also gives a simple formula for the coefficients of that integral linear combination. For example, suppose P is a polynomial of degree 3 and D D^2 D^3 P(3) = 26 P(2) = 11 15 P(1) = 4 7 8 P(0) = 1 3 4 4 Thus, P(x) = 4 C(x,3) + 4 C(x,2) + 3 C(x,1) + 1 C(x,0) Rob Johnson <rob(a)trash.whim.org> take out the trash before replying to view any ASCII art, display article in a monospaced font
From: Rob Johnson on 15 Jul 2010 15:54 In article <20100714.151151(a)whim.org>, Rob Johnson <rob(a)trash.whim.org> wrote: >The condition about consecutive values being integers Sorry. Ignore that first line. It was left over from a previous iteration. Rob Johnson <rob(a)trash.whim.org> take out the trash before replying to view any ASCII art, display article in a monospaced font
From: Bill Dubuque on 15 Jul 2010 18:52
Rob Johnson <rob(a)trash.whim.org> wrote: > > [...] The Theorem and Lemma above not only provide a proof that if > a polynomial of degree n takes n+1 consecutive integers to integers, > then it can be written as an integral linear combination of > combinatorial polynomials, and therefore, takes all integers to > integers, but also gives a simple formula for the coefficients of > that integral linear combination. That's many centuries old and very well-known, cf. the reference to "finite difference calculus" in my earlier reply. For a much more general modern treatment google "umbral calculus". --Bill Dubuque |