Delsarte, a.k.a. Linear Programming (LP), upper bounds¶
This module provides LP upper bounds for the parameters of codes, introduced in [De73].
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)} \binom{x}{j} \binom{n-x}{l-j},\]INPUT:
n, q, x
– arbitrary numbersl
– a nonnegative integercheck
– check the input for correctness.True
by default. Otherwise, pass it as it is. Usecheck=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) -1.0 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)} \binom{x}{j} \binom{n-x}{l-j},\]INPUT:
n, q, x
– arbitrary numbersl
– a nonnegative integercheck
– check the input for correctness.True
by default. Otherwise, pass it as it is. Usecheck=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) -1.0 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 distanced
Find the Delsarte LP bound on
F_{q_base}
-dimension of additive codes in Hamming spaceH_q^n
of minimal distanced
with minimal distance of the dual code at leastd_star
. Ifq_base
is set to non-zero, thenq
is a power ofq_base
, and the code is, formally, linear overF_{q_base}
. Otherwise it is assumed thatq_base==q
.INPUT:
n
– the code lengthd
– the (lower bound on) minimal distance of the codeq
– the size of the alphabetd_star
– the (lower bound on) minimal distance of the dual code; only makes sense for additive codes.q_base
– if0
, the code is assumed to be linear. Otherwise,q=q_base^m
and the code is linear overF_{q_base}
.return_data
– ifTrue
, return a triple(W,LP,bound)
, whereW
is a weights vector, andLP
the Delsarte bound LP; both of them are Sage LP data.W
need not be a weight distribution of a code, or, ifisinteger==False
, even have integer entries.solver
– the LP/ILP solver to be used. Defaults toPPL
. It is arbitrary precision, thus there will be no rounding errors. With other solvers (seeMixedIntegerLinearProgram
for the list), you are on your own!isinteger
– ifTrue
, uses an integer programming solver (ILP), rather that an LP solver. Can be very slow if set toTrue
.
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 [De73] on codes in Hamming space
H_q^n
of minimal distanced
INPUT:
n
– the code lengthd
– the (lower bound on) minimal distance of the codeq
– the size of the alphabetreturn_data
– ifTrue
, return a triple(W,LP,bound)
, whereW
is a weights vector, andLP
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 toPPL
. It is arbitrary precision, thus there will be no rounding errors. With other solvers (seeMixedIntegerLinearProgram
for the list), you are on your own!isinteger
– ifTrue
, uses an integer programming solver (ILP), rather that an LP solver. Can be very slow if set toTrue
.
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:
[De73] (1, 2) P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Rep., Suppl., vol. 10, 1973.