Opened 2 years ago
Last modified 4 months ago
#30017 needs_work defect
Random elements in quadratic field always integral
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sage9.7 
Component:  number fields  Keywords:  random, number fields 
Cc:  slelievre  Merged in:  
Authors:  Dave Morris  Reviewers:  David Roe, Samuel Lelièvre 
Report Upstream:  N/A  Work issues:  
Branch:  public/30017 (Commits, GitHub, GitLab)  Commit:  58d0c6bd6ab91420cc64d6a3e42f91da70b395d3 
Dependencies:  Stopgaps: 
Description (last modified by )
We don't expect all random elements in a number field to be integral.
But in Sage <= 9.3.rc4, it is the case:
sage: K = QuadraticField(2) sage: all(K.random_element().is_integral() for _ in range(1000)) True
We address this problem so that without indication
of denominator bound random elements won't necessarily
be integral. To pick random integral elements, one can
always use den_bound=1
.
Change History (15)
comment:1 Changed 2 years ago by
 Milestone changed from sage9.2 to sage9.3
comment:2 Changed 18 months ago by
 Milestone changed from sage9.3 to sage9.4
comment:3 Changed 18 months ago by
The problem seems to come from the following lines in the definition of NumberFieldElement_quadratic._randomize()
in src/sage/rings/number_field/number_field_element_quadratic.pyx
, which set the default denominator bound to be 1.
# normalize denominator bound if den_bound is None or den_bound < 1: den_bound = 1
The problem goes away if an explicit denominator bound is specified:
sage: K = QuadraticField(2) sage: for _ in range(5): ....: print(K.random_element(den_bound=10)) 1/4*a + 3/5 1/8*a  1 1/10*a  4/7 6/7*a + 391/5 9/2
comment:4 Changed 18 months ago by
comment:5 Changed 18 months ago by
 Branch set to public/30017
comment:6 Changed 18 months ago by
 Commit set to 28bc8d8e722f9adade100908ef6bf18468687c3c
 Milestone changed from sage9.4 to sage9.3
 Status changed from new to needs_review
The PR adds a special case for den_bound=None
, and also adds some doctests.
New commits:
28bc8d8  trac 30017: denom_bound is None

comment:7 Changed 18 months ago by
 Commit changed from 28bc8d8e722f9adade100908ef6bf18468687c3c to 58d0c6bd6ab91420cc64d6a3e42f91da70b395d3
Branch pushed to git repo; I updated commit sha1. New commits:
58d0c6b  fix doctest failures

comment:8 Changed 18 months ago by
 Reviewers set to David Roe
 Status changed from needs_review to needs_work
The approach looks fine to me. The one change I would suggest is in tests: the cases where you use a random doctest tag (a._random_element() # random
) shouldn't be needed, since the random seed should make this consistent between doctest runs.
comment:9 Changed 18 months ago by
 Status changed from needs_work to needs_review
I prefer not to make that change, because I hope that doctests will soon use random seeds (see #29935).
comment:10 Changed 17 months ago by
 Milestone changed from sage9.3 to sage9.4
Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review of ticket status, priority, and last modification date.
comment:11 Changed 16 months ago by
 Status changed from needs_review to positive_review
Ok. I have some concerns about #29935, but that's an issue for another ticket.
comment:12 Changed 16 months ago by
 Cc slelievre added
 Description modified (diff)
 Reviewers changed from David Roe to David Roe, Samuel Lelièvre
 Status changed from positive_review to needs_work
This is a nice improvement.
There is one problem (see a below).
My other comments and suggestions (see b to e below) can be ignored or kept for later.
a.
The tests blocks in _randomize
are missing the doublecolon.
b.
Suggestion: state one can pick random integral elements
by setting den_bound
to one.
This could be added to the examples:
With denominator bound one, we always get integral elements:: sage: K = QuadraticField(2) sage: uu = [K.random_element(den_bound=1) for _ in range(5)] sage: uu # random [0, a + 2, 12*a  2, a + 1, a  2] sage: all(u.is_integral() for u in uu) True
This could be added to the tests:
With denominator bound one, we always get integral elements:: sage: def random_number_field(max_degree=3): ....: R.<x> = ZZ[] ....: p = x^2 ....: while not p.is_irreducible(): ....: d = ZZ.random_element(2, max_degree + 1) ....: p = x^d + R.random_element(degree=(0, d  1)) ....: return NumberField(p, 'a') sage: all(u.is_integral() ....: for _ in range(10) ....: for K in [random_number_field(max_degree=8)] ....: for u in [K.random_element(den_bound=1)]) True Without this constraint, we don't always get them:: sage: all(u.is_integral() ....: for _ in range(100) ....: for K in [random_number_field(max_degree=8)] ....: for u in [K.random_element()]) False
c.
One test builds a quadratic field using a random nonsquare in [100 .. 99]
:
sage: non_squares = [a for a in srange(100, 100) if not a.is_square()] sage: K = QuadraticField(non_squares[randint(0, len(non_squares)1)])
Here are some alternative ways to pick a random quadratic field.
We can use random.choice
to select a list element at random:
sage: import random sage: non_squares = [a for a in srange(100, 100) if not a.is_square()] sage: K = QuadraticField(random.choice(non_squares))
Or skip building a list by picking at random until we are happy:
sage: a = ZZ.random_element(100, 100) sage: while a.is_square(): ....: a = ZZ.random_element(100, 100) sage: K = QuadraticField(a)
d.
One test checks that five random elements are pairwise distinct:
sage: n = 5 sage: randlist = [K.random_element() for _ in range(n)] sage: all(randlist[i] != randlist[j] for i in range(n) for j in range(n) ....: if i != j) True
Here are alternative ways to write the test.
Have j
run through range(i)
:
sage: n = 5 sage: uu = [K.random_element() for _ in range(n)] sage: all(uu[i] != uu[j] for i in range(n) for j in range(i)) True
Use enumerate
:
sage: n = 5 sage: uu = [K.random_element() for _ in range(n)] sage: all(ui != uj for i, ui in enumerate(uu) for uj in uu[:i]) True
Use a set:
sage: n = 5 sage: len(set(K.random_element() for _ in range(n)) == n True
e.
The documentation could also mention one can pick random integral
elements using the random_element
method of the number field's
"ring of integers" or "maximal order".
sage: K = QuadraticField(2) sage: O = K.maximal_order() sage: O.random_element() # random 5*a  6 sage: O = K.ring_of_integers() sage: O.random_element() # random 4*a + 1
comment:13 Changed 13 months ago by
 Milestone changed from sage9.4 to sage9.5
Setting a new milestone for this ticket based on a cursory review.
comment:14 Changed 8 months ago by
 Milestone changed from sage9.5 to sage9.6
comment:15 Changed 4 months ago by
 Milestone changed from sage9.6 to sage9.7
Setting new milestone based on a cursory review of ticket status, priority, and last modification date.