Opened 11 years ago

# adding Delsarte bound for codes — at Version 9

Reported by: Owned by: Dima Pasechnik David Joyner major sage-5.12 coding theory John Pang, Keshav Kini, David Joyner, Nathann Cohen, Punarbasu Purkayastha, Risan N/A

Delsarte bound for codes, aka Linear Programming bound, is easy to implement in Sage. Here is a quick and dirty code that does it; so the problem would be to integrate this properly.

```def Kra(n,q,l,i): # K^{n,q}_l(i), i.e Krawtchouk polynomial
return sum([((-1)**j)*((q-1)**(l-j))*binomial(i,j)*binomial(n-i,l-j)
for j in range(l+1)])

def roundres(x): # this is a quick and unsafe way to round the result...
import math
tol = 0.0001
if math.ceil(x)-x < tol:
return int(math.ceil(x))
if x-math.floor(x) < tol:
return int(math.floor(x))
return x

# @cached_function
def delsarte_bound(n, q, d, d_star=1, q_base=0, return_log=True,\
isinteger=False, return_data=False):
p = MixedIntegerLinearProgram(maximization=True)
A = p.new_variable(integer=isinteger) # A>=0 is assumed
p.set_objective(sum([A[r] for r in range(n+1)]))
for i in range(1,d):
for j in range(1,n+1):
rhs = sum([Kra(n,q,j,r)*A[r] for r in range(n+1)])
if j >= d_star:
else: # rhs is proportional to j-th weight of the dual code
try:
bd=p.solve()
except sage.numerical.mip.MIPSolverException, exc:
print "Solver exception: ", exc, exc.args
if return_data:
return A,p,False
return False
if q_base > 0: # rounding the bound down to the nearest power of q_base,
# for q=q_base^m
#      if len(qb) == 1:
#         base = qb.expand()
#         bd = base^int(log(bd, base=base))
if return_log:
#            bd = int(log(roundres(bd), base=q_base)) # unsafe:
# loss of precision
bd = roundres(log(bd, base=q_base))
else:
#            bd = q_base^int(log(roundres(bd), base=q_base))
bd = q_base^roundres(log(bd, base=q_base))
if return_data:
return A,p,bd
return bd
```

d_star is the minimal distance of the dual code (if it exists at all) If q_base is 0, just compute the upper bound. If q_base is >0, it is assumed to be a prime power, and the code assumed to be additive over this field (i.e. the dual code exists,and its weight enumerator is obtained by applying `MacWilliams transform` --- the matrix A of the LP times the weight enumerator of our code), then the output is the corr. dimension, i.e. `floor(log(bound, q_base))`.

One obstacle for this to work well in big dimensions is a lack of arbitrary precision LP solver backend available in Sage. This is (almost - i.e. the corresponding ticket is still not 100% ready, as reviewers think) taken care of by #12533, which should be made a dependence for this ticket.

### comment:1 Changed 11 years ago by Dima Pasechnik

Last edited 10 years ago by Dima Pasechnik (previous) (diff)

### comment:4 Changed 11 years ago by Dima Pasechnik

Cc: Nathann Cohen added modified (diff)

### comment:5 Changed 11 years ago by Nathann Cohen

(GLPK can solve non-integer rational LP. It is not exposed, but may not be too hard either)

### comment:6 Changed 11 years ago by Dima Pasechnik

The function named `delsarte_bound` should be renamed to something like `delsarte_bound_hamming_space`. This is so that in future other functions like `delsarte_bound_johnson_space`, `delsarte_bound_permutation_space`, etc can be added easily, without having inconsistencies in naming.