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.
80
questions
13
votes
2
answers
978
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 ...
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,(...
- 28.7k
56
votes
14
answers
20k
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.
...
- 225k
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$...
- 115k
21
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 ...
- 211
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+...
- 24.2k
17
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. ...
- 287
6
votes
1
answer
277
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 ...
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 ...
- 11.4k
10
votes
1
answer
790
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
238
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.
...
- 24.2k
21
votes
1
answer
571
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.4k
19
votes
4
answers
1k
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,349
18
votes
2
answers
928
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$-...
- 151k
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 ...
- 17.4k
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 ...
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]→[...
- 56.6k
14
votes
3
answers
962
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
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}$ ...
- 53.6k
13
votes
2
answers
627
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,196
13
votes
1
answer
455
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)+\...
- 22.8k
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 ...
- 13.4k
12
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$ ...
- 4,761
11
votes
2
answers
774
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,167
11
votes
2
answers
548
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,014
10
votes
2
answers
1k
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.2k
10
votes
1
answer
546
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|&...
- 22.8k
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.3k
9
votes
1
answer
408
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,621
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
299
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
0
answers
260
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 ...
- 22.9k
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
124
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 ...
- 22.8k
7
votes
1
answer
768
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
6
votes
1
answer
368
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} | \...
- 430
6
votes
1
answer
307
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 ...
- 19.3k
6
votes
3
answers
420
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
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
1
answer
301
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.2k
6
votes
1
answer
492
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.
6
votes
0
answers
635
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 ...
- 433
6
votes
0
answers
329
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 ...
5
votes
1
answer
328
views
Large gaps in Singer planar difference sets?
By a classical result of Singer (1938), for a prime number $p$ the cyclic group $C_n$ of order $n=1+p+p^2$ contains a subset $D$ of cardinality $|D|=1+p$ such that $DD^{-1}=C_n$. Such set $D$ is ...
- 40.9k
5
votes
1
answer
955
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 ...
- 53.6k
5
votes
1
answer
445
views
More expanders?
Having received several exhausting answers to my recent question about
the expansion properties of a certain graph, I now wonder whether anything is
known on the following graphs of a similar nature:
...
- 22.8k
5
votes
1
answer
400
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
451
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