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.
769
questions
9
votes
0
answers
144
views
Who was the first to prove that the automorphism group of a finite field is cyclic and is generated by the Frobenius automorphism?
$\DeclareMathOperator\Aut{Aut}$It is well-known that the automorphism group $\Aut(F)$ of a finite field $F$ of characteristic $p$ is cyclic of order $n$ where $|F|=p^n$. Moreover, the cyclic group $\...
5
votes
1
answer
151
views
Rational functions of order $3$
Let $p$ be a prime, let $\mathbb K$ a field with $\operatorname{char}(\mathbb K)=p$ and $\mathbb{K}(x)$ be the field of fractions of the polynomial ring $\mathbb{K}[x]$, i.e. $$\mathbb{K}(x)=\left\{\...
-2
votes
0
answers
131
views
Elimination over $\mathbb F_p[x,y]$
Let $p$ be a prime. Consider the two independent modular equations:
$$a_1x^2+b_1y^2+c_1xy\equiv d_1\bmod p$$
$$a_2x^2+b_2y^2+c_2xy\equiv d_2\bmod p$$
Is it possible to extract the common roots $(x,y)\...
0
votes
0
answers
165
views
Degree 6 Galois extension over $\mathbb{Q} $
Let L be the splitting field of $ x^3- 2$ over $ \mathbb{Q}$. Then $ G=\operatorname{Gal}(L/K) \cong S_3$. Let $\sigma\in G$ such that the fixed field of $ \sigma$ is $\mathbb{Q}(2^{1/3})$. Let $x,y\...
0
votes
0
answers
73
views
Number of solutions $x$ of equation $a_1 b_1^x + \dotsb + a_n b_n^x=0$ over a finite field
Let $F$ be a finite field and let $a_1, b_1, \dotsc, a_n, b_n \in F$ be field elements. I am interested in the number of solutions $0\leq x \leq |F|-1$ such that
\begin{equation}\label{e:1}
a_1 b_1^x +...
10
votes
2
answers
483
views
Isomorphic finite fields of a skew field
Let $D$ be a skew field and $F$ and $E$ be isomorphic finite subfields of $D$, is it true that $F=E$?
1
vote
1
answer
165
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 ...
0
votes
1
answer
109
views
Loss of degree for polynomials
Let $q$ be a power of a prime $p$, $m$ be an integer greater than $0$. Does there exist polynomials $P_0,\cdots,P_m$ of $\mathbb F_q[T]$ not all in $\mathbb F_q$ such that there exist polynomials $Q_0,...
0
votes
1
answer
180
views
Constructing a family of $3$-wise independence functions from $\mathbb{Z}_p^n \rightarrow \mathbb{Z}_p$
A family of function hash functions $\mathcal{H}:\{h:N\rightarrow M\}$ is call $k$-wise independent if whenenver $h$ is drawn uniformly from $\mathcal{H}$, let $x_1,\ldots,x_k$ be distinct elements of ...
3
votes
0
answers
160
views
Characters of finite fields - Reference request
Let $\mathbf{F}_q$ ($q=p^f$) be a finite field. We are interested in the characters $\chi: \mathbf{F}_q\rightarrow \mathbf{K}$ ($\chi(0)=0$) where the $ \mathbf{K}$ is an alg.closed field of ...
8
votes
1
answer
584
views
A question on algebraic independence
Let $f_1,f_2,\ldots,f_n, g \in \mathbb{F}_q[x_1,...,x_m]$. Assume that $f_1,\ldots,f_n$ vanish at $0$, so that $\mathbb{F}_q[[f_1,...,f_n]]$ is a subring of $\mathbb{F}_q[[x_1,...,x_n]]$. Suppose that ...
4
votes
0
answers
156
views
When is $q$ invertible mod $m$, mod its order mod $m$, mod its order mod its order mod $m$, ad infinitum?
Fix an [edit: positive] integer $q$. Let me say that an [edit: positive] integer $m$ is IK over $q$ if $q$ and $m$ are coprime and the (multiplicative) order of $q$ mod $m$ is IK over $q$. Note that ...
0
votes
0
answers
113
views
A question on a system of quadratic polynomials
Consider the following system of quadratic polynomials $f_1,...,f_n \in \bar{\mathbb{F}}_2[x_1,....,x_n]$ :
$f_1 (\bar{x}) = x_1 + x_n^2 + q_1$
$f_i(\bar{x}) = x_i + q_i$ for $i \in \{2,...,n-1 \}$
$...
2
votes
1
answer
126
views
Are there a few input bits that randomize the output of an $\mathbb{F}_2$ polynomial?
Suppose $f:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$ is a degree $d$ polynomial and $\epsilon>0$ is some real number. Does there necessarily exist a set $C\subset [n]$ of coordinates with the size of ...
3
votes
0
answers
96
views
A question on the averages of Kloosterman sums
Sorry to disturb. Recently, I encountered a puzzle on the sums involving two Kloosterman sums. That is,
For any $h, q_1,q_2\in \mathbb{N}$ with $(q_1,q_2)=1$ and $Q>1$, how two get a bound
$$\sum_{...
2
votes
0
answers
114
views
Can K$_3$ of finite fields be related to Teichmüller cocycles?
This is sort of a blind shot, but...
For a ring $R$, its third algebraic K-group is given by $\operatorname K_3(R)=H_3(\operatorname{St}(R))$.
To simplify matters, let $R$ be a finite field $\mathbb ...
4
votes
1
answer
226
views
Frobenius and regular scheme
Let $X$ be a noetherian regular scheme over $\mathbb{F}_{p}$. Then by Kunz's theorem, the absolute Frobenius $F: X\rightarrow X$ is flat and integral. Can it be written as a projective limit of finite ...
2
votes
2
answers
415
views
Defining a sign of square roots in GF(p)
$\DeclareMathOperator\GF{GF}$Consider the following expression:
$$
\sqrt{a_1} \pm \sqrt{a_2} \pm \dots \pm \sqrt{a_n} = 0,
$$
where $a_1, \dots, a_n$ are positive integers. We want to find the number ...
0
votes
0
answers
109
views
Characterisation of even characteristic quadratic system
$\DeclareMathOperator\supp{supp}$Let $f_i \in \bar{\mathbb{F}}_2[x_1,..,x_5]$ for $1 \leq i \leq 5$ be such that
$f_1(\bar{x}) = x_1 + x_5^2 + q_1$,
$f_2(\bar{x}) = x_2 + x_1^2 + q_2$,
$f_3(\bar{x}) = ...
1
vote
1
answer
105
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 ...
2
votes
2
answers
299
views
A graphic representation of classical unitals on 28 points
I would like to understand the geometry of the classical unitals.
They are block designs containing $q^3+1$ points and whose blocks have cardinality $q+1$, where $q$ is a prime power. For $q=2$ (if I ...
1
vote
1
answer
95
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 ...
1
vote
0
answers
67
views
Bias of $a^k / q$ modulo $q$?
Let $q$ be a prime. Let $0< a < q$ be an integer so that it is primitive modulo $q$. Let $k$ be a random integer up to $q-1$. Consider
$$a^k = b_k + q * c_k$$
as $k$ varies modulo $q^2$. So $b_k$...
0
votes
1
answer
184
views
Trying to solve for the remainder of $a^q$ modulo $q$
Let $q$ be a prime and $a$ be a number from $0$ to $q-1$ (not an equivalence class).
The elements $a^q$ are exactly the elements of order $q-1$ modulo $q^2$.
I'm trying to solve the equation:
$$a+2*\...
1
vote
1
answer
169
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{...
4
votes
0
answers
171
views
Intrinsic maps between complex integers modulo $p$ and integers modulo $p+2$
$\DeclareMathOperator\GF{GF}$Let $p$ and $p+2$ be twin primes. Let's assume that $-1$ is not a quadratic residue modulo $p$ (and therefore is a Q.R. modulo $p+2$).
Consider the complex numbers $a+bi$ ...
2
votes
0
answers
68
views
Is the discrete logarithm equivalent to solving polynomial discrete logarithms?
Suppose we can quickly solve the discrete logarithm modulo $p$. Let's say $2$ is a generator so we can quickly find $l$ for which $2^l =h$ for any given target $h$.
An interesting observation is that ...
1
vote
1
answer
212
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:
$$...
0
votes
0
answers
88
views
A question on the evaluations of certain three-dimensional hyper-Kloostermans
There is a basic question regrading the 3-dimensional hyper-Kloosterman sum which needs some help from the experts here:
For any integers $q,h \in \mathbb{N}$, how to estimate the sum:
$$\sideset{_{}^{...
1
vote
0
answers
84
views
Functions that take quadratic residues to non quadratic residues
Let $p$ be prime and $Q$ be the set of integers $x$ mod $p$ so that $x^2-1$ is a quadratic residue. Let $Q^c$ be the complement of $Q$. If we don't consider $x = 1$ then these two sets have the same ...
4
votes
0
answers
253
views
Cosine Modulo $p$?
Consider the integers modulo a prime $p$. I'm looking for a nice polynomial function that acts as a sort of "cosine" on the integers modulo $p$. Specifically, I'm looking for solutions to ...
4
votes
1
answer
328
views
GCD in $\mathbb{F}_3[T]$ with powers of linear polynomials
This is a continuation of my previous question on $\gcd$s of polynomials of type $f^n - f$.
Let us call $n > 1$ simple at a prime $p$ when $p-1 \mid n-1$ but $p^k - 1 \not\mid n-1$ for all $k > ...
6
votes
0
answers
176
views
Newton type method for finite fields?
I have a polynomial $p(x)$ in $\mathbb{Z}/q\mathbb{Z}$ that is easy to compute for any $x$ but has an absurdly large degree $d > 2^{256}$. I know for a fact that it has a zero and I would like to ...
2
votes
0
answers
134
views
What is the periodicity of $((a^n \text{ modulo } p) \text{ modulo } q)$
This feels like it should be elementary but it came up in my research and I was not able to solve it.
We can ask this question for any $p$ and $q$ but,let $p$ and $q$ be primes for simplicity. The ...
1
vote
1
answer
118
views
Constant term of a power modulo a polynomial
I'm interested in the constant term of $$(x+k)^m \in F_p[x]$$
modulo a polynomial $q(x)$ over the field $F_p$. The polynomial $q(x)$ is relatively simple in practice, take $q(x) = x^6 -2x^3+3$, for an ...
5
votes
1
answer
337
views
Fermat cubic hypersurfaces over finite fields
Consider the Fermat cubic
$$
X = \{x_0^3+\dots +x_n^3 = 0\}\subset\mathbb{P}^n_{\mathbb{F}_{q}}
$$
over a finite field $\mathbb{F}_{q}$ with $q$ elements.
If $q \equiv 2 \mod 3$ then the projection $\...
4
votes
1
answer
203
views
Points on affine hypersurface over finite field
I am interested in the hypersurface $X\subset\mathbb{A}^4_{\mathbb{F}_{5^n}}$ defined by
$$
X = \{x^3 + 3xy^2 + z^3 + 3zw^2 + 1 = 0\}
$$
over a finite field $\mathbb{F}_{5^n}$ with $5^n$ elements. Via ...
2
votes
1
answer
182
views
Chinese remainder theorem for composition
Let $f(x) \in F_p[x]$ and I know $f(x)$ modulo two polynomials $\phi_1(x)$ and $\phi_2(x)$. What sort of information about $f$ modulo the composition $\phi_1(\phi_2(x))$ can I recover?
I'm looking ...
6
votes
2
answers
397
views
Good and bad reduction for twists of algebraic curves
Suppose we have two curves $C/\mathbb{Q}$ and $C'/\mathbb{Q}$ which are twists of each other i.e. they are isomorphic over a field extension $K/\mathbb{Q}$.
Suppose that $C$ has good reduction at a ...
2
votes
1
answer
145
views
Automorphism of positive characteristic field
Suppose $K$ is a field with $\text{char}(K) \geq 0$. Let $L$ be a cyclic extension of $K$ with degree $2n$. We consider the generator $\sigma$ of the Galois group $\text{Gal}(L/K)$.
I am interested in ...
2
votes
0
answers
186
views
Factorization of the polynomial $x^k + x^{k-1} + x^{k-2} + \cdots + x + 1$ in $\mathbb{F}_2[x]$ [closed]
Is anything known about the factorization of the polynomial $x^k + x^{k-1} + x^{k-2} + \cdots + x + 1$ in $\mathbb{F}_2[x]$?
When can it be factored, what are the irreducible factors, what are the ...
5
votes
1
answer
298
views
Galois action on algebraic K-theory of finite fields
This might be well-known to experts. I was just teaching a course where we went through some parts of Quillen's theorem computing the higher algebraic K-theory of finite fields. Denote by $\mathbb F_q$...
0
votes
1
answer
79
views
Algorithm to find a number B with same modulus as A with prime P and specific binary positions set to zero
Given a prime $P$, an integer $A$ $(0\leq A<P$), and a set of legal positions (encoded as a binary mask $\text{mask}$), is there an efficient algorithm to find a number $B$ that has the same ...
1
vote
1
answer
277
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 ...
2
votes
1
answer
145
views
On the estimate for the mixed 3-dimensional hyper-Kloosterman sum
There is a basic question regrading the mixed 3-dimensional hyper-Kloosterman sum:
For any positive integer $n$ not divisible by $p$, how to prove
$$\sideset{_{}^{}}{^{\ast}_{}}\sum _{x,y ,z\bmod p}
\...
3
votes
0
answers
111
views
Effective Lang-Weil bounds for higher codimension varities
The Lang-Weil bounds imply that for a geometrically irreducible variety $X$ of dimension d over $\overline{\mathbb{F}_p}$ we have,
$$|N_q(X)-q^{d}|\le O(q^{d-1/2}),$$
where $N_q(X)$ is the number of $\...
4
votes
1
answer
329
views
Polynomial that is not always a square over $\mathbb{Z}_p$
Let $p > 3$ be prime. Is is true that there exists $x \in \mathbb{Z}_p$ such that
$$
(1+x^2)^3-1
$$
is not a square in $\mathbb{Z}_p$? In particular, when $-1$ is not a square in $\mathbb{Z}_p$, ...
0
votes
0
answers
107
views
Cubic monic polynomial over z_p
Let
$$
f_{a}(x)=x^3+(u-2-a)x^2+ax+1,
$$
where $u\in\mathbb{Z}_p^*$ is fixed. Let $S$ be the set consisting of all $a\in\mathbb{Z}_p$ such that $f_{a}(x)$ factor linearly. Then what is the cardinality ...
13
votes
2
answers
702
views
Isomorphism of varieties in $\mathbb{C}$ implies isomorphism over finite fields
Suppose that $X$ and $Y$ are algebraic varieties over $\mathbb{Z}$ (add your favourite hypotheses, like smooth or affine if needed). Denote by $X_k$ and $Y_k$ their base-change to varieties over a ...
1
vote
0
answers
63
views
Is there an available English translation for Artin's "Quadratische Körper im Gebiete der höheren Kongruenzen"?
Otherwise, is it reasonable to work through the German edition with only a basic knowledge of German?