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.
770
questions
0
votes
0
answers
37
views
When does the sum of squares/cubes of polynomials over finite field have less than maximum degree?
Given polynomials $p_1(x), p_2(x), \dots p_m(x) \in \mathbb{F}_p[x]/\langle x^p-x\rangle$ where $p$ is a prime, when does $\sum_{i=1}^m p^2_i(x)$ have degree $< p-1$? What about $\sum_{i=1}^m p^3_i(...
9
votes
0
answers
154
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 $\...
18
votes
5
answers
7k
views
Is $x^p-x+1$ always irreducible in $\mathbb 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 ...
21
votes
1
answer
570
views
Existence of a polynomial $Q$ of degree $\geq (p-1)/4$ in $\mathbb F_p[x]$ such that $QQ'$ factorizes into distinct linear factors
For all primes up to $p=89$ there exists a product $Q=\prod_{j=1}^d(x-a_j)$ involving $d\geq (p-1)/4$ distinct linear factors $x-a_j$ in $\mathbb F_p[x]$ such that $Q'$ has all its roots in $\mathbb ...
5
votes
1
answer
157
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
2
answers
303
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 ...
-2
votes
0
answers
132
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 +...
5
votes
3
answers
1k
views
How to generate the n-torsion group in an elliptic curve
Let $E$ be an elliptic curve over a field $K$.
I was curious about the following sentence: "then the $n$-torsion on $E(\overline{K})$ has known structure, as a Cartesian product of two cyclic ...
0
votes
1
answer
231
views
Product of subspace and its inverse
$\DeclareMathOperator\GF{GF}$Let $R=\GF(q)$ be a finite field with $q=p^r$ elements, where $p$ is a prime number, $S=\GF(q^n)$ be an extension of $R$, where $n\in \mathbb{N}$, $n\geq 2$ and let $K=\GF(...
10
votes
2
answers
485
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
181
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 ...
1
vote
1
answer
282
views
A "semi-genetic" definition of addition and multiplication in the field $\operatorname{On}_p$?
Let $+,\cdot$ denote multiplication in $\mathbb{N}_0$. The addition and multiplication in $\operatorname{On}_p$ are denoted $\oplus, \otimes$.
Recursive definition of addition:
$$x \oplus y := ((x+y) \...
7
votes
2
answers
302
views
When is Chevalley Warning's bound best possible?
Chevalley Warning's theorem (a form of) states that any homogeneous form over a finite field of degree $d$ in more than $d$ variables has a nontrivial zero in the field. However, for diagonal forms, ...
0
votes
1
answer
108
views
Does the Plotkin bound mean that one can not achieve the Singleton bound asymptotically?
I am a little confused with the relationship between various bounds for error correcting codes.
Does the Plotkin bound mean that one can not achieve the Singleton bound asymptotically? That is, is ...
8
votes
1
answer
589
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 ...
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 ...
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
114
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
127
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 ...
8
votes
1
answer
449
views
How large can the dimension of a 'Span of powers of a finite field basis' be?
Let $p$ be a prime. For finite field $\mathbb{F}_{p^k}$ and $d\in\mathbb{Z}^+$, I am considering the following quantity, where we interpret the field $\mathbb{F}_{p^k}$ also as a $\mathbb{F}_p$-vector ...
3
votes
0
answers
97
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
116
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 ...
5
votes
1
answer
528
views
How different can the bias of two polynomials be?
I'm trying to figure out how to approach the following question:
Let $g,h$ be polynomials over $\mathbb{Z}_p$ (for prime $p$) with $n>1$ variables.
Denote by $bias(g)=|\sum_{x\in \mathbb{Z}_p^n}e^{...
4
votes
1
answer
227
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
417
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 ...
9
votes
2
answers
757
views
What is a function field analog of Giuga's conjecture?
Giuga's conjecture (1950), which is still open and has strong numerical support, reads :
Let $n$ be a positive integer. If $1+\sum_{k=1}^{n-1}k^{n-1} \equiv 0\pmod{n}$ then $n$ is prime.
What would ...
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$...
4
votes
0
answers
173
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$ ...
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{...
0
votes
1
answer
185
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*\...
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 > ...
2
votes
0
answers
69
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
254
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 ...
6
votes
0
answers
188
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
120
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
338
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
204
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
186
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
398
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 ...