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^...
Joe Silverman's user avatar
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 ...
Alexandre Eremenko's user avatar
24 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'...
KConrad's user avatar
  • 49.5k
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 ...
GH from MO's user avatar
  • 98.2k
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 $...
LeechLattice's user avatar
  • 9,421
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, ...
Max Horn's user avatar
  • 5,112
18 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|$. ...
Mark Wildon's user avatar
  • 10.8k
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, ...
GH from MO's user avatar
  • 98.2k
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 ...
Peter Webb's user avatar
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 ...
Will Sawin's user avatar
  • 135k
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 ...
user44191's user avatar
  • 4,961
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 ...
Peter Scholze's user avatar
16 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 ...
Peter Mueller's user avatar
16 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 ...
Seva's user avatar
  • 22.8k
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})...
Qiaochu Yuan's user avatar
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) ...
js21's user avatar
  • 7,199
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 ...
GH from MO's user avatar
  • 98.2k
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^{...
Fedor Petrov's user avatar
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 ...
dinamo's user avatar
  • 156
14 votes

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

Here is a proof of the experimental fact Joe Silverman discovered. Let $f$ be a polynomial of degree $d$ in $R:=\mathbb{F}_q[x]$. For $I=(f)$, the sum $$1+\sum_{a \in R/I} a^{\# R/I - 1}$$ is equal, ...
Ofir Gorodetsky's user avatar
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" (...
Michael Zieve's user avatar
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 ...
Geoff Robinson's user avatar
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 ...
darij grinberg's user avatar
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 $...
Will Sawin's user avatar
  • 135k
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 $$\...
Will Sawin's user avatar
  • 135k
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.
Daniel Litt's user avatar
  • 22.2k
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$ ...
Will Sawin's user avatar
  • 135k
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 ...
Felipe Voloch's user avatar
12 votes
Accepted

Maximal order of elements in SL(n,q)

Yes. It is shown in the paper Darafsheh, M.R., Order of elements in the groups related to the general linear group., Finite Fields Appl. 11, No. 4, 738-747 (2005). ZBL1147.20043. (Theorem 1) that ...
Igor Rivin's user avatar
  • 95.5k
12 votes
Accepted

Galois action on $p$-adic Tate module of Abelian variety over finite field semisimple?

You're just asking whether Frobenius acts semsimply on the $p$-adic Tate module. We know from Tate's theorem that Frobenius acts semisimply on the $\ell$-adic Tate module, and hence satisfies some ...
Will Sawin's user avatar
  • 135k

Only top scored, non community-wiki answers of a minimum length are eligible