# Generating de Bruijn sequence over Galois fields using primitive polynomial

We define a de Bruijn sequence of order $$k$$ over the set of $$l$$ distinct symbols as a cyclic sequence of length $$l^k$$, containing all possible letters sub-sequences of length $$k$$ exactly once. In the mentioned paper, they say that for any arbitrary Galois field - $$GF(p^n)$$, for $$p$$ a prime number and $$n$$ an integer, a de Bruijn sequence of order $$k$$ over all elements can be generated by the following recursion:

$$\begin{equation} s_i=\theta_{k-1}s_{i-1} + \dots + \theta_0s_{i-k}, \end{equation}$$

with arithmetic performed over $$GF(p^n)$$ and $$\theta_i\in GF(p^n)$$ so the polynomial $$\sum_{i=0}^{k-1}\theta_i x^i$$ is primitive. In Greg Slodkowicz's question, it was mentioned that the considered polynomial seems to be actually $$x^k - \sum_{i=0}^{k-1}\theta_i x^i$$. I find it hard to get the right primitive polynomial by which in the paper they illustrated the construction of the de Bruijn sequence over $$GF(4)$$ with what seems to be $$k=2$$ in Figure 3a. If we have $$GF(4)=\{0,1,2,3\}$$ with the known addition and multiplication:

how does one get, using primitive polynomial and the suggested recursion equation, the generated sequence in the paper in Figure 3a? i.e.,

$$\begin{equation} 011210331302232, \end{equation}$$

so, with the addition of a single $$0$$ to the beginning, we get the de Bruijn sequence over $$GF(4)$$ with k=2.

Looking at the de Bruijn sequences with alphabet $$GF(4)$$ and over $$GF(16)$$ only, as that seems to be your main interest.
I rather think of $$GF(4)$$ as $$GF(4)=\{0,1,\beta,\beta+1\}.$$ If only to match with my notation in this old answer. Commonly $$\alpha$$ is used in place of $$\beta$$, but in that answer I wanted to avoid symbol overload. Does not matter, because we can rename the elements if we so desire.
Here $$\beta$$ satisfies the equation $$\beta^2=\beta+1$$ which together with $$1+1=0$$ determines the arithmetic completely. In your notation my $$\beta$$ can be either $$2$$ or $$3$$ and $$\beta+1$$ is the other. Makes no difference which way you define, because there is an isomorphism of the field $$GF(4)$$ interchanging $$\beta$$ and $$\beta+1$$.
In the linked answer I show that both $$m_1(x)=x^2+x+\beta$$ and $$m_2(x)=x^2+x+\beta+1$$ are primitive polynomials. These are the minimal polynomials of the zeros of $$x^4+x+1$$ over $$GF(4)$$. The other primitive polynomials are the reciprocals (scaled to be monic) $$m_2(x)=\beta x^2m_2(1/x)=x^2+\beta x+\beta$$ and $$m_4(x)=\beta^2 x^2m_1(1/x)=x^2+\beta^2x+\beta.$$ The latter two are the minimal polynomials of the zeros of $$x^4+x^3+1$$, the reciprocal of $$x^4+x+1$$.
This leaves you with four possible recurrency relations \begin{aligned} s_i&=s_{i-1}+\beta s_{i-2},\\ s_i&=s_{i-1}+\beta^2s_{i-2},\\ s_i&=\beta s_{i-1}+\beta s_{i-2},\\ s_i&=\beta^2s_{i-1}+\beta^2s_{i-2}. \end{aligned} Your sequence begins $$0,1,1$$ which rules out the latter two. The first recurrence relation leads to the cycle (starting from $$0,1$$) $$0,1,1,\beta^2,1,0,\beta,\beta,1,\beta,0,\beta^2,\beta^2,\beta,\beta^2,(0,1,1,\ldots),$$ which seems to match with what you want under the labelling $$\beta=3$$, $$\beta^2=2$$. Anyway, we can easily check that the resulting sequence has the de Bruijn -property: every ordered pair of elements (other than $$0,0$$) appears exactly once in the cycle as consecutive entries.