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.
62 questions from the last 365 days
1
vote
0
answers
70
views
Quadratic forms with the same roots over GF(2) for low rank problems
Let $Q_1(x)=x^TA_1x$ and $Q_2(x)=x^TA_2x$ with $x\in GF(2)^n$, $A_i\in GF(2)^{n\times n}, i \in \{1, 2\}$. If $rank(A_1)=rank(A_2)=2$, is it possible that $Q_1(x)$ and $Q_2(x)$ can have the same roots ...
- 63
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
4
votes
0
answers
108
views
Differential duality: Triangular codes vs. VT codes / Single-substitution vs. Single-deletion
Here is the introduction to my problem:
Codes correcting single-deletion. Let $q$ and $n$ be non-negative integers, and let $\mathbf{x}= \left ( x_{1}, x_{2}, \ldots, x_{n} \right )\in\mathbb{Z}_{q}^{...
- 41
0
votes
0
answers
80
views
Solution modulo $9$ of certain linear equation implies triviality modulo $3$
Question: Let $k \geq 2$ and $r \geq 4$ be two natural numbers. We are given eight integers $\nu_{ij} \geq 0$ for every $1 \leq i \leq k$ and $1 \leq j \leq r$ such that the following two conditions ...
- 119
-1
votes
0
answers
73
views
Why is there in theory no morphism/isogenies when enlarging a prime field sharing a common suborder/subgroup? [closed]
Simple question : I have a prime field having modulus $p$ where $p−1$ contains $O$ as prime factor, and I have a larger prime field $q$ also having $O$ as its suborder/subgroup. Why are there no ...
- 87
7
votes
0
answers
139
views
Average number of $\mathbb{F}_p$-points over twists of a variety
Let $p \gg 1$ be a sufficiently large prime. I recently stumbled across a fascinating fact about the number of $\mathbb{F}_p$-points on elliptic curves over finite fields. Specifically, we have:
Fact ...
1
vote
1
answer
64
views
Dual of blocking sets in finite geometry
Let $V$ be an $n$-dimensional vector space over the finite field of cardinality $q$ and let $W_1,\ldots,W_m$ be hyperplanes of $V$ such that
$$V=\bigcup_{i=1}^mW_i \,\,\hbox{ and }\,\,0=\bigcap_{i=...
- 934
2
votes
1
answer
188
views
Uniqueness of differences of roots of polynomials over finite field
Let $f$ be a polynomial over a finite field $\mathbf{F}_p$ with $p \neq 2$. Let $R$ be the roots of $f$ in some extension field. I am interested in the multiset of differences $R - R = \{ r - s \mid r,...
- 309
11
votes
2
answers
387
views
Bounds for the difference in the number of ones in $M$ and $M^{-1}$
If $M$ is a full rank $n$ by $n$ binary matrix over $\mathbb{F}_2$, how much larger or smaller can the number of $1$s in $M^{-1}$ be, compared to the number of $1$s in $M$?
Clearly the identity matrix ...
- 3,377
4
votes
1
answer
244
views
Distinct eigenvalues of random matrix over finite field
Let $A$ be a uniformly random matrix in $\mathrm{M}_n(\mathbf{F}_p)$.
It is well known that, as $p$ is fixed and $n$ tends to infinity, $A$ has repeated eigenvalues (over the algebraic closure $\...
- 309
8
votes
1
answer
366
views
Why do we have fewer distinct Gauss sums over a field of characteristic $2$?
Let $p$ be a prime number and $q$ be a power of $p$. Fix a non-trivial additive character $\psi\colon \mathbb{F}_q\to \mathbb{C}^\times$ and, for each non-trivial multiplicative character $\chi\colon \...
- 711
2
votes
0
answers
167
views
Centralizer of PSL in PGL and of SL in GL: reference request
$\DeclareMathOperator\GL{GL}\DeclareMathOperator\SL{SL}\DeclareMathOperator\PGL{PGL}\DeclareMathOperator\PSL{PSL}$Consider the general linear group $\GL(n,q)$ over a finite field with $q$ elements and ...
- 361
0
votes
1
answer
95
views
Number of points of Fermat surfaces $X^n + Y^n - U^n - V^n = 0$
Let $n$ be a positive integer such that $n^2 + n + 1$ is a prime, and consider the Fermat surface $F$ given by the equation $X^n + Y^n - U^n - V^n = 0$ (where we work with homogeneous coordinates $(x :...
- 4,547
3
votes
2
answers
303
views
Asymptotics of A000613
The general linear group $GL_n(\mathbb{F}_2)$ acts on the powerset $2^{{\mathbb{F}_2}^n \setminus \{0\}}$ by multiplication: $A \cdot S := \{Ax \in {\mathbb{F}_2}^n : \, x \in S\}$, for an invertible ...
- 331
1
vote
0
answers
92
views
Counting conjugacy classes of completely reducible subgroups in general linear groups [closed]
Let $G = GL(n, q)$ be the general linear group over the finite field $\mathbb{F}_q$ with $q$ elements, where $q$ is a power of a prime $p$. Let $m$ be a positive integer dividing $q-1$. Suppose $\...
1
vote
0
answers
88
views
Ramanujan graph element in $\mathsf{PSL}(2, \mathbb{Z}_q)$
I am trying to follow the construction of the Ramanujan graph $X^{p, q}$ given in the paper 1. The first few steps of the construction proceed as follows:
Let $p$, $q$ be two unequal primes that are ...
- 333
2
votes
0
answers
120
views
Looking at versions of Implicit Function Theorem (IFT) on rings
$ \let \ovr \overline
\def \Z {\mathbb Z}
\def \C {\mathbb C}
\def \F {\mathbb F}
\def \P {\mathcal P}
\def \x {\boldsymbol x}
\def \a {\boldsymbol a} $
Let $ \P = \{ p _ i ( \x , y ) \} _ { i = 1 } ^ ...
- 346
0
votes
0
answers
122
views
Is it in theory possible to create a subexponential algorithm for solving discrete logarithms in multiplicative subgroups or within an Integer range?
As far I understand, when it comes to finite fields, Pollard rho and Pollard’s lambda are still the best algorithm for solving discrete logarithms in a multiplicative subgroup/suborder…
Index calculus ...
- 87
2
votes
1
answer
262
views
Randomly fixing elements and transcendence degree
Given $f_1,\ldots,f_n \in \mathbb{F}_q[x_1,\ldots,x_m]$ such that $\deg(f_i) \leq d < q$. Suppose we have for some $1 \leq j \leq m$
$$ \operatorname{trdeg}_{\mathbb{F}(x_1,\ldots,x_j)}\{f_1,\ldots,...
- 341
2
votes
0
answers
187
views
Matrix with elementary symmetric polynomials as entries
Let $n\geq 1$, and for each $j=1,\ldots, n+1$ let $\mathbf{X}_{j}=(X_{j1},\ldots, X_{jn})$ be $n$ variables. Let $M$ be the $(n+1)\times (n+1)$ matrix whose $(i,j)$-th entry is $$M_{ij}=(-1)^i e_{i-1}(...
3
votes
1
answer
117
views
How to understand 'the problem of determining the exact number of monomials in P(x) given by a black box is #P-Complete'
In this paper:
Michael Ben-Or and Prasoon Tiwari. 1988. A deterministic algorithm for sparse multivariate polynomial interpolation, In: Proceedings of the twentieth annual ACM symposium on Theory of ...
- 31
8
votes
1
answer
827
views
Integer solutions for a simple cubic
What are the integer solutions to $x^3 - 7xy + y + 1 = 0$? A computation only finds $(0, -1), (-1, 0), (-6, 5), (-49, 342)$. This is surprisingly few.
Are these all of them? Is there an algebraic ...
- 83
0
votes
0
answers
53
views
A question on bounding the size of the polynomial
Suppose we are given the following n polynomials in $\bar{\mathbb{F}}_2[x_1,...,x_n]$:
$f_1 = x_1 + x_n^2$
$f_2 = x_2 + x_1^2$
$\cdot$
$\cdot$
$f_{n-3} = x_{n-3} + x_{n-4}^2$
$f_{n-2} = x_{n-2} + x_{n-...
- 341
13
votes
0
answers
188
views
Why is $ULU=NU$ (a refinement of $|N|=q^{n^2-n}$)?
Let $G=GL_n(\mathbb{F}_q)$, $U$, $L$, $N$ the subsets of upper-triangular unipotent, lower-triangular unipotent, all unipotent matrices respectively. Then $ULU=NU$ means that for any $g\in G$ the ...
- 3,772
1
vote
0
answers
158
views
Representation of finite fields as matrices
How a prime-ordered finite field $F_p$ can be represented as a matrix field? I found many claims that this is possible online but all the links are either paywalled or non-functional (as in this ...
- 10.1k
3
votes
0
answers
174
views
On the sheaves-functions dictionary
Let $X$ be a variety over a finite field $k$. Let $\pi_{1}(X)$ be the arithmetic etale fundamental group of $X$, and $\rho:\pi_{1}(X)\to k^{\times}$ a continuous character. If $x: \text{Spec}(k)\to X$ ...
- 667
1
vote
1
answer
234
views
Are there conditions for an elliptic curve to have a quadratic $\mathbb{F}_q$-cover of the line without ramification $\mathbb{F}_q$-points?
Consider an elliptic curve $E: y^2 = f(x) := x^3 + ax + b$ over a finite field $\mathbb{F}_q$ of characteristic $> 3$. Obviously, the projection to $x$ is a quadratic $\mathbb{F}_q$-cover of the ...
- 1,833
2
votes
0
answers
122
views
What do we know about efficiently finding a solution to a system of multivariate polynomials over finite fields?
Consider the following (NP-complete) problem:
Given a system of polynomials $f_1, f_2, \ldots, f_m \in \mathbb{F}_q[x_1, x_2, \ldots, x_n]$ of total degree at most $d$, find an $\mathbb{F}_q$-rational ...
- 121
0
votes
0
answers
61
views
Is generating semirandom blake256 hashes until packed points is on the curve, a safe algorithm to avoid the discrete log between the generated points?
I know there are more robust methods, but I wanted to know about this specific one
For any distinct said randomly generated point : $P_i,P_j\in \{P_1,...,P_k\}$ it should be hard to find $s$ such that ...
- 87
4
votes
1
answer
338
views
Bounds on quadratic character sums
I asked this question on Mathematics stack exchange but didn't get a response, so I ask here too.
Let $\chi$ be the non-trivial quadratic character of $\mathbb{F}_q$, and let $f(x)$ be a square-free ...
- 153
0
votes
0
answers
54
views
Solving sparse bilinear systems with a relatively large number of variables
I'm trying to solve a bilinear system of equations over a finite field. (More specifically: I'm trying to find a single solution, if one exists.) The system consists of equations of the form
$$y^T A_i ...
- 101
2
votes
1
answer
119
views
Asymptotic size of largest subset in $\mathbb F_p^2$ defining only lines of different slopes
Suppose that all lines defined by pairs of distinct elements in a subset of $\mathbb F_p^2$ have different slopes. How large can such a subset be asymptotically (for primes $p\rightarrow \infty$)?
...
- 17.9k
2
votes
1
answer
158
views
Under row operations and column permutations a matrix A can be put in the non-unique form ( I | X ), what is known about the set of possible X?
Given a full row-rank matrix $A$, this can be put into a unique reduced row echelon form via elementary row operations. Allow column permutations (no column addition / multiplication) and this can be ...
- 33
0
votes
0
answers
97
views
Algebraic independence and substitution for quadratics
Let $f_{1},...,f_{n-1} \in \mathbb{F}[x_1,...,x_n]$ such that $\{ f_1,..., f_{n-1},x_n \}$ is algebraically independent over $\mathbb{F}$. Let $G \in \mathbb{F}[x_1,...,x_n,y_1,...,y_{n-1}]\...
- 341
0
votes
0
answers
113
views
Relation between minimality and algebraic independence for binomials?
$\DeclareMathOperator\supp{supp}$Given $f_1,...,f_n \in \mathbb{F}[x_1,...,x_n]$ such that
$f_1 = x_1 + q_1$
$f_2 = x_2 + q_2$
$\cdot \cdot \cdot$
$f_{n-1} = x_{n-1} + q_{n-1}$
$f_{n} = q_n$
such that ...
- 341
2
votes
1
answer
210
views
Minimality implies algebraic independence?
$\DeclareMathOperator\supp{supp}$Given $f_1,...,f_n \in \mathbb{F}[x_1,...,x_n]$ such that
$f_1 = x_1 + q_1$
$f_2 = x_2 + q_2$
$\cdot \cdot \cdot$
$f_{n-1} = x_{n-1} + q_{n-1}$
$f_{n} = q_n$
such that ...
- 341
1
vote
0
answers
65
views
Are these kinds of bases for $\mathbb{F}_2^q$ seen as a vector space studied?
In the context of my research, I have to work with sets of vectors $\left\{y_i\right\}_{i\in[n+1]}$ of $\mathbb{F}_2^n$ such that the following property is true:
$$\forall i\in[n+1], \left\{y_i\oplus ...
- 167
0
votes
0
answers
47
views
Counting zero-sum subsets of a finite field with a particular form
Let $\mathbb{F}$ be a finite prime field of characteristic different than $2$ and $\beta \in \mathbb{F}$ a generator of the $2$-power order multiplicative subgroup of order $2^k$, so $\beta^{2^{k-1}} =...
- 3,058
0
votes
0
answers
78
views
Bounding the dimension of $H^1(G, V\otimes V^{\vee})$
Let $G_S$ denote the Galois group of the maximal extension of $\mathbb{Q}$ unramified away from a finite set of primes, $S$. Let $V$ be a finite dimensional, $G_S$-representation over $\mathbb{F}_p$ (...
- 2,907
3
votes
1
answer
334
views
Sum of products of Fourier coefficients in finite field
Let $\mathbb{F_q}$ be some finite field and let $f,g: \mathbb{F_q} \to \mathbb{C}$.
By $\hat{f}, \hat{g}$ let's denote the Fourier coefficients of $f,g$ with respect to the additive characters of the ...
- 153
6
votes
0
answers
176
views
Fundamental lemma of sieve theory in function fields
Is there any literature concerning the fundamental lemma of sieve theory in $\mathbb{F}_q[T]$?
In integers there are various versions of the lemma (bases on different sieves); I would be happy with ...
- 14.6k
1
vote
1
answer
111
views
Expected number of solutions of a random quadratic polynomial system over a finite field
Let $\mathbb{F}_q$ be a field of $q$ elements. Let $a_{i,j,k}$, $b_{i,j}$, $c_i$ ($1 \leq i \leq m$, $1 \leq j \leq k \leq n$) be independent uniformly distributed random variables in $\mathbb{F}_q$, ...
- 157
0
votes
0
answers
35
views
Endomorphism of torsion points of Drinfeld modules
Reposting from mathstackexchange.
A Drinfeld module is defined to be an $\mathbb F_q$-algebra morphism $\phi: \mathbb F_q[T] \rightarrow K\{\tau\}$, where $K=\mathbb F_{q^m}$ is a finite field and $K\{...
- 149
1
vote
0
answers
88
views
When does sum of algebraically independent polynomial become dependent?
Given $f_1,...,f_n \in \mathbb{F}[x_1,...,x_n]$ where $f_n = g + h$. Suppose the sets $\{ f_1,...,f_{n-1},g \}$ and $\{ f_1,...,f_{n-1},h \}$ are algebraically independent then is there a ...
- 341
1
vote
0
answers
121
views
Solution formula in an explicit equation over $\mathbb{F}_p^3$
I'm looking into a formula involving prime numbers $p \geq 7$ and an equation's solutions. The equation in question is:
$$z^2 = (x^2 - 4x)(y^2 - 4y)((x + 1 - y)^2 - 4x),$$
where $(x,y,z)\in \mathbb{F}...
- 71
0
votes
0
answers
102
views
Is there an inner product on $\mathbb{F}_p\left[S_n\right]$ for which $\langle x, x \rangle \ne 0$ for all $x$?
Let $\mathbb{F}_p\left[S_n\right]$ be the group algebra of the symmetric group $S_n$ over the finite field $\mathbb{F}_p$.
One can define an "inner product" in the usual way:
$$\langle x,y \...
- 571
0
votes
0
answers
43
views
When does the sum of squares/cubes of polynomials over finite field have less than maximum degree?
Given polynomials $p_1(x), p_2(x), \dots p_m(x) \in \mathbb{F}_p[x]/\langle x^p-x\rangle$ where $p$ is a prime, when does $\sum_{i=1}^m p^2_i(x)$ have degree $< p-1$? What about $\sum_{i=1}^m p^3_i(...
9
votes
0
answers
261
views
Who was the first to prove that the automorphism group of a finite field is cyclic and is generated by the Frobenius automorphism?
$\DeclareMathOperator\Aut{Aut}$It is well-known that the automorphism group $\Aut(F)$ of a finite field $F$ of characteristic $p$ is cyclic of order $n$ where $|F|=p^n$. Moreover, the cyclic group $\...
- 41.8k
5
votes
1
answer
176
views
Rational functions of order $3$
Let $p$ be a prime, let $\mathbb K$ a field with $\operatorname{char}(\mathbb K)=p$ and $\mathbb{K}(x)$ be the field of fractions of the polynomial ring $\mathbb{K}[x]$, i.e. $$\mathbb{K}(x)=\left\{\...
- 51
0
votes
0
answers
184
views
Degree 6 Galois extension over $\mathbb{Q} $
Let L be the splitting field of $ x^3- 2$ over $ \mathbb{Q}$. Then $ G=\operatorname{Gal}(L/K) \cong S_3$. Let $\sigma\in G$ such that the fixed field of $ \sigma$ is $\mathbb{Q}(2^{1/3})$. Let $x,y\...
- 923