Delsarte (or linear programming) bounds

This module provides LP upper bounds for the parameters of codes, introduced 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): minor fixes

REFERENCES:

[De73]P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Rep., Suppl., vol. 10, 1973.
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: 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 \(F_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 \(F_2\)-dimension of additive \(F_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_hamming_space(n, d, q, return_data=False, solver='PPL', isinteger=False)

Find the Delsarte bound [De1973] 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: 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 \(F_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 \(F_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.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.

EXAMPLES:

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