Iterating (programmatically) over "all" integer polynomials (how to order them and when to stop to be sure we checked all what we wanted?)

Question

I have some annoyingly stubborn problems that are basically of the form "are all integer polynomials of some kind a sum of a few products of polynomials of some other kind?". For instance I want a polynomial $P$ that is not of the form $P_1Q_1 + P_2Q_2$, where $P,P_i,Q_i$ have some easy to check property. Since I can't seem to get far using my wits alone, I was thinking I could try to write a simple program to find a polynomial that isn't of the desired form, so I have something concrete to work with.

However, I have no idea how to iterate over polynomials in such a way that I will be sure I've already checked all possibilities. Obviously I can limit the degree, but that still leaves me with infinitely many options.

What I'm hoping to find is some sort of semi-invariant $f$ that has finite equivalence classes, but also is (for example) superadditive and supermultiplicative. That way I could check all $P_i,Q_i$ with $f<n$ and be sure that any polynomial I didn't get which also has $f<n$ is not of the specified form.

Of course superadditivity and supermultiplicativity may not be the only options here, or perhaps I need to combine a few different semi-invariants, I only care about being able to stop iterating at some point.

If you want a specific problem: $P_i$ are of the form $2ax+6b$ modulo $x^2$, $Q_i$ are of the form $5cx+35d$ modulo $x^2$ ($a,b,c,d$ are integers). Find a $P$ such that $P$ is of the form $10ex+210f$ modulo $x^2$ and $P$ is certainly not of the form $P=P_1Q_1+P_2Q_2$. Of course it'd be great if the method worked for a wider range of problems of similar nature.

Answer 1

The scope of your question is not entirely clear to me. Here are some possible interpretations and corresponding answers:

Is there an invariant that takes only finitely-many values on $\mathbb{Z}[x]$?

Yes, of course. Take the invariant "is equal to the polynomial $x$". This takes two values on $\mathbb{Z}[x]$: true and false. If you want one that offers interesting insight your problem, you need to tell us what your problem is (it is unclear to me if your last paragraph is your problem or just an example).

⟨ Your last paragraph ⟩

That is, does there exist $P(x)\in\mathbb{Z}[x]$ such that $P(0)=210$ and $P(x)$ cannot be written $$P(x)=a(x)\alpha(x)+b(x)\beta(x)$$ where \begin{gather*} a(x)\equiv2u_ax+6v_a\pmod{x^2} \\ \alpha(x)\equiv5c_{\alpha}x+35d_{\alpha}\pmod{x^2} \end{gather*} for some $u_a,v_a,c_{\alpha},d_{\alpha}$ and likewise for $b$ and $\beta$?

Of course. Note that any such \begin{align*} a(x)\alpha(x)+b(x)\beta(x)&\equiv2(u_ax+3v_a)\cdot5(c_{\alpha}x+7d_{\beta})+2(u_bx+3v_b)\cdot5(c_{\beta}x+7d_{\beta}) \pmod{x^2} \\ &=10(7u_ad_{\beta}+3v_ac_{\alpha}+7u_bd_{\beta}+3v_bc_{\beta})x \pmod{x^2,210} \end{align*} Since $10\mid 210$, the linear term is a multiple of $10$ even without the moduli. But there are many polynomials for which $P(210)=0$, and the linear term is not a multiple of $10$; for example, $210+x$.

How can I write a program to iterate over all integer polynomials?

The idea is to find an computably-invertable invariant that takes on a recursively-enumerable set of values on $\mathbb{Z}[x]$. When I had to do this, I used $$H\left(\sum_{j=0}^d{a_jf(x)}\right)=d+\sum_{j=0}^d{|a_j|}$$ This takes on every integer in $\mathbb{N}$. Conversely, given a value $h$, I can find $H^{-1}(\{h\})$ quite easily:

For each d in [0,1,...,h]:
    Let a,b be arrays of d+1 integers
    Set b(-1)=0
    Comment:
        This is "stars-and-bars":
        We want to solve \sum_j{c_j}=h-d; then add signs
        It's easier to iterate over the partial sums \sum_{j=0}^J{c_j}
    For each 0<=b(0)<=b(1)<=b(2)<=...<=b(d)<=h+1:
        For each j in [0,1,2,...,d]:
            For each sign in [-1,1]:
                a(j)=sign*(b(j)-b(j-1))
        Compute with the polynomial a(0)+a(1)x+a(2)x^2+...+a(d)x^d