3
$\begingroup$

Is it true that for any sufficiently large prime $p$, there exists a prime $q\ne p$ and a cyclic code of length $p$ over $\mathbb{F}_q$ that contains a codeword of Hamming weight at most ord$_p(q)$ and which is not orthogonal to the all-ones vector?

Viewed as an element of $\mathbb{F}_q[x]/(x^p-1)$, the second condition asks that the codeword is not a multiple of $(x-1)$. Here ord$_p(q)$ is the multiplicative order of $q$ modulo $p$.

Numerical experiments give the impression that the above is true for a codeword corresponding to an irreducible factor of $(x^p - 1)/(x-1) \in \mathbb{F}_q[x]$ (for some prime $q$).

Improve this question
$\endgroup$
14
  • 2
    $\begingroup$ As motivation for the condition on $\mathrm{ord}_p(q)$, observe that if $q$ has order $s$ mod $p$ so $p$ divides $q^s-1$ then $x^p-1$ has a factor, say $g(x)$, of degree $s$ in $\mathbb{F}_q[x]$. Now if the Hamming weight of $g(x)$ is $s$ or less, we're done. But in the worst case $g(x)$ has Hamming weight $s+1$, so this method fails. So it seems to me the real question is: when is there a prime $q$ such that one of the $(p-1)/\mathrm{ord}_p(q)$ irreducible factors of $1+x+\cdots+x^{p-1} = (x^p-1)/(x-1)$ in $\mathbb{F}_q$ has Hamming weight at most its degree, i.e. at most $\mathrm{ord}_p(q)$? $\endgroup$
    – Mark Wildon
    Commented Jul 2, 2020 at 17:10
  • $\begingroup$ Thanks for the quick answer! I agree with the observation. The numerics seem to suggest that your reformulation has a positive answer. But the type of codeword I’m after is allowed to be a multiple of an irreducible factor (provided 1 is not a root). That might make the problem easier. $\endgroup$
    – Jop
    Commented Jul 2, 2020 at 17:51
  • $\begingroup$ Instead of positive answer I meant to say that the answer might be “when p is big enough”. $\endgroup$
    – Jop
    Commented Jul 2, 2020 at 18:00
  • 2
    $\begingroup$ One way this could work: choose $q$ so that $p$ divides $q^2+q+1$ but not $q-1$. Then $(x^p-1)/(x-1)$ splits into cubic factors in $\mathbb{F}_q$. Each factor splits as $(x-\zeta)(x-\zeta^q)(x-\zeta^{q^2})$ in a cubic extension field $\mathbb{F}_q(\zeta)$, so has norm $(-1)^3 \zeta^{1+q+q^2}$; since $p$ divides $1+q+q^2$ this is $-1$, and the cubic factor in $\mathbb{F}_q[x]$ is $x^3 + ax^2 + bx - 1$. Now if we could choose the cubic factor to have $0$ trace, we'd get a generating polynomial of Hamming weight $\le 3$, as required. $\endgroup$
    – Mark Wildon
    Commented Jul 2, 2020 at 20:21
  • 1
    $\begingroup$ I am not completely sure if I understand what you mean by that the cubic factor has zero trace. This sounds a bit related to showing that if p does not divide $t = $ord$_p(q)$, then the trace Tr$_{\mathbb{F}_{q^t}/\mathbb{F}_q}$ has a primitive $p$'th root of unity as a root. If there is a $q$ for which this is true, then that would work since the trace has "Hamming weight" $t$ and is not zero mod $p$ at 1. Is this indeed related to what you suggest? $\endgroup$
    – Jop
    Commented Jul 3, 2020 at 10:41

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .