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

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]

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

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]

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

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

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

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

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]

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

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

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]

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]

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

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]

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

Such an input is invalid:

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

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

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

See Wikipedia article Eberlein_polynomials.

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

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

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

See Wikipedia article Kravchuk_polynomials.

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.