Timeline for Points of bounded height in a number field
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 9, 2011 at 13:18 | comment | added | Maurizio Monge | @Xander: ah ok, now it is clear where the d2 in the exponent was coming from. And unluckily at the moment i have no better idea. | |
| Jun 7, 2011 at 16:17 | comment | added | Xander Faber | @Maurizio: Oh my, you're right! Your bound is too small to be compatible with Schanuel's theorem ... but that's because I forgot to normalize my definition of the height correctly. (It has been corrected.) With the extra exponent on the H(x), it follows that if one searches over all irreducible polynomials of degree $d$, then the search space of roots has size at most $d(2^{d/2} B^d)^{d+1}$. I believe that this is also roughly equivalent to the approach by Petho and Schmitt. | |
| Jun 7, 2011 at 16:11 | history | edited | Xander Faber | CC BY-SA 3.0 |
added 12 characters in body
|
| Jun 7, 2011 at 11:16 | comment | added | Maurizio Monge | The polynomials $a_dx^d+\dots+a_1x+a_0$ of degree $d$ with Mahler measure $\leq B$ always have $|a_i|\leq \min\{\binom{d}{i}, \binom{d}{d-i}\}B$, shouldn't this restrict the search space to at most $d(2^{d/2}B)^{d+1}$ total roots? | |
| Jun 7, 2011 at 3:41 | comment | added | Xander Faber | @Joe: I want the full set $S(K, B)$ for a very general implementation in Sage. This is also the reason for fixing the number field, rather than ranging over all number fields of bounded degree as one might expect from Northcott's theorem. | |
| Jun 7, 2011 at 3:03 | comment | added | Joe Silverman | @Xander: Do you actually want the full set $S(K,B)$, or do you have some other problem such as a Diophantine equation whose solutions you know have height less than $B$, and you want to find the solutions? If the latter, there are often tricks to cut the search space. As for Schanuel's proof, my impression is that if it's done carefully with error estimates, it will yield an algorithm, but I don't imagine it would be at all efficient. (However, I haven't actually tried to do it.) | |
| Jun 6, 2011 at 22:50 | history | edited | Xander Faber | CC BY-SA 3.0 |
added 221 characters in body
|
| Jun 6, 2011 at 22:45 | comment | added | Xander Faber | Once you have a nice basis $L$ for the ring of integers $\mathcal{O}_K$, you still need to use some kind of algebraic number theory to turn a height bound into bounds for the coefficients of an element $x \in K$, as written in the basis $L$. The paper by Petho/Schmitt that I mentioned above uses exactly this strategy, but their bounds for the coefficients are fairly weak. | |
| Jun 6, 2011 at 22:19 | comment | added | Junkie | Block korkine-zolotareff reduction, slightly stronger than LLL. It interpolates between LLL and HKZ (hermite). | |
| Jun 6, 2011 at 21:58 | comment | added | Xander Faber | @Dror: what is BKZ? | |
| Jun 6, 2011 at 21:47 | comment | added | Dror Speiser | Maybe applying BKZ to a basis of the integer ring divided by $a$, varying over $a$, will work? | |
| Jun 6, 2011 at 21:22 | comment | added | Joseph O'Rourke | @Xander: Thanks for adding the definition! | |
| Jun 6, 2011 at 21:01 | history | edited | Xander Faber | CC BY-SA 3.0 |
Added a relevant definition
|
| Jun 6, 2011 at 20:39 | comment | added | Joseph O'Rourke | Perhaps you should define "the absolute multiplicative height of an algebraic number" just for the education of those less versed in this area. Is it $n + \sum |a_i|$ where the $a_i$ are the coefficients of the min degree polynomial of which it is a root? | |
| Jun 6, 2011 at 20:31 | history | asked | Xander Faber | CC BY-SA 3.0 |