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

  • 4
    $\begingroup$ Umm...just choose D,X,E,Y,F,Z very large, with D and E and F pairwise coprime, and then gcd(D^X,E^Y,F^Z)=1 so by Euclid you can find A,B,C such that AD^X+BE^Y+CF^Z=1. Now if A,B,C happen to be too small just change them until they're not, e.g. A-->A+E^Y,B-->B-D^X. $\endgroup$ Apr 15 '10 at 18:53
  • 1
    $\begingroup$ ...alternatively, make X,Y,Z all very negative ;-) $\endgroup$ Apr 15 '10 at 19:42
  • $\begingroup$ ... so the answer is: Yes, because all integers greater than 1 satisfy this property. Could you could give some explanation of what this had to do with the ABC or Catalan conjectures? The connection is not obvious from here. $\endgroup$
    – S. Carnahan
    Apr 16 '10 at 0:47
  • $\begingroup$ I don't understand your definition of "sparse integer". $\endgroup$
    – Qfwfq
    Apr 16 '10 at 9:23
  • $\begingroup$ Thanks and d'oh. My intention was that A,B,C were all about the same size as D,E,F,X,Y,Z (possibly smaller). I will have to rethink the question. (also X,Y,Z are meant to be positive) The relation to the ABC conjecture is possibly better illustrated with the (zero-testing) question: Given A,B,C,X,Y,Z, is A^X+B^Y=C^Z? (if Z is relatively large [compared with A,B,C], then C^Z > rad(A^X B^Y C^Z) = rad(ABC)) The relation to the Catalan conjecture is in the attempt to find "small" combinations of integer powers. $\endgroup$ Apr 16 '10 at 17:51

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.

  • $\begingroup$ Thanks, I read that paper earlier but obviously failed to register its usefulness! So for sparse integers of fixed number of terms we can (subject to coprimality constraints and the generalized abc conjecture) efficiently zero-test sparse integers as there are only finitely many cases where the exponents can be "large". I wonder if it's possible to remove the reliance on the abc conjecture (and fixed number of terms) since the general question is such a special instance of the conjecture... [but since that wasn't the question I asked, I deem this to be an answer] $\endgroup$ Apr 20 '10 at 12:23

It looks like you're trying to examine the Tijdeman-Zagier conjecture which is usually referred to as Beal's conjecture because Andrew Beal has offered 100000 USD for its solution.

Conjecture (Tijdeman, Zagier) If $(a,b,c,x,y,z)$ are positive integers such that $$a^x + b^y = c^z$$ and $x,y,z$ are all $ > 2$ then $a,b,$ and $c$ share a common prime factor.

This is a natural generalization of Fermat's Last Theorem. The ABC conjecture implies that there are only finitely many counterexamples to the above conjecture.

If you want to know more about the ABC conjecture these expositions of Mazur and Elkies are good places to start.

  • $\begingroup$ Lang also has a pretty good section in Algebra all about the ABC conjecture. $\endgroup$ Apr 18 '10 at 21:51
  • $\begingroup$ Jamie, see mathoverflow.net/questions/28764/…. Perhaps you could provide the explicit reference for the conjecture's proper attribution to Tijdeman & Zagier? $\endgroup$ Jun 26 '10 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.