#25379 closed defect (fixed)

random failure in QuadraticResidueCodeOddPair

Reported by: vdelecroix Owned by:
Priority: blocker Milestone: sage-8.3
Component: coding theory Keywords: thursdaysbdx, random_fail
Cc: cremona Merged in:
Authors: Jeroen Demeyer Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: 28a4212 (Commits) Commit: 28a4212ce9b8479d305c850a2959a28e07c93b6e
Dependencies: Stopgaps:

Description

Reported on https://groups.google.com/forum/#!topic/sage-release/zh04lo8d44U and also on some patchbots

sage -t --long src/sage/coding/code_constructions.py
**********************************************************************
File "src/sage/coding/code_constructions.py", line 624, in sage.coding.code_constructions.QuadraticResidueCodeOddPair
Failed example:
    codes.QuadraticResidueCodeOddPair(17, GF(13))
Exception raised:
    Traceback (most recent call last):
      File "/home/vdelecro/sage_patchbot/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 562, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/vdelecro/sage_patchbot/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 972, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.coding.code_constructions.QuadraticResidueCodeOddPair[0]>", line 1, in <module>
        codes.QuadraticResidueCodeOddPair(Integer(17), GF(Integer(13)))
      File "/home/vdelecro/sage_patchbot/local/lib/python2.7/site-packages/sage/coding/code_constructions.py", line 666, in QuadraticResidueCodeOddPair
        return DuadicCodeOddPair(F,Q,N)
      File "/home/vdelecro/sage_patchbot/local/lib/python2.7/site-packages/sage/coding/code_constructions.py", line 425, in DuadicCodeOddPair
        gg1 = P2(coeffs1)
      File "sage/structure/parent.pyx", line 920, in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9734)
        return mor._call_(x)
      File "sage/structure/coerce_maps.pyx", line 145, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4555)
        raise
      File "sage/structure/coerce_maps.pyx", line 140, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4423)
        return C._element_constructor(x)
      File "/home/vdelecro/sage_patchbot/local/lib/python2.7/site-packages/sage/rings/polynomial/polynomial_ring.py", line 404, in _element_constructor_
        return C(self, x, check=check, is_gen=False, construct=construct)
      File "sage/rings/polynomial/polynomial_zmod_flint.pyx", line 100, in sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint.__init__ (build/cythonized/sage/rings/polynomial/polynomial_zmod_flint.cpp:14356)
        lst = [k(i) for i in x]
      File "sage/structure/parent.pyx", line 920, in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9734)
        return mor._call_(x)
      File "sage/rings/finite_rings/hom_prime_finite_field.pyx", line 46, in sage.rings.finite_rings.hom_prime_finite_field.SectionFiniteFieldHomomorphism_prime._call_ (build/cythonized/sage/rings/finite_rings/hom_prime_finite_field.c:3457)
        raise ValueError("%s is not in the image of %s" % (x, self._inverse))
    ValueError: 10*z^3 + 9*z^2 + z is not in the image of (map internal to coercion system -- copy before use)
    Ring morphism:
      From: Finite Field of size 13
      To:   Finite Field in z of size 13^4
**********************************************************************
1 item had failures:
   1 of  13 in sage.coding.code_constructions.QuadraticResidueCodeOddPair
    [146 tests, 1 failure, 2.83 s]
----------------------------------------------------------------------
sage -t --long src/sage/coding/code_constructions.py  # 1 doctest failed
----------------------------------------------------------------------

Change History (18)

comment:1 Changed 19 months ago by vdelecroix

  • Summary changed from coercion and QuadraticResidueCodeOddPair to random failure in QuadraticResidueCodeOddPair

comment:2 Changed 19 months ago by gh-darijgr

There's a function in code_constructions.py that makes me dizzy:

def _lift2smallest_field(a):
    """
    INPUT: a is an element of a finite field GF(q)

    OUTPUT: the element b of the smallest subfield F of GF(q) for
    which F(b)=a.

    EXAMPLES::

        sage: from sage.coding.code_constructions import _lift2smallest_field
        sage: FF.<z> = GF(3^4,"z")
        sage: a = z^10
        sage: _lift2smallest_field(a)
        (2*z + 1, Finite Field in z of size 3^2)
        sage: a = z^40
        sage: _lift2smallest_field(a)
        (2, Finite Field of size 3)

    AUTHORS:

    - John Cremona
    """
    FF = a.parent()
    k = FF.degree()
    if k == 1:
        return a, FF
    pol = a.minimal_polynomial()
    d = pol.degree()
    if d == k:
        return a, FF
    p = FF.characteristic()
    F = GF(p**d,"z")
    b = pol.roots(F,multiplicities=False)[0]
    return b, F

How does pol.roots(F,multiplicities=False)[0] know to return the *right* root of pol (i.e., the one that coerces back to a), rather than a random root?

comment:3 Changed 18 months ago by chapoton

  • Authors set to Frédéric Chapoton
  • Branch set to u/chapoton/25379
  • Commit set to ea8fa5c491d9055ed1b213526d439ce82177de34
  • Status changed from new to needs_review

Here is a tentative of enhancement of this lifting procedure.


New commits:

ea8fa5cenhance one lifting procedure in code constructions

comment:4 Changed 17 months ago by vbraun

  • Cc cremona added

John, do you want to review this?

comment:5 Changed 17 months ago by roed

I'm not sure about the context here, but there are serious performance penalties in using GF(q**n) rather than GF(q**n) as n increases. Is there a reason we need to do so?

comment:6 Changed 17 months ago by chapoton

could you please clarify ?

comment:7 follow-up: Changed 17 months ago by roed

We've added the following comment

This is now designed to work only with finite fields with automatic names, built using ``GF(q)``.

and changed FF = GF(q**k,"z") to FF = GF(q**k) meaning that we're using pseudo-Conway polynomials for the extension if k is large, rather than a randomly selected polynomial. Here's some timings (I use number=1 and repeat=1 to eliminate caching effects).

sage: for k in srange(100,150):
....:     if len(k.factor()) < 3: continue
....:     print "3^%s conway "%k,
....:     timeit("FF = GF(3^%s)"%k,number=1,repeat=1)
....:     print "3^%s random "%k,
....:     timeit("FF = GF(3^%s,'z')"%k,number=1,repeat=1)
3^102 conway  1 loops, best of 1: 717 ms per loop
3^102 random  1 loops, best of 1: 2.93 ms per loop
3^105 conway  1 loops, best of 1: 537 ms per loop
3^105 random  1 loops, best of 1: 3.1 ms per loop
3^110 conway  1 loops, best of 1: 794 ms per loop
3^110 random  1 loops, best of 1: 3.17 ms per loop
3^114 conway  1 loops, best of 1: 962 ms per loop
3^114 random  1 loops, best of 1: 3.41 ms per loop
3^120 conway  1 loops, best of 1: 1.25 s per loop
3^120 random  1 loops, best of 1: 3.77 ms per loop
3^126 conway  1 loops, best of 1: 1.47 s per loop
3^126 random  1 loops, best of 1: 3.51 ms per loop
3^130 conway  1 loops, best of 1: 1.06 s per loop
3^130 random  1 loops, best of 1: 6.67 ms per loop
3^132 conway  1 loops, best of 1: 1.26 s per loop
3^132 random  1 loops, best of 1: 5.12 ms per loop
3^138 conway  1 loops, best of 1: 1.57 s per loop
3^138 random  1 loops, best of 1: 3.71 ms per loop
3^140 conway  1 loops, best of 1: 1.5 s per loop
3^140 random  1 loops, best of 1: 4.89 ms per loop

These will continue to worsen as the number of factors of the degree increases.

comment:8 Changed 17 months ago by chapoton

Ok. The modified function is only used in this precise file, and I have no idea if its use here involve finite fields for high powers of primes or not.

What is crucial is to have finite fields that have a coherent system of inclusions, all of them sitting in a common algebraic closure. If I understood correctly, this is only ensured by using the syntax GF(q) without names.

comment:9 Changed 17 months ago by jdemeyer

In any case, there should at least be a test showing that it doesn't work if the assumption

This is now designed to work only with finite fields
with automatic names, built using ``GF(q)``.

does not hold.

comment:10 in reply to: ↑ 7 Changed 17 months ago by jdemeyer

Replying to roed:

meaning that we're using pseudo-Conway polynomials for the extension if k is large, rather than a randomly selected polynomial.

When you look at the code, it's certainly assuming implicitly(!) that the defining polynomial is primitive (its root generates the multiplicative group).

comment:11 Changed 17 months ago by jdemeyer

There are more issues with this code:

sage: S1 = [1,3,4,5,7,12,13]; S2 = [2,6,8,9,10,11,14]
sage: codes.DuadicCodeEvenPair(GF(3), S1, S2)
...
ArithmeticError: multiplicative order of 3 not defined since it is not a unit modulo 15

comment:12 Changed 17 months ago by jdemeyer

  • Authors changed from Frédéric Chapoton to Jeroen Demeyer
  • Branch u/chapoton/25379 deleted
  • Commit ea8fa5c491d9055ed1b213526d439ce82177de34 deleted
  • Status changed from needs_review to needs_work

There are various issues with these functions, I think a stopgap is the best solution. I opened #25896 for the actual issues.

comment:13 Changed 17 months ago by jdemeyer

  • Branch set to u/jdemeyer/25379

comment:14 Changed 17 months ago by jdemeyer

  • Commit set to 3eee0002a1ea161b861269564292e144c77f9cfd
  • Status changed from needs_work to needs_review

New commits:

3eee000Add a stopgap to DuadicCodeEvenPair/DuadicCodeOddPair

comment:15 Changed 17 months ago by git

  • Commit changed from 3eee0002a1ea161b861269564292e144c77f9cfd to 28a4212ce9b8479d305c850a2959a28e07c93b6e

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

28a4212Add a stopgap to DuadicCodeEvenPair/DuadicCodeOddPair

comment:16 Changed 17 months ago by chapoton

  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok

comment:17 Changed 17 months ago by gh-timokau

  • Keywords random_fail added

comment:18 Changed 17 months ago by vbraun

  • Branch changed from u/jdemeyer/25379 to 28a4212ce9b8479d305c850a2959a28e07c93b6e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.