The tag has no wiki summary.

learn more… | top users | synonyms

4
votes
1answer
191 views

How can I solve a cubic equation in a finite field with characteristic 2?

I need to solve the usual cubic equation x^3 + ax^2 + bx + c = 0 over a finite field GF(2^n). This is to avoid doing a brute-force Chien search in a BCH decoder. I read in a paper about an easy way ...
-1
votes
0answers
43 views

Trace of Frobenius of elliptic curve is integer [migrated]

I recently started to read the book "Arithmetic of Elliptic Curves" by Silverman. And I can't solve an exercise 5.10. Let $E/\mathbb F_q$ be an elliptic curve and $\phi$ is Frobenius endomorphism, ...
3
votes
1answer
80 views

Higher Discrete logarithms over finite fields

The polylogarithm function is defined by $$Li_s(z)=\sum_{k=1}^\infty\frac{z^k}{k^s}.$$ At $s=1$, we have the natural logarithm function. We have the inverse of natural logarithm function as the ...
4
votes
0answers
131 views

# roots of polynomials over GF(2)

Consider a polynomial $p(x)$ with of degree $d$ with coefficients in $GF(2)$. How many roots can it have in $GF(2^m)$? The intent here is that $d \ll 2^m$. The trivial bound is of course $\leq d$. ...
0
votes
0answers
51 views

Multivariable irreducible polynomials over finite fields [migrated]

It is not difficult to prove the following result, and it seems that it should be already proved. I would appreciate it if someone offer me some reference to it. For any $f(x_1,\dots, x_n)=\sum ...
2
votes
1answer
68 views

Stabilizer of a nonsingular vector in a quadratic space (char (k)=2)

suppose that $k$ is a finite field of characteristic 2 and $(V,q)$ a quadratic space, i.e., $V$ is a $k$-vector space and $q:V\to k$ quadratic form. Suppose that $\dim(V)\geq 4$ and that $q$ is ...
34
votes
2answers
763 views

A curious identity related to finite fields

To three elements $a_1$, $a_2$, $a_3$ in the finite field $\mathbb F_q$ of $q$ elements we associate the number $N(a_1,a_2,a_3)$ of elements $a_0\in \mathbb F_q$ such that the polynomial ...
6
votes
0answers
295 views

On the number of polynomials that divide $x^{q-1}-1$ in some subspaces of $\mathbb F_q[x]$

Let $\mathbb F_q$ be a finite field (where $q$ is in general a power of a prime), and let $e, k$ be positive integers with $k \leq e < q-1$. Let $f_0(x), \ldots, f_k(x) \in \mathbb F_q[x]$ be ...
1
vote
0answers
49 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: ...
0
votes
1answer
129 views

Generators of cyclic group of finite fields

Let $F$ be a finite field and $f(x)\in F[X]$ be an irreducible polynomial of degree $n$. Let $\alpha$ be a root of $f(x)$. So $E:=F[\alpha]$ is a finite field of order $|F|^{n}$. We know that ...
4
votes
1answer
109 views

Constructing GF(2^n) in poly(n) time

I need to, on input $n$, deterministically, in poly(n) time, construct $GF(2^n)$. There is a very simple randomized algorithm (pick a random polynomial, check if it's irreducible; if not, repeat). ...
4
votes
2answers
299 views

When are arithmetic and geometric monodromy equal?

Let $f: Y\to X$ be a finite separable morphism of curves over the finite field $\mathbb{F}_q$. Is there a simple condition under which the arithmetic and geometric monodromy of the covering are equal ...
3
votes
0answers
122 views

What is the function like when its Mobius inversion is $\sum_{w|r, (w,t)=1}\mu(w)q^{r/w}$?

Everyone, I am now reading a paper named The Irreducible Factors of $(cx+d)x^{q^m}-(ax+b)$ over $GF(q)$, http://qjmath.oxfordjournals.org/content/14/1/61.extract. And I’m confused with one of its ...
2
votes
3answers
287 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. ...
4
votes
2answers
781 views

Calculus over finite fields

$P(x,y,z)$ is a polynomial function on an algebraic surface $S$ in $F_{q}^{3}$. Suppose that the derivative of $P$ along any tangent vector of $S$ is zero. Can we say that $P$ is constant on $S$? ...
6
votes
2answers
317 views

Dimension of incomplete matrix over finite fields.

Hi, Suppose one has an incompletely specified $2^n \times 2^n$ matrix over some fixed finite field $\mathbb{F}_{p^k}$. In fact, one knows that the diagonal entries are zero and all other entries are ...
6
votes
3answers
309 views

On the rank of a matrix $S$ with coefficients in $\mathbb F_{2^m}$

Let $\mathbb F$ be a finite field with characteristic 2 and let $S \in M(2k, 2k, \mathbb F)$ be the matrix defined as follows $$ S=\left[\begin{array}{ccccccc} 0 & ...
15
votes
6answers
1k views

Fantastic properties of Z/2Z

Recently I gave a lecture to master's students about some nice properties of the group with two elements $\mathbb{Z}/2\mathbb{Z}$. Typically, I wanted to present simple, natural situations where the ...
3
votes
1answer
182 views

When does a Bohr set have the right size?

Fix a set $ \Gamma\subset \mathbb F_p$, the field with $p$ elements and a parameter $\epsilon>0$. The Bohr set $B(\Gamma,\epsilon)$ consists of those $x$ for which $x\cdot \Gamma\subseteq[-\epsilon ...
4
votes
1answer
162 views

Cyclic subgroups of GL(n,q)

Let $q$ be a prime power. It is well known that every Singer subgroup (subgroup of order $q^n-1$) in $GL(n,q)$ are conjugate. My question is: If $H$ is a cyclic subgroup of order $m$ in $GL(n,q)$, ...
2
votes
1answer
152 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
1answer
101 views

Ranks of higher incidence matrices of designs

In 1978 Doyen, Hubaut and Vandensavel proved that if $S$ is a Steiner triple system $S(2,3,v)$ then the $GF(2)$ rank of its incidence matrix $N$ is $$ Rk_{2}(N)=v-(d_{p}+1), $$ where $d_{p}$ is the ...
2
votes
1answer
179 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 ...
4
votes
1answer
177 views

Full-rank rectangular matrices over GF(2)

Given positive integers $k$, $m$, $n$, let $A$ be an $m \times n$ matrix over $GF(2)$ constructed as follows. Let $X_1, \ldots, X_m$ be independent random subsets of $\{1,\ldots,n\}$ with cardinality ...
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 ...
10
votes
3answers
586 views

Probability of coprime polynomials

Given positive integer $N$, we choose $m_1, m_2, n_1, n_2$ independently and with equal probabilities from $\{0,1,\ldots,N\}$, and let $f_1 = x^{m_1} + (1+x)^{n_1}$ and $f_2 = x^{m_2} + (1+x)^{n_2}$ ...
4
votes
2answers
377 views

Quotient of $Z[x_1,…,x_n]$ by a maximal ideal is a finite field [duplicate]

I am seeing the proof of the Ax-Groethendieck theorem from commutative algebra and I have a problem. How can I prove that if $x_1,...,x_n$ are complex numbers and $I$ is a maximal ideal of ...
1
vote
3answers
166 views

Complete sets of functions

A (finite) set $S$ of boolean functions is called functionally complete if every boolean function can be presented as a finite composition of functions from $S$. For example, $\{ \neg,\wedge \}$ is ...
1
vote
0answers
123 views

Finite fields: alternating sums of values of polynomials

Notation In what follows let $p$ be a (odd, if needed) prime, $e$ a positive integer, $q = p^e$; $\mathbb{F}_q$ will denote a finite field with $q$ elements whose prime subfield will be denoted as ...
4
votes
0answers
182 views

Seeking conceptual explanation of these nice bijections on roots of unity

I proved the following facts by unenlightening calculations. Since the statements are quite clean, I think there should be a conceptual explanation for them, which my proof certainly is not. Let $q$ ...
5
votes
1answer
193 views

Polynomiality of functions over residue rings

Suppose $\mathbb{Z}/m \mathbb{Z}$ is a residue ring for some $m \in \mathbb{N}$. If $m=p$ is a prime number then every function $f:\mathbb{Z}/p \mathbb{Z} \rightarrow \mathbb{Z}/p \mathbb{Z}$ is a ...
6
votes
2answers
367 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$ ...
3
votes
1answer
521 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
1answer
483 views

Trivializing principal bundles on a curve over a finite field

This is related to my question Adelic description of moduli of $G$-bundles on a curve. Let $X$ be a smooth, projective, and geometrically connected curve over a finite field $\mathbb{F}_q$ and $G$ a ...
0
votes
1answer
145 views

Number of Minimal left ideals in the full matrix ring over a finite commutative local ring

Inspired with another QUESTION I would like to know the number of minimal left ideals of $M_n(R)$ in terms of $n$ and $R$ where $R$ is a finite local commutative ring with identity ?
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: ...
4
votes
4answers
694 views

computer algebra system for polynomial algebras over finite fields

Is there a computer algebra system that can do arithmetic over polynomial algebras over finite fields where I can specify the extension? Exempli gratia, if $f(x), g(x) \in ...
8
votes
1answer
270 views

A Balog-Szemeredi-Gowers-type question

A nice Lemma due to Konyagin asserts that for any subset $B \subset \mathbb{F}_p$ holds $$ |B.B - B.B + B.B - B.B + B.B - B.B| \geq \frac{1}{2}\min\{p, |B|^2 \}, $$ where the standard notation for the ...
0
votes
1answer
143 views

trace cotrace Matrix

Hello I want to know whats mean (trace) cotrace matrix. In the context, mapping a matrix (t x n) $\in$ GF($2^m$) to a cotrace matrix (tm x n) $\in$ GF($2$)?
1
vote
2answers
375 views

Equations of elliptic curves

First part of question I have asked on mathoverflow already: http://math.stackexchange.com/questions/467088/explict-form-of-the-equation-of-elliptic-curve 1) Let $E(\mathbb{F}_{q^2})$ is elliptic ...
4
votes
3answers
568 views

Field with cyclic product group

If a field has a cyclic multiplicative group, is it necessarily finite?
14
votes
1answer
191 views

Do mutually dual finite vector spaces have the same orbit cardinalities under a linear group action?

Let $G$ be a finite group acting linearly on a finite dimensional vector space $V$ over a finite field. By Burnside's lemma, $$ |V/G| = \frac 1{|G|} \sum_{g\in G} q^{\dim(ker(g - I))}. $$ Since $g-I$ ...
3
votes
0answers
89 views

Closest sumset to a set

Suppose $A$ is a subset of the finite field with $p$ elements. What is the best approximation of $A$ by a sumset $B+C$ in the sense that $|A\Delta (B+C)|$ is minimal? Of course if $B=A-x$ and ...
5
votes
1answer
355 views

Are there Carlitz analogues of quadratic residues and reciprocity?

Let $q$ be a prime power. I will use the notations of Keith Conrad's Carlitz extensions paper (but I'll work over $\mathbb{F}_q$ rather than $\mathbb{F}_p$). The most general question I'm asking here ...
1
vote
1answer
145 views

probability of having linearly independent sparse vectors over finite fields

Suppose that there are $i< N$ linearly independent $N$-dimensional vectors $\mathbf{v}_1,\mathbf{v}_2,\ldots,\mathbf{v}_i$ over a finite field $\mathbb{F}_q$, whose elements are denoted as ...
5
votes
0answers
200 views

Transferring addition and multiplication over finite fields to $\mathbb{Z}$

It seems to me that the most basic wisdom on why many number-theoretic conjectures are hard is because the interplay between addition and multiplication is subtle and delicate (much of the lay chatter ...
0
votes
1answer
151 views

Existence of nontrivial roots of a homogeneous polynomial over a finite field in extension fields

Consider a homogeneous polynomial, f, of total degree n in n variables, with coefficients in a prime order finite field, GF(p). Are there any general rules regarding the existence of nontrivial roots ...
9
votes
0answers
223 views

Noether-Lefschetz over finite fields

The classical Noether-Lefschetz theorem asserts the following: Over the complex numbers, a very general surface $S\subset \mathbb{P}^3$ has Picard number 1 (that is, $Pic(S)\simeq \mathbb Z$), ...
2
votes
0answers
433 views

Books on advanced galois theory

I have been studying galois theory on my own and find it very fascinating. I have gone through Ian Stewarts book: http://www.amazon.co.uk/Galois-Theory-Third-Chapman-Mathematics/dp/1584883936. I am ...
8
votes
4answers
878 views

The “interplay” between additive and multiplicative structure in a field

A field is an ordered triple $(F, +,\cdot)$ of a set $F$ and binary operations $+,\times$ on $F$ such that $(F,+)$ and $(F\backslash 0,\times)$ are abelian groups satisfying the distributive laws ...