Questions tagged [finite-fields]
A finite field is a field with a finite number of elements. For each prime power $q^k$, there is a unique (up to isomorphism) finite field with $q^k$ elements. Up to isomorphism, these are the only finite fields.
814 questions
2
votes
0
answers
190
views
Existence of roots of high order polynomial over finite fields
I want to solve the following question:
Consider a polynomial $f(x)=a_0+a_1*x^{e_1}+a_2*x^{e_2}+\cdots+x^{e_m}\in F_p[x]$ where $p$ is a prime such that $\log(p)\sim m$ and $e_m\sim 2^m$, I want to ...
- 509
2
votes
0
answers
337
views
Enumerating certain types of permutation polynomials
Given a prime power $q$, I would like to enumerate (preferably up to isomorphism*) all the permutation polynomials $f(x)$ on $K = GF(q^3)$ satisfying the following conditions:
$f(ax) = af(x)$ for all ...
- 1,197
2
votes
0
answers
358
views
Counting points on an algebraic set over a finite field
Let $q=p^n$, for $p$ a prime. Let $C$ be an Artin–Schreier curve defined by $y^p-y=f(x)$ where $f(x) \in \mathbb{F}_{q}[x]$.
Let $C_g$ be $y^p-y=f(x)$ where $x \in g(\mathbb{F}_{p^{n}})$ for some $...
- 21
1
vote
2
answers
502
views
When is PSU(2,q^2) = PSL(2,q) ?
The context for this question is from page 284 - 287 of Berger's paper: http://pdn.sciencedirect.com/science?_ob=MiamiImageURL&_cid=272332&_user=209810&_pii=S0021869398976785&_check=y&...
- 10.7k
1
vote
3
answers
1k
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, ...
- 1,109
1
vote
1
answer
234
views
Are there conditions for an elliptic curve to have a quadratic $\mathbb{F}_q$-cover of the line without ramification $\mathbb{F}_q$-points?
Consider an elliptic curve $E: y^2 = f(x) := x^3 + ax + b$ over a finite field $\mathbb{F}_q$ of characteristic $> 3$. Obviously, the projection to $x$ is a quadratic $\mathbb{F}_q$-cover of the ...
- 1,833
1
vote
1
answer
177
views
Algebraic independence of polynomials when truncated imply algebraic independence of the entire polynomial?
Let $f_1,\ldots,f_m \in \mathbb{F}[x_1,\ldots,x_n]$ and suppose $\hat{f}_i = f_i$ $\bmod \langle x_1,\ldots,x_n\rangle^3$ (i.e. the linear and quadratic part of $f_i$). Then if $\hat{f}_1,\ldots,\hat{...
- 341
1
vote
2
answers
371
views
Automorphisms of a curve
I am looking the group of automorphisms $G$ of the curve defined over $\mathbb F_3$ by (in projective coordinates) $Y^2Z=X(X-Z)(X-2Z)$.
Obviously, there are the automorphisms $X\mapsto X+\alpha Z$ (...
- 3,998
1
vote
1
answer
84
views
infinite many multiples of a polynomial in $\mathbb F_q[T]$
Let $P$ be an irreducible polynomial of $\mathbb F_q[T]$, $(u_n)_n$ be an infinite sequence of distinct elements of $\mathbb N_0$. Does there exist infinitely many multiples of $P$ in $\mathrm{Vect}_{\...
- 3,998
1
vote
2
answers
391
views
A quantity associated to a field extension
Let $F\subset E$ be a field extension. So $E$ has a natural structure of $F$-vector space.
A vector subspace $V\subset E$ is a special subspace if $F\subset V$ and $V$ is closed under the inverse ...
- 356
1
vote
2
answers
349
views
How many non-isomorphic associative algebras of dimension 2 over the field F_{p^k} are there?
How many non-isomorphic associative algebras of dimension 2 over the field F_{p^k} are there?
As much as I have searched, I have not found any results that answer my question; not even for k = 1,2.
1
vote
2
answers
323
views
Does there exist a surface over a finite field which contains three skew lines?
Does there exist an irreducible surface, other than Hermitian surface, in $\mathbb{P}^3 (\mathbb{F}_q)$ containing three skew lines?
I know that this is true for Hermitian surface. In fact, at every ...
- 41
1
vote
2
answers
290
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 ...
- 24.9k
1
vote
1
answer
167
views
Limit of trace maps in finite fields
If $\mathbb{F}_{q^n}$ is a finite field with $q^n$ elements ($q$ being a power of a prime $p$) we have the trace map $tr^n_m:\mathbb{F}_{q^n}\rightarrow \mathbb{F}_{q^m}$ such that $x\mapsto x+F^m(x)+....
- 335
1
vote
1
answer
323
views
Maximal separable extension of $\mathbb F_q((t))$
Let $K=\mathbb F_q((t))$. I want to prove that $K^{sep}$ is composite of $K^{sep}(p)$ and $K^{sep}(not \ p)$, where $K^{sep}(p)$ is maximal Galois extension of $K$ of exponent $p$, $K^{sep}(not \ p)$ ...
- 11
1
vote
2
answers
472
views
Equations of elliptic curves
First part of question I have asked on mathoverflow already: https://math.stackexchange.com/questions/467088/explict-form-of-the-equation-of-elliptic-curve
1) Let $E(\mathbb{F}_{q^2})$ is elliptic ...
- 2,576
1
vote
1
answer
468
views
Artin's conjecture for polynomials and rational functions over finite fields
Artin's conjecture on primitive roots over the integers states that a given integer
$0\ne h\in \mathbb{Z}$ that is neither a square number nor $-1$ is a primitive root modulo infinitely many primes $p$...
- 11
1
vote
2
answers
256
views
Reference for integral extensions of $\mathbb{Z}/p^k\mathbb{Z}$
I was looking for a reference which discusses the structure of finite integral extensions of $\mathbb{Z}/p^k\mathbb{Z}$. In particular, I am interested in understanding what the abelian group of its ...
- 145
1
vote
1
answer
540
views
Number of zeros of quadratic equation over finite fields
Let $\mathbb{F}_q$ denote the finite field with $q$ elements and Ch$\mathbb{F}_q\neq 2$. What is the number of solutions of the quadratic equation
$X_1^2+\cdots + X_r^2=0$ in $\mathbb{F}_q^m$ for $1\...
- 179
1
vote
1
answer
993
views
Number of subset sums
Let $\mathbb{F}_q$ be a finite field with characteristic $p$ and $p < q$ (i.e. not a prime field). Let $D\subseteq \mathbb{F}_q$ be a some set with $|D|=n$. Find a non-empty subset $\{x_1,\dots,x_k\...
- 273
1
vote
1
answer
111
views
Expected number of solutions of a random quadratic polynomial system over a finite field
Let $\mathbb{F}_q$ be a field of $q$ elements. Let $a_{i,j,k}$, $b_{i,j}$, $c_i$ ($1 \leq i \leq m$, $1 \leq j \leq k \leq n$) be independent uniformly distributed random variables in $\mathbb{F}_q$, ...
- 157
1
vote
1
answer
100
views
Existence of a symmetric matrix satisfying certain irreducible conditions
Let $K$ be a field such that $ \mathrm{char}(K) \neq 2 $. Let $ p(x) $ be an arbitrary irreducible polynomial over $K$ of degree $n$. Using the rational canonical form, we can always construct an $ n ...
- 923
1
vote
1
answer
259
views
On the estimate for a double exponential sum
I encounter a hyper-Kloosterman sum which needs some help from the experts here:
For any integers $q,s \in \mathbb{N}^+$(which may not be necessarily co-prime with each other), how to bound the sum:
$$...
- 563
1
vote
1
answer
154
views
Lifting Lang-Steinberg to DVR's in Characteristic 0
Let $A$ be a compact DVR in characteristic $0$, uniformizer $\pi$ and residue field $k$. Let $A\subset B$ be a complete DVR with the same uniformizer $\pi$ and algebraicly closed residue field $F$. ...
- 273
1
vote
2
answers
185
views
Number of solutions to $mx^2+ny^2 \equiv k\pmod{p}$
I need a reference for the result which gives the number of solutions to the congruence $mx^2+ny^2 \equiv k\pmod{p}$. This result seems to be something that would be discussed in Gauss' ...
- 11
1
vote
1
answer
178
views
Matrices over a finite field: matrices for which some unipotent $U$ satisfies Trace$(ZU)=0$ for all $Z$ in the commutant
Let $p$ be an odd prime number, let $A\in M_p(\mathbb{F}_p)$ be a $p$-by-$p$ matrix with coefficients in $\mathbb{F}_p$, let $C(A)$ be the commutant of $A$, and let $N\in M_p(\mathbb{F}_p)$ be a ...
- 3,741
1
vote
1
answer
116
views
A question on classification of quadratic polynomials in even characteristic
$\DeclareMathOperator\supp{supp}$Let $f_1,...,f_n \in \bar{\mathbb{F}}_2[x_1,...,x_n]$ such that $f_i = x_i + q_i$ for $1\leq i \leq n-1$ and $f_n = q_n$ where $q_1,...,q_n$ are homogenous quadratic ...
- 341
1
vote
1
answer
184
views
Known estimate for gaussian sum $\sum_{x \in \mathbb{F}_q} \psi( a x^m + b x^n)$?
Let $\mathbb{F}_q$ be a finite field, $\psi$ be a non-trivial additive character over $\mathbb{F}_q$, and $a, b \in \mathbb{F}_q$ constants. Is there any known estimate for the gaussian sum
$$\sum_{x \...
- 219
1
vote
1
answer
203
views
Order of roots for a polynomial $P\in\mathbb{F}_p[T]$
Let $P\in\mathbb{F}_p[T]$ (not supposed irreducible). All roots $\xi$ of $P$ have a certain order $k$ such that $\xi^k=1$.
Question: is it possible to know the order of the roots of the given ...
- 275
1
vote
1
answer
199
views
Is finite field version kakeya conjecture still true when changing the line of every direction with only 2(or several but not the full line)element?
The classical finite field Kakeya conjecture state as following (for conveinent, all version of kakeya conjecture is state in hasdorff dimension version):
$\mathrm{Finite\ Field\ Kakeya\ ...
- 543
1
vote
1
answer
111
views
Notions of convergence over extensions of finite fields
Let $\displaystyle Q_p[x] = \left\{\frac{p(x)}{q(x)} \mid \, p(x),q(x) \in \mathbb{F}_p[x], \, q(x) \neq 0 \right\}$ denote the field of fractions extending $\mathbb{F}_p[x]$. If we consider the ...
- 1,549
1
vote
1
answer
221
views
Linear characters of algebraic closed fields
This question is a bit of a follow up to this question.
Let us consider the finite field $\mathbb{F}_q$ and its algebraic closure $\mathbb{F}$, viewed as an additive abelian group. Its group of ...
- 335
1
vote
1
answer
139
views
A polynomial recovery problem
Suppose we know $deg(m(x))=n-1=deg(f_1(x))=deg(f_2(x))$.
Suppose we know $C_1(x),C_2(x)$ where $deg(C_i)=n$.
Then given $n$ values of $$C_1(x)(x+1)m(x) +C_1(x)(x+2)f_1(x)\in\Bbb F_q[x]$$ and $n$ ...
user94040
1
vote
1
answer
82
views
question about sets of polynomials with a special agreement guarantee
Let $\mathbb{F}$ be a finite field and $S\subset\mathbb{F}_{\leq d}[x,y]$, a set of bivariate polynomials over $\mathbb{F}$ of degree at most $d\ll|\mathbb{F}|$. Assume the linear span of $S$ is all ...
- 125
1
vote
1
answer
190
views
How to prove non-divisibility by a linear factor
Let $f(x,y) := (x+1)\cdots (x+j)-(y+1)\cdots (y+k) \in \mathbb{F}_{q}$, where $j>k$. Do you know if there is a quick way to show that no polynomial of the form $ax+by+c$, with $(a,b)\in \mathbb{F}_{...
- 87
1
vote
1
answer
802
views
Trace 0 and Norm 1 elements in finite fields
Let $\mathbb{F}_{q^\ell}/\mathbb{F}_{q}$ be the extension of finite filed $\mathbb{F}_{q}$, where $\ell$ be a odd prime and $(\neq q)$. Take $\zeta\in\mathbb{F}_{q^\ell}$. Does there exist different $...
- 255
1
vote
1
answer
781
views
Solving Non-Linear Equations over a Finite Field of a Large Prime Order
I want to know is there is an efficient way to figure out whether or not a ( underdetermined) system of non-linear equations have a solution over a finite field of large prime order. The equations ...
- 11
1
vote
3
answers
1k
views
Complete sets of functions
A (finite) set $S$ of boolean functions is called functionally complete if every boolean function can be presented as a finite composition of functions from $S$. For example, $\{ \neg,\wedge \}$ is ...
- 411
1
vote
1
answer
401
views
Finding an embedding efficiently in field extension of finite field
We know that $GF(p^c)$ is a subfield of $GF(p^{cn})$. Also we know that elements in $GF(p^c)$ can be represent by degree $c$ polynomials with coefficients in $\mathbb Z_p$, where multiplication is ...
- 207
1
vote
2
answers
406
views
Minimum Growth Rate of Hamming Weight of Multiples of Primitive Polynomials
Let $F_2[x]$ denote the ring of polynomials over the field of 2 elements.
Richard Brent has a page on finding primitive trinomials in $F_2[x]$ of huge degree at http://maths.anu.edu.au/~brent/trinom....
- 10.4k
1
vote
1
answer
291
views
Sub-representations of the affine group
Let $F=\mathrm{GF}\left(p^k\right)$ be any finite field. Let $G$ be the group of all affine permutations on $F$ (i.e. permutations of form $x\mapsto ax+b$). Then the set of all functions from $F$ to $\...
- 2,179
1
vote
1
answer
333
views
Szemerédi–Trotter type theorem in finite field
This question is about the content of this paper by J. Bourgain, N. Katz, T. Tao.
In the final step (page 18) of the proof of Szemerédi-Trotter type theorem, we have already known
$$|A''+A''|\lesssim ...
- 13
1
vote
1
answer
109
views
Distribution of weight of special type of random-matrix vector product?
Let $G$ be a matrix of dimension $k \times n$ sampled uniformly randomly from $F_2^{k \times n}$. It is a well known fact that $y = xG$ is uniformly distributed in $F_2^n - \{0\}$ for all $x \in F_2^k$...
- 111
1
vote
1
answer
338
views
Polynomial form/Fourier transform of rational function over finite affine space
I am certainly going to make a mess of any serious algebraic terminology, so bear with me as I present my problem arising from a probability problem.
Consider the space of sequences of $n$ zero-one ...
- 526
1
vote
1
answer
391
views
System of equations - Proof that a solution exists
Let $ a = (a_1,a_2, \ldots,a_{10})\in \{ 0,1\}^{10}$ be a binary vector of length $10$.
Question: Without using a computer-aided method, how to prove that there exists binary vectors $x_{i,j} \in \{ ...
user83947
1
vote
1
answer
85
views
Converging sequence of polynomials
Let $P$ be an irreducible polynomial of $\mathbb F_q[T]$ of degree $2$. Does there exist two polyomials $\alpha,\beta\in\mathbb F_q[T]$ (not both zeroes) such that the sequence $(\beta T^{q^{2n}}-\...
- 3,998
1
vote
1
answer
2k
views
Write the algebra closure of $F_p$ as union of finite fields [closed]
This question follows Field theory by Steven Roman, Chapter 9, Exercise 20.
Denote the algebraic closure of the finite field $F_q$ by $\Gamma(q)$, and let $a_n$ be any strictly increasing infinite ...
- 205
1
vote
1
answer
175
views
Pair of vectors multiplied by a random matrix and its inverse transpose are distributed randomly up to their dot product
Given arbitrary nonzero vectors $\vec{x}_1, \vec{y}_1, \vec{x}_2, \vec{y}_2 \in \mathbb{Z}^{n}_p$ ($p$ prime) with $\langle x_1, y_1 \rangle = \langle x_2, y_2 \rangle$, I am trying to show that: $(...
- 11
1
vote
1
answer
134
views
Generalization of a field norm to the linear group
I've been struggling with this question for some days now. Let $K$ be a field extension of $k$, and $x$ an invertible linear transformation of the $K$-vector space $V$. If we consider $V$ as a $k$-...
1
vote
1
answer
426
views
Efficient algorithm for $x^n-x \bmod P(x)$ over $GF(2^{12})$
My goal is to generate an irreducible polynomial over $GF(2^{12})$ with degree $t$, which can get fairly big, let's say up to $t=200$ or so. I've found this very helpful paper that walks me through ...
- 131