# Polynomials over $\mathbb N$ generating no primefactors smaller than $p_0$ - methods for proving?

Studying a family of recurrent sequences (generalized from the NSW-numbers) I came to the observation, that certain polynomials (over $\mathbb N$) avoid primefactors below some smallest one. For instance the polynomial $$\small f_{11}(x) = x^5 + 11x^4 + 44x^3 + 77x^2 + 55x + 11 \qquad \qquad x \in \mathbb N$$ seems to have never a smaller primefactor than $p_{11,0}=23$ (except for the "trivial" $11$ at every $x=11k,k \in \mathbb N$) which occurs the first time at $x=2$.
Similarly, the polynomial $$\small f_{13}(x)= x^6 + 13x^5 + 65x^4 + 156x^3 + 182x^2 + 91x + 13$$ seems to have never a smaller primefactor than $p_{13,0}=53$ (except for $13$ at every $x =13k$) which occurs the first time at $x=6$.

Similarly, the polynomial $$\small f_{17}(x)= x^8 + 17x^7 + 119x^6 + 442x^5 + 935x^4 + 1122x^3 + 714x^2 + 204x + 17$$ seems to have never a smaller primefactor than $p_{17,0}=67$ (except for $17$ at every $x =17k$) which occurs the first time at $x=11$.

This comes from just eyeballing a table of data and is possibly false, but the heuristic looks very good and so I'm quite confident that this is true.

I have no idea how I could attack the question of proving such type of claims (I want to say a similar statement in general for that whole family of polynomials).

So besides of the basic question,
Q1: are these three observations true?
I'd like to get an idea for
Q2: how could I proceed to prove such types of conjectures?

[update] Answering to the comment of @chu: Consider the sequence of NSW-numbers recursively defined by $$a_6(k) =- a_6(k-2) + 6a_6(k-1) \qquad \qquad a_6(0)=-1,a_6(1) = 1$$ (the initial elements are one index shifted from that in the OEIS). And in general $$a_m(k) =- a_m(k-2) + ma_m(k-1) \qquad \qquad a_m(0)=-1,a_m(1) = 1$$

The first few members of the sequence are $$\small a_6(n) =[-1, 1, 7, 41, 239, 1393, 8119, 47321, 275807, 1607521, 9369319, 54608393,...]$$ The element $a_6(6)$ is that with the value $8119$.
Now the sequence $a_5(n)$ is similarly defined, just replace a $5$ instead of the $6$ in the recursion formula. The element $a_5(6) = 3191$. Do the same with sufficiently many sequences $a_k(6)$ We get the sequence of numbers $b_{11}(m)= 1,-1,11,199,989,3191,8119$ for the sequences $a_0$ to $a_6$ I chose the index $11$ at $b_{11}$ because of the occurence of the value $11$ in $a_2(6)$ (There is also some deeper reason for this, but that's not important here) That sequence can arbitrarily be expanded so that we can define an interpolating polynomial $f_{11}(x)$ which generates that numbers.
Completely similar is this done for the general $f_k(x)$.
But note, that relevant for me in this question is, how I could approach a proof for the primefactor-conditions described above; I want to get an idea/understand how this can be done in general.

Here is the left part of the table with the data. The sequence of $a_6()$ is in the row with index $6$, beginning with $-1,1,7,41,...$
The row with index $2$ having the odd natural numbers give $a_2()$ and make the second column-index at the top of the table. For the vertical columns we can find interpolating polynomials which become then my functions $f_m()$

    x  |   0  1    2    3      4       5        6         7           8            9
m  |  -1  1    3    5      7       9       11        13          15           17
-  +   -  -    -    -      -       -        -         -           -            -
-15  |  -1  1  -14  209  -3121   46606  -695969  10392929  -155197966   2317576561
-14  |  -1  1  -13  181  -2521   35113  -489061   6811741   -94875313   1321442641
-13  |  -1  1  -12  155  -2003   25884  -334489   4322473   -55857660    721827107
-12  |  -1  1  -11  131  -1561   18601  -221651   2641211   -31472881    375033361
-11  |  -1  1  -10  109  -1189   12970  -141481   1543321   -16835050    183642229
-10  |  -1  1   -9   89   -881    8721   -86329    854569    -8459361     83739041
-9  |  -1  1   -8   71   -631    5608   -49841    442961    -3936808     34988311
-8  |  -1  1   -7   55   -433    3409   -26839    211303    -1663585     13097377
-7  |  -1  1   -6   41   -281    1926   -13201     90481     -620166      4250681
-6  |  -1  1   -5   29   -169     985    -5741     33461     -195025      1136689
-5  |  -1  1   -4   19    -91     436    -2089     10009      -47956       229771
-4  |  -1  1   -3   11    -41     153     -571      2131       -7953        29681
-3  |  -1  1   -2    5    -13      34      -89       233        -610         1597
-2  |  -1  1   -1    1     -1       1       -1         1          -1            1
-1  |  -1  1    0   -1      1       0       -1         1           0           -1
0  |  -1  1    1   -1     -1       1        1        -1          -1            1
1  |  -1  1    2    1     -1      -2       -1         1           2            1
2  |  -1  1    3    5      7       9       11        13          15           17
3  |  -1  1    4   11     29      76      199       521        1364         3571
4  |  -1  1    5   19     71     265      989      3691       13775        51409
5  |  -1  1    6   29    139     666     3191     15289       73254       350981
6  |  -1  1    7   41    239    1393     8119     47321      275807      1607521
7  |  -1  1    8   55    377    2584    17711    121393      832040      5702887
8  |  -1  1    9   71    559    4401    34649    272791     2147679     16908641
9  |  -1  1   10   89    791    7030    62479    555281     4935050     43860169
10  |  -1  1   11  109   1079   10681   105731   1046629    10360559    102558961
11  |  -1  1   12  131   1429   15588   170039   1854841    20233212    220710491
12  |  -1  1   13  155   1847   22009   262261   3125123    37239215    443745457
13  |  -1  1   14  181   2339   30226   390599   5047561    65227694    842912461
14  |  -1  1   15  209   2911   40545   564719   7865521   109552575   1525870529
15  |  -1  1   16  239   3569   53296   795871  11884769   177475664   2650250191
16  |  -1  1   17  271   4319   68833  1097009  17483311   278635967   4440692161
17  |  -1  1   18  305   5167   87534  1482911  25121953   425590290   7209912977
18  |  -1  1   19  341   6119  109801  1970299  35355581   634430159  11384387281
19  |  -1  1   20  379   7181  136060  2577959  48845161   925480100  17535276739
20  |  -1  1   21  419   8359  166761  3326861  66370459  1324082319  26415275921
-  +   -  -    -    -      -       -        -         -           -            -


The following table shows the factorizations; they seem to be cyclic not only in the rows but also in the columns. The columns are in a way multiplicative: the value at some entry can only be prime if the column-index $m$ is prime; for composite column-indexes $m$ the entry has all the primefactors from the other columns whose $m$-indexes are divisors of the "current" $m$ and seemingly one more - just like in the theorem of Szygmondi about the compositions of the Mersenne-numbers. (Note: the minus signs have mostly vanished, but seem irrelevant here)

    x  |   0  1      2      3       4            5           6            7                   8               9
m  |  -1  1      3      5       7            9          11           13                  15              17
-  +   -  -      -      -       -            -           -            -                   -               -
-15  |  -1  1    2.7  11.19    3121     2.7.3329    307.2267  53.157.1249  2.7.11.19.29.31.59    17.136328033
-14  |  -1  1     13    181    2521     13.37.73      489061      6811741       13.61.181.661      1321442641
-13  |  -1  1  2^2.3   5.31    2003  2^2.3^2.719    23.14543      4322473   2^2.3.5.31.59.509     137.5268811
-12  |  -1  1     11    131   7.223     11.19.89    23^2.419    157.16823        11.131.21841       375033361
-11  |  -1  1    2.5    109   29.41     2.5.1297      141481    13.118717      2.5^2.109.3089       183642229
-10  |  -1  1    3^2     89     881    3^3.17.19     131.659       854569       3^2.59.89.179      4691.17851
-9  |  -1  1    2^3     71     631      2^3.701   11.23.197       442961       2^3.29.71.239        34988311
-8  |  -1  1      7   5.11     433        7.487       26839     131.1613       5.7.11.29.149    101.103.1259
-7  |  -1  1    2.3     41     281    2.3^2.107      43.307        90481         2.3.41.2521        67.63443
-6  |  -1  1      5     29    13^2        5.197        5741        33461          5^2.29.269        137.8297
-5  |  -1  1    2^2     19    7.13      2^2.109        2089        10009          2^2.19.631          229771
-4  |  -1  1      3     11      41       3^2.17         571         2131            3.11.241          67.443
-3  |  -1  1     -2      5      13         2.17          89          233              2.5.61            1597
-2  |  -1  1     -1      1      -1            1          -1            1                  -1               1
-1  |  -1  1      0     -1       1            0          -1            1                   0              -1
0  |  -1  1      1     -1      -1            1           1           -1                  -1               1
1  |  -1  1      2      1      -1           -2          -1            1                   2               1
2  |  -1  1      3      5       7          3^2          11           13                 3.5              17
3  |  -1  1    2^2     11      29       2^2.19         199          521           2^2.11.31            3571
4  |  -1  1      5     19      71         5.53       23.43         3691           5^2.19.29         101.509
5  |  -1  1    2.3     29     139     2.3^2.37        3191        15289          2.3.29.421          350981
6  |  -1  1      7     41     239        7.199      23.353       79.599           7.31^2.41       103.15607
7  |  -1  1    2^3   5.11   13.29    2^3.17.19      89.199      233.521      2^3.5.11.31.61       1597.3571
8  |  -1  1    3^2     71   13.43      3^3.163       34649      53.5147         3^2.71.3361        16908641
9  |  -1  1    2.5     89   7.113    2.5.19.37     43.1453     53.10477       2.5^2.89.1109      307.142867
10  |  -1  1     11    109   13.83       11.971     23.4597     937.1117         11.109.8641      373.274957
11  |  -1  1  2^2.3    131    1429  2^2.3^2.433     23.7393    53.79.443    2^2.3.61.131.211     1531.144161
12  |  -1  1     13   5.31    1847      13.1693      262261    103.30341       5.13.31.18481     1973.224909
13  |  -1  1    2.7    181    2339   2.7.17.127    11.35509   53.131.727       2.7.181.25741     67.12580783
14  |  -1  1    3.5  11.19   41.71  3^2.5.17.53   23.43.571    2131.3691  3.5^2.11.19.29.241  67.101.443.509
15  |  -1  1    2^4    239   43.83     2^4.3331      795871    13.914213       2^4.239.46411   67.271.145963
16  |  -1  1     17    271   7.617      17.4049     1097009     17483311      17.31.271.1951      4440692161
17  |  -1  1  2.3^2   5.61    5167   2.3^3.1621    67.22133     25121953    2.3^2.5.61.77521   101.8431.8467
18  |  -1  1     19  11.31  29.211      19.5779    199.9901   79.521.859    11.19.31.181.541   919.3469.3571
19  |  -1  1  2^2.5    379  43.167   2^2.5.6803  67.109.353   1091.44771   2^2.5^2.379.24419  17.647.1594261
20  |  -1  1    3.7    419  13.643   3^2.7.2647     3326861     66370459     3.7.29.419.5189  137.2551.75583
-  +   -  -      -      -       -            -           -            -                   -               -

-
What does $p_{x,y}$ means? And how do you construct $f_p$ coefficients? – chubakueno Dec 9 '13 at 1:48
@chu : $p_{x,y}$ means nothing else than the distinction that for some $k$'th polynomial there is a first ($j=0$) primefactor $p_{k,j}$ as a lower bound. The coefficients come from the polynomial interpolation of the columns of the square array where I filled in the sequences of the generalized NSW-numbers. The NSW-numbers (see my link to the OEIS) can be defined by the recursion $a_k=-1 a_{k-2} + 6a_{k-1}$ and $a_0=-1,a_1=1$ and for the generalizations I replace the value $6$ by positive and negative integers.(...) – Gottfried Helms Dec 9 '13 at 2:02
(...) This has also some resemblance to the Fibonacci-numbers which I've discussed recently in another question here in MSE; they occur at negative indexes of that generalizations. (That resemblance made the NSW-numbers and this generalizations interesting for me; I also want later to study the fractionally interpolated sequences in a whole) – Gottfried Helms Dec 9 '13 at 2:06
It is easy to prove individual cases by considering all possible residue clases of each prime to be ruled out, but a generalization seems difficult... – chubakueno Dec 9 '13 at 2:11
@chu: I expanded my question giving an example as you asked for. I hope this is sufficient explanative – Gottfried Helms Dec 9 '13 at 2:48

As chubakuneo comments, if you want to prove that $p$ never divides any $f(m)$ where $f \in \Bbb Z[X]$, it's enough to check that $f$ has no roots modulo $p$, i.e. that $f(0),f(1),f(2),\ldots f(p-1)$ are not multiples of $p$. So a straightforward computation can confirm your claims.

If you consider $m$ as an indeterminate $X$ over $\Bbb Z$, you have a sequence $-1,1,X+1,X^2+X-1,\ldots$ of polynomials $f_n(X)$ satisfying the recurrent relation $f_{n+1} = Xf_n - f_{n-1}$ and the initialisation $f_0 = -1, f_1 = 1$

It turns out that for $n\ge 2$, the roots of $f_n(X)$ are the $2\cos(\frac{2k\pi}{2n-1})$ for $1 \le k \le n-1$, so that $(X-2)f_n^2 = 2T_{2n-1}(X/2) -2$ where $T_n$ is the Chebyshev polynomial. You can probably prove this equality by induction using the recurrence relations for Chebyshev polynomials.

Now that we know the roots of $f_n$, we also know the Galois group of $f_n$ : it is isomorphic to $G_n = (\Bbb Z/(2n-1)\Bbb Z)^*/\{\pm 1\}$.
Furthermore, the map $\rho : R_n = (\Bbb Z/(2n-1)\Bbb Z \setminus \{0\})/\{\pm 1\} \to \text{the roots of } f_n$ given by $\rho_{\pm k} = 2\cos(2k\pi/(2n-1))$ is compatible with the usual action of $G_n$ on $R_n$, as $\sigma_{\pm u}(\rho_{\pm k}) = \rho_{\pm uk}$.

In the following, I will always assume that $p$ is a prime that doesn't divide $2n-1$ (the discriminant of $f_n$), so that $p$ doesn't ramify.

Then, you can count the number of roots of $f_n$ modulo $p$ by counting the number of fixpoints of the Artin symbol $[p]_n \in G_n$ (when looking at its action on $R_n$). In particular, to see what primes don't appear in the factorizations of $f_n(m)$, we need to point out what are the elements of $G_n$ without fixpoints on $R_n$.

If $2n-1 = \prod_{i=1}^d p_i^{k_i}$, then the roots $\rho_{\pm(2n-1)/p_i}$ are fixed by $\sigma_{\pm u}$ where $u \equiv \pm 1 \pmod {p_i}$, so there are $2^{d-1}$ elements of the Galois group having fixpoints (conversely we check that any automorphism fixing someone fixes one of those roots).

Hence the density of automorphisms having a fixpoint is $1 - \prod_{p\mid 2n-1} (1-2/(p-1))$.

What's more, Artin's reciprocity law tells you that $[p]_n = \sigma_{\pm p \pmod {2n-1}}$. Together with Dirichlet's theorem, this tells you exactly the density of what primes that can appear how often in the factorisations of $f_n(m)$.

In particular the density of primes appearing in the factorisations of $f_n(m)$ is $1 - \prod_{p\mid 2n-1}(1-2/(p-1))$ because they are exactly the primes congruent to $\pm 1$ modulo some prime divisor of $2n-1$.

$f_2 = X+1$. It has trivial Galois group, $R_2 = \{1,2\} = G_2$, so the only element of $G_2$ fixes $R_2$ : $f_2$ has one root mod $p$ forall $p$.

$f_3 = X^2 + X-1$. $R_2 = G_2 = \{\{1,4\},\{2,3\}\}$. If $p \equiv 2,3 \pmod 5$ then it never divides $f_3(m)$, while if $p \equiv 1,4 \pmod 5$ then $f_3$ has 2 roots mod $p$.

$f_4 = X^3+X^2-2X-1$. As in the above, $2n+1 = 7$ is prime, so only the primes $p \equiv 1,6 \pmod 7$ have 3 roots mod $p$, all the others can't appear.

$f_5 = X^4+X^3-3X^2-2X+1$. Now, $2n+1 = 9 = 3^2$. If $p \equiv 1,8 \pmod 9$ then it has 4 roots mod $p$. Otherwise it has 1 roots mod $p$. So every prime appears, but primes like $17,19,37$ especially so.

$f_6 = X^5+X^4-4X^3-3X^2+3X+1$. Again, $2n+1 = 11$ is prime so the only primes that can appear are those congruent to $1,10 \pmod {11}$ and then they have 5 roots.

In general, if $2n+1$ is a prime $q$, then $f_n$ has no root mod $p$ except when $p \equiv \pm 1 \pmod q$, where it splits completely. So since $1,q-1$ and $q+1$ are not primes, the smallest prime that can possibly appear is $2q-1$.

-
Mercio - wow, that's much stuff to chew on. I'm thinking over the very first remark and I'll do exercises with some examples. The Galois-stuff should go over my head, I'm afraid: I'm a late learner you know...; but if that shall be required I think I must leave the problem as open for me. I didn't expect that the checking of the residue classes would be so simple, so perhaps I can do at least some better understanding and then simplification there. – Gottfried Helms Dec 10 '13 at 15:30
@GottfriedHelms : I nuked a fly when talking about Artin's stuff. A much more concrete way of studying this is that we know how to write the roots in term of roots of unity (they are the $(\zeta_{2n-1}^k + \zeta_{2n-1}^{-k}$), and in finite fields, we know that $[p]_n = Frob_p = x \mapsto x^p$. So we understand well the action on the roots of unity in terms of $p \pmod {2n+1}$, and so we recover very easily the relationship between $p \pmod {2n+1}$ and the Galois group mod $p$, which finally leads to the number of roots mod $p$. So my advice is to learn about those nice finite fields first ! – mercio Dec 10 '13 at 17:22