search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.33k stars 453 forks source link

DuadicCodeEvenPair/DuadicCodeOddPair are broken #25896

Open jdemeyer opened 6 years ago

jdemeyer commented 6 years ago
  1. The use of _lift2smallest_field is very dubious:
sage: S1 = [1,3,4,5,7,12,13]; S2 = [2,6,8,9,10,11,14]
sage: from sage.coding.code_constructions import _is_a_splitting
sage: _is_a_splitting(S1, S2, 15)
True
sage: codes.DuadicCodeEvenPair(GF(7), S1, S2)
...
ValueError: 5*z + 2 is not in the image of (map internal to coercion system -- copy before use)
Ring morphism:
  From: Finite Field of size 7
  To:   Finite Field in z of size 7^2
  1. It doesn't work as documented:
sage: S1 = [1,3,4,5,7,12,13]; S2 = [2,6,8,9,10,11,14]
sage: from sage.coding.code_constructions import _is_a_splitting
sage: _is_a_splitting(S1, S2, 15)
True
sage: codes.DuadicCodeEvenPair(GF(3), S1, S2)
---------------------------------------------------------------------------
ArithmeticError                           Traceback (most recent call last)
<ipython-input-27-0b1b7f661976> in <module>()
----> 1 codes.DuadicCodeEvenPair(GF(Integer(3)), S1, S2)

/usr/local/src/sage-config/local/lib/python2.7/site-packages/sage/coding/code_constructions.pyc in DuadicCodeEvenPair(F, S1, S2)
    359         raise TypeError("%s, %s must be a splitting of %s."%(S1,S2,n))
    360     q = F.order()
--> 361     k = Mod(q,n).multiplicative_order()
    362     FF = GF(q**k,"z")
    363     z = FF.gen()

/usr/local/src/sage-config/local/lib/python2.7/site-packages/sage/rings/finite_rings/integer_mod.pyx in sage.rings.finite_rings.integer_mod.IntegerMod_abstract.multiplicative_order (build/cythonized/sage/rings/finite_rings/integer_mod.c:22221)()
   1766             return sage.rings.integer.Integer(self.__pari__().znorder())
   1767         except PariError:
-> 1768             raise ArithmeticError("multiplicative order of %s not defined since it is not a unit modulo %s"%(
   1769                 self, self.__modulus.sageInteger))
   1770 

ArithmeticError: multiplicative order of 3 not defined since it is not a unit modulo 15

  1. The code assumes implicitly that the generator of a finite field is a multiplicative generator (this is easy to fix).

  2. Since you explicitly refer to the docstring of _is_a_splitting, the latter should be public and documented.

I can imagine that 1. and 2. should be considered "bad input" but that's not clear. It seems that there is an additional hidden assumption that q S1 = S1 (and then also q S2 = S2).

Updating the documentation is the absolute minimum that must be done before anything else: if we don't even know what the function should do, we cannot fix it.

Component: coding theory

Stopgaps: #25379

Branch/Commit: u/chapoton/25379 @ ea8fa5c

Issue created by migration from https://trac.sagemath.org/ticket/25896

jdemeyer commented 6 years ago
comment:1

Just adding the branch for reference, it probably isn't a good solution.

New commits:

ea8fa5cenhance one lifting procedure in code constructions
jdemeyer commented 6 years ago

Branch: u/chapoton/25379

jdemeyer commented 6 years ago

Commit: ea8fa5c

jdemeyer commented 6 years ago

Description changed:

--- 
+++ 
@@ -1,47 +1,16 @@
 1. The use of `_lift2smallest_field` is very dubious:

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

-2. The code assumes implicitly that the generator of a finite field is a multiplicative generator

-3. It doesn't work as documented: +2. It doesn't work as documented:

 sage: S1 = [1,3,4,5,7,12,13]; S2 = [2,6,8,9,10,11,14]
@@ -70,3 +39,7 @@

 ArithmeticError: multiplicative order of 3 not defined since it is not a unit modulo 15

+ +3. The code assumes implicitly that the generator of a finite field is a multiplicative generator (this is easy to fix). + +I can imagine that 1. and 2. should be considered "bad input" but in that case the documentation must be updated.

jdemeyer commented 6 years ago

Description changed:

--- 
+++ 
@@ -42,4 +42,6 @@

 3. The code assumes implicitly that the generator of a finite field is a multiplicative generator (this is easy to fix).

+4. It becomes very inefficient as `q` gets large.
+
 I can imagine that 1. and 2. should be considered "bad input" but in that case the documentation must be updated.
jdemeyer commented 6 years ago

Description changed:

--- 
+++ 
@@ -42,6 +42,6 @@

 3. The code assumes implicitly that the generator of a finite field is a multiplicative generator (this is easy to fix).

-4. It becomes very inefficient as `q` gets large.
+4. It becomes very inefficient as `n` gets moderately large.

 I can imagine that 1. and 2. should be considered "bad input" but in that case the documentation must be updated.
jdemeyer commented 6 years ago

Description changed:

--- 
+++ 
@@ -2,6 +2,9 @@

sage: S1 = [1,3,4,5,7,12,13]; S2 = [2,6,8,9,10,11,14] +sage: from sage.coding.code_constructions import _is_a_splitting +sage: _is_a_splitting(S1, S2, 15) +True sage: codes.DuadicCodeEvenPair(GF(7), S1, S2) ... ValueError: 5*z + 2 is not in the image of (map internal to coercion system -- copy before use) @@ -44,4 +47,6 @@

  1. It becomes very inefficient as n gets moderately large.

+5. Since you explicitly refer to the docstring of _is_a_splitting, the latter should be public and documented. + I can imagine that 1. and 2. should be considered "bad input" but in that case the documentation must be updated.

jdemeyer commented 6 years ago

Description changed:

--- 
+++ 
@@ -49,4 +49,4 @@

 5. Since you explicitly refer to the docstring of `_is_a_splitting`, the latter should be public and documented.

-I can imagine that 1. and 2. should be considered "bad input" but in that case the documentation must be updated.
+I can imagine that 1. and 2. should be considered "bad input" but in that case the documentation must be updated. That's the absolute minimum that must be done before anything else: if we don't even know what the function *should* do, we cannot fix it.
jdemeyer commented 6 years ago

Description changed:

--- 
+++ 
@@ -49,4 +49,6 @@

 5. Since you explicitly refer to the docstring of `_is_a_splitting`, the latter should be public and documented.

-I can imagine that 1. and 2. should be considered "bad input" but in that case the documentation must be updated. That's the absolute minimum that must be done before anything else: if we don't even know what the function *should* do, we cannot fix it.
+I can imagine that 1. and 2. should be considered "bad input" but that's not clear. It seems that there is an additional hidden assumption that `q S1 = S1` (and then also `q S2 = S2`).
+
+Updating the documentation is the absolute minimum that must be done before anything else: if we don't even know what the function *should* do, we cannot fix it.
jdemeyer commented 6 years ago

Description changed:

--- 
+++ 
@@ -45,9 +45,7 @@

 3. The code assumes implicitly that the generator of a finite field is a multiplicative generator (this is easy to fix).

-4. It becomes very inefficient as `n` gets moderately large.
-
-5. Since you explicitly refer to the docstring of `_is_a_splitting`, the latter should be public and documented.
+4. Since you explicitly refer to the docstring of `_is_a_splitting`, the latter should be public and documented.

 I can imagine that 1. and 2. should be considered "bad input" but that's not clear. It seems that there is an additional hidden assumption that `q S1 = S1` (and then also `q S2 = S2`).