3
$\begingroup$

Are there $[n,k]_q$ constant rate $\frac kn$ and constant alphabet linear code families with automorphism group of size $\Omega((n-n^\beta)!)$ that have minimum distance $d=O(n^\alpha)$ and number of minimum weight code words $A_d=O(2^{n^\beta})$ for any two given $\alpha,\beta\in(0,1)$ with $\beta<\alpha$ (ideally I want $\alpha\rightarrow1^-$ and $\beta\rightarrow0^+$)?

My guess is $q>n/d$ should provide interesting extreme examples of such families of codes while $q<n/d$ is impossible to achieve.

Improve this question
$\endgroup$
4
  • $\begingroup$ I assume the alphabet is fixed. Are you interested in binary codes, or in codes over arbitrary fields? Could you give a bit more motivation for this problem? In particular, do such codes exist if the condition on the automorphism group is weakened? $\endgroup$
    – Mark Wildon
    Jul 19, 2016 at 11:46
  • $\begingroup$ @MarkWildon I think $q<n/d$ would be impossible to achieve. I do not think even with $q>n/d$ there is any real hope but possible. I was playing with automorphism groups and weight enumerators. Such code families would form an interesting extreme example. $\endgroup$
    – Turbo
    Jul 19, 2016 at 12:27
  • $\begingroup$ @MarkWildon Actually the problem came from something else in complexity theory. If such codes exist something important will happen in complexity theory however I think for every fixed $q>n/d$ we can have infinite families of such codes or even slightly better $\endgroup$
    – Turbo
    Jul 20, 2016 at 1:38
  • 1
    $\begingroup$ Up to version 14 now. $\endgroup$
    – Gerry Myerson
    Jul 20, 2016 at 2:35

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.