Saturday, 18 April 2009

nt.number theory - Generalization of primitive roots

The standard definition is that ainmathbbZ is a primitive root modulo p if the order of a modulo p is p1.



Let me rephrase, to motivate my generalization: ainmathbbZ is a primitive root modulo p if the linear recurrence defined by x0=1, xn=axn1 for ngeq1 has maximum possible period in mathbbZ/pmathbbZ.



So, we could define (a1,ldots,ar)inmathbbZr to be an r-primitive root modulo p when the order r linear recurrence defined by x0=cdots=xr2=0, xr1=1, and xn=a1xn1+cdots+arxnr for ngeqr has the maximum possible period (for such sequences) in mathbbZ/pmathbbZ.



Is anything known about the generalized version of primitive roots I've described? I chose my initial values x0=cdots=xr2=0, xr1=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 mathbbZ/pmathbbZ? An obvious upper bound is pr1, but it's not clear to me that this is the correct number to replace p1 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 (a1,ldots,ar) 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.

No comments:

Post a Comment