Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2204.06090 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908468752941056 |
|---|---|
| author | Li, Rupert |
| author_facet | Li, Rupert |
| contents | The Delsarte linear program is used to bound the size of codes given their block length $n$ and minimal distance $d$ by taking a linear relaxation from codes to quasicodes. We study for which values of $(n,d)$ this linear program has a unique optimum: while we show that it does not always have a unique optimum, we prove that it does if $d>n/2$ or if $d \leq 2$. Introducing the Krawtchouk decomposition of a quasicode, we prove there exist optima to the $(n,2e)$ and $(n-1,2e-1)$ linear programs that have essentially identical Krawtchouk decompositions, revealing a parity phenomenon among the Delsarte linear programs. We generalize the notion of extending and puncturing codes to quasicodes, from which we see that this parity relationship is given by extending/puncturing. We further characterize these pairs of optima, in particular demonstrating that they exhibit a symmetry property, effectively halving the number of decision variables. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2204_06090 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Unique Optima of the Delsarte Linear Program Li, Rupert Combinatorics Information Theory 94B65 The Delsarte linear program is used to bound the size of codes given their block length $n$ and minimal distance $d$ by taking a linear relaxation from codes to quasicodes. We study for which values of $(n,d)$ this linear program has a unique optimum: while we show that it does not always have a unique optimum, we prove that it does if $d>n/2$ or if $d \leq 2$. Introducing the Krawtchouk decomposition of a quasicode, we prove there exist optima to the $(n,2e)$ and $(n-1,2e-1)$ linear programs that have essentially identical Krawtchouk decompositions, revealing a parity phenomenon among the Delsarte linear programs. We generalize the notion of extending and puncturing codes to quasicodes, from which we see that this parity relationship is given by extending/puncturing. We further characterize these pairs of optima, in particular demonstrating that they exhibit a symmetry property, effectively halving the number of decision variables. |
| title | Unique Optima of the Delsarte Linear Program |
| topic | Combinatorics Information Theory 94B65 |
| url | https://arxiv.org/abs/2204.06090 |