Finding simple relations among consecutive polynomial values

The above relationship,

p(x+1)+p(x+2)+p(x+6) = p(x)+p(x+4)+p(x+5)

is a relation that will hold for any polynomial of degree 2. It is interesting as a side topic to be able to generate this kind of simple relationships, not just for coefficients 1 and -1, but for small coefficients. This can be resolved with signatures of expressions and the LLL lattice reduction algorithm, and it is a very good example of both. The problem can be formalized as follows: we are looking for a polynomial p(x) = a_dx^d+...a₁x+a₀such that $\alpha_0p(x)+\alpha_1p(x+1)+ ... +\alpha_mp(x+m) = 0$for any coefficients in p(x) and for any value of x. Furthermore, we are interested in the case where the $\alpha_i$coefficients are small.

For this we will construct the $(m+2) \times (m+2)$ matrix

$$\begin{array}{ccccc} 1 & 0 & ... & 0 & bS_n(p(x)) \\ 0 & 1 &... ... & ... & 1 & bS_n(p(x+m)) \\ 0 & 0 & ... & 0 & bn \end{array}$$

where b is an integer blow up factor, used to make sure that for the shortest vectors, a 0 will be in that column, and hence the corresponding relations with the polynomials are exact. The last column contains all the signatures of the unknown polynomial, which are computed (mod n). The last row serves the purpose of computing the linear combinations of the signatures (mod n).

For example, if we let d=2, n=100000007, m=6 and b=10 and the random variables assigned to the unknowns: $a_0=19639163,\;\; a_1=10670793;\;\; a_2=33049645$ and x=56110369 then the matrix is

$$\begin{array}{rrrrrrrr} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 574292850... ...7500130 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1000000070 \end{array}$$

Applying the LLL algorithm to the above produces the reduced matrix:

$$\begin{array}{rrrrrrrr} -1 & 2 & 0 & -2 & 1 & 0 & 0 & 0\\ 0 ... ...& 10\\ 43 & -36 & -29 & -24 & -16 & -9 & -2 & -20 \end{array}$$

From these short vectors we can conclude the previous relation from row 3 and the relation

2p(x+1)+p(x+4) = p(x)+2p(x+3)

from row 1. These relations can be verified with a computer algebra system if necessary.