Generalization of primitive roots - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T16:25:40Z http://mathoverflow.net/feeds/question/11377 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/11377/generalization-of-primitive-roots Generalization of primitive roots Zev Chonoles 2010-01-10T23:28:30Z 2010-01-12T21:52:04Z <p>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$.</p> <p>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}$.</p> <p>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}$.</p> <p>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?</p> <p>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.</p> http://mathoverflow.net/questions/11377/generalization-of-primitive-roots/11381#11381 Answer by Felipe Voloch for Generalization of primitive roots Felipe Voloch 2010-01-11T00:03:47Z 2010-01-11T00:03:47Z <p>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.</p> http://mathoverflow.net/questions/11377/generalization-of-primitive-roots/11382#11382 Answer by Ben Weiss for Generalization of primitive roots Ben Weiss 2010-01-11T00:09:47Z 2010-01-11T00:09:47Z <p>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.</p> <p>The paper is titled, "A quadratic Analogue of Artin's Conjecture on Primitive Roots" Journal of Number Theory 81, 93-109.</p> <p>You can find his papers <a href="http://jtnb.cedram.org/item?id=JTNB_2002__14_1_287_0" rel="nofollow">here</a> and <a href="http://www.sciencedirect.com.proxy.lib.umich.edu/science?_ob=ArticleURL&amp;_udi=B6WKD-45F4XHM-17&amp;_user=99318&amp;_rdoc=1&amp;_fmt=&amp;_orig=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_acct=C000007678&amp;_version=1&amp;_urlVersion=0&amp;_userid=99318&amp;md5=bca22c50f43dd18dbc24c26888640541" rel="nofollow">this is also good</a>.</p> <p>Hope this helps.</p> http://mathoverflow.net/questions/11377/generalization-of-primitive-roots/11390#11390 Answer by Qiaochu Yuan for Generalization of primitive roots Qiaochu Yuan 2010-01-11T01:34:48Z 2010-01-12T21:52:04Z <p>The proof is short enough to give here. </p> <p><strong>Proposition:</strong> A finite subgroup of the multiplicative group of a field is cyclic.</p> <p><em>Proof.</em> 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|$).</p> <p><strong>Corollary:</strong> $(\mathbb{F}_{p^n})^{*}$ has an element of order $p^n - 1$. (This gives the primitive element theorem for finite fields.)</p> <p>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$.</p>