Delsarte (or linear programming) bounds#

This module provides LP upper bounds for the parameters of codes, introduced in by P. Delsarte in [De1973].

The exact LP solver PPL is used by default, ensuring that no rounding/overflow problems occur.

AUTHORS:

• Dmitrii V. (Dima) Pasechnik (2012-10): initial implementation

• Dmitrii V. (Dima) Pasechnik (2015, 2021): minor fixes

• Charalampos Kokkalis (2021): Eberlein polynomials, general Q matrix codes

sage.coding.delsarte_bounds.delsarte_bound_Q_matrix(q, d, return_data=False, solver='PPL', isinteger=False)[source]#

Delsarte bound on a code with Q matrix q and lower bound on min. dist. d.

Find the Delsarte bound on a code with Q matrix q and lower bound on minimal distance d.

INPUT:

• q – the Q matrix

• d – the (lower bound on) minimal distance of the code

• return_data – if True, return a triple (W,LP,bound), where W is a weights vector, and LP the Delsarte upper bound LP; both of them are Sage LP data. W need not be a weight distribution of a code.

• solver – the LP/ILP solver to be used. Defaults to PPL. It is arbitrary precision, thus there will be no rounding errors. With other solvers (see MixedIntegerLinearProgram for the list), you are on your own!

• isinteger – if True, uses an integer programming solver (ILP), rather that an LP solver. Can be very slow if set to True.

EXAMPLES:

The bound on dimension of linear $$\GF{2}$$-codes of length 10 and minimal distance 6:

sage: q_matrix = Matrix([[codes.bounds.krawtchouk(10,2,i,j) for i in range(11)]
....:                    for j in range(11)])
sage: codes.bounds.delsarte_bound_Q_matrix(q_matrix, 6)
2

sage: a,p,val = codes.bounds.delsarte_bound_Q_matrix(q_matrix, 6, return_data=True)
sage: [j for i,j in p.get_values(a).items()]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

>>> from sage.all import *
>>> q_matrix = Matrix([[codes.bounds.krawtchouk(Integer(10),Integer(2),i,j) for i in range(Integer(11))]
...                    for j in range(Integer(11))])
>>> codes.bounds.delsarte_bound_Q_matrix(q_matrix, Integer(6))
2

>>> a,p,val = codes.bounds.delsarte_bound_Q_matrix(q_matrix, Integer(6), return_data=True)
>>> [j for i,j in p.get_values(a).items()]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

sage.coding.delsarte_bounds.delsarte_bound_additive_hamming_space(n, d, q, d_star=1, q_base=0, return_data=False, solver='PPL', isinteger=False)[source]#

Find a modified Delsarte bound on additive codes in Hamming space $$H_q^n$$ of minimal distance $$d$$.

Find the Delsarte LP bound on F_{q_base}-dimension of additive codes in Hamming space $$H_q^n$$ of minimal distance d with minimal distance of the dual code at least d_star. If q_base is set to non-zero, then q is a power of q_base, and the code is, formally, linear over F_{q_base}. Otherwise it is assumed that q_base==q.

INPUT:

• n – the code length

• d – the (lower bound on) minimal distance of the code

• q – the size of the alphabet

• d_star – the (lower bound on) minimal distance of the dual code; only makes sense for additive codes.

• q_base – if 0, the code is assumed to be linear. Otherwise, q=q_base^m and the code is linear over F_{q_base}.

• return_data – if True, return a triple (W,LP,bound), where W is a weights vector, and LP the Delsarte bound LP; both of them are Sage LP data. W need not be a weight distribution of a code, or, if isinteger==False, even have integer entries.

• solver – the LP/ILP solver to be used. Defaults to 'PPL'. It is arbitrary precision, thus there will be no rounding errors. With other solvers (see MixedIntegerLinearProgram for the list), you are on your own!

• isinteger – if True, uses an integer programming solver (ILP), rather that an LP solver. Can be very slow if set to True.

EXAMPLES:

The bound on dimension of linear $$\GF{2}$$-codes of length 11 and minimal distance 6:

sage: codes.bounds.delsarte_bound_additive_hamming_space(11, 6, 2)
3
sage: a,p,val = codes.bounds.delsarte_bound_additive_hamming_space(\
11, 6, 2, return_data=True)
sage: [j for i,j in p.get_values(a).items()]
[1, 0, 0, 0, 0, 0, 5, 2, 0, 0, 0, 0]

>>> from sage.all import *
>>> codes.bounds.delsarte_bound_additive_hamming_space(Integer(11), Integer(6), Integer(2))
3
>>> a,p,val = codes.bounds.delsarte_bound_additive_hamming_space(\
11, 6, 2, return_data=True)
>>> [j for i,j in p.get_values(a).items()]
[1, 0, 0, 0, 0, 0, 5, 2, 0, 0, 0, 0]


The bound on the dimension of linear $$\GF{4}$$-codes of length 11 and minimal distance 3:

sage: codes.bounds.delsarte_bound_additive_hamming_space(11,3,4)
8

>>> from sage.all import *
8


The bound on the $$\GF{2}$$-dimension of additive $$\GF{4}$$-codes of length 11 and minimal distance 3:

sage: codes.bounds.delsarte_bound_additive_hamming_space(11,3,4,q_base=2)
16

>>> from sage.all import *
16


Such a d_star is not possible:

sage: codes.bounds.delsarte_bound_additive_hamming_space(11,3,4,d_star=9)
Solver exception: PPL : There is no feasible solution
False

>>> from sage.all import *
Solver exception: PPL : There is no feasible solution
False

sage.coding.delsarte_bounds.delsarte_bound_constant_weight_code(n, d, w, return_data=False, solver='PPL', isinteger=False)[source]#

Find the Delsarte bound on a constant weight code.

Find the Delsarte bound on a constant weight code of weight w, length n, lower bound on minimal distance d.

INPUT:

• n – the code length

• d – the (lower bound on) minimal distance of the code

• w – the weight of the code

• return_data – if True, return a triple (W,LP,bound), where W is a weights vector, and LP the Delsarte upper bound LP; both of them are Sage LP data. W need not be a weight distribution of a code.

• solver – the LP/ILP solver to be used. Defaults to PPL. It is arbitrary precision, thus there will be no rounding errors. With other solvers (see MixedIntegerLinearProgram for the list), you are on your own!

• isinteger – if True, uses an integer programming solver (ILP), rather that an LP solver. Can be very slow if set to True.

EXAMPLES:

The bound on the size of codes of length 17, weight 3, and minimal distance 4:

sage: codes.bounds.delsarte_bound_constant_weight_code(17, 4, 3)
45
sage: a, p, val = codes.bounds.delsarte_bound_constant_weight_code(17, 4, 3, return_data=True)
sage: [j for i,j in p.get_values(a).items()]
[21, 70/3]

>>> from sage.all import *
>>> codes.bounds.delsarte_bound_constant_weight_code(Integer(17), Integer(4), Integer(3))
45
>>> a, p, val = codes.bounds.delsarte_bound_constant_weight_code(Integer(17), Integer(4), Integer(3), return_data=True)
>>> [j for i,j in p.get_values(a).items()]
[21, 70/3]


The stricter bound (using ILP) on codes of length 17, weight 3, and minimal distance 4:

sage: codes.bounds.delsarte_bound_constant_weight_code(17, 4, 3, isinteger=True)
43

>>> from sage.all import *
>>> codes.bounds.delsarte_bound_constant_weight_code(Integer(17), Integer(4), Integer(3), isinteger=True)
43

sage.coding.delsarte_bounds.delsarte_bound_hamming_space(n, d, q, return_data=False, solver='PPL', isinteger=False)[source]#

Find the Delsarte bound on codes in H_q^n of minimal distance d

Find the Delsarte bound [De1973] on the size of codes in the Hamming space H_q^n of minimal distance d.

INPUT:

• n – the code length

• d – the (lower bound on) minimal distance of the code

• q – the size of the alphabet

• return_data – if True, return a triple (W,LP,bound), where W is a weights vector, and LP the Delsarte upper bound LP; both of them are Sage LP data. W need not be a weight distribution of a code.

• solver – the LP/ILP solver to be used. Defaults to PPL. It is arbitrary precision, thus there will be no rounding errors. With other solvers (see MixedIntegerLinearProgram for the list), you are on your own!

• isinteger – if True, uses an integer programming solver (ILP), rather that an LP solver. Can be very slow if set to True.

EXAMPLES:

The bound on the size of the $$\GF{2}$$-codes of length 11 and minimal distance 6:

sage: codes.bounds.delsarte_bound_hamming_space(11, 6, 2)
12
sage: a, p, val = codes.bounds.delsarte_bound_hamming_space(11, 6, 2, return_data=True)
sage: [j for i,j in p.get_values(a).items()]
[1, 0, 0, 0, 0, 0, 11, 0, 0, 0, 0, 0]

>>> from sage.all import *
>>> codes.bounds.delsarte_bound_hamming_space(Integer(11), Integer(6), Integer(2))
12
>>> a, p, val = codes.bounds.delsarte_bound_hamming_space(Integer(11), Integer(6), Integer(2), return_data=True)
>>> [j for i,j in p.get_values(a).items()]
[1, 0, 0, 0, 0, 0, 11, 0, 0, 0, 0, 0]


The bound on the size of the $$\GF{2}$$-codes of length 24 and minimal distance 8, i.e. parameters of the extended binary Golay code:

sage: a,p,x = codes.bounds.delsarte_bound_hamming_space(24,8,2,return_data=True)
sage: x
4096
sage: [j for i,j in p.get_values(a).items()]
[1, 0, 0, 0, 0, 0, 0, 0, 759, 0, 0, 0, 2576, 0, 0, 0, 759, 0, 0, 0, 0, 0, 0, 0, 1]

>>> from sage.all import *
>>> a,p,x = codes.bounds.delsarte_bound_hamming_space(Integer(24),Integer(8),Integer(2),return_data=True)
>>> x
4096
>>> [j for i,j in p.get_values(a).items()]
[1, 0, 0, 0, 0, 0, 0, 0, 759, 0, 0, 0, 2576, 0, 0, 0, 759, 0, 0, 0, 0, 0, 0, 0, 1]


The bound on the size of $$\GF{4}$$-codes of length 11 and minimal distance 3:

sage: codes.bounds.delsarte_bound_hamming_space(11,3,4)
327680/3

>>> from sage.all import *
>>> codes.bounds.delsarte_bound_hamming_space(Integer(11),Integer(3),Integer(4))
327680/3


An improvement of a known upper bound (150) from https://www.win.tue.nl/~aeb/codes/binary-1.html

sage: a,p,x = codes.bounds.delsarte_bound_hamming_space(23,10,2,return_data=True,isinteger=True); x # long time
148
sage: [j for i,j in p.get_values(a).items()]                                      # long time
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 95, 0, 2, 0, 36, 0, 14, 0, 0, 0, 0, 0, 0, 0]

>>> from sage.all import *
>>> a,p,x = codes.bounds.delsarte_bound_hamming_space(Integer(23),Integer(10),Integer(2),return_data=True,isinteger=True); x # long time
148
>>> [j for i,j in p.get_values(a).items()]                                      # long time
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 95, 0, 2, 0, 36, 0, 14, 0, 0, 0, 0, 0, 0, 0]


Note that a usual LP, without integer variables, won’t do the trick

sage: codes.bounds.delsarte_bound_hamming_space(23,10,2).n(20)
151.86

>>> from sage.all import *
>>> codes.bounds.delsarte_bound_hamming_space(Integer(23),Integer(10),Integer(2)).n(Integer(20))
151.86


Such an input is invalid:

sage: codes.bounds.delsarte_bound_hamming_space(11,3,-4)
Solver exception: PPL : There is no feasible solution
False

>>> from sage.all import *
>>> codes.bounds.delsarte_bound_hamming_space(Integer(11),Integer(3),-Integer(4))
Solver exception: PPL : There is no feasible solution
False

sage.coding.delsarte_bounds.eberlein(n, w, k, u, check=True)[source]#

Compute $$E^{w,n}_k(x)$$, the Eberlein polynomial.

It is defined as:

$E^{w,n}_k(u)=\sum_{j=0}^k (-1)^j \binom{u}{j} \binom{w-u}{k-j} \binom{n-w-u}{k-j},$

INPUT:

• w, k, x – arbitrary numbers

• n – a nonnegative integer

• check – check the input for correctness. True by default. Otherwise, pass it as it is. Use check=False at your own risk.

EXAMPLES:

sage: codes.bounds.eberlein(24,10,2,6)
-9

>>> from sage.all import *
>>> codes.bounds.eberlein(Integer(24),Integer(10),Integer(2),Integer(6))
-9

sage.coding.delsarte_bounds.krawtchouk(n, q, l, x, check=True)[source]#

Compute $$K^{n,q}_l(x)$$, the Krawtchouk (a.k.a. Kravchuk) polynomial.

It is defined by the generating function

$(1+(q-1)z)^{n-x}(1-z)^x=\sum_{l} K^{n,q}_l(x)z^l$

and is equal to

$K^{n,q}_l(x)=\sum_{j=0}^l (-1)^j (q-1)^{(l-j)} \binom{x}{j} \binom{n-x}{l-j}.$

INPUT:

• n, q, x – arbitrary numbers

• l – a nonnegative integer

• check – check the input for correctness. True by default. Otherwise, pass it as it is. Use check=False at your own risk.

Symbolic Krawtchouk polynomials $$\tilde{K}_l(x; n, p)$$ which are related by

$(-q)^l K^{n,q^{-1}}_l(x) = \tilde{K}_l(x; n, 1-q).$

EXAMPLES:

sage: codes.bounds.krawtchouk(24,2,5,4)
2224
sage: codes.bounds.krawtchouk(12300,4,5,6)
567785569973042442072

>>> from sage.all import *
>>> codes.bounds.krawtchouk(Integer(24),Integer(2),Integer(5),Integer(4))
2224
>>> codes.bounds.krawtchouk(Integer(12300),Integer(4),Integer(5),Integer(6))
567785569973042442072