Elements of bounded height in number fields¶

This module provides functions to list all elements of a given number field with height less than a specified bound.

REFERENCES:

[DK2013]

AUTHORS:

John Doyle, David Krumm (2013): initial version
TJ Combs, Raghukul Raman (2018): added Doyle-Krumm algorithm-4

sage.rings.number_field.bdd_height.bdd_height(K, height_bound, tolerance=0.01, precision=53)[source]¶

Compute all elements in the number field \(K\) which have relative multiplicative height at most height_bound.

The function can only be called for number fields \(K\) with positive unit rank. An error will occur if \(K\) is \(\QQ\) or an imaginary quadratic field.

This algorithm computes 2 lists: \(L\), containing elements \(x\) in \(K\) such that \(H_k(x) \leq B\), and a list \(L'\) containing elements \(x\) in \(K\) that, due to floating point issues, may be slightly larger then the bound. This can be controlled by lowering the tolerance.

In current implementation both lists \((L,L')\) are merged and returned in form of iterator.

ALGORITHM:

This is an implementation of the revised algorithm (Algorithm 4) in [DK2013].

INPUT:

height_bound – real number
tolerance – (default: 0.01) a rational number in (0,1]
precision – (default: 53) positive integer

OUTPUT: an iterator of number field elements

EXAMPLES:

There are no elements of negative height:

Sage

sage: from sage.rings.number_field.bdd_height import bdd_height
sage: x = polygen(ZZ, 'x')
sage: K.<g> = NumberField(x^5 - x + 7)
sage: list(bdd_height(K, -3))
[]

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import bdd_height
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(5) - x + Integer(7), names=('g',)); (g,) = K._first_ngens(1)
>>> list(bdd_height(K, -Integer(3)))
[]

Sage Live

from sage.rings.number_field.bdd_height import bdd_height
x = polygen(ZZ, 'x')
K.<g> = NumberField(x^5 - x + 7)
list(bdd_height(K, -3))

The only nonzero elements of height 1 are the roots of unity:

Sage

sage: from sage.rings.number_field.bdd_height import bdd_height
sage: K.<g> = QuadraticField(3)
sage: list(bdd_height(K, 1))
[0, -1, 1]

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import bdd_height
>>> K = QuadraticField(Integer(3), names=('g',)); (g,) = K._first_ngens(1)
>>> list(bdd_height(K, Integer(1)))
[0, -1, 1]

Sage Live

from sage.rings.number_field.bdd_height import bdd_height
K.<g> = QuadraticField(3)
list(bdd_height(K, 1))

Sage

sage: from sage.rings.number_field.bdd_height import bdd_height
sage: K.<g> = QuadraticField(36865)
sage: len(list(bdd_height(K, 101))) # long time (4 s)
131

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import bdd_height
>>> K = QuadraticField(Integer(36865), names=('g',)); (g,) = K._first_ngens(1)
>>> len(list(bdd_height(K, Integer(101)))) # long time (4 s)
131

Sage Live

from sage.rings.number_field.bdd_height import bdd_height
K.<g> = QuadraticField(36865)
len(list(bdd_height(K, 101))) # long time (4 s)

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import bdd_height
>>> K = QuadraticField(Integer(36865), names=('g',)); (g,) = K._first_ngens(1)
>>> len(list(bdd_height(K, Integer(101)))) # long time (4 s)
131

Sage Live

from sage.rings.number_field.bdd_height import bdd_height
K.<g> = QuadraticField(36865)
len(list(bdd_height(K, 101))) # long time (4 s)

Sage

sage: from sage.rings.number_field.bdd_height import bdd_height
sage: K.<g> = NumberField(x^6 + 2)
sage: len(list(bdd_height(K, 60))) # long time (5 s)
1899

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import bdd_height
>>> K = NumberField(x**Integer(6) + Integer(2), names=('g',)); (g,) = K._first_ngens(1)
>>> len(list(bdd_height(K, Integer(60)))) # long time (5 s)
1899

Sage Live

from sage.rings.number_field.bdd_height import bdd_height
K.<g> = NumberField(x^6 + 2)
len(list(bdd_height(K, 60))) # long time (5 s)

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import bdd_height
>>> K = NumberField(x**Integer(6) + Integer(2), names=('g',)); (g,) = K._first_ngens(1)
>>> len(list(bdd_height(K, Integer(60)))) # long time (5 s)
1899

Sage Live

from sage.rings.number_field.bdd_height import bdd_height
K.<g> = NumberField(x^6 + 2)
len(list(bdd_height(K, 60))) # long time (5 s)

Sage

sage: from sage.rings.number_field.bdd_height import bdd_height
sage: K.<g> = NumberField(x^4 - x^3 - 3*x^2 + x + 1)
sage: len(list(bdd_height(K, 10)))
99

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import bdd_height
>>> K = NumberField(x**Integer(4) - x**Integer(3) - Integer(3)*x**Integer(2) + x + Integer(1), names=('g',)); (g,) = K._first_ngens(1)
>>> len(list(bdd_height(K, Integer(10))))
99

Sage Live

from sage.rings.number_field.bdd_height import bdd_height
K.<g> = NumberField(x^4 - x^3 - 3*x^2 + x + 1)
len(list(bdd_height(K, 10)))

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import bdd_height
>>> K = NumberField(x**Integer(4) - x**Integer(3) - Integer(3)*x**Integer(2) + x + Integer(1), names=('g',)); (g,) = K._first_ngens(1)
>>> len(list(bdd_height(K, Integer(10))))
99

Sage Live

from sage.rings.number_field.bdd_height import bdd_height
K.<g> = NumberField(x^4 - x^3 - 3*x^2 + x + 1)
len(list(bdd_height(K, 10)))

sage.rings.number_field.bdd_height.bdd_height_iq(K, height_bound)[source]¶

Compute all elements in the imaginary quadratic field \(K\) which have relative multiplicative height at most height_bound.

The function will only be called with \(K\) an imaginary quadratic field.

If called with \(K\) not an imaginary quadratic, the function will likely yield incorrect output.

ALGORITHM:

This is an implementation of Algorithm 5 in [DK2013].

INPUT:

K – an imaginary quadratic number field
height_bound – a real number

OUTPUT: an iterator of number field elements

EXAMPLES:

Sage

sage: from sage.rings.number_field.bdd_height import bdd_height_iq
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^2 + 191)
sage: for t in bdd_height_iq(K,8):
....:     print(exp(2*t.global_height()))
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import bdd_height_iq
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(2) + Integer(191), names=('a',)); (a,) = K._first_ngens(1)
>>> for t in bdd_height_iq(K,Integer(8)):
...     print(exp(Integer(2)*t.global_height()))
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000
00000000000000

Sage Live

from sage.rings.number_field.bdd_height import bdd_height_iq
x = polygen(ZZ, 'x')
K.<a> = NumberField(x^2 + 191)
for t in bdd_height_iq(K,8):
    print(exp(2*t.global_height()))

There are 175 elements of height at most 10 in \(QQ(\sqrt(-3))\):

Sage

sage: from sage.rings.number_field.bdd_height import bdd_height_iq
sage: K.<a> = NumberField(x^2 + 3)
sage: len(list(bdd_height_iq(K,10)))
175

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import bdd_height_iq
>>> K = NumberField(x**Integer(2) + Integer(3), names=('a',)); (a,) = K._first_ngens(1)
>>> len(list(bdd_height_iq(K,Integer(10))))
175

Sage Live

from sage.rings.number_field.bdd_height import bdd_height_iq
K.<a> = NumberField(x^2 + 3)
len(list(bdd_height_iq(K,10)))

The only elements of multiplicative height 1 in a number field are 0 and the roots of unity:

Sage

sage: from sage.rings.number_field.bdd_height import bdd_height_iq
sage: K.<a> = NumberField(x^2 + x + 1)
sage: list(bdd_height_iq(K,1))
[0, a + 1, a, -1, -a - 1, -a, 1]

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import bdd_height_iq
>>> K = NumberField(x**Integer(2) + x + Integer(1), names=('a',)); (a,) = K._first_ngens(1)
>>> list(bdd_height_iq(K,Integer(1)))
[0, a + 1, a, -1, -a - 1, -a, 1]

Sage Live

from sage.rings.number_field.bdd_height import bdd_height_iq
K.<a> = NumberField(x^2 + x + 1)
list(bdd_height_iq(K,1))

A number field has no elements of multiplicative height less than 1:

Sage

sage: from sage.rings.number_field.bdd_height import bdd_height_iq
sage: K.<a> = NumberField(x^2 + 5)
sage: list(bdd_height_iq(K,0.9))
[]

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import bdd_height_iq
>>> K = NumberField(x**Integer(2) + Integer(5), names=('a',)); (a,) = K._first_ngens(1)
>>> list(bdd_height_iq(K,RealNumber('0.9')))
[]

Sage Live

from sage.rings.number_field.bdd_height import bdd_height_iq
K.<a> = NumberField(x^2 + 5)
list(bdd_height_iq(K,0.9))

sage.rings.number_field.bdd_height.bdd_norm_pr_gens_iq(K, norm_list)[source]¶

Compute generators for all principal ideals in an imaginary quadratic field \(K\) whose norms are in norm_list.

The only keys for the output dictionary are integers n appearing in norm_list.

The function will only be called with \(K\) an imaginary quadratic field.

The function will return a dictionary for other number fields, but it may be incorrect.

INPUT:

K – an imaginary quadratic number field
norm_list – list of positive integers

OUTPUT: dictionary of number field elements, keyed by norm

EXAMPLES:

In \(QQ(i)\), there is one principal ideal of norm 4, two principal ideals of norm 5, but no principal ideals of norm 7:

Sage

sage: from sage.rings.number_field.bdd_height import bdd_norm_pr_gens_iq
sage: x = polygen(ZZ, 'x')
sage: K.<g> = NumberField(x^2 + 1)
sage: L = range(10)
sage: bdd_pr_ideals = bdd_norm_pr_gens_iq(K, L)
sage: bdd_pr_ideals[4]
[2]
sage: bdd_pr_ideals[5]
[-g - 2, -g + 2]
sage: bdd_pr_ideals[7]
[]

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import bdd_norm_pr_gens_iq
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(2) + Integer(1), names=('g',)); (g,) = K._first_ngens(1)
>>> L = range(Integer(10))
>>> bdd_pr_ideals = bdd_norm_pr_gens_iq(K, L)
>>> bdd_pr_ideals[Integer(4)]
[2]
>>> bdd_pr_ideals[Integer(5)]
[-g - 2, -g + 2]
>>> bdd_pr_ideals[Integer(7)]
[]

Sage Live

from sage.rings.number_field.bdd_height import bdd_norm_pr_gens_iq
x = polygen(ZZ, 'x')
K.<g> = NumberField(x^2 + 1)
L = range(10)
bdd_pr_ideals = bdd_norm_pr_gens_iq(K, L)
bdd_pr_ideals[4]
bdd_pr_ideals[5]
bdd_pr_ideals[7]

There are no ideals in the ring of integers with negative norm:

Sage

sage: from sage.rings.number_field.bdd_height import bdd_norm_pr_gens_iq
sage: K.<g> = NumberField(x^2 + 10)
sage: L = range(-5,-1)
sage: bdd_pr_ideals = bdd_norm_pr_gens_iq(K,L)
sage: bdd_pr_ideals
{-5: [], -4: [], -3: [], -2: []}

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import bdd_norm_pr_gens_iq
>>> K = NumberField(x**Integer(2) + Integer(10), names=('g',)); (g,) = K._first_ngens(1)
>>> L = range(-Integer(5),-Integer(1))
>>> bdd_pr_ideals = bdd_norm_pr_gens_iq(K,L)
>>> bdd_pr_ideals
{-5: [], -4: [], -3: [], -2: []}

Sage Live

from sage.rings.number_field.bdd_height import bdd_norm_pr_gens_iq
K.<g> = NumberField(x^2 + 10)
L = range(-5,-1)
bdd_pr_ideals = bdd_norm_pr_gens_iq(K,L)
bdd_pr_ideals

Calling a key that is not in the input norm_list raises a KeyError:

Sage

sage: from sage.rings.number_field.bdd_height import bdd_norm_pr_gens_iq
sage: K.<g> = NumberField(x^2 + 20)
sage: L = range(100)
sage: bdd_pr_ideals = bdd_norm_pr_gens_iq(K, L)
sage: bdd_pr_ideals[100]
Traceback (most recent call last):
...
KeyError: 100

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import bdd_norm_pr_gens_iq
>>> K = NumberField(x**Integer(2) + Integer(20), names=('g',)); (g,) = K._first_ngens(1)
>>> L = range(Integer(100))
>>> bdd_pr_ideals = bdd_norm_pr_gens_iq(K, L)
>>> bdd_pr_ideals[Integer(100)]
Traceback (most recent call last):
...
KeyError: 100

Sage Live

from sage.rings.number_field.bdd_height import bdd_norm_pr_gens_iq
K.<g> = NumberField(x^2 + 20)
L = range(100)
bdd_pr_ideals = bdd_norm_pr_gens_iq(K, L)
bdd_pr_ideals[100]

sage.rings.number_field.bdd_height.bdd_norm_pr_ideal_gens(K, norm_list)[source]¶

Compute generators for all principal ideals in a number field \(K\) whose norms are in norm_list.

INPUT:

K – a number field
norm_list – list of positive integers

OUTPUT: dictionary of number field elements, keyed by norm

EXAMPLES:

There is only one principal ideal of norm 1, and it is generated by the element 1:

Sage

sage: from sage.rings.number_field.bdd_height import bdd_norm_pr_ideal_gens
sage: K.<g> = QuadraticField(101)
sage: bdd_norm_pr_ideal_gens(K, [1])
{1: [1]}

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import bdd_norm_pr_ideal_gens
>>> K = QuadraticField(Integer(101), names=('g',)); (g,) = K._first_ngens(1)
>>> bdd_norm_pr_ideal_gens(K, [Integer(1)])
{1: [1]}

Sage Live

from sage.rings.number_field.bdd_height import bdd_norm_pr_ideal_gens
K.<g> = QuadraticField(101)
bdd_norm_pr_ideal_gens(K, [1])

Sage

sage: from sage.rings.number_field.bdd_height import bdd_norm_pr_ideal_gens
sage: K.<g> = QuadraticField(123)
sage: bdd_norm_pr_ideal_gens(K, range(5))
{0: [0], 1: [1], 2: [g + 11], 3: [], 4: [2]}

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import bdd_norm_pr_ideal_gens
>>> K = QuadraticField(Integer(123), names=('g',)); (g,) = K._first_ngens(1)
>>> bdd_norm_pr_ideal_gens(K, range(Integer(5)))
{0: [0], 1: [1], 2: [g + 11], 3: [], 4: [2]}

Sage Live

from sage.rings.number_field.bdd_height import bdd_norm_pr_ideal_gens
K.<g> = QuadraticField(123)
bdd_norm_pr_ideal_gens(K, range(5))

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import bdd_norm_pr_ideal_gens
>>> K = QuadraticField(Integer(123), names=('g',)); (g,) = K._first_ngens(1)
>>> bdd_norm_pr_ideal_gens(K, range(Integer(5)))
{0: [0], 1: [1], 2: [g + 11], 3: [], 4: [2]}

Sage Live

from sage.rings.number_field.bdd_height import bdd_norm_pr_ideal_gens
K.<g> = QuadraticField(123)
bdd_norm_pr_ideal_gens(K, range(5))

Sage

sage: from sage.rings.number_field.bdd_height import bdd_norm_pr_ideal_gens
sage: x = polygen(ZZ, 'x')
sage: K.<g> = NumberField(x^5 - x + 19)
sage: b = bdd_norm_pr_ideal_gens(K, range(30))
sage: key = ZZ(28)
sage: b[key]
[157*g^4 - 139*g^3 - 369*g^2 + 848*g + 158, g^4 + g^3 - g - 7]

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import bdd_norm_pr_ideal_gens
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(5) - x + Integer(19), names=('g',)); (g,) = K._first_ngens(1)
>>> b = bdd_norm_pr_ideal_gens(K, range(Integer(30)))
>>> key = ZZ(Integer(28))
>>> b[key]
[157*g^4 - 139*g^3 - 369*g^2 + 848*g + 158, g^4 + g^3 - g - 7]

Sage Live

from sage.rings.number_field.bdd_height import bdd_norm_pr_ideal_gens
x = polygen(ZZ, 'x')
K.<g> = NumberField(x^5 - x + 19)
b = bdd_norm_pr_ideal_gens(K, range(30))
key = ZZ(28)
b[key]

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import bdd_norm_pr_ideal_gens
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(5) - x + Integer(19), names=('g',)); (g,) = K._first_ngens(1)
>>> b = bdd_norm_pr_ideal_gens(K, range(Integer(30)))
>>> key = ZZ(Integer(28))
>>> b[key]
[157*g^4 - 139*g^3 - 369*g^2 + 848*g + 158, g^4 + g^3 - g - 7]

Sage Live

from sage.rings.number_field.bdd_height import bdd_norm_pr_ideal_gens
x = polygen(ZZ, 'x')
K.<g> = NumberField(x^5 - x + 19)
b = bdd_norm_pr_ideal_gens(K, range(30))
key = ZZ(28)
b[key]

sage.rings.number_field.bdd_height.integer_points_in_polytope(matrix, interval_radius)[source]¶

Return the set of integer points in the polytope obtained by acting on a cube by a linear transformation.

Given an \(r\)-by-\(r\) matrix matrix and a real number interval_radius, this function finds all integer lattice points in the polytope obtained by transforming the cube [-interval_radius, interval_radius]^r via the linear map induced by matrix.

INPUT:

matrix – a square matrix of real numbers
interval_radius – a real number

OUTPUT: list of tuples of integers

EXAMPLES:

Stretch the interval \([-1,1]\) by a factor of 2 and find the integers in the resulting interval:

Sage

sage: from sage.rings.number_field.bdd_height import integer_points_in_polytope
sage: m = matrix([2])
sage: r = 1
sage: integer_points_in_polytope(m, r)
[(-2), (-1), (0), (1), (2)]

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import integer_points_in_polytope
>>> m = matrix([Integer(2)])
>>> r = Integer(1)
>>> integer_points_in_polytope(m, r)
[(-2), (-1), (0), (1), (2)]

Sage Live

from sage.rings.number_field.bdd_height import integer_points_in_polytope
m = matrix([2])
r = 1
integer_points_in_polytope(m, r)

Integer points inside a parallelogram:

Sage

sage: from sage.rings.number_field.bdd_height import integer_points_in_polytope
sage: m = matrix([[1, 2], [3, 4]])
sage: r = RealField()(1.3)
sage: integer_points_in_polytope(m, r)
[(-3, -7), (-2, -5), (-2, -4), (-1, -3), (-1, -2), (-1, -1), (0, -1),
 (0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 4), (2, 5), (3, 7)]

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import integer_points_in_polytope
>>> m = matrix([[Integer(1), Integer(2)], [Integer(3), Integer(4)]])
>>> r = RealField()(RealNumber('1.3'))
>>> integer_points_in_polytope(m, r)
[(-3, -7), (-2, -5), (-2, -4), (-1, -3), (-1, -2), (-1, -1), (0, -1),
 (0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 4), (2, 5), (3, 7)]

Sage Live

from sage.rings.number_field.bdd_height import integer_points_in_polytope
m = matrix([[1, 2], [3, 4]])
r = RealField()(1.3)
integer_points_in_polytope(m, r)

Integer points inside a parallelepiped:

Sage

sage: from sage.rings.number_field.bdd_height import integer_points_in_polytope
sage: m = matrix([[1.2,3.7,0.2], [-5.3,-.43,3], [1.2,4.7,-2.1]])
sage: r = 2.2
sage: L = integer_points_in_polytope(m, r)
sage: len(L)
4143

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import integer_points_in_polytope
>>> m = matrix([[RealNumber('1.2'),RealNumber('3.7'),RealNumber('0.2')], [-RealNumber('5.3'),-RealNumber('.43'),Integer(3)], [RealNumber('1.2'),RealNumber('4.7'),-RealNumber('2.1')]])
>>> r = RealNumber('2.2')
>>> L = integer_points_in_polytope(m, r)
>>> len(L)
4143

Sage Live

from sage.rings.number_field.bdd_height import integer_points_in_polytope
m = matrix([[1.2,3.7,0.2], [-5.3,-.43,3], [1.2,4.7,-2.1]])
r = 2.2
L = integer_points_in_polytope(m, r)
len(L)

If interval_radius is 0, the output should include only the zero tuple:

Sage

sage: from sage.rings.number_field.bdd_height import integer_points_in_polytope
sage: m = matrix([[1,2,3,7], [4,5,6,2], [7,8,9,3], [0,3,4,5]])
sage: integer_points_in_polytope(m, 0)
[(0, 0, 0, 0)]

Python

>>> from sage.all import *
>>> from sage.rings.number_field.bdd_height import integer_points_in_polytope
>>> m = matrix([[Integer(1),Integer(2),Integer(3),Integer(7)], [Integer(4),Integer(5),Integer(6),Integer(2)], [Integer(7),Integer(8),Integer(9),Integer(3)], [Integer(0),Integer(3),Integer(4),Integer(5)]])
>>> integer_points_in_polytope(m, Integer(0))
[(0, 0, 0, 0)]

Sage Live

from sage.rings.number_field.bdd_height import integer_points_in_polytope
m = matrix([[1,2,3,7], [4,5,6,2], [7,8,9,3], [0,3,4,5]])
integer_points_in_polytope(m, 0)