User zahra - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T08:52:49Z http://mathoverflow.net/feeds/user/19929 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/102143/special-polynomials-over-finite-fields Special polynomials over finite fields Zahra 2012-07-13T13:52:53Z 2012-07-13T14:32:58Z <p>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.</p> <p>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}}‎$.‎ ‎</p> <p>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:‎</p> <p>‎$‎‎\overline{f(x)}‎={f_0}^{2^m}+f_1^{2^m}x+‎\cdots ‎+f_k^{2^m}x^k.$‎</p> <p>In particular, if a polynomial is equal to its conjugate polynomial ‎over‎ ‎$‎‎F_{2^{2m}}‎$, then it is called self-conjugate polynomial.‎ ‎</p> <p>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}}‎$.‎ ‎‎</p> <p>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}}‎$. ‎‎ ‎</p> <p>For ‎example, let ‎‎$‎‎\omega‎‎$ be a‎ ‎primitive ‎element ‎of‎ $‎‎F_4‎$‎. ‎‎‎‎‎The factorization of ‎$‎‎x^5+1$ over $‎‎F_4‎$ is ‎</p> <p>‎$‎‎x^5+1=(x+1)(x^2+‎\omega ‎x+1)(x^2+‎\omega‎^2x+1)‎‎$‎‎‎‎‎‎</p> <p>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‎$‎‎.‎ ‎‎</p> <p>For another ‎example, let $‎‎\omega‎‎$ be a‎ ‎primitive ‎element ‎of‎ $‎‎F_{16}‎$‎. ‎The factorization of ‎$‎‎x^{11}+1$ over $‎‎‎‎F_{16}‎‎$ is‎</p> <p>‎$‎‎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)‎‎$</p> <p>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}‎‎$.‎</p> <p>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.‎‎‎ ‎</p> <p>Is this conjecture true in general? If the answer is no, please give me an example?</p> http://mathoverflow.net/questions/94635/for-two-graphs-h-and-g-let-barh-and-barg-be-their-respective-compl/94636#94636 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}$. Zahra 2012-04-20T13:01:58Z 2012-04-20T13:01:58Z <p>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}$.</p> <p>It is interesting that, you think about this question:</p> <p>When this statement is true? </p> http://mathoverflow.net/questions/90343/how-to-proof-every-loopless-graph-g-has-a-bipartite-subgraph-with-at-least-eg/90355#90355 Answer by Zahra for how to proof "every loopless graph G has a bipartite subgraph with at least e(G)/2 edges"? Zahra 2012-03-06T11:41:13Z 2012-03-06T11:41:13Z <p>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$.</p> <p>If $H$ has at least $\frac{e(G)}{2}$ edges, the proof is complete.</p> <p>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.</p> <p>Suppose that there is a vertex in one partition of $H$, say $\nu \in X$, that $d_H(\nu)&lt; \frac{d_G(\nu)}{2}$. We move $\nu$ from $X$ to $Y$. So, now $d_H(\nu) \geq \frac{d_G(\nu)}{2}$.</p> <p>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.</p> <p>This Idea of proof is well-known and its name is switching method.</p> http://mathoverflow.net/questions/86548/request-sources-about-self-dual-cyclic-codes request sources about self-dual cyclic codes Zahra 2012-01-24T17:12:35Z 2012-01-28T11:17:27Z <p>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.</p> <p>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$.</p> <p>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.</p> <p>My questions are:</p> <p>1) Where can I find the proof of the claim that introduced in my first paragraph?</p> <p>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?</p> http://mathoverflow.net/questions/83644/the-generator-polynomial-of-cyclic-code The generator polynomial of cyclic code Zahra 2011-12-16T17:44:08Z 2011-12-16T23:25:55Z <p>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:</p> <p>$-:F_{q^2} ‎\longrightarrow‎ ‎F_{q^2}$</p> <p>$x ‎\longmapsto‎ x^q$</p> <p>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$.</p> <p>It is obvious that $\bar{C}$ is also a cyclic code. </p> <p>Is it possible to determine the generator polynomial of $\bar{C}$ from $g(x)$?</p> http://mathoverflow.net/questions/83359/covering-radius-of-ldpc-codes Covering radius of LDPC codes Zahra 2011-12-13T18:04:30Z 2011-12-13T18:48:29Z <p>Does the performance of LDPC code $C$ depends on the covering radius, $Cr(C)$?</p> http://mathoverflow.net/questions/119364/minimum-sum-among-fixed-length-factors-of-a-number Comment by Zahra Zahra 2013-01-20T07:57:04Z 2013-01-20T07:57:04Z Where $n=l^{s-r}(l+1)^r$ and $s&gt;r\geq 0$, the minimum sum is $sl+r$. http://mathoverflow.net/questions/102143/special-polynomials-over-finite-fields/102148#102148 Comment by Zahra Zahra 2012-07-14T07:48:54Z 2012-07-14T07:48:54Z Thanks for your helpful answer. http://mathoverflow.net/questions/101567/the-chromatic-number-of-a-hamming-related-graph Comment by Zahra Zahra 2012-07-07T12:28:36Z 2012-07-07T12:28:36Z By your definition, I think you mean this notation: $\overline{H_{n}^{k}}$. Is it true? http://mathoverflow.net/questions/86548/request-sources-about-self-dual-cyclic-codes/86753#86753 Comment by Zahra Zahra 2012-01-27T13:37:25Z 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: &quot; and again this is impossible when $q$ is odd&quot;. Would you please explain the reason of this claim? http://mathoverflow.net/questions/86548/request-sources-about-self-dual-cyclic-codes/86753#86753 Comment by Zahra Zahra 2012-01-27T10:59:20Z 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$? http://mathoverflow.net/questions/86548/request-sources-about-self-dual-cyclic-codes/86753#86753 Comment by Zahra Zahra 2012-01-26T23:25:39Z 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. http://mathoverflow.net/questions/83644/the-generator-polynomial-of-cyclic-code Comment by Zahra Zahra 2011-12-17T19:20:02Z 2011-12-17T19:20:02Z Thank you for your helpful answer.