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
3
votes
1
answer
608
views
Representation of GL(n, F_p) over F_p, for n small
The question is related to this post
Representation theory of the general linear group over a finite prime field
However, I am asking for more detailed references for n small, for example, for n=2, ...
- 31
3
votes
1
answer
517
views
Distribution of the powers of a primitive element of a finite field
What are known results regarding the distribution of the powers of a primitive element (generator of the multiplicative group) of a finite field? Specifically, compare the ordered list of ascending ...
- 2,075
3
votes
2
answers
195
views
Cases of almost-linear time solvable linear systems
Let a square $n\times n$ real matrix ${\bf A}$ and two vectors ${\bf x}$ and ${\bf b}$ of length $n$, such that $${\bf A}{\bf x}={\bf b}.$$
Solving for ${\bf x}$ through standard Gaussian Elimination ...
- 449
3
votes
1
answer
299
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 $K[t]...
- 1,641
3
votes
2
answers
1k
views
Cyclic order relation in Zn
The ring Zn:={0,1,..,n-1} under addition and multiplication modulo n.
Suppose a,b,c,x $\in$ Zn are nonzero and the cyclic order R(a,b,c) holds, then under what conditions does R(ax,bx,cx) hold ?
- 1,190
3
votes
1
answer
1k
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 ...
3
votes
1
answer
340
views
Number of certain elements in a finite field having zero trace
I have a question concerning certain elements having zero trace in a finite field extension and I do have the feeling that additive characters should play a role, but I am not sure how. I am stating ...
- 934
3
votes
1
answer
292
views
Number of solutions of a degree 4 polynomial equation over a finite field
Suppose that $q$ is a prime power and $\xi, \eta\in \mathbb{F}_q$ are nonzero. A computer calculation for $q<70$ suggests that the number $N$ of $4$-tuples
$(a,b,c,d)\in\mathbb{F}_q^{4}$ satisfying ...
- 1,991
3
votes
2
answers
248
views
Upper bounds on the order of a number in prime fields
Let $k$ be a fixed integer and for any prime number $p$ larger than $k$, let $\text{Order}(k,p)$ be the order of $k$ in $\mathbb{F}_p$ (i.e., $\text{Order}(k,p)$ is the least integer $n$ such that $k^...
- 343
3
votes
1
answer
285
views
A summation of powers defined by an equation over finite fields
Let $p$ be an odd prime and let $k\mid q$ for some positive integer numbers $k$ and $q$. Suppose that $r \in \mathbb{F}_{p^q}$ has multiplicative order $p^k-1$.
For each $1\leq u \leq p^k-3$, the ...
- 211
3
votes
1
answer
237
views
Intersections of products of Sylow $p$-subgroups
Motivated by the work of Cohn, Umans and collaborators on bounding the complexity of matrix multiplication, a student and I have been investigating the following problem.
For subsets $X$ and $Y$ of a ...
- 1,300
3
votes
1
answer
200
views
$P\in \mathbb{F}_{2}[x]$ for which $(\mathbb{F}_{2}[x]/(P))^{*}$ is a cyclic group
For $n \in \mathbb{N}$, we know that $(\mathbb{Z}/n\mathbb{Z})^{*}$ is a cyclic group if and only if $ n=2$, 4, $p^{k}$, or $2p^{k}$ for an odd prime number $p$.
Is there any known similar result for ...
- 39
3
votes
1
answer
321
views
Viewing $\overline{\mathbb{F}_{q}}$ as a $\mathbb{F}_{q}[X]-$module
Here $\mathbb{F}_{q}$ means a finite field with $q = p^m$ elements where $p$ is the characteristic of the field in question and $\overline{\mathbb{F}_{q}}$ means its algebraic closure.
I am studying ...
- 141
3
votes
2
answers
221
views
Number of involutions in finite reductive groups
Let $G$ be a connected split reductive group over $\mathbb{Z}$. Let $n$ be a positive integer. Let $i_n(q)$ be the number of elements of $G(\mathbb{F}_q)$ satisfying $x^n=1$.
Question: Is there a &...
- 2,751
3
votes
1
answer
237
views
invariant subspaces of general linear groups for finite fields
Let $K$ be a finite field, let $n\ge 1$ be an integer and let $G=\mathrm{GL}(n,K)$ be acting linearly on a finite dimensional $K$-vector space $V$. Although $G$ is a reductive group, it is not ...
- 7,722
3
votes
1
answer
131
views
Factoring $x^p H(x) + x^q B(x) + T(x)$ over a finite field
$\newcommand\S{\mathcal S}$
Let $p$ be a prime, and suppose that $0.9(p-1)<q<p-1$. Suppose, furthermore, that $H,B,T\in\mathbb F_p[x]$ satisfy $\max\{\deg H,\deg T\}\le q-1$ and $\deg B\le p-1-q$...
- 23k
3
votes
1
answer
237
views
Number of linearly bisected subsets in finite vector space $F_2^n$
We consider the $n$-dimenstional finite vector space $\mathbb{F}_2^{n}$ over the finite field of two elements. For a subset $A\subseteq \mathbb{F}_2^{n}$ of even size $|A|=2m$ and a linear form $l\in(\...
- 133
3
votes
2
answers
254
views
Obstruction to get a galois invariant cycle
Let $X$ be a smooth projective variety over a finite field $k$, $G=Gal(\bar{k}/k)$ and $\Gamma\in CH^i(\bar{X})$ such that:
$cl(\Gamma) \in H_{et}^{2i}(\bar{X},\mathbb{Z}_l(i))^G$ and
$\exists$ $...
- 101
3
votes
1
answer
245
views
An upper bound on the number of sets of parallel lines covering points in a finite plane?
Let $\mathbb{F}$ be a finite field of characteristic $2$. Let $L_m$ denote the set of lines in $\mathbb{F}^2$ with slope $m\in\mathbb{F}$, that is, all parallel lines of the form $y=mx+b$. Consider a ...
- 133
3
votes
1
answer
485
views
Chebyshev polynomials factoring uniformly modulo all primes
Consider the Chebyshev polynomial of the first kind $T_n(x)$ and its factorization in $\mathbb F_p$ for a given prime $p$. Most often, this factorization is not uniform (meaning that the irreducible ...
- 13.4k
3
votes
1
answer
230
views
Higher Discrete logarithms over finite fields
The polylogarithm function is defined by $$Li_s(z)=\sum_{k=1}^\infty\frac{z^k}{k^s}.$$ At $s=1$, we have the natural logarithm function. We have the inverse of natural logarithm function as the ...
- 13.9k
3
votes
1
answer
427
views
Ranks of higher incidence matrices of designs
In 1978 Doyen, Hubaut and Vandensavel proved that if $S$ is a Steiner triple system $S(2,3,v)$ then the $GF(2)$ rank of its incidence matrix $N$ is
$$
Rk_{2}(N)=v-(d_{p}+1),
$$
where $d_{p}$ is the ...
- 6,962
3
votes
1
answer
249
views
Does the Hilbert polynomial determine the weight of the Galois representation associated to a variety
Let $X$ be a curve or an abelian variety (over a finite field). Then the Galois representation associated to $X$ via the etale cohomology of $X$ (in degree $1$) is integral of weight $1$ and its ...
- 295
3
votes
1
answer
335
views
additive structure in a small multiplicative group of a finite field?
Let $p$ be a prime. Given a positive integer $n$, does there exist a
$\beta$ in an extension of $F_p$ such that
1) If $F_p[\beta] = F_{p^N}$, then $N > n^n$; ( $\beta$ lies in a high extension)
...
- 503
3
votes
1
answer
175
views
Largest subset of quadratic residues with no pair of elements differing by 1
In $\mathbb{F_p}$, $p$ prime what is the larget subset $S$ of quadratic residues with no pair of elements differing by 1?
In this related question Seva gives an example:
"...assuming $p\equiv\...
- 4,862
3
votes
2
answers
246
views
Number of solutions of quadratic equation from a perfect pairing over $\mathbb{Z}/p^n\mathbb{Z}$
Let $p>2$ be a prime number, $V=\left(\mathbb{Z}/p^n\mathbb{Z}\right)^{2k+1}$. The bilinear form $$B:V\times V \rightarrow \mathbb{Z}/p^n\mathbb{Z}$$
is a perfect pairing. That is, mapping $x\in V$ ...
- 453
3
votes
1
answer
240
views
Elliptic curve over Galois Field, Blockchain [closed]
I am interested in the elliptic curve
$$
y^2 = x^3 + 7
$$
where both $x$ and $y$ are in the finite residue class field $F_p$ with $p=2^{256}-2^{32}-2^9-2^8-2^7 -2^6-2^4 -1$. Those parameters are used ...
- 133
3
votes
1
answer
169
views
Image of the Lang-Steinberg map on disconnected centralizers of semisimple elements
Let $\newcommand{\dbF}{\mathbb F}\dbF_q$ be a finite field and let $G\subseteq\mathrm{GL}_N(\bar{\dbF}_q)$ be a connected reductive group defined over $\dbF_q$. Let $F$ be the associated Frobenius map,...
- 993
3
votes
1
answer
288
views
Representation of a finite group over a finite field from rational representations
Suppose $G$ is a the cyclic group of $n$ elements and $p$ is a prime not in $n$. $G$ has an action on the cyclotomic field as a $\mathbb{Q}$-vector space $\mathbb{Q}[X] / \langle \Phi_n(X) \rangle$ by ...
- 885
3
votes
1
answer
171
views
Solving system of multivariable algebraic equations over $\mathbb Q$ by reducing over $\mathbb F_p$
I try to solve the finite system of multivariable algebraic equations with coefficients from $\mathbb Q$. It would be sufficient for me to prove that there is only finite number of solutions over $\...
- 424
3
votes
1
answer
232
views
Computing the decimation ratio between two m-sequences
Let's suppose I have an LFSR that generates an m-sequence $y_1[k]$ --- in other words, the LFSR has $N$ bits and $y_1[k]$ has period $m=2^N - 1$.
Now suppose I know someone has decimated this and ...
- 663
3
votes
1
answer
249
views
Curious about an old algorithm which calculates modular inverse [closed]
I am not sure if I should ask this question here or somewhere else.
Background: I was searching through random mathematics paper that are related to cryptography and I came across this paper (page 3)....
- 133
3
votes
1
answer
128
views
embedding of $O_4^-(q)$ in $U_4(q)$
For $q$ an odd prime power, one can construct $H:=O_4^-(q)<U_4(q)$ by treating the $H$-invariant bilinear form as Hermitean. On the other hand $U_4(q)$ is isomorphic to $O_6^-(q)$; I need to ...
- 14k
3
votes
3
answers
161
views
How to evaluate this function in F_p efficiently?
For the positive prime integer $p$, Let $\mathbb{F}_p=\{0,1,\cdots, p-1\}$ be the finite field of order $p$.
For $x\in \mathbb{F}_p$, define $f_p(x)$ to be the maximum element in the set $\{ x^n+x^{-...
- 51
3
votes
2
answers
256
views
Picking codewords that are close
I posted this question in https://math.stackexchange.com/questions/1142698/picking-codewords-that-are-close a week back.
Let $[n,k,d]$ be a linear code over $\Bbb F_q$ with minimum distance $d$ and ...
- 13.9k
3
votes
1
answer
266
views
p-adic logarithms with fixed precision
Probably this is easy, but we would like to see it on paper.
Let $p$ be prime and $D,g,n$ positive integers.
Let $A=g^n \bmod p^D$.
Let $\log(p,a,D)$ be the p-adic logarithm with precision $D$.
In ...
- 25.4k
3
votes
1
answer
202
views
Non-zero coefficients of primitive polynomials
Let $R$ be the finite field with $q$ elements, and let $m,n\in \mathbb{N}$
be positive integers $\geq 2$. I want to prove that there exists a primitive
polynomial $$F(x) = x^{mn}-\sum\limits_{j=0}^{...
3
votes
1
answer
394
views
When does a Bohr set have the right size?
Fix a set $
\Gamma\subset \mathbb F_p$, the field with $p$ elements and a parameter $\epsilon>0$. The Bohr set $B(\Gamma,\epsilon)$ consists of those $x$ for which $x\cdot \Gamma\subseteq[-\epsilon ...
- 133
3
votes
1
answer
822
views
Trivializing principal bundles on a curve over a finite field
This is related to my question Adelic description of moduli of $G$-bundles on a curve.
Let $X$ be a smooth, projective, and geometrically connected curve over a finite field $\mathbb{F}_q$ and $G$ a ...
- 3,605
3
votes
1
answer
1k
views
Finite fields: Is multiplicative order of $x^p - x - 1$ equal to $\frac{p^p-1}{p-1}$ over GF(p)? [duplicate]
Possible Duplicate:
Multiplicative order of zeros of the Artin-Schreier Polynomial
I will be grateful for any reference to some literature on the following question (to the best of my knowledge ...
- 33
3
votes
0
answers
174
views
On the sheaves-functions dictionary
Let $X$ be a variety over a finite field $k$. Let $\pi_{1}(X)$ be the arithmetic etale fundamental group of $X$, and $\rho:\pi_{1}(X)\to k^{\times}$ a continuous character. If $x: \text{Spec}(k)\to X$ ...
- 667
3
votes
0
answers
118
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_{...
- 563
3
votes
0
answers
73
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 ...
- 591
3
votes
0
answers
167
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
3
votes
0
answers
293
views
Approximate versions of Segre's Theorem
Consider projective $2$-space over a finite field of odd prime characteristic $p$. We say a set of points, $A$, in this space is an arc if any line meets it in at most two points. We say that an arc ...
- 13k
3
votes
0
answers
91
views
Equirepartition of sums for large multisets in subsets of finite fields
Let
$p$ be a prime number and let $\mathcal A$ be a subset of $a\leq p$ distinct
elements in $\mathbb F_p$.
We denote by $\mathcal M_k(\mathcal A)$ the set of all ${k+a-1\choose k}$
multisets ...
- 17.9k
3
votes
0
answers
106
views
Is there a bijection between elements in algebraic closure of F2 and all bi-infinite periodic sequences made of 0 and 1, filling the properties below?
(And if so, how can I describe the "multiplication" on the sequence?)
We consider a bijection, denoted by $f$, from the algebraic closure of $\mathbb{F}_2$, named $\bar{\mathbb{F}_2}$, to ...
- 31
3
votes
0
answers
104
views
Are supersingular K3 surfaces unirational?
There is a conjecture due to Artin, Rudakov, Shafarevich, Shioda that supersingular K3 surfaces over a finite field are unirational. This paper claims to prove this result but it has had a recent ...
- 7,746
3
votes
0
answers
125
views
Order of elements $\gamma$ and $1-\gamma$ in $\mathbb{F}_q$
I'd like to find if possible the orders possible for $1-\gamma$ given a $\gamma\in\mathbb{F}_q$ of given order $\mathcal{o}$ (where $q=p^f$).
Which is clear is that these order have the same degree (...
- 275
3
votes
0
answers
306
views
Why the curve $x^2+y^2+y+1=0$ has only one point over $\mathbb{F}_{3^7}$?
According to both sagemath and Magma the curve $x^2+y^2+y+1=0$ has only one point over $\mathbb{F}_{3^7}$.
The projective closure has only one point too.
Q1 What hypothesis are missing to not violate ...
- 25.4k