(some trig trivia at end —rwg) ---------- Forwarded message --------- From: Julian Ziegler Hunts <julianj.zh@gmail.com> Date: Fri, Nov 16, 2018 at 11:33 PM Subject: Re: [math-fun] Rational-coefficient polynomial, applied to integers To: Bill Gosper <billgosper@gmail.com> I'm sure this has already been answered by now, at least the first part, but: (i) Easy proof that if there's an irrational coefficient the polynomial takes irrational values: find a basis over Q, including 1, for the vector space spanned by the coefficients (and 1), then write the polynomial as a linear combination of rational polynomials with coefficients in the basis. An irrational basis element has a nonzero polynomial coefficient, and the value of the polynomial can only be rational when this component is zero, which occurs only finitely many times. (ii) You don't need to test 0 through K-1, just up to the largest prime-power factor of K (minus one), or better yet make it symmetric around zero. (iii) After clearing denominators, you need to check that the polynomial is always zero mod p^m for any prime power p^m dividing K. There are probably general results on how to do this, but there are some obvious tricks to get started: since (x^p-x)^m is always zero, you can mod out by it; the polynomial needs to be a multiple of x(x-1)…(x-p+1) mod p^m, a multiple of x(x-1)…(x-2p+1) mod p^(m-1), …, a multiple of x(x-1)…(x-p^2+1) mod x^(m-p+1), a multiple of x(x-1)…(x-p^2-p+1) mod x^(m-p-1), … . (iv) Further consideration of the above shows that it is necessary and sufficient to test any r consecutive integers, for r large enough that r! is divisible by K. This is, of course, usually much smaller than K. And when it isn't, it's because K has large prime factors with small powers; we can consider those primes separately and use simpler methods which apply to small powers (I think you might be able to make these methods work for larger powers; ask me tomorrow). (v) The above method can give an explicit description of all polynomials of degree at most d which are zero mod p^m; for example, it allows us to count that there are sum(p^(a(j)(d-jp)), j=1,…,l-1)+p^((m-h)(d-lp)), where a(j) is the power of p dividing pj, l=r/p is minimal such that (lp)! is divisible by p^m, and h is the power of p dividing ((l-1)p)!. (I'm not entirely confident about (iv) and (v), and I'd like to double-check them, but I think they should be right.) I think the (somewhat) simpler/faster methods in (iv) apply up to p^p, but fail for p^(p+1), though they may be able to be modified. Julian On Fri, Nov 16, 2018 at 10:06 AM Bill Gosper <billgosper@gmail.com> wrote:
On 2018-11-15 15:06, Allan Wechsler wrote:
For a polynomial P with coefficients in Z, it's trivial that P(n) is integer if n is.
The converse is not true. There are lots of polynomials that always give integer answers to integer questions, but whose coefficients are not integers. For example, n(n+1)/2 = (1/2)n + (1/2)n^2 always takes integer values for integer n, even though the coefficients aren't integers.
Is there a way to quickly eyeball a polynomial in general to see if it is Z -> Z?
If the coefficients are rational, one can find K = the LCM of the denominators, multiply through by K, and test it for all the integers from 0 to K-1 to see if the result is always divisible by K. But I am hoping there is a simpler way.
If any of the coefficients are irrational, my intuition is that the polynomial is never Z->Z, but I haven't been able to think of an easy proof.
That's how Macsyma did it, in an internal three-valued Lisp function named divby1: (c59) COS(ODD^2*%PI/8);
2 odd ---- + 7/8 %pi 8 (d59) - cos(---) (- 1) 8
(c60) ?LSP("(divby1 '((MEXPT SIMP) $ODD 2)))");
(d60) 8 1 true —rwg
(c80) SIN(%PI*BERNPOLY(INTEGER,6)/6); 6 5 4 2 2 integer - 6 integer + 5 integer - integer ----------------------------------------------- %pi 4 (d80) sin(---) (- 1) 252 Mathematica partly gets it: In[43]:= FullSimplify[Sin[\[Pi] BernoulliB[6, n]/6], n \[Element] Integers] Out[43]= Sin[1/252 (\[Pi] + 21 (-1 + n)^2 n^2 (-1 + 2 (-1 + n) n) \[Pi])] In[42]:= Table[Sin[\[Pi] BernoulliB[6, n]/6], {n, 9}] Out[42]= {Sin[\[Pi]/252], -Sin[\[Pi]/252], -Sin[\[Pi]/252], Sin[\[Pi]/252], Sin[\[Pi]/252], -Sin[\[Pi]/252], -Sin[\[Pi]/252], Sin[\[Pi]/252], Sin[\[Pi]/252]} Sin[π/7] and Sin[π/9] aren't constructible and thus won't come out in real radicals, but at least you can (c88) HALFANGLES(HALFANGLES(d80)); %pi sqrt(cos(---) + 1) 63 (d88) sqrt(1 - ------------------) sqrt(2) 6 5 4 2 2 integer - 6 integer + 5 integer - integer ----------------------------------------------- 4 (- 1) /sqrt(2) I don't know if Mathematica can partially TrigToRadicals. —rwg (Amazing: OS-X or GMail flags "constructible" and accepted "constructable" for many seconds before flagging that too!)