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
1 vote
0 answers
57 views

Solving efficiently a quadratic equation in a large finite field of characteristic two

I'm trying to solve efficiently a quadratic equation in the finite field $\text{GF}(2^{128})$ represented as $(\mathbb{Z}/2\mathbb{Z})[x] / (x^{128} + x^7 + x^2 + x + 1)$. Until now, I came across ...
3 votes
0 answers
73 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 ...
1 vote
0 answers
244 views

Reductions of a system of equations at various primes

Let $f_1, \dots, f_n$ be a finite set of polynomials in the polynomial ring $Z[x_1, \dots, x_m]$. At a prime $p$, let $N_p$ be the number of solutions $x=(x_1, \dots, x_m)\in (\mathbb{Z}/p\mathbb{Z})^...
4 votes
1 answer
191 views

Intersection of the general linear group $\text{GL}_n(\mathbb{F}_q)$ and an affine subspace over a finite field

Let $\mathbb{F}_q$ be a finite field of $q$ elements, let $\text{M}_n(\mathbb{F}_q)$ be the vector space of $n \times n$ matrices over $\mathbb{F}_q$, let $\text{GL}_n(\mathbb{F}_q)$ be the group of $...
  • 43
17 votes
2 answers
597 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$-...
6 votes
0 answers
197 views

Cardinality of a polynomial image $\pmod{p^n}$

Given $P(x) \in \mathbb{Z}[x]$ a polynomial, $n$ a positive integer and $p$ a prime, there is a result that relates $|\text{Im } P \pmod{p^n}|$ with $|\text{Im } P \pmod{p^{n+1}}|$ perhaps in terms of ...
  • 61
0 votes
0 answers
87 views

Representing an $m$ dimensional quadratic polynomial as a polynomial on $\mathbb F_{q^m}$

We can represent $\mathbb{F}_{q^m}$ as $\mathbb{F}_q[\alpha]$ where $\alpha$ is root of an irreducible $m$-degree polynomial on $\mathbb{F}_q$. By sending $\sum_{i=0}^{m-1} c_i\alpha^i \mapsto (c_{m-1}...
  • 1
5 votes
1 answer
258 views

How to make Burnside's formula compatible with point counting for varieties over finite fields?

If $G$ is a finite group acting on a finite set $X$, we have Burnside's formula that counts the number of orbits $|X/G|$ as: $$ |X/G| = \frac1{|G|} \sum_{g\in G} |X^g|, $$ with $X^g$ being the set of ...
0 votes
1 answer
164 views

Product of subspace and its inverse

$\DeclareMathOperator\GF{GF}$Let $R=\GF(q)$ be a finite field with $q=p^r$ elements, where $p$ is a prime number, $S=\GF(q^n)$ be an extension of $R$, where $n\in \mathbb{N}$, $n\geq 2$ and let $K=\GF(...
7 votes
2 answers
302 views

Sum of two $n$th powers in finite fields

Let $q$ be a prime power, let $n$ be a positive integer and let $\mathbb{F}_q$ be the finite field of cardinality $q$. I have some computational evidence that the set $$\{x^n+(-1)^nay^n:x,y\in\mathbb{...
0 votes
0 answers
151 views

How many elements have a "small" order in a finite field?

I'm hoping that this is an easy question for someone. How many elements can we expect to have multiplicative order at most $n^{1/c}$ in one of the finite fields $\mathbb{F}_p$ with $p$ prime with $n \...
0 votes
0 answers
81 views

number of solutions of system of equation over finite finite fields

Let p>5 is a prime $$\mathop{\sum_{a=1}^{p}\sum_{b=1}^{p}\sum_{c=1}^{p}\sum_{d=1}^{p}}_{\substack{a+b+c+d+1\equiv0(mod p)\\a^3+b^3+c^3+d^3+1\equiv(mod p)}}1$$ I find the this system of equation ...
4 votes
0 answers
113 views

Statistics about existence of rational points on a curve over $\mathbb{F}_q$

I wish to ask the naive question: if we write down a random curve $C$ over $\mathbb{F}_q$, what can be said about the probability that $C(\mathbb{F}_q)=\emptyset$? Of course, this depends on the ...
6 votes
0 answers
164 views

Number of square-free polynomials over a finite field - a combinatorial interpretation?

Cross-posted from MSE. The question has remained unanswered for six years but I still like it! One can show using zeta functions that the number of (monic)square-free polynomials of degree $n$ over a ...
  • 7,142
1 vote
0 answers
51 views

Constructing k-wise independent variables over a general set

We have seen in class a polynomials based construction that builds in $O(n^k)$ time, $n$ random variables, $k$-wise independent, over a field with $n$ elements. More specifically, you generate all the ...
  • 11
2 votes
0 answers
72 views

Maximal subsets of affine or projective space with no three collinear points

Let ${\mathbb A}^n_q$ and ${\mathbb P}^n_q$ be affine and projective spaces of dimension $n$ over a field of order $q$. Say that a subset of either ${\mathbb A}^n_q$ or ${\mathbb P}^n_q$ is generic if ...
0 votes
1 answer
52 views

Enumerating (i.e. generating one by one) matrices of given rank over a finite field

Let be given positive integers $m,n,r$, with $r \leq \min(m, n)$, and a finite field of $q$ elements $\mathbb{F}_q$. I'm looking for an efficient algorithm to enumerate (i.e., generate one by one) all ...
  • 43
3 votes
0 answers
84 views

Visiting zero-sum triples in a vector space

Is it true that for any set $A\subset\mathbb F_5^n$ satisfying $A\cap(-A)=\varnothing$, there is a subset $A'\subseteq A$ such any triple $(a,b,c)\in A\times A\times A$ with $a+b+c=0$ has exactly one ...
  • 21.8k
3 votes
1 answer
153 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,512
4 votes
0 answers
117 views

7D simple Lie algebras over $\mathbb{F}_3$

Up to isomorphism, what are all the seven-dimensional simple Lie algebras over the field with three elements?
11 votes
2 answers
1k views

Algebraic geometry over the complex numbers, and beyond

My question basically is very simple: when did mathematicians start to do algebraic geometry "outside the complex numbers" ? In the old days, algebraic geometry was solely done over the ...
  • 3,649
8 votes
1 answer
268 views

The distribution of certain Galois groups

Let $f(x)$ be a polynomial of degree $d$ with integer coefficients. Let $G_p^+$ be the Galois group of the polynomial $f(x)-y$ over $\overline{\mathbb{F}}_p(y)$ and $G_p$ be the Galois group of the ...
2 votes
2 answers
200 views

Sum over exponentiated bilinear form in finite-field vector space

Let $A$ be a linear map over the finite-field vector space $(\mathbb F_2)^n$, i.e., an $\mathbb F_2$-valued $n\times n$ matrix, not necessarily symmetric. I'm interested in the sum $$Z(A) = \sum_{X\...
  • 2,699
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 ...
  • 9,077
3 votes
0 answers
70 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
1 vote
0 answers
114 views

Counting non-zero Gramians of Grassmanians over finite field

In case of $\mathbb{F}_{2}$, we can obtain the number of all reduced row echelon forms (so called Grassmannians) for some m$\times$n full rank matrices by the following gaussian polynomial, $$ \binom{...
  • 11
3 votes
0 answers
75 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,142
0 votes
0 answers
83 views

Invertible matrices with bounded nonnegative coefficients

I am teaching a class in linear algebra and I asked myself the following question: what is the chance to get an invertible matrix if I write a random one? My impulsive answer is "very likely"...
1 vote
0 answers
83 views

How to show the minimal polynomial of primitive n-th root of unity on prime field with characteristic p is the following? [closed]

How to show : w, the primitive n-th root of unity over prime field F with characteristic p, gcd(n,p)=1, is $(x-w)(x-w^p)(x-w^{p^2})...(x-w^{p^{r-1}})$ where r is the smallest positive integer s.t. $p^...
  • 11
2 votes
4 answers
429 views

How to prove that a quaternion algebra over ℤₚ is isomorphic to Mat₂(ℤₚ) for p prime?

How to prove without using advanced theorems that quaternions algebra $H = \genfrac(){}{}{-1,-1}{\mathbb{Z}_p}$, where $p$ is prime that $H \cong\operatorname{Mat}_2({\mathbb{Z}_p})$? My ideas: I ...
1 vote
1 answer
146 views

Known estimate for gaussian sum $\sum_{x \in \mathbb{F}_q} \psi( a x^m + b x^n)$?

Let $\mathbb{F}_q$ be a finite field, $\psi$ be a non-trivial additive character over $\mathbb{F}_q$, and $a, b \in \mathbb{F}_q$ constants. Is there any known estimate for the gaussian sum $$\sum_{x \...
  • 177
1 vote
1 answer
179 views

A "semi-genetic" definition of addition and multiplication in the field $\operatorname{On}_p$?

Let $+,\cdot$ denote multiplication in $\mathbb{N}_0$. The addition and multiplication in $\operatorname{On}_p$ are denoted $\oplus, \otimes$. Recursive definition of addition: $$x \oplus y := ((x+y) \...
3 votes
0 answers
120 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 (...
0 votes
0 answers
55 views

A matrix of character and trace

Let $q$ be a prime power. Let $g$ be a multiplicative generator of $F_{q^2}$, the finite field with $q^2$ elements. Assume that $l$ is a fairly large prime ($>q^4$) dividing $q^{2(q-1)}-1$. Let $\...
  • 503
1 vote
1 answer
95 views

Order of roots for a polynomial $P\in\mathbb{F}_p[T]$

Let $P\in\mathbb{F}_p[T]$ (not supposed irreducible). All roots $\xi$ of $P$ have a certain order $k$ such that $\xi^k=1$. Question: is it possible to know the order of the roots of the given ...
4 votes
1 answer
177 views

Discrete logarithms and primitive elements in finite fields

The recent papers: R. Granger, T. Kleinjung, J. Zumbragel, "On the Discrete Logarithm Problem in Finite Fields of Fixed Characteristic," Trans. Amer. Math. Soc., 370(5) (2018), 3129–3145. T....
  • 425
2 votes
0 answers
106 views

When $\gcd(P(x),Q(x))\bmod R(x)=\gcd(P(x) \bmod R(x),Q(x) \bmod R(x))$?

Let's $P,Q\in\mathbb K[x]$, with $\mathbb K$ a finite field. On what necessary and sufficient condition on $R \in \mathbb K[x]$ is it : $\gcd(P(x),Q(x))\bmod R(x)=\gcd(P(x) \bmod R(x),Q(x) \bmod R(x))...
  • 3,225
1 vote
1 answer
79 views

infinite many multiples of a polynomial in $\mathbb F_q[T]$

Let $P$ be an irreducible polynomial of $\mathbb F_q[T]$, $(u_n)_n$ be an infinite sequence of distinct elements of $\mathbb N_0$. Does there exist infinitely many multiples of $P$ in $\mathrm{Vect}_{\...
  • 3,091
4 votes
1 answer
150 views

Bound for sum of multiplicative character calculated over multivariate polynomial

Let $f \in \mathbb{F}_q[x_1, \dots, x_k]$ be a polynomial with $\deg f = n$, and let $\chi$ be a multiplicative character over $\mathbb{F}_q$. Is there any known bound, possibly with conditions about $...
  • 177
5 votes
1 answer
262 views

About closed points in symmetric product schemes over a finite field

Let $k=\mathbb{F}_q$ be a finite field with $q$ elements and let $X$ be a quasi-projective $k$-scheme. I saw somewhere claims the following results (without explanation): Let $N$ be a positive ...
  • 1,624
8 votes
2 answers
359 views

Zero trace elements in finite fields

There is so much literature on the relation between the multiplicative structure of a finite field and elements having zero trace, that I am hoping that the following is known. Let $q$ be a prime ...
3 votes
1 answer
239 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 ...
1 vote
1 answer
91 views

Distribution of weight of special type of random-matrix vector product?

Let $G$ be a matrix of dimension $k \times n$ sampled uniformly randomly from $F_2^{k \times n}$. It is a well known fact that $y = xG$ is uniformly distributed in $F_2^n - \{0\}$ for all $x \in F_2^k$...
4 votes
1 answer
163 views

Order of a rational function on $\mathbb{F}_p$

Let $a$ be an element of $\mathbb{F}_p$, which is not a quadratic residue. Define $$f(x) = \frac{x + a}{x+1},$$ which is a rational function on $\mathbb{F}_p$. In fact, if we set $f(-1)=\infty$ and $f(...
10 votes
2 answers
712 views

The maximal subset of a finite field where the sum of any subset is non-zero

Given a finite field $\mathbb{F}_q$ with $q=p^m$ where $p$ is the characteristic. For any subset $S=\{a_1,\dots,a_n\}$ of $\mathbb{F}_q$, if any partial sum (i.e. the sum of elements in a non-empty ...
  • 377
4 votes
1 answer
234 views

Can we explicitly compute this "shift"-quantity over Boolean functions $u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$?

This question is a follow-up of this question. Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and suppose that $n$ is odd. Question: Can we compute the exact minimum $$A:= \min_{u:\mathbb{...
  • 6,397
9 votes
1 answer
345 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,397
4 votes
2 answers
458 views

Smoothness of fibers over finite fields

Let $f:X\rightarrow Y$ be a morphism of smooth projective varieties over a finite field of characteristic different from $2$. Is there any result on the existence of a point $y\in Y$ such that $X_y = ...
user avatar
8 votes
0 answers
335 views

Who realized the finite fields $\mathbb F_{p^n}$ first? Gauss or Galois?

Let $p$ be a prime, and let $n$ be a positive integer. The finite field $\mathbb F_{p^n}$ is often called a Galois field and denoted by $\mathrm{GF}(p^n)$ by researchers on coding theory. On the other ...
  • 13.3k
3 votes
1 answer
268 views

Smooth surfaces in positive characteristic

Let $K = \mathbb{F}_p$ be a field of positive characteristic $p > 0$. Consider a surface in $\mathbb{A}^3_K$ of the following form $$ S = \{f_1(x_0)y_0^2+f_2(x_0)y_0y_1+f_3(x_0)y_0+f_4(x_0)y_1^2+...
user avatar

1
2 3 4 5
15