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.

Filter by
Sorted by
Tagged with
13
votes
2answers
854 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
6answers
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,(...
53
votes
14answers
14k 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
9answers
4k 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. ...
20
votes
4answers
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$...
21
votes
1answer
3k 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 ...
18
votes
1answer
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+...
6
votes
1answer
238 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 ...
15
votes
5answers
1k 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. ...
10
votes
1answer
630 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$, ...
0
votes
1answer
227 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. ...
12
votes
3answers
2k 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$ ...
19
votes
4answers
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
votes
2answers
1k 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.
16
votes
3answers
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]→[...
14
votes
3answers
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}$ ...
16
votes
2answers
968 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 ...
13
votes
2answers
498 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 ...
11
votes
2answers
591 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,...
14
votes
3answers
841 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})|$ ...
9
votes
1answer
725 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 ...
7
votes
2answers
4k 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 ...
7
votes
0answers
84 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 ...
7
votes
0answers
231 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 ...
6
votes
1answer
508 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/~...
6
votes
2answers
2k 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$? ...
6
votes
1answer
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 ...
4
votes
2answers
620 views

Pointless, non-singular, absolutely irreducible affine plane curves over finite fields

We think the following is true: For all sufficiently large primes $p$ and all natural $g \ge 1$, there exists affine plane curve $f(x,y)=0$ over $\mathbb{F}_p$ which is non-singular, absolutely ...
2
votes
0answers
329 views

Enumerating certain types of permutation polynomials

Given a prime power $q$, I would like to enumerate (preferably up to isomorphism*) all the permutation polynomials $f(x)$ on $K = GF(q^3)$ satisfying the following conditions: $f(ax) = af(x)$ for all ...
17
votes
0answers
277 views
+500

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 ...
11
votes
2answers
484 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?
10
votes
1answer
474 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|&...
6
votes
0answers
282 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
1answer
366 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. ...
4
votes
1answer
165 views

$\#E(\mathbb{F}_p) \in \{p,p+2\}$ iff $p$ is of the form $27a^2+27a+7$

Related to this question. Let $E / \mathbb{F}_p : y^2=x^3+2$. Numerical evidence up to $2 \cdot 10^5$ suggests: Conjecture: $\#E(\mathbb{F}_p) \in \{p,p+2\}$ iff $p$ is of the form $27a^2+27a+7$ ...
4
votes
0answers
222 views

Polynomial equations in many variables have solutions (Lang 1952 paper)

I am trying to understand the proof of the following result: Suppose $F$ is a function field in $k$ variables over an algebraically closed field. Let $f_1,...,f_r \in F[x_1,...,x_n]$ be ...
3
votes
3answers
1k views

how to generate the n-torsion group

Hello, I was curious about the following sentence: "then the $n$-torsion on $E(\overline{K})$ has known structure, as a Cartesian product of two cyclic groups of order $n$" (found at http://en....
13
votes
1answer
406 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)+\...
8
votes
0answers
293 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 ...
6
votes
1answer
243 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 ...
5
votes
1answer
276 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,...
5
votes
1answer
767 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 ...
4
votes
1answer
258 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 ...
3
votes
2answers
215 views

Largest $A\subset \mathbb{F}_2^n$ such that no two $a\neq b$ in $A$ add to an element of $A.$

If such a set $A$ of size $m$ exists, all its admissible pairwise sums must lie in its complement, thus $$ \binom{m}{2} \leq 2^n-m, $$ which gives $$m\leq 2^{(n+1)/2}\qquad (1)$$. Edit: The upper ...
1
vote
1answer
832 views

maximal number of mutually orthogonal vectors

Let $F$ be a field, $n$ be a positive integer. Denote by $h_{F}(n)$ the maximal dimension of a subspace $X\subset F^n$ such that $(x,y)=0$ for any two (not necessary distinct) vectors $x,y\in F^n$, ...
0
votes
1answer
1k views

Chains of numbers generated by 2 involutions

$\DeclareMathOperator\GF{GF}$Consider the finite field $\GF(p)$ for prime $p$. Consider the pair of involutions $f(x) = 1-x$ , $g(x) = 1/x$, and the chain of numbers generated by these 2 involutions ...
6
votes
1answer
292 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} | \...
6
votes
3answers
386 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 & \...
6
votes
0answers
527 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 ...
5
votes
1answer
426 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: ...