The standard definition is that ainmathbbZ is a primitive root modulo p if the order of a modulo p is p−1.
Let me rephrase, to motivate my generalization: ainmathbbZ is a primitive root modulo p if the linear recurrence defined by x0=1, xn=axn−1 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=xr−2=0, xr−1=1, and xn=a1xn−1+cdots+arxn−r 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=xr−2=0, xr−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 mathbbZ/pmathbbZ? An obvious upper bound is pr−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 (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