Delsarte, a.k.a. Linear Programming (LP), upper bounds¶

This module provides LP upper bounds for the parameters of codes. 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. Minor fixes (2015)

sage.coding.delsarte_bounds.Kravchuk(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)}{x \choose j}{n-x \choose 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.

EXAMPLES:

sage: Krawtchouk(24,2,5,4)
2224
sage: Krawtchouk(12300,4,5,6)
567785569973042442072

TESTS:

check that the bug reported on trac ticket #19561 is fixed:

sage: Krawtchouk(3,2,3,3)
-1
sage: Krawtchouk(int(3),int(2),int(3),int(3))
-1
sage: Krawtchouk(int(3),int(2),int(3),int(3),check=False)
-5
sage: Kravchuk(24,2,5,4)
2224

other unusual inputs

sage: Krawtchouk(sqrt(5),1-I*sqrt(3),3,55.3).n()
211295.892797... + 1186.42763...*I
sage: Krawtchouk(-5/2,7*I,3,-1/10)
480053/250*I - 357231/400
sage: Krawtchouk(1,1,-1,1)
Traceback (most recent call last):
...
ValueError: l must be a nonnegative integer
sage: Krawtchouk(1,1,3/2,1)
Traceback (most recent call last):
...
TypeError: no conversion of this rational to integer

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)}{x \choose j}{n-x \choose 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.

EXAMPLES:

sage: Krawtchouk(24,2,5,4)
2224
sage: Krawtchouk(12300,4,5,6)
567785569973042442072

TESTS:

check that the bug reported on trac ticket #19561 is fixed:

sage: Krawtchouk(3,2,3,3)
-1
sage: Krawtchouk(int(3),int(2),int(3),int(3))
-1
sage: Krawtchouk(int(3),int(2),int(3),int(3),check=False)
-5
sage: Kravchuk(24,2,5,4)
2224

other unusual inputs

sage: Krawtchouk(sqrt(5),1-I*sqrt(3),3,55.3).n()
211295.892797... + 1186.42763...*I
sage: Krawtchouk(-5/2,7*I,3,-1/10)
480053/250*I - 357231/400
sage: Krawtchouk(1,1,-1,1)
Traceback (most recent call last):
...
ValueError: l must be a nonnegative integer
sage: Krawtchouk(1,1,3/2,1)
Traceback (most recent call last):
...
TypeError: no conversion of this rational to integer

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 $F_2$ -codes of length 11 and minimal distance 6:

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

The bound on the dimension of linear $F_4$ -codes of length 11 and minimal distance 3:

sage: delsarte_bound_additive_hamming_space(11,3,4)
8

The bound on the $F_2$ -dimension of additive $F_4$ -codes of length 11 and minimal distance 3:

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

Such a d_star is not possible:

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

TESTS:

sage: a,p,x=delsarte_bound_additive_hamming_space(19,15,7,return_data=True,isinteger=True)
sage: [j for i,j in p.get_values(a).iteritems()]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 307, 0, 0, 1, 34]
sage: delsarte_bound_additive_hamming_space(19,15,7,solver='glpk')
3
sage: delsarte_bound_additive_hamming_space(19,15,7,isinteger=True,solver='glpk')
3

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

Find the Delsarte bound [1] on codes in 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 $F_2$ -codes of length 11 and minimal distance 6:

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

The bound on the size of the $F_2$ -codes of length 24 and minimal distance 8, i.e. parameters of the extened binary Golay code:

sage: a,p,x=delsarte_bound_hamming_space(24,8,2,return_data=True)
sage: x
4096
sage: [j for i,j in p.get_values(a).iteritems()]
[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 $F_4$ -codes of length 11 and minimal distance 3:

sage: delsarte_bound_hamming_space(11,3,4)
327680/3

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

sage: a,p,x= 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).iteritems()]                                      # 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: delsarte_bound_hamming_space(23,10,2).n(20)
151.86

Such an input is invalid:

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

REFERENCES:

[1]	P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Rep., Suppl., vol. 10, 1973.

Delsarte, a.k.a. Linear Programming (LP), upper bounds¶

Previous topic

Next topic

This Page