Computing sparse multiples of polynomials (Q1934308): Difference between revisions

Given a polynomial \(P\), for example with integer coefficients, a classical question is: is it true that \(P\) has some ``simple'' mutiple? for example a multiple with coefficients \(0\) or \(\pm1\)? Here the authors consider the existence of sparse multiples, i.e. multiples with only few non-zero coefficients. They give an algorithm to answer such a question in the case of polynomials over the rational numbers. They also study this problem for polynomials with coefficients in a finite field and show -- in a certain sense -- that this is a hard problem.