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
0
votes
0answers
62 views

On $g^{2^x}=B$ modulo $p$

Let $p$ be prime and $g$ positive integer. Define $f(g,x)=g^{2^x} \bmod p$. Q1 Given $g,p,B=f(g,X)$, what is the complexity of finding $X$? If necessary assume $\varphi(p-1)$ is smooth. Some ...
0
votes
0answers
59 views

Gaussian integer square root solution [closed]

I'm trying to solve the equation $$ E(x)=\frac{(1+ix)^{1/2}-(1-ix)^{1/2}}{(1+ix)^{1/2}+(1-ix)^{1/2}} \mod p, $$ where $p$ is a prime and $1+ix$ is a Gaussian integer over $p$. For some values of $x$, ...
2
votes
1answer
118 views

Subgroups of $\mathrm{SO}(A_0, \mathbb{F}_p)$

Let $n \geq 3$. Let $A_0$ denote the $n \times n$ symmetric matrix with $1$'s on the antidiagonal and $0$'s everywhere else. We can define the associated special orthogonal group $$ \mathrm{SO}(A_0, \...
9
votes
1answer
308 views

p-adic analogue of octonions

There are the complex p-adic numbers. But what is the p-adic analogue of the Cayley–Dickson construction? Or more important: What is the p-adic analogue of the octonions? It would be nice if the (unit)...
1
vote
1answer
96 views

Does Conway’s field of finite nim values have arithmetically tractable isomorphisms?

Conway constructed a field of characteristic 2 whose elements are the finite Nim values, indexed by the natural numbers. What is known about nontrivial automorphisms of this field? Do any of them ...
21
votes
1answer
481 views

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

"multi-dimensional" cyclotomic number

Let $F_q$ be the finite field with $q$ elements with characteristic $p$ and with $g$ being a primitive root. Let $N$ be a divisor of $q-1$ and let $C_0$ be the subgroup of $F_q^*$ with index $N$. Then ...
0
votes
0answers
20 views

On rank distribution of certain matrix products

We are in $\mathbb F_2$ and we have a rank $k$ matrix in $\mathbb F_2^{n\times n}$ where $k\in\{1,\dots,n\}$ and we fix $j\in\{1,\dots,n-1\}$. We pick $n-j$ uniformly random matrices $M_1,\dots,M_{n-j}...
1
vote
1answer
118 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 ...
2
votes
1answer
212 views

The numbers of isomorphism classes of abelian variety over finite fields

It is known that there are only finitely many isomorphism classes of abelian variety over a finite field. I am curious about the exact number of these isomorphism classes. Explicitly, fix $g$, let $\...
0
votes
1answer
69 views

Does binary extension field multiplication matrix have random rows?

Any element in a boolean extension field $a\in GF(2^n)$ can be presented by a boolean vector $a_{(2)} \in GF(2)^n$. For any element $a\in GF(2^n)$, there exists a boolean matrix $M_a\in GF(2)^{n\...
6
votes
1answer
547 views

Upper bound for an exponential sum involving characters of a finite field

Let $q = p^n $ be a prime power, $\alpha\in\mathbb{F}_{q} $ a primitive element of the finite field $\mathbb{F}_q$ and denote by $\chi $ a non-trivial additive character of $\mathbb{F}_{q} $. Set $\...
19
votes
1answer
382 views

Varieties with the same number of $\mathbb{F}_p$-points for all but finitely many primes

If two varieties over $\mathbb{Q}$ have the same number of $\mathbb{F}_p$-points for all but finitely many primes do they have the same number of $\mathbb{F}_{p^n}$-points for all $n>1$ and for all ...
2
votes
0answers
139 views

Can the relation between count of commuting pairs and conjugacy classes for finite groups be generalized to semigroups?

It is well-known that number of pairs of commuting elements in finite group G is equal to number of conjugacy classes multiplied by cardinality of G. More generally here (MO275769) Qiaochu Yuan ...
7
votes
2answers
531 views

What is a function field analog of Giuga's conjecture?

Giuga's conjecture (1950), which is still open and has strong numerical support, reads : Let $n$ be a positive integer. If $1+\sum_{k=1}^{n-1}k^{n-1} \equiv 0\pmod{n}$ then $n$ is prime. What would ...
7
votes
1answer
495 views

Polynomials which are functionally equivalent over finite fields

Recall that two polynomials over a finite field are not necessarily considered equal, even if they evaluate to the same value at every point. For example, suppose $f(x) = x^2 + x + 1$ and $g(x) = 1$. ...
6
votes
0answers
139 views

Galois group of zeta function of hyperelliptic curve

Let $f \in \mathbb F_q[T]$ be monic, squarefree. Can we say anything on the Galois group of $Z_f$, the zeta function of the hyperelliptic curve $y^2=f$, directly in terms of $f$ (coefficients or ...
0
votes
0answers
42 views

Rank decomposition of matrices over $\mathbb F_2$

Given an integer matrix $M\in\mathbb Z^{n\times n}$ of real rank $k$ what is the minimum and maximum number of rank $1$ matrices $B_1$ to $B_t$ we require so that $M\equiv\sum_{i=1}^tB_i\bmod 2$? If $...
6
votes
1answer
239 views

How large can the dimension of a 'Span of powers of a finite field basis' be?

Let $p$ be a prime. For finite field $\mathbb{F}_{p^k}$ and $d\in\mathbb{Z}^+$, I am considering the following quantity, where we interpret the field $\mathbb{F}_{p^k}$ also as a $\mathbb{F}_p$-vector ...
3
votes
2answers
200 views

Number of involutions in finite reductive groups

Let $G$ be a connected split reductive group over $\mathbb{Z}$. Let $n$ be a positive integer. Let $i_n(q)$ be the number of elements of $G(\mathbb{F}_q)$ satisfying $x^n=1$. Question: Is there a &...
2
votes
0answers
74 views

Sum of binary quadratic forms over inputs of equal Hamming weight

$\DeclareMathOperator{\field}{\mathbb{F}}$ Let $n$ be a positive integer, and let $q : \field_2^{n} \rightarrow \field_2$ be a quadratic form, specified in coordinates as $$q(x)=\sum_{i =1}^n \alpha_i ...
3
votes
1answer
236 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^{...
1
vote
0answers
137 views

Vanishing product of polynomials over finite fields

$(x_1-x_2-x_3+x_4)(x_2-x_4-x_3+x_1)(x_3-x_1)(x_4-x_2)\equiv 0$ over $\mathbb F_3$. Take polynomials $p_1,\dots,p_n$ over variables $x_1,\dots,x_n$ such that $p_i$ does not depend on $x_i$ and $\Pi_{i=...
0
votes
1answer
191 views

For which $\beta \in \mathbb{F}_{p^k}$, $\{1,\beta,\beta^2,\cdots,\beta^{k-1}\}$ form a basis of $\mathbb{F}_{p^k}$? [closed]

Let $p$ be a prime, and let $\mathbb{F}_{p^k}$ be a finite field. For which $\beta \in \mathbb{F}_{p^k}$, $\mathcal{B}_{\beta}:=\{1,\beta,\beta^2,\cdots,\beta^{k-1}\}$ form a $\mathbb{F}_p$-basis of $\...
7
votes
2answers
395 views

Supersingular curves over $\mathbb{F}_q$ and the splitting of $p$

I'm looking at chapter 4 of Waterhouse's "Abelian varieties over finite fields"; and Theorems 4.1 and 4.2 seem to use the following fact: Suppose that $E/\mathbb{F}_q$ is an elliptic curve ...
3
votes
2answers
187 views

Number of solutions of quadratic equation from a perfect pairing over $\mathbb{Z}/p^n\mathbb{Z}$

Let $p>2$ be a prime number, $V=\left(\mathbb{Z}/p^n\mathbb{Z}\right)^{2k+1}$. The bilinear form $$B:V\times V \rightarrow \mathbb{Z}/p^n\mathbb{Z}$$ is a perfect pairing. That is, mapping $x\in V$ ...
0
votes
1answer
122 views

Primes of the form $p=u^2+1$ and number of points on the elliptic curve $x^3+a x z^2=y^2 z$

Let $p$ be prime of the form $p=u^2+1$. For $a \in \mathbb{F}_p,a \ne 0$, define $E_a : x^3+a x z^2=y^2 z$ Let $B= \lfloor 2 \sqrt{p}\rfloor$ Must we have $(\#E_a(\mathbb{F}_p) -p - 1) \in \{2,-2,B,-B\...
7
votes
2answers
294 views

How to count the number of tensors over a finite field of tensor rank $r$?

For simplicity, work over $\mathbb F_2$ and only consider order-$3$ equilateral tensors. For $r\in\mathbb Z_{>0}$, how many tensors $\mathfrak{T}\in\mathsf{Ten}_{n}^{\otimes 3}(\mathbb F_2)$ are ...
-1
votes
1answer
199 views

Bounds for the number of points on projective hyperelliptic curves over finite fields

Let $C$ be projective hyperelliptic curve over finite field $K$. What are bounds for the number of points $\#C(K)$? The Hasse-Weil bound requires smooth curves, and hyperelliptic curves are not smooth ...
6
votes
2answers
776 views

Does there exist a polar decomposition of matrices over finite fields?

There exists a polar decomposition for matrices over the reals. What I would like to know is if an analog has been shown for groups of matrices over finite fields. If not, it would be great to get ...
3
votes
6answers
2k views

Finite field special functions

I am looking for special class of involutive functions (f) with exactly one (zero) fixed point over finite field $F_q$ with properties: 1) $f(f(x))=x$ for any $x \in F_q$ , $f(x)=x$ iff $x=0$ 2) ...
2
votes
0answers
141 views

On hypergeometric functions over finite fields

Let $\mathbb{F}_q$ be a finite field of $q$ elements. Let $A,B,C,\cdots$ denote the multiplicative characters over $\mathbb{F}_q$, and let $\overline{A}$ denote the inverse of $A$, i.e., $A(x)\...
0
votes
1answer
89 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+...
2
votes
1answer
109 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 $\...
3
votes
1answer
215 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 ...
8
votes
2answers
392 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$ ...
2
votes
0answers
105 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 = ...
4
votes
2answers
261 views

Bivariate polynomial divisibility test of Spielman

Setup In his thesis (lemma 4.2.18, p. 97-98) Spielman describes a divisibility test for bivariate polynomials $E,P\in k[X,Y]$, where $k$ is a field (of positive characteristic for what I'm interested ...
1
vote
2answers
341 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 ...
14
votes
1answer
262 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-...
0
votes
0answers
8 views

On solutions to linear system amalgam

Input: I. System of $\Omega(t)$ linear polynomials in $\mathbb F_2[x_1,\dots,x_{t}]$. II. System of $\Omega(t)$ linear polynomials in $\mathbb Z[x_1,\dots,x_{t}]$. Can we output a common $0/1$ ...
0
votes
1answer
170 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 ...
4
votes
0answers
72 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 ...
1
vote
0answers
119 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 ...
3
votes
0answers
288 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 ...
9
votes
2answers
433 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 ...
1
vote
2answers
220 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.
2
votes
1answer
80 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 ...
11
votes
2answers
795 views

Is there an $\mathbb{R}$-valued cohomology theory for varieties over $\mathbb{F}_p$?

If $E$ is a supersingular elliptic curve over $\mathbb{F}_{p^m}$ with $m\geq 2$ its endomorphism ring is a maximal order in a quaternion algebra ramified at $p$ and $\infty$ so there can't be a Weil ...
4
votes
1answer
141 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\...

1
2 3 4 5
14