2
votes
2answers
195 views

irreducible polynomials on the polynomial sequence

I suspect this problem is very famous and it must be studied very well. But I searched in Google and I did not find good reference. I will appreciate any answer and reference for any contribution ...
3
votes
2answers
314 views

Degrees of factors of polynomial $f(x)=x^q-(ax^2+bx+c)\in \mathbb{F}_q[x]$

I’m facing the problem of factoring polynomials of type $f(x)=x^q-(ax^2+bx+c)\in \mathbb{F}_q[x]$ and the degrees of factors seem to be quite special. For example, according to my experimental results ...
10
votes
5answers
784 views

Is $x^p-x+1$ always irreducible in $F_p[x]$?

It seems that for any prime number $p$ and for any non-zero element $a$ in the finite field $\mathbb F_p$, the polynomial $x^p-x+a$ is irreducible over $\mathbb F_p$. (It is of course obvious that ...
34
votes
2answers
806 views

A curious identity related to finite fields

To three elements $a_1$, $a_2$, $a_3$ in the finite field $\mathbb F_q$ of $q$ elements we associate the number $N(a_1,a_2,a_3)$ of elements $a_0\in \mathbb F_q$ such that the polynomial ...
0
votes
1answer
207 views

Generators of cyclic group of finite fields

Let $F$ be a finite field and $f(x)\in F[X]$ be an irreducible polynomial of degree $n$. Let $\alpha$ be a root of $f(x)$. So $E:=F[\alpha]$ is a finite field of order $|F|^{n}$. We know that ...
10
votes
3answers
627 views

Probability of coprime polynomials

Given positive integer $N$, we choose $m_1, m_2, n_1, n_2$ independently and with equal probabilities from $\{0,1,\ldots,N\}$, and let $f_1 = x^{m_1} + (1+x)^{n_1}$ and $f_2 = x^{m_2} + (1+x)^{n_2}$ ...
1
vote
0answers
133 views

Finite fields: alternating sums of values of polynomials

Notation In what follows let $p$ be a (odd, if needed) prime, $e$ a positive integer, $q = p^e$; $\mathbb{F}_q$ will denote a finite field with $q$ elements whose prime subfield will be denoted as ...
5
votes
1answer
195 views

Polynomiality of functions over residue rings

Suppose $\mathbb{Z}/m \mathbb{Z}$ is a residue ring for some $m \in \mathbb{N}$. If $m=p$ is a prime number then every function $f:\mathbb{Z}/p \mathbb{Z} \rightarrow \mathbb{Z}/p \mathbb{Z}$ is a ...
0
votes
1answer
168 views

Existence of nontrivial roots of a homogeneous polynomial over a finite field in extension fields

Consider a homogeneous polynomial, f, of total degree n in n variables, with coefficients in a prime order finite field, GF(p). Are there any general rules regarding the existence of nontrivial roots ...
0
votes
1answer
93 views

Probability of summing products of irreducible polynomials in a finite field to zero

Let $f(x), g(x), h(x)$ be randomly chosen irreducible polynomials over the finite field $GF(2^n)$. What would the probability be for $\sum_{(i,j,k:i,j,k\in\mathbb{N},i+j+k=C)} f^i(x)g^j(x)h^k(x)=0$, ...
16
votes
4answers
906 views

A mixing property for finite fields of characteristic $2$

In connection with this MO post, here is a question somewhat implicitly contained in a joint paper of S. Kopparty, S. Saraf, M. Sudan, and myself. Let ${\mathbb F}$ be a finite field, and suppose ...
1
vote
1answer
191 views

Given g1(x), g2(x) minimize over p(x) Hamming weight of [p(x)g1; p(x)g2(x) ] ? (Or how to find minimal distance of convolutional code?)

Fix polynoms g1(x), g2(x) over F_2[x]. Question: How to find minimum over polynoms p(x) of the: HammingWeight(p(x) g1(x) ) + HammingWeight(p(x) g2(x) ) ? By HammingWeight of polynom I mean number ...
3
votes
1answer
237 views

Special polynomials over finite fields

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 ...
1
vote
1answer
186 views

How many k-nomials of deg N divisible by X^16+x^12+x^5 +1 ? (Spectrum of CRC-16-CCITT erroc-correcting code ?)

Let us consider polynoms over $F_2$. Consider the linear SUBSPACE of polynoms divisible by $x^{16}+x^{12}+x^5 +1$ and of degree less or equal $N$ (e.g. 40). Question: How many k-nomials belong to ...
5
votes
1answer
358 views

Probability of a set of random vectors over finite field being a spanning set

Suppose I have a set of random vectors $f(a_1, \ldots, a_\ell) := (v_1, \ldots, v_m) \subset F_p^n$, $m \ge n$, given by a matrix valued polynomial function $f$, where the $a_i$'s are independent, ...
11
votes
3answers
2k views

Truncated Exponential Series Modulo $p$: Deeper meaning for a Putnam Question.

Apparently B6 of the Putnam this year asked: Suppose $p$ is an odd prime. Prove that for $n\in \{0,1,2...p-1\}$, at least $\frac{p+1}{2}$ of the numbers $\sum^{p-1}_{k=0} k! n^{k}$ are not ...
0
votes
1answer
189 views

Low degree approximation of the polynomial extension of the logical-or function

Let $x\in\{0,1\}^n$ be a binary vector of dimension $n$, and let $OR(x)$ be the "logical or" function (i.e., returns $1$ if at least one of the coordinates is $1$ and otherwise returns $0$). Consider ...
1
vote
0answers
236 views

Sums of three squares in $GF(q)[t]$

Let $q$ be a power of an odd prime number $p>3,$ say $q=p^r$ with $r \geq 1.$ It is known that every polynomial $M$ in $GF(q)[t]$ is a sum of at most $3$ squares with some conditions on degrees. ...
3
votes
1answer
251 views

A kind of `pell` equation in characteristic $2.$

Given polynomials $a(t),b(t) \in K[t]$ where $K$ is a finite extension of $GF(2)$, with $$ a(t) \neq 0, $$ we consider the equation $$ x^2+axy+by^2=1 $$ with unknowns $x,y$ also polynomials in ...
3
votes
2answers
509 views

Reducible trinomials $x^{odd}+x^2+s(t)$ in characteristic $2$

Let $F$ be a finite field of characteristic $2$. Let $m \geq 2 $ be a positive integer. Seems unknown if the trinomial $$ T(t,x) = x^{2m+1}+x^2+s(t) \in F[t][x] $$ (more explicitly, the ...
1
vote
2answers
521 views

best deterministic complexity for factoring polynomials over finite field

I would like to know currently what's the best deterministic complexity for factoring polynomials over finite field (without the assumption of GRH)? I have searched on google, there are many source, ...
4
votes
1answer
1k views

Irreducibility of some trinomials modulo $p$

Let $n>1$ be an integer. An old result of Selmer, See Theorem 1, page 289 in http://www.mscand.dk/article.php?id=1472, (If the link does not work try googling: ...
1
vote
0answers
179 views

Binary `neighbors` perfect polynomials, instead of `consecutive`

Inspired by Andrei's nice solution of 52609, (namely consecutive perfect polynomials): Denote by $A$ the full ring of polynomials in one variable $t$ over the ...
3
votes
1answer
263 views

Can two Consecutive Polynomials both be perfect ?

Denote by $A$ the full ring of polynomials in one variable $t$ over the finite field with $q$ elements. For any monic polynomial $P \in A$ define $$ \sigma(P) = \sum_{d \mid P, d\, \text{monic}} d. ...
1
vote
0answers
320 views

J. T. B. Beard's algorithm to catch `perfect polynomials`

For any monic polynomial $P$ with coefficients in a finite field of order $q$, we put $$ \sigma(P) = \sum_{d \mid P, d \text{ monic}} d. $$ Observe that $P$ and $\sigma(P)$ have the same degree. ...
9
votes
1answer
817 views

All polynomials over a finite field are sums of $2$ square-free polynomials

I quote Proposition 2.3, page 14 lines -3 and -4 of Michael Rosen's book Number Theory in Function Fields: Let $b_n$ be the number of square-free monics in $A= \mathbb{F}_q[t]$ of degree $n.$ Then ...
3
votes
1answer
798 views

Inverse for a permutation over GF(2)

Given a permutation $f: \{0,1\}^n \rightarrow \{0,1\}^n$ as $n$ polynomials over $GF(2)$ how to get formulas for the inverse permutation $f^{-1}$? I am interested in the answer to the previous ...
1
vote
3answers
3k views

How to factorize X^n - 1 in Z/pZ?

How do I factorize a polynomial $X^n - 1$ over $\mathbb{F}_p$? In particular I need to find factors of the polynomial $X^{3^3 - 1} - 1 = X^{26} - 1$ over $\mathbb{F}_3$.