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.
773
questions
0
votes
0
answers
24
views
Endomorphism of torsion points of Drinfeld modules
Reposting from mathstackexchange.
A Drinfeld module is defined to be an $\mathbb F_q$-algebra morphism $\phi: \mathbb F_q[T] \rightarrow K\{\tau\}$, where $K=\mathbb F_{q^m}$ is a finite field and $K\{...
- 139
1
vote
0
answers
64
views
When does sum of algebraically independent polynomial become dependent?
Given $f_1,...,f_n \in \mathbb{F}[x_1,...,x_n]$ where $f_n = g + h$. Suppose the sets $\{ f_1,...,f_{n-1},g \}$ and $\{ f_1,...,f_{n-1},h \}$ are algebraically independent then is there a ...
- 159
1
vote
0
answers
114
views
Solution formula in an explicit equation over $\mathbb{F}_p^3$
I'm looking into a formula involving prime numbers $p \geq 7$ and an equation's solutions. The equation in question is:
$$z^2 = (x^2 - 4x)(y^2 - 4y)((x + 1 - y)^2 - 4x),$$
where $(x,y,z)\in \mathbb{F}...
- 71
0
votes
0
answers
91
views
Is there an inner product on $\mathbb{F}_p\left[S_n\right]$ for which $\langle x, x \rangle \ne 0$ for all $x$?
Let $\mathbb{F}_p\left[S_n\right]$ be the group algebra of the symmetric group $S_n$ over the finite field $\mathbb{F}_p$.
One can define an "inner product" in the usual way:
$$\langle x,y \...
- 519
0
votes
0
answers
39
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
162
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 $\...
- 40.9k
5
votes
1
answer
162
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\{\...
- 51
0
votes
0
answers
169
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\...
- 913
0
votes
0
answers
74
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
487
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$?
- 103
1
vote
1
answer
170
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,574
0
votes
1
answer
111
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,...
- 3,737
0
votes
1
answer
184
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 ...
- 121
3
votes
0
answers
161
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 ...
- 31
8
votes
1
answer
598
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 ...
- 159
4
votes
0
answers
157
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 ...
- 53.1k
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 \}$
$...
- 159
2
votes
1
answer
130
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 ...
- 21
3
votes
0
answers
100
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_{...
- 553
2
votes
0
answers
119
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 ...
- 17.5k
4
votes
1
answer
228
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 ...
- 3,432
2
votes
2
answers
421
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 ...
- 1,141
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}) = ...
- 159
1
vote
1
answer
107
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 ...
- 159
2
votes
2
answers
304
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 ...
- 40.9k
1
vote
1
answer
96
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 ...
- 913
1
vote
0
answers
68
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$...
- 581
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*\...
- 581
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{...
- 159
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$ ...
- 581
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 ...
- 581
1
vote
1
answer
216
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:
$$...
- 553
0
votes
0
answers
89
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{_{}^{...
- 553
1
vote
0
answers
85
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 ...
- 581
4
votes
0
answers
255
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 ...
- 581
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 > ...
- 61.5k
6
votes
0
answers
190
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 ...
- 581
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 ...
- 581
1
vote
1
answer
123
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 ...
- 581
5
votes
1
answer
342
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 $\...
- 8,852
4
votes
1
answer
206
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 ...
- 8,852
2
votes
1
answer
188
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 ...
- 581
6
votes
2
answers
399
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 ...
- 595
2
votes
1
answer
149
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 ...
- 913
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 ...
- 209
5
votes
1
answer
304
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$...
- 25.3k
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 ...
- 3
1
vote
1
answer
282
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
2
votes
1
answer
146
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}
\...
- 553
3
votes
0
answers
112
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 $\...
- 145