The tag has no wiki summary.

learn more… | top users | synonyms

4
votes
2answers
821 views

Vandermonde matrices and general position

I was wondering if it is known whether a Vandermonde matrix over a sufficiently large finite field is in general position with respect to intersections of subspaces spanned by subsets of columns, i.e. ...
5
votes
1answer
358 views

Probability of a set of random vectors over finite field being a spanning set

Suppose I have a set of random vectors $f(a_1, \ldots, a_\ell) := (v_1, \ldots, v_m) \subset F_p^n$, $m \ge n$, given by a matrix valued polynomial function $f$, where the $a_i$'s are independent, ...
2
votes
0answers
282 views

Counting points over over an algebraic set over finite field.

Let $q=p^n$. Let $C$ be an Artin schierer curve defined by $y^p-y=f(x)$ where $f(x) \in \mathbb{F}_{q}[x]$. Let $C_g$ be $y^p-y=f(x)$ where $x \in g(\mathbb{F}_{p^{n}})$ for some $g \in ...
9
votes
6answers
1k views

Proofs in the same vein as Ax-Grothendieck

I would like to see other examples of (ideas of) proofs and results in the same vein as the proof of the Ax-Grothendieck theorem. To explain what I mean by "in the same vein", I will quote from the ...
6
votes
2answers
377 views

request sources about self-dual cyclic codes

X. Kai and S. Zhu in the paper "On cyclic self-dual codes", AAECC, vol. 19, pp. 509-525, 2008, at page 510 in line 6 said that, It is well Known that there are no cyclic self-dual codes over $F_q$ ...
5
votes
1answer
280 views

Aschbacher classes and $\mathbb{F}_p$-subspace stabilizers in classical linear groups

I am reading the Kleidman-Liebeck book ("The subgroup structure of the finite classical groups") which is about the Aschbacher classification of maximal subgroups of the classical almost simple ...
4
votes
4answers
897 views

Is there an analogue of finite fields for products of two prime powers?

The collection of prime powers can be characterized in the following way: There is a field with $q$ elements if and only if $q$ is a prime power. Furthermore if it exists then this field is unique ...
11
votes
3answers
2k views

Truncated Exponential Series Modulo $p$: Deeper meaning for a Putnam Question.

Apparently B6 of the Putnam this year asked: Suppose $p$ is an odd prime. Prove that for $n\in \{0,1,2...p-1\}$, at least $\frac{p+1}{2}$ of the numbers $\sum^{p-1}_{k=0} k! n^{k}$ are not ...
10
votes
3answers
936 views

Can we always find such an irreducible polynomial of degree n where degree(p(x)-x^n)<= n/2?

Consider unitary polynomials of degree $n$ over $GF(2)$. That is, polynomials of the form $p(x) = \sum_{i=0}^n a_i x^i$ where $a_i\in GF(2)$ and $a_n=1$. Can we always find such an irreducible ...
1
vote
0answers
151 views

reference-request for connection between numerator of zeta-function and characteristic polynomial of Frobenius on hyperelliptic curves over finite fields

Let $H$ be a hyperellipitic curve of genus $g$ defined over $\mathbb{F}_q$. The Frobenius endomorphism operates on the divisor class group of $H$ and satisfies a characteristic polynomial ...
0
votes
1answer
445 views

Multiplication of matrices in GF(2) and R

$H$ is an $n \times n$ matrix with elements in $ \{ -1,1 \}$ $G$ is an $n \times k$ matrix with elements in $GF(2)$ and also upper triangular, invertable $m$ is an $k \times 1$ vector with elements ...
2
votes
2answers
165 views

Cases of almost-linear time solvable linear systems

Let a square $n\times n$ real matrix ${\bf A}$ and two vectors ${\bf x}$ and ${\bf b}$ of length $n$, such that $${\bf A}{\bf x}={\bf b}.$$ Solving for ${\bf x}$ through standard Gaussian Elimination ...
0
votes
1answer
189 views

Low degree approximation of the polynomial extension of the logical-or function

Let $x\in\{0,1\}^n$ be a binary vector of dimension $n$, and let $OR(x)$ be the "logical or" function (i.e., returns $1$ if at least one of the coordinates is $1$ and otherwise returns $0$). Consider ...
0
votes
1answer
182 views

Finding an embedding efficiently in field extension of finite field

We know that $GF(p^c)$ is a subfield of $GF(p^{cn})$. Also we know that elements in $GF(p^c)$ can be represent by degree $c$ polynomials with coefficients in $\mathbb Z_p$, where multiplication is ...
6
votes
1answer
582 views

Exponential sums over finite fields with even characteristic

I am looking for an elementary evaluation (if one exists) of the exponential sum $$ G_r(a,b) = \sum_{x \in \mathbb{F}_{2^r}} \psi(ax^2 + bx), $$ where $a,b \in \mathbb{F}_{2^r}^*$ are both units, ...
1
vote
2answers
257 views

Minimum Growth Rate of Hamming Weight of Multiples of Primitive Polynomials

Let $F_2[x]$ denote the ring of polynomials over the field of 2 elements. Richard Brent has a page on finding primitive trinomials in $F_2[x]$ of huge degree at ...
8
votes
2answers
447 views

Invariant functor for admissible representations of reductive groups over local fields

Hello, I have a question concerning a certain functor between represention categories. I'm rather sure this is already known, but I could not find a reference. Let $F$ be a local non-archimedean ...
4
votes
3answers
582 views

Field with cyclic product group

If a field has a cyclic multiplicative group, is it necessarily finite?
4
votes
3answers
692 views

Fast Vandermonde matrix multiplication over finite field

Let $V_{i,j}=x_i^j$ where $x_i\in\mathbb F_q$ for $1\le i\le n,1\le j\le n$ be a Vandermonde matrix over finite field $\mathbb F_q$. I wish to know the currently known fastest algorithms for ...
1
vote
0answers
316 views

non-split Frobenius map

there are 3 simple groups arising from $SO(8)$, i.e.$ SO(8,F_{q})$, $2D_4(q,q^2)$,$3D_4(q,q^3),$ so I want to know For the $3D_4(q,q^3),$, what is the corresponding Frobenius?
1
vote
0answers
235 views

Sums of three squares in $GF(q)[t]$

Let $q$ be a power of an odd prime number $p>3,$ say $q=p^r$ with $r \geq 1.$ It is known that every polynomial $M$ in $GF(q)[t]$ is a sum of at most $3$ squares with some conditions on degrees. ...
3
votes
1answer
251 views

A kind of `pell` equation in characteristic $2.$

Given polynomials $a(t),b(t) \in K[t]$ where $K$ is a finite extension of $GF(2)$, with $$ a(t) \neq 0, $$ we consider the equation $$ x^2+axy+by^2=1 $$ with unknowns $x,y$ also polynomials in ...
3
votes
2answers
509 views

Reducible trinomials $x^{odd}+x^2+s(t)$ in characteristic $2$

Let $F$ be a finite field of characteristic $2$. Let $m \geq 2 $ be a positive integer. Seems unknown if the trinomial $$ T(t,x) = x^{2m+1}+x^2+s(t) \in F[t][x] $$ (more explicitly, the ...
6
votes
2answers
378 views

How do the number of plane curves over a finite field of a fixed genus increase with the degree?

Let $k$ be a finite field. We define $N(d,g)$ to be the number of plane curves $f(x,y)$ defined over $k$ of degree $d$ with (geometric) genus $g$. If $D(d) := (d-1)(d-2)/2$ (the maximum possible ...
22
votes
1answer
1k views

How does Tate verify his own conjecture for the Fermat hypersurface?

This question is about Tate's 1963 paper "Algebraic Cycles and Poles of Zeta Functions". Here he announces a conjecture (now known as "the Tate conjecture") which states that certain classes in the ...
1
vote
2answers
521 views

best deterministic complexity for factoring polynomials over finite field

I would like to know currently what's the best deterministic complexity for factoring polynomials over finite field (without the assumption of GRH)? I have searched on google, there are many source, ...
12
votes
1answer
485 views

Does $\mathbb{K}[G]\simeq\mathbb{K}[H]$ for some field $\mathbb{K}$ of characteristic $p$, imply $\mathbb{F}_p[G]\simeq\mathbb{F}_p[H]$?

Due to the first (and very helpful) answer I received, I've reformulated the question a little: $G$ and $H$ are now assumed to be $p$-groups. Let $\{p}$ be a prime, and let $\mathbb{F}_p$ be the ...
5
votes
7answers
538 views

Classifications of finite simple objects

I'm curious to know if other classifications are known of "finite simple structures" in the same spirit of the monumental classification of finite simple groups. Here I mean "classification" in the ...
0
votes
1answer
680 views

nontrivial cube root of unity [closed]

Hi, I have a finite field Fp with p = 11 mod(12) and I am trying to get the third nontrivial root of unity in Fp^2 = Fp^2[x]/(x^2+1). So, i need x where x^3=1. Somehow I came into a source saying ...
0
votes
1answer
583 views

Elliptic curve over finite field: scalar multiplication

I'm implementing arithmetics for elliptic curves over secp256r1 as a homework assignment. For scalar multiplication, the assignment specifically specifies that $k$ is "any hexidecimal encoded ...
3
votes
1answer
2k views

Number of n-th roots of unity over finite fields [closed]

How many $n$-th roots of unity does a finite field $\mathbb{GF}\left(p^k\right)$ have? ($p$ is prime). And then kind of related to that, is there a finite field with exactly $n_1,\ldots,n_N$ ...
4
votes
1answer
1k views

Irreducibility of some trinomials modulo $p$

Let $n>1$ be an integer. An old result of Selmer, See Theorem 1, page 289 in http://www.mscand.dk/article.php?id=1472, (If the link does not work try googling: ...
1
vote
0answers
179 views

Binary `neighbors` perfect polynomials, instead of `consecutive`

Inspired by Andrei's nice solution of 52609, (namely consecutive perfect polynomials): Denote by $A$ the full ring of polynomials in one variable $t$ over the ...
3
votes
1answer
263 views

Can two Consecutive Polynomials both be perfect ?

Denote by $A$ the full ring of polynomials in one variable $t$ over the finite field with $q$ elements. For any monic polynomial $P \in A$ define $$ \sigma(P) = \sum_{d \mid P, d\, \text{monic}} d. ...
1
vote
0answers
319 views

J. T. B. Beard's algorithm to catch `perfect polynomials`

For any monic polynomial $P$ with coefficients in a finite field of order $q$, we put $$ \sigma(P) = \sum_{d \mid P, d \text{ monic}} d. $$ Observe that $P$ and $\sigma(P)$ have the same degree. ...
9
votes
1answer
815 views

All polynomials over a finite field are sums of $2$ square-free polynomials

I quote Proposition 2.3, page 14 lines -3 and -4 of Michael Rosen's book Number Theory in Function Fields: Let $b_n$ be the number of square-free monics in $A= \mathbb{F}_q[t]$ of degree $n.$ Then ...
2
votes
1answer
234 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 ...
0
votes
0answers
132 views

elementary question on ECDLP

If $\mathbb{F}_q$ is a finite field and the elliptic curve E is defined over finite field $\mathbb{F}_p$ such that ECDLP is hard in E($\mathbb{F}_p$), where $q, p$ are prime and $q \ll p$. Let T $\in ...
3
votes
0answers
319 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 ...
20
votes
2answers
831 views

Does the etale fundamental group of the projective line minus a finite number of points over a finite field depend on the points?

Clearly the etale fundamental group of $\mathbb{P}^1_{\mathbb{C}} \setminus \{a_1,...,a_r\}$ doesn't depend on the $a_i$'s, because it is the profinite completion of the topological fundamental group. ...
3
votes
1answer
928 views

Finite fields: Is multiplicative order of $x^p - x - 1$ equal to $\frac{p^p-1}{p-1}$ over GF(p)? [duplicate]

Possible Duplicate: Multiplicative order of zeros of the Artin-Schreier Polynomial I will be grateful for any reference to some literature on the following question (to the best of my ...
13
votes
0answers
448 views

Noether-Deuring for injections and surjections?

Noether-Deuring theorem (not in the strongest form, but in the one I usually need): Let $L\diagup K$ be a field extension. Let $A$ be a $K$-algebra which is finite-dimensional as a vector space over ...
9
votes
2answers
737 views

Multiplicative order of zeros of the Artin-Schreier Polynomial

This question was asked on NMBRTHRY by Kurt Foster: If $p$ is a prime number and $\mathbb{F}_p$ the field of $p$ elements, the zeroes of the Artin-Schreier polynomial $x^p - x - 1 \in ...
4
votes
1answer
452 views

A silly question: is the number of points on a Jacobian (of a curve, over a finite field) known?

In a cryptography book I read that people does not known how to compute the number of points on a Jacobian of a hyperelliptic curve $C$ over a finite field $F_q$? Is this true? It seems easy to ...
7
votes
2answers
492 views

Gelfand-Tsetlin bases for Lie groups over finite fields

There is a method of constructing representations of classical Lie algebras via Gelfand-Tsetlin bases. It has also been applied to Symmetric groups by Vershik and Okounkov. Does anybody know of any ...
12
votes
1answer
708 views

A family of hypersurfaces with many points

This question is a sequel to an earlier question, which asked about the zeta function of a certain affine variety over a finite field $k$. The unusual thing about this variety is that it had the ...
4
votes
0answers
328 views

Given two linear operators A and B over a finite field, is there a third operator C whose kernel is the intersection of kernels of A and B?

Let $V$ be a finite dimensional linear space over a finite field $k$. Let $A$ and $B$ be two endomorphisms of $V$. Question 1. Is there an endomorphism $C$ of $V$, which is expressed in terms of ...
2
votes
2answers
462 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,$ ...
2
votes
2answers
308 views

vectors with entries from a finite ring

I've been working recently with vectors over finite fields, but I was hoping to work in a more general setting and consider vectors over finite commutative rings. The question I had is as follows: if ...
2
votes
1answer
496 views

Existence question on rational points on a curve

I am puzzled about the following question: Let C be a smooth, projective, absolutely irreducible curve defined over GF(q) and let g denote the genus of C. O is a rational point on C, and the divisor ...