Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The standard definition is that $a\in\mathbb{Z}$ is a primitive root modulo $p$ if the order of $a$ modulo $p$ is $p-1$.

Let me rephrase, to motivate my generalization: $a\in\mathbb{Z}$ is a primitive root modulo $p$ if the linear recurrence defined by $x_0=1$, $x_n=ax_{n-1}$ for $n\geq1$ has maximum possible period in $\mathbb{Z}/p\mathbb{Z}$.

So, we could define $(a_1,\ldots,a_r)\in\mathbb{Z}^r$ to be an $r$-primitive root modulo $p$ when the order $r$ linear recurrence defined by $x_0=\cdots=x_{r-2}=0$, $x_{r-1}=1$, and $x_n=a_1x_{n-1}+\cdots+a_rx_{n-r}$ for $n\geq r$ has the maximum possible period (for such sequences) in $\mathbb{Z}/p\mathbb{Z}$.

Is anything known about the generalized version of primitive roots I've described? I chose my initial values $x_0=\cdots=x_{r-2}=0$, $x_{r-1}=1$ in analogy with the Fibonacci numbers, but is there a standard / most general choice? The starting values affect the period a lot, so it's important to be working with the "right" ones, I guess. What is the maximum achievable period for a linear recurrence in $\mathbb{Z}/p\mathbb{Z}$? An obvious upper bound is $p^r-1$, but it's not clear to me that this is the correct number to replace $p-1$ in the standard definition of primitive root. Is anything known in the direction of Artin's conjecture for "$r$-primitive roots", as I've called them?

Other thoughts: because there is no "formula" for the order of $a$ modulo $p$ (this would amount to a formula for the discrete logarithm), there certainly isn't a formula for the period of the linear recurrence defined by $(a_1,\ldots,a_r)$ modulo $p$. I tried to come up with one for a while before I realized this, so I just wanted to save anyone else the trouble.

share|improve this question
    
The characterization that Voloch gave implies the $r$-primitive root property is independent of the choice of nonzero initial vector $(x\_0, \dots, x\_{r-1})$, since all nonzero vectors are reached by a maximal length cycle. More specifically, if there were a shorter cycle with a nonzero initial value, then there wouldn't be enough elements left in a field with $p^r$ elements to make a disjoint cycle that satisfied the $r$-primitive root property. –  S. Carnahan Jan 12 '10 at 23:29
    
Ah, I see! Thanks for the explanation. –  Zev Chonoles Jan 13 '10 at 23:30
add comment

3 Answers 3

up vote 7 down vote accepted

If $(a_1,\ldots,a_r)$ is an $r$-primitive root in your definition, then the polynomial $x^r-a_1x^{r-1}-\cdots-a_r$ is irreducible in $Z/pZ[x]$ and any of its roots is a generator (i.e. a primitive root) of the multiplicative group of the field of $p^r$ elements and conversely. This maximal period is $p^r-1$. See, e.g., Lidl-Niederreiter Finite Fields.

share|improve this answer
    
Thanks for your answer and reference! I still have some concerns, so I'd appreciate it if you could explain further. For example, I seem to remember that we can only write $x_n=c_1\lambda_1^n+\cdots+c_n\lambda_r^n$, where the $\lambda_i$ are the roots of $X^r-a_1X^{r-1}-\cdots-a_r$ and the $c_i$ are determined by the starting values, if the $\lambda_i$ are in fact all distinct, and $r<p$, so I was worried that some sort of degenerate case could mess any nice characterization up. –  Zev Chonoles Jan 11 '10 at 4:38
    
Furthermore, even if the above conditions are met and $X^r-a_1X^{r-1}-\cdots-a_r$ is irreducible in $\mathbb{Z}/p\mathbb{Z}[X]$, it seems possible that $x_n=c_1\lambda_1^n+\cdots+c_n\lambda_r^n$ could repeat earlier than the period of the $\lambda_i$ individually. This is why I was concerned about the apparent lack of "canonical" starting values: the $c_i$ could cause earlier periodicity than the roots of the polynomial "warrant", in some sense. –  Zev Chonoles Jan 11 '10 at 4:39
    
Of course, we could always reformulate the question to just be about how an element of $\mathbb{Z}[X]$ factors in each $\mathbb{Z}/p\mathbb{Z}[X]$, and ignore the relationship with sequences - which I'm not entirely against, since it seems like an intriguing question all on its own. –  Zev Chonoles Jan 11 '10 at 4:43
add comment

The proof is short enough to give here.

Proposition: A finite subgroup of the multiplicative group of a field is cyclic.

Proof. Let $G$ be a finite subgroup of the multiplicative group of a field $K$. Since $g^{|G|} = 1$ for all $g$ and since polynomials over a field have at most as many roots as their degree, it follows necessarily that $\prod_g (x - g) = x^{|G|} - 1$. By inspecting the roots of the polynomials $x^d - 1, d | |G|$, it follows that $G$ has $\phi(d)$ elements of order $d$, and this condition is equivalent to $G$ being cyclic (indeed it implies that there is at least one element of order $|G|$).

Corollary: $(\mathbb{F}\_{p^n})^{*}$ has an element of order $p^n - 1$. (This gives the primitive element theorem for finite fields.)

Let $\alpha$ be such an element and let $f(x) = x^n - a_{n-1} x^{n-1} - ... - a_0 = \prod_{i=0}^{n-1} (x - \alpha^{p^i})$ be its minimal polynomial. The generating function $\frac{1}{x^n f \left( \frac{1}{x} \right)} \bmod p$ has a partial fraction decomposition containing terms corresponding to $(p^n - 1)^{th}$ roots of unity, so its coefficients necessarily have period exactly $p^n - 1$.

share|improve this answer
add comment

There are good results related to what you are asking. Hans Roskam stated and proved a quadratic analogue of Artin's conjecture (and I think his paper is much easier to read than Hooley's). He studies the density of primes in which a fundamental unit in a real quadratic field has a maximal order.

The paper is titled, "A quadratic Analogue of Artin's Conjecture on Primitive Roots" Journal of Number Theory 81, 93-109.

You can find his papers here and this is also good.

Hope this helps.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.