User zahra - MathOverflow

Special polynomials over finite fields

2012-07-13T13:52:53Z

My field of research is coding theory and I am working on cyclic codes. During my research, I tackled an algebraic problem. After some simple definitions, I asked my question. I will appreciate any helpful answer and comment.

Let ‎$‎‎F_{2^{2m}}‎$ ‎denote ‎the ‎finite ‎field ‎of ‎‎$‎{2^{2m}}‎$‎‏ ‎elements‎, where ‎$‎m‎$‎‏ ‎is a‎ ‎positive ‎integer. ‎Let‎ ‎$‎‎‎‎F_{2^{2m}}[x]‎$ ‎denote ‎the polynomial ring in indeterminate ‎$‎x‎$ ‎with ‎coefficients ‎from‎ ‎$‎‎F_{2^{2m}}‎$.‎ ‎

Suppose that ‎$‎f(x)‎$ ‎‎is a polynomial in $‎‎F_{2^{2m}}[x]‎$ ‎and‎ ‎‎$‎f(x)=f_0+f_1x+‎\cdots‎+f_kx^k‎$. We define the conjugate polynomial of ‎$‎f(x)‎$ ‎over‎ ‎$‎‎‎‎F_{2^{2m}}‎$ as follows:‎

‎$‎‎\overline{f(x)}‎={f_0}^{2^m}+f_1^{2^m}x+‎\cdots ‎+f_k^{2^m}x^k.$‎

In particular, if a polynomial is equal to its conjugate polynomial ‎over‎ ‎$‎‎F_{2^{2m}}‎$, then it is called self-conjugate polynomial.‎ ‎

Let ‎$‎n‎$ ‎be ‎an ‎odd ‎positive ‎integer. Since ‎‎$‎gcd(n,‎2^{2m})=1‎$‎, the polynomial ‏‎$‎‎‎x^n+1‎$ ‎can ‎be ‎factorized ‎into ‎distinct ‎irre‎ducible polynomials over ‎$‎‎F_{2^{2m}}‎$.‎ ‎‎

It ‎is ‎obvious ‎that ‎for ‎any ‎monic ‎irreducible ‎polynomial ‎dividing ‎‎$‎x^n+1‎$ ‎over‎‎ ‎$‎‎‎‎F_{2^{2m}}‎$, its conjugate polynomial ‎is ‎also a ‎monic ‎irreducible ‎polynomial ‎dividing ‎‎$‎x^n+1‎$ ‎over‎‎ ‎$‎‎‎‎F_{2^{2m}}‎$. ‎‎ ‎

For ‎example, let ‎‎$‎‎\omega‎‎$ be a‎ ‎primitive ‎element ‎of‎ $‎‎F_4‎$‎. ‎‎‎‎‎The factorization of ‎$‎‎x^5+1$ over $‎‎F_4‎$ is ‎

‎$‎‎x^5+1=(x+1)(x^2+‎\omega ‎x+1)(x^2+‎\omega‎^2x+1)‎‎$‎‎‎‎‎‎

It ‎is ‎obvious ‎that ‎$‎x+1‎$‎‏ ‎is a‎ ‎‎self-conjugate polynomial ‎and ‎‎$x^2+‎\omega ‎x+1‎$ ‎is ‎the‎ conjugate polynomial of ‎$x^2+‎\omega‎^2x+1‎$ ‎over $‎‎‎‎F_4‎$‎‎.‎ ‎‎

For another ‎example, let $‎‎\omega‎‎$ be a‎ ‎primitive ‎element ‎of‎ $‎‎F_{16}‎$‎. ‎The factorization of ‎$‎‎x^{11}+1$ over $‎‎‎‎F_{16}‎‎$ is‎

‎$‎‎x^{11}+1=(x+1)(x^5+‎\omega^5 ‎x^4+x^3+x^2+‎\omega‎^{10}x+1)(x^5+‎\omega^{10} ‎x^4+x^3+x^2+‎\omega‎^{5}x+1)‎‎$

It ‎is ‎obvious ‎that ‎$‎x+1‎$, ‎‎$x^5+‎\omega^5 ‎x^4+x^3+x^2+‎\omega‎^{10}x+1‎$ and ‎$x^5+‎\omega^{10} ‎x^4+x^3+x^2+‎\omega‎^{5}x+1‎$‎ ‎are‎ ‎‎self-conjugate polynomials over $‎‎‎‎F_{16}‎‎$.‎

Because of my researches I think that if $‎f(x)‎$ ‎‎is a self-conjugate monic ‎irreducible ‎polynomial ‎dividing ‎‎$‎x^n+1‎$ ‎over‎‎ ‎$‎‎F_{2^{2m}}‎‎$, then the degree of $‎f(x)‎$ is odd, ‎but I ‎‎could ‎not ‎prove ‎it.‎‎‎ ‎

Is this conjecture true in general? If the answer is no, please give me an example?

Answer by Zahra for For two graphs, $H$ and $G$ let $\bar{H}$ and $\bar{G}$ be their respective compliments. Then if $H$ is a subgraph of $G$, then $\bar{H}$ is a subgraph of $\bar{G}$.

2012-04-20T13:01:58Z

This statement is not true. For example, let $G=K_4$ and $H=C_4$, where $G$ and $H$ are complete graph and cycle graph with four vertices, respectively. It is easy to check that, $H$ is a subgraph of $G$, but $\overline{H}$ is not a subgraph of $\overline{G}$.

It is interesting that, you think about this question:

When this statement is true?

Answer by Zahra for how to proof "every loopless graph G has a bipartite subgraph with at least e(G)/2 edges"?

2012-03-06T11:41:13Z

We start with any partition of $V(G)$ into two sets $X$ and $Y$. Using the edges having one endpoint in each set yields a bipartite subgraph $H$ with partitions $X$ and $Y$.

If $H$ has at least $\frac{e(G)}{2}$ edges, the proof is complete.

If for each vertex $x$ of $H$, $d_H(x) \geq \frac{d_G(x)}{2}$, then by applying degree-sum formula we have $e(H) \geq \frac{e(G)}{2}$ and the proof is complete.

Suppose that there is a vertex in one partition of $H$, say $\nu \in X$, that $d_H(\nu)< \frac{d_G(\nu)}{2}$. We move $\nu$ from $X$ to $Y$. So, now $d_H(\nu) \geq \frac{d_G(\nu)}{2}$.

We repeat this algorithm until for each vertex $x$ of $H$, $d_H(x) \geq \frac{d_G(x)}{2}$. It is clear that this algorithm must terminate. Now by by applying degree-sum formula we have $e(H) \geq \frac{e(G)}{2}$ and the proof is complete.

This Idea of proof is well-known and its name is switching method.

request sources about self-dual cyclic codes

2012-01-24T17:12:35Z

X. Kai and S. Zhu in the paper "On cyclic self-dual codes", AAECC, vol. 19, pp. 509-525, 2008, at page 510 in line 6 said that, It is well Known that there are no cyclic self-dual codes over $F_q$ when $q$ is odd.

I know that W. Cary Huffman and V. Pless in the book "Fundamentals of error correcting codes" proved that there are no self-dual cyclic codes of length $n$ over $F_q$ when $gcd(n,q)=1$.

Also Y. Jia, S. Ling and C. Xing in the paper with name "On self-dual cyclic codes over finite fields" at 2011 proved that there exist at least one self-dual cyclic code of length $n$ over $F_q$ if and only if $q$ is a power of $2$ and $n$ is even.

My questions are:

1) Where can I find the proof of the claim that introduced in my first paragraph?

2) Generally, how can I find some good sources about self-dual (self-orthogonal) cyclic codes, precisely about the existence of these codes over finite fields?

The generator polynomial of cyclic code

2011-12-16T17:44:08Z

Let $q$ be a power of prime number $p$ and let $F_{q^2}$ be a finite field of order $q^2$. Suppose that "-" be a conjugation operation that is defined as follow:

$-:F_{q^2} ‎\longrightarrow‎ ‎F_{q^2}$

$x ‎\longmapsto‎ x^q$

Let $C$ be a cyclic code of length n over $F_{q^2}$ with the generator polynomial $g(x)$ and let $\bar{C}=\lbrace \bar{c} : c \in C \rbrace$ be the conjugate code of $C$.

It is obvious that $\bar{C}$ is also a cyclic code.

Is it possible to determine the generator polynomial of $\bar{C}$ from $g(x)$?

Covering radius of LDPC codes

2011-12-13T18:04:30Z

Does the performance of LDPC code $C$ depends on the covering radius, $Cr(C)$?

Comment by Zahra

2013-01-20T07:57:04Z

Where $n=l^{s-r}(l+1)^r$ and $s>r\geq 0$, the minimum sum is $sl+r$.

Comment by Zahra

2012-07-14T07:48:54Z

Thanks for your helpful answer.

Comment by Zahra

2012-07-07T12:28:36Z

By your definition, I think you mean this notation: $\overline{H_{n}^{k}}$. Is it true?

Comment by Zahra

2012-01-27T13:37:25Z

@Mark: I agree with your last comment and because of your proof, I know that $m=2r$. You said in your proof that: " and again this is impossible when $q$ is odd". Would you please explain the reason of this claim?

Comment by Zahra

2012-01-27T10:59:20Z

Dear Mark, thanks for your new proof. I understand from your proof that for a self-dual cyclic code $C$ with the generator polynomial $f(x)$, always we have $(x-1)|f(x)$, because $m \neq 0$ and $m=2r$. Is this true in general for self-dual cyclic codes over $F_q$?

Comment by Zahra

2012-01-26T23:25:39Z

Dear Mark, thanks for your contribution. But, if $C$ be a cyclic code of length $n$ with generator polynomial $f(x)$ and $g(x)=(x^n-1)/f(x)$, then the generator polynomial of its dual is $f^{\perp}(x)={g_0}^{-1}x^{deg(g(x))}g(x^{-1})$, where $g_0$ is the constant term of $g(x)$. Therefor, I think your proof can't be true.

Comment by Zahra

2011-12-17T19:20:02Z

Thank you for your helpful answer.