36
votes
Accepted
The period of Fibonacci numbers over finite fields
This maybe too elementary for this site, so if your question is closed, you might try asking on MathStackExchange. Many questions about the period can be answered by using the formula
$$ F_n = (A^n-B^...
- 44.2k
28
votes
Algebraic geometry over the complex numbers, and beyond
Algebraic geometry began over the field of reals. What Apollonius of Perga did would be certainly qualified today as algebraic geometry: he classified real plane curves of second order and studied ...
23
votes
The period of Fibonacci numbers over finite fields
I won't address your question about how small the period of $\{F_n \bmod p\}$ can be as $p$ grows, but instead ask if the upper bounds on the period can be achieved infinitely often. For consistency I'...
- 47.8k
22
votes
Accepted
Conjecture: The number of points modulo $p$ of certain elliptic curve is $p$ or $p+2$ for $p$ of form $p=27a^2+27a+7$
The conjecture is true. To prove it, we can restrict to $k=1$ as explained in the comments. Let $\chi$ denote a cubic Dirichlet character modulo $p$; this exists as $p\equiv 1\pmod{3}$, and it is ...
- 90.6k
20
votes
Accepted
(Barely) linearly independent vectors over $\mathbb{Z}/2\mathbb{Z}$
Since every $n$ vectors span a space of dimension $n-1$, the whole set $S$ spans a space of dimension $n-1$, and we can assume that $V$ has dimension $n-1$.
Choose $n-1$ linearly independent vectors $...
- 9,108
18
votes
Accepted
Is hyperelliptic cryptography "practical"?
I am not aware of anybody seriously considering hyperelliptic curves for actual real-world usage, beyond toys, and I would be rather surprised to hear differently from anyone.
As you say, ...
- 4,643
18
votes
Accepted
Does the equation $x^2+x=a$ have an integer solution?
The answer is yes, and in general if $f(x)\in\mathbb{Z}[x]$ is a monic irreducible polynomial whose Galois group contains a cycle of length $\deg f$ (which is always the case when $\deg f$ is prime, ...
- 90.6k
17
votes
Number of commuting pairs (triples, n-tuples) in GL_n(F_q) (and other groups)?
The probability that two elements of a finite group $G$ commute is $k(G)/|G|$, where $k(G)$ is the number of conjugacy classes of $G$. Hence the number of pairs of commuting elements is $k(G)|G|$. ...
- 10.5k
17
votes
Accepted
Steinberg representation for sporadic simple groups?
The approach that I have taken to generalizing the Steinberg module to finite groups other than groups of Lie type is that, in general, the object we should consider is a chain complex, rather than ...
- 186
17
votes
Polynomials which are functionally equivalent over finite fields
The cardinality of $S_f$ is $p^{ \max(0, d+1-p)}$ because $S_f$ consists of polynomials of the form $f + (x^p-x) g$ with $g$ of degree $\leq d-p$.
The fact that such polynomials lie in $S_f$ follows ...
- 126k
16
votes
Accepted
Linear permutations commuting with $x\rightarrow x^{-1}$
The answer is no: a linear transformation of $F$ which commutes with $\phi$ is an automorphism of $F$.
This is a seemingly inelegant but simple argument.
Any map $\psi: F \rightarrow F$ can be ...
- 4,736
16
votes
Is there an $\mathbb{R}$-valued cohomology theory for varieties over $\mathbb{F}_p$?
Let me advertise a conjectural positive answer to a slightly different question. This actually works not only over $\mathbb F_p$ but over its algebraic closure $\overline{\mathbb F}_p$.
Consider the ...
- 17.7k
15
votes
How many Lie and associative algebras over a finite field are there?
Bjorn Poonen addresses this question for commutative (associative, unital) algebras in The moduli space of commutative algebras of finite rank; asymptotically we have
$$q^{\frac{2}{27} n^3 + O(n^{8/3})...
- 112k
15
votes
Accepted
Existence of a polynomial $Q$ of degree $\geq (p-1)/4$ in $\mathbb F_p[x]$ such that $QQ'$ factorizes into distinct linear factors
Such polynomials always exist, examples are Dickson polynomials of the first kind (with parameter $1$). For a positive integer $n$ these degree $n$ polynomials $D_n$ are most conveniently defined ...
- 19.2k
15
votes
Accepted
The maximal subset of a finite field where the sum of any subset is non-zero
I could trace this question down to the paper of Erdős and Heilbronn "On the addition of residue classes mod $p$" (Acta Arith. 17 (1970), 227–229), where it is shown that for a prime $p$, if ...
- 22.2k
14
votes
Accepted
Finite field "contour" sum
What you call finite field contour sums are more usually called exponential sums. Like complex analytic contour integrals, they do not always (or even usually) have a nice exact formula. Instead, ...
- 126k
14
votes
Accepted
Algebraic dynamics in finite fields
There is a growing body of literature on dynamics of rational maps over finite fields. The following paper would seem to be relevant.
Ugolini, S., Graphs associated with the map $x\mapsto x+x^{-1}$ ...
- 44.2k
14
votes
Accepted
Can you use Chevalley‒Warning to prove existence of a solution?
Let $f_i \in \mathbb{F}_q[X_1,\dots,X_n]$ have degree at most $d$ for each $i \in [|1,r|]$, and assume that the affine scheme
$$
X = \operatorname{Spec} \mathbb F_q [x_1,\ldots,x_n]/(f_1, \ldots, f_r)
...
- 7,139
14
votes
Accepted
Distribution of primitive roots, as p varies
Let me adjust your quantity slightly as
$$\tilde D_p(f) := \frac{1}{\phi(p-1)}\sum_{x \in \Phi(p)} f \left( \frac{x}{p} \right),$$
and let me initially impose the natural condition $f(0)=f(1)$. Then I ...
- 90.6k
14
votes
Roots of lacunary polynomials over a finite field
Note that the number of distinct non-zero roots of a polynomial $P(x)$ over $\mathbb{F}_q$ always equals to the minimal degree of a non-zero polynomial belonging to the ideal generated by $P$ and $x^{...
- 94.7k
14
votes
Accepted
Does this degree 12 genus 1 curve have only one point over infinitely many finite fields?
The polynomial you wrote is the product of the four polynomials $x^3 - r y^3 - z^3$, where $r$ is a root of the polynomial $t^4 - t^3 + t^2 - t + 1$. I did not read your reference, but likely they ...
- 156
13
votes
Accepted
An efficient isomorphism between finite fields
Google provides an answer to this question. The first deterministic polynomial time algorithm for this is due to H. W. Lenstra, Jr., in his paper "Finding isomorphisms between finite fields" (...
- 6,299
13
votes
Number of commuting pairs (triples, n-tuples) in GL_n(F_q) (and other groups)?
The number of commuting pairs in any finite group $G$ is well-known to be $k(G)\lvert G\rvert$ where $k(G)$ is the number of conjugacy classes of $G$. There are also well-known generating functions ...
- 40.5k
13
votes
Cubic polynomials over finite fields whose roots are quadratic residues or non-residues
Yes, it does. Here is a stronger claim:
Theorem 1. Let $F$ be a field of characteristic $\neq2$. Let $c\in F$. Let
$r\in F$ be a nonzero square, and let $n_{1},n_{2}\in F$ be such that the
...
- 32.1k
13
votes
Accepted
Cubic polynomials over finite fields whose roots are quadratic residues or non-residues
EDIT: Following a clever observation of user44191 in the comments:
If $f(x)$ is a monic polynomial, and $c$ a number, then the polynomial $xf(x)^2+c$ has a similar property to your example (the case $...
- 126k
13
votes
Accepted
Subgroups of the multiplicative group of a finite field satisfying a certain additive property
If we let $S$ be the set of characters of $\mathbb F_p^\times$ trivial on $G$ then $$\sum_{\chi \in S} \chi(g) = \begin{cases} \frac{p-1}{|G|} & g\in G \\ 0 & g\notin G \end{cases}$$
so $$\...
- 126k
13
votes
Accepted
Pointless groups
Perhaps I'm missing something, but it seems to me that $k=\mathbb{F}_2$, $G=\mathbb{G}_{m, k}$ works, where $H$ is the trivial subgroup.
- 21.7k
12
votes
Accepted
Reinterpreting Galois descent over finite fields
Yes, assuming $X$ is reduced (so that its absolute Frobenius endomorphism is schematically dominant); this really is a formal consequence of the usual descent formalism (despite whatever red herring ...
- 958
12
votes
Accepted
Hypersurface missing just one point
It's $n(q-1)$. We must have
$$\sum_{x_1,\dots,x_n \in \mathbb F_q}f(x_1,\dots,x_n)=f(0,\dots,0) \neq 0$$
but
$$\sum_{x_1,\dots,x_n \in \mathbb F_q} \prod_i x_i^{e_i}$$
vanishes unless each $e_i$ ...
- 126k
12
votes
Accepted
Elliptic-curve related equivalence between fields of different characteristic?
If $\# E(\mathbb{F}_p) = q$ and $j=0$, then the endomorphism ring is an order in the field of third roots of unity so $(p+1-q)^2 - 4p = -3u^2$ for some integer $u$. Now note that $(p+1-q)^2 - 4p$ is ...
- 30k
Only top scored, non community-wiki answers of a minimum length are eligible