I'm looking to efficiently zero-test "sparse integers", i.e. integers of the form $\sum C_i \cdot A_i^{X_i}$ (where $A_i, C_i, X_i$ are integers); equivalently test if a given (integer or rational) point is a zero of a sparse polynomial. For example, a randomised algorithm would be to compute the sum modulo a random prime since Fermat's Little Theorem reduces computations to a "manageable" level and with good probability there won't be a false positive. I'm wondering if this can be derandomised.
So beside the obvious does anyone know anything relevant about the general problem, I have more of a first step question:
Is (are) there (infinitely many) positive integer(s) $M$ such that there are integers $A,B,C,D,E,F,X,Y,Z$
with
$|A|,|B|,|C| < M$, $D,E,F,X,Y,Z>M$ and
$$ 0 < A\cdot D^X+B\cdot E^Y+C \cdot F^Z< \log M?$$
Best Answer
Regarding Paul's "first step question", I believe the answer may well be that the set of such M is finite. This follows under some coprimality hypothesis from the n-term abc conjecture of Browkin and Brzezinski [Math. Comp. 62 (1994), 931--939]. This states that, if we have $a_1, a_2, \ldots, a_n$ integers, for $n \geq 3$, with $\gcd(a_1, \ldots, a_n)=1$, $a_1 + \cdots + a_n=0$, and no vanishing subsums, then $$ \limsup \frac{\log \max |a_i|}{\log \mbox{Rad} (a_1 a_2 \cdots a_n)} = 2n-3. $$
There may be examples with small M (like 3 or 4).....I'm not sure.