{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T22:41:25Z","timestamp":1777675285188,"version":"3.51.4"},"reference-count":21,"publisher":"American Mathematical Society (AMS)","issue":"296","license":[{"start":{"date-parts":[[2016,4,1]],"date-time":"2016-04-01T00:00:00Z","timestamp":1459468800000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    We describe an algorithm which, given a number field\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper K\">\n                        <mml:semantics>\n                          <mml:mi>K<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">K<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    and a bound\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper B\">\n                        <mml:semantics>\n                          <mml:mi>B<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">B<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , finds all the elements of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper K\">\n                        <mml:semantics>\n                          <mml:mi>K<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">K<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    having relative height at most\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper B\">\n                        <mml:semantics>\n                          <mml:mi>B<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">B<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . Two lists of numbers are computed: one consisting of elements\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"x element-of upper K\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>x<\/mml:mi>\n                            <mml:mo>\n                              \u2208\n                              \n                            <\/mml:mo>\n                            <mml:mi>K<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">x\\in K<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    for which it is known with certainty that\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper H Subscript upper K Baseline left-parenthesis x right-parenthesis less-than-or-equal-to upper B\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:msub>\n                              <mml:mi>H<\/mml:mi>\n                              <mml:mi>K<\/mml:mi>\n                            <\/mml:msub>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>x<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                            <mml:mo>\n                              \u2264\n                              \n                            <\/mml:mo>\n                            <mml:mi>B<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">H_K(x)\\leq B<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , and one containing elements\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"x\">\n                        <mml:semantics>\n                          <mml:mi>x<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">x<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    such that\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"StartAbsoluteValue upper H Subscript upper K Baseline left-parenthesis x right-parenthesis minus upper B EndAbsoluteValue greater-than theta\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mo stretchy=\"false\">|<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:msub>\n                              <mml:mi>H<\/mml:mi>\n                              <mml:mi>K<\/mml:mi>\n                            <\/mml:msub>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>x<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                            <mml:mo>\n                              \u2212\n                              \n                            <\/mml:mo>\n                            <mml:mi>B<\/mml:mi>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mo stretchy=\"false\">|<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mo>&gt;<\/mml:mo>\n                            <mml:mi>\n                              \u03b8\n                              \n                            <\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">|H_K(x)-B|&gt;\\theta<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    for a tolerance\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"theta\">\n                        <mml:semantics>\n                          <mml:mi>\n                            \u03b8\n                            \n                          <\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">\\theta<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    chosen by the user. We show that every element of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper K\">\n                        <mml:semantics>\n                          <mml:mi>K<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">K<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    whose height is at most\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper B\">\n                        <mml:semantics>\n                          <mml:mi>B<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">B<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    must appear in one of the two lists.\n                  <\/p>","DOI":"10.1090\/mcom\/2954","type":"journal-article","created":{"date-parts":[[2015,4,1]],"date-time":"2015-04-01T13:33:43Z","timestamp":1427895223000},"page":"2867-2891","source":"Crossref","is-referenced-by-count":5,"title":["Computing algebraic numbers of bounded height"],"prefix":"10.1090","volume":"84","author":[{"given":"John","family":"Doyle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Krumm","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2015,4,1]]},"reference":[{"key":"1","isbn-type":"print","first-page":"91","article-title":"An algorithmic theory of lattice points in polyhedra","author":"Barvinok, Alexander","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/0521770874"},{"key":"2","isbn-type":"print","first-page":"27","article-title":"A subexponential algorithm for the determination of class groups and regulators of algebraic number fields","author":"Buchmann, Johannes","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0817634932"},{"key":"3","isbn-type":"print","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/BFb0091539","article-title":"Factoring integers with the number field sieve","author":"Buhler, J. P.","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540570136"},{"issue":"5","key":"4","first-page":"1063","article-title":"The complexity of the construction of the ring of integers of a global field","volume":"306","author":"Chistov, A. L.","year":"1989","journal-title":"Dokl. Akad. Nauk SSSR","ISSN":"https:\/\/id.crossref.org\/issn\/0002-3264","issn-type":"print"},{"key":"5","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02945-9","volume-title":"A course in computational algebraic number theory","volume":"138","author":"Cohen, Henri","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540556400"},{"issue":"4","key":"6","doi-asserted-by":"publisher","first-page":"1273","DOI":"10.1016\/j.jsc.2003.04.003","article-title":"Effective lattice point counting in rational convex polytopes","volume":"38","author":"De Loera, Jes\u00fas A.","year":"2004","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"7","first-page":"507","article-title":"Preperiodic points for quadratic polynomials over quadratic fields","volume":"20","author":"Doyle, John R.","year":"2014","journal-title":"New York J. Math."},{"key":"8","isbn-type":"print","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/3-540-12868-9_103","article-title":"A procedure for determining algebraic integers of given norm","author":"Fincke, U.","year":"1983","ISBN":"https:\/\/id.crossref.org\/isbn\/3540128689"},{"key":"9","unstructured":"John Jones, Number fields, \\url{http:\/\/hobbes.\/a.qsu.edu\/NFDB\/}."},{"issue":"4","key":"10","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"Lenstra, A. K.","year":"1982","journal-title":"Math. Ann.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5831","issn-type":"print"},{"issue":"2","key":"11","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1090\/S0273-0979-1992-00284-7","article-title":"Algorithms in algebraic number theory","volume":"26","author":"Lenstra, H. W., Jr.","year":"1992","journal-title":"Bull. Amer. Math. Soc. (N.S.)","ISSN":"https:\/\/id.crossref.org\/issn\/0273-0979","issn-type":"print"},{"issue":"1","key":"12","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.exmath.2006.08.001","article-title":"Counting integral ideals in a number field","volume":"25","author":"Murty, M. Ram","year":"2007","journal-title":"Expo. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0723-0869","issn-type":"print"},{"issue":"5","key":"13","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1006\/jsco.2002.0531","article-title":"Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding","volume":"33","author":"Pan, Victor Y.","year":"2002","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"1-2","key":"14","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1023\/A:1015225430108","article-title":"Elements with bounded height in number fields","volume":"43","author":"Peth\u0151, A.","year":"2001","journal-title":"Period. Math. Hungar.","ISSN":"https:\/\/id.crossref.org\/issn\/0031-5303","issn-type":"print"},{"key":"15","series-title":"Encyclopedia of Mathematics and its Applications","isbn-type":"print","volume-title":"Algorithmic algebraic number theory","volume":"30","author":"Pohst, M.","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/0521596696"},{"issue":"1","key":"16","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/PL00004405","article-title":"The classification of rational preperiodic points of quadratic polynomials over \ud835\udc44: a refined conjecture","volume":"228","author":"Poonen, Bjorn","year":"1998","journal-title":"Math. Z.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5874","issn-type":"print"},{"key":"17","series-title":"International Series in Pure and Applied Mathematics","volume-title":"Principles of mathematical analysis","author":"Rudin, Walter","year":"1976","edition":"3"},{"issue":"4","key":"18","doi-asserted-by":"crossref","first-page":"433","DOI":"10.24033\/bsmf.1905","article-title":"Heights in number fields","volume":"107","author":"Schanuel, Stephen Hoel","year":"1979","journal-title":"Bull. Soc. Math. France","ISSN":"https:\/\/id.crossref.org\/issn\/0037-9484","issn-type":"print"},{"key":"19","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-69904-2","volume-title":"The arithmetic of dynamical systems","volume":"241","author":"Silverman, Joseph H.","year":"2007","ISBN":"https:\/\/id.crossref.org\/isbn\/9780387699035"},{"key":"20","unstructured":"W. A. Stein et al., Sage Mathematics Software (Version 5.9), The Sage Development Team, 2013, http:\/\/www.sagemath.org."},{"issue":"3","key":"21","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1006\/jcom.1995.1014","article-title":"Short proofs using compact representations of algebraic integers","volume":"11","author":"Thiel, Christoph","year":"1995","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2015-84-296\/S0025-5718-2015-02954-8\/S0025-5718-2015-02954-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2015-84-296\/S0025-5718-2015-02954-8\/S0025-5718-2015-02954-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:33:19Z","timestamp":1776796399000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2015-84-296\/S0025-5718-2015-02954-8\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,1]]},"references-count":21,"journal-issue":{"issue":"296","published-print":{"date-parts":[[2015,11]]}},"alternative-id":["S0025-5718-2015-02954-8"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/2954","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2015,4,1]]}}}