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



abc-conjecture meets Catalan conjecture?
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.


