Summary: A pair \((n, q)\) with \(q\) a prime power and \(n\) a positive integer for which \(\gcd(n, q) = 1\) is non-standard if one of the following properties holds, which we will show to be equivalent.
\(-\) The group \(\mathcal{U}_{n , q}\) of \(n\)-th roots-of-unity in the splitting field \(\mathbb{F}_{q^m}\) of \(x^n - 1\) over \(\mathbb{F}_q\) is fixed set-wise by an \(\mathbb{F}_q\)-linear map on \(\mathbb{F}_{q^m}\) that is not of the form \(x \longrightarrow \alpha x^{q^j}\).
\(-\) There is a non-cyclic linear recurring sequence \(\mathbf{s}\) of period \(n\) (so with \(\mathbf{s}\) not of the form \(s_i = \alpha \xi^i\) for \(i \geq 0\)) with associated characteristic polynomial being irreducible over \(\mathbb{F}_q\), such that \(\mathcal{U}_{n , q} = \{ s_0, \ldots, s_{n - 1} \} \). In that case, the group \(\mathcal{U}_{n , q}\) is called non-standard by Brison and Nogueira, who studied this phenomenon in a sequence of papers.
\(-\) A \(q\)-ary irreducible cyclic code of length \(n\) has “extra” permutation automorphisms (some well-known examples are the (duals of the) Golay codes and binary simplex codes for \(n \geq 7\)). We will refer to such codes as non-standard irreducible cyclic codes or NSIC-codes.
We first investigate non-standard linear recurring sequence subgroups and establish the equivalence between the first and second of the above properties. Then we investigate permutation automorphisms of general (repeated-root) cyclic codes and irreducible cyclic codes and establish the equivalence between the first and third of these properties. We also introduce a notion of non-standardness for general cyclic codes, and relate it to our earlier definition of NSIC-codes. This paper is the first part of an expanded version of the arXiv paper [arXiv:0807.0595].