Timeline for Cyclic codes: sparse codewords not orthogonal to the all-ones vector
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 21, 2020 at 7:13 | comment | added | Jop | This doesn't sound like what I'm after. I am not sure what minimal and universal cyclic codes are to be honest. Is my question perhaps ill stated? I do want the codeword (polynomial) to have a $p$th root of unity as a root. | |
| Jul 23, 2020 at 10:14 | comment | added | Jyrki Lahtonen | Are only interested in the minimal cyclic codes? For if we can use large cyclic codes the question becomes trivial by the cheating example of the universal code. That is cyclic and contains the word $x$ of Hamming weight one :-) | |
| Jul 4, 2020 at 12:50 | comment | added | Jop | Incidentally I just found a paper of Cohen (sciencedirect.com/science/article/pii/0012365X90902154) on primitive elements with arbitrary trace. (There are a number of later works showing more general results.) I wonder if this can be adapted to elements of order $p$. | |
| Jul 4, 2020 at 12:43 | comment | added | Jop | Yes you’re completely right, sorry. I should have said that the coefficient of $x^{t-1}$ is the trace of $\alpha$. | |
| Jul 4, 2020 at 12:27 | comment | added | Mark Wildon | I think you are mistaken, or I am misunderstanding. For a small example, take $p=7$ and $q=2$, so $\mathrm{ord}_7(2) = 3$ and $x^7-1 = (x+1)(x^3+x+1)(x^3+x^2+1)$. Each cubic factor has as its roots $\zeta$, $\zeta^2$, $\zeta^4$ for some primitive $7$th root of unity (since $p$ is prime, any $p$th root of unity except $1$ is primitive). Moreover both factors are primitive in the sense their roots generate the extension field $\mathbb{F}_{2^3}$. But $x^3+x^2+1$ has a non-zero coefficient of $x^{3-1}$. | |
| Jul 4, 2020 at 11:05 | comment | added | Jop | @MarkWildon: I agree that that would work. I guess more generally you maybe meant the trace of a primitive $p$'th root of unity $\alpha$? If ord$_p(q) = t$, then if I'm not mistaken, the coefficient of $x^{t-1}$ in the minimal polynomial of $\alpha$ will be zero, and so this minimal polynomial will work. | |
| Jul 4, 2020 at 10:24 | comment | added | Jop | The examples I've seen all have $q<p$. But I don't know if $p>q$ is impossible. | |
| Jul 3, 2020 at 22:43 | comment | added | kodlu | Stupid question is $q<p,$ or $p>q,$ or either is possible? | |
| Jul 3, 2020 at 11:30 | comment | added | Mark Wildon | I think I used 'trace' in a rather confusing way. All I meant was that if we could pick a cubic factor with $a=0$, then that would work. | |
| Jul 3, 2020 at 10:41 | comment | added | Jop | 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? | |
| Jul 2, 2020 at 20:21 | comment | added | Mark Wildon | 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. | |
| Jul 2, 2020 at 18:00 | comment | added | Jop | Instead of positive answer I meant to say that the answer might be “when p is big enough”. | |
| Jul 2, 2020 at 17:51 | comment | added | Jop | 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. | |
| Jul 2, 2020 at 17:10 | comment | added | Mark Wildon | 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)$? | |
| Jul 2, 2020 at 13:47 | history | asked | Jop | CC BY-SA 4.0 |