Opened 2 years ago

# Random elements in quadratic field always integral

Reported by: Owned by: gh-kliem major sage-9.7 number fields random, number fields slelievre Dave Morris David Roe, Samuel Lelièvre N/A public/30017 58d0c6bd6ab91420cc64d6a3e42f91da70b395d3

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`.

### 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

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

 ​28bc8d8 `trac 30017: denom_bound is None`

### comment:7 Changed 18 months ago by git

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

 ​58d0c6b `fix 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

• 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: 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()]
```

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()]
```

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)
```

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.