0
$\begingroup$

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

Improve this question
$\endgroup$
8
  • 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$
    – Kevin Buzzard
    Commented Apr 15, 2010 at 18:53
  • 1
    $\begingroup$ ...alternatively, make X,Y,Z all very negative ;-) $\endgroup$
    – Kevin Buzzard
    Commented Apr 15, 2010 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 ♦
    Commented Apr 16, 2010 at 0:47
  • $\begingroup$ I don't understand your definition of "sparse integer". $\endgroup$
    – Qfwfq
    Commented Apr 16, 2010 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$
    – Paul Hunter
    Commented Apr 16, 2010 at 17:51

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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$
    – Paul Hunter
    Commented Apr 20, 2010 at 12:23
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Lang also has a pretty good section in Algebra all about the ABC conjecture. $\endgroup$
    – Harry Gindi
    Commented Apr 18, 2010 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$
    – Halfdan Faber
    Commented Jun 26, 2010 at 16:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .