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
3
votes
0
answers
269
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 ...
- 2,137
3
votes
0
answers
130
views
Cyclic codes: sparse codewords not orthogonal to the all-ones vector
Is it true that for any sufficiently large prime $p$, there exists a prime $q\ne p$ and a cyclic code of length $p$ over $\mathbb{F}_q$ that contains a codeword of Hamming weight at most ord$_p(q)$ ...
- 93
3
votes
0
answers
147
views
Under what conditions on $A$ and $v$ is the size of the sumset $v \cdot A + A$ over $\mathbb{F}_p$ equal or close to $|A|^2$?
Let $p$ be a prime, let $A$ be a subset of $\mathbb{F}_p$, and let $v \in \mathbb{F}_p \setminus \{0\}$.
Under what conditions is $|v \cdot A + A|$ (that is, $|\{ va + b : a \in A,\ b \in A \}|$) ...
3
votes
0
answers
99
views
Unitary matrices $p$-root of identity such that the Fourier transform matrices are $p$-root of identity
Take a prime number $p$ and $\omega=e^{2i\pi/p}$. Assume we have p complex matrices (in finite dimension $n$) $A_0, \dotsc, A_{p-1}$ such that $\forall i, A_i^p=I$.
Define the $p$ fourrier transform ...
- 583
3
votes
0
answers
181
views
On an exercise in The Probabilistic Method : random dilate of a set in a finite field
This is related to Problem $4.6$ in ``The Probabilistic Method'' by Alon and Spencer, where one essentially has to prove the following:
Let $p$ be a prime, and $A$ be any subset of $\mathbb{F}_p$. ...
- 31
3
votes
0
answers
116
views
Trace of Symmetric matrices in fixed rank
I am solving some problem related to symmetric matrices over a finite field $\mathbb{F}_q$ and I am stuck at the following problem:
For every $a\in\mathbb{F}_q $, let $S_a(t,m)$ be the set of all $m\...
- 179
3
votes
0
answers
324
views
Roots of polynomials over $\mathbb{Z}/p^k\mathbb{Z}$
Over a finite field, such as $\mathbb{Z}/p\mathbb{Z}$, the number of roots of a polynomial is no larger than the degree. I'm interested in how does this generalize to $\mathbb{Z}/p^k\mathbb{Z}$.
I'm ...
- 41
3
votes
0
answers
213
views
Inverse of reduction mod $p$ functor?
I have a very general, and possibly not very precisely stated question, which comes up quite often in my work, and I would be very happy to be able to address. To my dismay, I only have some very ...
- 993
3
votes
0
answers
215
views
Why we are interested in p>3 Schoof's algorithm
In the Schoof's algorithm we are particularly interested in $char(K)>3$, where $K$ is the field. I know Schoof's algorithm is mostly used over large prime fields. Also, when we are transforming ...
- 149
3
votes
0
answers
401
views
Independence of elements of a finite field over a subfield
Let $a_1,a_2,\ldots,a_k$ be elements of the Galois field of order $q^n$, say $\mathbb{F}_{q^n}$, with $n \geq k$.
By Lemma 3.51 of Lidl, Niederreiter-Finite Fields,
$\left|
\begin{array}{...
- 325
3
votes
1
answer
241
views
Binary subspace membership testing with signed vectors
Say we are working in $\mathbb{F}^{2n}_2$ where vectors can be written as pairs $(a,b)$ with $a,b \in \mathbb{F}^{n}_2$. Given a list of basis vectors for an $n-1$ dimensional subspace $S \subset \...
- 31
3
votes
0
answers
285
views
What is known about the prime-to-$p$ etale fundamental group of $\mathbb{P}^1_{\mathbb{F}_p}$ minus $\mathbb{F}_p$-rational points?
Is it known to be (the prime-to-$p$ part of the profinite completion of) a finitely presentable group?
Is such a presentation known? Is there a guess for what it is? What is known about it?
- 2,071
3
votes
0
answers
394
views
Calculation of Cartier-Manin matrix
Let $\mathbb{F}_q$ be a finite field of characteristic $p$ and let $C$ be a plane projective nonsingular curve over $\mathbb{F}_q$ ,
with function field $K = \mathbb{F}_q(C)$. Let $K^p$ denote the ...
- 2,576
3
votes
0
answers
73
views
Number of classes $\pmod p$ represented by $b_1s^{n-1} + \dots + b_n$ where $ord_p(s) = n$
Let $n \in \mathbb Z$ with $n \ge 3$ and let $p$ be a prime number such that $n|p-1$. Let $a_1,a_2,\dots,a_{2n-1} \in \mathbb Z/p\mathbb Z$. Suppose that the same class is represented by at most $n-1$ ...
- 169
3
votes
0
answers
230
views
On weight enumerators of codes
Are there $[n,k]_q$ constant rate $\frac kn$ and constant alphabet linear code families with automorphism group of size $\Omega((n-n^\beta)!)$ that have minimum distance $d=O(n^\alpha)$ and number of ...
- 13.9k
3
votes
0
answers
174
views
Carlitz factorials and Euler-like series
Let $q$ be a power of a prime $p$. For every $i\in\mathbb N$, one denotes $D_i=\prod_{\substack{h\in\mathbb F_q[T]\text{ monic}\\\deg h=i}}\limits h$. For $n\in\mathbb N$, write $$n=n_0+n_1q+\cdots+...
- 3,998
3
votes
0
answers
108
views
How to construct large sets of $m$-dimensional vectors over a finite field such that any $m$ of them are independent?
Let $m\ge 2$ be an integer and $\mathbb{F}$ be a finite field of order $p^k$. I want to construct as many as possible $m$-dimensional vectors $v_1,v_2,\ldots,v_n$ in field $\mathbb{F}$ such that any $...
- 103
3
votes
1
answer
206
views
Characterization of Lagrangian planes in symplectic vector spaces over finite fields [closed]
EDIT: As L Spice pointed out, there is an error in the observation. The question is void therefore
Let $p$ be a prime and $q=p^r$. Let $V$ be a $\mathbb F_q$-vector space of dimension four, with a ...
3
votes
0
answers
118
views
How order of divisor with support at infinity is changed at reduction?
Jing Yu in his paper "On Arithmetic Of Hyperelliptic Curves" on page 5 asserts the following
The most interesting case is certainly the case $k = \mathbb Q$ and $D \in \mathbb Z[t]$.
To decide ...
- 424
3
votes
0
answers
290
views
Fields whose algebraic closure is a finite extension [duplicate]
It is well-known that the complex numbers $\mathbb{C}$ is a degree two extension of $\mathbb{R}$, where one possible minimal polynomial is $x^2 + 1$. Further, $\mathbb{C}$ is algebraically closed.
...
- 26.9k
3
votes
0
answers
321
views
When does composing polynomials reduce the degree?
Let $\mathbb{F}$ be the field of size 2. For a function $f : \mathbb{F}^n \to \mathbb{F}$, let $d(f)$ be the smallest integer such that there exists a degree-$d(f)$, $n$-variate, multilinear ...
- 71
3
votes
0
answers
167
views
Intersection of two trace equations over finite fields
Let $F_q$ be a finite field with $q$ elements. Let $n$ be an integer and $Tr:F_{q^n} \rightarrow F_q$ the trace function. My question is: For which integer $k$,
$$\{x: Tr(x)=0\}\cap\{x: Tr(x^k)=0\}=\{...
- 123
3
votes
0
answers
122
views
Family with a fixed special fiber over finite fields
Let $X$ be a smooth projective variety over a finite field $\mathbb{F}_p$. What are the conditions for the existence of a projective variety $X'$ over $\mathbb{Q}_p$ such that $X$ is a special fiber ...
- 1,040
3
votes
0
answers
168
views
Number of Inverse Pairs Modulo Prime $p$
Is there a result which gives a lower bound on the number of inverse pairs $(a, a^{-1})$ modulo prime $p$ lying in the interval $[1,t]$, where $t < p$?
- 91
3
votes
0
answers
346
views
Finch's sequence over $\mathbb{F}_3$
In http://algo.inria.fr/csolve/seqmod3.pdf -- "Periodicity in sequences mod 3" Steven Finch (also cited in Sloane's OEIS A112683) defines the following sequences in $\mathbb{F}_3$:
For each positive ...
- 4,636
2
votes
4
answers
752
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 ...
2
votes
3
answers
6k
views
How to factorize X^n - 1 in Z/pZ?
How do I factorize a polynomial $X^n - 1$ over $\mathbb{F}_p$? In particular I need to find factors of the polynomial $X^{3^3 - 1} - 1 = X^{26} - 1$ over $\mathbb{F}_3$.
- 330
2
votes
3
answers
852
views
Can a Decidable Theory Have Non-recursive Models?
Tennenbaums' theorem proves neither addition nor multiplication can be recursive in any countable non-standard model of arithmetic. Tennenbaum's proof applies to theories much weaker than PA.
...
- 687
2
votes
2
answers
570
views
Elliptic curves over proper variety over $\mathbf{F}_q$ isotrivial
Why is every elliptic curve over a proper (edit: smooth and geometrically connected) base over $\mathbf{F}_q$ isotrivial, i.e. is constant after base changing with $\bar{\mathbf{F}}_q$? If the moduli ...
- 227
2
votes
1
answer
115
views
Binary algebra, is it possible to partition the elements in GF(2^12) into 65 subgroups closed under addition?
The set of all binary vectors with 12 components forms a field with 2^12 elements containing 000000000000 and another 65*63 elements. Is it possible to partition these elements into 65 subgroups of 63 ...
- 23
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
2
votes
1
answer
458
views
Model of hyperbolic geometry with finite number of parallel line
Does there exist a model of hyperbolic geometry such that only finite number of distinct parallel lines through a point which does not intersect given line?
Edit (Misha): I usually do not edit other ...
2
votes
2
answers
175
views
linear independence of orbits via a set of transformations in char p
Let $T_1, \ldots, T_n \in GL(n,\mathbb{F}_p)$. Suppose for all $\vec{v} \in \mathbb{F}_p^n$ we have $\det (T_1 \vec{v}, T_2 \vec{v}, \ldots, T_n \vec{v}) = 0$. Now, let $k$ be a finite extension of $\...
- 23
2
votes
1
answer
3k
views
Primitive $k$th root of unity in a finite field $\mathbb{F}_p$
I am given a prime $p$ and another number $k$ ($k$ is likely a power of $2$). I want an efficient algorithm to find the $k$th root of unity in the field $\mathbb{F}_p$. Can someone tell me how to do ...
2
votes
1
answer
270
views
Quadratic forms without common zeroes
A question which, I suppose, is as easy as abc for an expert. For a given finite field $F$ of odd characteristic (if needed, the characteristic is $3$ and the size of $F$ is large), do there exist two ...
- 23k
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
154
views
On the estimate for the mixed 3-dimensional hyper-Kloosterman sum
There is a basic question regrading the mixed 3-dimensional hyper-Kloosterman sum:
For any positive integer $n$ not divisible by $p$, how to prove
$$\sideset{_{}^{}}{^{\ast}_{}}\sum _{x,y ,z\bmod p}
\...
- 563
2
votes
2
answers
327
views
How to prove that $A$ is supersingular iff the Picard number $\rho(A)$ is equal to the second $l$-adic Betti number $b_2(A) = 6$?
Let $A$ be an abelian surface over algebraically closed field $k$ of characteristic $p > 2$. How to prove that $A$ is supersingular (in other words, there is an isogeny between $A$ and $E^2$, where ...
- 1,833
2
votes
2
answers
243
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\...
- 3,001
2
votes
1
answer
229
views
Is there a regular surjective map $\psi\!: \mathbb{P}^2 \to X$ over $k$?
Assume there is $\varphi\!: \mathbb{P}^2 \to X$, a purely inseparable rational dominant map over a finite field $k$, where $X$ is an absolutely irreducible smooth surface over $k$. Is there a regular ...
- 1,833
2
votes
2
answers
273
views
Need help with paper written in Russian... Yorgov's paper on self-dual codes with automorphisms of odd order
I came across this paper by V.I.Yorgov named "Binary self-dual codes with automorphisms of odd order". (Actually I was first reading another paper by Borello that cited this paper. It later become ...
- 165
2
votes
1
answer
380
views
Dihedral subgroups of $\mathrm{PSL}_2(\mathbb{F}_q)$
Let $\mathbb{F}_q$ be a finite field with $q=p^f$ elements. I need to know when $\mathrm{PSL}_2(\mathbb{F}_q)$ contains the group $D_{(q+1)/2}$, where by $D_n$ I mean the dihedral group of order $2n$. ...
- 2,508
2
votes
1
answer
259
views
$\text{mod} \, p^2$ trace identity
Let $p$ be a prime, and let $\text{GL}_n \big( \Bbb{Z} / p^2 \Bbb{Z} \big)$ be the group of $n \times n$ invertible matrices over the ring $\Bbb{Z} / p^2 \Bbb{Z}$. Does there exist a positive integer $...
- 2,137
2
votes
2
answers
594
views
Polynomials over Z evaluated with finite field arguments
A) Given a non-constant polynomial $q\in\mathbb{Z}[\alpha_1,\alpha_2,\ldots,\alpha_n],$ if we pick random $\omega_i\in\mathbb{F}$ (a finite field) uniformly and independently across $1\leq i\leq n,$ ...
- 1,269
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
2
votes
1
answer
333
views
Uncountable cardinals and Prufer $p$-groups
Let $A$ be an elementary Abelian uncountable $p$-group. Is it known if there is an action of a Prufer $q$-group (here $q$ is a prime not necessarily distinct from $p$) $C_{q^{\infty}}$ onto $A$ such ...
- 599
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
1
answer
150
views
Are there a few input bits that randomize the output of an $\mathbb{F}_2$ polynomial?
Suppose $f:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$ is a degree $d$ polynomial and $\epsilon>0$ is some real number. Does there necessarily exist a set $C\subset [n]$ of coordinates with the size of ...
- 21
2
votes
2
answers
321
views
A graphic representation of classical unitals on 28 points
I would like to understand the geometry of the classical unitals.
They are block designs containing $q^3+1$ points and whose blocks have cardinality $q+1$, where $q$ is a prime power. For $q=2$ (if I ...
- 41.9k
2
votes
1
answer
170
views
Automorphism of positive characteristic field
Suppose $K$ is a field with $\text{char}(K) \geq 0$. Let $L$ be a cyclic extension of $K$ with degree $2n$. We consider the generator $\sigma$ of the Galois group $\text{Gal}(L/K)$.
I am interested in ...
- 923