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.
84 questions
13
votes
2
answers
1k
views
Number of commuting pairs (triples, n-tuples) in GL_n(F_q) (and other groups)?
Question 1 What is the number of pairs of commuting elements in GL_n(F_q) ?
I am aware of many results concerning commuting elements in Mat_n(F_q), but I am interested in GL i.e. non-degenerate ...
- 24.9k
67
votes
6
answers
7k
views
How to recognise that the polynomial method might work
A couple of days ago I was at a nice seminar given by Christian Reiher, during which he told us about a short proof of the following special case of a theorem of Olson.
Theorem. Let $(a_1,b_1),\dots,(...
- 29k
56
votes
14
answers
21k
views
Fantastic properties of Z/2Z
Recently I gave a lecture to master's students about some nice properties of the group with two elements $\mathbb{Z}/2\mathbb{Z}$. Typically, I wanted to present simple, natural situations where the ...
32
votes
9
answers
5k
views
How many groups of size at most n are there? What is the asymptotic growth rate? And what of rings, fields, graphs, partial orders, etc.?
Question. How many (isomorphism types of) finite groups of size at most n are there? What is the asymptotic growth rate? And the same question for rings,
fields, graphs, partial orders, etc.
...
- 236k
23
votes
4
answers
3k
views
Exhibit an explicit bijection between irreducible polynomials over finite fields and Lyndon words.
Let $q$ be a power of a prime. It's well-known that the function $B(n, q) = \frac{1}{n} \sum_{d | n} \mu \left( \frac{n}{d} \right) q^d$ counts both the number of irreducible polynomials of degree $n$...
- 118k
22
votes
1
answer
4k
views
maximal order of elements in GL(n,p)
I am looking for a formula for the maximal order of an element in the group $\operatorname{GL}\left(n,p\right)$, where $ p$ is prime.
I recall seeing such a formula in a paper from the mid- or early ...
- 221
18
votes
5
answers
2k
views
Good source for representation of GL(n) over finite fields?
I'd like to gain some understanding of unitary representations of GL(n) over finite fields. Any good source would be appreciated.
======== edit =========
My original question was ambiguous. ...
- 297
18
votes
1
answer
2k
views
Conjecture: The number of points modulo $p$ of certain elliptic curve is $p$ or $p+2$ for $p$ of form $p=27a^2+27a+7$
Numerical evidence suggests a conjecture that the number of
points of certain elliptic curve over $\mathbb{F}_p$ is
either $p$ or $p+2$ for $p$ of certain form.
Let $p$ be prime of the form $p=27a^2+...
- 25.4k
6
votes
1
answer
283
views
If number of points on a manifold is $q^n ( [n+1]_q )$ does it imply a geometric relation to $A^n (P^n)$?
Consider an algebraic manifold whose number of points is $q^n ([n+1]_q)$. Is there a geometric relation to $A^n (P^n)$? In particular, is there an equivalence in the Grothendieck ring of varieties ...
- 24.9k
11
votes
1
answer
1k
views
Pointless groups
This question now has two sequels, Pointless groups II (to which @R.vanDobbendeBruyn gave a counterexample for an infinite, imperfect field) and Pointless groups III, both using revised wording ...
- 12.9k
10
votes
1
answer
807
views
How many Lie and associative algebras over a finite field are there?
This question is related to the following general question:
Given a variety of (non-associative) algebras $\mathcal V$, a finite field $\mathbb{F}_q$, with $q$ elements, and a positive integer $n$, ...
- 398
0
votes
1
answer
242
views
Primes of the form $p=3a^2+3ab+b^2$ or $p=27a^2+27ab+7b^2$ and the number of points of $y^2=x^3+2$ modulo $p$
Trying to generalize this answered question based on limited numerical evidence.
Let $E / \mathbb{F}_p : y^2=x^3+2$.
Conjecture 1 Let $p=3a^2+3ab_0+b_0^2$ be prime and $a,b_0$
positive integers.
...
- 25.4k
22
votes
1
answer
969
views
Grothendieck on polyhedra over finite fields
In Grothendieck's Sketch of a Programme he spends a few pages discussing polyhedra over arbitrary rings and concludes with some intriguing remarks on specializing polyhedra over their "most ...
- 528
21
votes
1
answer
584
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 ...
- 17.9k
19
votes
4
answers
2k
views
Non-split extensions of $GL_n(F_q)$ by $F_q^n$ ?
A very naive question :
I just learned that there is a non-split extension of $GL_3(F_2)$ by $F_2^3$ (with standard action). It can be realized as the subgroup of the automorphism group $G_2$ of ...
- 9,389
18
votes
5
answers
8k
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 ...
- 17.9k
18
votes
2
answers
1k
views
Has anyone seen this construction of the Weil representation of $\mathrm{Sp}_{2k}(\mathbb{F}_p)$?
$\def\FF{\mathbb{F}}\def\CC{\mathbb{C}}\def\QQ{\mathbb{Q}}\def\Sp{\text{Sp}}\def\SL{\text{SL}}\def\GL{\text{GL}}\def\PGL{\text{PGL}}$Let $p$ be an odd prime. The Weil representation is a $p^k$-...
- 156k
16
votes
3
answers
2k
views
Periodic orbits and polynomials
There are two simple and classic enumerations that still I'm puzzled about. Let's start with a simple counting problem from a well-known dynamical system.
fact 1 Consider the "tent map" f:[0,1]→[...
- 60.5k
16
votes
2
answers
1k
views
Examples of problems where considering "discrete analogues" has provided insight or led to a solution of the original problem
The Kakeya conjecture posits that any Kakeya set in $\mathbb{R}^n$ has dimension $n$.
A discrete (finitized?) version of this problem is the Finite Field Kakeya conjecture, which was proved by Dvir ...
14
votes
3
answers
978
views
Zeta function of Abelian variety over finite field
Let $A/\mathbf{F}_q$ be an Abelian variety of dimension $g$. Suppose one knows $|A(\mathbf{F}_{q^n})|$ for all $1 \leq n \leq g$. Does one know then $\zeta(A,s)$ (equivalently, $|A(\mathbf{F}_{q^n})|$ ...
user19475
14
votes
3
answers
3k
views
Quadratic reciprocity and Weil reciprocity theorem
I was told that Weil reciprocity theorem (one has two meromorphic function $f,g$ on a complex curve $C$, so $\prod\limits_{x\in C} g(x)^{ord_xf}=\prod\limits_{x\in C}f(x)^{ord_xg} \ $ where $ord_xf$ ...
- 5,053
14
votes
3
answers
1k
views
Probability of coprime polynomials
Given positive integer $N$, we choose $m_1, m_2, n_1, n_2$ independently and with equal probabilities from $\{0,1,\ldots,N\}$, and let
$f_1 = x^{m_1} + (1+x)^{n_1}$ and $f_2 = x^{m_2} + (1+x)^{n_2}$ ...
- 54.2k
14
votes
2
answers
655
views
Number triangle
This question arose just out of curiosity. Note the triangle of 0-1's below, whose construction is as follows. Choose any number, say 53 as done here. The first line of the triangle is the binary ...
- 1,216
13
votes
1
answer
468
views
Near-linear mappings from $\mathbb F_p$ to $\mathbb R$
$\newcommand{\F}{{\mathbb F}}$
$\newcommand{\R}{{\mathbb R}}$
$\renewcommand{\phi}{\varphi}$
Let $p\ge 5$ be a prime.
If the functions $\phi_1,\phi_2,\phi_3\colon\F_p\to\R$ satisfy $\phi_1(x)+\...
- 23k
12
votes
1
answer
1k
views
Related Forms for the Riemann Hypothesis over Function Fields
There are several formulations and consequences of the Riemann Hypothesis over Function Fields (RH, from now on). I am interested in the logical implications between those, and in proofs\references ...
- 14.6k
11
votes
2
answers
788
views
Blocking sets in three dimensional finite affine spaces
What is the smallest possible size of a set of points in $\mathbb{F}_q^3$ which intersects (blocks) every line?
Clearly the union of three affine hyperplanes that intersect in a singleton, say $x = 0,...
- 1,197
11
votes
2
answers
574
views
Are $E_n$-operads not formal in characteristic not equal to zero?
This is a short question:
Is it just unproven folklore (yet), or is it definitively known that $E_n$-operads are not formal, if the characteristic of the underlying field is not equal to zero?
- 2,074
10
votes
1
answer
561
views
How many rich directions does a set in $\mathbb F_p^2$ determine?
$\newcommand{\F}{\mathbb F}$
A subset $P$ of the affine plane $\F_p^2$ is said to determine a direction if there is a line in this direction containing at least two points of $P$.
A set of size $|P|&...
- 23k
10
votes
2
answers
2k
views
Richardson varieties over finite fields
Let me start with some background to set the notation before I ask my question.
Let G be a semisimple algebraic group over some algebraically closed field K, and suppose we have fixed a Borel ...
- 10.7k
9
votes
1
answer
425
views
Are there functions $\mathbb{F}_2^n \to \mathbb{F}_2$ satisfying these special relations?
Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and let
$u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$. Suppose that $n$ is odd.
Is it possible that
$$
\sum_{x \in \mathbb{F}_2^n}(-1)^{u(x)+u(...
- 6,741
9
votes
2
answers
2k
views
What is an example of a smooth variety over a finite field F_p which does not lift to Z_p?
Somebody answered this question instead of the question here, so I am asking this with the hope that they will cut and paste their solution.
- 10.5k
8
votes
2
answers
5k
views
Algorithms to find irreducible polynomials of a given degree
I need to know what are the efficient algorithms to find all the irreducible polynomials of a given degree, say $d$ over a given finite field, say $\mathbb{F}_{p^n}.$
One way is to factorize the ...
- 1,305
8
votes
0
answers
304
views
A strong sum-product "for translates" in finite fields
In the course of some recent research, I've sketched out a proof of the following result. My basis question is: is the result interesting?
Proposition There exists an absolute constant $c$ such ...
- 11.2k
7
votes
1
answer
812
views
Galois action on $p$-adic Tate module of Abelian variety over finite field semisimple?
Let $A,B$ be positive dimensional Abelian varieties over a finite field and $p$ be an arbritrary prime. By Zarhin, Homomorphisms of abelian varieties over finite fields http://www.math.nyu.edu/~...
user19475
7
votes
2
answers
3k
views
Calculus over finite fields
$P(x,y,z)$ is a polynomial function on an algebraic surface $S$ in $F_{q}^{3}$. Suppose that the derivative of $P$ along any tangent vector of $S$ is zero. Can we say that $P$ is constant on $S$?
...
- 79
7
votes
3
answers
2k
views
Fast Vandermonde matrix multiplication over finite field
Let $V_{i,j}=x_i^j$ where $x_i\in\mathbb F_q$ for $1\le i\le n,1\le j\le n$ be a Vandermonde matrix over finite field $\mathbb F_q$.
I wish to know the currently known fastest algorithms for ...
- 207
7
votes
0
answers
133
views
Removing rows to reduce the rank
What is the smallest number of rows one can delete from a matrix to reduce its rank (by $1$)? Is there any standard name / notation for this characteristic? Has it been studied?
I am in fact ...
- 23k
7
votes
0
answers
276
views
Cyclic shift acting on finite Grassmannian
The (twisted) cyclic shift $(v_1,v_2,\ldots,v_n) \mapsto (v_2,v_3,\ldots,v_n,(-1)^{k-1}v_1)$ acting on the Grassmannian $\mathrm{Gr}(\mathbb{C};k,n)$ of $k$-planes in $\mathbb{C}^n$ is an important ...
- 24.2k
6
votes
1
answer
2k
views
How can I solve a cubic equation in a finite field with characteristic 2?
I need to solve the usual cubic equation $x^3 + ax^2 + bx + c = 0$ over a finite field $GF(2^n)$. This is to avoid doing a brute-force Chien search in a BCH decoder.
I read in a paper about an easy ...
- 87
6
votes
0
answers
342
views
What is known about the $q$-analogue of the simplex?
I am interested in the field with one element. I am thus interested in combinatorial interpretations of the Gaussian binomial coefficients. Richard Stanley's "Enumerative combinatorics" mentions ...
6
votes
1
answer
368
views
Number of points on a linear algebraic group over a finite field
Let $G$ be a linear algebraic group defined over a finite field $\mathbb{F}_q$ as a variety of dimension $d$. What would be a good, simple lower bound for $G(F_q)$?
One can get something fairly nice ...
- 20.2k
6
votes
1
answer
378
views
Enumeration of field generators of a finite field over $\mathbb{F}_{q}$, which are $m^{th}$ powers in the same field
Consider the finite field extension $\mathbb{F}_{{q}^{d}}$ over $\mathbb{F}_{q}$, where $q=p^a$ for some prime $p$. We assume $d\geq 2$. Let,
$$ S=\{ \alpha \in \mathbb{F}_{q^d}\hspace{0.1 cm} | \...
- 428
6
votes
1
answer
331
views
Which criteria for "uniformly splitting" polynomials?
Let $P(x)$ be an irreducible monic polynomial of degree $\ge4$ with integer coefficients. We all know that over a finite field $\mathbb F_p$, $P$ will often split, and I am interested in polynomials ...
- 13.4k
6
votes
3
answers
437
views
On the rank of a matrix $S$ with coefficients in $\mathbb F_{2^m}$
Let $\mathbb F$ be a finite field with characteristic 2 and let $S \in M(2k, 2k, \mathbb F)$ be the matrix defined as follows
$$ S=\left[\begin{array}{ccccccc}
0 & \...
- 307
6
votes
0
answers
652
views
Counting the number of linearly independent primitive elements of a field extension
Let $L/K$ be a field extension with extension degree $n>1$. We say $L/K$ is simple if $L=K(a)$ for some a in $L$. In this case, $a$ is called a primitive element. My question is now about the ...
- 429
6
votes
1
answer
499
views
Do you know which is the minimal local ring that is not isomorphic to its opposite?
The most popular examples are non-local rings and minimal has 16 elements. I am interested in knowing examples of local rings not isomorphic to their opposite.
5
votes
1
answer
459
views
$(n-2)$-blocking sets in $AG(n,2)$
Let's define $k$-blocking set in affine space $AG(n,q)$ a set that meets every coset (translate of subspace) of dimension $k$.
I have seen a lot work related to minimal $(n-1)$-blockings set.
...
- 337
5
votes
1
answer
432
views
Image of a polynomial function $x^2+y^2-x+y-axy$ over $\mathbb{F}_p$
Let $p$ be an odd prime and $h(x)=x^2+ax+1$ be an irreducible polynomial over the field $\mathbb{F}_p$. I need to prove that the function
$$\Psi: \mathbb{F}_p^2 \longrightarrow \mathbb{F}_p, \quad (x,...
- 457
5
votes
1
answer
432
views
Number of roots of a quadratic form over GF(2)
If $Q(x) = x^T A x$ with $x \in GF(2)^n$ and $A \in GF(2)^{n \times n}$, is there a way to find how many roots $Q(x)$ has based on any properties of $A$ (e.g., rank, etc.)?
- 63
5
votes
1
answer
993
views
Full-rank rectangular matrices over GF(2)
Given positive integers $k$, $m$, $n$, let $A$ be an $m \times n$ matrix over $GF(2)$ constructed as follows. Let $X_1, \ldots, X_m$ be independent random subsets of $\{1,\ldots,n\}$ with cardinality ...
- 54.2k