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.
774
questions
0
votes
1
answer
230
views
$\mathbb R$ and $\mathbb F_2$ rank in boolean matrix product
By rank I imply rank over reals ($\mathbb R$).
I consider two $n\times n$ matrices $A,B$ having entries in $0/1$.
The product below follows usual matrix product rules except $xy$ is $AND(x,y)$ and $x+...
- 23
8
votes
2
answers
583
views
Isomorphic endomorphism algebras implies isogenous (for abelian varieties over finite fields)?
$\newcommand{\F}{\mathbb{F}}
\newcommand{\End}{\mathrm{End}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}$
I would like to know if the following is true:
Proposition A : Let $A_1, A_2$ ...
- 1,702
2
votes
0
answers
132
views
What can we say about the intersection of an algebraic and product set?
This question is a bit vague by design. Let $F$ be a field. I'm mostly interested in finite fields, but would also be interested in $R$ or $C$.
Let $S \subset F^d$ be an algebraic set and let $A = ...
- 11.8k
2
votes
1
answer
121
views
Curves sharing points over finite fields, and their mutual divisibility
Consider in $\mathbb{A}^2(\mathbb{F}_q)$ two $\mathbb{F}_q$-rational curves $\mathcal{X}:f(x,y)=0$ and $\mathcal{Y}:g(x,y)=0$, and let $\mathcal{Y}$ be absolutely irreducible. Suppose also that $\...
- 21
1
vote
2
answers
381
views
A quantity associated to a field extension
Let $F\subset E$ be a field extension. So $E$ has a natural structure of $F$-vector space.
A vector subspace $V\subset E$ is a special subspace if $F\subset V$ and $V$ is closed under the inverse ...
- 312
0
votes
1
answer
178
views
On a system of equations in $\mathbb F_2$
Input: System of $\Omega(t)$ independent polynomials in $\mathbb F_2[x_1,\dots,x_{t}]$ of degree $O(t)$.
Can we output a common solution of the system in polynomial time?
Can we output parity of the ...
- 13.7k
3
votes
1
answer
261
views
p-adic logarithms with fixed precision
Probably this is easy, but we would like to see it on paper.
Let $p$ be prime and $D,g,n$ positive integers.
Let $A=g^n \bmod p^D$.
Let $\log(p,a,D)$ be the p-adic logarithm with precision $D$.
In ...
- 24.2k
4
votes
1
answer
160
views
Subspaces of vanishing permanent
Suppose that $p\ge 5$ is a prime, $n$ a positive integer divisible by $p-1$,
and $L<\mathbb F_p^n$ a subspace of dimension $d=n/(p-1)$. Do there exist
vectors $l_1,\dotsc,l_n\in L$ such that the ...
- 22.8k
14
votes
1
answer
281
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-...
- 151k
1
vote
0
answers
138
views
Properties of pointless projective curves over finite fields?
Probably not research level, feel free to downvote.
We got construction of bounded degree projective curves
with no points over finite fields. This construction generalizes to higher dimension.
One of ...
- 24.2k
3
votes
0
answers
303
views
Why the curve $x^2+y^2+y+1=0$ has only one point over $\mathbb{F}_{3^7}$?
According to both sagemath and Magma the curve $x^2+y^2+y+1=0$ has only one point over $\mathbb{F}_{3^7}$.
The projective closure has only one point too.
Q1 What hypothesis are missing to not violate ...
- 24.2k
2
votes
1
answer
161
views
Low-Hamming weight vectors in low-dimensional subspaces of $\mathbb{F}_p^n$
What is the maximum number vectors of Hamming weight at most $w$ in a $d$-dimensional subspace of $\mathbb{F}_p^n$, where $w,d,p$ are constant and $p$ is odd. (The Hamming weight is the number of ...
- 93
9
votes
2
answers
503
views
Chevalley-Warning-Ax for double covers
Let $f(x_1,\ldots,x_n)$ be a polynomial of degree $d$ with coefficients in the finite field $\mathbb F_q$ and let $V(f)\subseteq\mathbb F_q^n$ be its set of zeroes. Assume $d<n$. Then Chevalley ...
- 15.3k
1
vote
0
answers
83
views
On the real and finite field rank of a $0/1$ matrix - II
Let $M\in\{-\ell,\dots,-1,0,+1,\dots,+\ell\}^{n\times n}$ be a matrix of rank $r$ where $\ell\geq1$ such that there is a permutation matrix in $\{0,1\}^{m\times m}$ of order $2\ell$.
Fix a permutation ...
- 13.7k
4
votes
1
answer
296
views
On the real and finite field rank of a $0/1$ matrix - I
Let $M\in\{-1,0,+1\}^{n\times n}$ be a matrix of rank $r$.
Consider the matrix $f(M)\in\{0,+1\}^{mn\times mn}$ where $0$ in $M$ is replaced by $m\times m$ all $0$ matrix, $+1$ in $M$ is replaced by $m\...
- 13.7k
6
votes
1
answer
366
views
Least prime in Artin's primitive root conjecture
Let $a$ be an integer which is neither a square nor $-1$. Artin's conjecture states that there are infinitely many primes $p$ for which $a$ is a primitive root modulo $p$. My question is whether there ...
- 2,949
7
votes
2
answers
585
views
On a matrix problem in the field $\mathbb F_2$
Given $M$ a symmetric matrix in $\mathbb F_2^{n\times n}$ having $\mathsf{det}_\mathbb R(M)\neq0$ (non-singular in reals) and satisfying $PMP'=(M+J+I)$ or $P(M+J+I)P'=M$ where $P$ is a permutation ...
- 13.7k
1
vote
0
answers
94
views
Polynomial composition utilizing polynomials in two different finite fields
At every $n\in\mathbb N$ (all polynomials are of degree $O(1)$) is there $g_{3,1}^{(n)},\dots,g_{3,k}^{(n)}\in\mathbb F_3[x_1,\dots,x_n]$ at $k=\mathsf{poly}(n)$ and $g_2^{(n)}\in\mathbb F_2[x_1,\dots,...
- 13.7k
0
votes
0
answers
212
views
What is the computational complexity of solving a highly underdetermined system?
Let $F$ be a finite field with $q$ elements. Consider an underdetermined system of linear equations with $m$ equations and $n$ variables where $n\gg m$. What is the complexity of solving such a highly ...
- 131
3
votes
0
answers
249
views
Finding (and saturating) a sharp Babenko-Beckner inequality for finite fields
My question is a follow-up to Abdelmalek Abdesselam's recent post
What makes Gaussian distributions special? Local field version?
asking about various characterizations of (real-valued) Gaussian ...
- 1,847
2
votes
0
answers
137
views
Distinguishing $0/1$ unimodular or singular matrices having $\mathsf{Permanent}\in\{0,1\}$?
Let $\mathcal T_n=\{M\in\{0,1\}^{n\times n}:\mathsf{Per}(M)=\mathsf{Det}(M)\wedge\mathsf{Det}(M)\in\{0,1\}\}$ (restricted set unimodular or singular having permanent and determinant identical).
$\...
- 13.7k
1
vote
2
answers
315
views
How many non-isomorphic associative algebras of dimension 2 over the field F_{p^k} are there?
How many non-isomorphic associative algebras of dimension 2 over the field F_{p^k} are there?
As much as I have searched, I have not found any results that answer my question; not even for k = 1,2.
4
votes
1
answer
252
views
Dominating sets in subtournaments of the Paley tournament
For a tournament $T$, let $\mathrm{dom}(T)$ be the order of a smallest dominating set in $T$. Let $q$ be a prime power congruent to 3 mod 4 and let $T_q$ be the Paley tournament on $q$ vertices.
Is ...
- 1,666
0
votes
0
answers
227
views
Question on rank of matrices over $\mathbb F_2$
$A$ is a square matrix in $\mathbb F_2^{n\times n}$ of rank $k\leq n-1$.
$B$ is a square matrix in $\mathbb F_2^{n\times n}$ of rank $n$.
$T$ is a square matrix in $\mathbb F_2^{n\times n}$ of rank $1$...
- 13.7k
1
vote
1
answer
142
views
Schur complement and depermuting an algorithm for $\mathsf{determinant}\bmod2$
Let $$M=\begin{bmatrix}A&B\\C&D\end{bmatrix}$$ be a matrix in $\mathbb F_2^{n\times n}$ where $A\in\mathbb F_2$ and $D\in\mathbb F_2^{(n-1)\times(n-1)}$ are square.
Through the determinant ...
- 13.7k
5
votes
1
answer
162
views
Polynomials vanishing on prescribed layers
Given a prime $p$ and an integer $n\ge p$, what is the smallest possible degree of a polynomial $Q\in\mathbb F_p[x_1,\dotsc, x_n]$ such that $Q$ vanishes on every vector $x\in\{0,1\}^n$ of weight $w(x)...
- 22.8k
10
votes
1
answer
532
views
Does every geometric progression contain a small remainder modulo a large prime?
The exact question I am interested in is the following.
Fix a small $\varepsilon\in(0,1)$ and an integer $q\ge 2$ (you may assume that $q$ is prime if it helps though I believe it shouldn't matter too ...
- 59.8k
8
votes
0
answers
268
views
Maximum probability of a set of vectors from $ \mathbb{F}_2^n $ being linearly independent
Suppose $ m $ vectors from the vector space $ \mathbb{F}_2^n $ are selected independently according to a distribution $ P $ over $ \mathbb{F}_2^n $. Here $ \mathbb{F}_2 $ denotes the field with two ...
- 503
0
votes
0
answers
124
views
Injectivity of pushforward of rational Chow groups
I'd like to know whether there is a known counter-example to the following statement. Let $X$ be a smooth projective variety over a finite field. Let $Z$ be a codimension $2$ smooth subvariety which ...
- 5,851
2
votes
0
answers
169
views
Computing monodromy groups of curves over function fields
Suppose I consider a hyperelliptic curve given by an equation such as $y^2 = x^{n} + tx + 1$ or some variation on this (where $t$ is a parameter on $\mathbb P^1$ and this curve is really a surface ...
- 7,646
1
vote
2
answers
253
views
Reference for integral extensions of $\mathbb{Z}/p^k\mathbb{Z}$
I was looking for a reference which discusses the structure of finite integral extensions of $\mathbb{Z}/p^k\mathbb{Z}$. In particular, I am interested in understanding what the abelian group of its ...
- 145
0
votes
0
answers
97
views
Related involutions
Let's say that we have finite field $\mathbb F_q$ and we have a couple of involutions $g,f$ with exactly one fixed point (zero).
Let's take any element $\alpha \in \mathbb F_q$
Let's start applying ...
- 33
3
votes
1
answer
216
views
invariant subspaces of general linear groups for finite fields
Let $K$ be a finite field, let $n\ge 1$ be an integer and let $G=\mathrm{GL}(n,K)$ be acting linearly on a finite dimensional $K$-vector space $V$. Although $G$ is a reductive group, it is not ...
- 7,652
7
votes
2
answers
306
views
Representations of $\operatorname{Sp}(2g,\mathbb{Z}_3)$
Let $V$ be a $2g$-dimensional vector space over $\mathbb{Z}_3 := \mathbb{Z}/3\mathbb{Z}$. First, $\operatorname{Sp}(2g,\mathbb{Z}_3)$ acts on $\Lambda^2(V)$, and this decomposition is reducible, as ...
- 73
2
votes
0
answers
115
views
Loewy structure of $S_4$
How to deduce the Loewy Structure of $kS_4$ where $k$ has characteristic 2. I can compute the Cartan matrix and Decomposition matrix with Brauer Characters without difficulties. But when it comes to ...
- 51
2
votes
0
answers
108
views
Standard interpretation of permanents (of orthogonal included) over finite fields
Given a $0/1$ matrix in $\mathbb Z^{n\times n}$ the standard interpretation of permanent of the matrix is the number of perfect matchings in the underlying $2n$ vertex balanced bipartite graph with ...
- 13.7k
9
votes
1
answer
350
views
Standard conjecture on u-invariants?
This is well beyond my expertise, but I just learned some of the history behind
$u$-invariants of fields $F$,
where ($u(F)+1$)-variable quadratic equations always have a non-trivial solution,
but $u(F)...
- 149k
0
votes
0
answers
97
views
Invertible matrix by using polynomial in LDPC codes
I am studying about QC-LDPC codes.
These codes can be represented by matrices or polynomial.
For instance:
Example.
So, we have two polynomials: $a_1(x) = 1 +x$ and $a_2(x) = 1+x^2+x^4$.
The second ...
2
votes
0
answers
140
views
On some rational points on an elliptic curve over finite field
Let $p\equiv3\pmod4$ be a prime. We consider the elliptic curve $E$ over the finite field $\mathbb{F}_p$
(in affine coordinates) defined by
$$y^2=x^3+x.$$
Clearly the discriminant of $E$ is $-2^6$. ...
user125345
1
vote
1
answer
308
views
Polynomial form/Fourier transform of rational function over finite affine space
I am certainly going to make a mess of any serious algebraic terminology, so bear with me as I present my problem arising from a probability problem.
Consider the space of sequences of $n$ zero-one ...
- 516
5
votes
1
answer
549
views
How different can the bias of two polynomials be?
I'm trying to figure out how to approach the following question:
Let $g,h$ be polynomials over $\mathbb{Z}_p$ (for prime $p$) with $n>1$ variables.
Denote by $bias(g)=|\sum_{x\in \mathbb{Z}_p^n}e^{...
- 181
1
vote
1
answer
191
views
Is finite field version kakeya conjecture still true when changing the line of every direction with only 2(or several but not the full line)element?
The classical finite field Kakeya conjecture state as following (for conveinent, all version of kakeya conjecture is state in hasdorff dimension version):
$\mathrm{Finite\ Field\ Kakeya\ ...
- 543
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.
11
votes
4
answers
1k
views
Explicit large finite fields in characteristic $2$
Every finite field of characteristic $2$ ist given by $\mathbb{F}_2[x]/P(x)$ for some irreducible polynomial $P\in \mathbb{F}_2[x]$.
For small degree, a simple algorithm gives a way to find $P$. Is ...
- 7,652
1
vote
0
answers
73
views
Symmetric matrices of hyperbolic and elliptic type with certain kind of trace zero
I have been working on a problem related to determinantal varieties in symmetric matrices. I am stuck at the following point and would like to get some reference/help for the following question.
Let $\...
- 179
2
votes
0
answers
179
views
Dyadic models in number theory and "spillover"
In a classic blog post, Tao discusses the appearance of "dyadic models" in various guises in various areas of math. The number-theoretic version of the idea is to study polynomials over a ...
10
votes
1
answer
570
views
Discrete logarithm for polynomials
Let $p$ be a fixed small prime (I'm particularly interested in $p = 2$), and let $Q, R \in \mathbb{F}_p[X]$ be polynomials.
Consider the problem of determining the set of $n \in \mathbb{N}$ such that $...
- 12.2k
5
votes
1
answer
190
views
Orbit counting polynomials over finite fields
Let $X$ be an affine variety defined over $\mathbb{Z}$ and let $G$ be an algebraic group defined over $\mathbb{Z}$. Let $q$ be a power of a prime number. We write $\mathbb{F}_q$ for the field with $q$ ...
- 4,979
1
vote
0
answers
121
views
Permutation induced by multiplication of finite field elements [closed]
Consider a finite field $\mathbb F$. Let $a \in \mathbb F$. Then multiplication by $a$ induces a permutation on the field elements. $0 \rightarrow 0$, $1 \rightarrow a$, $2 \rightarrow 2a$, etc.
Is ...
- 11
4
votes
0
answers
129
views
$\delta$-equidistributed polynomials over finite fields
I'm trying to show that a polynomial over finite (prime) field is "close enough" to being equidistributed over its range. A polynomial $p(\cdot)$ from $\mathbb{F}^n$ to $\mathbb{F}$ is $\...
- 181