# Tagged Questions

**2**

votes

**2**answers

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

**2**answers

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

**5**answers

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

**2**answers

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

**1**answer

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

**3**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**4**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**3**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**2**answers

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

**2**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**3**answers

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$.