Opened 2 years ago

Last modified 4 months ago

#30017 needs_work defect

Random elements in quadratic field always integral

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.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:

Status badges

Description (last modified by slelievre)

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 mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:2 Changed 18 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

comment:3 Changed 18 months ago by gh-DaveWitteMorris

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 gh-DaveWitteMorris

  • Authors set to Dave Morris

comment:5 Changed 18 months ago by gh-DaveWitteMorris

  • Branch set to public/30017

comment:6 Changed 18 months ago by gh-DaveWitteMorris

  • Commit set to 28bc8d8e722f9adade100908ef6bf18468687c3c
  • Milestone changed from sage-9.4 to sage-9.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:

28bc8d8trac 30017: denom_bound is None

comment:7 Changed 18 months ago by git

  • Commit changed from 28bc8d8e722f9adade100908ef6bf18468687c3c to 58d0c6bd6ab91420cc64d6a3e42f91da70b395d3

Branch pushed to git repo; I updated commit sha1. New commits:

58d0c6bfix doctest failures

comment:8 Changed 18 months ago by roed

  • 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 gh-DaveWitteMorris

  • 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 mkoeppe

  • Milestone changed from sage-9.3 to sage-9.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 roed

  • 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 slelievre

  • 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 double-colon.

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 mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5

Setting a new milestone for this ticket based on a cursory review.

comment:14 Changed 8 months ago by mkoeppe

  • Milestone changed from sage-9.5 to sage-9.6

comment:15 Changed 4 months ago by mkoeppe

  • Milestone changed from sage-9.6 to sage-9.7
Note: See TracTickets for help on using tickets.