Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
4  
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. –  Kevin Buzzard Apr 15 '10 at 18:53
1  
...alternatively, make X,Y,Z all very negative ;-) –  Kevin Buzzard Apr 15 '10 at 19:42
    
... 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. –  S. Carnahan Apr 16 '10 at 0:47
    
I don't understand your definition of "sparse integer". –  Qfwfq Apr 16 '10 at 9:23
    
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. –  Paul Hunter Apr 16 '10 at 17:51
show 3 more comments

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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] –  Paul Hunter Apr 20 '10 at 12:23
add comment

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.

share|improve this answer
    
Lang also has a pretty good section in Algebra all about the ABC conjecture. –  Harry Gindi Apr 18 '10 at 21:51
    
Jamie, see mathoverflow.net/questions/28764/…. Perhaps you could provide the explicit reference for the conjecture's proper attribution to Tijdeman & Zagier? –  Halfdan Faber Jun 26 '10 at 16:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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