Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
    -  +   -  -      -      -       -            -           -            -                   -               -
share|improve this question
    
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
1  
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
1  
@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

1 Answer 1

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$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.