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
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 ...
56
votes
0
answers
3k
views
Uniformization over finite fields?
The following is a question I've been asking people on and off for a few years, mostly out of idle curiosity, though I think it's pretty interesting. Since I've made more or less no progress, I ...
- 23k
47
votes
3
answers
3k
views
A curious identity related to finite fields
To three elements $a_1$, $a_2$, $a_3$ in the finite field $\mathbb F_q$
of $q$ elements we associate the number $N(a_1,a_2,a_3)$
of elements $a_0\in \mathbb F_q$ such that the polynomial
$x^4+a_3x^3+...
- 17.9k
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
29
votes
0
answers
2k
views
A modern perspective on the relationship between Drinfeld modules and shtukas
Shtukas were defined by Drinfeld as a generalization of Drinfeld modules. While the relationship between the definitions of Drinfeld modules and shtukas is not obvious, one does have a natural ...
- 148k
28
votes
1
answer
2k
views
How does Tate verify his own conjecture for the Fermat hypersurface?
This question is about Tate's 1963 paper "Algebraic Cycles and Poles of Zeta Functions". Here he announces a conjecture (now known as "the Tate conjecture") which states that certain classes in the ...
- 4,487
28
votes
2
answers
2k
views
Does the etale fundamental group of the projective line minus a finite number of points over a finite field depend on the points?
Clearly the etale fundamental group of $\mathbb{P}^1_{\mathbb{C}} \setminus \{a_1,...,a_r\}$ doesn't depend on the $a_i$'s, because it is the profinite completion of the topological fundamental group. ...
- 5,929
28
votes
1
answer
1k
views
Algebraic dependency over $\mathbb{F}_{2}$
Let $f_{1},f_{2},\ldots,f_{n}$ be $n$ polynomials in $\mathbb{F}_{2}[x_{1},x_{2},\ldots,x_{n}]$
such that $\forall a=(a_1,a_2,\ldots,a_n)\in\mathbb{F}_{2}^{n}$ we have $\forall i\in[n]:f_{i}(a)=a_{i}$....
- 583
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
23
votes
1
answer
1k
views
Is hyperelliptic cryptography "practical"?
Previosly my impression on this subject was that hyperelliptic cryptography systems (as well as other possible cryptosystems based on abelian varieties of dimension $>1$) have no advantages over ...
- 16.9k
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
22
votes
3
answers
813
views
A hypersurface with many points
Ok, it's time for me to ask my first question on MO.
Consider the affine curve $Y+Y^q=X^{q+1}$ over the finite field $\mathbf{F}_q$. It's interesting because it has the largest number of points over ...
- 4,487
22
votes
1
answer
970
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
20
votes
2
answers
2k
views
Sums of powers mod p
For prime $p > 7$ with $p-1=rs$, $r>1$, $s>1$, let $A=\{x^r|x \in \mathbb{Z}_p\}$ and $B = \{x^s|x \in \mathbb{Z}_p\}$. If $g$ is a primitive root mod $p$ then $A = \{0\} \cup \{g^{ir}|0 \leq ...
- 619
19
votes
3
answers
2k
views
The period of Fibonacci numbers over finite fields
I stumbled upon these very nice looking notes by Brian Lawrence on the period of the Fibonacci numbers over finite fields. In them, he shows that the period of the Fibonacci sequence over $\mathbb{F}...
- 423
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
19
votes
3
answers
2k
views
Classification of rings satisfying $a^4=a$
We have the famous classification of rings satisfying $a^2=a$ (for each element $a$) in terms of Stone spaces, via $X \mapsto C(X,\mathbb{F}_2)$. Similarly, rings satisfying $a^3=a$ are classified by ...
- 63.1k
19
votes
1
answer
419
views
Varieties with the same number of $\mathbb{F}_p$-points for all but finitely many primes
If two varieties over $\mathbb{Q}$ have the same number of $\mathbb{F}_p$-points for all but finitely many primes do they have the same number of $\mathbb{F}_{p^n}$-points for all $n>1$ and for all ...
- 325
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
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
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
17
votes
4
answers
1k
views
A mixing property for finite fields of characteristic $2$
In connection with this MO post, here is a question somewhat implicitly contained in a joint paper of S. Kopparty, S. Saraf, M. Sudan, and myself.
Let ${\mathbb F}$ be a finite field, and suppose ...
- 23k
17
votes
1
answer
381
views
Do mutually dual finite vector spaces have the same orbit cardinalities under a linear group action?
Let $G$ be a finite group acting linearly on a finite dimensional vector space $V$ over a finite field. By Burnside's lemma,
$$
|V/G| = \frac 1{|G|} \sum_{g\in G} q^{\dim(ker(g - I))}.
$$
Since $g-I$ ...
- 5,654
17
votes
0
answers
750
views
Elements of finite fields with many powers of trace zero
Let $p$ be an odd prime number, $n>1$ be an integer, and $\mathrm{tr}$ be the trace map of the field extension $\mathrm{GF}(p^{2n})/\mathrm{GF}(p)$. For which pair $(p,n)$ does there exists $x\in\...
- 767
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 ...
16
votes
1
answer
3k
views
How do I see the equality $57 = 3 \times 19$ geometrically?
Consider the finite field ${\bf F}_p$ and its cubic extension ${\bf F}_{p^3}$. The multiplicative group ${\bf G}_m({\bf F}_{p^3})$ contains the multiplicative group ${\bf G}_m({\bf F}_p) \cong {\bf Z}/...
- 364
15
votes
2
answers
1k
views
Can you use Chevalley‒Warning to prove existence of a solution?
Recall the Chevalley‒Warning theorem:
Theorem. Let $f_1, \ldots, f_r \in \mathbb F_q[x_1,\ldots,x_n]$ be polynomials of degrees $d_1, \ldots, d_r$. If
$$d_1 + \ldots + d_r < n,$$
then the ...
- 28.7k
15
votes
2
answers
951
views
Does $\mathbb{K}[G]\simeq\mathbb{K}[H]$ for some field $\mathbb{K}$ of characteristic $p$, imply $\mathbb{F}_p[G]\simeq\mathbb{F}_p[H]$?
Due to the first (and very helpful) answer I received, I've reformulated the question a little: $G$ and $H$ are now assumed to be $p$-groups.
Let $p$ be a prime, and let $\mathbb{F}_p$ be the field ...
- 151
15
votes
1
answer
4k
views
Order of finite unitary group
This may be an easy exercise but I am not getting it. Let $\mathbf F_q$ be a finite field with $q$ elements and $\mathbf F_{q^2}$ be its degree two extension. Define an automorphism $\sigma$ of $\...
- 899
15
votes
0
answers
500
views
Do we expect abelian varieties (and “Artin motives”) to generate the Grothendieck ring of varieties over a finite field?
The Tate conjecture implies that the category of motives over a finite field is generated (as tensor category) by the motives of abelian varieties and Artin motives. See [1] for details.
Let $K(\...
- 5,504
15
votes
0
answers
427
views
Counting abelian varieties over finite fields in a given isogeny class
Let $f(x) \in \mathbb Z[x]$ be a monic polynomial of degree $g$ with all roots having absolute value $\sqrt{q}$. How many principally polarized abelian varieties over $\mathbb F_q$ have $f(x)$ as the ...
- 148k
14
votes
3
answers
3k
views
Truncated Exponential Series Modulo $p$: Deeper meaning for a Putnam Question.
Apparently B6 of the Putnam this year asked:
Suppose $p$ is an odd prime. Prove that for $n\in \{0,1,2...p-1\}$, at least $\frac{p+1}{2}$ of the numbers $\sum^{p-1}_{k=0} k! n^{k}$ are not divisble ...
- 11.4k
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,063
14
votes
3
answers
1k
views
A question on representation of graphs
Take a complete graph $K_n$. You want to assign a vectors from $\Bbb F_2^d$ to every edge such that sum of vectors in every simple cycle does not sum to $0$ vector. The question is what is minimum $d$ ...
- 13.9k
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
3
answers
2k
views
Collatz-like properties of finite fields
I was wondering what an equivalent of the Collatz conjecture might be for finite fields. In a Collatz sequence a number is moved down within a set $\{2^k n : k \in \mathbb{Z}^* \}$ for some odd $n$ or ...
- 261
14
votes
4
answers
5k
views
Books on advanced galois theory
I have been studying galois theory on my own and find it very fascinating. I have gone through Ian Stewarts book: http://www.amazon.co.uk/Galois-Theory-Third-Chapman-Mathematics/dp/1584883936. I am ...
- 141
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
1
answer
790
views
Noether-Deuring for injections and surjections?
Noether-Deuring theorem (not in the strongest form, but in the one I usually need):
Let $L\diagup K$ be a field extension. Let $A$ be a $K$-algebra which is finite-dimensional as a vector space over $...
- 33.8k
14
votes
1
answer
285
views
Lower bounds for class number of function fields with fixed $q$, growing $g$
Let $X$ be a smooth project curve of genus $g$ over the finite field with $q$ elements. Let $h$ be $\# \mathrm{Pic}^0(X)(\mathbb{F}_q)$. Weil showed that $h \geq (\sqrt{q}-1)^{2g}$. Lachaud and Martin-...
- 156k
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
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
13
votes
2
answers
950
views
Is there an $\mathbb{R}$-valued cohomology theory for varieties over $\mathbb{F}_p$?
If $E$ is a supersingular elliptic curve over $\mathbb{F}_{p^m}$ with $m\geq 2$ its endomorphism ring is a maximal order in a quaternion algebra ramified at $p$ and $\infty$ so there can't be a Weil ...
user158636
13
votes
2
answers
1k
views
An expander (?) graph
For a prime $p$, consider the graph on the vertex set ${\mathbb F}_p$, in
which every vertex $z$ is adjacent to $z\pm 1$ and also to $z^{-1}$ (unless
$z=0$). I was told that this graph is known to be ...
- 23k
13
votes
2
answers
866
views
Isomorphism of varieties in $\mathbb{C}$ implies isomorphism over finite fields
Suppose that $X$ and $Y$ are algebraic varieties over $\mathbb{Z}$ (add your favourite hypotheses, like smooth or affine if needed). Denote by $X_k$ and $Y_k$ their base-change to varieties over a ...
- 507
13
votes
4
answers
5k
views
Orthogonal Groups over finite fields
Hello
Let $\mathbb{F}_p$ be the finite field with $p$ elements. One can show that over finite fields, there are just two non-degenerate quadratic forms.
So here I want to pick
any non-degenerate ...
- 2,508