DuadicCodeEvenPair/DuadicCodeOddPair are broken

[jdemeyer]

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

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

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

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

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]

comment:1

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

---

New commits:

ea8fa5c

enhance one lifting procedure in code constructions

[jdemeyer]

Branch: u/chapoton/25379

[jdemeyer]

Commit: ea8fa5c

[jdemeyer]

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:
-    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
-**********************************************************************
+sage: S1 = [1,3,4,5,7,12,13]; S2 = [2,6,8,9,10,11,14]
+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
 ```
 
-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]

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]

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]

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 @@
 
 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.
+
 I can imagine that 1. and 2. should be considered "bad input" but in that case the documentation must be updated.

[jdemeyer]

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]

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]

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